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

We prove the following characterizations of nonstandard models of ZFC (Zermelo-Fraenkel set theory with the axiom of choice) that have an expansion to a model of GB (Gödel-Bernays class theory) plus Δ11-CA (the scheme of Δ11-Comprehension). In what follows, M(α):=(V(α),∈)M, LM is the set of formulae of the infinitary logic L∞,ω that appear in the well-founded part of M, and Σ11-AC is the scheme of Σ11-Choice. Theorem A. The following are equivalent for a nonstandard model M of ZFC of any cardinality: (a) M(α)≺LMM for an unbounded collection of α∈OrdM. (b) (M,X)⊨GB+Δ11-CA, where X is the family of LM-definable subsets of M. (c) There is X such that (M,X)⊨GB+Δ11-CA. Theorem B. The following are equivalent for a countable nonstandard model of ZFC: (a) M(α)≺LMM for an unbounded collection of α∈OrdM. (b) There is X such that (M,X)⊨GB+Δ11-CA+Σ11-AC.

Motivated by problems involving end extensions of models of set theory, we develop the rudiments of the power admissible cover construction (over ill-founded models of set theory), an extension of the machinery of admissible covers invented by Barwise as a versatile tool for generalising model-theoretic results about countable well-founded models of set theory to countable ill-founded ones. Our development of the power admissible machinery allows us to obtain new results concerning powerset-preserving end extensions and rank extensions of countable models of subsystems of ZFC. The canonical extension KPP of Kripke-Platek set theory KP plays a key role in our work; one of our results refines a theorem of Rathjen by showing that Σ1P-Foundation is provable in KPP (without invoking the axiom of choice).

Abstract By a classical theorem of Harvey Friedman (1973), 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}(\mathcal {M})$ 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 $ . (I) There is a cardinal in $\mathcal {M}$ that is a strict upper bound for the cardinality of each member of $\mathrm {WF}(\mathcal {M})$ . (II) $\mathrm {WF}(\mathcal {M})$ satisfies the powerset axiom. (III) For all $n \in \omega $ and for all $b \in M$ , there exists a proper initial self-embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ </

Abstract 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 (Peano arithmetic). 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 ϕ.

Abstract In ZFC, the class Ord of ordinals is easily seen to satisfy the definable version of strong inaccessibility. Here we explore deeper ZFC-verifiable combinatorial properties of Ord, as indicated in Theorems A & B below. Note that Theorem A shows the unexpected result that Ord is never definably weakly compact in any model of ZFC. Theorem A. Let ${\cal M}$ be any model of ZFC. (1) The definable tree property fails in ${\cal M}$ : There is an ${\cal M}$ -definable Ord-tree with no ${\cal M}$ -definable cofinal branch. (2) The definable partition property fails in ${\cal M}$ : There is an ${\cal M}$ -definable 2-coloring $f:{[X]^2} \to 2$ for some ${\cal M}$ -definable proper class X such that no ${\cal M}$ -definable proper classs is monochromatic for f. (3) The definable compactness property for ${{\cal L}_{\infty ,\omega }}$ fails in ${\cal M}$ : There is a definable theory ${\rm{\Gamma }}$ in the logic ${{\cal L}_{\infty ,\omega }}$ (in the sense of ${\cal M}$ ) of size Ord such that every set-sized subtheory of ${\rm{\Gamma }}$ is satisfiable in ${\cal M}$ , but there is no ${\cal M}$ -definable model of ${\rm{\Gamma }}$ . Theorem B. The definable ⋄Ordprinciple holds in a model ${\cal M}$ of ZFC iff ${\cal M}$ carries an ${\cal M}$ -definable global well-ordering. Theorems A and B above can be recast as theorem schemes in ZFC, or as asserting that a single statement in the language of class theory holds in all ‘spartan’ models of GB (Gödel-Bernays class theory); where a spartan model of GB is any structure of the form $\left( {{\cal M},{D_{\cal M}}} \right)$ , where ${\cal M} \models {\rm{ZF}}$ and

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

Abstract. 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 nonisomorphic countable Leibnizian models. Theorem B. If κ is a prescribed definable infinite cardinal ofa complete theory T extending ZF + V = OD, then there are nonisomorphic Leibnizian models of T of power ℵ1such that is ℵ1-like. Theorem C. Every complete theory T extendingZF + V = ODhas nonisomorphic ℵ1-like Leibnizian models.

Abstract. A model = (M. E, …) of Zermelo-Fraenkel set theory ZF is said to be 0-like. where E interprets ∈ and θ is an uncountable cardinal, if ∣M∣ = θ but ∣{b ∈ M: bEa}∣ < 0 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 0 such that 2<0 = 0 then every consistent extension of ZF also has a 0+-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 0 has the tree property then the following are equivalent for any completion T of ZFC: (i) T has a 0-like model. (ii) Ф ⊆ 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 , all ℵ2-like models of ZFC( ) satisfy the schemeФ( ).

An attempt to answer the following question gave rise to the results of the present paper. Let be an arbitrary model of set theory. Does there exist an elementary extension of satisfying the two requirements: (1) contains an ordinal exceeding all the ordinals of ; (2) does not enlarge any (hyper) integer of ? Note that a trivial application of the ordinary compactness theorem produces a model satisfying condition (1); and an internal ultrapower modulo an internal ultrafilter produces a model satisfying condition (2) (but not (1), because of the axiom of replacement). Also, such a satisfying both conditions (1) and (2) exists if the external cofinality of the ordinals of is countable, since by [KM], would then have an elementary end extension. Using a class of models constructed by M. Rubin using in [RS], and already employed in [E1], we prove that our question in general has a negative answer (see Theorem 2.3). This result generalizes the results of M. Kaufmann and the author (appearing respectively in [Ka] and [E1]) concerning models of set theory with no elementary end extensions. In the course of the proof it was necessary to establish that all conservative extensions (see Definition 2.1) of models of ZF must be cofinal. This is in direct contrast with the case of Peano arithmetic where all conservative extensions are end extensional (as observed by Phillips in [Ph1]). This led the author to introduce two useful weakenings of the notion of a conservative end extension which, as shown by the “completeness” theorems in §3, can exist.

The central notion of this paper is that of a κ-elementary end extension of a model of set theory. A model is said to be a κ-elementary end extension of a model of set theory if > and κ, which is a cardinal of , is end extended in the passage from to , i.e., enlarges κ without enlarging any of its members (see §0 for more detail). This notion was implicitly introduced by Scott in [Sco] and further studied by Keisler and Morley in [KM], Hutchinson in [H] and recently by the author in [E]. It is not hard to see that if has a κ-elementary end extension then κ must be regular in . Keisler and Morley [KM] noticed that this has a converse if is countable, i.e., if κ is a regular cardinal of a countable model then has a κ-elementary end extension. Later Hutchinson [H] refined this result by constructing κ-elementary end extensions 1 and 2 of an arbitrary countable model in which κ is a regular uncountable cardinal, such that 1 adds a least new element to κ while 2 adds no least new ordinal to κ. It is a folklore fact of model theory that the Keisler-Morley result gives soft and short proofs of countable compactness and abstract completeness (i.e. recursive enumera-bility of validities) of the logic L(Q), studied extensively in Keisler's [K2]; and Hutchinson's refinement does the same for stationary logic L(aa), studied by Barwise et al. in [BKM]. The proof of Keisler-Morley and that of Hutchinson make essential use of the countability of since they both rely on the Henkin-Orey omitting types theorem. As pointed out in [E, Theorem 2.12], one can prove these theorems using “generic” ultrapowers just utilizing the assumption of countability of the -power set of κ. The following result, appearing as Theorem 2.14 in [E], links the notion of κ-elementary end extension to that of measurability of κ. The proof using (b) is due to Matti Rubin.