- #1

issacnewton

- 1,020

- 35

- Homework Statement
- Suppose that the set ##\mathbb{N}## together with the element ##1 \in \mathbb{N}## and the function ##s: \mathbb{N} \rightarrow \mathbb{N}##, and that the set ##\mathbb{N}'## together with the element ##1' \in \mathbb{N}'## and the function ##s' :\mathbb{N}' \rightarrow \mathbb{N}' ##, both satisfy the Peano Postulates. Prove that there is a bijective function ##f :\mathbb{N} \rightarrow \mathbb{N}' ## such that ##f(1) = 1'## and ## f\circ s = s' \circ f##. The existence of such a bijective function proves that the natural numbers are essentially unique.

- Relevant Equations
- Theorem (definition by recursion)--> Let ##H## be a set, let ##e \in H## and let ##k : H \rightarrow H## be a function. Then there is a unique function ## f: \mathbb{N} \rightarrow H## such that ##f(1) = e## and that ## f \circ s = k \circ f ##.

Following is a set of Peano postulates I am using.

There exists a set ##\mathbb{N}## with an element ##1 \in \mathbb{N}## and a function ##s: \mathbb{N} \rightarrow \mathbb{N} ## that satisfy the following three properties.

1) There is no ##n \in \mathbb{N}## such that ##s(n) = 1##

2) The function ##s## is injective.

3) Let ##G \subseteq \mathbb{N}## be a set. Suppose that ##1 \in G##, and that if ##g \in G## then ##s(g) \in G##. Then ## G = \mathbb{N} ##

===============================================================

Now, we are given that ##\mathbb{N}'## is a set and ##1' \in \mathbb{N}'## and ##s' :\mathbb{N}' \rightarrow \mathbb{N}' ## is a function. So, using the recursion theorem, there is a unique function ##f : \mathbb{N} \rightarrow \mathbb{N}'## such that ##f(1) = 1'## and ## f\circ s = s' \circ f##. This part is easy. But I am stuck on how to prove that ##f## is a bijection. Should I start with ##f(a) = f(b)## and then try to prove that ##a = b## for ##f## to be one to one ? But I don't get anywhere with this. Any hints will be helpful.

Thanks

Thanks