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

 

[issacnewton]

Thanks for the input. $s$ and $s'$ both satisfy Peano postulates as stated in the problem. So, they are injective.
By letting $a = s(p)$ and $b = s(q)$, I proved in post #3 that $f(p) = f(q)$, which is where I was struck. Do we have to make assumption that $a$ is the least member such that $f(a) = f(b)$ ?

 

[fresh_42]

Thanks for the input. $s$ and $s'$ both satisfy Peano postulates as stated in the problem. So, they are injective.
By letting $a = s(p)$ and $b = s(q)$, I proved in post #3 that $f(p) = f(q)$, which is where I was struck. Do we have to make assumption that $a$ is the least member such that $f(a) = f(b)$ ?

Probably not necessarily. I was a bit dizzy toward the end because I tried various ways and dead-end roads before I ended up with what I had posted. So it isn't ruled out that there might be a more elegant way. The idea with the minimal $a$ is that it uses the fact that $\mathbb{N}$ is bounded from below. It is shorter than saying "Repeat the argument until $a=1$" and then deal with this special case. The minimality argument occurs quite often in statements about natural numbers so I'm kind of used to it. It is like stretching a net at the beginning of the proof in order to have it in place if necessary.

The whole idea of the proof is to define $f$ with the two properties, the "induction base" $f(1)=1'$ and the recursion identity $f\circ s= s'\circ f$ meaning $f(n+1)=f(n)+1'.$ This is all we have and it explicitly defines $f(n+1)$ by means of its predecessor $f(n).$ That invites literally to assume the smallest $n$ that does not satisfy a property, in our case injectivity and surjectivity.

The other possibility would be an induction proof along $s$ and $s'$. Try it! It's likely more elegant.

 

[issacnewton]

Since you are using minimality arguments here, I have a question. Is this the use of well ordering principle ?

 

[fresh_42]

Since you are using minimality arguments here, I have a question. Is this the use of well ordering principle ?

No. Well-ordering is equivalent to the axiom of choice. We do not select an element by the axiom of choice, we assume the existence of a counterexample and use an indirect proof. If there is a counterexample, then there is a minimal one because the natural numbers are totally ordered by $s$ and bounded from below so that minimality does not lead to minus infinity. It is a typical argument when natural numbers are involved. We have a total ordering and all non-empty sets always have a minimal element.

Abstract algebra often uses the axiom of choice and sometimes without mentioning it, but not in this case.

 

[issacnewton]

I have studied proof techniques from Daniel Velleman's book "How to prove it". He didn't mention this technique there. So, this is new to me. But it does make sense. So, we can use minimality argument when we have any set $A$, such that there is a bijection $f: A \rightarrow \mathbb{N}$ and $A$ has a lower bound. Would that be right way to say it ? Can you give me other examples of proofs where this argument is made ? I am self learning analysis, so that would be helpful.

 

[fresh_42]

I have studied proof techniques from Daniel Velleman's book "How to prove it". He didn't mention this technique there. So, this is new to me. But it does make sense. So, we can use minimality argument when we have any set $A$, such that there is a bijection $f: A \rightarrow \mathbb{N}$ and $A$ has a lower bound. Would that be right way to say it ? Can you give me other examples of proofs where this argument is made ? I am self learning analysis, so that would be helpful.

Almost. We only need $A\neq \emptyset .$ Sure, if $A$ is infinite then there is a bijection $f,$ but this is an artificial view on $A$ and if $A$ is finite, then there are automatically a lowest and a largest element since $s$ is a total ordering.

However, we do not need to consider the size of $A$. Of course, we need that $A$ is not empty. If $1\in A$ then $1$ is the minimal element of $A$ and we are done. Otherwise, we define recursively
$$
A_0:=A \quad \text{ and } \quad A_k:=\{y\in \mathbb{N}\,|\,s^{-1}(y)\in A_{k-1}\} \;\text{ for } \;k \ge1
$$
As soon as $1\in A_k$ for some $k\in \mathbb{N},$ we have found the minimal element of $A$ which is the unique one with $s^{-k}(x)=1.$ The existence of such a chain is provided by your lemma. It remains to show that there always exists a $k\in \mathbb{N}$ such that $1\in A_k.$

If this wasn't the case, then we can select any element of $x\in A$ and define the sequence $(s^{-k}(x))_{k\in \mathbb{N}}$ that does not contain $1.$ But $s^{-k}(x) < s^{-k+1}(x)$ and we cannot decent infinitely within $\mathbb{N}$ as it is bounded from below by $1.$

Edit: I corrected the power of $s$. We need the unique predecessor, not the successor, so the powers are negative (sorry). Uniqueness in the statement of the lemma guarantees that there is only one (or none in case we arrive at $1$).

 

[fresh_42]

I have studied proof techniques from Daniel Velleman's book "How to prove it". He didn't mention this technique there.

You can find it in Richard Hammack's "Book of Proof" in chapter 10 (Mathematical Induction) as 10.3. Proof by Smallest Counterexample.