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 $\left\langle{x_n}\right\rangle_{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 \left[{a \,.\,.\, b}\right]$

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 = \left\{{f\left(x\right), x \in Y}\right\}$

is an injection $Y \hookrightarrow N$, which is a contradiction.

$\Box$

$(2)$ implies $(3)$

Suppose $\left\langle{x_n}\right\rangle_{n \mathop \in \N}$ is a sequence 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 $f \left({x}\right) = 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 $f \left({n}\right)$ for some $n \in \N$.

Define $g: X \to \N$ by $g \left({x}\right) = \inf \left\{ {n \in \N : f \left({n}\right) = x}\right\}$.

Then if $g \left({x_1}\right) = g \left({x_2}\right) = n$, we have $f \left({n}\right) = x_1$ and $f \left({n}\right) = 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 = \operatorname {Im} \left({f}\right)$ and:

$x_1 = f^{-1} \left({\inf \left\{{n \in \N : n \in S_1}\right\} }\right)$

and define $f \left({x}\right) = 1$.

Note that $x$ is a singleton because $f$ is injective.

Given $S_n \subseteq \operatorname {Im} \left({f}\right)$, let:

$x_n = f^{-1} \left({\inf \left\{{n \in \N : n \in S_n}\right\} }\right)$

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 $\operatorname {Im} \left({f}\right)$ 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$