Множества


1. Определение и примеры

Редкое определение играет в математике столь же большую роль, что и определение множества. Собственно, поэтому так важно понять его и уловить его суть сразу, в самом начале. В этой статье я попытаюсь дать неискушённому читателю представление о множествах в высшей математике, их свойствах и применениях.

В формальной математике множество — обычно аксиоматическое понятие, и у него нет определения как такового. И его действительно сложно дать — ведь под множеством мы подразумеваем любой набор любых объектов. Этот набор может быть пустым, конечным или бесконечным; он может содержать натуральные, вещественные числа, матрицы, целые последовательности, мыслимые как самостоятельные объекты, или даже другие множества, такие, как отрезки и лучи вещественной прямой (или даже вся вещественная прямая), а также стулья, столы, вилки, яблоки, торшеры, турнюры и так далее. Притом не налагается абсолютно никаких ограничений на однородность объектов, содержащихся в множестве — одно множество может содержать одновременно как числа, так и, например, другие множества. Объекты в множестве также по умолчанию никак не упорядочены (если не указано обратное, смотри далее про упорядоченные множества). Кстати, объекты, содержащиеся в множестве, обычно называются его элементами.

Основоположник теории множеств, великий немецкий математик Георг Кантор говорил, что множество – это многое, мыслимое как единое.

Однако некоторые ограничения при конструировании всевозможных множеств всё-таки есть. Необходимость в введении таких ограничений явно показывает, например, парадокс Рассела. Он звучит так:

Пусть K — множество всех множеств, которые не содержат себя в качестве своего элемента. Вопрос: содержит ли K само себя в качестве элемента? Если да, то, по определению K, оно не должно быть элементом K — получаем противоречие. Если нет — то, по определению K, оно должно быть элементом K; вновь получаем противоречие.

Логический парадокс, возникший здесь, связан в том числе с использованием такой конструкции, как «множество всех множеств, таких, что …» и «множество, содержащее себя в качестве элемента». Такие множества невозможно себе представить, и невозможно сконструировать какими-либо разумными и последовательными путями. Чтобы избежать возникновения таких вот парадоксов, математики вот уже добрую сотню лет пытаются формализовать понятие множества, усложняя и усложняя теорию Кантора. Но это очень специфичная область; нам же достаточно лишь знать, что без формулировок типа «множество всех множеств» и «множество, содержащее себя» в наших выкладках всё будет хорошо.

Студенты, изучающие всевозможные курсы высшей математики и математического анализа, большую часть времени будут сталкиваться с частными случаями множеств — числовыми множествами, то есть множествами, элементами которых являются исключительно вещественные числа. Например, все вещественные числа образуют множество, которые мы привыкли называть вещественной прямой и обозначать значком ℝ. Также мы уже знаем о таких числовых множествах, как отрезок [a,b] — множество всех вещественных чисел x, удовлетворяющих неравенству a≤ x≤ b, и интервал (a,b) — множество всех вещественных чисел x, удовлетворяющих неравенству a< x<b. Кстати, давайте разберёмся с обозначениями. Последние два примера множеств можно записать в следующем, общепринятом для описания множеств виде:
[a, b] = {x∈ℝ: a≤ x≤ b} ,
(a, b) = {x∈ℝ: a<x<b} .

То есть такое описание множества состоит из двух частей: определения, какого рода элементы оно содержит, и условия (или нескольких), которому должен удовлетворять элемент, чтобы в нём содержаться. Например, в последней формуле выражением x∈ℝ мы обозначили, что наше множество содержит только вещественные числа, а условием a<x<b сузили «круг подозреваемых» до элементов интервала (a,b). Можно придумать и более экзотические примеры. Например,
A = {x∈ℝ: x^2+x−2=0}
— это множество всех вещественных корней уравнения x^2+x−2=0. Кстати, мы ведь знаем эти корни — это 1 и −2. Так давайте тогда запишем множество A проще:
A = {1, −2} .

Здесь мы сконструировали множество простым перечислением всех входящих в него элементов. При таком способе построения множество записывается просто как фигурные скобки с выписанными внутри них в любом порядке элементами множества.

Причём так можно записывать и бесконечные множества. Например, множество натуральных чисел:
ℕ = {1, 2, 3, …, n, n+1, …} .

Отдельно обращу внимание на то, что элементы во множествах не могут повторяться. То есть если у нас есть некий элемент x и множество A, то мы можем лишь сказать, что x принадлежит множеству A (это записывается как x∈ A) либо не принадлежит множеству A (это записывается как x\notin 
A), но не можем и не имеем права сказать, сколько раз он содержится в A. Но если мы вдруг запишем множество A={x, x}, то ничего страшного не случится и запись не будет ошибочной — просто она будет значить то же самое, что и A={x}.

2. Сравнение множеств

Есть несколько способов сравнить два данных нам множества A и B. Множество A называется подмножеством множества B (или говорят, что A вложено в множество B), если все элементы A содержатся в B. То есть множество B «шире» множества A и полностью его покрывает. Такое взаимоотношение множеств обозначается как A⊂ B или A⊆ B. Соответственно, симметричные значки ⊃ и ⊇ означали бы, что B является подмножеством A. (Тут присутствует полная аналогия со знаками <, ≤, >, ≥.)

В некоторых книжках различают ещё понятие строгой вложенности: множество A называется собственным подмножеством множества B, или говорят, что A строго вложено в множество B, если оно просто вложено в B и при этом не совпадает с ним, то есть в B есть ещё какие-то элементы, которых нет в A. В таких книжках значки ⊂ и ⊃ используют именно для обозначения строгой вложенности. Но мы, следуя большинству учебников для младших курсов, не будем различать строгую и нестрогую вложенность множеств и будем пользоваться значками ⊂ и ⊃ независимо от того, могут A и B совпадать или нет.

Как можно было догадаться, множества A и B называются равными, если они совпадают, то есть любой элемент, который есть в A, есть и в B, и наоборот. Ещё это определение можно записать так: A=B, если одновременно A⊂ B и A⊃ B. (Ещё раз обращаю внимание: мы могли написать A⊆ B и A⊇ B, но мы договорились не различать между собой значки ⊂ и ⊆.)

Ещё одно интересное понятие, касающееся сравнения множеств — их эквивалентность — мы подробно обсудим ниже.

3. Операции над множествами

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

Итак, пусть у нас есть два произвольных множества A и B.

Объединением множеств A и B называется множество C, содержащее и все элементы A, и все элементы B; и только их. (Причём если какой-то элемент есть и там, и там, то в C он будет, разумеется, в единственном экземпляре, ведь, как мы заметили выше, элементы в множествах не повторяются.) Множество C обозначается как A∪ B; причём мы можем записать его, используя введённые выше обозначения:
C = {x: x∈ A  или  x∈ B} .
То есть операция объединения множеств имеет чёткую логическую интерпретацию: если x принадлежит C, то либо x принадлежит A, либо x принадлежит B (вариант «и то, и то», разумеется, тоже возможен).

Например, если A⊂ B, то A∪ B=B, потому что все элементы из A и так уже содержатся в B.

Далее, пересечением множеств A и B называется множество C, содержащее только те элементы, что есть и в A, и в B. Множество C обозначается как A∩ B; причём мы опять-таки можем записать его, используя общие обозначения:
C = {x: x∈ A  и  x∈ B} 
То есть логическая интерпретация операции пересечения такая: если x принадлежит C, то x непременно принадлежит и A, и B.

А что произойдёт, если у множеств A и B нет никаких общих элементов? Множество C=A∩ B тогда не должно содержать ни одного элемента. Так и будет! Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается ∅.

Кстати, когда говорят о двух непересекающихся множествах A и B, то их объединение иногда обозначают специальным значком A\sqcup B, чтобы подчеркнуть, что «слагаемые» не пересекаются.

Разностью множеств A и B называется множество C, содержащее все элементы A, не содержащиеся в B. C обозначается через A\ B и в общих обозначениях записывается как
C = {x: x∈ A  и  x\notin B} .
То есть C — это множество A, из которого «вырезали» множество B.

Симметрической разностью множеств A и B называется множество C = (A\ B)∪ 
(B\ A). Оно обозначается как A\bigtriangleup B. Легко видеть, откуда у этой операции такое название — в отличие от обычной разности, она симметрична, то есть от перемены мест «слагаемых» «сумма» не изменяется.

3.1. Диаграммы Венна

Диаграммы Венна — отличный способ сделать вышеизложенное ещё понятнее и очевиднее. Вот пример диаграммы Венна, изображающей результат операции пересечения:
То есть просто наши множества A и B совершенно загадочной для нас природы изображаются схематически в виде кругов. Такой подход позволяет предельно наглядно изобразить результаты элементарных операций над множествами. На картинке выше заштриховано пересечение множеств A и B. А вот как будет выглядеть их объединение:
А вот разность:
Диаграммы Венна позволяют изобразить ситуации и посложнее, и в дальнейшем мы будем ими пользоваться для доказательства некоторых соотношений. Вот пример диаграммы Венна с тремя множествами:
(Попробуйте отгадать, какая формула с A, B и C соответствует такому множеству!)

3.2. Законы де Моргана

Первое, в чём мы попытаемся разобраться с помощью диаграмм Венна, — это два закона де Моргана.

Для этого нам понадобятся кое-какие приготовления. Давайте возьмём какое-нибудь большое множество Ω (например, вещественную плоскость) и будем предполагать, что наши множества A и B являются подмножествами Ω. При таком рассмотрении мы можем ввести ещё одну элементарную операцию — операцию дополнения. Дополнением ко множеству A во множестве Ω называется множество C=Ω\ A. Оно обозначается как \bar{A} (если только из контекста понятно, в каком Ω идёт дело; если нет, то используются альтернативные обозначения, например, A^{Ω}).

Теперь, зная понятие дополнения и зафиксировав какое-нибудь произвольное Ω на ваш вкус, мы можем сформулировать два логических закона де Моргана:
\begin{array}{c}
\overline{A∪ B}=\bar{A}∩\bar{B} ,\\
\overline{A∩ B}=\bar{A}∪\bar{B} .
\end{array}
Законы эти я назвал логическими, потому что они пришли к нам из особого раздела математики — математической логики. Огастес Де Морган не видел в них какие-либо множества — он видел логическое утверждение A и логическое утверждение B (под логическим я подразумеваю утверждение, которое заведомо либо является истиной, либо ложью). Объединение A и B было для него логическим утверждением «верно хотя бы одно из утверждений A и B», пересечение — «верны одновременно и A, и B», а дополнение к A значило утверждение, противоположное A (то есть являющееся истинным, если A ложно, и ложным, если A истинно). Вспомните наши замечания по поводу логической интерпретации операций над множествами — вот они и пригодились.

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

Итак, во-первых,
A∪ B=    
Следовательно,
§cale[2]{\overline{A∪ B}=}    
На диаграмме Ω — это весь прямоугольник.

Во-вторых, имеем
§cale[2]{\bar{A}=}    
и
§cale[2]{\bar{B}=}    
Следовательно,
§cale[2]{\bar{A}∩\bar{B}=}    

Итак, мы получили в левой и правой части формулы одно и то же множество. Точно так же можно доказать и второй закон. Впрочем, строгим доказательством это назвать нельзя, но, хотя и так, его полезность сложно переоценить. Диаграммы Венна дали нам понять, почему справедлив закон де Моргана, — и это самое важное. Ну а строгое доказательство — это уже дело техники. (Попробуйте его проделать!)

3.3. Произведение множеств

Ещё одна крайне важная и часто встречающаяся операция над множествами — их произведение. Чтобы дать определение этой причудливой операции, нам потребуется понятие набора.

Набором, или кортежем называется совокупность конечного числа элементов, заданных в определённом порядке. Важно: в наборе, в отличие от нашего традиционного множества, элементы могут повторяться. Набор из элементов x_1,x_2,…,x_k зачастую обозначается как ⟨ x_1,x_2,…,x_k⟩.

Собственно, в этом параграфе нас будет интересовать по большей части один частный случай набора — упорядоченная пара. Упорядоченная пара — это просто набор из двух элементов. Пару из элементов a и b мы будем обозначать как (a,b) (не путать с интервалом вещественной прямой!).

Вот теперь можно перейти и к самому интересному.

Представьте, что у нас есть два непустых множества A и B. Их элементы, как обычно, могут не иметь между собой ничего общего; сами множества могут пересекаться, а могут и нет — в данный момент нас это совершенно не волнует. Так вот, декартовым произведением двух множеств A и B называется множество C всевозможных упорядоченных пар (a,b), в которых a∈ A и b∈ B. Оно обозначается как A× B.

Итак, что же мы сделали? Мы «скрестили» два множества A и B, получив новое множество с совершенно новыми элементами. Если раньше, например, элементами «множителей» A и B были числа, то мы получим множество, элементы которого — пары чисел. Например, пусть A={1,2,3} и B={4,5,6}. Тогда
A× B = {
    (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)
} .
Кстати, множество A× B можно записать в удобной форме, которую мы уже изучили выше:
A× B = {
    (a, b): a∈ A  и  b∈ B
} .

Рассмотрим пример посложнее. Вы, наверное, помните, что точки на плоскости удобно описывать двумя числами — её координатами. То есть любой точке плоскости M с координатами x_M,y_M соответствует упорядоченная пара (x_M,y_M)! Значит, упорядоченные пары вещественных чисел можно рассматривать как точки на плоскости. Так и будем делать.

Теперь пусть A=[a.b] и B=[c,d] — два отрезка вещественной прямой. Тогда их декартовым произведением будет множество точек плоскости C, которое имеет вид
Прямоугольник на плоскости
То есть мы получаем прямоугольник на плоскости! Действительно, если первые координаты всех входящих в C точек изменяются от a до b, а вторые — от c до d, то фигура, которую они образуют, и будет изображённым выше прямоугольником.

Давайте двигаться дальше. Что, если полученый прямоугольник мы умножим на ещё один отрезок [p,q]? Элементами полученного множества будут упорядоченные пары вида (s,z), где z∈ [p,q], а s — тоже упорядоченная пара вида (x,y). То есть вся эта конструкция имеет вид ((x,y),z). Давайте отождествим её с набором из трёх элементов (x,y,z) — и полученное нами множество теперь можно связать с некоторым множеством в трёхмерном пространстве. Можете самостоятельно проверить, что в данном случае это будет прямоугольный параллелепипед размера (b−a)×(d−c)×(q−p).

Ещё одним примером трёхмерной фигуры, полученной декартовым произведением множеств, может быть цилиндр:
Цилиндр в пространстве является произведением круга и отрезка
Кстати, заметьте, что круг декартовым произведением двух множеств в декартовых координатах уже не получить (попробуйте это доказать!).

Для удобства вводят иногда определение декартова произведения n множеств; декартовым произведением n множеств A_1,A_2,…,A_n называют множество
C = {
    (x_1, x_2, …, x_n): x_1∈ A_1, x_2∈ A_2, …, x_n∈ A_n
} .
Здесь элементами произведения сразу являются наборы из n элементов исходных множеств, а не пары, содержащие другие пары, что позволяет сразу рассматривать множество C как многомерную фигуру без дополнительных замечаний, сделанных нами выше. Кстати, такое произведение обозначается как A_1× A_2×…× A_n.

4. Мощности множеств

Итак, мы потихоньку подходим к важнейшему вопросу о мощности множеств. Формальная сторона этого вопроса довольно замысловата, так что поначалу займёмся объяснением «на пальцах».

4.1. Счётные множества

Мы уже столкнулись с таким понятием, как конечное множество — это множество, в котором конечное (то есть не бесконечное) количество элементов. Такие множества довольно просты. Например, мы можем записать их обычным перечислением всех их элементов. (Разумеется, можем мы это чисто теоретически; даже если множество и конечно, то в нём может быть миллион, миллиард, триллион и вообще сколько угодно элементов, и записать их все мы физически не сможем.) Понятно, что объединение, пересечение, разность двух конечных множеств — тоже конечное множество. (Обратите внимание, что пустое множество считается по определению конечным и содержащим 0 элементов.) Действительно, откуда там взяться бесконечному количеству элементов? Можно взять свойство и посложнее: пересечение конечного и бесконечного множеств всегда конечно. Опять-таки, откуда в нём взяться бесконечному числу элементов, если все они должны принадлежать каждому из «множителей», в том числе и нашему конечному множеству?

В конечном множестве мы можем точно и однозначно сосчитать количество элементов. Если A — некоторое конечное множество, то количество его элементов обозначается как \#A или |A|. (Кстати, интересное замечание: если A={1,2,{3,4,5}}, то |A|=3, потому что в A ровно 3 элемента: 1, 2 и некоторое множество {3,4,5}.) Соответственно, мы можем легко сравнить, в каком множестве, например, больше элементов; можем сделать оценки, сколько элементов может быть в объединении, пересечении, разности двух конечных множеств. Например, для двух конечных м ножеств A и B справедливы неравенства
\max{|A|, |B|} ≤ |A ∪ B| ≤ |A|+|B| ;
0 ≤ |A ∩ B| ≤ \min{|A|, |B|} ;
|A|−|B| ≤ |A\ B| ≤ |A|
и равенство
|A× B| = |A|⋅|B| .
(Не поленитесь, проверьте каждое из них. Диаграммы Венна вам в помощь, кстати.)

Вспомним один из примеров бесконечных множеств, а именно множество натуральных чисел ℕ. Оно бесконечно; но у него есть приятная особенность — хоть его элементы и нельзя сосчитать, их можно занумеровать, каждому дать порядковый номер, причём так, что ни один элемент не окажется обделён вниманием. И сделать это очень просто — здесь каждый элемент, собственно, и есть номер.

Теперь возьмём какую-нибудь последовательность {a_n}_{n=1}^{∞}, в которой, для простоты, все числа разные. Она, рассмотренная как множество, удовлетворяет тому же свойству — все её элементы могут быть занумерованы натуральными числами, и даже не могут, а уже занумерованы. (Если бы в ней какие-то числа повторялись, то при превращении последовательности в множество повторы пришлось бы выкинуть, и нумерация бы усложнилась.)

И вообще, возьмём теперь любое множество X, в котором все элементы занумерованы натуральными числами, при этом номера не повторяются и каждому натуральному номеру соответствует элемент (то есть нет пробелов в нумерации). Тогда говорят, что определено взаимно-однозначное соответствие между элементами множеств X и ℕ (обозначается X≤ftrightarrowℕ), а само множество X называется счётным множеством.

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

Класс счётных множеств шире, чем могло показаться на первый взгляд. Очень простым, но в то же время довольно поучительным примером счётного множества является множество целых чисел ℤ. Изначально оно «занумеровано», но некоторым особым образом: нумерация идёт в две стороны. Но, тем не менее, элементы этого множества можно занумеровать. Вот так:
\begin{matrix}
1 && 2 & 3 & 4 & 5 & ⋅s & 2n & 2n+1 & ⋅s\ 
\updownarrow && \updownarrow & \updownarrow & \updownarrow & 
\updownarrow && \updownarrow & \updownarrow & \ 
0 && 1 & −1\hphantom{−} & 2 & −2\hphantom{−} & ⋅s & n & −n\hphantom{−} & ⋅s
\end{matrix}
Но и это ещё не всё. Давайте рассмотрим множество рациональных чисел
ℚ=≤ft{
    (m) ⁄ (n): m∈ℤ, n∈ℕ
\right} .
На первый взгляд (ну или по крайней мере на второй) кажется, что оно ну просто невообразимо шире множеств ℕ и ℤ: как же, ведь можно построить взаимно-однозначное соответствие между ℚ и декартовым произведением ℤ×ℕ:
(m) ⁄ (n) \longleftrightarrow (m,n), где m∈ℤ,n∈ℕ .
Однако. Во-первых, это не взаимно-однозначное соответствие. Почему? Потому что разным парам чисел (m,n) могут соответствовать одни и те же рациональные числа:
1 \longleftrightarrow (1,1), но также 1 \longleftrightarrow (17,17) .
Так что правильнее было бы обозначать его значком \longleftarrow.

Во-вторых, даже если бы оно было взаимно-однозначным, это бы не стало проблемой! Вот как можно занумеровать всевозможные пары из одного целого и одного натурального чисел:
\begin{array}{c|ccccccccc}
& 0 && 1 && −1 && 2 && ⋅s \ \hline
1 & (0,1) &\rightarrow& (1,1) && (−1,1) &\rightarrow& (2,1) && ⋅s \\[1mm]
  &       && \downarrow && \uparrow && \downarrow \\[1mm]
2 & (0,2) &≤ftarrow& (1,2) && (−1,2) && (2,2) && ⋅s \\[1mm]
  & \downarrow &&&& \uparrow && \downarrow\\[1mm]
3 & (0,3) &\rightarrow& (1,3) &\rightarrow& (−1,3) && (2,3) && ⋅s \\[1mm]
  & &&&&&& \downarrow\\[1mm]
4 & (0,4) &≤ftarrow& (1,4) &≤ftarrow& (−1,4) &≤ftarrow& (2,4) && ⋅s \\[1mm]
  & \downarrow \\
\vdots & \vdots && \vdots && \vdots && \vdots && \ddots
\end{array}
Здесь стрелки указывают направление нумерации, которая начинается на элементе (0,1). Настойчивый студент, вероятно, даже сможет найти формулу, определяющую номер пары (m,n)∈ℤ×ℕ. Также можно заметить, что, по большому счёту, мы не использовали структуру множеств ℤ и ℕ, а только лишь их нумерацию. Иными словами, точно такой же метод нумерования позволяет занумеровать декартово произведение любых двух счётных множеств: декартово произведение двух счётных множеств всегда счётно!

Что же касается несчастных рациональных чисел, то тут теперь всё просто. Будем нумеровать пары (m,n) по описанной схеме, записывая по ходу дела соответствующие им рациональные числа (m) ⁄ (n) в какое-нибудь множество A. Если полученное на очередном шаге рациональное число уже есть в A, отбрасываем его, не нумеруя повторно, и идём дальше. Если внимательно провести этот процесс, множество рациональных чисел занумеруется примерно следующим образом:
\begin{matrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & ⋅s \ 
\updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & 
\updownarrow & \updownarrow & \\[2mm]
\hphantom{−}0\hphantom{−} & \hphantom{−}1\hphantom{−} & \hphantom{−}(1) ⁄ (2)\hphantom{−} & \hphantom{−}(1) ⁄ (3)\hphantom{−} & −(1) ⁄ (3)\hphantom{−} & −(1) ⁄ (2)\hphantom{−} & −1\hphantom{−} & ⋅s
\end{matrix}
(Попробуйте самостоятельно продолжить последовательность!)

Итак, рациональные числа занумерованы и совсем не страшны! Поначалу может быть трудно представить, что рациональные числа, бесконечное количество которых можно найти даже в самом микроскопическом кусочке вещественной прямой, можно занумеровать, и, стало быть, в этом смысле их даже не больше, чем натуральных. Но, тем не менее, мы только что убедились, что это так.

Такая вот «магия» встречается в теории множеств. Хоть множество натуральных чисел и вложено во множество рациональных, в плане счётности их одинаково много! Так же и с целыми числами: их, вроде бы, «в два раза больше», но в плане счётности и их столько же, сколько и натуральных. Если же взять чисел поменьше, например, из натуральных оставить только чётные, то и их будет счётное число! Получается, что из бесконечной последовательности всегда можно выкинуть бесконечное число элементов так, что она всё равно останется бесконечной.

4.2. Несчётные множества

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

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

Напомню сперва, что вещественное число — это число, представимое в виде бесконечной десятичной дроби вида
a_0.a_1a_2a_3… a_k…,  a_0∈ℤ, a_i∈{0,…,9}
 для всех номеров i∈ℕ .
Рассмотрим для простоты все вещественные числа полуинтервала [0,1). Для них для всех в указанной выше формуле a_0=0. Теперь предположим, что мы вдруг смогли каким-либо образом их все занумеровать, вытянув их в последовательность x_1,x_2,…,x_n,…, исчерпывающую все числа в полуинтервале [0,1). Выпишем элементы этой последовательности в указанном выше виде:
\begin{matrix}
x_1 & = & 0.a_1^1a_2^1a_3^1… a_k^1… \\[2mm]
x_2 & = & 0.a_1^2a_2^2a_3^2… a_k^2… \\[2mm]
x_3 & = & 0.a_1^3a_2^3a_3^3… a_k^3… \ 
\vdots && \vdots \ 
x_n & = & 0.a_1^na_2^na_3^n… a_k^n… \ 
\vdots && \vdots
\end{matrix}
Здесь a_k^n — цифра в k-м разряде после запятой числа x_n (не путать с n-й степенью числа a_k!). Все эти цифры вместе образуют этакую бесконечную таблицу (бесконечную матрицу, если хотите). Она может выглядеть как-нибудь так:
\begin{matrix}
0. 3141592653589793238462643383279 … \\
0.2 718281828459045235360287471352 … \\
0.16 18033988749894848204586834365 … \ 
0.141 4213562373095048801688724209 … \ 
0.1732 050807568877293527446341505 … \\
0.22360 67977499789696409173668731 … \\
0.120205 6903159594285399738161511 … \\
\vdots
\end{matrix}
Теперь построим вещественное число
x = 0.b_1b_2b_3… b_k…,  где  b_i=9−a_i^i .
То есть мы берём из первого числа x_1 первую цифру после запятой, вычитаем её из девяти и ставим результат первой цифрой числа x; потом берём из второго числа x_2 вторую цифру после запятой, вычитаем её из девяти, ставим результат второй цифрой числа x и так далее. В нашем примере у нас получится что-то вроде
\begin{array}{cl}
x_1= & 0.\mathbf{{\color{Red} 3}}141592653589793238462643383279… \ 
x_2= & 0.2\mathbf{{\color{Red} 7}}18281828459045235360287471352… \ 
x_3= & 0.16\mathbf{{\color{Red} 1}}8033988749894848204586834365… \ 
x_4= & 0.141\mathbf{{\color{Red} 4}}213562373095048801688724209… \ 
x_5= & 0.1732\mathbf{{\color{Red} 0}}50807568877293527446341505… \ 
x_6= & 0.22360\mathbf{{\color{Red} 6}}7977499789696409173668731… \ 
x_7= & 0.120205\mathbf{{\color{Red} 6}}903159594285399738161511… \\
 & \hphantom{0..}\vdots\hphantom{1202056}{\color{Red} \ddots} \\[4mm]
x = & 0.\mathbf{{\color{DarkBlue}6285933…}}
\end{array}
Это число гарантированно (не только в нашем примере, а вообще) лежит в интервале [0,1) и по нашему предположению должно быть занумеровано. Однако, это число не может быть среди занумерованных. В самом деле: пусть у него есть порядковый номер n. Но его n-я цифра после запятой по построению отличается от n-й цифры n-го числа: b_n=9−a_n^n≠ a_n^n! Полученное противоречие означает, что все вещественные числа полуинтервала [0,1) невозможно занумеровать.

Замечание. Я слукавил немножко, сказав, что x обязательно лежит в [0,1) только потому, что у него часть перед запятой нулевая. Дело в том, что вещественное число 0.999999… считается в математике равным единице (тому есть веские причины), так что оно не лежит в [0,1), хотя вполне может получиться в ходе нашего процесса, если на «диагонали» таблицы все нули. Впрочем, это означает, что число 0.111111… заведомо не занумеровано — в его представлении-то нет ни одного нуля. Можно обойти проблему и другим способом: вооружившись сакральным знанием о единице, мы можем просто повторить все наши рассуждения для отрезка [0,1] вместо полуинтервала. Части перед запятой у всех чисел в этом отрезке можно считать нулевыми, потому что 1=0.999999….

В связи с ненумеруемостью говорят, что полуинтервал [0,1) — множество мощности континуума.

4.3. Понятие мощности множества

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

Итак, пусть у нас есть два (необязательно бесконечных) множества A и B. Если нашёлся способ сопоставить каждому элементу a из A единственный элемент b из B (называемый при этом образом элемента a) так, что при этом каждый элемент b∈ B обязательно сопоставлен какому-то единственному элементу a∈ A (который называется прообразом элемента b), то этот способ называется взаимно-однозначным отображением или биекцией, а множества A и B называются эквивалентными или равномощными.

Это и есть ключевое определение в сравнении бесконечных множеств. Два множества мы положили равными по размеру, если их элементы можно связать друг с другом неким взаимно-однозначным преобразованием. Примером такого преобразования может быть наша нумерация элементов: занумеровав элементы какого-либо множества, мы определили взаимно-однозначное отображение между этим множеством и множеством натуральных чисел ℕ.

Теперь пусть два множества A и B оба равномощны какому-нибудь третьему множеству C. Давайте докажем, что в этом случае и между собой множества A и B равномощны.

Действительно, пусть каждому элементу a из A взаимно-однозначным отображением сопоставляется элемент из C, который мы обозначим как f(a), а каждому элементу c из C другим взаимно-однозначным отображением сопоставляется элемент из B, который мы обозначим как g(c). Теперь сопоставим каждому элементу a из A элемент g(f(a)). Если разобраться, то видно, что это корректная формула и что g(f(a))∈ B. Остаётся доказать, что это соответствие тоже взаимно-однозначное.

Для этого нужно доказать, что любому элементу b∈ B сопоставлен единственный элемент a∈ A. Убедимся в этом. Во-первых, ему сопоставлен единственный элемент c∈ C такой, что g(c)=b. Во-вторых, этому элементу c сопоставлен единственный элемент a'∈ A такой, что f(a')=c. Значит, и элементу b сопоставлен один-единственный только элемент a' такой, что g(f(a'))=b. (И, значит, a=a').

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

Кстати, это свойство можно переписать в таком виде (временно используя значок = для обозначения равномощности множеств):
A=C,  B=C \Rightarrow  A=B .
Не правда ли, такое свойство — то, чего мы всегда ожидаем от какой-либо операции сравнения?

Теперь можно перейти к понятию мощности множества. В случае конечного множества говорят, что его мощность равна числу элементов в нём. (Кстати, заметьте, что два конечных множества равномощны тогда и только тогда, когда в них одинаковое число элементов. Обязательно самостоятельно проверьте этот факт.) Про счётные множества говорят, что они имеют мощность счётного множества. Про вещественный полуинтервал и все множества, равномощные ему, говорят, что они имеют мощность континуума. Вообще мощность — это некоторая абстрактная характеристика множества, определяющая его размер. Для какого-то множества у неё может не быть конкретного имени, выражения или обозначения, но суть в том, что если два множества равномощны, то их мощность считается одинаковой. Для некоторых «популярных» мощностей существуют особые обозначения — например, мощность счётного множества обозначается через ℵ_0 (читается «алеф нуль»), а мощность континуума — через \mathfrak{c}.

Конкретные мощности конкретных множеств называют также кардинальными числами.

О мощностях развита обширная теория, в ней есть свои теоремы, неразрешённые гипотезы, своя арифметика, интересные соотношения и так далее. Возможно, где-то дальше я когда-нибудь затрону более глубокие стороны этого вопроса.

5. Указатель

© Aleph, 2016. При использовании материалов ссылка на math.siomax.ru обязательна.
Последняя редакция: , Т. Салуев.