class="cite">

Для доказательства полезно привлечь так называемые биномиальные коэффициенты.

Биномиальные коэффициенты – это коэффициенты разложения бинома (1 + x)n по возрастающим степеням x:

Из выписанной формулы видно, как они обозначаются. Если в этой формуле положить x = –1, то получим:

Только что полученная формула очень похожа на равенство, которое требовалось доказать. И это не случайно. Дело в том, что биномиальный коэффициент

и количество подмножеств  – это одно и то же число.

Пример 42. Доказать равенство

Мы наметим лишь план доказательства. Сначала равенство проверяется для случаев k = 0 и k = n. Затем доказывается равенство, аналогичное равенству из примера 40:

Доказать это равенство чрезвычайно просто. Надо рассмотреть два способа записи разложения степени бинома (1 + x)n+1 по возрастающим степеням x. Первый способ – стандартный, с использованием коэффициентов

Второй способ таков: возводим (1 + x) в степень n, располагаем по степеням x с использованием коэффициентов

а затем это разложение умножаем на (1 + x) и развёртываем в многочлен. Если теперь приравнять коэффициенты при одинаковых степенях переменной, то получим равенство (****). Далее, для получения равенства (***) рассуждаем по индукции.

Этому рассуждению можно придать легко запоминающуюся форму. Рассмотрим так называемый треугольник Паскаля:

По краям стоят единицы, а каждое другое число равно сумме двух его «соседей» из предыдущей строки. Таблица неограниченно продолжается вниз. Занумеруем строки, считая верхнюю строку (из одной единицы) нулевой. Таким образом, первая строка – это 11, вторая – 121 и т. д. Аналогично нумеруем числа в каждой строке: самая левая единица получает номер ноль, за ней следует число номер один и т. д. Например, третье число в шестой строке – это 20.

Наше доказательство равенства

можно теперь сформулировать так: числа равны потому, что каждое из них есть k-е число в n-й строке треугольника Паскаля.

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

Прежде всего не станем уподобляться свифтовским остроконечникам и тупоконечникам, готовым воевать с теми, кто при поедании яиц разбивает их не с того конца. Признаем, что ноль можно считать, а можно и не считать натуральным числом. Потому что на самом деле есть два понятия натурального числа: количественное, возникающее при исследовании количества элементов в множестве, и считательное, возникающее при пересчёте элементов этого множества, при условии, что таковые существуют[141]. Из сказанного ясно, что наименьшее количественное натуральное число есть ноль; это количество элементов в пустом множестве. Наименьшее считательное натуральное число есть единица, потому что с неё начинается любой пересчёт. Сообразно этому есть два натуральных ряда – количественный, начинающийся с ноля, и считательный, начинающийся с единицы. Между ними нетрудно установить взаимно однозначное соответствие:

К сожалению, оба натуральных ряда претендуют на обозначение N. Это не слишком страшно, потому что из контекста ясно, какой из двух натуральных рядов имеется в виду. В этом параграфе натуральный ряд начинается с единицы.

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

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

Позволительно дать и такое определение счётного множества:

множество называется счётным, если его можно пересчитать, т. е. назвать какой-то его элемент первым; какой-то элемент, отличный от первого, – вторым; какой-то, отличный от первых двух, – третьим и т. д., причём ни один элемент множества не должен быть пропущен при пересчёте.

Как только какое-либо бесконечное множество удалось расположить в последовательность отличных друг от друга элементов, так сразу возникает его взаимно однозначный пересчёт: член последовательности, стоящий на первом месте, и только он, объявляется первым; член, стоящий на втором месте, и только он, – вторым и т. д. Возьмём, к примеру, множество всех слов, составленных из букв a и b, и расположим его в последовательность:

A, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …, baaba, baabb, ….

Правило расположения слов в последовательности мы выбрали таким (а могли бы выбрать и другим): группируем слова по длине, а в пределах группы располагаем их в алфавитном порядке. Раз множество всех слов в двухбуквенном алфавите удалось расположить в последовательность различающихся элементов, значит, оно счётно. Аналогичным образом можно расположить в последовательность различающихся элементов и множество слов в любом другом алфавите. Поэтому имеет место следующий фундаментальный факт: каков бы ни был алфавит, множество всех слов в этом алфавите счётно.

Пример 42. Доказать, что объединение счётного множества A с конечным множеством B является счётным множеством.

Пусть A = {a1, a2, a3, …, an, …} и B = {b1, b2, b3, …, bn}. Тогда их объединение A ∪ B можно расположить в последовательность {b1, b2, b3, …, bn, a1, a2, a3, … an, …}. Элемент a1 получит в этой последовательности номер (n + 1). Следовательно, объединение счётного и конечного множеств счётно.

Пример 43. Доказать, что объединение счётного множества A со счётным множеством B является счётным множеством.

Пусть A = {a1, a2, a3, …, an, …} и B = {b1, b2, b3, …, bn, …}. Тогда их объединение A ∪ B можно расположить в последовательность {a1, b1, a2, b2, a3, b3, …, an,