If $\#(S)<\#(\Bbb N)$, then prove that $S$ is finite, without using the Axiom of Choice.

Question

If we have a set $S$ such that $\#(S)<\#(\Bbb N)$, where $\Bbb N$ is the set of the natural numbers, how would one prove that $S$ must be finite?

Here is a proof using the Axiom of Choice:

Proof: From $\#(S)<\#(\mathbb{N})$, we know that there exists an injection $f:S\to \mathbb{N}$. On the other hand, $S$ cannot be an infinite set: If $S$ is infinite, it contains a copy of $\mathbb{N}$ by the Axiom of choice. Therefore, we have an injection $g:\mathbb{N}\to S$. By the Schröder–Bernstein Theorem, $\#(S)=\#(\mathbb{N})$, which is a contradiction.

Can we prove the theorem without the Axiom of Choice?

Answer 1

By definition of $<$ for cardinalities, there exists an injection $f\colon S\to \Bbb N$. For $n\in\Bbb N$, let $$h(n)=\Big|\big\{\,x\in f(S)\mid x<n\,\big\}\Big|\,.$$ If $h$ is bounded, $h(n)<M$ for all $n$, this shows that $f(s)<M$ for all $s\in S$, whence $f$ can be viewed as map $\to\{0,\ldots, M\}$ and $S$ is finite; on the other hand, if $h$ is not bounded, for $n\in\Bbb N$, let $$m=\min\big\{\,k\in\Bbb N\mid h(j)\ge n\,\big\}\,,$$ observe that then $m\in f(S)$, and define $g(n)=f^{-1}(m)$. This gives us an injection (in fact, bijection) $\Bbb N\to S$.

Answer 2

I think you can prove this by assuming that a set is infinite, you can clearly select an element and by definition of infinity you can select another element ad infinitum and you can enumerate the element that you selected at step as n.

Answer 3

Assuming $$\# (S)<\#(\Bbb N)$$ we do not need choice, we just need to take the smallest element after the previous one, if it is finite it will end, if it is not finite than it will create bijective from $S$ to $\Bbb N$, and thus $\# (S)=\# (\Bbb N)$, this is contradiction thus $\# (S)<\#(\Bbb N)$ implies $S$ is finite.

But assuming $$\# (S)\not\ge\#(\Bbb N)$$is not enough to show $S$ is finite without choice! There exists infinite finite-dedekind set which is not comparable to $\Bbb N$! But if you assume the axiom us choice it is provable that those sets do not exists.