Математика · объяснение и практика

Как взаимно однозначное соответствие доказывает равенство количеств

Как доказать равенство количеств без прямого перечисления, построить обратное соответствие и заметить потерянные или склеенные объекты при кодировании.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Множества, отношения и мощности · 10 тем

Главная мысль

Биекция сопоставляет каждому объекту одного набора ровно один объект другого без совпадения образов разных объектов и без пропусков целевого набора. Поэтому конечные количества равны.

Соответствие должно работать в обе стороны

Иногда считать сложные объекты удобнее после перевода в простые коды. Но сам факт выдачи кода каждому объекту ещё не гарантирует равенство количеств. Два разных объекта могут получить один код, либо некоторые коды вообще не соответствуют объектам. Биекция требует исключить обе потери: склеивание и незаполненные места.

Надёжный способ — описать прямое преобразование и обратное, а затем проверить оба возвращения. Если декодирование кода любого исходного объекта возвращает его самого, объекты не склеиваются. Если кодирование декодированного допустимого кода возвращает этот код, целевая область полностью покрыта. Так доказательство заменяет длинное перечисление вариантов.

Подмножество становится двоичной записью

Для подмножеств {1,2,3,4} запишем четыре бита: бит равен единице, когда соответствующее число выбрано. Например, {2,4} переходит в 0101. Обратно из записи читаем позиции единиц. Ни одна четырёхбитная строка не запрещена и никакие два подмножества не имеют одинакового набора единичных позиций. Поэтому их количества совпадают.

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

Пример

Почему путей из (0,0) в (3,2), состоящих из шагов вправо и вверх, ровно столько же, сколько двухэлементных подмножеств {1,2,3,4,5}?

Путь кодируем позициями двух шагов вверх среди пяти шагов. По выбранным позициям путь однозначно восстанавливается. Следовательно, путей C(5,2)=10; проверены оба направления соответствия.

Одинаковый размер не равен включению

Для конечных множеств биекция означает равенство численностей. Для бесконечных она становится определением равномощности. Натуральным 1,2,3,… соответствуют чётные положительные 2,4,6,… по правилу n↦2n. Каждый чётный положительный объект имеет единственного предка n. Поэтому собственная часть бесконечного набора может быть ему равномощна.

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

От чтения к действию

А теперь — вы

Двоичная строка длины 6 содержит ровно три единицы. С чем её естественно взаимно однозначно сопоставить?

Частые вопросы

Достаточно ли разных кодов для разных объектов?

Это доказывает отсутствие склеивания, но ещё нужно показать, что каждый целевой код используется. Иначе получена только инъекция.

Зачем явно задавать целевой набор?

От него зависит отсутствие пропусков. Одно и то же правило может быть биекцией на свой образ и не быть биекцией на более широкое множество.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться