Sufficient Conditions for Uncountability
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 Proof Wiki by redesigning it.
To discuss this proof in more detail, feel free to use the talk page.
If you are able to fix this proof, then when you have done so you can remove this instance of {{Improve}} from the code.
If you would welcome a second opinion as to whether your improvement is correct, add an invitation to {{Proofread}} the page (see the proofread template for usage).
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)$
to do
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof.
When this page/section has been completed, {{ProofWanted}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
$\blacksquare$