# Non-standard models of finite set theory

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.

-
Ali, welcome to MO! – Joel David Hamkins May 4 '11 at 14:28
Interesting. Thanks. – SJR May 4 '11 at 14:36
Isn’t ZF-Inf defined so that it includes TC (or rather, epsilon-induction)? – Emil Jeřábek May 4 '11 at 14:42
ZF-Inf is usually defined as ZF\{Inf}+{negation of Inf}- Ali Enayat – Ali Enayat May 4 '11 at 14:58
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. – Emil Jeřábek May 4 '11 at 15:09

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.

-
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 – boumol May 4 '11 at 9:00
@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? – SJR May 4 '11 at 10:17
@SJR: Yes, this is true, well known, and easy. – Emil Jeřábek May 4 '11 at 10:24
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) – Hans Stricker May 4 '11 at 11:43
@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. – Emil Jeřábek May 4 '11 at 14:41