Соответствием между множествами A и B называют правило, по которому некоторым элементам A сопоставляются один или несколько элементов B (ученики школы и купленные ими билеты в театр).
Определение 4. Соответствие между A и B называется взаимно однозначным, если каждому элементу A сопоставлен ровно один элемент B и каждому элементу B — ровно один элемент A.
Примеры: сопоставление каждому ученику класса его месяца рождения — не взаимно однозначное (у многих один месяц, некоторые месяцы не заняты); движение, переводящее квадрат в равный ему квадрат, — взаимно однозначное соответствие их точек; правило n → 3n — взаимно однозначное соответствие между N и множеством натуральных чисел, кратных 3.
Определение 5. Множества A и B называются эквивалентными (равномощными), если между ними можно установить взаимно однозначное соответствие.
Конечные множества эквивалентны, только если в них поровну элементов. С бесконечными интереснее: N эквивалентно множеству чисел, кратных 3, хотя это его подмножество.
Пример 3. N и Z эквивалентны: сопоставим чётному n число n/2, нечётному n — число -(n - 1)/2: 1 → 0, 2 → 1, 3 → -1, 4 → 2, 5 → -2, … Каждое целое число получается ровно один раз.
Эквивалентные бесконечные множества содержат «одинаково много» элементов. Но не все бесконечные множества эквивалентны: например, R не эквивалентно Q — действительных чисел «больше» (об этом — в пункте о счётных и несчётных множествах).