This is from an introduction to mathematical proofs a transition to advanced mathematics.

Let $g:\mathbb{N}\to A \cup \{x\}$ such that

$$g(n) = \begin{cases} x \ \ &\text{if} \ \ n=1\\ f(n-1) \ \ &\text{if} \ \ n\neq 1 \end{cases}$$ where $f:\mathbb{N}\to A$, where $A$ is denumerable or countably infinite and $f$ is a one-to-one correspondence or bijection.

Attempted proof - Suppose $n_1$ and $n_2$ are integers.

Case 1: If $n_1 = 1$ and $n_2 = 1$ then $$g(n_1) = g(n_2) \Leftrightarrow 1 = 1$$

Case 2: If $n_1\neq 1$ and $n_2\neq 1$ then

$$g(n_1) = g(n_2) \Leftrightarrow f(n_1 - 1) = f(n_2 - 1) \Leftrightarrow n_1 = n_2$$

Case 3: If $n_1 = 1$ and $n_2 \neq 1$ then

$$g(n_1) = g(n_2) \Rightarrow 1 = f(n_2 - 1)$$

What happens from there? I assume case 3 arrives at some contradiction but I am lost from here. Unless taking the inverse of both sides leads to $n_2 = 1$ which is a contradiction but I am not sure if that is true.

Also I am not sure how to prove that $g(n)$ is onto.

  • $\begingroup$ You have argued as if $f$ is a bijection, but this is not stated anywhere as a hypothesis. Perhaps a full statement of the problem in the body of the question would be a good idea. $\endgroup$ – Gerry Myerson Mar 7 '19 at 6:44
  • $\begingroup$ @GerryMyerson Sorry I edited my question $f$ is a bijection. $\endgroup$ – Wolfy Mar 7 '19 at 6:54
  • $\begingroup$ May one assume $x\notin A\,$? $\endgroup$ – Christian Blatter Mar 7 '19 at 8:47

You need $f$ to be a bijection, as pointed out by @Gerry Myerson.

For surjectivity, you need that $\forall y\in A\cup\{x\}\,,\exists m\in\Bbb N$ such that $g(m)=y$.

If $y\in A\cup\{x\}$, then $y\in A$ or $y=x$.

If $y\in A$, then $g(m)=y$, where $m-1=f^{-1}(y)$.

And if $y=x$, then $g(1)=y$.

Thus $g$ is onto.


To prove $g$ is injective, arguing in cases for what $n_1,n_2$ are isn't the way to do it. The basic way to prove anything is injective is to prove $f(x_1) = f(x_2) \implies x_1 = x_2$.

Suppose $g(n_1) = g(n_2)$. If $g(n_1) = g(n_2) = x$, then $n_1 = n_2 = 1$. If $g(n_1) = g(n_2) \in A$, then $g(n_1) = f(n_1 - 1) = f(n_2 -1) \implies n_1 -1 = n_2 -1 \implies n_1 = n_2$, since $f$ is injective.

To prove this function is surjective prove that $\forall a \in A\cup\{x\}, \exists n\in \mathbb{N}$ such that $f(n)=a$.

If $a=x$ then choose $n=1$ and we are done. If $a\in A$, then $\exists m \in \mathbb{N}$ such that $f(m) = a$, since $A$ is surjective. Let $n = m+1$. Then $g(n) = a$.

  • $\begingroup$ Are my first two cases wrong then? $\endgroup$ – Wolfy Mar 7 '19 at 7:19
  • $\begingroup$ Yea, those two cases can hold for an $f$ that isn't injective. Consider $f:\mathbb{N} \to \mathbb{N}$ $$f(n) =\begin{cases} n\ \ &\text{if} \ \ n=1\\ n-1 \ \ &\text{if} \ \ n\neq 1 \end{cases} $$ $\endgroup$ – Anthony Ter Mar 7 '19 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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