Given an arbitrary infinite set $S$, how to construct an injection $\mathbb{N} \to S$ with the Axiom of Choice?

Question

Let $S$ be an arbitrary infinite set. As a part of our homework, I have the following question:

Question: How can I construct an injection $\mathbb{N} \to S$?

Intuitively, I understand that such an injection should exist but describing it explicitly is probably not possible. Therefore, I think we need to use the

Axiom of Choice: If $X$ is a set of non-empty sets, then there exists a choice function $F$ on $X$, i.e. a function on $X$ such that for all $M \in X$, we have $F(M) \in M$.

Our class was given the following hint: Construct a family of $A_n \subseteq S$ with $|A_n| = 2^n$ for all $n \in \mathbb{N}$. Next, construct a family $B_n \subseteq S$ of non-empty and pairwise disjoint subsets.

However, I do not really know what to do with this hint. Maybe the condition $|A_n| = 2^n$ indicates that we should use the power set of some set with $n$ elements but that is just a vague idea.

I would really appreciate it if you could help me advancing with this problem.

Answer 1

How would you naively argue that an infinite set has an injection from $\Bbb N$ into the set?

Well, pick some $x_0$, then suppose that $\{x_0,\dots,x_{n-1}\}$ were chosen, since the set is infinite, there is some $x_n$ which is different from those $n$ elements. So we defined $\{x_n\mid n\in\Bbb N\}$, which is clearly the range of an injection from $\Bbb N$ into the set.

Where did we use the axiom of choice? Well, the choice of $x_0$ was arbitrary, but the choice of $x_1$—while arbitrary—depends on the choice of $x_0$, since $x_1\neq x_0$ by design. And the choice of $x_{216}$ depends on the $216$ previous choices. So the choice here is literally in the ability to consolidate the real proof that an infinite set has arbitrarily large finite subsets, into a proof that it has a countably infinite subset.

Where did we use choice? We chose the $x_n$. So by fixing a choice function, $F$, and applying the recursion theorem to choose $F(n)$ from $X\setminus\operatorname{rng}(F\restriction n)$ we can get our infinite sequence.

---

Fun exercise. The above proof relies on the principle of dependent choice, but we can still prove that every infinite set has a countably infinite subset from the weaker "axiom of choice for countable families of sets".

Answer 2

I am assuming that your definition of infinite is such that $S$ is infinite if for each $n\in\Bbb Z^+$ there is an injection $f_n$ of $\{1,\ldots,n\}$ into $S$ (or something from which that can easily be inferred). For each $n\in\Bbb N$ let $A_n=f_{2^n}\left[\left\{1,\ldots,2^n\right\}\right]$.

• Show that $A_n\setminus\bigcup_{k<n}A_k\ne\varnothing$ for each $n\in\Bbb N$. HINT: What is the largest possible value of $\sum_{k<n}|A_k|$?

Now let $B_n=A_n\setminus\bigcup_{k<n}A_k$ for each $n\in\Bbb N$ and apply the axiom of choice to $\{B_n:n\in\Bbb N\}$ to construct an injection from $\Bbb N$ to $S$.