Множество A равномощно множеству B, если существует биекция .
Любое множество, равномощное множеству всех натуральных чисел, называют счетным.
Мощность счетного множества обозначают (читается «алеф нуль»).
– мощность множества действительных чисел.
Пример.
Множество всех нечетных натуральных чисел счетно. Нумерацию можно задать так: ,
Теорема.
Любое подмножество счетного множества конечно или счетно.
Доказательство:
Пустое подмножество конечно по определению. Пусть М – счетное множество, а В – его некоторое непустое подмножество. Поскольку множество М счетно, можно считать, что
задана некоторая его нумерация. Следовательно, каждый элемент подмножества В имеет свой номер. Запишем номера элементов множества В в порядке возрастания:
Если среди них есть наибольший номер , то подмножество В конечно. В противном случае получим счетное подмножество нумерация которого установлена так: .
Если множество конечно или счетно, его называют не более чем счетным.
Теорема.
Объединение конечного и счетного множеств счетно.
