Коротко — биекция (взаимно однозначное соответствие) между двумя множествами A и B — это такое соответствие f: A → B, что
- для каждого a ∈ A существует ровно один f(a) ∈ B (т. е. f — функция), и
- f инъективна (разным a соответствуют разные f(a)) и сюръективна (для каждого b ∈ B существует a ∈ A с f(a)=b).
Эквивалентные формулировки: существует обратная функция f^{-1}: B → A; каждому элементу A соответствует ровно один элемент B и каждому элементу B — ровно один элемент A (то есть одно-к-одному и на-вовсю); или ребра между A и B образуют «совершенное паросочетание» (perfect matching).
Почему ваше сомнение обосновано. Фраза «у каждого элемента обоих множеств есть ровно одна стрелка к элементу противоположного множества» может быть истолкована неоднозначно. Если под ней понимают просто наличие двух функций f: A→B и g: B→A (каждый элемент имеет ровно один исходящий стрелочный образ), то из этого вовсе не следует биекция. Пример:
- A = {1,2}, B = {a}. Возьмём f(1)=a, f(2)=a и g(a)=1.
Тогда у каждого элемента слева (1 и 2) есть ровно одна стрелка в B, и у каждого элемента справа (a) есть ровно одна стрелка в A. Но множества имеют разные мощности (|A|=2, |B|=1), биекции нет.
Что действительно гарантирует равенство мощностей (и существование биекции):
- если есть функция f: A→B которая и инъективна, и сюръективна — это и есть биекция;
- если найдены инъекции в обе стороны (инъекция A→B и инъекция B→A), то по теореме Кантора–Шрёдера–Бернштейна существует биекция (в частности для конечных множеств это очевидно: |A|≤|B| и |B|≤|A| ⇒ |A|=|B|);
- если вы рисуете стрелки как несориентированный паросочетательный граф и требуете, чтобы каждая вершина имела степень ровно 1 (т. е. каждая точка слева соединена ровно с одной справа и наоборот), то это уже «совершенное паросочетание», и число элементов слева равно числу элементов справа (число ребер равно обеим мощностям).
В комбинаторике обычно фразу «каждому элементу слева соответствует ровно один элемент справа и наоборот» используют как краткую запись для «существует взаимно однозначное соответствие» — то есть авторы подразумевают и исходящую, и входящую уникальность (bijectivity). Но если трактовать буквально только исходящие стрелки с обеих сторон, то это недостаточно, как показан пример.