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

---

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

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

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

---