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.
- $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.
- $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.
Best Answer
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$.