Infinite subset of natural numbers

Question

I want to show that if the set $A$ is an infinite subset of natural numbers $N$, then $\text{card}(A)=\text{card}(N)$. To do so, it suffices to find an injective function $f:N\rightarrow A$.

One natural way to construct $f$ is as follows: we assign to $f(1)$ the smallest element of $A$. Then we omit the smallest element of $A$ and we assign to $f(2)$ the smallest element of the remaining numbers and so on.

I do not want to use the well ordering principle. I argue as follows. I assign to $f(1)$ an arbitary element of A like $a_1$.Then I remove $a_1$ from $A$ and assign to $f(2)$ an arbitrary element of $A/a_1$. Since $A$ is infinite, I can assign to $f(n)$ a number from $A$ for any $n$ because $A$ never gets empty.

Do I need to use the axiom of choice here??

Answer 1

No. You don't need the axiom of choice. $\Bbb N$ is well-ordered without relying on the axiom of choice, indeed it is a defining property of $\Bbb N$: it is the unique non-empty linear order that is well-ordered, without a maximal, and every element has a successor.

The thing about the term "arbitrary" is that you're effectively hiding a choice function from the non-empty subsets of $A$ (or at least the co-finite subsets). So the question is why such a function exists, and in order to prove this you'll need to resort to proving that $A$ is either countable, or at least there is an injection from $\Bbb N$ into $A$.

So you run into a slight circularity. Of course, the axiom of choice might be used for the argument a priori, and then removed in the a postriori by arguing "actually since there is a well-ordering of $A$ as a subset of $\Bbb N$ here's a choice function".

Answer 2

Yes, you do need some amount of the axiom of choice to run the argument you're describing (although of course the result doesn't need choice at all, and there's absolutely no reason to avoid using the well-orderedness of $\mathbb{N}$). Specifically, you're using dependent choice.

---

It's worth noting that the following statement is not provable in $\mathsf{ZF}$ (= set theory without choice) alone:

If $X$ is infinite, then there is an injection $\mathbb{N}\rightarrow X$.

(Sets not admitting an injection from $\mathbb{N}$, or equivalently sets with no non-surjective self-injection, are called Dedekind-finite; in $\mathsf{ZFC}$ every Dedekind-finite set is finite, but this is not provable in $\mathsf{ZF}$ alone. In fact, it is consistent with $\mathsf{ZF}$ that there is an infinite Dedekind-finite set of real numbers!)

So if you want to prove "Every infinite set of natural numbers admits a surjection from $\mathbb{N}$" without using the axiom of choice, you need to at some point use something particular about the natural numbers - such as their well-orderedness. Given that the well-orderedness of $\mathbb{N}$ is basically its most fundamental property, this isn't exactly a high cost.