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

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

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

Счётное множество является «простейшим» бесконечным множеством в следующем смысле: в любом бесконечном множестве найдётся счётное подмножество; всякое подмножество счётного множества конечно или счётно; если к бесконечному множеству присоединить конечное или счётное, то получится множество, равномощное с исходным.

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

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

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

Литература

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