Equivalence: Injective function from natural numbers to a set $X$, and injective but not surjective function from $X$ to $X$

Question

How do I go about proving the equivalence of these statements?
(1) There is an injective function $f: \mathbb{N} \rightarrow X$
(2) There is an injective but not surjective function $g:X \rightarrow X$

Answer 1

Let's first assume that (2) holds. Let $g: X \to X$ be a function, which is surjective, but not not injective. From this we can deduce, that the set $X$ contains infintely many elements, since for a finite $X$ every injective function is also surjective. We now choose a $x_1 \in X$. Suppose that $x_1, \ldots, x_n \in X$ have been chosen. Then we choose a $x_{n+1} \in X$, such that $$ x_{n+1} \neq x_i \quad \text{for } i = 1, \ldots, n \; .$$ This is possible, because $X$ contains infinately many elements. Now we can define $g: \Bbb N \to X$ as $$ g(n) := x_n \; ,$$ and we see that $g$ is injective, since for $n, m \in \Bbb N$ with $n \neq m$ we have $$ g(n) = x_n \neq x_m = g(m) \; , $$ by construction of our sequence $\{x_n \}_{n=1}^\infty$.

Now assume that (1) holds. Define $g: X \to X$ as $$g(x) := \begin{cases} f\left( f^{-1}(x)+1 \right) \; , & \text{if } x \in f(X) \\ x \; , & \text{if } x \not\in f(X) \end{cases} \; .$$ We claim that $g$ is injective, but not surjective. Let $x,y \in X$ with $x \neq y$.

• If $x \in f(X)$, $y \not\in f(X)$, then we have $g(y) = y$, but $g(x) = f\left( f^{-1}(x) + 1 \right) \neq y$, since $y \not\in f(X)$, so $g(x) \neq g(y)$.
• If $x, y \in f(X)$, then $f^{-1}(x) \neq f^{-1}(y)$, so $$g(x) = f( f^{-1}(x) + 1) \neq f(f^{-1}(y) + 1) = g(y) \; $$ since $f$ is injective.
• If $x,y \not\in f(X)$, then $g(x) = x \neq y = g(y)$.

This shows that $g$ is injective. To see that $g$ is not surjective, consider the element $f(1) \in X$. If we assume that $g$ is sujective, then there exists a $y \in X$, such that $$ g(y) = f(1) \; .$$ This means that $$f(f^{-1}(x) + 1) = f(1) \; ,$$ so $$ f^{-1}(x) + 1 = 1 \; ,$$ which is a contradiction, because $f^{-1}(x) \geq 1$. So we have shown, that $g$ is injective but not surjective.

Answer 2

$\bf (1) \Rightarrow (2)$

Define $g$ as:

$$ g(x) = \begin{cases} f(f^{-1}(x)+1) & \text{if $x$ is in the image of $f$} \\ x & \text{otherwise} \end{cases} $$

Then $g$ is injective, but no element maps to $f(1)$.

---

$\bf (2) \Rightarrow (1)$

Assume that $(1)$ is not true. Then $X$ must be finite. If $X$ has $n$ elements, then an injective function $g$ must map these $n$ elements of $X$ to $n$ distinct elements, i.e., the whole set. Thus $(2)$ cannot be true either, and we have proof by contradiction.