Theorem 4.15 page 22, Real and Abstract Analysis, Hewitt and Stromberg

Question

Following is Theorem 4.15 from Real and Abstract Analysis, Hewitt and Stromberg

Theorem: Every infinite set has a countably infinite subset.

Proof: Let $A$ be a infinite set. We show by induction that for each $n \in \mathbb{N}$ there exists a set $A_n \subset A$ such that $|A|=n$. Indeed $A \neq \emptyset$, there exists $A_1 \subset A$. If $A_n \subset A$ and $|A|=n$, then since $A$ is infinite, there exists $x \in A-A_n$. Letting $A_{n+1}=A \cup \{x\}$, we have $A_{n+1} \subset A$ and $|A_{n+1}|=n+1$.

Next let $\{A_n\}_{n \in \mathbb{N}}$ be any family of subsets of $A$ described above. [Notice the use of Axiom of choice in selecting this family] ......

I do not understand the use of Axiom of Choice in the proof.

Answer 1

First let me point out that without the axiom of choice it is possible to prove that if $A$ is infinite, then for every finite $n$, there is a subset of $A$ of size $n$.

The proof here, however, chooses and glues up such subsets into a countably infinite subset.

Where is the axiom of choice hiding? At each step you chose $x$, and this choice was arbitrary. You made infinitely many steps, therefore you had to use the axiom of choice.

And indeed, it is consistent with the failure of the axiom of choice that there are infinite sets which do not have a countably infinite subset. One classical example is an infinite set which cannot be written as a disjoint union of two infinite sets (meaning, every subset is finite or its complement is finite). I'll leave you to think about why this is an example.

Answer 2

First, let us remind ourselves of what the Axiom of Choice is. It can be written as:

For every indexed family $\{S_i\}_{i \in I}$ of non-empty sets there exists an indexed family $\{x_i\}_{i \in I}$ of elements such that $x_i \in S_i$ for every $i \in I$.

In our case, our index is $\mathbb{N}$ and our family of non-empty sets is $\{A-A_n\}_{n \in \mathbb{N}} $. In every induction step we have to show we have an $x_n \in A-A_n$. Since we need to do this an infinite number of times, we need the Axiom of Choice to gives us our indexed family $\{ x_n \}_{n \in \mathbb{N}}$.

Without using the Axiom of Choice we could not assume that we can make infinitely many arbitrary choices to get our $x_n$ and thus we couldn't assume that our induction step holds for every $n$.