We introduce an atomic formula ${\vec{y} \bot_{\vec{x}}\vec{z}}$ intuitively saying that the variables ${\vec{y}}$ are independent from the variables ${\vec{z}}$ if the variables ${\vec{x}}$ are kept constant. We contrast this with dependence logic ${\mathcal{D}}$ based on the atomic formula = ${(\vec{x}, \vec{y})}$ , actually equivalent to ${\vec{y} \bot_{\vec{x}}\vec{y}}$ , saying that the variables ${\vec{y}}$ are totally determined by the variables ${\vec{x}}$ . We show that ${\vec{y} \bot_{\vec{x}}\vec{z}}$ gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence. (...) We show that ${\vec{y} \bot_{\vec{x}}\vec{z}}$ can be used to give partially ordered quantifiers and IF-logic an alternative interpretation without some of the shortcomings related to so called signaling that interpretations using = ${(\vec{x}, \vec{y})}$ have. (shrink)
We try to answer the question which is the “right” foundation of mathematics, second order logic or set theory. Since the former is usually thought of as a formal language and the latter as a first order theory, we have to rephrase the question. We formulate what we call the second order view and a competing set theory view, and then discuss the merits of both views. On the surface these two views seem to be in manifest conflict with each (...) other. However, our conclusion is that it is very difficult to see any real difference between the two. We analyze a phenomenon we call internal categoricity which extends the familiar categoricity results of second order logic to Henkin models and show that set theory enjoys the same kind of internal categoricity. Thus the existence of non-standard models, which is usually taken as a property of first order set theory, and categoricity, which is usually taken as a property of second order axiomatizations, can coherently coexist when put into their proper context. We also take a fresh look at complete second order axiomatizations and give a hierarchy result for second order characterizable structures. Finally we consider the problem of existence in mathematics from both points of view and find that second order logic depends on what we call large domain assumptions, which come quite close to the meaning of the axioms of set theory. (shrink)
We show that for any pair $\phi$ and $\psi$ of contradictory formulas of dependence logic there is a formula $\theta$ of the same logic such that $\phi\equiv\theta$ and $\psi\equiv\neg\theta$. This generalizes a result of Burgess.
We take a fresh look at the logics of informational dependence and independence of Hintikka and Sandu and Väänänen, and their compositional semantics due to Hodges. We show how Hodges’ semantics can be seen as a special case of a general construction, which provides a context for a useful completeness theorem with respect to a wider class of models. We shed some new light on each aspect of the logic. We show that the natural propositional logic carried by the semantics (...) is the logic of Bunched Implications due to Pym and O’Hearn, which combines intuitionistic and multiplicative connectives. This introduces several new connectives not previously considered in logics of informational dependence, but which we show play a very natural rôle, most notably intuitionistic implication. As regards the quantifiers, we show that their interpretation in the Hodges semantics is forced, in that they are the image under the general construction of the usual Tarski semantics; this implies that they are adjoints to substitution, and hence uniquely determined. As for the dependence predicate, we show that this is definable from a simpler predicate, of constancy or dependence on nothing. This makes essential use of the intuitionistic implication. The Armstrong axioms for functional dependence are then recovered as a standard set of axioms for intuitionistic implication. We also prove a full abstraction result in the style of Hodges, in which the intuitionistic implication plays a very natural rôle. (shrink)
We study the expressive power of open formulas of dependence logic introduced in Väänänen [Dependence logic (Vol. 70 of London Mathematical Society Student Texts), 2007]. In particular, we answer a question raised by Wilfrid Hodges: how to characterize the sets of teams definable by means of identity only in dependence logic, or equivalently in independence friendly logic.
The Craig Interpolation Theorem is intimately connected with the emergence of abstract logic and continues to be the driving force of the field. I will argue in this paper that the interpolation property is an important litmus test in abstract model theory for identifying “natural,” robust extensions of first order logic. My argument is supported by the observation that logics which satisfy the interpolation property usually also satisfy a Lindström type maximality theorem. Admittedly, the range of such logics is small.
Dependence is a common phenomenon, wherever one looks: ecological systems, astronomy, human history, stock markets - but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first order logic. Here the syntax and semantics of dependence logic are studied, dependence logic is given an alternative game theoretic (...) semantics, and results about its complexity are proven. This is a graduate textbook suitable for a special course in logic in mathematics, philosophy and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers, with a basic knowledge of logic, interested in new phenomena in logic. (shrink)
We study definability in terms of monotone generalized quantifiers satisfying Isomorphism Closure, Conservativity and Extension. Among the quantifiers with the latter three properties – here called CE quantifiers – one finds the interpretations of determiner phrases in natural languages. The property of monotonicity is also linguistically ubiquitous, though some determiners like an even number of are highly non-monotone. They are nevertheless definable in terms of monotone CE quantifiers: we give a necessary and sufficient condition for such definability. We further identify (...) a stronger form of monotonicity, called smoothness, which also has linguistic relevance, and we extend our considerations to smooth quantifiers. The results lead us to propose two tentative universals concerning monotonicity and natural language quantification. The notions involved as well as our proofs are presented using a graphical representation of quantifiers in the so-called number triangle. (shrink)
We discuss the differences between first-order set theory and second-order logic as a foundation for mathematics. We analyse these languages in terms of two levels of formalization. The analysis shows that if second-order logic is understood in its full semantics capable of characterizing categorically central mathematical concepts, it relies entirely on informal reasoning. On the other hand, if it is given a weak semantics, it loses its power in expressing concepts categorically. First-order set theory and second-order logic are not radically (...) different: the latter is a major fragment of the former. (shrink)
Let K 0 λ be the class of structures $\langle\lambda, , where $A \subseteq \lambda$ is disjoint from a club, and let K 1 λ be the class of structures $\langle\lambda, , where $A \subseteq \lambda$ contains a club. We prove that if $\lambda = \lambda^{ is regular, then no sentence of L λ+κ separates K 0 λ and K 1 λ . On the other hand, we prove that if $\lambda = \mu^+,\mu = \mu^{ , and a forcing axiom (...) holds (and ℵ L 1 = ℵ 1 if μ = ℵ 0 ), then there is a sentence of L λλ which separates K 0 λ and K 1 λ. (shrink)
We prove some results about the limitations of the expressive power of quantifiers on finite structures. We define the concept of a bounded quantifier and prove that every relativizing quantifier which is bounded is already first-order definable (Theorem 3.8). We weaken the concept of congruence closed (see [6]) to weakly congruence closed by restricting to congruence relations where all classes have the same size. Adapting the concept of a thin quantifier (Caicedo [1]) to the framework of finite structures, we define (...) the concept of a meager quantifier. We show that no proper extension of first-order logic by means of meager quantifiers is weakly congruence closed (Theorem 4.9). We prove the failure of the full congruence closure property for logics which extend first-order logic by means of meager quantifiers, arbitrary monadic quantifiers, and the Härtig quantifier (Theorem 6.1). (shrink)
We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type .We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.
In this paper (except in Section 5) all quantifiers are assumedto be so called simple unaryquantifiers, and all models are assumedto be finite. We give a necessary and sufficientcondition for a quantifier to be definablein terms of monotone quantifiers. For amonotone quantifier we give a necessaryand sufficient condition for beingdefinable in terms of a given set of bounded monotonequantifiers. Finally, we give a necessaryand sufficient condition for a monotonequantifier to be definable in terms of agiven monotone quantifier.Our analysis shows that (...) the quantifierat least one half and its relatives behavedifferently than other monotone quantifiers. (shrink)
The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity type t there is a generalized quantifier of type t which is not definable in the extension of first order logic by all generalized quantifiers of type smaller than t. This was proved for unary similarity types by Per Lindström [17] with (...) a counting argument. We extend his method to arbitrary similarity types. (shrink)
Let σ(U) denote the number of automorphisms of a model U of power ω1. We derive a necessary and sufficient condition in terms of trees for the existence of an U with $\omega_1 < \sigma(\mathfrak{U}) < 2^{\omega_1}$. We study the sufficiency of some conditions for σ(U) = 2ω1 . These conditions are analogous to conditions studied by D. Kueker in connection with countable models.
A fundamental notion in a large part of mathematics is the notion of equicardinality. The language with Hartig quantifier is, roughly speaking, a first-order language in which the notion of equicardinality is expressible. Thus this language, denoted by LI, is in some sense very natural and has in consequence special interest. Properties of LI are studied in many papers. In [BF, Chapter VI] there is a short survey of some known results about LI. We feel that a more extensive exposition (...) of these results is needed. The aim of this paper is to give an overview of the present knowledge about the language LI and list a selection of open problems concerning it. After the Introduction $(\S1)$ , in $\S\S2$ and 3 we give the fundamental results about LI. In $\S4$ the known model-theoretic properties are discussed. The next section is devoted to properties of mathematical theories in LI. In $\S6$ the spectra of sentences of LI are discussed, and $\S7$ is devoted to properties of LI which depend on set-theoretic assumptions. The paper finishes with a list of open problem and an extensive bibliography. The bibliography contains not only papers we refer to but also all papers known to us containing results about the language with Hartig quantifier. Contents. $\S1$ . Introduction. $\S2$ . Preliminaries. $\S3$ . Basic results. $\S4$ . Model-theoretic properties of $LI. \S5$ . Decidability of theories with $I. \S6$ . Spectra of LI- sentences. $\S7$ . Independence results. $\S8$ . What is not yet known about LI. Bibliography. (shrink)
Let U and B be two countable relational models of the same first order language. If the models are nonisomorphic, there is a unique countable ordinal α with the property that $\mathfrak{U} \equiv^\alpha_{\infty\omega} \mathfrak{B} \text{but not} \mathfrak{U} \equiv^{\alpha + 1}_{\infty\omega} \mathfrak{B},$ i.e. U and B are L ∞ω -equivalent up to quantifier-rank α but not up to α + 1. In this paper we consider models U and B of cardinality ω 1 and construct trees which have a similar relation (...) to U and B as α above. For this purpose we introduce a new ordering T ≪ T' of trees, which may have some independent interest of its own. It turns out that the above ordinal α has two qualities which coincide in countable models but will differ in uncountable models. Respectively, two kinds of trees emerge from α. We call them Scott trees and Karp trees, respectively. The definition and existence of these trees is based on an examination of the Ehrenfeucht game of length ω 1 between U and B. We construct two models of power ω 1 with 2 ω 1 mutually noncomparable Scott trees. (shrink)
The following problem is studied: How large and how small can the Löwenheim and Hanf numbers of unbounded logics be in relation to the most common large cardinals? The main result is that the Löwenheim number of the logic with the Härtig-quantifier can be consistently put in between any two of the first weakly inaccessible, the first weakly Mahlo, the first weakly compact, the first Ramsey, the first measurable and the first supercompact cardinals.
