# Without Axiom of Choice, Is there anything wrong with my proof that $\aleph_0$ is the smallest cardinality of infinite sets?

I transfer the statement that $\aleph_0$ is the smallest cardinality of infinite sets into the below theorem.

Let $A$ be a set where $|A|<\aleph_0$. Then $A$ is finite.

Then I go on to prove it without appealing to Axiom of Choice. But I read https://math.stackexchange.com/a/517045/368425 and found Andrés E. Caicedo's comment Curious that you did not mention the key use of the axiom of choice....

I don't know what's wrong with my proof! Please shed some lights!

Lemma 1: If $B$ is a subset of $I_n=\{0,1,\cdots,n\}$. Then $B$ is finite. (I presented a proof here)

Lemma 2: If $B$ is a nonempty subset of $\Bbb N$ without a greatest element. Then there exists a bijection $g:B \to \Bbb N$. (I presented a proof here)

$|A|<\aleph_0 \implies$ For any injection $f:A \to \Bbb N$, $f$ is not surjective $\implies$ $f(A) = B \subsetneq \Bbb N$. There are only two possible cases.

1. $B$ is bounded above.

This means $B \subseteq I_n$ for some $n \in \Bbb N$. By Lemma 1, $B$ is finite and consequently $A$ is finite.

1. $B$ is unbounded above.

This means $B$ has no greatest element. By Lemma 2, there exists a bijection $g:B \to \Bbb N$. It follows that $g \circ f:A \to \Bbb N$ is bijective. This contradicts the fact that $|A|<\aleph_0$. Hence $B$ is bounded above.

To sum up the two above cases, $A$ is finite.

• I mean, did you read the remark I made in that answer you linked, about the axiom of choice? – Asaf Karagila Sep 9 '18 at 5:02
• @AsafKaragila did you mean the remark that the mentioned proof in that post must appeal to some form of Axiom of Choice? – Le Anh Dung Sep 9 '18 at 5:13
• Note that the above proves that $\aleph_0$ is a minimal element of the infinite cardinals. There is no smaller. To prove that it is in fact the smallest of the infinite cardinals we need to use some other set theoretical assumptions (e.g. every two cardinals are comparable) which are commonly assumed throughout mathematics nowadays. – Asaf Karagila Sep 9 '18 at 5:15
• Yes, they are, it was asked and asked and asked again. – Asaf Karagila Sep 9 '18 at 11:18
• That is correct. Moreover, countable choice is strictly stronger than "Every infinite set has a countably infinite subset". (This too was discussed before, several times, on the site, by the way.) – Asaf Karagila Sep 9 '18 at 14:00

Your proof is correct, but the statement you are proving is not the same as "$\aleph_0$ is the smallest cardinality of infinite sets". You have proved that there is no cardinality of infinite sets that is smaller than $\aleph_0$. However, there may exist a cardinality of infinite sets that is incomparable with $\aleph_0$. In other words, there could exist a set $A$ such that there does not exist an injection $A\to\mathbb{N}$ and there also does not exist an injection $\mathbb{N}\to A$.
• Thank you for your answer! If I transfer the statement $\aleph_0$ is the smallest cardinality of infinite sets into the theorem If $A$ is infinite, then $\aleph_0 \le |A|$. Is it correct? – Le Anh Dung Sep 9 '18 at 3:57
• Your original statement is almost the contrapositive of that statement, except that $|A|<\aleph_0$ is NOT the negation of $\aleph_0\leq |A|$ since $\aleph_0$ and $|A|$ may be incomparable. – Eric Wofsey Sep 9 '18 at 4:01