Set of Pairwise Disjoint Intervals is Countable

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $X$ be a subset of $\mathcal P \left({\R}\right)$ such that:

$(1): \quad X$ is pairwise disjoint:
$\forall A,B \in X: A \ne B \implies A \cap B = \varnothing$.
$(2): \quad$ every element of $X$ contains an open interval:
$\forall A \in X: \exists x, y \in \R: x < y \land \left({x \,.\,.\, y}\right) \subseteq A$.


Then $X$ is countable.


Proof

By Between two Real Numbers exists Rational Number:

$\forall A \in X: \exists x, y \in \R, q \in \Q: x < y \land q \in \left({x \,.\,.\, y}\right) \subseteq A$

By the Axiom of Choice define a mapping $f: X \to \Q$:

$\forall A \in X: f \left({A}\right) \in A$


First it needs to be shown that $f$ is an injection by definition.

Let $A, B \in X$ such that:

$f \left({A}\right) = f \left({B}\right)$

By definition of $f$:

$f \left({A}\right) \in A$ and $f \left({B}\right) \in B$

By definition of intersection:

$f \left({A}\right) \in A \cap B$

Then by definition of empty set:

$A \cap B \ne \varnothing$

Thus by definition of pairwise disjoint:

$A = B$

Hence $f$ is an injection.


By Set is Subset of Itself, $X$ is a subset of $X$.

Thus by Cardinality of Image of Injection:

$\left\vert{X}\right\vert = \left\vert{f^\to \left({X}\right)}\right\vert$

By definition of image:

$f^\to \left({X}\right) \subseteq \Q$

By Rational Numbers are Countably Infinite:

$\Q$ is countable.

Hence by Subset of Countable Set is Countable:

$f^\to \left({X}\right)$ is countable.

Thus by Set is Countable if Cardinality equals Cardinality of Countable Set the result:

$X$ is countable.

$\blacksquare$


Sources