Search

A probabilistic propositional logic, endowed with a constructor for asserting compatibility of diagonalisable and bounded observables, is presented and illustrated for reasoning about the random results of projective measurements made on a given quantum state. Simultaneous measurements are assumed to imply that the underlying observables are compatible. A sound and weakly complete axiomatisation is provided relying on the decidable first-order theory of real closed ordered fields. The proposed logic is proved to be a conservative extension of classical propositional logic. [ABSTRACT FROM AUTHOR]

A structure [ABSTRACT FROM AUTHOR]

Tree paths are investigated using first-order logic. The following results are obtained: (i) every definable path can be defined by a first-order formula using at most one parameter chosen from the path itself; (ii) a canonical representation of the formulas that define definable paths is obtained; and (iii) every tree that has only finitely many paths that are not definable is n-equivalent to a tree of which all paths are definable. Moreover, a certain property that might be expected to hold, involving the transfer of n-equivalence between trees, is shown not to be true. [ABSTRACT FROM AUTHOR]

Information about the 2014 European summer meeting of the Association for Symbolic Logic, held in Vienna, Austria on July 14-19 is presented. The event was hosted by the Vienna University of Technology. Topics discussed include theory of classical realizability, applications of logic to number theory, and first-order monadic logic.

Modern Logic has generated a lot of problems for itself through inattention to natural forms of speech. In particular it has had difficulties with a large group of 'logical paradoxes' through its preoccupation with the Predicate Calculus and related structures to the exclusion of other formal structures that represent natural language more fully, and thereby escape these paradoxes. In natural speech the unrecognized forms involved are principally individual referring terms with a non-specific or fictional reference. For, under the influence of the Logical Empiricists, the focus in formal logic has been on individual terms with a specific, factual reference. But a similar point arises with certain predicates, and indeed even the proper concept of a predicate has been lost, producing the most notorious of the standard puzzles: Russell's Paradox. The paper inevitably makes reference to contemporary logical symbolism in places, but its purpose is to show that the only way forward is to use a symbolism that is abbreviatory only, i.e. maps directly onto natural speech. [ABSTRACT FROM AUTHOR]

‘The Principles of the Pure Type Theory’ is a translation of Leon Chwistek's 1922 paper ‘Zasady czystej teorii typów’. It summarizes Chwistek's results from a series of studies of the logic of Whitehead and Russell's Principia Mathematica which were published between 1912 and 1924. Chwistek's main argument involves a criticism of the axiom of reducibility. Moreover, ‘The Principles of the Pure Type Theory’ is a source for Chwistek's views on an issue in Whitehead and Russell's ‘no-class theory of classes’ involving the notion of ‘scope’. [ABSTRACT FROM PUBLISHER]

We prove that the strong polarized relation Due to image rights restrictions multiple line equation(s) cannot be graphically displayed. → Due to image rights restrictions multiple line equation(s) cannot be graphically displayed. is consistent with ZFC, for a singular μ which is a limit of measurable cardinals. [ABSTRACT FROM AUTHOR]

We study first-order logic with two variables FO² and establish a small substructure property. Similar to the small model property for FO² we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be infinite. We apply this technique to analyse the satisfiability problem for FO² under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO² has the finite model property and is complete for non-deterministic exponential time, just as for plain FO². With two equivalence relations, FO² does not have the finite model property, but is shown to be decidable via a construction of regular models that admit finite descriptions even though they may necessarily be infinite. For three or more equivalence relations, FO² is undecidable. [ABSTRACT FROM AUTHOR]

Nominal logic is an extension of first-order logic with equality, name-binding, renaming via name-swapping and freshness of names. Contrarily to lambda-terms, in nominal terms, bindable names, called atoms, and instantiable variables are considered as distinct entities. Moreover, atoms are capturable by instantiations, breaking a fundamental principle of the lambda-calculus. Despite these differences, nominal unification can be seen from a higher-order perspective. From this view, we show that nominal unification can be quadratically reduced to a particular fragment of higher-order unification problems: higher-order pattern unification. We also prove that the translation preserves most generality of unifiers. [ABSTRACT FROM AUTHOR]

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds. [ABSTRACT FROM AUTHOR]

What does it mean to say that logic is formal? The short answer is: it means (or can mean) several different things. In this paper, I argue that there are (at least) eight main variations of the notion of the formal that are relevant for current discussions in philosophy and logic, and that they are structured in two main clusters, namely the formal as pertaining to forms, and the formal as pertaining to rules. To the first cluster belong the formal as schematic; the formal as indifference to particulars; the formal as topic-neutrality; the formal as abstraction from intentional content; the formal as de-semantification. To the second cluster belong the formal as computable; the formal as pertaining to regulative rules; the formal as pertaining to constitutive rules. I analyze each of these eight variations, providing their historical background and raising related philosophical questions. The significance of this work of ‘conceptual archeology’ is that it may enhance clarity in debates where the notion of the formal plays a prominent role (such as debates where it is expected to play a demarcating role), but where it is oftentimes used equivocally and/or imprecisely. [ABSTRACT FROM PUBLISHER]

Abstract: We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest (especially with probability in the picture), we show that they are not equi-expressive. We then consider the pragmatics of dealing with logical omniscience—how to choose an approach and construct an appropriate model. [ABSTRACT FROM AUTHOR]

Abstract: Logical filtering is the process of updating a belief state (set of possible world states) after a sequence of executed actions and perceived observations. In general, it is intractable in dynamic domains that include many objects and relationships. Still, potential applications for such domains (e.g., semantic web, autonomous agents, and partial-knowledge games) encourage research beyond intractability results. In this paper we present polynomial-time algorithms for filtering belief states that are encoded as First-Order Logic (FOL) formulas. Our algorithms are exact in many cases of interest. They accept belief states in FOL without functions, permitting arbitrary arity for predicates, infinite universes of elements, and equality. They enable natural representation with explicit references to unidentified objects and partially known relationships, still maintaining tractable computation. Previous results focus on more general cases that are intractable or permit only imprecise filtering. Our algorithms guarantee that belief-state representation remains compact for STRIPS actions (among others) with unbounded-size domains. This guarantees tractable exact filtering indefinitely for those domains. The rest of our results apply to expressive modeling languages, such as partial databases and belief revision in FOL. [ABSTRACT FROM AUTHOR]

We investigate labeled resolution calculi for hybrid logics with inference rules restricted via selection functions and orders. We start by providing a sound and refutationally complete calculus for the hybrid logic $\mathcal{H}(@,{\downarrow},\mathsf{A})$, even under restrictions by selection functions and orders. Then, by imposing further restrictions in the original calculus, we develop a sound, complete and terminating calculus for the $\mathcal{H}(@)$ sublanguage. The proof scheme we use to show refutational completeness of these calculi is an adaptation of a standard completeness proof for saturation-based calculi for first-order logic that guarantees completeness even under redundancy elimination. In fact, one of the contributions of this article is to show that the general framework of saturation-based proving for first-order logic with equality can be naturally adapted to saturation-based calculi for other languages, in particular modal and hybrid logics. [ABSTRACT FROM AUTHOR]

We prove that given any first order formula Φ in the language L' = {+, ⋅, <, (fi)i∈I, (ci)i∈I}, where the fi are unary function symbols and the ci are constants, one can find an existential formula ψ such that Φ and ψ are equivalent in any L'-structure 〈ℝ, +, ⋅, <, (xci)i∈I, (ci)i∈I〉. [ABSTRACT FROM AUTHOR]

We reformulate, in the context of continuous logic, an oscillation theorem proved by G. Hjorth and give a proof of the theorem in that setting which is similar to, but simpler than. Hjorth's original one. The point of view presented here clarifies the relation between Hjorth's theorem and first-order logic. [ABSTRACT FROM AUTHOR]

In 1952, Quine showed that the problem of reducing a propositional formula to a simplest normal equivalent can be solved in two steps, viz., (i) express the given formula, Φ, equivalently as the disjunction of all its prime implicants, and (ii) find all non-redundant disjunctions of the latter that are equivalent to Φ (Quine1952). However, it seems not generally known that an ingenious form of the same two-step process was published by Hugh McColl in 1878. [ABSTRACT FROM AUTHOR]

This explorative article is organized around a set of questions concerning the concept of a function. First, a summary of certain general facts about functions that are a common coin in contemporary logic is given. Then Frege's attempt at clarifying the nature of functions in his famous paper Function and Concept and in his Grundgesetze is discussed along with some questions which Freges' approach gave rise to in the literature. Finally, some characteristic uses of functional notions to be found in the work of Bernard Bolzano and in Edmund Husserl's early work are presented and elucidated. [ABSTRACT FROM AUTHOR]

We offer an analysis of the disciplinary transformations underwent by mathematical or symbolic logic since its emergence in the late 19th century. Examined are its origins as a hybrid of philosophy and mathematics, the maturity and institutionalisation attained under the label "logic and foundations", a second wave of institutionalisation in the Postwar period, and the institutional developments since 1975 in connection with computer science and with the study of language and informatics. Although some "internal history" is discussed, the main focus is on the emergence, consolidation and convolutions of logic as a discipline, through various professional associations and journals, in centers such as Torino, Göttingen, Warsaw, Berkeley, Princeton, Carnegie Mellon, Stanford, and Amsterdam. [ABSTRACT FROM AUTHOR]

The entire development of modern logic is characterized by various forms of confrontation of what has come to be called proof theory with what has earned the label of model theory. For a long time the widely accepted view was that while model theory captures directly what logical formalisms are about, proof theory is merely our technical means of getting some incomplete grip on this; but in recent decades the situation has altered. Not only did proof theory expand into new realms, generalizing the concept of proof in various directions; many philosophers also realized that meaning may be seen as primarily consisting in certain rules rather than in language-world links. However, the possibility of construing meaning as an inferential role is often seen as essentially compromised by the limits of proof-theoretical means. The aim of this paper is to sort out the cluster of problems besetting logical inferentialism by disentangling and clarifying one of them, namely determining the power of various inferential frameworks as measured by that of explicitly semantic ones. [ABSTRACT FROM AUTHOR]

We show that there is a first order sentence φ(x;a,b,l) such that for every computable partial order 퓟 and Δ20-degree u > 0e, there are Δ20-enumeration degrees a ≤ u, b, and l such that 퓟 ≅ {x : φ(x;a,b,l)}. Allowing 퓟 to be a suitably defined standard model of arithmetic gives a parametefized interpretation of true arithmetic in the Δ20-enumeration degrees. Finally we show that there is a first order sentence that correctly identifies a subset of the standard models, which gives a parameterless interpretation of true arithmetic in the Δ20-enumeration degrees. [ABSTRACT FROM AUTHOR]

In this paper we generalize the MPMA belief update operator by admitting first-order knowledge bases and restricted first-order update formulae. This allows us to consider scenarios which cannot be properly formalized either in the originalMPMA or in other existing approaches to belief update. [ABSTRACT FROM AUTHOR]

This article opposes a view widely accepted in studies concerning the history of modal logic, according to which (i) the approach of C. I. Lewis towards constructing modern modal logic was purely syntactical (i.e. limited to the construction of axiomatic systems S1-S5 of propositional modal logic), and (ii) the notion of a possible world was incorporated into modern logic and philosophy mainly by authors such as Rudolf Carnap and Saul Kripke. The article presents Lewis' definition of a possible world, and his formulation of the truth-conditions of statements containing strict implication as their main connective in terms of possible worlds. The main question of the article is whether it is possible to consider Lewis' work in this area as an early stage of the development of possible world semantics, and if so, in what sense? The article concludes by answering affirmatively, due to soundness and completeness proofs with respect to S5 using Lewis' semantics. [ABSTRACT FROM AUTHOR]

We compare three categorical models of type theory with extensional constructs: setoids over extensional type theory; setoids over intensional type theory and a certain free exact category (the free '?W-pretopos'). By studying the amount of choice available in these categories, we are able show that they are distinct. [ABSTRACT FROM AUTHOR]

There are several ways for defining the notion submodel for Kripke models of intuitionistic first-order logic. In our approach a Kripke model A is a submodel of a Kripke model B if they have the same frame and for each two corresponding worlds Aα and Bα of them, Aα is a subset of Bα and forcing of atomic formulas with parameters in the smaller one, in A and B, are the same. In this case, B is called an extension of A. We characterize theories that are preserved under taking submodels and also those that are preserved under taking extensions as universal and existential theories, respectively. We also study the notion elementary submodel defined in the same style and give some results concerning this notion. In particular, we prove that the relation between each two corresponding worlds of finite Kripke models A ≤ B is elementary extension (in the classical sense) (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Abstract  Though deceptively simple and plausible on the face of it, Craig’s interpolation theorem (published 50 years ago) has proved to be a central logical property that has been used to reveal a deep harmony between the syntax and semantics of first order logic. Craig’s theorem was generalized soon after by Lyndon, with application to the characterization of first order properties preserved under homomorphism. After retracing the early history, this article is mainly devoted to a survey of subsequent generalizations and applications, especially of many-sorted interpolation theorems. Attention is also paid tomethodological considerations, since the Craig theorem and its generalizations were initially obtained by proof-theoretic arguments while most of the applications are model-theoretic in nature. The article concludes with the role of the interpolation property in the quest for “reasonable” logics extending first-order logic within the framework of abstract model theory. [ABSTRACT FROM AUTHOR]

Abstract  Work on how to axiomatize the subtheories of a first-order theory in which only a proper subset of their extra-logical vocabulary is being used led to a theorem on recursive axiomatizability and to an interpolation theorem for first-order logic. There were some fortuitous events and several logicians played a helpful role. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider certain first-order neutral differential system with two parameters. Some existence results of one positive periodic solution and two positive periodic solutions and nonexistence of positive periodic solutions are obtained. Our approach is based on Krasnoselskii fixed point theorem in cones. [Copyright &y& Elsevier]

Abstract: This paper concerns the study of the fragments without implication of the logic of residuated lattices (or monoidal logic, or intuitionistic logic without contraction). We obtain that these fragments are exactly the same fragments as those found in classical logic. As a corollary of this result we obtain that the implication-less fragments of every t-norm based fuzzy logic are exactly the same fragments as those found in classical logic. [Copyright &y& Elsevier]

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order correspondence language, so both can express the same input–output behavior of processes. [ABSTRACT FROM AUTHOR]

In this paper I investigate the logical analysis of statements in which a predicate applies collectively to a plurality of subjects. The standard treatment of such cases in first-order logic is not completely satisfactory, and the search for alternative modes of representation opens up interesting perspectives. I concentrate on the introduction of multigrade predicates, pointing out a number of weaknesses in the current literature on the subject. I argue that the collective/distributive opposition must be located in the logical structure of the statement in question. [ABSTRACT FROM AUTHOR]

In a recent article (2005), the authors proposed the first-order approximation (FOA) index for the measurement of gender occupational segregation across detailed occupational categories. The FOA index can remedy the two inherent limitations—sensitivity and singularity—associated with the ratio index and the association index, especially when applied to the measurement of micro-segregation. Grusky and Levanon (this issue), while acknowledging these limitations, view the FOA index as a misguided effort to remedy the shortcomings of the other indexes. When responding to Grusky and Levanon, the authors address two kinds of controversies. The first aims directly at the methodological reasoning put forward by Grusky and Levanon and Centers on the statistical properties and statistical assumptions embodied in the various measures. The second revolves around different paradigmatic approaches to the study of occupational segregation and centers on different conceptual views of the gender segregation phenomenon. [ABSTRACT FROM AUTHOR]

An algebraization of multi-signature first-order logic without terms is presented. Rather than following the traditional method of choosing a type of algebras and constructing an appropriate variety, as is done in the case of cylindric and polyadic algebras, a new categorical algebraization method is used: The substitutions of formulas of one signature for relation symbols in another are treated in the object language. This enables the automatic generation via an adjunction of an algebraic theory. The algebras of this theory are then used to algebraize first-order logic. [ABSTRACT FROM AUTHOR]

I consider the well-known criticism of Quine's characterization of first-order logical truth that it expands the class of logical truths beyond what is sanctioned by the model-theoretic account. Briefly, I argue that at best the criticism is shallow and can be answered with slight alterations in Quine's account. At worse the criticism is defective because, in part, it is based on a misrepresentation of Quine. This serves not only to clarify Quine's position, but also to crystallize what is and what is not at issue in choosing the model-theoretic account of first-order logical truth over one in terms of substitutions. I conclude by highlighting the need for justifying the belief that the definition of first-order logical truth in terms of models is superior to its definition in terms of substitutions. [ABSTRACT FROM AUTHOR]

For a complete first order theory of Boolean algebras T which has nonisomorphic countable models, we determine the first limit ordinal α = α(T) such that We show that for some and for all other T‘s, A nonprincipal ideal I of B is almost principal, if a is a principal ideal of B} is a maximal ideal of B. We show that the theory of Boolean algebras with an almost principal ideal has complete extensions and characterize them by invariants similar to the Tarski’s invariants. [ABSTRACT FROM AUTHOR]

Kamp’s theorem states that there is a temporal logic with two modalities (“until” and “since”) which is expressively complete for the first-order monadic logic of order over the real line. In this paper we show that there is no temporal logic with finitely many modalities which is expressively complete for the future fragment of first-order monadic logic of order over the real line (a future formula over the real time line is a formula whose truth value at a point is independent of what happened in the past). [Copyright &y& Elsevier]

We study the class of Sperner spaces, a generalized version of affine spaces, as defined in the language of pointline incidence and line parallelity. We show that, although the class of Sperner spaces is a pseudo-elementary class, it is not elementary nor even &Lscr;∞ω-axiomatizable. We also axiomatize the first-order theory of this class. [ABSTRACT FROM AUTHOR]

The article presents abstracts on information and computation which include the managing fragments, boundedness problem for fragments of first-order logic and topology.

The computational complexity of a problem is the amount of resources, such as time or space, required by a machine that solves the problem. The descriptive complexity of problems is the complexity of describing problems in some logical formalism over finite structures. One of the exciting developments in complexity theory is the discovery of a very intimate connection between computational and descriptive complexity. It is this connection between complexity theory and finite-model theory that we term computational model theory.In this overview paper we offer one perspective on computational model theory. Two important observations underly our perspective: (1) while computational devices work on encodings of problems, logic is applied directly to the underlying mathematical structures, and this 'mismatch' complicates the relationship between logic and complexity significantly, and (2) first-order logic has severely limited expressive power on finite structures, and one way to increase the limited expressive power of first-order logic is by adding fixpoint constructs. These observations motivated the introduction of two abstract formalisms: that of finite-variable infinitary logic and that of relational machines. This paper is the story of how these formalisms are used in computational model theory and their interrelationship.Keywords:computational model theory, computational complexity, descriptive complexity, finite-model theory, infinitary logic, relational machines [ABSTRACT FROM PUBLISHER]