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

Question

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

1. Infinite Set has greater or equal cardinality that of N

2. How can I prove that the set of natural numbers $\mathbb N$ is infinite?

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?

Answer 1

This can't be proved without the axiom of choice. Or, more precisely, it cannot be proved in ZF alone.

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.

(You don't need the full axiom of choice, though. The naive pick-a-sequence argument will go through with the axiom of dependent choice, and even the axiom of countable choice is enough, with a slightly more involved argument).