Problem involving recursion theorem

[issacnewton]

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

 

[fresh_42]

The standard proofs in algebra and about natural numbers use indirect methods. This theorem has a logical aspect, so I'm not sure whether an indirect proof is allowed in your specific setup.

If so assume ##f## is not injective (subjective) and find a contradiction. Or, use the fact that ##\mathbb{N}## and ##\mathbb{N}'## are totally ordered: assume the smallest element that breaks the assumption and construct a smaller one that also breaks the assumption.

 

[issacnewton]

Ok, fresh_42, taking hints from you, following is my proof. Assume to the contrary that ##f## is not one to one. Then ##\exists a,b \in \mathbb{N}## such that ##f(a) = f(b) ## and ## a \ne b ##. I am going to use a Lemma here, which I have already proven.
Lemma: Let ##x \in \mathbb{N}##. Suppose that ## x \ne 1##. Then there is a unique ## y \in \mathbb{N}## such that ## x = s(y) ##.

Now, we will consider three cases here

Case 1) ## a = 1## and ##b \ne 1##
Using Lemma above, there is some ##m \in \mathbb{N}## such that ##b = s(m)##. Since ##f(a) = f(b) ##, this means that ##f(1) = f(s(m)) ##. But, we have, ## f \circ s = s' \circ f##. So, ##f(s(m)) = s'(f(m))##. Since ##f(1) = 1'##, we have ##s'(f(m)) = 1'##. But, according to the Peano postulates, there is no ##n' \in \mathbb{N'}## such that ## s'(n') = 1'##. So, we have reached a contradiction.

Case 2) ## a \ne 1## and ##b = 1##
This case is similar to the case above and reasoning is along the same line.

Case 3) ##a \ne b## and ##a \ne 1## and ##b \ne 1##
Again using the Lemma, there are some ##p, q \in \mathbb{N}## such that ##a = s(p)## and ##b = s(q)##. Since ##f(a) = f(b) ##, it follows that ##f(s(p)) = f(s(q)) ##. But, ## f \circ s = s' \circ f##, so,

$$ s'(f(p)) = s'(f(q)) \cdots\cdots (1)$$

Since ##s'## is one to one function, it follows that ##f(p) = f(q)##. But I am stuck here and no idea what to do. Also, I forgot to write part of the problem where author gives some hints. He says that find an inverse for ##f## by using existence part of the recursion theorem again and then prove that the function you found is an inverse of ##f## by using the uniqueness part of the same theorem.
So, let ##\mathbb{N}## be a set and ##1 \in \mathbb{N}## and ## s: \mathbb{N} \rightarrow \mathbb{N}## is a function. Then according to the theorem, there is a unique function ##f' : \mathbb{N'} \rightarrow \mathbb{N}## such that ##f'(1') = 1 ## and ## f' \circ s' = s \circ f'##. Now, how do I prove that this is indeed the inverse of the function ## f## ?

 

[fresh_42]

Ok, fresh_42, taking hints from you, following is my proof. Assume to the contrary that ##f## is not one to one. Then ##\exists a,b \in \mathbb{N}## such that ##f(a) = f(b) ## and ## a \ne b ##. I am going to use a Lemma here, which I have already proven.
Lemma: Let ##x \in \mathbb{N}##. Suppose that ## x \ne 1##. Then there is a unique ## y \in \mathbb{N}## such that ## x = s(y) ##.

Now, we will consider three cases here

Case 1) ## a = 1## and ##b \ne 1##
Using Lemma above, there is some ##m \in \mathbb{N}## such that ##b = s(m)##. Since ##f(a) = f(b) ##, this means that ##f(1) = f(s(m)) ##. But, we have, ## f \circ s = s' \circ f##. So, ##f(s(m)) = s'(f(m))##. Since ##f(1) = 1'##, we have ##s'(f(m)) = 1'##. But, according to the Peano postulates, there is no ##n' \in \mathbb{N'}## such that ## s'(n') = 1'##. So, we have reached a contradiction.

Case 2) ## a \ne 1## and ##b = 1##
This case is similar to the case above and reasoning is along the same line.

Case 3) ##a \ne b## and ##a \ne 1## and ##b \ne 1##
Again using the Lemma, there are some ##p, q \in \mathbb{N}## such that ##a = s(p)## and ##b = s(q)##. Since ##f(a) = f(b) ##, it follows that ##f(s(p)) = f(s(q)) ##. But, ## f \circ s = s' \circ f##, so,

$$ s'(f(p)) = s'(f(q)) \cdots\cdots (1)$$

Since ##s'## is one to one function, it follows that ##f(p) = f(q)##. But I am stuck here and no idea what to do. Also, I forgot to write part of the problem where author gives some hints. He says that find an inverse for ##f## by using existence part of the recursion theorem again and then prove that the function you found is an inverse of ##f## by using the uniqueness part of the same theorem.
So, let ##\mathbb{N}## be a set and ##1 \in \mathbb{N}## and ## s: \mathbb{N} \rightarrow \mathbb{N}## is a function. Then according to the theorem, there is a unique function ##f' : \mathbb{N'} \rightarrow \mathbb{N}## such that ##f'(1') = 1 ## and ## f' \circ s' = s \circ f'##. Now, how do I prove that this is indeed the inverse of the function ## f## ?

Before you start proving details about ##f##, you have to prove the existence of such a function! The lemma you quoted is the key to doing so. We set ##f(1)=1'.## Now for ##n>1## there is - according to the lemma - an ##m\in \mathbb{N}## such that ##s(m)=n## and we can define recursively
$$
f(n)= f(s(m)):= s'(f(m)) =s'(m').
$$
Now we have defined the function ##f## so that it automatically fulfills the requirements ##f(1)=1'## and ##f\circ s= s'\circ f.## (Note that ##s## and ##s'## could be any ordering of natural numbers, and ##f## any permutation. We do not know that ##s(1)=2## or ##s(1')=2'.## We only know that ##s^{-1}(1)=\emptyset ## and ##s'^{-1}(1')=\emptyset .## However, we may assume that ##>## and ##<## in ##\mathbb{N}## are given by the ordering ##s## and ##>## and ##<## in ##\mathbb{N}'## are given by the ordering ##s'.##)

Now we can use your arguments with the lemma. I think they can be shortened a bit ...

Assume ##f(a)=f(b)## with ##a\neq b.## If ##a=1## then there is an ##m\in \mathbb{N}## such that ##s(m)=b## because ##b\neq a=1## according to the lemma. Hence ##f(b)=f(a)=f(1)=1'## and ##f(b)=f(s(m))=s'(f(m))=s'(m')## by definition of ##f.## Hence, ##s'(m')=1',## but there is no such number in the system ##(1',s',\mathbb{N}').## So ##a>1.## We also have ##b>1## for the same argument with ##b.##

... but the idea is correct.

Now let ##a## be the smallest (according to ##s##) number such there exists a ##b\in \mathbb{N}-\{a\}## such that ##f(a)=f(b).## This implies that ##1<a<b## by the previous argument and that there are ##\bar a,\bar b\in \mathbb{N}## such that ##s(\bar a)=a## and ##s(\bar b)=b## according to the lemma.

I further assume that we already know that ##\mathbf s## and ##\mathbf s'## are injective. If not, prove it here.
$$
f(a)=f(s\bar a)=s'(f(\bar a))=f(b)=f(s\bar b)=s'(f(\bar b)) \Longrightarrow f(\bar a)=f(\bar b)
$$
contradicting the minimality of ##a.##

This shows that ##f## is injective since there is no minimal counterexample.

Assume that ##n'\in \mathbb{N}'## is the smallest number with no preimage under ##f.## Then ##n'>1'## since ##f(1)=1'## has a preimage. Chose ##s'(m')=n'.## Then ##n'=s'(m') =s'(f(m))=f(s(m))## and ##s(m)## would be a preimage. Since there is no such preimage per assumption, we conclude that ##m=1## as the only element without a number ##s(m).## But this means ##n'=s'(m')=s'(f(1))=s'(1')## contradicting the fact that ##1'\in \mathbb{N}'## has no predecessor.

 

[fresh_42]

Another idea for surjectivity is the following. Set ##G':=f(\mathbb{N})\subseteq \mathbb{N}'.## Then ##1'=f(1)\in \mathbb{N}'.## Let ##g'\in G'-\{1\}, ## i.e. ##g'=f(n)## for some ##n\in \mathbb{N}-\{1\}.## We rule out ##g'=1'## since we want to show ##s'(g')\in G'.## Since ##f## is injective, ##n## cannot be ##1## and ##s(n)## exists. Then
$$
s'(g')=s'(f(n))=f(s(n)) \in f(\mathbb{N})=G'.
$$
Therefore ##G'=\mathbb{N}'## by property 3 in post ##1## for the system ##(1',s',\mathbb{N}').##