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

ЛЕКЦИЯ № 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 — по крайней мере вторым и т.д. Таким образом, построенная последовательность отличается от любой из занумерованных последовательностей хотя бы одним элементом. Следовательно, множество всех бинарных последовательностей занумеровать невозможно, а это означает, что оно несчетно.

Источник

Аннотация: Вводится понятие счетного множества, определяется несколько теорем с подробным доказательством. Что интересно, есть несколько замечаний к теоремам, которые решают тонкие вопросы, связанные с доказательством. Даются примеры счетных множеств для более глубокого понимания сути данной лекции. Некоторое количество задач для самостоятельного изучения. Также имеется небольшая историческая справка насчет теоремы: «Квадрат (с внутренностью) равномощен отрезку»

Множество называется счетным, если оно равномощно
множеству bb N натуральных
чисел,
то есть если его можно
представить в виде ${x_0,x_1,x_2,dots}$ (здесь x_i —
элемент, соответствующий числу ; соответствие взаимно
однозначно, так что все x_i различны).

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

Теорема 2.

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

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

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

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

(а) Пусть — подмножество счетного множества $Ahm={a_0,a_1,a_2,dots}$ . Выбросим из последовательности a_0, a_1, dots те члены, которые не принадлежат
(сохраняя
порядок оставшихся). Тогда оставшиеся члены образуют либо
конечную последовательность (и тогда конечно), либо
бесконечную (и тогда счетно).

(б) Пусть бесконечно. Тогда оно непусто и
содержит некоторый
элемент b_0 . Будучи бесконечным, множество не
исчерпывается
элементом b_0 — возьмем какой — нибудь другой
элемент b_1 , и т.д.
Получится последовательность b_0, b_1, dots ;
построение не прервется ни на каком шаге, поскольку бесконечно.
Теперь множество $Bhm={b_0,b_1,dots}$ и будет искомым счетным
подмножеством. (Заметим, что вовсе не обязано совпадать
с , даже если счетно.)

(в) Пусть имеется счетное число счетных множеств A_1, A_2, dots Расположив элементы каждого из них слева направо в
последовательность ( $A_ihm={a_{i0},a_{i1},dots}$ ) и
поместив эти последовательности друг под другом, получим
таблицу

$begin{array}{ccccc} a_{00} & a_{01} & a_{02} & a_{03} & ldots \ a_{10} & a_{11} & a_{12} & a_{13} & ldots \ a_{20} & a_{21} & a_{22} & a_{23} & ldots \ a_{30} & a_{31} & a_{32} & a_{33} & ldots \ ldots & ldots & ldots & ldots & ldots end{array}$

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

$a_{00}, a_{01}, a_{10}, a_{02}, a_{11}, a_{20}, a_{03}, a_{12}, a_{21}, a_{30}, ldots$

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

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

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

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

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

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

Множество рациональных
чисел
счетно. В самом деле,
рациональные числа представляются несократимыми дробями с целым
числителем и знаменателем. Множество дробей с данным знаменателем
счетно, поэтому представимо в виде
объединения счетного числа счетных множеств. Забегая вперед
(см.
«лекцию 4»
), отметим, что множество всех
действительных чисел несчетно.
Множество , элементами
которого являются наборы
из натуральных чисел, счетно. Это легко доказать индукцией
по . При множество пар натуральных
чисел разбивается на счетное число счетных множеств
(элементами -го множества будут пары, первый член которых
равен ).
Поэтому счетно. Аналогичным образом
множество
троек натуральных чисел разбивается на счетное
число множеств .
Каждое из них состоит из троек, первый член которых фиксирован и
потому равномощно множеству , которое счетно.
Точно так же можно перейти от счетности множества
к счетности множества $bbN^{k+1}$ .
Множество всех конечных последовательностей натуральных чисел
счетно. В самом деле, множество всех последовательностей
данной длины счетно (как мы только что видели), так что
интересующее нас множество разбивается на счетное число
счетных множеств.
В предыдущем примере не обязательно говорить о натуральных числах — можно
взять любое счетное (или конечное) множество. Например, множество
всех текстов, использующих русский алфавит (такой текст можно считать
конечной последовательностью букв, пробелов, знаков препинания и т.п.),
счетно; то же самое можно сказать о множестве (всех мыслимых)
компьютерных программ и т.д.
Число называют алгебраическим, если оно
является корнем
ненулевого многочлена с целыми коэффициентами. Множество
алгебраических чисел счетно, так как многочленов счетное число
(многочлен задается конечной последовательностью целых чисел —
его коэффициентов), а каждый многочлен имеет конечное число
корней (не более для многочленов степени ).
Множество периодических дробей счетно.
В самом деле, такая дробь
может быть записана как конечная последовательность символов из
конечного множества (запятая, цифры, скобки); например,
дробь можно записать как . А таких последовательностей счетное множество.

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

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

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

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

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

Источник

Теорема 2.

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

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

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

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

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

$a_{00}, a_{01}, a_{10}, a_{02}, a_{11}, a_{20}, a_{03}, a_{12}, a_{21}, a_{30}, ldots$

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

Множество рациональных
чисел
счетно. В самом деле,
рациональные числа представляются несократимыми дробями с целым
числителем и знаменателем. Множество дробей с данным знаменателем
счетно, поэтому представимо в виде
объединения счетного числа счетных множеств. Забегая вперед
(см.
«лекцию 4»
), отметим, что множество всех
действительных чисел несчетно.
Множество , элементами
которого являются наборы
из натуральных чисел, счетно. Это легко доказать индукцией
по . При множество пар натуральных
чисел разбивается на счетное число счетных множеств
(элементами -го множества будут пары, первый член которых
равен ).
Поэтому счетно. Аналогичным образом
множество
троек натуральных чисел разбивается на счетное
число множеств .
Каждое из них состоит из троек, первый член которых фиксирован и
потому равномощно множеству , которое счетно.
Точно так же можно перейти от счетности множества
к счетности множества $bbN^{k+1}$ .
Множество всех конечных последовательностей натуральных чисел
счетно. В самом деле, множество всех последовательностей
данной длины счетно (как мы только что видели), так что
интересующее нас множество разбивается на счетное число
счетных множеств.
В предыдущем примере не обязательно говорить о натуральных числах — можно
взять любое счетное (или конечное) множество. Например, множество
всех текстов, использующих русский алфавит (такой текст можно считать
конечной последовательностью букв, пробелов, знаков препинания и т.п.),
счетно; то же самое можно сказать о множестве (всех мыслимых)
компьютерных программ и т.д.
Число называют алгебраическим, если оно
является корнем
ненулевого многочлена с целыми коэффициентами. Множество
алгебраических чисел счетно, так как многочленов счетное число
(многочлен задается конечной последовательностью целых чисел —
его коэффициентов), а каждый многочлен имеет конечное число
корней (не более для многочленов степени ).
Множество периодических дробей счетно.
В самом деле, такая дробь
может быть записана как конечная последовательность символов из
конечного множества (запятая, цифры, скобки); например,
дробь можно записать как . А таких последовательностей счетное множество.

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

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

Источник