This paper starts by investigating Ackermann's interpretation of finite set theory in the natural numbers. We give a formal version of this interpretation from Peano arithmetic (PA) to Zermelo-Fraenkel set theory with the infinity axiom negated (ZF−inf) and provide an inverse interpretation going the other way. In particular, we emphasize the precise axiomatization of our set theory that is required and point out the necessity of the axiom of transitive containment or (equivalently) the axiom scheme of ∈-induction. This clarifies the (...) nature of the equivalence of PA and ZF−inf and corrects some errors in the literature. We also survey the restrictions of the Ackermann interpretation and its inverse to subsystems of PA and ZF−inf, where full induction, replacement, or separation is not assumed. The paper concludes with a discussion on the problems one faces when the totality of exponentiation fails, or when the existence of unordered pairs or power sets is not guaranteed. (shrink)

We give an examination of the automorphism group Aut of a countable recursively saturated model M of PA. The main result is a characterisation of strong elementary initial segments of M as the initial segments consisting of fixed points of automorphisms of M. As a corollary we prove that, for any consistent completion T of PA, there are recursively saturated countable models M1, M2 of T, such that Aut[ncong]Aut, as topological groups with a natural topology. Other results include a classification (...) of the normal subgroups of Aut of the form [lcub]g: g [uharr] A = idA[rcub], for sets A M, and a highly homogeneous representation of Aut as a subgroup of Aut. (shrink)

We show that Matijasevič's Theorem on the diophantine representation of r.e. predicates is provable in the subsystem I ∃ - 1 of Peano Arithmetic formed by restricting the induction scheme to diophantine formulas with no parameters. More specifically, I ∃ - 1 ⊢ IE - 1 + E ⊢ Matijasevič's Theorem where IE - 1 is the scheme of parameter-free bounded existential induction and E is an ∀∃ axiom expressing the existence of a function of exponential growth. We conclude by (...) examining the consequences of these results to the structure of countable nonstandard models of IE - 1. (shrink)

A theory of two-sided containers, denoted ZF2, is introduced. This theory is then shown to be synonymous to ZF in the sense of Visser (2006), via an interpretation involving Quine pairs. Several subtheories of ZF2, and their relationships with ZF, are also examined. We include a short discussion of permutation models (in the sense of Rieger–Bernays) over ZF2. We close with highlighting some areas for future research, mostly motivated by the need to understand non-wellfounded games.

We consider the quantifier hierarchy of Takahashi [1972] and show how it gives rise to reflection theorems for some large cardinals in ZF, a new natural subtheory of Zermelo's set theory, a potentially useful new reduction of the consistency problem for Quine's NF, and a sharpening of another reduction of this problem due to Boffa.

This undergraduate textbook covers the key material for a typical first course in logic, in particular presenting a full mathematical account of the most important result in logic, the Completeness Theorem for first-order logic. Looking at a series of interesting systems, increasing in complexity, then proving and discussing the Completeness Theorem for each, the author ensures that the number of new concepts to be absorbed at each stage is manageable, whilst providing lively mathematical applications throughout. Unfamiliar terminology is kept to (...) a minimum, no background in formal set-theory is required, and the book contains proofs of all the required set theoretical results. The reader is taken on a journey starting with König's Lemma, and progressing via order relations, Zorn's Lemma, Boolean algebras, and propositional logic, to completeness and compactness of first-order logic. As applications of the work on first-order logic, two final chapters provide introductions to model theory and nonstandard analysis. (shrink)

We present some general results concerning the topological space of cuts of a countable model of arithmetic given by a particular indicator Y.The notion of “indicator” is de.ned in a novel way, without initially specifying what property is indicated and is used to de.ne a topological space of cuts of the model. Various familiar properties of cuts are investigated in this sense, and several results are given stating whether or not the set of cuts having the property is comeagre.A new (...) notion of “generic cut” is introduced and investigated and it is shown in the case of countable arithmetically saturated models M ⊧ PA that generic cuts exist, indeed the set of generic cuts is comeagre in the sense of Baire, and furthermore that two generic cuts within the same “small interval” of the model are conjugate by an automorphism of the model.The paper concludes by outlining some applications to constructions of cuts satisfying properties incompatible with genericity, and discussing in model-theoretic terms those properties for which there is an indicator Y. (shrink)

Let M be a countable recursively saturated model of Th(), and let GAut(M), considered as a topological group. We examine connections between initial segments of M and subgroups of G. In particular, for each of the following classes of subgroups HG, we give characterizations of the class of terms of the topological group structure of H as a subgroup of G. (a) for some (b) for some (c) for some (d) for some (Here, M(a) denotes the smallest M containing a, (...) , , and .). (shrink)

We generalize Specker's theorem on typical ambiguity, that NF and TST + Ambiguity have the same stratified consequences, to the subschemes Amb(Γ) of ambiguity restricted to classes of sentences Γ with certain natural closure conditions.

In an earlier paper the first author initiated the study of generic cuts of a model of Peano arithmetic relative to a notion of an indicator in the model. This paper extends that work. We generalise the idea of an indicator to a related neighbourhood system; this allows the theory to be extended to one that includes the case of elementary cuts. Most results transfer to this more general context, and in particular we obtain the idea of a generic cut (...) relative to a neighbourhood system, which is studied in more detail. The main new result on generic cuts presented here is a description of truth in the structure , where I is a generic cut of a model M of Peano arithmetic. The special case of elementary generic cuts provides a partial answer to a question of Kossak [R. Kossak, Four problems concerning recursively saturated models of arithmetic, Notre Dame Journal of Formal Logic 36 519–530]. (shrink)

Let $\mathscr{L} = \{0, 1, +, \cdot, <\}$ be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order L-theory containing IΔ0 + exp such that every complete extension T of it has a countable model K satisfying. (i) K has no proper elementary substructures, and (ii) whenever $L \prec K$ is a countable elementary extension there is $\bar{L} \prec L$ and $\bar{K} \subseteq_\mathrm{e} \bar{L}$ such that $K \prec_{\mathrm{cf}}\bar{K}$ . Other model-theoretic conditions similar to (i) (...) and (ii) are also discussed and shown to characterize Peano arithmetic. (shrink)

In this paper we study the model theory of extensions of models of first-order Peano Arithmetic by means of the arithmetized completeness theorem applied to a definable complete extension of PA in the original model. This leads us to many interesting model theoretic properties equivalent to reflection principles and ω-consistency, and these properties together with the associated first-order schemes extending PA are studied.

A model is said to be -like if but for all , . In this paper, we shall study sentences true in -like models of arithmetic, especially in the cases when is singular. In particular, we identify axiom schemes true in such models which are particularly `natural' from a combinatorial or model-theoretic point of view and investigate the properties of models of these schemes.

We present a number of results on the structure of initial segments of models of Peano arithmetic with the arithmetic operations of addition, subtraction, multiplication, division, exponentiation and logarithm. Each of the binary operations introduced is defined in two dual ways, often with quite different results, and we attempt to systematise the issues and show how various calculations may be carried out. To understand the behaviour of addition and subtraction we introduce a notion of derivative on cuts, analogous to differentiation (...) in the calculus. Multiplication, division and other operations are described by higher order versions of derivative. The work here is presented as important preliminary work related to a nonstandard measure theory of non‐definable bounded subsets of a model of Peano arithmetic. (shrink)

Let ${\mathfrak{M}}$ be a nonstandard model of Peano Arithmetic with domain M and let ${n \in M}$ be nonstandard. We study the symmetric and alternating groups S n and A n of permutations of the set ${\{0,1,\ldots,n-1\}}$ internal to ${\mathfrak{M}}$ , and classify all their normal subgroups, identifying many externally defined such normal subgroups in the process. We provide evidence that A n and S n are not split extensions by these normal subgroups, by showing that any such complement if (...) it exists, cannot be a limit of definable sets. We conclude by identifying an ${\mathbb{R}}$ -valued metric on ${\tilde{S}_n = S_n /B_S}$ and ${\tilde{A}_n = A_n /B_A}$ (where B S , B A are the maximal normal subgroups of S n and A n identified earlier) making these groups into topological groups, and by showing that if ${\mathfrak{M}}$ is ${\mathfrak\aleph_1}$ -saturated then ${\tilde{S}_n}$ and ${\tilde{A}_n}$ are complete with respect to this metric. (shrink)

We expand the notion of resplendency to theories of the kind T + p", where T is a fi rst-order theory and p" expresses that the type p is omitted. We investigate two di erent formulations and prove necessary and sucient conditions for countable recursively saturated models of PA. Some of the results in this paper can be found in one of the author's doctoral thesis [3].

We raise an issue of circularity in the argument for the completeness of first-order logic. An analysis of the problem sheds light on the development of mathematics, and suggests other possible directions for foundational research.

Hilbert's tenth problem for a theory T asks if there is an algorithm which decides for a given polynomial p() from [] whether p() has a root in some model of T. We examine some of the model-theoretic consequences that an affirmative answer would have in cases such as T = Open Induction and others, and apply these methods by providing a negative answer in the cases when T is some particular finite fragment of the weak theories IE1 or IU-1.

This paper addresses the structures and ), whereMis a nonstandard model of PA andωis the standard cut. It is known that ) is interpretable in. Our main technical result is that there is an reverse interpretation of in ) which is ‘local’ in the sense of Visser [11]. We also relate the model theory of to the study of transplendent models of PA [2].This yields a number of model theoretic results concerning theω-models and their standard systems SSy, including the following.•$\left (...) \prec \left$if and only if$M \prec K$and$\left} \right) \prec \left} \right)$.•$\left} \right) \prec \left} \right)$if and only if$\left \prec \left$for someω-saturatedM*.•$M{ \prec _{\rm{e}}}K$implies SSy = SSy, but cofinal extensions do not necessarily preserve standard system in this sense.• SSy=SSy if and only if ) satisfies the full comprehension scheme.• If SSy is uniformly defined by a single formula, then ) satisfies the full comprehension scheme; and there are modelsMfor which SSy is not uniformly defined in this sense. (shrink)

Let= {0,1, +,·,<} be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order-theory containingIΔ0+ exp such that every complete extensionTof it has a countable modelKsatisfying(i)Khas no proper elementary substructures, and(ii) wheneverL≻Kis a countable elementary extension there isandsuch that.Other model-theoretic conditions similar to (i) and (ii) are also discussed and shown to characterize Peano arithmetic.