Каждому элементу первого множества должен соответствовать один и только один элемент второго множества, и наоборот. Это единственное правило, которому должны подчиняться биективные, то есть взаимно однозначные отображения.
На рисунке ниже мы также видим соответствия:
Однако они не удовлетворяют этому правилу.
Таким образом, Кантор определил простейшее понятие подсчета, а также ввел понятие кардинальности множества.
Если мы рассмотрим множества, между которыми можно установить биективное отображение, то увидим, что число элементов в этих множествах одинаково. Но если одно множество состоит из четырех элементов, а другое — из трех, между ними нельзя установить биективное отображение: какой-либо элемент остается без пары или какому-либо элементу будет сопоставлено сразу несколько элементов.
Кантор определил эквивалентность множеств следующим образом: «Кардинальность двух множеств одинакова, если между ними можно установить биективное (взаимно однозначное) отображение». О множествах с одинаковой кардинальностью говорят, что они являются равномощными, то есть имеют одинаковое число элементов.
Таким образом, если дано произвольное множество, например коробка цветных карандашей, которое мы обозначим А, и можно установить взаимно однозначное соответствие между множеством A и множеством N = {1, 2, 3, 4, 5, 6}, то говорят, что кардинальность А и N одинакова:
|A| = |N| = 6
Может показаться, что мы усложняем очевидное, но это впечатление обманчиво: новый логический аппарат позволил дать четкое определение бесконечному множеству.
Для этого сначала определим, что такое конечное множество. Непустое множество А (иными словами, содержащее как минимум один элемент) является конечным, если для некоторого числа n множество А имеет ту же кардинальность, что и множество {1, 2, 3, …, n}. Следовательно, n будет числом элементов множества A. В противном случае говорят, что множество А бесконечное.
Аналогично: множество А бесконечно, если существует собственное подмножество В множества А, имеющее ту же кардинальность, что и само А. В противном случае множество А является конечным.
На последнем определении стоит остановиться подробнее ввиду его чрезвычайной важности. Во-первых, следует пояснить, что понимается под собственным подмножеством. Это очень просто: если дано произвольное множество А, например {a, b, с, d}, его собственным подмножеством будет любое подмножество, которое можно составить из элементов А, при этом нельзя использовать их все. Примерами собственных подмножеств А будут:
{а} {а, Ь} {а, b, с} {а, с, d} {d} {b, с, d}.
В соответствии с вышесказанным кажется логичным, что между множеством и его собственным подмножеством нельзя установить взаимно однозначное соответствие: собственное подмножество всегда будет содержать меньше элементов, чем само множество.
Но существуют примеры, когда это не так. Рассмотрим 
— множество всех натуральных чисел и его собственное подмножество Р, образованное всеми четными числами. Очевидно, что между обоими множествами можно установить взаимно однозначное соответствие: для этого каждому натуральному числу п нужно поставить в соответствие это же число, умноженное на 2.
n —> 2n
В соответствии с этим
1 —> 2
2 —> 4
3 —> 6
…
Иными словами, каждому натуральному числу соответствует четное число и, напротив, каждому четному числу соответствует натуральное число. Это означает, что кардинальность этих множеств одинакова, и утверждение «существует столько же натуральных чисел, сколько четных» вовсе не парадокс, хотя оно явно противоречит интуиции. Таким образом, альтернативное определение бесконечного множества звучит так: множество является бесконечным, если между этим множеством и какой-либо из его частей (каким-либо его собственным подмножеством) можно установить взаимно однозначное соответствие.