Not Skolem's Paradox – Part 3

This is a follow up to a previous question: Not Skolem’s Paradox – Part 2.

Assume we have a countable, non-standard model of Peano Arithmetic in ZFC. This ZFC model must include a set of ordered triplets that defines addition in this model.

There are various ways to encode finite sets in PA. For example, we can say the binary expansion of a natural number defines a set. The number $7 = 2^0 + 2^1 + 2^2$ encodes the set $\{0,1,2\}$. We can similarly encode ordered pairs. Encode $[a,b]$ as $2^{2a} + 2^{2b+1}$. The ordered pair $[2,0]$ would be encoded as $18 = 2^4 + 2^1$. We can now encode sets of ordered pairs, etc. I want to encode a set of ordered triplets that defines addition in a ring $\mathbb{Z} /n \mathbb{Z}$. I want to define addition modulo $n$. For example, let $n=3$:

$0+0=0$

$0+1=1$

$0+2=2$

$1+0=1$

$1+1=2$

$1+2=0$

$2+0=2$

$2+1=0$

$2+2=1$

Lets call this the addition function. This is a finite set that I can encode as a natural number in our model of PA. Now assume $n$ is a nonstandard natural number larger than any standard natural number. Our nonstandard model of PA still considers the addition function modulo $n$ to be finite and we can still encode this function as a nonstandard natural number.

Tennenbaums’ theorem proves neither addition nor multiplication can be recursive in any countable nonstandard model of arithmetic. This means ZFC has to prove the addition function modulo $n$ doesn’t exist when $n$ is larger than any standard natural number.

My question is how can a set be definable inside the model (PA) and yet not exist in the meta-theory (ZFC)?

Solutions Collecting From Web of "Not Skolem's Paradox – Part 3"

In the best case, what you get here is an encoding of addition for a subset of the model which happens to include the standard integers. That’s not in conflict with Tennenbaum’s theorem — for example, there’s nothing that prevents us from having a countable nonstandard model where the standard integer $n$ is represented by $2n$ and the nonstandard elements are all represented by odd numbers. In that case addition and multiplication of standard elements is easily possible. All Tennenbaum’s theorem says is that we can’t get a nonstandard model where the complete addition function is computable.

But we don’t even get that far — just because there’s a number inside the model that encodes the addition table for standard (and some nonstancard) elements doesn’t mean knowing that number lets us extract that information, working from the outside. Doing so would presumably require us to do some arithmetic inside the model (on nonstandard numbers) — but that’s exactly what we can’t do!

Also, you seem to be confused between “is not computable” and “does not exist in the metatheory”. The model and its addition and multiplication functions certainly exists in ZFC.


Note that we don’t even need choice for the model to exist, so ZF is enough — in fact even PA+con(PA) will suffice as the metatheory. By carefully tracing the details of the usual compactness argument and the proof of the completeness theorem, we can see that there must exist a nonstandard model of PA where the carrier set is $\mathbb N$ and the addition and multiplication are represented by particular $\Sigma^0_2$ arithmetical formulas.