Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.