# Proving a function from $\mathbb{N}\to A\cup \{x \}$ is a bijection.

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.

• 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. – Gerry Myerson Mar 7 '19 at 6:44
• @GerryMyerson Sorry I edited my question $f$ is a bijection. – Wolfy Mar 7 '19 at 6:54
• May one assume $x\notin A\,$? – 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$$.

• Are my first two cases wrong then? – Wolfy Mar 7 '19 at 7:19
• 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}$$ – Anthony Ter Mar 7 '19 at 7:35