13
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • 5
    $\begingroup$ Ali, welcome to MO! $\endgroup$
    – Joel David Hamkins
    Commented May 4, 2011 at 14:28
  • 2
    $\begingroup$ ZF-Inf is usually defined as ZF\{Inf}+{negation of Inf}- Ali Enayat $\endgroup$
    – Ali Enayat
    Commented May 4, 2011 at 14:58
  • 1
    $\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
    Commented May 4, 2011 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andreas Blass
    Commented May 4, 2011 at 21:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented May 5, 2011 at 14:38
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented May 4, 2011 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
    Commented May 4, 2011 at 10:17
  • $\begingroup$ @SJR: Yes, this is true, well known, and easy. $\endgroup$
    – Emil Jeřábek
    Commented May 4, 2011 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
    Commented May 4, 2011 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
    Commented May 4, 2011 at 14:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .