How to prove that a set is infinite iff it is Dedekind infinite?

I am going to replace some definitions by obviously equivalent ones. The benefit will be that the proofs are easier to understand. I am writing down very detailed proofs that you would not normally find in a college-level math textbook.

Definition: For $n \in \mathbb{N}$ define $[n] = \{k \in \mathbb{N} \mid k < n\}$.

Definition: The image of a map $f : X \to Y$ is the set $\mathrm{im}(f) = \{y \in Y \mid \exists x \in X \,.\, f(x) = y\}$.

Definition: A set $X$ is infinite when for every $n \in \mathbb{N}$ and every map $f : [n] \to X$ there is some $x \in X$ which is not in the image of $f$.

Lemma 1: An infinite set $X$ contains an element.

Proof. Because $X$ is infinite there is $x \in X$ which is not in the image of the unique map $[0] \to X$. QED.

Lemma 2: If $X$ is infinite then there exists a map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for every $n \in \mathbb{N}$ and every $f : [n] \to X$.

Proof. For every $n \in \mathbb{N}$ and $f : [n] \to X$ the set $X \setminus \mathrm{im}(f)$ contains an element because $X$ is infinite. By the axiom of choice there exists a choice map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for all $n$ and $f$. QED.

Here is an informal explanation of the map $c$. Given an infinite set $X$ and any elements $x_0, \ldots, x_{n-1} \in X$, we may view the tuple $(x_0, \ldots, x_n)$ as a map $f : [n] \to X$ where $f(k) = x_k$. By a slight abuse of notation we can then write $c(n,f)$ as $c(x_0, \ldots, x_{n-1})$. Now we see that $c$ accepts finitely many elements of $X$ and returns an element in $X$ which is different from all of them.

Proposition 1: If $X$ is infinite then there exists an injective map $i : \mathbb{N} \to X$.

Proof. By Lemma 1 there is $x \in X$ and let $c$ be the map from Lemma 2. Define $i$ by recursion: \begin{align*} i(0) &= x \\ i(n) &= c(i(0), \ldots, i(n-1)) \qquad\qquad \text{for $n \geq 1$} \end{align*} Clearly, $i$ is injective because $i(n)$ is chosen so that it is different from $i(0), i(1), \ldots, i(n-1)$. QED.

Proposition 2: If $X$ is infinite then it is in bijection with some proper subset $Y \subseteq X$.

Proof. Suppose $X$ is infinite. We seek a proper subset $Y \subseteq X$ and a bijection $f : X \to Y$. Let $i$ be the map from Proposition 1. Define $$Y = X \setminus \{i(0)\}$$ and define $b : X \to Y$ by $$b(x) = \begin{cases} x & \text{if $x \not\in \mathrm{im}(i)$}\\ i(n+1) & \text{if $x = i(n)$ for a (unique) $n \in \mathbb{N}$} \end{cases} $$ in words, $b$ takes $i(0)$ to $i(1)$, $i(1)$ to $i(2)$, and so on, and does not move elements which are outside the image of $i$. Clearly, $b$ is injective because $i$ is. It is surjective because the only element not in the image of $b$ is $i(0)$. QED.

Proposition 3: If $X$ is a set and $b : X \to Y$ a bijection from $X$ to a proper subset $Y \subseteq X$, then there is an injective map $j : \mathbb{N} \to X$.

Proof. Because $Y$ is a proper subset there exists $x \in X \setminus Y$. We define a map $j : \mathbb{N} \to X$ by recursion: \begin{align*} j(0) &= x \\ j(n) &= b(j(n-1)) \qquad\qquad\text{for $n \geq 1$} \end{align*} To prove that $j$ is injective, it suffices to verify that $j(m) \neq j(n)$ for all $m < n$. We do this by induction on $m$:

• if $m = 0$ then $j(0) = x$ is different from $j(n) = b(j(n-1))$ because $b(j(n-1)) \in Y$ and $x \not\in Y$.

• for the induction step, suppose we had $j(m) = j(n)$ for some $0 < m < n$. Then we would have $b(j(m-1)) = j(m) = j(n) = b(j(n-1))$ and because $b$ is a bijection it would follow that $j(m-1) = j(n-1)$, which is impossible by the induction hypothesis for $m-1$. Therefore it must be the case that $j(m) \neq j(n)$.

QED.

Theorem: A set is infinite if, and only if, it is equipotent with some proper subset.

Proof. If $X$ is infinite then we apply Propostion 2 to get a proper subset $Y \subseteq X$ which is equipotent with $X$.

Conversely, suppose we have a bijection $b : X \to Y$ for a proper subset $Y \subseteq X$. By Proposition 3 there is an injective map $j : \mathbb{N} \to X$. To see that $X$ is infinite, consider any $n \in \mathbb{N}$ and $f : [n] \to X$. There are $n+1$ distinct elements $j(0), j(1), \ldots, j(n) \in X$, and so at least one of them is not in $\mathrm{im}(f)$ because $\mathrm{im}(f)$ has at most $n$ elements. QED.

Let me address quickly the first part of the proof, $\Rightarrow$. You don't need to do it by contradiction. You can show that if $f\colon X\to A$ is a bijection, where $A$ is a proper subset of $X$, then there is an injection from $\Bbb N$ into $X$, and therefore $X$ is infinite.

To your second question, perhaps it would have been better to say "recursive construction", since many people only see "induction" as a method for proving statements and not for constructing mathematical objects (which they would say is a recursive definition).

The inductive step says, suppose that $\{a_1,\ldots,a_k\}$ is a defined set, let's define $\{a_1,\ldots,a_k,a_{k+1}\}$. How do we define it? We simply choose an element from $X\setminus\{a_1,\ldots,a_k\}$. Why can we do it? Because $X$ is infinite and we only removed a finite set from $X$.

You might argue, what is $a_{k+1}$? Which element is it? Well, you can't quite pinpoint that element, because you have to make some arbitrary choice and you have to appeal to the axiom of choice. Namely, we first fix some "black box operation" that given a non-empty subset of $X$, it will give us back an element of that subset. And then we use this black box to choose $a_{k+1}$.

So no one is constructing a bijection between an infinite set and a singleton. We construct an infinite set, then we show that this set is denumerable. But that's quite simple because we literally chose for each $n$ a different element, so the map $k\mapsto a_k$ is necessarily an injection.