Proof involving functions

Question

Prove that $q(n) = n$ is the only onto function that satisfies $q \circ p = p \circ q$

Answer 1

Let $p, q: \mathbb{N} \longrightarrow \mathbb{N}$ be given by $p(n)=n+1$, $q(n)=n$.

It is clear that $p \circ q = q \circ p$ and that $q$ is surjective.

To see that $q$ is the unique surjection from $\mathbb{N}$ to $\mathbb{N}$ such that $p \circ q = q \circ p$, assume we are given a surjection $r: \mathbb{N} \longrightarrow \mathbb{N}$ such that $r \circ p = p \circ r$.

We show that $q = r$.

Note that $r$ must be a total function.

For $n$ a natural number, $(r \circ p)(n) = r(n+1) = r(n)+1 = (p \circ r)(n)$.

Since $r$ is surjective, there exists $m \in \mathbb{N}$ such that $r(m)=1$.

Assume that $m \neq 1$. Then $m > 1$ and so $r(m-1)$ is defined.

Noticing that $r(m)-r(m-1)=1$, we see that $r(m-1)=r(m)-1=0$, which is impossible. Thus $m=1$.

That $r(n)=n$ for all $n$ follows by induction. $\Box$