Jouko A Vaananen

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict‐II11 reflection (or ∑1‐compactness). We show that admissible sets such as H(ω2) and Lω2 which fail to have strict‐II11 reflection, may or may not, depending on set‐theoretic hypotheses satisfy one or both of these weaker forms. Mathematics Subject Classification: 03C70, 03C75.

We show, assuming PD, that every complete finitely axiomatized second-order theory with a countable model is categorical, but that there is, assuming again PD, a complete recursively axiomatized second-order theory with a countable model which is non-categorical. We show that the existence of even very large (e.g., supercompact) cardinals does not imply the categoricity of all finitely axiomatizable complete second-order theories. More exactly, we show that a non-categorical complete finitely axiomatized second-order theory can always be obtained by (set) forcing. We also show that the categoricity of all finite complete second-order theories with a model of a certain singular cardinality $\kappa $ of uncountable cofinality can be forced over any model of set theory. Previously, Solovay had proved, assuming $V=L$, that every complete finitely axiomatized second-order theory (with or without a countable model) is categorical, and that in a generic extension of L there is a complete finitely axiomatized second-order theory with a countable model which is non-categorical.

In Bagaria (J Symb Log 81(2), 584–604, 2016), Bagaria and Väänänen developed a framework for studying the large cardinal strength of _downwards_ Löwenheim-Skolem theorems and related set theoretic reflection properties. The main tool was the notion of _symbiosis_, originally introduced by the third author in Väänänen (Applications of set theory to generalized quantifiers. PhD thesis, University of Manchester, 1967); Väänänen (in Logic Colloquium ’78 (Mons, 1978), volume 97 of Stud. Logic Foundations Math., pages 391–421. North-Holland, Amsterdam 1979) _Symbiosis_ provides a way of relating model theoretic properties of strong logics to definability in set theory. In this paper we continue the systematic investigation of _symbiosis_ and apply it to _upwards_ Löwenheim-Skolem theorems and reflection principles. To achieve this, we need to adapt the notion of _symbiosis_ to a new form, called _bounded symbiosis_. As one easy application, we obtain upper and lower bounds for the large cardinal strength of upwards Löwenheim–Skolem-type principles for second order logic.

We introduce a new inner model [Formula: see text] arising from stationary logic. We show that assuming a proper class of Woodin cardinals, or alternatively PFA, the regular uncountable cardinals of [Formula: see text] are measurable in the inner model [Formula: see text] and [Formula: see text] satisfies CH. Moreover, assuming a proper class of Woodin cardinals, the theory of [Formula: see text] is (set) forcing absolute. We introduce an auxiliary concept that we call Club Determinacy, which simplifies the construction of [Formula: see text] greatly but may have also independent interest. Based on Club Determinacy, we introduce the concept of aa-mouse which we use to prove CH and other properties of the inner model [Formula: see text].

In Bagaria (J Symb Log 81(2), 584–604, 2016), Bagaria and Väänänen developed a framework for studying the large cardinal strength of downwards Löwenheim-Skolem theorems and related set theoretic reflection properties. The main tool was the notion of symbiosis, originally introduced by the third author in Väänänen (Applications of set theory to generalized quantifiers. PhD thesis, University of Manchester, 1967); Väänänen (in Logic Colloquium ’78 (Mons, 1978), volume 97 of Stud. Logic Foundations Math., pages 391–421. North-Holland, Amsterdam 1979) Symbiosis provides a way of relating model theoretic properties of strong logics to definability in set theory. In this paper we continue the systematic investigation of symbiosis and apply it to upwards Löwenheim-Skolem theorems and reflection principles. To achieve this, we need to adapt the notion of symbiosis to a new form, called bounded symbiosis. As one easy application, we obtain upper and lower bounds for the large cardinal strength of upwards Löwenheim–Skolem-type principles for second order logic.

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.

We show that the predicate “x is the power set of y” is Σ1(Card)$\Sigma _1(\operatorname{Card})$‐definable, if V = L[E] is an extender model constructed from a coherent sequences of extenders, provided that there is no inner model with a Woodin cardinal. Here Card$\operatorname{Card}$ is a predicate true of just the infinite cardinals. From this we conclude: the validities of second order logic are reducible to VI$V_I$, the set of validities of the Härtig quantifier logic. Further we show that if no L[E] model has a cardinal strong up to one of its ℵ‐fixed points, and ℓI$\ell _{I}$, the Löwenheim number of this logic, is less than the least weakly inaccessible δ, then (i) ℓI$\ell _I$ is a limit of measurable cardinals of K, and (ii) the Weak Covering Lemma holds at δ.

Lindström’s Theorem characterizes first order logic as the maximal logic satisfying the Compactness Theorem and the Downward Löwenheim-Skolem Theorem. If we do not assume that logics are closed under negation, there is an obvious extension of first order logic with the two model theoretic properties mentioned, namely existential second order logic. We show that existential second order logic has a whole family of proper extensions satisfying the Compactness Theorem and the Downward Löwenheim-Skolem Theorem. Furthermore, we show that in the context of negation-less logics, _positive logics_, as we call them, there is no strongest extension of first order logic with the Compactness Theorem and the Downward Löwenheim-Skolem Theorem.

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.