Intereting Posts

Easy way to find out limit of $a_n = \left (1+\frac{1}{n^2} \right )^n$ for $n \rightarrow \infty$?
Find the condition on $a$ and $b$ so that the two tangents drawn to the parabola $y^2=4ax$ from a point are normals to the parabola $x^2=4by$
Evaluating Combination Sum $\sum{n+k\choose 2k} 2^{n-k}$
How do we show the equality of these two summations?
Wielandt's proof of Sylow's theorem.
Switching from Mathematica to MATLAB: As a text editor?
Solving the general quadratic congruence mod $2^k$
Why does the graph of $e^{1/z}$ look like a dipole?
Books like Grundlagen der Analysis in French
How do you pronounce the symbol $'$ in $f'$?
Tablet for reading textbooks and writing math by hand?
If $g$ is a primitive root of $p^2$ where $p$ is an odd prime, why is $g$ a primitive root of $p^k$ for any $k \geq 1$?
Why doesn't $\sum_{n=1}^\infty \frac{1}{n^{1+\frac{1}{n}}}$ converge?
Fundamental group and path-connected
How to Compute $\frac{d}{dx}\left(\left(1+x^2\right)^x\right)$?

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$:

- What books to use to start studying Mathematical Logic?
- Are non-standard models always not well-founded?
- Does “This is a lie” prove the insufficiency of binary logic?
- Why is compactness in logic called compactness?
- How can some statements be consistent with intuitionistic logic but not classical logic, when intuitionistic logic proves not not LEM?
- Turing's 1939 paper on ordinal logic

$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)?

- Deduction Theorem + Modus Ponens + What = Implicational Propositional Calculus?
- Most astonishing applications of compactness theorem outside logic
- Complete calculus of first-order logic working for empty structures too
- intersection of the empty set and vacuous truth
- Does weak completeness (“If $\vDash\phi$, then $\vdash\phi$”) imply strong completeness (“If $\Gamma\vDash\phi$, then $\Gamma\vdash\phi$”)?
- Substitution for bound variables in logic
- Purpose of the Peano Axioms
- Can someone explain Gödel's incompleteness theorems in layman terms?
- Does the existence of a $\mathbb{Q}$-basis for $\mathbb{R}$ imply that choice holds up to $\frak c$?
- Peano Arithmetic before Gödel

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.

- Algebra of matrices — equivalence of norms
- A puzzle with powers and tetration mod n
- Calculate the angle of a vector in compass (360) direction
- Hard integral that standard CAS get totally wrong
- For $n \geq 2$, show that $n \nmid 2^{n}-1$
- Who invented or used very first the double lined symbols $\mathbb{R},\mathbb{Q},\mathbb{N}$ etc
- How does knowing a function as even or odd help in integration ??
- Show $\vert G \vert = \vert HK \vert$ given that $H \trianglelefteq G$, $G$ finite and $K \leq G$.
- Where is Cauchy's wrong proof?
- If $x^5 = x$ in a ring, is the ring commutative?
- About Mellin transform and harmonic series
- Counterexamples for “every linear map on an infinite dimensional complex vector space has an eigenvalue”
- Finding range of $\frac{x}{(1-x)^2}$
- How to deal with misapplying mathematical rules?
- Proving the irrationality of $e^n$