Sufficient Conditions for Uncountability
Theorem
Let $X$ be a set.
The following are equivalent:
- $(1): \quad X$ contains an uncountable subset
- $(2): \quad X$ is uncountable
- $(3): \quad $ Every sequence of distinct points $\sequence {x_n}_{n \mathop \in \N}$ in $X$ omits at least one $x \in X$
- $(4): \quad $ There is no surjection $\N \twoheadrightarrow X$
- $(5): \quad X$ is infinite and there is no bijection $X \leftrightarrow \N$
Assuming the Continuum Hypothesis holds, we also have the equivalent uncountability condition:
- $(6): \quad $There exist extended real numbers $a < b$ and a surjection $X \to \closedint a b$
Proof
Recall that $X$ is uncountable if there is no injection $X \hookrightarrow \N$.
$(1)$ implies $(2)$
Suppose there exists an injection $f: X \hookrightarrow \N$.
Let $Y \subseteq X$ be uncountable.
Then $\hat f: Y \to \N$ defined as:
- $\hat f = \set {\map f x: x \in Y}$
is an injection $Y \hookrightarrow N$, which is a contradiction.
$\Box$
$(2)$ implies $(3)$
Suppose $\sequence {x_n}_{n \mathop \in \N}$ is a sequence of distinct points such that every $x \in X$ equals $x_n$ for some $n$.
Since the $x_n$ are distinct, this $n$ is unique.
Let $f: X \to \N$ be defined by $\map f x = n$, where $n$ is the unique natural number such that $x_n = x$.
Then $f$ is injective because $n = m$ implies that $x_n = x_m$.
So there is an injection $X \hookrightarrow \N$, a contradiction.
$\Box$
$(3)$ implies $(4)$
Suppose there exists a surjection $f: \N \to X$.
Therefore every $x \in X$ is $\map f n$ for some $n \in \N$.
Define $g: X \to \N$ by $\map g x = \inf \set {n \in \N : \map f n = x}$.
Then if $\map g {x_1} = \map g {x_2} = n$, we have $\map f n = x_1$ and $\map f n = x_2$.
So by the definition of a mapping, $x_1 = x_2$.
Therefore $g$ is an injection $X \to \N$, a contradiction.
$\Box$
$(4)$ implies $(5)$
Since there exists no surjection $\N \to X$, and a bijection $\N \to X$ must be surjective, there is no such mapping.
$\Box$
$(5)$ implies $(1)$
Suppose $f: X \hookrightarrow \N$ is an injection.
We essentially relabel the image of $f$ to obtain a bijection, and thus a contradiction.
Construct a map $g: X \to \N$ as follows.
Let $S_1 = \Img f$ and:
- $x_1 = \map {f^{-1} } {\inf \set {n \in \N : n \in S_1} }$
and define $\map f x = 1$.
Note that $x$ is a singleton because $f$ is injective.
Given $S_n \subseteq \Img f$, let:
- $x_n = \map {f^{-1} } {\inf \set {n \in \N : n \in S_n} }$
and set $S_{n + 1} = S_n \setminus x_n$.
The mapping:
- $n \stackrel {f^{-1} } \longrightarrow x_k \stackrel g \longrightarrow k$
defines a bijection from $\Img f$ to $\N$, so $g$ is injective because $f$ is.
Furthermore $g$ assigns each $n \in \N$ to some $x \in X$ (because $X$ is infinite) so $g$ is surjective.
Thus $g$ is a bijection, a contradiction.
$\Box$
$(6)$ implies $(1)$
$\blacksquare$