Welcome to MathOverflow

Question

6

1

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?

flag	asked May 4 2011 at 6:49 Hans Stricker 5,362●13●39

SJR · Answer 1 · 2011-05-07 04:15:10Z UTC

6

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.

edited May 7 2011 at 4:15

answered May 4 2011 at 8:44

SJR
3,082●1●6●16

	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 2011 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 2011 at 10:17
	@SJR: Yes, this is true, well known, and easy. – Emil Jeřábek May 4 2011 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 2011 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 2011 at 14:41

Ali Enayat · Answer 2 · 2011-05-07 00:43:07Z UTC

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:

http://academic2.american.edu/~enayat/ESV%20%28May19,2009%29.pdf

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.

Non-standard models of finite set theory

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.