4.2. Взаимно однозначные соответствия и мощность множеств
Утверждение (о взаимно однозначном соответствии равномощных множеств)
Если между конечными
множествами А и В существует взаимно
однозначное соответствие, то
.
Доказательство:
Действительно, если это не так, то либо
и тогда, так как соответствие всюду
определено, в А найдутся 2 элемента,
которым соответствует один и тот же
элемент
,
но тогда нарушена единственность
прообраза либо;
и тогда, поскольку соответствие
сюрьектвно, в В найдутся 2 элемента,
соответствующие одному и тому же
,
но тогда нарушена единственность образа.
Этот факт:
- позволяет установить равенство мощностей двух множеств, не вычисляя мощностей этих множеств;
- дает возможность вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.
Для иллюстрации этого приема докажем теорему о числе подмножеств конечного множества.
Теорема (числе подмножеств конечного множества)
Если для конечного
множества А,
,
то число всех подмножеств А равно
,
то есть
.
Доказательство:
Занумеруем элементы А по номерам от 1 до n.
и рассмотрим
множество
двоичных векторов из нулей единиц длины
n. Каждому подмножеству
поставим в соответствие вектор
следующим образом:
Например,
,
,
,
.
Здесь и далее
знаком “
”
обозначено “соответствует”.
Например,
,
то подмножеству
соответствует вектор (1, 1, 1, 1, 0), а
.
Поэтому, подмножеству
соответствует вектор из нулей, а самому
А - из единиц. Очевидно, что установленное
соответствие между множеством всех
подмножеств множества А и двоичными
векторами длины n является взаимно
однозначным, и число подмножеств А равно
.
А так как
является прямым произведением n
двухэлементных множеств {0,1} (т. е.
),
то, в силу следствия из теоремы о мощности
прямого произведения множеств, имеем:
так как
,
то есть
.
Определение: Множества равномощны, если между их элементами можно установить взаимно однозначное соответствие.
Для конечных множеств это утверждение доказывается. Для бесконечных множеств оно является определением равномощности.
Определение: Счетные множества это множества равномощные N (т. е. между ними и N можно установить взаимно однозначное соответствие).
4.3. Счетные множества
Утверждение 1:
Множество
- счетно. Соответствие между N и
взаимно однозначно. Это было показано
в примере.
.
Утверждение 2:
Вообще любое бесконечное подмножество множества N - счетно.
Пояснение.
Действительно, пусть
.
Выберем в
наименьший элемент и обозначим его за
.
В
выберем наименьший элемент и обозначим
его за
.
В
выберем наименьший элемент и обозначим
его за
и т. д. Поскольку для всякого
натурального числа имеется лишь конечное
множество меньших натуральных чисел,
то любой элемент из
рано или поздно получит свой номер. Эта
нумерация, то есть соответствие
,
и есть взаимно однозначное соответствие
между
и N.
Утверждение 3:
Множество
- счетно.
Пояснение.
Нумерацию
можно устроить следующим образом.
Разобьем
на классы. К первому классу
отнесем все пары чисел с наименьшей
суммой, такая пара одна — (1, 1).
Ко второму классу
отнесем все пары чисел с суммой 3:
.
В общем случае
.
Каждый класс содержит ровно i пар.
Упорядочим теперь классы по возрастанию
индексов i, а пары внутри класса по
возрастанию первого элемента и занумеруем
получившуюся последовательность
номерами 1, 2, 3, . . . Очевидно,
что если a+b = i+1, то пара (a,b) получит
номер:
1+2 + . . . (i - 1) + a ,
(где а – нумерация
в классе
по возрастанию первого элемента пары,
то есть по элементу а). Эта нумерация
доказывает счетность
.
Следствие (из Утверждения 3)
Множество P -
положительных рациональных чисел
(то есть дробей вида
,
где a и b - натуральные числа) - счетно.
Подчеркнем, что нумерация числового множества Р не имеет ничего общего с упорядочением элементов по величине. В множестве Р нет ни наименьшего элемента, ни двух соседних по величине элементов, однако есть элементы с наименьшим номером и с соседними номерами).
Утверждение 4:
Множество
и вообще
для
любого натурального k
- счетно.
Доказательство: аналогично (3).
Утверждение 5:
Объединение
конечного числа счетных множеств
- счетно, то есть счетно
,
где
-
конечное число.
Доказательство:
Перенумеруем сначала все первые элементы множеств, затем все вторые и т. д.
Утверждение 6:
Объединение счетного множества конечных множеств - счетно.
Доказательство:
Нумеруем сначала
все элементы первого множества, затем
все элементы второго и т. д., т. е.
счетно
,
где
- конечное число.
Следствие (из Утверждения 6):
Множество всех слов конечного алфавита - счетно.
А - алфавит,
- множество всех слов,
- конечное число.
Так как
,
то каждое из этих множеств имеет конечную
мощность. Введем обозначение
, тогда
,
то есть выполняется
утверждение - счетное объединение
конечных множеств - счетно.
- объединение счетного числа множеств,
так как между
и множеством натуральных чисел можно
установить взаимно однозначное
соответствие.
Утверждение 7:
Объединение
счетного множества счетных множеств -
счетно, т. е.
- счетное число и
- счетное число.
Пример:
Объединением счетного множества счетных
множеств является, например,
- множество всех векторов с натуральными
компонентами.
- счетное множество,
и для любого i
- счетно.
Теорема Кантора:
Множество всех действительных чисел отрезка [0, 1] не является счетным.
Доказательство:
При доказательстве используется так называемый диагональный метод Кантора. Докажем от противного.
Пусть это множество
точек отрезка
счетно, и существует его нумерация
(взаимно однозначное соответствие с
N). Расположим все числа, изображенные
бесконечными десятичными дробями в
порядке этой нумерации.
Рассмотрим любую
бесконечную десятичную дробь
такую, что
Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от второго - второй и т. д. Таким образом, все числа отрезка [0, 1] не могут быть пронумерованы, следовательно, множество всех действительных чисел отрезка [0, 1] несчетно.
Определение: Мощность несчетного множества называется континуум.
Континуальные множества - множества мощности континуум (то есть несчетные множества).
Следствие из теоремы Кантора:
Множество всех подмножеств счетного множества континуально.
Доказательство:
- счетное множество.
- некоторое его подмножество.
Воспользуемся, как в теореме о числе подмножеств конечного множества, представлением подмножества в виде последовательности (но теперь уже бесконечной!) нулей и единиц.
На i - месте
последовательности стоит 1, если
входит в данное подмножество.
На i - месте
последовательности стоит 0, если
не входит в данное подмножество. Получаем
(соответствует), где
следующим образом:
.
Причем, каждый такой вектор единственным образом соответствует десятичной дроби отрезка [0, 1] по принципу: если данную последовательность считать дробной частью двоичного представления числа, то найти его значение в десятичной системе счисления можно по формуле
0,101011... 
...
Это
взаимно однозначное соответствие между
подмножествами счетного множества А
и правильными двоичными дробями
,
которые, в свою очередь, взаимно однозначно
соответствуют континуальному множеству
чисел отрезка [0, 1] приводит к выводу
о том, что мощность множества V-
есть континуум, а, значит, континуальным
является и множество подмножеств
счетного множества А.