Let ${\cal T}$ be any of the three canonical truth theories CT^− (compositional truth without extra induction), FS^− (Friedman–Sheard truth without extra induction), or KF^− (Kripke–Feferman truth without extra induction), where the base theory of ${\cal T}$ is PA. We establish the following theorem, which implies that ${\cal T}$ has no more than polynomial speed-up over PA. Theorem.${\cal T}$is feasibly reducible to PA, in the sense that there is a polynomial time computable function f such that for every ${\cal T}$-proof (...) π of an arithmetical sentence ϕ, f(π) is a PA-proof of ϕ. (shrink)

By a well-known result of Kotlarski et al., first-order Peano arithmetic \ can be conservatively extended to the theory \ of a truth predicate satisfying compositional axioms, i.e., axioms stating that the truth predicate is correct on atomic formulae and commutes with all the propositional connectives and quantifiers. This result motivates the general question of determining natural axioms concerning the truth predicate that can be added to \ while maintaining conservativity over \. Our main result shows that conservativity fails even (...) for the extension of \ obtained by the seemingly weak axiom of disjunctive correctness \ that asserts that the truth predicate commutes with disjunctions of arbitrary finite size. In particular, \ implies \\). Our main result states that the theory \ coincides with the theory \ obtained by adding \-induction in the language with the truth predicate. This result strengthens earlier work by Kotlarski and Cieśliński. For our proof we develop a new general form of Visser’s theorem on non-existence of infinite descending chains of truth definitions and prove it by reduction to Gödel’s second incompleteness theorem, rather than by using the Visser–Yablo paradox, as in Visser’s original proof. (shrink)

We present a novel, perspicuous framework for building iterated ultrapowers. Furthermore, our framework naturally lends itself to the construction of a certain type of order indiscernibles, here dubbed tight indiscernibles, which are shown to provide smooth proofs of several results in general model theory.

Given a model \ of set theory, and a nontrivial automorphism j of \, let \\) be the submodel of \ whose universe consists of elements m of \ such that \=x\) for every x in the transitive closure of m ). Here we study the class \ of structures of the form \\), where the ambient model \ satisfies a frugal yet robust fragment of \ known as \, and \=m\) whenever m is a finite ordinal in the sense (...) of \ Our main achievement is the calculation of the theory of \ as precisely \-\. The following theorems encapsulate our principal results:Theorem A. Every structure in \ satisfies \-\.Theorem B. Each of the following three conditions is sufficient for a countable structure \ to be in \: \ is a transitive model of \-\. \ is a recursively saturated model of \-\. \ is a model of \.Theorem C. Suppose \ is a countable recursively saturated model of \ and I is a proper initial segment of \ that is closed under exponentiation and contains \. There is a group embedding \ from \\) into \\) such that I is the longest initial segment of \ that is pointwise fixed by \ for every nontrivial \.\)In Theorem C, \\) is the group of automorphisms of the structure X, and \ is the ordered set of rationals. (shrink)

A DO model (here also referred to a Paris model) is a model of set theory all of whose ordinals are first order definable in . Jeffrey Paris (1973) initiated the study of DO models and showed that (1) every consistent extension T of ZF has a DO model, and (2) for complete extensions T, T has a unique DO model up to isomorphism iff T proves V=OD. Here we provide a comprehensive treatment of Paris models. Our results include the (...) following:1. If T is a consistent completion of ZF+V≠OD, then T has continuum-many countable nonisomorphic Paris models.2. Every countable model of ZFC has a Paris generic extension.3. If there is an uncountable well-founded model of ZFC, then for every infinite cardinal κ there is a Paris model of ZF of cardinality κ which has a nontrivial automorphism.4. For a model ZF, is a prime model ⇒ is a Paris model and satisfies AC⇒ is a minimal model. Moreover, Neither implication reverses assuming Con(ZF). (shrink)

We develop the method of iterated ultrapower representation to provide a unified and perspicuous approach for building automorphisms of countable recursively saturated models of Peano arithmetic . In particular, we use this method to prove Theorem A below, which confirms a long-standing conjecture of James Schmerl.Theorem AIf is a countable recursively saturated model of in which is a strong cut, then for any there is an automorphism j of such that the fixed point set of j is isomorphic to .We (...) also fine-tune a number of classical results. One of our typical results in this direction is Theorem B below, which generalizes a theorem of Kaye–Kossak–Kotlarski .Theorem BSuppose is a countable recursively saturated model of in which is a strong cut. There is a group embedding from into such that for each that is fixed point free, moves every undefinable element of. (shrink)

The principal result of this paper answers a long-standing question in the model theory of arithmetic [R. Kossak, J. Schmerl, The Structure of Models of Peano Arithmetic, Oxford University Press, 2006, Question 7] by showing that there exists an uncountable arithmetically closed family of subsets of the set ω of natural numbers such that the expansion of the standard model of Peano arithmetic has no conservative elementary extension, i.e., for any elementary extension of , there is a subset of ω* (...) that is parametrically definable in but whose intersection with ω is not a member of . We also establish other results that highlight the role of countability in the model theory of arithmetic. Inspired by a recent question of Gitman and Hamkins, we furthermore show that the aforementioned family can be arranged to further satisfy the curious property that forcing with the quotient Boolean algebra collapses 1 when viewed as a notion of forcing. (shrink)

A model M = (M, E,...) of Zermelo-Fraenkel set theory ZF is said to be θ-like, where E interprets ∈ and θ is an uncountable cardinal, if |M| = θ but $|\{b \in M: bEa\}| for each a ∈ M. An immediate corollary of the classical theorem of Keisler and Morley on elementary end extensions of models of set theory is that every consistent extension of ZF has an ℵ 1 -like model. Coupled with Chang's two cardinal theorem this implies (...) that if θ is a regular cardinal θ such that $2^{ then every consistent extension of ZF also has a θ + -like model. In particular, in the presence of the continuum hypothesis every consistent extension of ZF has an ℵ 2 -like model. Here we prove: THEOREM A. If θ has the tree property then the following are equivalent for any completion T of ZFC: (i) T has a θ-like model. (ii) $\Phi \subseteq T$ , where Φ is the recursive set of axioms {∃ κ(κ is n-Mahlo and "V κ is a Σ n -elementary submodel of the universe"): n ∈ ω}. (iii) T has a λ-like model for every uncountable cardinal λ. THEOREM B. The following are equiconsistent over ZFC: (i) "There exists an ω-Mahlo cardinal". (ii) "For every finite language L, all ℵ 2 -like models of ZFC(L) satisfy the scheme Φ(L). (shrink)

A model is said to be Leibnizian if it has no pair of indiscernibles. Mycielski has shown that there is a first order axiom LM (the Leibniz-Mycielski axiom) such that for any completion T of Zermelo-Fraenkel set theory ZF, T has a Leibnizian model if and only if T proves LM. Here we prove: THEOREM A. Every complete theory T extending ZF + LM has $2^{\aleph_{0}}$ nonisomorphic countable Leibnizian models. THEOREM B. If $\kappa$ is aprescribed definable infinite cardinal of a (...) complete theory T extending ZF + V = OD. then there are $2^{\aleph_{1}}$ nonisomorphic Leibnizian models $\mathfrak{M}$ of T of power $\aleph_{1}$ such that $(\kappa^{+})^\mathfrak{M}$ is $\aleph_{1}-like$ . THEOREM C. Every complete theory T extending ZF + V = OD has $2^{\aleph_{1}}$ nonisomorphic \aleph_{1}-like$ Leibnizian models. (shrink)

This paper develops the model theory of ordered structures that satisfy Keisler’s regularity scheme and its strengthening REF ${(\mathcal{L})}$ (the reflection scheme) which is an analogue of the reflection principle of Zermelo-Fraenkel set theory. Here ${\mathcal{L}}$ is a language with a distinguished linear order <, and REF ${(\mathcal {L})}$ consists of formulas of the form $$\exists x \forall y_{1} < x \ldots \forall y_{n} < x \varphi (y_{1},\ldots ,y_{n})\leftrightarrow \varphi^{ < x}(y_1, \ldots ,y_n),$$ where φ is an ${\mathcal{L}}$ -formula, φ (...) shrink)

By a classical theorem of Harvey Friedman, every countable nonstandard model $\mathcal {M}$ of a sufficiently strong fragment of ZF has a proper rank-initial self-embedding j, i.e., j is a self-embedding of $\mathcal {M}$ such that $j[\mathcal {M}]\subsetneq \mathcal {M}$, and the ordinal rank of each member of $j[\mathcal {M}]$ is less than the ordinal rank of each element of $\mathcal {M}\setminus j[\mathcal {M}]$. Here, we investigate the larger family of proper initial-embeddings j of models $\mathcal {M}$ of fragments of (...) set theory, where the image of j is a transitive submodel of $\mathcal {M}$. Our results include the following three theorems. In what follows, $\mathrm {ZF}^-$ is $\mathrm {ZF}$ without the power set axiom; $\mathrm {WO}$ is the axiom stating that every set can be well-ordered; $\mathrm {WF}$ is the well-founded part of $\mathcal {M}$ ; and $\Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $ is the full scheme of dependent choice of length $\alpha $.Theorem A.There is an $\omega $ -standard countable nonstandard model $\mathcal {M}$ of $\mathrm {ZF}^-+\mathrm {WO}$ that carries no initial self-embedding $j:\mathcal {M} \longrightarrow \mathcal {M}$ other than the identity embedding.Theorem B.Every countable $\omega $ -nonstandard model $\mathcal {M}$ of $\ \mathrm {ZF}$ is isomorphic to a transitive submodel of the hereditarily countable sets of its own constructible universe $L^{\mathcal {M}}$.Theorem C.The following three conditions are equivalent for a countable nonstandard model $\mathcal {M}$ of $\mathrm {ZF}^{-}+\mathrm {WO}+\forall \alpha \ \Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $. There is a cardinal in $\mathcal {M}$ that is a strict upper bound for the cardinality of each member of $\mathrm {WF}$. $\mathrm {WF}$ satisfies the powerset axiom.For all $n \in \omega $ and for all $b \in M$, there exists a proper initial self-embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ such that $b \in \mathrm {rng}$ and $j[\mathcal {M}] \prec _n \mathcal {M}$. (shrink)

A definable pair of disjoint non-OD sets of reals exists in the Sacks and ????0-large generic extensions of the constructible universe L. More specifically, if a∈2ω is eith...

TheoremEvery model of ZFChas a conservative elementary extension which possesses a cofinal minimal elementary extension.An application of Boolean ultrapowers to models of full arithmetic is also presented.

We give a new negative solution to Keisler's problem regarding Skolem functions and elementary extensions. In contrast to existing ad hoc solutions due to Payne, Knight, and Lachlan, our solution uses well-known models.

A model \ of ZF is said to be condensable if \\prec _{\mathbb {L}_{{\mathcal {M}}}} {\mathcal {M}}\) for some “ordinal” \, where \:=,\in )^{{\mathcal {M}}}\) and \ is the set of formulae of the infinitary logic \ that appear in the well-founded part of \. The work of Barwise and Schlipf in the 1970s revealed the fact that every countable recursively saturated model of ZF is cofinally condensable \prec _{\mathbb {L}_{{\mathcal {M}}}}{\mathcal {M}}\) for an unbounded collection of \). Moreover, it (...) can be readily shown that any \-nonstandard condensable model of \ is recursively saturated. These considerations provide the context for the following result that answers a question posed to the author by Paul Kindvall Gorbow.Theorem A. Assuming a modest set-theoretic hypothesis, there is a countable model \ of ZFC that is both definably well-founded is in the well-founded part of \}\) and cofinally condensable. We also provide various equivalents of the notion of condensability, including the result below.Theorem B. The following are equivalent for a countable model \ of \: \ is condensable. \ is cofinally condensable. \ is nonstandard and \\prec _{\mathbb {L}_{{\mathcal {M}}}}{\mathcal {M}}\) for an unbounded collection of \. (shrink)