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

ЛЕКЦИЯ № 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,...}.Построим из его элементов последовательность: a₁=0; a₂=-1; a₃=1; a₄=-2; a₅=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...

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

Из элементов этой таблицы построим последовательность по следующему правилу a₁=0/1; a₂=1/1; a₃=-1/1; a₄=1/2; a₅=-2/1; a₆=2/1 и т.д., двигаясь в направлении, указанном стрелками. Очевидно, в эту последовательность войдут все рациональные числа. Более того, в ней многие числа будут повторяться. Следовательно, мощность множества элементов данной последовательности не меньше мощности множества рациональных чисел. С другой стороны, эта последовательность эквивалентна натуральному ряду, т.е. подмножеству множества Q, а значит она не может иметь мощность, большую чем Q. Значит, множество рациональных чисел счетно.

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

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

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

a₁, a₂, a₃,...

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

a_n1, a_n2, a_n3,...

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

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

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

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

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

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

А₁={a₁₁, a₁₂, a₁₃,...}

А₂={a₂₁, a₂₂, a₂₃,...}

А₃={a₃₁, a₃₂, a₃₃,...}

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

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

b₁=a₁₁, b₂=a₁₂, b₃=a₂₁, b₄=a₃₁, b₅=a₂₂,... (1)

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

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

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

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

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

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

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

ДОКАЗАТЕЛЬСТВО. Предположим противное, т.е. что эти последовательности можно занумеровать. Пусть P₁, P₂,... - последовательности, где P₁={a₁₁, a₁₂, a₁₃,...}, P₂={a₂₁, a₂₂, a₂₃,...} и т.д., где а_ij=0 или а_ij=1.

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