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

Question

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.

Answer 1

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.

Answer 2

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$.