Биекция

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

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

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

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

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

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

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

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

Определение

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

Состав

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

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

Мощность

If X and Y are finite sets, then there exists a bijection between the two sets X and Y if and only if X and Y have the same number of elements. Indeed, in axiomatic set theory, this is taken as the definition of "same number of elements" (equinumerosity), and generalising this definition to infinite sets leads to the concept of cardinal number, a way to distinguish the various sizes of infinite sets.

Properties

A function f: R → R is bijective if and only if its graph meets every horizontal and vertical line exactly once.
If X is a set, then the bijective functions from X to itself, together with the operation of functional composition (∘), form a group, the symmetric group of X, which is denoted variously by S(X), S_X, or X! (X factorial).
Bijections preserve cardinalities of sets: for a subset A of the domain with cardinality |A| and subset B of the codomain with cardinality |B|, one has the following equalities:
|f(A)| = |A| and |f⁻¹(B)| = |B|.
If X and Y are finite sets with the same cardinality, and f: X → Y, then the following are equivalent:
1. f is a bijection.
2. f is a surjection.
3. f is an injection.
For a finite set S, there is a bijection between the set of possible total orderings of the elements and the set of bijections from S to S. That is to say, the number of permutations of elements of S is the same as the number of total orderings of that set—namely, n!.

Category theory

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

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

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

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

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

Галерея

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

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

Примечания

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

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

Викискладе есть медиафайлы, связанные с биективностью .

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