Лекция №3

1.5. Сравнение множеств. Счетные множества.Мощность множеств

Для сравнения бесконечных множеств и характеристики степени насыщенности бесконечных множеств элементами используются понятия эквивалентности и мощности множеств.

Определение 1. Два множества называются эквивалентными или равномощными, если между их элементами можно установить взаимно однозначное соответствие.

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

Пример 1. Множество натуральных чисел и множество целых чисел эквивалентны. Взаимно однозначное соответствие устанавливается следующим образом

Отсюда следует, что множество счетно.

Пример 2. Отрезки и эквивалентны. Соответствие устанавливается с помощью отображения .

Пример 3. Интервал эквивалентен . Соответствие устанавливается с помощью отображения

.

Отметим наиболее важные свойства счетных множеств.

1. Каждое бесконечное подмножество счетного множества счетно.

Действительно, пусть Х – счетное множество, его элементы могут быть пронумерованы: Х={а₁, а₂,…, а_n ,…}. Пусть Y – бесконечное подмножество множества Х. Обозначим через b₁ встретившийся в Х первым элемент множества Y, т.е. тот из элементов ряда а₁, а₂,…, а_n …, который принадлежит множеству Y и имеет наименьший номер n₀: . Через b₂ – тот из элементов а_n, который принадлежит множеству Y и имеет наименьший номер среди номеров n>n₀ и т.д. Каждый элемент множества Y имеется в ряде а₁, а₂,…, а_n ,…, поэтому через какое-то конечное число шагов он будет обозначен через b_m , и поскольку множество Y бесконечно, то индекс m примет любое значение 1, 2, …. Таким образом, все элементы множества Y будут занумерованы натуральными числами m=1, 2, ... . Это и означает счетность множества Y.

2. Объединение конечной или счетной совокупности счетных множеств счетно.

Рассмотрим сначала случай двух множеств. Пусть имеются множества А={а₁, а₂,…} и В={b₁, b₂,…}.Выпишем в одну строку все элементы обоих множеств по следующему правилу: а_1, b₁, а₂, b₂,…. Теперь все элементы можно заново перенумеровать по порядку следования в строке. Элемент, встречающийся два раза (т.е. входящий в оба множества), естественно приобретает номер в первый раз, а во второй раз пропускается. В результате каждый элемент объединения двух первоначальных множеств получит свой номер, что и требуется доказать.

Аналогично доказывается теорема и в случае конечного числа счетных множеств. В случае счетной совокупности

A₁={ а₁₁, а₁₂,…, а_1n,…},

A₂={ а₂₁, а₂₂,…, а_2n ,…},

A_m={ а_m1, а_m2,…, а_mn ,…}.

Изменение будет в способе нумерации. Например, можно использовать следующую схему

Рис. 1

3. Каждое бесконечное множество содержит счетное подмножество. Действительно, пусть Х – бесконечное множество. Возьмем какой-либо его элемент и обозначим его через х₁ .В силу того, что Х – бесконечное множество, в нем имеется хоть один элемент, отличный от х₁. Возьмем какой-либо из таких элементов и обозначим его через х_2. Пусть в множестве Х уже выбраны элементы х₁, … , х_n. Поскольку Х – бесконечное множество, в нем содержится еще и другие элементы. Выберем один из таких элементов и обозначим его х_n+1 и т.д. В результате мы получим элементы х_n, принадлежащие Х, n=1, 2, …, которые образуют счетное подмножество множества Х.

Теорема 1. Множество рациональных чисел счетно.

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

Занумеруем теперь элементы получившейся таблицы согласно схеме на рис. 1, в которой в кружочках стоят номера соответствующих элементов, а стрелки указывают направление нумерации. В результате все рациональные числа оказываются занумерованными, т.е. множество счетно.

Следствие 1. Множество всех многочленов с рациональными коэффициентами счетно.

Следствие 2. Множество всех алгебраических чисел (т.е. корней многочленов с рациональными коэффициентами) счетно.

Числа, не являющиеся алгебраическими, называются трансцендентными. Таковыми являются числа и е.

Бесконечные множества не являющиеся счетными называются несчетными множествами.

Теорема 2 (Кантора). Множество всех точек отрезка несчетно.

Доказательство. Допустим, что, напротив, множество всех точек отрезка [ 0,1] счетно и все их можно расположить в последовательность а₁, а₂,…, а_n ,… . Имея эту последовательность, построим следующим образом последовательность вложенных друг в друга отрезков. Разделим отрезок [0, 1] на три равные части. Где бы ни была точка а₁,она не может принадлежать сразу трем отрезкам [0, ⅓], [⅓, ⅔], [⅔, 1], и, следовательно среди них можно указать такой, который не содержит точки а_1. Этот отрезок мы обозначим через ∆₁ , на котором будет содержаться точка а₂. Когда таким образом будут построены отрезки ∆₁≥∆₂≥…≥ ∆_n, мы обозначим через ∆_n+1 ту из равных частей, на которой не содержится а_n+1 и т.д. Система вложенных отрезков по лемме о вложенных отрезках имеет общую точку ξ. Эта точка принадлежит каждому отрезку и, следовательно, не может совпадать ни с одной из точек а_n. Но это показывает, что последовательность а₁, а₂, …, а_n ,… не может исчерпывать всех точек отрезка [0, 1], вопреки первоначальному предположению.

Из этой теоремы и примера 3 следует, что множество всех действительных чисел несчетно.

Заметим, что, так как множество рациональных чисел отрезка счетно, следовательно, иррациональных чисел «значительно больше» чем рациональных. Более того, так как иррациональные алгебраические числа составляют счетное множество, то несчетное множество составляют числа, не являющиеся корнями многочленов с рациональными коэффициентами – трансцендентные числа.

Эквивалентные между собой два конечных множества состоят из одинакового числа элементов, т.е. конечные множества можно сравнивать по числу элементов. Но как сравнивать бесконечные множества? Если произвольные множества и эквивалентны, то говорят, что множества и имеют одинаковую мощность, таким образом, мощность – это то общее, что есть у всех эквивалентных между собой множеств. Мощность множества обозначается . Мощность счетного множества обозначается א₀ (алеф-нуль). Множества эквивалентные отрезку называются множествами мощности континуум. Мощность континуум обозначается буквой .

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

Из свойства 3 следует, что из всех бесконечных множеств счетные множества имеют наименьшую мощность, а из теоремы Кантора и свойства 3 следует, что C>א₀.

При сравнении бесконечных множеств используются следующие две наиболее важнейшие теоремы – теорема Кантора-Бернштейна и теорема 4.

Теорема 3 (Кантора-Бернштейна). Пусть и – два произвольных множества. Если в имеется подмножество А1~В, а в имеется подмножество В1~А, то множества и эквивалентны между собой.

Теорема 4. Множество всех подмножеств множества имеет мощность большую, чем мощность множества .

Рассмотрим конечное множество , содержащее элементов, и подсчитаем, сколько у него будет подмножеств. Будем использовать формулу числа сочетаний , выражающую число способов выбора k элементов из элементов. Имеем пустое подмножество , кроме того, имеются:

– одноэлементных подмножеств,

– двухэлементных подмножеств,

…………………………………………………….

– -элементных подмножеств,

…………………………………………………….

– ()-элементных подмножеств,

– само множество . Итого у множества имеется подмножеств.

Если теперь – бесконечное множество мощности , то по аналогии со случаем конечного множества мощность множества всех его подмножеств обозначают .

На основании теоремы 3 можно показать, что множество всех вещественных функций на отрезке имеет мощность большую чем , а именно , и более того, множеств с наибольшей мощностью не существует.