Определение 2: Множества, обладающие одинаковой мощностью, называются равномощными (эквивалентными).

Два конечных множества будут равномощными, если в них содержится одинаковое число элементов. Если имеем дело с бесконечными множествами, то вопросы, связанные с мощностями, решаются путём установления соответствия между элементами этих множеств.

Возвращаясь, к примеру, можно отметить, что множество точек любого интервала и прямой – равномощны. Это означает, что на прямой и в интервале одинаковое количество точек. Кардинальное число для бесконечного множества – это число, обозначаемое специальным символом или буквой.

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

Теорема 1 (о мощности промежуточного множества): Пусть , причем , тогда .

Т.е. теорема утверждает, что, если мощности крайних множеств одинаковы, то и мощность среднего (промежуточного множества), будет такой же.

Доказательство: По условию теоремы, крайние множества равномощны, т. е. . Это значит, что можно установить взаимно однозначное соответствие между элементами этих множеств. Пусть при этом собственной части множества будет соответствовать собственная часть множества , которую назовем . Итак , , где . В свою очередь, множеству будет соответствовать множество , т.е. , где . Продолжая этот процесс неограниченно, получим последовательность множеств:

,

таких, что , , ,...

Кроме того, имеют место следующие эквивалентности:

,

,

.

Обозначим через общую часть множеств . Представим теперь множества и в виде сумм попарно непересекающихся частей:

,

.

Эти части эквивалентны, так как слагаемые первой и второй строки либо совпадают, либо эквивалентны. Что и требовалось доказать.

Теорема 2 (Кантора-Бернштейна): Если каждое из двух данных множеств эквивалентно некоторой части другого множества, то данные множества эквивалентны.

Доказательство: Пусть даны два множества и , причём и . Части и предполагаем собственными, т.к. иначе теорема очевидна. Поставим элементы множества во взаимно однозначное соответствие элементам множества и назовем , ту собственную часть множества , которая составлена из элементов, соответствующих элементам множества . Тогда , причем , , следовательно, используя свойство транзитивности отношения эквивалентности, имеем: . Согласно предыдущей теореме, , но , значит данные множества эквивалентны: . Теорема доказана.

Следствие: Таким образом, при сравнении двух бесконечных множеств возможны следующие случаи:

1) между элементами множеств можно установить взаимно однозначное соответствие, тогда данные множества равномощны;

2) между элементами множеств нельзя установить взаимно однозначное соответствие, но можно установить взаимно однозначное соответствие между элементами одного из них и собственной частью другого, тогда мощность одного множества больше мощности другого.

Далее рассмотрим наиболее распространенные виды множеств в зависимости от их мощности.

Теорема 3: Мощность множества всех подмножеств любого непустого множества больше, чем мощность данного множества .

Доказательство: Пусть дано непустое множество . Обозначим множество всех его подмножеств . Мы покажем, что не эквивалентно и что, кроме того, эквивалентно некоторой части множества . Будем считать, что во множество подмножеств вместе с другими входят несобственные подмножества множества . Докажем неэквивалентность множеств и . Доказательство проведём от противного. Предположим, что . Тогда каждому элементу соответствует некоторое подмножество того же множества , являющегося элементом множества . В данной ситуации возможны два случая. Либо элемент принадлежит тому подмножеству, которому тот соответствует, либо нет. Разобьём в соответствии с этим все элементы множества на две категории: «включенные» элементы и «не включенные». Обе категории не пусты. Так, элемент множества , соответствующий всему множеству как подмножеству, является включенным, а элемент множества , соответствующий его пустому подмножеству – не включённым. Рассмотрим подмножество множества , составленное из всех не включённых элементов. Пусть этому элементу множества соответствует некоторый элемент . Тогда окажется, что не может быть ни включенным, ни не включенным элементом. В самом деле, если он включенный, то , что невозможно т.к. составлено из не включенных элементов. Если - не включённый элемент, то он должен принадлежать , где собраны не включенные элементы, но тогда он оказывается включенным. Значит, и этот случай невозможен. Пришли к противоречию, которое возникло из-за неверного допущения. Тем самым доказано, что множества и не эквивалентны.

Доказательство того, что , где - собственное подмножество множества , очень просто. Достаточно взять в качестве все одноэлементные подмножества множества и поставить каждому из них в соответствие тот же элемент, из которого это одноэлементное множество состоит. Теорема доказана.

Следствие: Из доказанной теоремы следует, что для каждого кардинального числа существует большее кардинальное число.

В последующих рассуждениях важное место занимает множество натуральных чисел.