Счётное множество

Не следует путать с перечислимым множеством.

Счётное множество — бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество $X$ является счётным, если существует биекция со множеством натуральных чисел: $X\leftrightarrow \mathbb {N}$, другими словами, счётное множество — это множество, равномощное множеству натуральных чисел. В иерархии алефов мощность счётного множества обозначается $\aleph _{0}$ («алеф-нуль»).

Свойства

Счётное множество является «простейшим» бесконечным множеством в следующем смысле: в любом бесконечном множестве найдётся счётное подмножество. Действительно, станем наугад выбирать элементы из бесконечного множества и сопоставлять им числа $1,\,2,\,3,\,\ldots$ Так как множество бесконечно, для всякого натурального $n$ в нём найдётся элемент для сопоставления с числом $n+1$, откуда по принципу индукции, построенное подмножество будет биективно с $\mathbb {N}$.

Кроме этого, всякое подмножество счётного множества конечно или счётно (не более чем счётно). Занумеруем элементы исходного множества натуральными числами, что возможно, так как оно счётно. Для каждого элемента известно, лежит оно в нашем подмножестве, или нет. Перебирая такие по порядку, станем, если очередной элемент не лежит в подмножестве — пропускать его; если лежит — приписывать к нему следующий номер (нумерацию начнём с $1$). По принципу индукции, подмножество будет равномощно $\mathbb {N}$, если не окажется конечным. Отметим, что перебирая по порядку, среди уже рассмотренных элементов мы никакой не упустили.

Также, не более чем счётное (конечное или счётное) объединение не более чем счётных множеств является не более чем счётным множеством. Занумеруем элементы объединяемых множеств (установим биекцию с $\mathbb {N}$). Если исходных множеств $A,\,B,\,C,\,\ldots$ конечное число $n$, элементы $S$ — их объединения станем нумеровать: $s_{1}=a_{1},\;s_{2}=b_{1},\;\ldots ,\;s_{n+1}=a_{2},\;s_{n+2}=b_{2},\;\ldots$ Нетрудно видеть из индукции, что установлена биекция с $\mathbb {N}$. В случае бесконечного объединения, указанное правило неприменимо, однако схожая нумерация возможна. Наглядно её можно представить следующим образом (дальнейший вывод, впрочем, можно формализовать): выпишем элементы каждого множества (упорядоченные по номерам) в столбик. Составим из таких таблицу, столбцы которой определяют каждое множество, включённое в объединение, а строки — определённые номера каждого из них. С левого верхнего угла станем змейкой обходить всю таблицу, нумеруя каждую клеточку на пути. По индукции мы обойдём всю таблицу и полученное объединение окажется счётным. Вообще говоря, саму таблицу придётся «строить» той же змейкой, поскольку она бесконечна. Элементы конечных же множеств всегда можно приписать сначала, тем самым сдвинув нумерацию на какое-то число.

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

Наконец, если к бесконечному множеству присоединить конечное или счётное, то получится множество, равномощное с исходным. Справедливость утверждения легко показать, если выбрать в исходном множестве $A$ счётное подмножество $B$. Таким образом, $A=(A\setminus B)\cup B\;\leftrightarrow (A\setminus B)\cup \mathbb {N}$. Присоединение к $B$ не более чем счётного множества не меняет его мощности, таким образом для не более чем счётного множества $C$ справедливо: $A\cup C=(A\setminus B)\cup (B\cup C)\;\leftrightarrow (A\setminus B)\cup \mathbb {N} \;\leftrightarrow A$.

Отметим, что множество всех конечных подмножеств счётного множества счётно. Множество конечных подмножеств из $n$ элементов счётно, так как оно подмножество декартова произведения $n$ исходных множеств. Множество же всех конечных подмножеств является объединением конечных подмножеств с определённым числом элементов (коих счётное число), то есть счётно.

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

Примеры

Счётными являются множества натуральных чисел $\mathbb {N}$, целых чисел $\mathbb {Z}$, рациональных чисел $\mathbb {Q}$, алгебраических чисел $\mathbb {A}$. Счётными являются объекты, получающиеся в результате рекурсивных процедур, в частности, таковы вычислимые числа, арифметические числа (как следствие, счётно и кольцо периодов, поскольку каждый период является вычислимым). Счётны множество всех конечных слов над счётным алфавитом и множество всех слов над конечным алфавитом. Любые объекты, которые можно определить со взаимно-однозначным сопоставлением со счётным множеством — счётны, например: любое бесконечное семейство непересекающихся открытых интервалов на вещественной оси; множество всех прямых на плоскости, каждая из которых содержит хотя бы две точки с рациональными координатами; любое бесконечное множество точек на плоскости, все попарные расстояния между элементами которого рациональны.

Несчётное множество — такое бесконечное множество, которое не является счётным, таковы, в частности, множества вещественных чисел $\mathbb {R}$, комплексных чисел $\mathbb {C}$, кватернионов $\mathbb {H}$, чисел Кэли $\mathbb {O}$. Таким образом, любое множество можно назвать либо конечным, либо счётным, либо несчётным.

Интересные факты

Основная статья: Парадокс «Гранд-отель»

На первый взгляд кажется невозможным установить взаимно-однозначное соответствие между, скажем $\mathbb {N}$ и $\mathbb {Z}$, ведь элементов второго множества, казалось бы, вдвое больше. Но здесь мы имеем дело с нашим восприятием понятия бесконечности, как чего-то не имеющего конца. Попытаться воспринять этот факт можно на следующем, абсурдном в некотором смысле, примере.

Представим, для заседания галактического совета построили гостиницу с бесконечным числом номеров и так случилось, что все номера оказались заняты. В этот момент прилетело $n$ дипломатов, которых требуется расселить. Поскольку номеров в гостинице и самих проживающих счётное число, предложим следующую стратегию по расселению новоприбывших. Переселим гостей из $1$-го номера в $(n+1)$-ый, проживающих $2$-го в $(n+2)$-й, и далее по порядку. В освободившиеся первые $n$ номеров, собственно, и поселим тех, кто прилетел. Гостиница, как была занята полностью, таковой, впрочем, и останется. Как же так, свободных мест, казалось бы, не было. Противоречие обнаруживается в представлении бесконечности, как некоторой конечности. Однако бесконечность характеризуется именно отсутствием своего конца, иначе говоря, бесконечность с добавлением конца, суть та же в точности бесконечность.

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

Литература

• Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.