Биекция

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

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

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

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

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

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

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

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

Определение

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

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

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

Примеры

Состав бейсбольной

Рассмотрим состав бейсбольной или крикетной команды (или любой список всех игроков любой спортивной команды, где каждый игрок занимает определенное место в составе). Набор 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 этой арктангенсной функции.
• Показательная функция , г : р → R , г ( Икс ) знак равно е ^Икс нет x , не является биективным: например, в R такого , что g ( x ) = −1, что показывает, что g не является on (сюръективным). Однако, если кодомен ограничен положительными действительными числами $\mathbb {R} ^{+}\equiv \left(0,\infty \right)$, то g было бы биективным; ее обратная функция (см. ниже) — это функция натурального логарифма ln.
• Функция h : R → R ⁺ , час ( Икс ) знак равно Икс ² не является биективным: например, h (−1) = h (1) = 1, показывая, что h не является взаимно однозначным (инъективным). Однако если домен ограничен $\mathbb {R} _{0}^{+}\equiv \left[0,\infty \right)$, то h будет биективным; ее обратная функция — это функция положительного квадратного корня.
• По теореме Шредера-Бернштейна для любых двух наборов 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).

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

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

Кардинальность

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

Свойства

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

  | ж ( А )| = | А | и | ж ⁻¹ ( Б )| = | Б |.

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

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

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

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

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

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

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

Галерея

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

См. также

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

Ссылки

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

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

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

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