Биекция, инъекция и сюръекция

	сюръективный	несюръективный
инъективный	биективный	только инъекционный
не- инъективный	только сюръективный	общий

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

Функция сопоставляет элементы из своего домена с элементами в своем кодомене. Дана функция $f\colon X\to Y$:

• Функция является инъективной или взаимно однозначной , если каждый элемент кодомена отображается не более чем одним элементом домена или, что то же самое, если отдельные элементы домена сопоставляются с различными элементами в кодомене. Инъективную функцию еще называют инъекцией . Условно:

$\forall x,x'\in X,f(x)=f(x')\implies x=x',$

или, что то же самое (с использованием логического транспонирования ),

$\forall x,x'\in X,x\neq x'\implies f(x)\neq f(x').$

• Функция является сюръективной или on , если каждый элемент кодомена отображается хотя бы одним элементом домена. То есть изображение и кодомен функции равны. Сюръективная функция — это сюръекция . Условно:

$\forall y\in Y,\exists x\in X{\text{ such that }}y=f(x).$

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

$\forall y\in Y,\exists !x\in X{\text{ such that }}y=f(x),$

где $\exists !x$ означает « существует ровно один x ».

• В любом случае (для любой функции) справедливо следующее:

$\forall x\in X,\exists !y\in Y{\text{ such that }}y=f(x).$

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

Инъекция

Основная статья: Инъективная функция

Дополнительная информация об обозначениях: Функция (математика) § Обозначения.

Инъективная композиция: вторая функция не обязательно должна быть инъективной.

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

Функция $f\colon X\to Y$ инъективен, если для всех $x,x'\in X$, $f(x)=f(x')\Rightarrow x=x'.$

Ниже приведены некоторые факты, связанные с инъекциями:

• Функция $f\colon X\to Y$ инъективен тогда и только тогда, когда $X$ пуст или $f$ слева обратима ; то есть есть функция $g\colon f(X)\to X$ такой, что $g\circ f=$ тождественная функция на X . Здесь, $f(X)$ это образ $f$.
• Поскольку каждая функция сюръективна, когда ее кодомен ограничен ее образом , каждая инъекция вызывает биекцию на ее образ. Точнее, каждая инъекция $f\colon X\to Y$ можно факторизовать как биекцию с последующим включением следующим образом. Позволять $f_{R}\colon X\rightarrow f(X)$ быть $f$ с кодоменом, ограниченным его изображением, и пусть $i\colon f(X)\to Y$ быть картой включения из $f(X)$ в $Y$. Затем $f=i\circ f_{R}$. Ниже приведена двойная факторизация для сюръекций.
• Состав двух инъекций – это опять же инъекция, но если $g\circ f$ инъективен, то можно только заключить, что $f$ инъективен (см. рисунок).
• Каждое вложение инъективно.

Сюръекция

Основная статья: Сюръективная функция

Сюръективная композиция: первая функция не обязательно должна быть сюръективной.

Функция является сюръективной или находящейся , если каждый элемент кодомена отображается хотя бы одним элементом домена . Другими словами, каждый элемент кодомена имеет непустой прообраз . Эквивалентно, функция сюръективна, если ее образ равен ее кодомену. Сюръективная функция — это сюръекция . Формальное определение следующее.

Функция $f\colon X\to Y$ сюръективно, если для всех $y\in Y$, есть $x\in X$ такой, что $f(x)=y.$

Ниже приведены некоторые факты, связанные с сюръективами:

• Функция $f\colon X\to Y$ сюръективен тогда и только тогда, когда он обратим справа, то есть тогда и только тогда, когда существует функция $g\colon Y\to X$ такой, что $f\circ g=$ функция идентификации включена $Y$. (Это утверждение эквивалентно аксиоме выбора .)
• Путем свертывания всех аргументов, отображаемых на заданное фиксированное изображение, каждая сюръекция вызывает биекцию из фактор-множества своей области определения в ее кодомен. Точнее, прообразы под f элементов образа $f$ являются классами эквивалентности отношения эквивалентности в области $f$, такие, что x и y эквивалентны тогда и только тогда, когда они имеют одинаковый образ при $f$. Поскольку все элементы любого из этих классов эквивалентности отображаются с помощью $f$на одном и том же элементе кодомена, это индуцирует биекцию между фактормножеством по этому отношению эквивалентности (множеством классов эквивалентности) и образом $f$ (который является его кодоменом, когда $f$ является сюръективным). Более того, f является композицией канонической проекции f на фактормножество и биекции между фактормножеством и кодоменой $f$.
• Композиция двух сюръекций снова является сюръекцией, но если $g\circ f$ сюръективно, то можно только заключить, что $g$ сюръективен (см. рисунок).

Биекция

Основная статья: Биективная функция

Биективная композиция: первая функция не обязательно должна быть сюръективной, а вторая функция не обязательно должна быть инъективной.

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

Функция $f\colon X\to Y$ является биективным, если для всех $y\in Y$, есть уникальный $x\in X$ такой, что $f(x)=y.$

Ниже приведены некоторые факты, связанные с биекциями:

• Функция $f\colon X\to Y$ биективен тогда и только тогда, когда он обратим, т. е. существует функция $g\colon Y\to X$ такой, что $g\circ f=$ тождественная функция на X и $f\circ g=$ функция идентификации включена $Y$. Эта функция сопоставляет каждое изображение с его уникальным прообразом.
• Композиция двух биекций снова является биекцией, но если $g\circ f$ является биекцией, то можно только заключить, что $f$ является инъективным и $g$ сюръективен (см. рисунок справа и замечания выше относительно инъекций и сюръекций).
• Биекции множества в себя образуют группу при композиции, называемую симметричной группой .

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

Предположим, что кто-то хочет определить, что означает, что два множества «имеют одинаковое количество элементов». Один из способов сделать это — сказать, что два множества «имеют одинаковое количество элементов» тогда и только тогда, когда все элементы одного набора могут быть соединены с элементами другого таким образом, что каждый элемент соединен с ровно один элемент. Соответственно, можно определить два набора как «имеющие одинаковое количество элементов» — если между ними существует взаимно однозначное соответствие. В этом случае говорят, что два множества имеют одинаковую мощность .

Аналогично можно сказать, что набор $X$ «имеет меньше или такое же количество элементов», как установлено $Y$, если есть инъекция из $X$ к $Y$; можно также сказать, что набор $X$ «имеет меньше, чем количество элементов» в наборе $Y$, если есть инъекция из $X$ к $Y$, но не биекция между $X$ и $Y$.

Примеры

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

Инъективный и сюръективный (биективный)

Функция идентичности id _X для каждого непустого множества X и, следовательно, конкретно $\mathbf {R} \to \mathbf {R} :x\mapsto x.$

$\mathbf {R} ^{+}\to \mathbf {R} ^{+}:x\mapsto x^{2}$, а значит, и его инверсия $\mathbf {R} ^{+}\to \mathbf {R} ^{+}:x\mapsto {\sqrt {x}}.$

Показательная функция $\exp \colon \mathbf {R} \to \mathbf {R} ^{+}:x\mapsto \mathrm {e} ^{x}$ (то есть экспоненциальная функция с ее кодоменом, ограниченным ее образом), а, следовательно, и ее обратный натуральный логарифм $\ln \colon \mathbf {R} ^{+}\to \mathbf {R} :x\mapsto \ln {x}.$

$\mathbf {R} \to \mathbf {R} :x\mapsto x^{3}$

Инъективный и несюръективный

Показательная функция $\exp \colon \mathbf {R} \to \mathbf {R} :x\mapsto \mathrm {e} ^{x}.$

Неинъективный и сюръективный

$\mathbf {R} \to \mathbf {R} :x\mapsto (x-1)x(x+1)=x^{3}-x.$

$\mathbf {R} \to [-1,1]:x\mapsto \sin(x).$

Неинъективный и несюръективный

$\mathbf {R} \to \mathbf {R} :x\mapsto \sin(x).$

$\mathbf {R} \to \mathbf {R} :x\mapsto x^{2}$

Свойства

• Для каждой функции f пусть X — подмножество области определения, а Y — подмножество области значений. Всегда X ⊆ f ⁻¹ ( ж ( X )) и ж ( ж ⁻¹ ( Y )) ⊆ Y , f ( X ) — образ X и где f ⁻¹ ( Y ) является прообразом Y ​ под f . Если f инъективен, то X = f ⁻¹ ( f ( X )) , и если f сюръективно, то f ( f ⁻¹ ( Y ) = Y. )
• Для каждой функции h : X → Y можно определить сюръекцию H : X → h ( X ) : x → h ( x ) и инъекцию I : h ( X ) → Y : y → y . Отсюда следует, что $h=I\circ H$. Это разложение как композиция сюръекции и инъекции единственно с точностью до изоморфизма в том смысле, что для такого разложения существует единственная биекция $\varphi :h(X)\to H(X)$ такой, что $H(x)=\varphi (h(x))$ и $I(\varphi (h(x)))=h(x)$ для каждого $x\in X.$

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

В категории множеств мономорфизмам инъекции, сюръекции и биекции соответствуют в точности , эпиморфизмам и изоморфизмам соответственно .

История

В Оксфордском словаре английского языка зафиксировано использование слова «инъекция» в качестве существительного С. Мак Лейном в «Бюллетене Американского математического общества» (1950), а слово «инъекция» в качестве прилагательного Эйленбергом и Стинродом в «Основах алгебраической топологии» (1952).

Однако только после того, как французская группа Бурбаки придумала инъективно-сюръективно-биъективную терминологию (как существительные, так и прилагательные), они получили широкое распространение.

См. также

• Тест горизонтальной линии
• Инъекционный модуль
• перестановка

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

• Самое раннее использование некоторых слов математики: статья «Инъекция», «Сюръекция» и «Биекция» содержит историю инъекции и связанных с ней терминов.