Номер §4, страница 337 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Дружим с компьютером - номер §4, страница 337.

Условие.

К § 4 «Равномощные множества. Счётные множества»

Какие задачи этого параграфа легко решить, пользуясь понятием о двоичной системе счисления?

Решение.

Понятие о двоичной системе счисления позволяет элегантно решать задачи, связанные с установлением биекций (взаимно-однозначных соответствий) между различными множествами, что является ключевым инструментом для сравнения их мощностей. В частности, двоичная система удобна для работы с подмножествами и действительными числами. Легко решить можно следующие задачи:

Доказательство того, что множество всех подмножеств счетного множества (например, $ \mathbb{N} $) является несчетным

Решение:

Рассмотрим множество натуральных чисел $ \mathbb{N} = \{1, 2, 3, ...\} $. Его мощность счетна. Требуется доказать, что его булеан (множество всех подмножеств), обозначаемый как $ P(\mathbb{N}) $ или $ 2^{\mathbb{N}} $, является несчетным.

Поставим в соответствие каждому подмножеству $ A \subseteq \mathbb{N} $ бесконечную последовательность из нулей и единиц. Это делается с помощью характеристической функции $ \chi_A: \mathbb{N} \to \{0, 1\} $, которая определяется так:

$ \chi_A(n) = \begin{cases} 1, & \text{если } n \in A \\ 0, & \text{если } n \notin A \end{cases} $

Таким образом, каждому подмножеству $ A $ соответствует уникальная бесконечная двоичная последовательность $ (\chi_A(1), \chi_A(2), \chi_A(3), ...) $. Например:

• Пустому множеству $ \emptyset $ соответствует последовательность $ (0, 0, 0, ...) $.
• Множеству $ \mathbb{N} $ соответствует последовательность $ (1, 1, 1, ...) $.
• Множеству четных чисел $ \{2, 4, 6, ...\} $ соответствует последовательность $ (0, 1, 0, 1, 0, 1, ...) $.

Это соответствие является биекцией между множеством $ P(\mathbb{N}) $ и множеством всех бесконечных двоичных последовательностей.

Докажем, что множество всех бесконечных двоичных последовательностей несчетно, используя диагональный метод Кантора. Предположим, что оно счетно. Тогда все такие последовательности можно пронумеровать и выписать в список:

$ s_1 = (b_{11}, b_{12}, b_{13}, ...) $

$ s_2 = (b_{21}, b_{22}, b_{23}, ...) $

$ s_3 = (b_{31}, b_{32}, b_{33}, ...) $

$ ... $

где $ b_{ij} \in \{0, 1\} $.

Теперь построим новую последовательность $ s' = (b'_1, b'_2, b'_3, ...) $, где каждый элемент $ b'_k $ определяется как $ b'_k = 1 - b_{kk} $. То есть, мы берем диагональные элементы $ b_{11}, b_{22}, b_{33}, ... $ и инвертируем их (0 меняем на 1, 1 на 0).

Полученная последовательность $ s' $ не может находиться в нашем списке. Она отличается от $ s_1 $ в первом элементе, от $ s_2 $ — во втором, и в общем, от любой последовательности $ s_k $ — в $ k $-ом элементе. Это противоречит нашему предположению, что список полон. Следовательно, множество всех бесконечных двоичных последовательностей несчетно.

Поскольку между $ P(\mathbb{N}) $ и этим множеством есть биекция, то и $ P(\mathbb{N}) $ также несчетно.

Ответ: Множество всех подмножеств счетного множества несчетно.

Доказательство несчетности множества действительных чисел на отрезке [0, 1]

Решение:

Каждое действительное число $ x \in [0, 1] $ можно представить в виде бесконечной двоичной дроби: $ x = 0.b_1b_2b_3..._2 $, где $ b_i \in \{0, 1\} $.

Например, $ 1/2 = 0.1_2 $, $ 1/4 = 0.01_2 $, $ 3/4 = 0.11_2 $. Некоторые числа имеют два двоичных представления (например, $ 1/2 = 0.1000..._2 = 0.0111..._2 $). Однако множество таких чисел счетно и не влияет на общую мощность множества.

Чтобы доказать несчетность отрезка [0, 1], достаточно показать, что множество всех бесконечных двоичных последовательностей $ (b_1, b_2, b_3, ...) $, которые можно рассматривать как "хвосты" двоичных дробей, несчетно. Как было показано в предыдущей задаче с помощью диагонального метода Кантора, это множество действительно несчетно.

Таким образом, мы устанавливаем соответствие (которое можно сделать биективным) между числами из отрезка [0, 1] и бесконечными двоичными последовательностями. Поскольку множество таких последовательностей несчетно, то и отрезок [0, 1] является несчетным множеством.

Ответ: Множество действительных чисел на отрезке [0, 1] несчетно.

Доказательство счетности множества всех конечных подмножеств счетного множества (например, $ \mathbb{N} $)

Решение:

Пусть $ A_{fin}(\mathbb{N}) $ — это множество всех конечных подмножеств множества натуральных чисел $ \mathbb{N} = \{1, 2, 3, ...\} $. Нам нужно доказать, что это множество счетно.

Воспользуемся двоичной системой счисления. Каждому конечному подмножеству $ S \subseteq \mathbb{N} $ мы можем сопоставить уникальное натуральное число. Определим отображение $ f: A_{fin}(\mathbb{N}) \to \mathbb{N}_0 $ (где $ \mathbb{N}_0 = \{0, 1, 2, ...\} $) следующим образом:

$ f(S) = \sum_{k \in S} 2^{k-1} $

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

• $ f(\emptyset) = 0 $ (сумма по пустому множеству равна 0). Двоичная запись: $ 0_2 $.
• $ f(\{1\}) = 2^{1-1} = 2^0 = 1 $. Двоичная запись: $ 1_2 $.
• $ f(\{3\}) = 2^{3-1} = 2^2 = 4 $. Двоичная запись: $ 100_2 $.
• $ f(\{1, 3\}) = 2^{1-1} + 2^{3-1} = 1 + 4 = 5 $. Двоичная запись: $ 101_2 $.
• $ f(\{2, 4, 5\}) = 2^{2-1} + 2^{4-1} + 2^{5-1} = 2 + 8 + 16 = 26 $. Двоичная запись: $ 11010_2 $.

Это отображение является биекцией. Любое целое неотрицательное число имеет единственное представление в двоичной системе счисления, которое, в свою очередь, однозначно определяет конечное подмножество $ \mathbb{N} $. Например, числу $ 13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0 $ (в двоичной системе $ 1101_2 $) соответствует множество $ \{1, 3, 4\} $.

Поскольку мы установили биекцию между множеством всех конечных подмножеств $ \mathbb{N} $ и счетным множеством неотрицательных целых чисел $ \mathbb{N}_0 $, то множество $ A_{fin}(\mathbb{N}) $ также является счетным.

Ответ: Множество всех конечных подмножеств счетного множества счетно.