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

не более чем счётное (конечное или счётное) объединение не более чем счётных множеств является не более чем счётным множеством

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

прямое произведение конечного числа не более чем счётных множеств — не более чем счётноесли к бесконечному множеству присоединить конечное или счётное, то получится множество, равномощное с исходным

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

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

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