4
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
11
  • $\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$ Jun 26, 2014 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, 2014 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$ Jun 26, 2014 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, 2014 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$ Jun 26, 2014 at 21:55

You must log in to answer this question.

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