Ali Enayat

This article is a contribution to the study of extensions of arbitrary models of $\mathsf {ZF}$ (Zermelo–Fraenkel set theory), with no regard to countability or well-foundedness of the models involved. Our main results include the theorems below; in Theorems A and B, ${\mathcal {N}}$ is said to be a conservative elementary extension of $\mathcal {M}$ if $\mathcal { N}$ elementarily extends $\mathcal {M}$, and the intersection of every $ {\mathcal {N}}$ -definable set with the universe of $\mathcal {M}$ is $\mathcal {M} $ -definable (parameters allowed). In Theorem B, $\mathsf {ZFC}$ is the result of augmenting $\mathsf {ZF}$ with the axiom of choice. Theorem A.Every model $\mathcal {M}$ of $\mathsf {ZF}+\exists p\left ( \mathrm {V}=\mathrm {HOD}(p)\right ) $ has a conservative elementary extension ${\mathcal {N}}$ that contains an ordinal above all of the ordinals of $\mathcal {M}$. Theorem B.If ${\mathcal {N}}$ is a conservative elementary extension of a model $\mathcal {M}$ of $ \mathsf {ZFC}$, and ${\mathcal {N}}$ has the same natural numbers as $\mathcal {M}$, then $\mathcal {M}$ is cofinal in ${\mathcal {N}}$. Theorem C.Every consistent extension of $ \mathrm {ZF}$ has a model $\mathcal {M}$ of power $\aleph _{1}$ such that $\mathcal {M}$ has no proper end extension to a model of $\mathsf {ZF}$.

This paper is primarily concerned with assessing a set-theoretical system, $$S^*$$, for the foundations of category theory suggested by Solomon Feferman. $$S^*$$ is an extension of NFU, and may be seen as an attempt to accommodate unrestricted categories such as the category of all groups (without any small/large restrictions), while still obtaining the benefits of ZFC on part of the domain. A substantial part of the paper is devoted to establishing an improved upper bound on the consistency strength of $$S^*$$. The assessment of $$S^*$$ as a foundation of category theory is framed by the following general desiderata (R) and (S). (R) asks for the unrestricted existence of the category of all groups, the category of all categories, the category of all functors between two categories, etc., along with natural implementability of ordinary mathematics and category theory. (S) asks for a certain relative distinction between large and small sets, and the requirement that they both enjoy the full benefits of the ZFC axioms. $$S^*$$ satisfies (R) simply because it is an extension of NFU. By means of a recursive construction utilizing the notion of strongly cantorian sets, we argue that it also satisfies (S). Moreover, this construction yields a lower bound on the consistency strength of $$S^*$$. We also exhibit a basic positive result for category theory internal to NFU that provides motivation for studying NFU-based foundations of category theory.

The seminal Krajewski–Kotlarski–Lachlan theorem (1981) states that every countable recursively saturated model of $\mathsf {PA}$ (Peano arithmetic) carries a full satisfaction class. This result implies that the compositional theory of truth over $\mathsf {PA}$ commonly known as $\mathsf {CT}^{-}[\mathsf {PA}]$ is conservative over $\mathsf {PA}$. In contrast, Pakhomov and Enayat (2019) showed that the addition of the so-called axiom of disjunctive correctness (that asserts that a finite disjunction is true iff one of its disjuncts is true) to $\mathsf {CT}^{-}[\mathsf {PA}]$ axiomatizes the theory of truth $\mathsf {CT}_{0}[\mathsf {PA}]$ that was shown by Wcisło and Łełyk (2017) to be nonconservative over $\mathsf {PA}$. The main result of this paper (Theorem 3.12) provides a foil to the Pakhomov–Enayat theorem by constructing full satisfaction classes over arbitrary countable recursively saturated models of $\mathsf {PA}$ that satisfy arbitrarily large approximations of disjunctive correctness. This shows that in the Pakhomov–Enayat theorem the assumption of disjunctive correctness cannot be replaced with any of its approximations.

We investigate the theory Peano Arithmetic with Indiscernibles ( \(\textrm{PAI}\) ). Models of \(\textrm{PAI}\) are of the form \(({\mathcal {M}},I)\), where \({\mathcal {M}}\) is a model of \(\textrm{PA}\), _I_ is an unbounded set of order indiscernibles over \({\mathcal {M}}\), and \(({\mathcal {M}},I)\) satisfies the extended induction scheme for formulae mentioning _I_. Our main results are Theorems A and B following. _Theorem A._ _Let_ \({\mathcal {M}}\) _be a nonstandard model of_ \(\textrm{PA}\) _ of any cardinality_. \(\mathcal {M }\) _has an expansion to a model of _ \(\textrm{PAI}\) _iff_ \( {\mathcal {M}}\) _has an inductive partial satisfaction class._ Theorem A yields the following corollary, which provides a new characterization of countable recursively saturated models of \(\textrm{PA}\) : _Corollary._ _A countable model_ \({\mathcal {M}}\) of \(\textrm{PA}\) _is recursively saturated iff _ \({\mathcal {M}}\) _has an expansion to a model of _ \(\textrm{PAI}\). _Theorem B._ _There is a sentence _ \(\alpha \) _ in the language obtained by adding a unary predicate_ _I_(_x_) _to the language of arithmetic such that given any nonstandard model _ \({\mathcal {M}}\) _of_ \(\textrm{PA}\) _ of any cardinality_, \({\mathcal {M}}\) _has an expansion to a model of _ \(\text {PAI}+\alpha \) _iff_ \({\mathcal {M}}\) _has a inductive full satisfaction class._.

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

We employ the lens provided by formal truth theory to study axiomatizations of Peano Arithmetic ${\textsf {(PA)}}$. More specifically, let Elementary Arithmetic ${\textsf {(EA)}}$ be the fragment $\mathsf {I}\Delta _0 + \mathsf {Exp}$ of ${\textsf {PA}}$, and let ${\textsf {CT}}^-[{\textsf {EA}}]$ be the extension of ${\textsf {EA}}$ by the commonly studied axioms of compositional truth ${\textsf {CT}}^-$. We investigate both local and global properties of the family of first order theories of the form ${\textsf {CT}}^-[{\textsf {EA}}] +\alpha $, where $\alpha $ is a particular way of expressing “ ${\textsf {PA}}$ is true” (using the truth predicate). Our focus is dominantly on two types of axiomatizations, namely: (1) schematic axiomatizations that are deductively equivalent to ${\textsf {PA}}$ and (2) axiomatizations that are proof-theoretically equivalent to the canonical axiomatization of ${\textsf {PA}}$.

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

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

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.

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.

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)

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)

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

Let$\left\langle {{W_n}:n \in \omega } \right\rangle$be a canonical enumeration of recursively enumerable sets, and supposeTis a recursively enumerable extension of PA (Peano Arithmetic) in the same language. Woodin (2011) showed that there exists an index$e \in \omega$(that depends onT) with the property that if${\cal M}$is a countable model ofTand for some${\cal M}$-finite sets,${\cal M}$satisfies${W_e} \subseteq s$, then${\cal M}$has an end extension${\cal N}$that satisfiesT+We=s.Here we generalize Woodin’s theorem to all recursively enumerable extensionsTof the fragment${{\rm{I}\rm{\Sigma }}_1}$of PA, and remove the countability restriction on${\cal M}$whenTextends PA. We also derive model-theoretic consequences of a classic fixed-point construction of Kripke (1962) and compare them with Woodin’s theorem.