6
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ What are your thoughts on this question? $\endgroup$ – paulplusx Sep 19 '18 at 8:47
  • 1
    $\begingroup$ If $f\colon A\to B$ is an injection, then this means that there is a set $A'\subseteq B$ such that $f\colon A\to A'$ is a bijection. In particular, this means that if $\#A\leq\#\Bbb N$, then there is a subset $A'$ of $\Bbb N$ such that $\#A=\#A'$. Therefore, it is enough to prove that if $A\subseteq\Bbb N$ then either $A$ is finite, or $\#A=\#\Bbb N$. The standard proof of this fact don't use the axiom of choice at all, since $\Bbb N$ is given with a standard well-ordering which is inherited by all of its subsets. $\endgroup$ – Asaf Karagila♦ Sep 19 '18 at 10:48
  • $\begingroup$ What exactly is "the standard proof of this fact"? $\endgroup$ – user386867 Sep 19 '18 at 15:44
  • $\begingroup$ The standard proof is the one given by Hagen, essentially. If $A\subseteq\Bbb N$ is non-empty, define $g(0)=\min A$ and $g(n+1)=\min\{a\in A\mid a>g(n)\}$ if that set is non-empty, otherwise stop. This is a bijection between $A$ and either $\{0,\ldots,n-1\}$, or $\Bbb N$ itself. $\endgroup$ – Asaf Karagila♦ Sep 20 '18 at 14:57
  • 2
    $\begingroup$ @ArcticChar I think the "confusing proof" should be included. It is the natural proof; the fact that it doesn't use AoC is, I guess, the point of Asaf's comment (and is not obvious to those who do not think about AoC much). Also, without the additional proof the question is low quality and should be closed. $\endgroup$ – user1729 Jul 29 at 10:34
14
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't understand the distinction between $\#(s)<\#(N)$ and $\#(s) \ngeq \#(N)$ and why this makes a difference between requiring the axiom of choice or not. Could you explain this some more? $\endgroup$ – user386867 Sep 19 '18 at 15:40
  • $\begingroup$ @A.Smith $\# A<\# B$ if and only if there exists injective function from $A$ to $B$ but there is no bijective function from $A$ to $B$. $\# A\ngeq\# B$ if and only if there is no injective nor bijective from $B$ to $A$, apparently if we do not assume choice the two are not equivalent but assuming choice they are equivalent $\endgroup$ – ℋolo Sep 19 '18 at 16:07
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 8
    $\begingroup$ That is exactly the proof that requires the axiom of choice. $\endgroup$ – Asaf Karagila♦ Sep 19 '18 at 5:39
  • 1
    $\begingroup$ "Selecting" without an explicit formula for how the selection is made means using the Axiom of Choice. The sentence $\forall n\in \Bbb N\; \forall \{x_j: n>j\in \Bbb N\}\; \exists x_n\in S$ \ $\{x_j:n>j\in \Bbb N\}\;$ is not the same as $\exists f:\Bbb N\to S\; \forall n\in \Bbb N\; (f(n)\not \in \{f(j):n>j\}).$ $\endgroup$ – DanielWainfleet Sep 19 '18 at 9:05

Your Answer

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