Какие свойства счетных множеств

ЛЕКЦИЯ № 3

Мощность множества

Рассмотрим множество всех молекул в земной атмосфере. Это множество содержит очень большое число элементов (примерно 1.02 77 010 541 0), но оно конечное, т.е. существует такая константа, которая больше числа элементов этого множества. Помимо конечных существуют бесконечные множества. Одной из задач теории множеств является определение числа элементов множества и исследование вопроса о сравнении друг с другом двух множеств по количеству элементов.

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

Пример 1. В качестве множества А рассмотрим интервал на числовой прямой, пусть А=(-1, 1), а в качестве множества В – множество действительных чисел R. Это множества одинаковой мощности, т.к отображение f(x) = tg(px/2), хÎА позволяет установить между ними искомое взаимно-однозначное соответствие.

Пример 2. Пусть А = [-1,1], В = (-1,1). Строим отображение f : A ® B по следующему правилу: выделим в А последовательность -1, 1, 1/2, 1/3, 1/4, . . . , 1/n и положим f(-1)=1/2, f(1)=1/3, f(1/2)=1/4, f(1/3)=1/5, т.е. f(1/n) = 1/(n+2), а все точки, не входящие в эту последовательность отобразим сами в себя, т.е. f(x) = =x. Следовательно, открытый и замкнутый интервалы эквивалентны.

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

Мощность – это то общее, что есть у двух эквивалентных множеств. Мощность множества A обозначается m(A) или |A|. Таким образом, m(A)=m(B), если A~B.

Если множество A эквивалентно какому-либо подмножеству множества B, то мощность A не больше мощности B (т.е. m(A)£m(B)). Если при этом множество B не эквивалентно никакому подмножеству множества A, то m(A)< m(B).

Простейшим среди бесконечных множеств является множество натуральных чисел N.

ОПРЕДЕЛЕНИЕ. Назовем счетным всякое множество, эквивалентное множеству N. Другими словами, счетным называется всякое множество, элементы которого можно перенумеровать или составить из них бесконечную последовательность.

Примеры счетных множеств.

1. Множество целых чисел Z={0, ±1, ±2, . . .}.Построим из его элементов последовательность: a1=0; a2=-1; a3=1; a4=-2; a5=2; . . . Формулу для вычисления ее общего члена можно записать в виде

2. Множество Q всех рациональных чисел.

Докажем счетность этого множества. Как известно, рациональные числа – это дроби вида p/q, где pÎZ, qÎN.

Запишем их в виде таблицы из бесконечного числа строк и столбцов

0/1®1/1 2/1®3/1 . . .

-1/1 -2/1 -3/1 -4/1 . . .

¯

1/2 2/2 3/2 4/2 . . .

-1/2 -2/2 -3/2 -4/2 . . .

. . . . . . . . . . . . .

Из элементов этой таблицы построим последовательность по следующему правилу a1=0/1; a2=1/1; a3=-1/1; a4=1/2; a5=-2/1; a6=2/1 и т.д., двигаясь в направлении, указанном стрелками. Очевидно, в эту последовательность войдут все рациональные числа. Более того, в ней многие числа будут повторяться. Следовательно, мощность множества элементов данной последовательности не меньше мощности множества рациональных чисел. С другой стороны, эта последовательность эквивалентна натуральному ряду, т.е. подмножеству множества Q, а значит она не может иметь мощность, большую чем Q. Значит, множество рациональных чисел счетно.

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

1. Всякое подмножество счетного множества конечно или счетно.

ДОКАЗАТЕЛЬСТВО. Пусть А – счетное множество и BÍА. Поскольку А счетно, то занумеруем его элементы и построим из них последовательность

a1, a2, a3, . . .

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

an1, an2, an3, . . .

Возможны следующие случаи:

1) множество B конечно;

2) множество B бесконечно.

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

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

ДОКАЗАТЕЛЬСТВО. Пусть множества А1, A2, . . . , Аn, . . . – счетные. Если их число не более, чем счетно, то множества можно занумеровать и расположить принадлежащие им элементы в таблицу

А1={a11, a12, a13, . . .}

А2={a21, a22, a23, . . .}

А3={a31, a32, a33, . . .}

. . . . . . . . . . . . . . . . .

Пусть B=. Построим последовательность подобно тому, как это было сделано в п. 4 при доказательстве счетности Q.

b1=a11, b2=a12, b3=a21, b4=a31, b5=a22, . . . (1)

Если множества Аi попарно пересекаются (Аi ÇАj ¹Æ), то в последовательность (1) не включаются те элементы, которые уже занумерованы. Таким образом, построено взаимно однозначное соответствие между множествами B и N. Следовательно, множество B счетно.

3. Всякое бесконечное множество содержит счетное подмножество.

ДОКАЗАТЕЛЬСТВО. Пусть М – произвольное бесконечное множество. Выберем в нем произвольный первый элемент и обозначим его a1 , затем – элемент a2 и т.д. Получаем последовательность a1, a2, . . . , которая не может оборваться на каком-то элементе, так как М бесконечно. Следовательно, данная последовательность образует счетное подмножество множества М.

Доказанная теорема позволяет утверждать, что среди бесконечных множеств счетное множество является самым “маленьким”.

Если множество конечно или счетно то говорят, что оно не более, чем счетно.

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

ТЕОРЕМА. Множество всех бесконечных бинарных последовательностей, т.е. состоящих из 0 и 1, несчетно.

ДОКАЗАТЕЛЬСТВО. Предположим противное, т.е. что эти последовательности можно занумеровать. Пусть P1, P2, . . . – последовательности, где P1={a11, a12, a13, . . .}, P2={a21, a22, a23, . . .} и т.д., где аij=0 или аij=1.

Построим последовательность P, не содержащуюся в этом списке. Такая последовательность существует, например, P={1-a11, 1-a22, 1-a33, . . .}. Очевидно, что ее элементы равны 0 или 1, причем она не равна никакой другой из списка, потому что отличается от последовательности P1 по крайней мере первым элементом, от P2 – по крайней мере вторым и т.д. Таким образом, построенная последовательность отличается от любой из занумерованных последовательностей хотя бы одним элементом. Следовательно, множество всех бинарных последовательностей занумеровать невозможно, а это означает, что оно несчетно.

                     7.
Счётные множества, их свойства

   Определение. Под множеством
А  понимается любое собрание определенных и различимых между собой

объектов, представляемых как единое целое. Эти объекты называются элементами
множества А.

Существенной деталью
является то, что для любого объекта можно установить, принадлежит он
множеству
или нет.

Множество задают (специфицируют) двумя
способами:

-перечислением: A={1,2,3};

– характеристикой свойств, общих для элементов
множества:

А = {X | P(X)} (А – это множество тех и только
тех элементов X для которых P от
X истинное предложение).

Примеры :||

А={1,2,3,4,5,6,7,8};

А- есть множество всех Х, таких, что Х-целое и
Х>0 и Х<9;

А={X | X – целое, 0<X<9}.  

Если элемент Х принадлежит множеству А, то
значит XîA, если не принадлежит, то XïA. Например, 7îА, 6ïА.

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

Например,

{1,2,3} = {2,1,3} = {2,1,1,3}

{{1,2}} ¹ {1,2} (Оболочка!)

То есть элемент не считается равным множеству,
если даже множество состоит только из этого элемента.

  Таким образом, Под
множеством А  понимается  любое собрание определенных и различимых
между собой
объектов, представляемых как единое целое. Эти объекты называются
элементами множества А.

  Множество задают (специфицируют) двумя
способами:

-перечислением: A={1,2,3};

– характеристикой свойств, общих для
элементов множества

        2.
Мощность множества.

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

Например, возьмём группу студентов из
тридцати человек и выдадим экзаменационные билеты по одному билету каждому
студенту из стопки, содержащей тридцать билетов, такое попарное соответствие из
30 студентов и 30 билетов будет одно-однозначным.

Два множества, равномощные с одним и тем
же третьим множеством, равномощны. Если множества M  и N равномощны, то и множества всех
подмножеств каждого из этих множеств M  и N , также равномощны.

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

 Мощность множества действительных
чисел, называют мощностью континуума и обозначают буквой «алеф»
 א .  
Наименьшей бесконечной областью является мощность множества натуральных чисел.
Мощность множества всех натуральных чисел принято обозначать (алеф-нуль)    .   

Часто мощности называют кардинальными
числами.  Это понятие введено немецким математиком Г. Кантором. Если
множества обозначают символическими буквами M, N , то кардинальные числа обозначают через
 m, n  . Г.Кантор доказал, что множество всех
подмножеств данного множества  М  имеет мощность большую, чем само
множество М.

Множество,
равномощное множеству всех натуральных чисел, называется  счетным
множеством

            Счётные множества, их свойства

Множество – равномощное множеству всех натуральных чисел (1,
2,3,….,n-1), например множество целых чисел, множество
чётных чисел, множество рациональных чисел; все другие бесконечные множества 
являются несчётными бесконечными множествами. Это означает, что все элементы
счётного множества можно перенумеровать, то есть обозначить натуральными
числами. Говорят, также, что счётное множество имеет мощность , а всякое множество, равномощное с множеством всех подмножеств
какого-нибудь счётного множества, имеет мощность или мощность континуума. Бесконечное множество считается счётным,
если можно установить одно-однозначное соответствие между его элементами и
натуральными числами. Мощность счётного множества, например, множества простых
чисел, меньше мощности любого бесконечного несчётного множества. Отношение между
счётным множеством и бесконечным несчётным множеством выражается следующими
теоремами:

1) мощность бесконечного множества не изменяется от прибавления
к нему счётного множества;

2)мощность несчётного множества не изменяется от удаления из
него  счётного множества;

3) любое подмножество счётного множества счётно;

4)сумма двух счётных множеств счётна;

5) сумма конечного и счётного множества счётна;

6) если множество А счётно, то множество всех конечных
последовательностей его элементов также счётно;

7) множество алгебраических чисел счётно.

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

Например, множество целых чисел счетно, так как
целые числа можно расположить в последовательность , , , , , , ,

Теорема 2.

(а) Подмножество счетного множества конечно или счетно.

(б) Всякое бесконечное множество содержит счетное
подмножество.

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

Доказательство

(а) Пусть – подмножество счетного множества . Выбросим из последовательности те члены, которые не принадлежат
(сохраняя
порядок оставшихся). Тогда оставшиеся члены образуют либо
конечную последовательность (и тогда конечно), либо
бесконечную (и тогда счетно).

(б) Пусть бесконечно. Тогда оно непусто и
содержит некоторый
элемент . Будучи бесконечным, множество не
исчерпывается
элементом – возьмем какой – нибудь другой
элемент , и т.д.
Получится последовательность ;
построение не прервется ни на каком шаге, поскольку бесконечно.
Теперь множество и будет искомым счетным
подмножеством. (Заметим, что вовсе не обязано совпадать
с , даже если счетно.)

(в) Пусть имеется счетное число счетных множеств Расположив элементы каждого из них слева направо в
последовательность ( ) и
поместив эти последовательности друг под другом, получим
таблицу

Теперь эту таблицу можно развернуть в последовательность,
например, проходя по очереди диагонали:

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

Если множеств конечное число или какие-то из множеств конечны,
то в этой конструкции части членов не будет – и
останется либо конечное, либо счетное множество.

29. Описанный
проход по диагоналям задает взаимно
однозначное соответствие между множеством всех пар натуральных
чисел (которое обозначается ) и .
Любопытно, что это соответствие
задается простой формулой
(многочленом второй степени с рациональными коэффициентами).
Укажите этот многочлен.

Замечание. В доказательстве утверждения (б)
теоремы 2 есть тонкий момент: на
каждом шаге мы должны выбрать один из оставшихся элементов
множества ; такие элементы есть, но у нас нет никакого
правила, позволяющего такой выбор описать. При более формальном
построении теории множеств тут нужно сослаться на специальную
аксиому, называемую аксиомой выбора.
Законность этой
аксиомы вызывала большие споры в начале 20-го века, но
постепенно к ней привыкли, и эти споры сейчас почти не
воспринимаются. В середине века великий логик Курт
Гедель доказал, что аксиому выбора
нельзя опровергнуть, пользуясь остальными аксиомами теории
множеств, а в 1960-е годы американский математик
Пол Дж.Коэн доказал, что ее нельзя и вывести
из остальных аксиом. (Конечно, понимание этих утверждений
требует подробного изложения теории множеств как аксиоматической
теории.)

30. Такой же тонкий момент (хотя и менее очевидный) есть и в
доказательстве утверждения (в). Можете ли вы догадаться,
где он? (Ответ: мы знаем, что множества счетны,
то есть что существует взаимно однозначное
соответствие между и . Но нужно
выбрать и фиксировать эти соответствия, прежде чем
удастся построить соответствие между объединением всех
и .)

Еще несколько примеров счетных множеств:

• Множество рациональных
  чисел
  счетно. В самом деле,
  рациональные числа представляются несократимыми дробями с целым
  числителем и знаменателем. Множество дробей с данным знаменателем
  счетно, поэтому представимо в виде
  объединения счетного числа счетных множеств. Забегая вперед
  (см.
  “лекцию 4”
  ), отметим, что множество всех
  действительных чисел несчетно.
• Множество , элементами
  которого являются наборы
  из натуральных чисел, счетно. Это легко доказать индукцией
  по . При множество пар натуральных
  чисел разбивается на счетное число счетных множеств
  (элементами -го множества будут пары, первый член которых
  равен ).
  Поэтому счетно. Аналогичным образом
  множество
  троек натуральных чисел разбивается на счетное
  число множеств .
  Каждое из них состоит из троек, первый член которых фиксирован и
  потому равномощно множеству , которое счетно.
  Точно так же можно перейти от счетности множества
  к счетности множества .
• Множество всех конечных последовательностей натуральных чисел
  счетно. В самом деле, множество всех последовательностей
  данной длины счетно (как мы только что видели), так что
  интересующее нас множество разбивается на счетное число
  счетных множеств.
• В предыдущем примере не обязательно говорить о натуральных числах – можно
  взять любое счетное (или конечное) множество. Например, множество
  всех текстов, использующих русский алфавит (такой текст можно считать
  конечной последовательностью букв, пробелов, знаков препинания и т.п.),
  счетно; то же самое можно сказать о множестве (всех мыслимых)
  компьютерных программ и т.д.
• Число называют алгебраическим, если оно
  является корнем
  ненулевого многочлена с целыми коэффициентами. Множество
  алгебраических чисел счетно, так как многочленов счетное число
  (многочлен задается конечной последовательностью целых чисел –
  его коэффициентов), а каждый многочлен имеет конечное число
  корней (не более для многочленов степени ).
• Множество периодических дробей счетно.
  В самом деле, такая дробь
  может быть записана как конечная последовательность символов из
  конечного множества (запятая, цифры, скобки); например,
  дробь можно записать как . А таких последовательностей счетное множество.

31. Докажите, что любое семейство непересекающихся интервалов
на прямой конечно или счетно. (Указание: в каждом интервале
найдется рациональная точка.)

32. (а)
Докажите, что любое множество непересекающихся восьмерок на
плоскости конечно или счетно. (Восьмерка – объединение двух
касающихся окружностей любых размеров.)

(б)
Сформулируйте и докажите аналогичное утверждение для букв
“Т”.

33. Докажите, что множество точек строгого локального максимума любой
функции действительного аргумента конечно или счетно.

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