§ 4. Конечные и счетные множества

Множество, равномощное с отрезком натурального ряда (т. е. с множеством натуральных чисел, не превосходящих некоторого числа называется конечным. Пустое множество также называется конечным.

Проще говоря, множество называется конечным, если его элементы можно занумеровать натуральными числами от 1 до так, чтобы различные элементы имели различные номера и чтобы все номера от 1 до были использованы. В соответствии с этим элементы конечного множества можно обозначить через

(см. скан)

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

Основная теорема о конечных множества х гласит:

Каждое конечное множество не может быть равномощно с каким-либо собственным объемлющим множеством.

Доказательство. Пусть, вопреки утверждению теоремы, существует некоторое отображение конечного множества А на его собственное надмножество В. Пусть элементы множества А обозначены через а их образы — через Среди последних содержатся все элементы кроме того, еще по крайней мере один элемент, который мы обозначим через

Для противоречие очевидно: единственный элемент не может иметь два различных образа

Невозможность существования отображения с указанными выше свойствами будем считать доказанной для ; докажем ее теперь для

Можно считать, что потому что если это не так, т. е.

то имеет другой прообраз

и вместо отображения можно построить другое, сопоставляющее элементу элемент элементу а; элемент , а в остальном совпадающее с

Подмножество отображается функцией на некоторое множество которое получается из отбрасыванием элемента

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

Из этой теоремы прежде всего следует, что множество никогда не может быть равномощно с двумя различными отрезками натурального ряда, потому что в противном случае эти отрезки были бы равномощны и при этом обязательно один из них содержался бы в другом. Таким образом, любое конечное множество А равномощно с одним и только одним отрезком натурального ряда. Однозначно определяемое таким способом число называется числом элементов множества оно может служить мерой мощности в этом случае.

Во-вторых, из теоремы следует, что произвольный отрезок натурального ряда неравномощен со всем натуральным рядом. Таким образом, ряд натуральных чисел бесконечен. Множество, равномощное с множеством натуральных чисел, называется счетно бесконечным. Элементы счетно бесконечного множества могут быть перенумерованы так, что любое натуральное число появится в качестве номера ровно один раз.

Конечные и счетно бесконечные множества объединяются названием счетные множества.

(см. скан)

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

Построим последовательность чисел

Она также должна иметь некоторый номер, скажем, номер Тогда

в частности,

получили противоречие.

(см. скан)

Объединение счетного множества счетных множеств снова является счетным.

Доказательство. Обозначим данные множества через а элементы множества через

Существует лишь конечное число элементов для которых ; аналогично, существует лишь конечное число элементов для которых Перенумеруем сначала все элементы, для которых (например, по возрастающим значениям затем (с помощью последующих чисел) — элементы, для которых и т. д. При этом каждый элемент получит некоторый номер и различные элементы будут иметь различные номера. Отсюда следует утверждение.