Счётное множество
Шаблон:Не путать Счётное множество — бесконечное множество, элементы которого возможно пронумеровать всеми натуральными числами. Более формально: множество <math>X</math> является счётным, если существует биекция со множеством натуральных чисел: <math>X\leftrightarrow \N</math>, другими словами, счётное множество — это множество, равномощное множеству натуральных чисел. В иерархии алефов мощность счётного множества обозначается <math>\alef_0</math> («алеф-нуль»).
Счётное множество является «простейшим» бесконечным множеством в следующем смысле: в любом бесконечном множестве найдётся счётное подмножество — если выбирать элементы из бесконечного множества и сопоставлять им числа <math>1,\,2,\,3,\,\ldots</math>, то для всякого натурального <math>n</math> в нём найдётся элемент для сопоставления с числом <math>n+1</math>, откуда по принципу индукции выбрать подмножество, взаимно-однозначно соответствующее <math>\N</math>.
Шаблон:ЯкорьИногда к счётным множествам относят также и конечные множества; в русской математической литературе такие множества чаще называют не более чем счётными или разве что счётными<ref>Шаблон:Книга</ref>. Всякое подмножество счётного множества конечно или счётно — не более чем счётно.
Счётными являются множества натуральных чисел <math>\N</math>, целых чисел <math>\Z</math>, рациональных чисел <math>\Q</math>, алгебраических чисел <math>\mathbb A</math>. Счётными являются объекты, получающиеся в результате рекурсивных процедур, в частности, таковы вычислимые числа, арифметические числа (как следствие, счётно и кольцо периодов, поскольку каждый период является вычислимым). Счётны множество всех конечных слов над счётным алфавитом и множество всех слов над конечным алфавитом. Любые объекты, которые можно определить со взаимно-однозначным сопоставлением со счётным множеством — счётны, например: любое бесконечное семейство непересекающихся открытых интервалов на вещественной оси; множество всех прямых на плоскости, каждая из которых содержит хотя бы две точки с рациональными координатами; любое бесконечное множество точек на плоскости, все попарные расстояния между элементами которого рациональны. Обширность класса счётных множеств — следствие свойств в условиях бесконечностиШаблон:Переход, позволяющих установить взаимно-однозначное соответствие, которое было бы невозможно в конечных случаях; одной из известных демонстраций таких возможностей является парадокс «Гранд-отель».
Несчётное множество — такое бесконечное множество, которое не является счётным, таковы, в частности, множества вещественных чисел <math>\R</math>, комплексных чисел <math>\Complex</math>, кватернионов <math>\mathbb H</math>, чисел Кэли <math>\mathbb O</math>. Таким образом, любое множество можно назвать либо конечным, либо счётным, либо несчётным.
Свойства
Не более, чем счётное объединение не более чем счётных множеств является не более чем счётным множеством; в случае произвольного бесконечного объединения указанное правило неприменимо. Декартово произведение конечного числа не более чем счётных множеств — не более чем счётно. Если к бесконечному множеству присоединить конечное или счётное, то получится множество, равномощное с исходнымШаблон:Sfn.
Множество всех конечных подмножеств счётного множества счётно. Множество конечных подмножеств из <math>n</math> элементов счётно, так как оно подмножество декартова произведения <math>n</math> исходных множеств. Множество же всех конечных подмножеств является объединением конечных подмножеств с определённым числом элементов (коих счётное число), то есть счётно.
Однако множество всех подмножеств счётного множества континуально, и счётным не является.