Source author record

Jouko Väänänen

Jouko Väänänen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

19works
2topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

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.

Published work

19 published item(s)

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

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.

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

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 .