Биекция

Переписка один на один

Биективная функция f : X → Y , где множество X равно {1, 2, 3, 4}, а множество Y равно {A, B, C, D}. Например, f (1) = D.

Биекция , биективная функция или взаимно однозначное соответствие между двумя математическими наборами — это функция , при которой каждый элемент второго набора ( кодомен ) отображается ровно в один элемент первого набора (домен ) . Эквивалентно, биекция — это такое отношение между двумя множествами, при котором каждый элемент любого набора соединен ровно с одним элементом другого набора.

Функция биективна тогда и только тогда, когда она обратима ; то есть функция является биективной тогда и только тогда, когда существует функция, обратная f , такая , что каждый из двух способов составления двух функций дает тождественную функцию : для каждого in и для каждого in ${\displaystyle f:X\to Y}$ ${\displaystyle g:Y\to X,}$ ${\displaystyle g(f(x))=x}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle f(g(y))=y}$ ${\displaystyle y}$ ${\displaystyle Y.}$

Например, умножение на два определяет биекцию целых чисел на четные числа , обратной функцией которой является деление на два .

Функция является биективной тогда и только тогда, когда она одновременно инъективна (или взаимно однозначна ) — это означает, что каждый элемент в кодомене отображается не более чем в один элемент области — и сюръективна (или на ) — это означает, что каждый элемент кодомена сопоставляется по крайней мере с одним элементом домена. Термин «однозначное соответствие» не следует путать с « однозначной функцией» .

Элементарная операция подсчета устанавливает взаимно однозначное соответствие некоторого конечного набора первым натуральным числам (1, 2, 3, ...) с точностью до количества элементов в подсчитанном наборе. Это приводит к тому, что два конечных множества имеют одинаковое число элементов тогда и только тогда, когда между ними существует взаимно однозначное соответствие. В более общем смысле говорят, что два множества имеют одинаковое кардинальное число , если между ними существует взаимно однозначное соответствие.

Биективная функция множества в себя также называется перестановкой [ ^1] , а совокупность всех перестановок множества образует его симметрическую группу .

Некоторые биекции с дополнительными свойствами получили конкретные имена, к которым относятся автоморфизмы , изоморфизмы , гомеоморфизмы , диффеоморфизмы , группы перестановок и большинство геометрических преобразований . Соответствия Галуа — это биекции между наборами математических объектов , очевидно, совершенно разной природы.

Определение

Чтобы бинарное отношение, соединяющее элементы множества X с элементами множества Y , было биекцией, должны выполняться четыре свойства:

1. каждый элемент X должен быть в паре хотя бы с одним элементом Y ,
2. ни один элемент X не может быть соединен более чем с одним элементом Y ,
3. каждый элемент Y должен быть в паре хотя бы с одним элементом X и
4. ни один элемент Y не может быть соединен более чем с одним элементом X.

Удовлетворение свойств (1) и (2) означает, что спаривание является функцией с областью определения X . Чаще всего свойства (1) и (2) записаны в виде одного утверждения: каждый элемент X соединен ровно с одним элементом Y . Функции, удовлетворяющие свойству (3), называются « на Y » и называются сюръективными (или сюръективными функциями ). Функции, удовлетворяющие свойству (4), называются « взаимно-однозначными функциями » и называются инъекциями (или инъективными функциями ). ^[2] Используя эту терминологию, биекция — это функция, которая является одновременно сюръекцией и инъекцией, или, другими словами, биекция — это функция, которая является одновременно «один к одному» и «на». ^[3]

Примеры

Состав бейсбольной или крикетной команды

Рассмотрим состав бейсбольной или крикетной команды (или любой список всех игроков любой спортивной команды, где каждый игрок занимает определенное место в составе). Набор X будет состоять из игроков команды (девятого размера в случае бейсбола), а набор Y будет позициями в порядке отбивания мяча (1-й, 2-й, 3-й и т. д.). «Пара» определяется следующим образом: В какой позиции в этом порядке находится игрок. Свойство (1) выполняется, поскольку каждый игрок находится где-то в списке. Свойство (2) выполняется, поскольку ни один игрок не бьет в двух (или более) позициях в порядке. Свойство (3) гласит, что для каждой позиции в порядке есть какой-то игрок, отбивающий мяч в этой позиции, а свойство (4) утверждает, что два или более игроков никогда не отбивают мяч на одной и той же позиции в списке.

Места и ученики класса

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

1. Все ученики сидели на своих местах (никто не стоял),
2. Ни один студент не сидел более чем на одном месте,
3. На каждом месте кто-то сидел (пустых мест не было), и
4. Ни на одном месте не было более одного студента.

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

Больше математических примеров

Биекция натуральных чисел в целые числа , которая отображает 2 n в − n и 2 n − 1 в n для n ≥ 0.

• Для любого набора X тождественная функция 1 _X : X → X , 1 _X ( x ) = x является биективной.
• Функция f : R → R , f ( x ) = 2 x + 1 является биективной, поскольку для каждого y существует единственный x = ( y − 1)/2 такой, что f ( x ) = y . В более общем смысле, любая линейная функция над действительными числами f : R → R , f ( x ) = ax + b (где a не равно нулю) является биекцией. Каждое действительное число y получается из действительного числа x = ( y − b )/ a (или в сочетании с ним) .
• Функция f : R → (−π/2, π/2), заданная формулой f ( x ) = arctan( x ), является биективной, поскольку каждое действительное число x сопряжено ровно с одним углом y в интервале (−π/ 2, π/2), так что tan( y ) = x (т. е. y = arctan( x )). Если бы кодобласть (−π/2, π/2) была увеличена и включала целое число, кратное π/2, то эта функция больше не была бы сюръективной, поскольку не существует действительного числа, которое можно было бы соединить в пару с кратное π/2 этой арктангенсной функции.
• Показательная функция g : R → R , g ( x ) = e ^x , не является биективной: например, в R не существует такого x, что g ( x ) = −1, что показывает, что g не находится на (сюръективном) . Однако, если кодобласть ограничена положительными действительными числами , то g будет биективным; ее обратная функция (см. ниже) — это функция натурального логарифма ln. ${\displaystyle \mathbb {R} ^{+}\equiv \left(0,\infty \right)}$
• Функция h : R → R ⁺ , h ( x ) = x ² не является биективной: например, h (−1) = h (1) = 1, показывая, что h не является взаимно однозначным (инъективным). Однако, если область определения ограничена , то h будет биективным; ее обратная функция — это функция положительного квадратного корня. ${\displaystyle \mathbb {R} _{0}^{+}\equiv \left[0,\infty \right)}$
• По теореме Шредера-Бернштейна для любых двух наборов X и Y и двух инъективных функций f : X → Y и g : Y → X существует биективная функция h : X → Y.

Инверсии

Биекция f с областью определения X (обозначаемая f : X → Y в функциональной записи ) также определяет обратное отношение, начинающееся в Y и идущее к X (путем поворота стрелок). Процесс «поворота стрелок» для произвольной функции, вообще говоря , не дает функции, но свойства (3) и (4) биекции говорят, что это обратное отношение представляет собой функцию с областью определения Y . Более того, свойства (1) и (2) тогда говорят, что эта обратная функция является сюръекцией и инъекцией, то есть обратная функция существует и также является биекцией. Функции, имеющие обратные функции, называются обратимыми . Функция обратима тогда и только тогда, когда она является биекцией.

В кратких математических обозначениях функция f : X → Y является биективной тогда и только тогда, когда она удовлетворяет условию

для каждого y в Y существует уникальный x в X с y = f ( x ).

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

Состав

Биекция, состоящая из инъекции (X → Y) и сюръекции (Y → Z).

Композиция двух биекций f : X → Y и g : Y → Z является биекцией, обратная которой определяется выражением is . ${\displaystyle g\,\circ \,f}$ ${\displaystyle g\,\circ \,f}$ ${\displaystyle (g\,\circ \,f)^{-1}\;=\;(f^{-1})\,\circ \,(g^{-1})}$

И наоборот, если композиция двух функций биективна, из этого следует только то, что f инъективна , а g сюръективна . ${\displaystyle g\,\circ \,f}$

Мощность

Если X и Y — конечные множества , то между двумя множествами X и Y существует взаимно однозначное соответствие тогда и только тогда, когда X и Y имеют одинаковое количество элементов. Действительно, в аксиоматической теории множеств это воспринимается как определение «одного и того же числа элементов» ( равномерность ), и обобщение этого определения на бесконечные множества приводит к понятию кардинального числа , способу различать различные размеры бесконечных множеств.

Характеристики

• Функция f : R → R является биективной тогда и только тогда, когда ее график пересекает каждую горизонтальную и вертикальную прямую ровно один раз.
• Если X — множество, то биективные функции из X в себя вместе с операцией функциональной композиции (∘) образуют группу , симметрическую группу X , _{которая} обозначается по-разному через S( X ), SX или ИКС ! ( Х- факториал ).
• Биекции сохраняют мощность множеств: для подмножества A области мощности | А | и подмножество B кодомена мощности | B |, имеют место следующие равенства:

  | ж ( А )| = | А | и | ж ^-1 ( Б )| = | Б |.

• Если X и Y — конечные множества одинаковой мощности и f : X → Y , то следующие условия эквивалентны:
  1. f — биекция.
  2. f — сюръекция .
  3. f — инъекция .
• Для конечного множества S существует биекция между множеством возможных полных упорядочений элементов и множеством биекций от S до S. Другими словами, количество перестановок элементов S такое же, как и количество полных упорядочений этого набора, а именно n !.

Теория категорий

Биекции - это в точности изоморфизмы в категории Множество множеств и функций множеств . Однако биекции не всегда являются изоморфизмами более сложных категорий. Например, в категории групп Grp морфизмы должны быть гомоморфизмами , поскольку они должны сохранять структуру группы, поэтому изоморфизмы являются групповыми изоморфизмами , которые являются биективными гомоморфизмами.

Обобщение на частичные функции

Понятие взаимно однозначного соответствия обобщается на частичные функции , где они называются частичными биекциями , хотя частичные биекции должны быть только инъективными. Причина этого ослабления состоит в том, что (собственная) частичная функция уже не определена для части своей области определения; таким образом, нет веской причины ограничивать ее обратную функцию полной , то есть определенной всюду в своей области определения. Набор всех частичных биекций на данном базовом наборе называется симметричной обратной полугруппой . ^[4]

Другой способ определить то же понятие — сказать, что частичная биекция из A в B — это любое отношение R (которое оказывается частичной функцией) со свойством, что R является графиком биекции f : A′ → B′. , где A’ — подмножество A , а B’ — подмножество B. ^[5]

Когда частичная биекция находится в одном и том же множестве, ее иногда называют частичным преобразованием «один к одному» . ^[6] Примером является преобразование Мёбиуса, просто определенное на комплексной плоскости, а не его завершение на расширенной комплексной плоскости. ^[7]

Галерея

• 
  Инъективная несюръективная функция (инъекция, а не биекция)
• 
  Инъективная сюръективная функция ( биекция )
• 
  Неинъективная сюръективная функция (сюръекция, а не биекция)
• 
  Неинъективная несюръективная функция (также не биекция)

Смотрите также

• Математический портал

• Теорема Акса – Гротендика
• Биекция, инъекция и сюръекция
• Биективная нумерация
• Биективное доказательство
• Теория категорий
• Многозначная функция

Примечания

1. Холл 1959, с. 3
2. Свойствам (1) и (2) также присвоены имена. Отношение, удовлетворяющее свойству (1), называется полным отношением , а отношение, удовлетворяющее (2), — однозначным отношением .
3. «Биекция, инъекция и сюръекция | Блестящая математическая и научная вики» . блестящий.орг . Проверено 7 декабря 2019 г.
4. Кристофер Холлингс (16 июля 2014 г.). Математика за железным занавесом: история алгебраической теории полугрупп. Американское математическое общество. п. 251. ИСБН 978-1-4704-1493-1.
5. Фрэнсис Борсо (1994). Справочник по категорической алгебре: Том 2, Категории и структуры. Издательство Кембриджского университета. п. 289. ИСБН 978-0-521-44179-7.
6. Пьер А. Грийе (1995). Полугруппы: введение в теорию структуры. ЦРК Пресс. п. 228. ИСБН 978-0-8247-9662-4.
7. Джон Микин (2007). «Группы и полугруппы: связи и контрасты». В CM Кэмпбелл; мистер Квик; Э. Ф. Робертсон; Г. К. Смит (ред.). Группы Сент-Эндрюс 2005 Том 2 . Издательство Кембриджского университета. п. 367. ИСБН 978-0-521-69470-4.препринт со ссылкой на Лоусона, М.В. (1998). «Обратный моноид Мёбиуса». Журнал алгебры . 200 (2): 428–438. дои : 10.1006/jabr.1997.7242 .

Рекомендации

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

• Холл, Маршалл младший (1959). Теория групп . Макмиллан.
• Вольф (1998). Доказательство, логика и гипотеза: набор инструментов математика . Фримен.
• Сундстрем (2003). Математическое рассуждение: написание и доказательство . Прентис-Холл.
• Смит; Эгген; Сент-Андре (2006). Переход к высшей математике (6-е изд.) . Томсон (Брукс/Коул).
• Шумахер (1996). Глава нулевая: Фундаментальные понятия абстрактной математики . Аддисон-Уэсли.
• О'Лири (2003). Структура доказательства: с логикой и теорией множеств . Прентис-Холл.
• Мораш. Мост к абстрактной математике . Случайный дом.
• Мэддокс (2002). Математическое мышление и письмо . Харкорт / Академическая пресса.
• Лэй (2001). Анализ с введением в доказательство . Прентис Холл.
• Гилберт; Ванстон (2005). Введение в математическое мышление . Пирсон Прентис-Холл.
• Флетчер; Пэтти. Основы высшей математики . PWS-Кент.
• Иглевич; Стойл. Введение в математические рассуждения . Макмиллан.
• Девлин, Кейт (2004). Множества, функции и логика: введение в абстрактную математику . Чепмен и Холл / CRC Press.
• Д'Анджело; Вест (2000). Математическое мышление: решение задач и доказательства . Прентис Холл.
• Купиллари (1989). Основные моменты доказательств . Уодсворт. ISBN 9780534103200.
• Связь. Введение в абстрактную математику . Брукс/Коул.
• Барнье; Фельдман (2000). Введение в высшую математику . Прентис Холл.
• Пепел. Букварь абстрактной математики . МАА.

Внешние ссылки

• «Биекция», Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Биекция». Математический мир .
• Самое раннее использование некоторых слов математики: статья об инъекциях, сюръекциях и биекциях содержит историю инъекций и связанных с ними терминов.