Апология математики (сборник статей)

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

Пример 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. Это не слишком страшно, потому что из контекста ясно, какой из двух натуральных рядов имеется в виду. В этом параграфе натуральный ряд начинается с единицы.

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