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

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

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

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

Иногда к счётным множествам относят также и конечные множества; в русской математической литературе такие множества чаще называют не более чем счётными или разве что счётными^[1]. Всякое подмножество счётного множества конечно или счётно — не более чем счётно.

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

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

Свойства

Не более, чем счётное объединение не более чем счётных множеств является не более чем счётным множеством; в случае произвольного бесконечного объединения указанное правило неприменимо. Декартово произведение конечного числа не более чем счётных множеств — не более чем счётно. Если к бесконечному множеству присоединить конечное или счётное, то получится множество, равномощное с исходным^[2].

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

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