Sufficient Conditions for Uncountability

Although this article appears correct, it's inelegant. There has to be a better way of doing it. In particular: Explicit statements as to what is assumed and what is to be proved at each stage would make it easy to follow. Exactly which statements are contradicted also need to be pointed out. Also, exactly what is a set and what is an element of a set for arguments to the various defined mappings need to be clarified. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by redesigning it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Improve}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

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

This theorem requires a proof. In particular: to do You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

$\blacksquare$