# Prove infinite set has cardinality greater or equal to $\mathbb{N}$ without axiom of choice

There are two related posts but I didn't see the satisfied answer there:

My question is how to prove infinite set has cardinality greater or equal to $$\mathbb{N}$$ without axiom of choice, and for generality without using contradiction?

Since $$\mathbb{N}$$ was constructed through the inductive sets, I can hardly see a direct construction of a function $$f$$.

The possible solution I have right now seemed to be using the recursion theorem and define $$g(f_n,n)$$ to be the elements of $$B-\{f_0,...,f_n\}$$, but this seem to be impossible without AC.

Another way I thought about is argue that one can pick a sequence $$b_0,...,$$, such that $$b_i\neq b_j$$ for $$i\neq j$$. The sequence won't end other wise $$B$$ will be finite. But this required the usage of contradiction.

How to ptove the theorem without axiom of choice and the usage of contradiction?

• How do you define a set to be infinite? – Abstract Analysis Oct 30 '18 at 5:46
• @LeAnhDung the standard definition from Introduction to set thoery. $\mathbb{N}=\{ x|x\in I$ for every inductive set $I \}$. – ShoutOutAndCalculate Oct 30 '18 at 5:49
• No, I meant $X$ is infinite $\iff\cdots$ – Abstract Analysis Oct 30 '18 at 5:50
• @LeAnhDung If $X$ is not finite, then $X$ is infinite, so there is no bijection between $X$ and any elements of $\mathbb{N}$. – ShoutOutAndCalculate Oct 30 '18 at 5:51
• It can't be done. You need the axiom of choice to prove that every infinite set is greater than or equal to $\mathbb N$. – bof Oct 30 '18 at 5:53

It is known to be consistent with ZF that an amorphous set exists -- meaning an infinite set that is not the disjoint union of two infinite sets. Such a set would be an infinite set whose cardinality is incomparable with that of $$\mathbb N$$ and therefore be a counterexample to the claim.