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 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 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)

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.

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 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 the categoricity of second-order Peano axioms can be proved from the comprehension axioms. We also show that the categoricity of second-order Zermelo–Fraenkel axioms, given the order type of the ordinals, can be proved from the comprehension axioms. Thus these well-known categoricity results do not need the so-called “full” second-order logic, the Henkin second-order logic is enough. We also address the question of “consistency” of these axiom systems in the second-order sense, that is, the question of existence of (...) models for these systems. In both cases we give a consistency proof, but naturally we have to assume more than the mere comprehension axioms. (shrink)

If we replace first-order logic by second-order logic in the original definition of Gödel’s inner model L, we obtain the inner model of hereditarily ordinal definable sets [33]. In this paper...

Theoria, Volume 87, Issue 4, Page 986-1000, August 2021.

A logical approach to Bell's Inequalities of quantum mechanics has been introduced by Abramsky and Hardy [2]. We point out that the logical Bell's Inequalities of [2] are provable in the probability logic of Fagin, Halpern and Megiddo [4]. Since it is now considered empirically established that quantum mechanics violates Bell's Inequalities, we introduce a modified probability logic, that we call quantum team logic, in which Bell's Inequalities are not provable, and prove a Completeness Theorem for this logic. For this (...) end we generalise the team semantics of dependence logic [7] first to probabilistic team semantics, and then to what we call quantum team semantics. (shrink)

Dependence logic, introduced in Väänänen [11], cannot be axiomatized. However, first-order consequences of dependence logic sentences can be axiomatized, and this is what we shall do in this paper. We give an explicit axiomatization and prove the respective Completeness Theorem.

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

The semantics of the independence friendly logic of Hintikka and Sandu is usually defined via a game of imperfect information. We give a definition in terms of a game of perfect information. We also give an Ehrenfeucht-Fraïssé game adequate for this logic and use it to define a Distributive Normal Form for independence friendly logic.

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 ask, when is a property of a model a logical property? According to the so-called Tarski–Sher criterion this is the case when the property is preserved by isomorphisms. We relate this to model-theoretic characteristics of abstract logics in which the model class is definable. This results in a graded concept of logicality in the terminology of Sagi [46]. We investigate which characteristics of logics, such as variants of the Löwenheim–Skolem theorem, Completeness theorem, and absoluteness, are relevant from the logicality (...) point of view, continuing earlier work by Bonnay, Feferman, and Sagi. We suggest that a logic is the more logical the closer it is to first order logic. We also offer a refinement of the result of McGee that logical properties of models can be expressed in $L_{\infty \infty }$ if the expression is allowed to depend on the cardinality of the model, based on replacing $L_{\infty \infty }$ by a “tamer” logic. (shrink)

Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of d-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements are modeled (...) by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics. (shrink)

We study descriptive set theory in the space ω1 ω 1 by letting trees with no uncountable branches play a similar role as countable ordinals in traditional descriptive set theory. By using such trees, we get, for example, a covering property for the class of Π 1 1 -sets of ω1 ω 1 . We call a family U of trees universal for a class V of trees if $\mathscr{U} \subseteq \mathscr{V}$ and every tree in V can be order-preservingly mapped (...) into a tree in U. It is well known that the class of countable trees with no infinite branches has a universal family of size ℵ 1 . We shall study the smallest cardinality of a universal family for the class of trees of cardinality ≤ℵ 1 with no uncountable branches. We prove that this cardinality can be 1 (under ¬CH) and any regular cardinal κ which satisfies ℵ 2 ≤ κ ≤ 2 ℵ 1 (under CH). This bears immediately on the covering property of the Π 1 1 -subsets of the space ω1 ω 1 . We also study the possible cardinalities of definable subsets of ω1 ω 1 . We show that the statement that every definable subset of ω1 ω 1 has cardinality $ or cardinality 2 ω1 is equiconsistent with ZFC (if n ≥ 3) and with ZFC plus an inaccessible (if n = 2). Finally, we define an analogue of the notion of a Borel set for the space ω1 ω 1 and prove a Souslin-Kleene type theorem for this notion. (shrink)

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)

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)

We use sets of assignments, a.k.a. teams, and measures on them to define probabilities of first-order formulas in given data. We then axiomatise first-order properties of such probabilities and prove a completeness theorem for our axiomatisation. We use the Hardy–Weinberg Principle of biology and the Bell’s Inequalities of quantum physics as examples.

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.

We show that a coherent theory of partially ordered connectives can be developed along the same line as partially ordered quantification. We estimate the expressive power of various partially ordered connectives and use methods like Ehrenfeucht games and infinitary logic to get various undefinability results.

We show that if $$ satisfies the first-order Zermelo–Fraenkel axioms of set theory when the membership relation is ${ \in _1}$ and also when the membership relation is ${ \in _2}$, and in both cases the formulas are allowed to contain both ${ \in _1}$ and ${ \in _2}$, then $\left \cong \left$, and the isomorphism is definable in $$. This extends Zermelo’s 1930 theorem in [6].

We show that, assuming the consistency of a supercompact cardinal, the first inaccessible cardinal can satisfy a strong form of a Löwenheim–Skolem–Tarski theorem for the equicardinality logic L, a logic introduced in [5] strictly between first order logic and second order logic. On the other hand we show that in the light of present day inner model technology, nothing short of a supercompact cardinal suffices for this result. In particular, we show that the Löwenheim–Skolem–Tarski theorem for the equicardinality logic at (...) κ implies the Singular Cardinals Hypothesis above κ as well as Projective Determinacy. (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 typetthere is a generalized quantifier of typetwhich is not definable in the extension of first order logic by all generalized quantifiers of type smaller thant. 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 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)

Trees are natural generalizations of ordinals and this is especially apparent when one tries to find an uncountable analogue of the concept of the Scott-rank of a countable structure. The purpose of this paper is to introduce new methods in the study of an ordering between trees whose analogue is the usual ordering between ordinals. For example, one of the methods is the tree-analogue of the successor operation on the ordinals.

I will give a brief overview of Saharon Shelah’s work in mathematical logic. I will focus on three transformative contributions Shelah has made: stability theory, proper forcing and PCF theory. The first is in model theory and the other two are in set theory.

In so-called full second-order logic, the second-order variables range over all subsets and relations of the domain in question. In so-called Henkin second-order logic, every model is endowed with a set of subsets and relations which will serve as the range of the second-order variables. In our Boolean-valued second-order logic, the second-order variables range over all Boolean-valued subsets and relations on the domain. We show that under large cardinal assumptions Boolean-valued second-order logic is more robust than full second-order logic. Its (...) validity is absolute under forcing, and its Hanf and Löwenheim numbers are smaller than those of full second-order logic. (shrink)

§1. Introduction. After the pioneering work of Mostowski [29] and Lindström [23] it was Jon Barwise's papers [2] and [3] that brought abstract model theory and generalized quantifiers to the attention of logicians in the early seventies. These papers were greeted with enthusiasm at the prospect that model theory could be developed by introducing a multitude of extensions of first order logic, and by proving abstract results about relationships holding between properties of these logics. Examples of such properties areκ-compactness.Any set (...) of sentences of cardinality ≤ κ, every finite subset of which has a model, has itself a model.Löwenheim-Skolem Theorem down toκ.If a sentence of the logic has a model, it has a model of cardinality at most κ.Interpolation Property.If ϕ and ψ are sentences such that ⊨ ϕ → Ψ, then there is θ such that ⊨ ϕ → θ, ⊨ θ → Ψ and the vocabulary of θ is the intersection of the vocabularies of ϕ and Ψ.Lindstrom's famous theorem characterized first order logic as the maximal ℵ0-compact logic with Downward Löwenheim-Skolem Theorem down to ℵ0. With his new concept of absolute logics Barwise was able to get similar characterizations of infinitary languagesLκω. But hopes were quickly frustrated by difficulties arising left and right, and other areas of model theory came into focus, mainly stability theory. No new characterizations of logics comparable to the early characterization of first order logic given by Lindström and of infinitary logic by Barwise emerged. What was first called soft model theory turned out to be as hard as hard model theory. (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)

Trees are natural generalizations of ordinals and this is especially apparent when one tries to find an uncountable analogue of the concept of the Scott-rank of a countable structure. The purpose of this paper is to introduce new methods in the study of an ordering between trees whose analogue is the usual ordering between ordinals. For example, one of the methods is the tree-analogue of the successor operation on the ordinals.

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)

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)

We show that many singular cardinals λ above a strongly compact cardinal have regular ultrafilters D that violate the finite square principle $\square _{\lambda ,D}^{\mathit{fin}}$ introduced in [3]. For such ultrafilters D and cardinals λ there are models of size λ for which Mλ / D is not λ⁺⁺-universal and elementarily equivalent models M and N of size λ for which Mλ / D and Nλ / D are non-isomorphic. The question of the existence of such ultrafilters and models was (...) raised in [1]. (shrink)

In this paper we develop an Ehrenfeucht‐Fraïssé game for. Unlike the standard Ehrenfeucht‐Fraïssé games which are modeled solely after the behavior of quantifiers, this new game also takes into account the behavior of connectives in logic. We prove the adequacy theorem for this game. We also apply the new game to prove complexity results about infinite binary strings.

We show that a strong form of the so called Lindström’s Theorem [4] fails to generalize to extensions of L κ ω and L κ κ : For weakly compact κ there is no strongest extension of L κ ω with the (κ,κ)-compactness property and the Löwenheim-Skolem theorem down to κ. With an additional set-theoretic assumption, there is no strongest extension of L κ κ with the (κ,κ)-compactness property and the Löwenheim-Skolem theorem down to <κ.

We define a logic capable of expressing dependence of a variable on designated variables only. Thus has similar goals to the Henkin quantifiers of [4] and the independence friendly logic of [6] that it much resembles. The logic achieves these goals by realizing the desired dependence declarations of variables on the level of atomic formulas. By [3] and [17], ability to limit dependence relations between variables leads to existential second order expressive power. Our avoids some difficulties arising in the original (...) independence friendly logic from coupling the dependence declarations with existential quantifiers. As is the case with independence friendly logic, truth of is definable inside . We give such a definition for in the spirit of [11] and [2] and [1]. (shrink)