0
$\begingroup$

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ How do you define a set to be infinite? $\endgroup$ – LE Anh Dung Oct 30 '18 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$ – ShoutOutAndCalculate Oct 30 '18 at 5:49
  • 1
    $\begingroup$ No, I meant $X$ is infinite $\iff\cdots$ $\endgroup$ – LE Anh Dung Oct 30 '18 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$ – ShoutOutAndCalculate Oct 30 '18 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 '18 at 5:53
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.