Всякое бесконечное множество содержит счетное подмножество

Доказательство. Пусть М – бесконечное множество. Выберем в нем произвольный элемент а₁. Поскольку М бесконечно, в нем найдется элемент а₂, отличный от а₁. Затем найдется а₃, отличный от а₁ и от а₂ и т. д. Продолжая этот процесс (который не может оборваться из-за нехватки элементов, т.к. М – бесконечно) полуим счетное подмножество А={a₁, a₂, …, a_n, …} множества М. Утверждение доказано. 1

Эквивалентность множеств

Сравнивая те или иные бесконечные множества с натуральным рядом, мы пришли к понятию счетного множества. Ясно, что множества логично сравнивать не только с множеством натуральных чисел; установление взаимно однозначного соответствия (биекции) позволяет сравнивать между собой любые два множества.

Определение: Два множества M и N, называют эквивалентными (обозначается M ~ N), если между их элементами можно установить взаимно однозначное соответствие.

Понятие эквивалентности применимо к любым множествам, как конечным, так и бесконечным. Два конечных множества эквивалентны между собой тогда когда число элементов у них одинаково.

Определение счетного множества можно сформулировать следующим образом:

Множество называется счетным, если оно эквивалентно множеству натуральных чисел.

Два множества, эквивалентные третьему, эквивалентны между собой, в частности, любые два счетных множества эквивалентны между собой.