Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Алгоритмы вокруг нас.doc
Скачиваний:
3
Добавлен:
01.05.2025
Размер:
13 Мб
Скачать
☆

§ 3. Кардинальные числа

Теория множеств позволяет сделать очень интересное обобщение понятия числа. Условимся мощностью конеч­ного множества называть наибольшее натуральное число, которое будет использовано при нумерации его элементов, т. е. при установлении взаимно однозначного соответствия с последовательными числами 1, 2, 3, ..., принадлежащими натуральному ряду. При этом мощности равномощных конечных множеств оказываются равными, что подтверж­дает естественность нового термина.

Множеству всех натуральных чисел поставим в соот­ветствие некоторую мощность, которую будем обозначать символом N. Ее же будем считать мощностью каждого множества, равномощного множеству натуральных чисел (т. е. каждому счетному множеству). Будем, наконец, считать, что множеству положительных действительных чисел, не превосходящих единицы, соответствует некото­рая мощность К, которая является мощностью также каждого континуального множества.

Если каждое множество, являющееся правильной ча­стью множества М, а также само множество М называть подмножествами множества М, можно доказать теорему:

Если М — конечное множество мощности п, то множе­ство всех его подмножеств (считаемых элементами этого нового множества) имеет мощность 2n (имеются в виду только попарно неравные между собой подмножества).

Мы не будем приводить доказательства этой теоремы, подтвердим ее только примером. Пусть множество М со­стоит из элементов а1, а2, а3 и, следовательно, имеет мощ­ность 3. Его подмножествами будут три одноэлементных множества {a1}, {a2}, {а3}, три двухэлементных множества {а1, а2}, {а1, а3}, {a2, а3}, одно трехэлементное множество {а1, а2, а3} и одно пустое множество { }. Их ровно восемь, а это значит, что мощность множества, для которого они являются элементами, равна 23.

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

{{ }, {а1}, {a2, {a3}, {a1. a2}, {a1, а3}, {а2, а3}, {a1, а2, а3}}. По аналогии с мощностями конечных множеств усло­вимся мощность множества всех (не равных между со­бой) подмножеств бесконечного множества обозначать сим­волом 2т, если мощность исходного множества т. До­казано, что K=2N. При этом 2К будет равно .

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

Остается «установить порядок» между мощностями. Делается это так. Полагают, что мощности равиомощных множеств равны. Это условие уже выполнено. Далее, считают, что мощность множества M1 (обозначим ее m1) меньше мощности множества М2 (обозначим ее m2), если M1 равномощно некоторому подмножеству множества М2, причем М2 не равномощно ни одному подмножеству множества M1. Это записывают так:

m1<m2.

Наконец считают, что mt больше тг и пишут т1>тг, если сформулированное выше условие при взаимной за­мене M1 на M2 окажется верным. Итак, теперь каждое множество характеризуется своей мощностью, и любые две мощности находятся в одном из трех перечисленных отношений.

Новая характеристика множества — его мощность — чем-то напоминает число, а для конечных множеств сов­падает с числом. Это позволило ввести термин кардиналь­ное число.

Кардинальным числом (элементов) множества М на­зывается его мощность т. Все натуральные числа содер­жатся среди кардинальных, но существуют кардинальные числа, не являющиеся натуральными. Г. Кантор доказал следующие две теоремы.

Теорема 1. Для любого кардинального числа т справедливо неравенство m<2m.

Теорема 2. Мощность т' подмножества множе­ства, имеющего мощность т, удовлетворяет неравенству т' ≤ т.

Теперь мы достаточно углубились в теорию множеств для того, чтобы суметь описать те «подземные толчки», которые потрясли математику в конце XIX — начале XX в.