It is well known how the intended model and how the (countable) non-standard models of arithmetic look like.

It's also well known how the intended model of set theory with the axiom of infinity replaced by its negation (ZF-Inf) looks like: $\langle V_\omega;\in\rangle$, the hereditarily finite sets with the $\in$-relation.

But how do (countable) non-standard models of ZF-Inf look like?


Models of ZF-Infinity that arise from models of PA via binary bits - a method first introduced by Ackermann in 1940 to interpret set theory in arithmetic- end up satisfying the statement TC := "every set has a transitive closure".

It is known that the strengthened theory ZF-Infinity+TC is bi-interpretable with PA, which in particular means that every model of ZF-Infinity+TC is an "Ackermann model" of a model of PA.

However, TC is essential: there are models of ZF-Infinity that do NOT satisfy TC; and therefore such models cannot arise via Ackermann coding on a model of PA.

It is also known that there are "lots of" nonstandard model of ZF-Infinity [i.e., models not isomorphic to the intended model $V_{\omega}$] that are ${\omega}$-models [i.e., they have no nonstandard integer].

It is possible for a nonstandard ${\omega}$-model of ZF-Infinity to have a computable epsilon relation. Indeed, there is an analogue of Tennenbaum's theorem here: all computable models of ZF-Infinity are ${\omega}$-models.

For more detail on the above, and references on the subject of finite set theory, you can consult the following paper:


Ali Enayat

PS. In light of the comments about TC to my posting, it is worth pointing out that even though TC is not provable in ZF-Infinity, the theory ZF-Infinity is "smart enough" to interpret ZF-Infinity + TC via the inner model of sets whose transitive closure exists as a set [as opposed to a definable class; cf. the aforementioned paper for more detail].

Therefore the relation of TC to ZF-Infinity is analogous to the relation between Foundation (Regularity) to ZF without Foundation since ZF is interpretable in ZF without Foundation via an inner model.

  • 4
    $\begingroup$ Ali, welcome to MO! $\endgroup$ – Joel David Hamkins May 4 '11 at 14:28
  • $\begingroup$ Isn’t ZF-Inf defined so that it includes TC (or rather, epsilon-induction)? $\endgroup$ – Emil Jeřábek May 4 '11 at 14:42
  • 1
    $\begingroup$ ZF-Inf is usually defined as ZF\{Inf}+{negation of Inf}- Ali Enayat $\endgroup$ – Ali Enayat May 4 '11 at 14:58
  • $\begingroup$ Well, yes, but that does not clarify anything, because equivalent definitions of ZF lead to nonequivalent results if you start dropping axioms. The way I’ve seen ZF-Inf defined always included epsilon-induction as the proper formulation of the axiom of foundation. $\endgroup$ – Emil Jeřábek May 4 '11 at 15:09
  • $\begingroup$ Emil, I thought the point was that in order to prove that every set has a transitive closure, you need the replacement axiom and the existence of $\omega$, since $TC(x)=x\cup(\cup x)\cup(\cup\cup x)\cup\cdots$. Thus, even with $\epsilon$-induction, you can't seem to get transitive closures. $\endgroup$ – Joel David Hamkins May 4 '11 at 15:14

Any positive integer can be written uniquely as a sum of distinct powers of 2. PA knows this, in the sense that one can write down a formula $\phi(x,y)$ meaning in the standard model that the $x$-th bit in the binary expansion of $y$ is 1. Moreover we can construct $\phi$ so that PA will prove all the expected facts about the $x$-th bit in the binary expansion of $y$.

If $M$ is any model of PA, then by taking $\phi(x,y)$ as the membership relation "$x\in y$" we get a model of ZF-Inf. This is worked out in detail in Chapter 1 of "Metamathematics of First Order Arithmetic" by Hajek and Pudlak. In fact the authors carry this out not just for PA but for the subtheory $\text{I}\Sigma_0(\text{exp})$.

(Added) I expected that every model $M$ of ZF-Inf would arise in this way, by applying the above construction to the model of PA consisting of the ordinals of $M$. But it seems this is not so... See Ali's answer below.

  • $\begingroup$ Is it known whether all ZF-Inf models come from this method (i.e., from PA models)? If this is not the case, this explanation do not say how are all ZF-Inf models $\endgroup$ – boumol May 4 '11 at 9:00
  • $\begingroup$ @boumol: Yes, I believe that all models of ZF-Inf arise this way, because given any such model $M$, the set $P$ of ordinals of $M$ will give a model of PA, and the relation $\phi$ on $P$ will give back $M$. I admit that I haven't worked through (or even seen) a proof of this.. Perhaps it is somewhere in Hajek and Pudlak? $\endgroup$ – Sidney Raffer May 4 '11 at 10:17
  • $\begingroup$ @SJR: Yes, this is true, well known, and easy. $\endgroup$ – Emil Jeřábek May 4 '11 at 10:24
  • $\begingroup$ Can these constructions been summed up in a somehow "pictorial" description, like in the case of non-standard models of arithmetic: "a countable nonstandard model begins with an infinite increasing sequence. This is followed by a collection of blocks, each of the order type of the integers. These blocks are in turn densely ordered with the order type of the rationals"? (from Wikipedia) $\endgroup$ – Hans-Peter Stricker May 4 '11 at 11:43
  • $\begingroup$ @Hans: The exact same pictorial descriptions works, where the order on the model is lexicographic: $x < y$ iff the maximal element of the symmetric difference of $x$ and $y$ belongs to $y$, where the order on the elements of $x$ and $y$ is defined recursively. $\endgroup$ – Emil Jeřábek May 4 '11 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.