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

  • 7 мин чтения
  • Послушать — 5 мин
  • 18 карточек

Алгебра, 8 класс · Л. Г. Петерсон, Н. Х. Агаханов, А. Ю. Петрович, О. К. Подлипский, М. В. Рогатова, Б. В. Трушин

Мысль о том, что бесконечные множества бывают «разных размеров» и их можно сравнивать, впервые высказал немецкий математик Георг Кантор во второй половине XIX века. Сначала её встретили враждебно, а теперь Кантора считают основателем теории множеств.

Определение. Множество называется счётным, если между ним и множеством N натуральных чисел можно установить взаимно однозначное соответствие, — иначе говоря, если оно бесконечно и все его элементы можно занумеровать: a₁, a₂, …, a_n, … Счётны, например, множество чётных чисел и множество Z.

Теорема 1. Любое бесконечное множество содержит счётное подмножество. (Выбираем элемент a₁, из оставшихся — a₂, и так далее.)

Теорема 2. Любое бесконечное подмножество B счётного множества A = {a₁, a₂, …} счётно: идём по номерам 1, 2, 3, … и нумеруем по порядку те a_n, которые лежат в B, — каждый элемент B получит свой номер.

Теорема 3. Объединение счётного и конечного, а также двух счётных множеств счётно: в первом случае сначала нумеруем конечное множество, потом счётное; во втором — нумеруем «через один»: a₁, b₁, a₂, b₂, … (общие элементы — один раз).

Теорема 4. Множество Q счётно. Положительные дроби p/q запишем в таблицу: в p-й строке и q-м столбце — p/q. Обходим таблицу по диагоналям p + q = 2, 3, 4, … и пропускаем уже встречавшиеся значения: 1; 1/2; 2; 1/3; 3; 1/4; 2/3; 3/2; 4; … — все положительные рациональные числа получили номера. Отрицательные нумеруются так же (r → -r), а Q = Q₊ ∪ Q₋ ∪ {0} счётно по теореме 3.

Несчётность. Бесконечное множество, которое не является счётным, называют несчётным; по теореме 1 оно «мощнее» N.

Теорема 5. Множество R несчётно. Достаточно доказать, что несчётен промежуток [0; 1) (если бы R было счётным, то и его бесконечная часть [0; 1) была бы счётной). От противного: пусть все числа [0; 1) занумерованы: a₁ = 0,a₁₁a₁₂a₁₃…, a₂ = 0,a₂₁a₂₂a₂₃…, … Составим число b = 0,b₁b₂b₃…, у которого k-я цифра отличается от k-й цифры числа a_k (и не равна 0 и 9). Тогда b отличается от каждого a_k — противоречие («диагональный метод» Кантора).

Следствия. Интервал (0; 1) несчётен (иначе, добавив 0, получили бы счётное [0; 1)). Любой интервал (a; b) эквивалентен (0; 1): x = a + t(b - a), t ∈ (0; 1), — значит, тоже несчётен. Множество иррациональных чисел несчётно: иначе R было бы объединением двух счётных множеств.

Зачем это

1 / 18

Разные бесконечности

Бесконечные множества бывают «разных размеров», и их можно сравнивать.

Эту мысль впервые высказал немецкий математик Георг Кантор во второй половине XIX века. Сначала её встретили враждебно, а теперь Кантора считают основателем теории множеств.

Определение

2 / 18

Счётное множество

Определение. Множество называется счётным, если между ним и N можно установить взаимно однозначное соответствие.

Иначе говоря, оно бесконечно и его элементы можно занумеровать: a₁, a₂, …, a_n, …

Счётны чётные числа (2, 4, 6, …) и Z (0, 1, -1, 2, -2, …).

Проверь себя

3 / 18

Какое счётно?

Вспомни определение счётного множества.

Какое множество счётно?

{1; 2; …; 100}кратные 5∅
Ответ и объяснение

Кратные 5 нумеруются так: a_n = 5n, то есть 5, 10, 15, … — каждое получает свой номер.

Свойство

4 / 18

Теорема 1

Любое бесконечное множество содержит счётное подмножество.

Выбираем элемент a₁, из оставшихся — a₂, из оставшихся — a₃, и так далее.

Множество бесконечно, поэтому элементы не кончатся.

Свойство

5 / 18

Теорема 2

Любое бесконечное подмножество B счётного множества A = {a₁, a₂, …} счётно.

Идём по номерам 1, 2, 3, … и нумеруем по порядку те a_n, которые лежат в B.

Квадраты в N: 1, 4, 9, 16, … получают номера 1, 2, 3, 4, …

Свойство

6 / 18

Теорема 3

Объединение счётного и конечного множеств, а также двух счётных множеств счётно.

Счётное и конечное: сначала нумеруем конечное, потом счётное.

Два счётных: нумеруем «через один» a₁, b₁, a₂, b₂, … (общие элементы — один раз).

Проверь себя

7 / 18

Как занумеровать?

A = {a₁, a₂, …} и B = {b₁, b₂, …} — счётные, общих элементов нет.

Как занумеровать A ∪ B?

сначала все a, потом все ba₁, b₁, a₂, b₂, …
Ответ и объяснение

Через один: a_n получает номер 2n - 1, а b_n — номер 2n; номер есть у каждого.

Наглядно

8 / 18

Таблица дробей

Теорема 4: Q счётно. Дробь p/q стоит в p-й строке и q-м столбце; обходим диагонали p + q = 2, 3, 4, …

Таблица дробей p/q: строки p от 1 до 4, столбцы q от 1 до 4. Клетки одной диагонали p + q одного цвета. Номера по диагоналям: 1 — 1/1, 2 — 1/2, 3 — 2/1, 4 — 1/3, 5 — 3/1, 6 — 1/4, 7 — 2/3, 8 — 3/2, 9 — 4/1; 2/2, 2/4, 3/3, 4/2, 4/4 зачёркнуты.
Таблица дробей p/q: строки p от 1 до 4, столбцы q от 1 до 4. Клетки одной диагонали p + q одного цвета. Номера по диагоналям: 1 — 1/1, 2 — 1/2, 3 — 2/1, 4 — 1/3, 5 — 3/1, 6 — 1/4, 7 — 2/3, 8 — 3/2, 9 — 4/1; 2/2, 2/4, 3/3, 4/2, 4/4 зачёркнуты.

Разбор

9 / 18

Почему Q счётно

Докажем, что множество Q счётно.

  1. Диагонали

    1; 1/2; 2; 1/3; 3; 1/4; 2/3; 3/2; 4; … — номер у каждого положительного числа.

  2. Отрицательные

    Отрицательные нумеруются так же: r → -r.

  3. Ответ

    Q = Q₊ ∪ Q₋ ∪ {0} — счётно по теореме 3.

Проверь себя

10 / 18

Номер дроби

Порядок: 1; 1/2; 2; 1/3; 3; 1/4; …

Какой номер у дроби 2/3?

786
Ответ и объяснение

После 1/4 (номер 6) на диагонали p + q = 5 идёт 2/3 — номер 7.

Определение

11 / 18

Несчётное множество

Бесконечное множество, которое не является счётным, называют несчётным.

По теореме 1 в нём есть счётное подмножество, но всё оно с N не эквивалентно: несчётное множество «мощнее» N.

Формула

12 / 18

Теорема 5

R несчётно

Достаточно доказать, что несчётен промежуток [0; 1): если бы R было счётным, то его бесконечная часть [0; 1) тоже была бы счётной по теореме 2.

Наглядно

13 / 18

Диагональ Кантора

Пусть числа из [0; 1) занумерованы. Цифры на диагонали обведены, b берёт на каждом месте другую цифру.

Список чисел: a1 = 0,5217…, a2 = 0,3380…, a3 = 0,7419…, a4 = 0,2064… Обведены цифры на диагонали: 5, 3, 1, 4. Ниже число b = 0,6425…: его k-я цифра на 1 больше k-й цифры числа a_k.
Список чисел: a1 = 0,5217…, a2 = 0,3380…, a3 = 0,7419…, a4 = 0,2064… Обведены цифры на диагонали: 5, 3, 1, 4. Ниже число b = 0,6425…: его k-я цифра на 1 больше k-й цифры числа a_k.

Разбор

14 / 18

Диагональный метод

Докажем от противного, что [0; 1) несчётно.

Пусть все числа занумерованы: a₁ = 0,a₁₁a₁₂a₁₃…, a₂ = 0,a₂₁a₂₂a₂₃…, …

  1. Число

    Строим b = 0,b₁b₂b₃…: цифра b_k не равна a_kk, и b_k ≠ 0, b_k ≠ 9.

  2. Сравнение

    b отличается от каждого a_k k-й цифрой, значит, b нет в списке.

  3. Ответ

    Но b ∈ [0; 1) — противоречие. Значит, [0; 1) и R несчётны.

Частая ошибка

15 / 18

Почему не 0 и не 9

Цифры 0 и 9 в b не берут: у некоторых чисел две записи.

0,0999… = 0,0(9): 100x - 10x = 9,(9) - 0,(9), 90x = 9, x = 9/90, x = 0,1.

Число b с девятками в периоде могло бы совпасть с числом списка, записанным иначе.

Правило

16 / 18

Следствия

Интервал (0; 1) несчётен: иначе, добавив 0, получили бы счётное [0; 1).

Любой (a; b) эквивалентен (0; 1): x = a + t(b - a), t ∈ (0; 1) — тоже несчётен.

Иррациональных чисел несчётно много: иначе R было бы объединением двух счётных множеств.

Проверь себя

17 / 18

Из (0; 1) в (2; 6)

x = a + t(b - a), (a; b) = (2; 6).

Какое x соответствует t = 1/4?

32,251
Ответ и объяснение

x = 2 + 1/4 · (6 - 2) = 2 + 1 = 3.

Главное

18 / 18

Главное

  • Счётное: бесконечное, элементы можно занумеровать a₁, a₂, … (чётные, Z, Q).
  • Подмножество счётного и объединение двух счётных — счётны.
  • R, любой интервал, иррациональные числа — несчётны.
  • Диагональный метод: строим число, которого нет в списке.

Проверь себя: тест по теме

Несколько заданий по этой теме из того же учебника. Каждый ответ проверяется сразу, а начать можно без регистрации.

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест