2
$\begingroup$

I am working on the following problem:

Let $ S_{Arithmetic} = \{+, *, 0, 1\}, \mathfrak{M} $ a model for PA (first-order peano axioms) }, and $ \mathbb{N} = (\mathbb{N},+ ^{\mathbb{N}}, *^{\mathbb{N}},0^{\mathbb{N}},1^{\mathbb{N}} )$.

Construct an embedding $f : \mathbb{N} \rightarrow |\mathfrak{M}| $ and show that f is unique.


So, for $f$ to be an embedding, the following has to be true (correct me if I'm wrong):

  • $ 0^\mathfrak{M} = f(0^\mathbb{N}) $
  • $ 1^\mathfrak{M} = f(1^\mathbb{N}) $
  • $ +^\mathfrak{M} (f(a_0),f(a_1)) = f(+^\mathbb{N}(a_0,a_1)) $
  • $ *^\mathfrak{M} (f(a_0),f(a_1)) = f(*^\mathbb{N}(a_0,a_1)) $
  • $ f $ injective

Now, if I set $f$ to $f(x) := x$, it seems to me that all these properties are satisfied, but I am not sure what to do to prove this assignment and what to do to show that $f$ is unique.

I would be glad if someone could point me in the right direction.

2 Answers 2

1

First note that $|\frak M|$ need not have $\mathbb N$ as a subset. Why is this important? Because a function is still a subset of $\mathbb N\times|\frak M|$, and $f(x)=x$ would require $\mathbb N\subseteq|\frak M|$.

Now to show that $f$ can be defined in such way, we already know what $f(0)$ and $f(1)$ are. Recall that $f(n)=f((n-1)+1)=f(n-1)+f(1)$. So we really have only one way to extend $f$ to the rest of the natural numbers.

To show uniqueness suppose that $g$ is another embedding with these properties and use induction to show that $g(n)=f(n)$ for all $n\in\mathbb N$.

0

We can construct such an embedding by using finite recursion:

$f(0^\mathbb{N}):=0^\frak M$

$f(n+^\mathbb{N}1^\mathbb{N}):=f(n)+^\mathbb{\frak M}1^\mathbb{\frak M}$

Setting $n=0$, we can prove $f(1^\mathbb{N})=1^\frak M$

By induction on $m$, we show that

$f(n+^\mathbb{N}m)=f(n)+^\mathbb{\frak M}f(m)$

Then, also by induction on $m$, we show that

$f(n \cdot^\mathbb{N} m)=f(n)\cdot^{\frak M} f(m)$

To show $f$ is injective, we must assume $f(n)=f(m)$ and prove that $n=m$. We can accomplish this by induction on $m$ and by recalling that $n=0 \lor n=a+1$, for some $a$. For the base case, show a contradiction with the assumption that $n=a+1$ and for the successor case, show a contradiction with $n=0$ (use $0 \not = n+1$).

Together, these show that $f:\mathbb{N} \to \frak{M}$ and shows the isomorphism between the two structures. Thus, any two Peano systems are isomorphic.

To prove $f$ is unique, assume $f$ and $g$ satisfy these properties. You may prove $f(n)=g(n)$ by induction on $n$. The uniqueness of $f$ is also a consequence of finite recursion. (It is sufficient to prove that $g$ satisfies the two properties that defined $f$).