12

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?

Hans-Peter Stricker
  • 9,628

2 Answers2

20

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.

Ali Enayat
  • 17,058
  • 5
    Ali, welcome to MO! – Joel David Hamkins May 04 '11 at 14:28
  • Isn’t ZF-Inf defined so that it includes TC (or rather, epsilon-induction)? – Emil Jeřábek May 04 '11 at 14:42
  • 2
    ZF-Inf is usually defined as ZF{Inf}+{negation of Inf}- Ali Enayat – Ali Enayat May 04 '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 04 '11 at 15:09
  • 1
    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. – Joel David Hamkins May 04 '11 at 15:14
  • Sochor, for one, does it that way (see e.g. http://dml.cz/dmlcz/105962, http://dml.cz/dmlcz/106132). – Emil Jeřábek May 04 '11 at 15:16
  • @Joel: you prove the existence of transitive closure directly by $\in$-induction: $TC(x)=x\cup\bigcup\{TC(y):y\in x\}$. – Emil Jeřábek May 04 '11 at 15:19
  • (And, by the way, separation implies replacement, if the negation of the axiom of infinity is formulated as “every set is finite according to Tarski’s definition”.) – Emil Jeřábek May 04 '11 at 15:22
  • I see. So does this mean that from the usual formulation of the foundation axiom (namely, every set has a $\in$-minimal element) plus the rest of ZF without infinity, we cannot prove the principle of $\in$-induction? I guess $\in$-induction is a class assertion, the scheme asserting of every $\varphi$ that if $\varphi(x)$ is not universal, then there is an $\in$-minimal failure. – Joel David Hamkins May 04 '11 at 15:29
  • Of course, the broader picture here is that the reason one should include $\in$-induction is precisely because of the reason Ali mentions, that otherwise one has weird models where sets don't have transitive closures. – Joel David Hamkins May 04 '11 at 15:33
  • Exactly. As for the second part, $\in$-induction is a schema, but it is finitely axiomatizable over the other axioms (in fact, it is equivalent to the conjunction of the existence of $\in$-minimal elements in any set and the existence of transitive closure). – Emil Jeřábek May 04 '11 at 15:35
  • 1
    Replacing foundation by $\in$-induction, which is needed here because of the absence of the axiom of infinity, is also needed in versions of ZF based on constructive logic, i.e., in the absence of the law of the excluded middle. I wonder whether there's any deeper significance to the need for the same change in these two, apparently unrelated situations. – Andreas Blass May 04 '11 at 21:31
  • 1
    I’d say it’s the other way round. The most natural way of expressing well-foundedness of a class relation is to postulate the corresponding induction schema (or the induction axiom for classes, if we are in a theory which supports classes as genuine objects). As it happens, the remaining axioms of ZF allow to simplify this schema to its instance where the class is just a set, but there is no reason why this should be possible (or desirable) in other contexts. – Emil Jeřábek May 05 '11 at 14:38
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.

Sidney Raffer
  • 6,159
  • 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 04 '11 at 09: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? – Sidney Raffer May 04 '11 at 10:17
  • @SJR: Yes, this is true, well known, and easy. – Emil Jeřábek May 04 '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-Peter Stricker May 04 '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 04 '11 at 14:41