We often use sets to represent natural numbers, but we can also use natural numbers to represent sets. For example, we can use the binary expansion of a natural number to represent a set. The number seven (111 base 2) could represent the set {2,1,0}.

It is known Peano Arithmetic (PA) is bi-interpretable with ZF - Infinity + all sets are finite + all sets have a transitive closure (ZF-Inf+TC). See Kang and Wong: On Interpretations of Arithmetic and Set Theory.

The axiom of regularity is an axiom of ZF-Inf+TC and it says there are no infinite descending chains of nested sets. Assume we have a nonstandard model of PA. Let $x$ be a nonstandard natural number larger than any standard natural number. Consider the sets defined by $2^x-1, 2^{x-1}-1, 2^{x-2}-1, ..., 2^0-1$.

This seems to be an infinite descending chain of nested sets.

My question is whether PA has ill-founded models and if so, how can it be bi-interpretable with ZF-Inf+TC.


Yes. It is easy to show that, too.

Suppose that $M$ is a model of Peano and its $\leq^M$ order is well-ordered (equivalently, well-founded). Consider $N\subseteq M$ the set made of $0^M$ and closed under $S^M$ (this is the interpretation of all the numerals in $M$).

If $M\setminus N$ is non-empty it has a least element $m$, but $m\neq 0^M$, therefore $m=S^M(x)$ for some $x\in N$. This is a contradiction since if $x\in N$ we have that $S^M(x)\in N$ too.

Do note that the definition of $N$ is external to $M$. But then again the definition of "non-standard" is external too.

You can show, however that if $A\subseteq M$ is a [parameter-free] definable set, then it is empty, or has a minimal element. It goes on to show that $N$ itself is not definable without parameters.

As for being bi-interpretable with $\sf ZF-Inf+TC$, note that the axiom of regularity is internal, not external. It is perfectly fine that $\sf ZF$ has an ill-founded model, as long as the model "doesn't know" about the decreasing chain.

Namely, every set inside the model, has a $\in$-minimal element. But it doesn't mean that every subset of the model is a set in the model.

Perhaps something which is worth pointing out, both $\sf ZF$ and $\sf PA$ are first-order theories. They have very limited powers when it comes to talking about sub-collections of the universe. Both can only ensure that a small fragments of these have a minimal element. So we can't quite write down the statement "Every set has a minimal element", and this fact exactly is what allows non-standard elements to exist.

| cite | improve this answer | |
  • $\begingroup$ "If M∖N is non-empty it has a least element m" may not be true. N could be the standard natural numbers. $\endgroup$ – Russell Easterly Jun 26 '14 at 21:12
  • $\begingroup$ Yes, so the only way there is no contradiction is $M\setminus N=\varnothing$ and therefore $M$ is isomorphic to $\Bbb N$, the standard model of $\sf PA$. $\endgroup$ – Asaf Karagila Jun 26 '14 at 21:14
  • $\begingroup$ If N is the standard natural numbers then M\N is not empty and it doesn't have a least element. $\endgroup$ – Russell Easterly Jun 26 '14 at 21:43
  • $\begingroup$ You're jumping too fast for me. I'm sorry. We have $M$. Is it any model of $\sf PA$ or a non-standard model of $\sf PA$? $\endgroup$ – Asaf Karagila Jun 26 '14 at 21:45
  • $\begingroup$ M/N being non-empty does not mean it has a least element $m$. M could be a nonstandard model and N the standard model. You only assume N is a subset of M, contains 0, and is closed under successor. The standard natural numbers satisfy this definition. $\endgroup$ – Russell Easterly Jun 26 '14 at 21:55

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.