Source author record

Jouko Väänänen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO Logic in Computer Science

Catalog footprint

Research overview

19works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Modular SAT-based techniques for reasoning tasks in team semantics

We study the complexity of reasoning tasks for logics in team semantics. Our main focus is on the data complexity of model checking but we also derive new results for logically defined counting and enumeration problems. Our approach is based on modular reductions of these problems into the corresponding problems of various classes of Boolean formulas. We illustrate our approach via several new tractability/intractability results.

preprint2022arXiv

On highly equivalent non-isomorphic countable models of arithmetic and set theory

It is well-known that the first order Peano axioms PA have a continuum of non-isomorphic countable models. The question, how close to being isomorphic such countable models can be, seems to be less investigated. A measure of closeness to isomorphism of countable models is the length of back-and-forth sequences that can be established between them. We show that for every countable ordinal alpha there are countable non-isomorphic models of PA with a back-and-forth sequence of length alpha between them. This implies that the Scott height (or rank) of such models is bigger than $α$ . We also prove the same result for models of ZFC.

preprint2020arXiv

Bounded Symbiosis and Upwards Reflection

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

preprint2020arXiv

Inner Models from Extended Logics: Part 1

If we replace first order logic by second order logic in the original definition of Gödel's inner model $L$ , we obtain HOD. In this paper we consider inner models that arise if we replace first order logic by a logic that has some, but not all, of the strength of second order logic. Typical examples are the extensions of first order logic by generalized quantifiers, such as the Magidor-Malitz quantifier, the cofinality quantifier, or stationary logic. Our first set of results show that both $L$ and HOD manifest some amount of {\em formalism freeness} in the sense that they are not very sensitive to the choice of the underlying logic. Our second set of results shows that the cofinality quantifier gives rise to a new robust inner model between $L$ and HOD. We show, among other things, that assuming a proper class of Woodin cardinals the regular cardinals $>\aleph_1$ of $V$ are weakly compact in the inner model arising from the cofinality quantifier and the theory of that model is (set) forcing absolute and independent of the cofinality in question. We do not know whether this model satisfies the Continuum Hypothesis, assuming large cardinals, but we can show, assuming three Woodin cardinals and a measurable above them, that if the construction is relativized to a real, then on a cone of reals the Continuum Hypothesis is true in the relativized model.

preprint2020arXiv

Tracing Internal Categoricity

Informally speaking, the categoricity of an axiom system means that its non-logical symbols have only one possible interpretation that renders the axioms true. Although non-categoricity has become ubiquitous in the second half of the 20th century whether one looks at number theory, geometry or analysis, the first axiomatizations of such mathematical theories by Dedekind, Hilbert, Huntington, Peano and Veblen were indeed categorical. A common resolution of the difference between the earlier categorical axiomatizations and the more modern non-categorical axiomatizations is that the latter derive their non-categoricity from Skolem's Paradox and Gödel's Incompleteness Theorems, while the former, being second order, suffer from a heavy reliance on metatheory, where the Skolem-Gödel phenomenon re-emerges. Using second order meta-theory to avoid non-categoricity of the meta-theory would only seem to lead to an infinite regress. In this paper we maintain that internal categoricity breaks this traditional picture. It applies to both first and second order axiomatizations, although in the first order case we have so far only examples. It does not depend on the meta-theory in a way that would lead to an infinite regress. And it covers the classical categoricity results of early researchers. In the first order case it is weaker than categoricity itself, and in the second order case stronger. We give arguments suggesting that internal categoricity is the "right" concept of categoricity.

preprint2016arXiv

A dichotomy theorem for the generalized Baire space and elementary embeddability at uncountable cardinals

We consider the following dichotomy for $Σ^0_2$ finitary relations $R$ on analytic subsets of the generalized Baire space for $κ$ : either all $R$ -independent sets are of size at most $κ$ , or there is a $κ$ -perfect $R$ -independent set. This dichotomy is the uncountable version of a result found in (W. Kubiś, Proc. Amer. Math. Soc. 131 (2003), no 2.:619--623) and in (S. Shelah, Fund. Math. 159 (1999), no. 1:1--50). We prove that the above statement holds assuming $\Diamond_κ$ and the set theoretical hypothesis $I^-(κ)$ , which is the modification of the hypothesis $I(κ)$ suitable for limit cardinals. When $κ$ is inaccessible, or when $R$ is a closed binary relation, the assumption $\Diamond_κ$ is not needed. We obtain as a corollary the uncountable version of a result by G. Sági and the first author (Log. J. IGPL 20 (2012), no. 6:1064--1082) about the $κ$ -sized models of a $Σ^1_1(L_{κ^+κ})$ -sentence when considered up to isomorphism, or elementary embeddability, by elements of a $K_κ$ subset of ${}^κκ$ . The role of elementary embeddings can be replaced by a more general notion that also includes embeddings, as well as the maps preserving $L_{λμ}$ for $ω\leqμ\leqλ\leqκ$ and the finite variable fragments of these logics.

preprint2016arXiv

A Logic for Arguing About Probabilities in Measure Teams

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.

preprint2016arXiv

Dependence Logic in Pregeometries and $ω$ -Stable Theories

We present a framework for studying the concept of independence in a general context covering database theory, algebra and model theory as special cases. We show that well-known axioms and rules of independence for making inferences concerning basic atomic independence statements are complete with respect to a variety of semantics. Our results show that the uses of independence concepts in as different areas as database theory, algebra and model theory, can be completely characterized by the same axioms. We also consider concepts related to independence, such as dependence.

preprint2016arXiv

Quantum Team Logic and Bell's Inequalities

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.

preprint2014arXiv

The Logic of Approximate Dependence

We extend the treatment of functional dependence, the basic concept of dependence logic, to include the possibility of dependence with a limited number of exceptions. We call this approximate dependence. The main result of the paper is a Completeness Theorem for approximate dependence atoms. We point out some problematic features of this which suggests that we should consider multi-teams, not just teams.

preprint2013arXiv

On Dependence Logic

We give an overview of some developments in dependence and independence logic. This is a tiny selection, intended for a newcomer, from a rapidly growing literature on the topic. Furthermore, we discuss conditional independence atoms and we prove that conditional and non-conditional independence logic are equivalent. Finally, we briefly discuss an application of our logics to belief representation.

preprint2013arXiv

Positional strategies in long Ehrenfeucht-Fraissé games

We prove that it is relatively consistent with ZF + CH that there exist two models of cardinality \aleph_2 such that the second player has a winning strategy in the Ehrenfeucht-Fraïssé-game of length ω_1 but there is no σ-closed back-and-forth set for the two models. If CH fails, no such pairs of models exist.

preprint2012arXiv

An Ehrenfeucht-Fraïssé Game for $L_{ω_1ω}$

Ehrenfeucht-Fraisse games are very useful in studying separation and equivalence results in logic. The standard finite Ehrenfeucht-Fraisse game characterizes equivalence in first order logic. The standard Ehrenfeucht-Fraisse game in infinitary logic characterizes equivalence in $L_{\inftyω}$ . The logic $L_{ω_1ω}$ is the extension of first order logic with countable conjunctions and disjunctions. There was no Ehrenfeucht-Fraisse game for $L_{ω_1ω}$ in the literature. In this paper we develop an Ehrenfeucht-Fraisse Game for $L_{ω_1ω}$ . This game is based on a game for propositional and first order logic introduced by Hella and Vaananen. Unlike the standard Ehrenfeucht-Fraisse 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.

preprint2012arXiv

Axiomatizing first order consequences in dependence logic

Dependence logic, introduced in [8], 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.

preprint2012arXiv

Dependence and Independence

We introduce an atomic formula intuitively saying that given variables are independent from given other variables if a third set of variables is kept constant. We contrast this with dependence logic. We show that our independence atom gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence.

preprint2012arXiv

On Second-order Characterizability

We investigate the extent of second order characterizable structures by extending Shelah's Main Gap dichotomy to second order logic. For this end we consider a countable complete first order theory T. We show that all sufficiently large models of T have a characterization up to isomorphism in the extension of second order logic obtained by adding a little bit of infinitary logic if and only if T is shallow superstable with NDOP and NOTOP. Our result relies on cardinal arithmetic assumptions. Under weaker assumptions we get consistency results or alternatively results about second order logic with Henkin semantics.

preprint2012arXiv

The size of a formula as a measure of complexity

We introduce a refinement of the usual Ehrenfeucht-Fra\"ıssé game. The new game will help us make finer distinctions than the traditional one. In particular, it can be used to measure the size formulas needed for expressing a given property. We will give two versions of the game: the first version characterizes the size of formulas in propositional logic, and the second version works for first-order predicate logic.

preprint1997arXiv

Stationary sets and infinitary logic

Let K^0_lambda be the class of structures < lambda,<,A>, where A subseteq lambda is disjoint from a club, and let K^1_lambda be the class of structures < lambda,<,A>, where A subseteq lambda contains a club. We prove that if lambda = lambda^{< kappa} is regular, then no sentence of L_{lambda^+ kappa} separates K^0_lambda and K^1_lambda. On the other hand, we prove that if lambda = mu^+, mu = mu^{< mu}, and a forcing axiom holds (and aleph_1^L= aleph_1 if mu = aleph_0), then there is a sentence of L_{lambda lambda} which separates K^0_lambda and K^1_lambda .

preprint1993arXiv

On the number of automorphism of uncontable models

Let s(A) denote the number of automorphisms of a model A of power omega_1. We derive a necessary and sufficient condition in terms of trees for the existence of an A with omega_1 < s(A) < 2^{omega_1}. We study the sufficiency of some conditions for s(A)=2^{omega_1}. These conditions are analogous to conditions studied by D.Kueker in connection with countable models.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jouko Väänänen

Research overview

Is this your work?

19 publications

Modular SAT-based techniques for reasoning tasks in team semantics

On highly equivalent non-isomorphic countable models of arithmetic and set theory

Bounded Symbiosis and Upwards Reflection

Inner Models from Extended Logics: Part 1

Tracing Internal Categoricity

A dichotomy theorem for the generalized Baire space and elementary embeddability at uncountable cardinals

A Logic for Arguing About Probabilities in Measure Teams

Dependence Logic in Pregeometries and $ω$ -Stable Theories

Quantum Team Logic and Bell's Inequalities

The Logic of Approximate Dependence

On Dependence Logic

Positional strategies in long Ehrenfeucht-Fraissé games

An Ehrenfeucht-Fraïssé Game for $L_{ω_1ω}$

Axiomatizing first order consequences in dependence logic

Dependence and Independence

On Second-order Characterizability

The size of a formula as a measure of complexity

Stationary sets and infinitary logic

On the number of automorphism of uncontable models

See the researcher in context

Building this map preview

Jouko Väänänen

Research overview

Is this your work?

19 publications

Modular SAT-based techniques for reasoning tasks in team semantics

On highly equivalent non-isomorphic countable models of arithmetic and set theory

Bounded Symbiosis and Upwards Reflection

Inner Models from Extended Logics: Part 1

Tracing Internal Categoricity

A dichotomy theorem for the generalized Baire space and elementary embeddability at uncountable cardinals

A Logic for Arguing About Probabilities in Measure Teams

Dependence Logic in Pregeometries and ωωω-Stable Theories

Quantum Team Logic and Bell's Inequalities

The Logic of Approximate Dependence

On Dependence Logic

Positional strategies in long Ehrenfeucht-Fraissé games

An Ehrenfeucht-Fraïssé Game for Lω1ωL_{ω_1ω}Lω1​ω​

Axiomatizing first order consequences in dependence logic

Dependence and Independence

On Second-order Characterizability

The size of a formula as a measure of complexity

Stationary sets and infinitary logic

On the number of automorphism of uncontable models

See the researcher in context

Building this map preview

Dependence Logic in Pregeometries and $ω$ -Stable Theories

An Ehrenfeucht-Fraïssé Game for $L_{ω_1ω}$