3.7. Счётные и несчётные множества

Определение 3.20. Множества $A$ и $B$ называются эквивалентными (равномощными), если $\exists f\colon A \to B$ — биекция. Обозначение: $A \sim B$.

Определение 3.21. Множество называется счётным, если оно эквивалентно $\mathbb {N}$.

Замечание. Множество $A$ счётно, если оно бесконечно и его элементы можно занумеровать. Действительно, $\forall n \in \mathbb {N}\ \exists ! a \in A\colon a = f(n)$. Обозначим его через $a_ n$. $\forall a \in A\ \exists ! n \in \mathbb {N}\colon a = a_ n$, тогда $A = \{ a_1, a_2, \ldots \} , a_ i \not= a_ j$ при $i \not= j$.

Определение 3.22. Множество называется не более чем счётным, если оно конечно или счётно.

Теорема 3.17 (Кантора). Не более чем счётное объединение не более чем счётных множеств не более чем счётно.

$\blacktriangle $ Занумеруем все множества последовательными натуральными числами, пусть $E_ k$ — множество, соответствующее номеру $k$, где $k$ пробегает либо конечное множество $\{ 1, \ldots , K\} $, либо $\mathbb {N}$. Занумеруем все элементы множества $E_ k, E_ k = \{ e_ m^ k\} $, где номер $m$ пробегает либо конечное множество $\{ 1, \ldots , M_ k\} $, либо $\mathbb {N}$. Запишем элементы $e_ m^ k$ в таблицу:

$E_1 = \{ e_1^1, e_2^1, e_3^1, e_4^1,\ldots \} , $

$ E_2 = \{ e_1^2, e_2^2, e_3^2, e_4^2,\ldots \} , $

$ E_3 = \{ e_1^3, e_2^3, e_3^3, e_4^3,\ldots \} , $

$ \ldots \ldots \ldots \ldots \ldots \ldots \ldots $

Теперь будем последовательно нумеровать элементы этой таблицы следующим образом: $e_1^1,\ \ e_1^2, e_2^1,\ \ e_1^3, e_2^2, e_3^1,\ \ \ldots $, пропуская пустые места и те элементы, которые ранее были занумерованы. В результате получим биекцию между $\bigcup \limits _ k E_ k$ и либо $\mathbb {N}$, либо конечным множеством. $\blacksquare $

Следствие 1. $\mathbb {Z}$ счётно.

$\blacktriangle $ $\mathbb {Z}= \mathbb {N}\cup \{ 0\} \cup (-\mathbb {N})$. $\blacksquare $

Следствие 2. $\mathbb {Q}$ счётно.

$\blacktriangle $ $\mathbb {Q}= \bigcup \limits _{q \in \mathbb {N}} E_ q,$ где $E_ q = \left\{ \frac{p}{q}\colon p \in \mathbb {Z}\right\} \sim \mathbb {Z}\sim \mathbb {N}$. $\blacksquare $

Определение 3.23. Бесконечное множество, не являющееся счётным, называется несчётным.

Теорема 3.18 (Кантор). Отрезок $[a, b]$ несчётен.

$\blacktriangle $ Предположим обратное. Пусть $[a, b] = \{ x_1, x_2, \ldots \} $. Поделим $[a, b]$ на три равных отрезка и обозначим через $[a_1, b_1]$ тот из них, который не содержит $x_1$. Пусть уже построен отрезок $[a_ n, b_ n] \not\ni x_ n$. Поделим $[a_ n, b_ n]$ на три равных отрезка и обозначим через $[a_{n+1}, b_{n+1}]$ тот из них, который не содержит $x_{n+1}$. Так будет построена последовательность вложенных отрезков $\{ [a_ n, b_ n]\} _{n=1}^\infty $. По теореме Кантора о вложенных отрезках $\exists c \in \bigcap \limits _{n=1}^{\smash {\infty }} [a_ n, b_ n] \Rightarrow \forall n \in \mathbb {N}\colon c \in [a_ n, b_ n] \Rightarrow $ $\forall n \in \mathbb {N}\colon c \not= x_ n$. Итак, $c \in [a_1, b_1] \subset [a, b], \forall n \in \mathbb {N}\colon c \not= x_ n$. !!! $\blacksquare $