7. Счетные множества
Определение 7.1
Множество А называется счётным, если оно эквивалентно множеству натуральных чисел \(N\). То есть можно построить биекцию \(f: A \Rightarrow N\)
Определение 7.2
Множество называется не более чем счётное, если оно является конечным или счётным
Классическим примером для счётного множества может служить множество целых чисел \(Z\). Чтобы проверить счётное ли данное множество, необходимо привести в соответствие элементы множества целых чисел и множества натуральных чисел. Таким образом, чтобы показать счётность множества, надо выписать его элементы в последовательность, каждый по одному разу и ничего не пропустив
Теорема 7.1
Любое бесконечное множество содержит счётное подмножество
Доказательство
Чтобы доказать данную теорему, необходимо выделить данное подмножество. Пусть \(A\) – бесконечное множество, \(B\) – счётное подмножество
\(a_1 \in A\). «Уберём» его из данного множества. А будет также бесконечным. Тогда можно также выделить \(a_2 \in A \setminus \{a_1\}\) , потом \(a_3 \in A \setminus \{a_1;a_2\}\) и так далее. Множество \(A\) будет бесконечным в любом случае, получается, что данный процесс будет идти бесконечно. С помощью этих элементов можем выделить подмножество \(B\), которое и будет счётным
Теорема 7.2
Любое подмножество счётного множества конечное или счётное
Доказательство
Дальнейшие доказательства будут довольны тривиальные, так как они направлены на один вид доказательства: перебор элементов и их упорядоченность.
Пусть \(A\) – подмножество счётного множества. Упорядочим элементы этого подмножества. Если мы исчерпаем его элементы, то данное подмножество конечное, если будет ситуация из прошлой теоремы, то подмножество – счётное
Теорема 7.3
Конечное объединение счетных множеств – счётное
Доказательство
Пусть \(A = \{a_1;a_2;...;a_n;...\}, B = \{b_1;b_2;...;b_n;...\}\). При объединении мы сможем упорядочить элементы, к примеру, таким образом: \(A \cup B = \{a_1;b_1;a_2;b_2;...;a_n;b_n;...\}\). Получаем, что конечное объединение – счётное
Теорема 7.4
Объединение не более чем счётного множества не более чем счётных множеств является не более чем счётным множеством
Доказательство
Для полного доказательства необходимо разобрать 3 случая:
- Пусть \(А\) и \(В\) – счётные множества. Доказательство уже было доказано выше;
- Пусть \(А\) – счётное множество, \(В\) – конечное. При упорядочении элементов мы получим, что данное множество будет либо счётным (если не будет конечного элемента), либо конечным (закончится на элементе конечного множества;
- Пусть \(А\) и \(В\) – конечные множества. Исходя из пункта 2 получим, что при упорядочении мы получим конечное множество, которое и является не более чем счётным.
Отсюда следует, что теорема верна