Структура некоторых числовых множеств
Значит
множество А
имеет мощность
.
Теорема доказана.
Теорема
8. Множество
всех последовательностей
вида
,
где
,
независимо
друг от друга,
принимают
значения 0 и 1,
имеет мощность
с.
Доказательство
Пусть
- множество тех
последовательностей
из
,
в которых, начиная
с некоторого
места, все
равны 1.
Каждой
последовательности
,
входящей в
,
можно соотнести
число, имеющее
двоичное разложение
;
это число будет
1 или
,
причем полученное
соответствие
между
и множеством
чисел указанного
вида, очевидно
взаимнооднозначно,
откуда следует,
что
множество
счетное.
С
другой стороны,
если
,
входящей в
соотнести число
с двоичным
разложением
,
то мы получим
взаимнооднозначное
соответствие
между
и полуинтервалом
[0,1), откуда вытекает,
что
,
а значит и Т,
имеют мощность
с. Теорема доказана.
Следствие 1. Если элементы множества А определяются с помощью счетного множества значков, каждый из которых, независимо от прочих, принимает два значения, то множество А имеет мощность с [6; 28].
§ 4. Сравнение мощностей
Мы определили
выше смысл
выражений «два
множества имеют
одинаковую
мощность»,
«множество
имеет мощность
»,
«множество
имеет мощность
с». Таким образом,
встретив слово
«мощность»
в одном из подобных
выражений, мы
знаем, что оно
означает, но
само по себе
понятие «мощность
множества»
у нас не определено.
Еще Г. Кантор пытался дать определение данному понятию:
«Мощностью данного множества А называется та общая идея, которая остается у нас, когда мы, мысля об этом множестве, отвлекаемся как от всех свойств его элементов, так и от их порядка» 2.
В
связи с этим
Г. Кантор обозначал
мощность множества
А символом
(две черты –
«двойное»
отвлечение).
В
настоящее время
канторовский
способ определения
понятия мощности
не считается
удовлетворительным
(хотя обозначение
оказалось очень
удачным). Вместо
этого принято
такое формальное
определение.
Определение
1.
Пусть все
множества
разбиты по
классам, так
что два множества
попадают в один
класс тогда
и только тогда,
когда они
эквивалентны.
Соотнесем
каждому такому
классу множеств
какой-либо
символ и будем
его называть
мощностью
любого множества
данного класса.
При этом, если
мощность некоторого
множества А
есть
,
то пишут
![]()
При таком
способе определения
ясно, что эквивалентные
множества
действительно
имеют одинаковую
мощность, а
также что, соотнеся
классу, содержащему
множество
всех натуральных
чисел, символ
,
можно сказать,
что счетное
множество имеет
мощность
.
Далее,
буква с есть
символ, соотнесенный
классу, содержащему
множество
и поэтому про
все множества,
эквивалентные
,
мы говорим, что
они имеют мощность
с.
Пусть
классу, содержащему
множество
,
соотнесен
символ «3». Тогда
можно сказать,
что любое множество,
эквивалентное
множеству А,
имеет мощность
3. Мы видим, что
понятие количества
элементов
конечного
множества есть
частный вид
более общего
понятия мощности.
Наконец, 0 есть мощность пустого множества, а 1 – мощность любого «одноэлементного» множества.
Имея, таким образом, определение понятия мощности, естественно поставить вопрос о сравнении мощностей.
Определение
2. Пусть
и
множества,
имеющие соответственно
мощности
и
(
,
)
Если: 1) множества
и
не эквивалентны,
но 2) в множестве
В есть подмножество
,
эквивалентная
множеству А,
то говорят, что
множество В
имеет большую,
а множество
А - меньшую мощность,
и пишут
,
.
Например
Пусть
,
,
,
,
тогда
не
,
но
,
где
.
Поэтому
.
Теорема 1.
Множество
всех действительных
функций, заданных
на отрезке
,
имеет мощность,
большую с.
Доказательство
Покажем
сначала, что
не
,
где
.
Допустим
противное.
Пусть
,
и пусть
- некоторое
взаимнооднозначное
соответствие
между
и
.
Условимся
обозначать
через
ту функцию из
,
которая отвечает
в соответствии
числу
.
Положим
.
Это некоторая
совершенно
определенная
функция двух
переменных,
заданная в
области
,
.
Положим теперь
.
Эта функция
задана для
,
т.е.
.
Но тогда в
соответствии
функция
отвечает некоторому
числу
,
т.е.
,
или
.
Таким образом,
получаем
,
.
А это невозможно,
например для
.
Итак, действительно
не
.
Рассмотрим
множество
функций
,
где
.
При этом
и
.
Значит множество
всех действительных
функций, заданных
на отрезке
,
имеет мощность,
большую с.
Теорема доказана.
Определение
3. Мощность
множества
всех функций,
заданных на
отрезке
,
обозначается
символом
.
Возникает
вопрос: существуют
ли мощности,
большие чем
?
Оказывается,
что да, существуют.
Больше того,
исходя из множества
любой мощности,
можно построить
множества
большей мощности
[6; 29].
Теорема 2.
Пусть М какое-либо
множество. Если
Т множество
всех подмножеств
множества М,
то
.
Доказательство
Отметим, что элементами множества Т являются все подмножества М, в частности само М, пустое множество 0 и все одноэлементные подмножества М.
Покажем
сначала, что
Т не
.
Допустим
противное.
Пусть
,
и пусть
- какое-либо
взаимнооднозначное
соответствие
между этими
множествами.
Каждому
в соответствии
отвечает определенный
элемент Т, который
мы обозначим
через
,
и каждый элемент
Т есть
для
одного и только
одного
.
Назовем
элемент
«хорошим», если
,
и «плохим» в
противном
случае. Элемент,
который в
соответствии
отвечает самому
множеству М,
наверное «хороший»,
а элемент, отвечающий
пустому множеству,
наверное «плохой».
Пусть
множество всех
«плохих» (и
только «плохих»)
элементов М.
Так как
,
то в соответствии
множеству
отвечает элемент
,
.
Каков же этот
элемент
- «хороший» или
«плохой»? Допустим,
что
«хороший»
элемент. Это
значит, что
,
а так как
состоит только
из «плохих»
элементов, то
элемент «плохой»,
что противоречит
сделанному
допущению.
Итак,
«плохой» элемент.
Но тогда
,
а это означает,
что
«хороший»
элемент.
Стало быть,
элемент
ни «хороший»,
ни «плохой»,
а так как всякий
элемент или
«хороший» или
«плохой», то
получается
абсурдная
ситуация, которая
и обнаруживает,
что Т не
.
Если
- множество
всех одноэлементных
подмножеств
М, то, очевидно,
,
а так как
,
то теорема
доказана.
Замечание.
Пусть М конечное
множество,
состоящее из
элементов.
Тогда множество
Т содержит
элементов.
В самом деле,
Т содержит одно
пустое множество,
одноэлементных
множеств,
двухэлементных
множеств, и
т.д., а всего в
Т будет входить
1 +
+
+ … +
=
элементов.
Отметим, что этот результат верен и для случаев, когда М пустое, или одноэлементное множество.
Определение
4. Если множество
М имеет мощность
,
а множество
всех его подмножеств
Т имеет мощность
,
то говорят, что
.
Теорема 3.
Справедлива
формула
.
Доказательство
Пусть Т –
множество всех
подмножеств
натуральных
чисел
,
а
множество всех
последовательностей
вида
.
Тогда