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?

  • 1
    $\begingroup$ How do you define a set to be infinite? $\endgroup$
    – Akira
    Oct 30, 2018 at 5:46
  • $\begingroup$ @LeAnhDung the standard definition from Introduction to set thoery. $\mathbb{N}=\{ x|x\in I $ for every inductive set $ I \}$. $\endgroup$ Oct 30, 2018 at 5:49
  • 1
    $\begingroup$ No, I meant $X$ is infinite $\iff\cdots$ $\endgroup$
    – Akira
    Oct 30, 2018 at 5:50
  • $\begingroup$ @LeAnhDung If $X$ is not finite, then $X$ is infinite, so there is no bijection between $X$ and any elements of $\mathbb{N}$. $\endgroup$ Oct 30, 2018 at 5:51
  • 1
    $\begingroup$ 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$. $\endgroup$
    – bof
    Oct 30, 2018 at 5:53

1 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).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .