Сюръективная функция

Математическая функция, такая что каждый выход имеет по крайней мере один вход

В математике сюръективная функция ( также известная как сюръекция или on function / ˈ ɒ n . t uː / ) — это функция f , такая что для каждого элемента y области определения функции существует по крайней мере один элемент x в области определения функции , такой что f ( x ) = y . Другими словами, для функции f  : X → Y область определения Y является образом области определения функции X . ^{[1] [2]} Не требуется, чтобы x был уникальным ; функция f может отображать один или несколько элементов X в один и тот же элемент Y .

Термин «сюръективный» и связанные с ним термины «инъективный» и «биективный» были введены Николя Бурбаки ^[3] [ ^{4] —} группой преимущественно французских математиков XX века , которые под этим псевдонимом написали серию книг, представляющих собой изложение современной продвинутой математики, начиная с 1935 года. Французское слово sur означает «над» или «выше» и относится к тому факту, что изображение области определения сюръективной функции полностью покрывает область определения функции.

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

Определение

Сюръективная функция — это функция , образ которой равен ее области определения . Эквивалентно, функция с областью определения и областью определения является сюръективной, если для каждого в существует хотя бы один в с . ^[1] Сюръекции иногда обозначаются двунаправленной стрелкой вправо ( U+ 21A0 ↠ ПРАВАЯ ДВУХНАПРАВЛЕННАЯ СТРЕЛКА ), ^[5] как в . ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle y}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle f(x)=y}$ ${\displaystyle f\colon X\twoheadrightarrow Y}$

Символично,

Если , то называется сюръективным, если ${\displaystyle f\colon X\rightarrow Y}$ ${\displaystyle f}$

${\displaystyle \forall y\in Y,\,\exists x\in X,\;\;f(x)=y}$. ^{[2] [6]}

Примеры

Несюръективная функция из области X в кодомен Y . Меньший желтый овал внутри Y является образом (также называемым диапазоном ) f . Эта функция не является сюръективной, поскольку изображение не заполняет всю кодомен. Другими словами, Y окрашивается в двухэтапный процесс: во-первых, для каждого x в X точка f ( x ) окрашивается в желтый цвет; во-вторых, все остальные точки в Y , которые не являются желтыми, окрашиваются в синий цвет. Функция f была бы сюръективной, только если бы не было синих точек.

• Для любого множества X функция тождества id _X на X является сюръективной.
• Функция f  : Z → {0, 1}, определяемая формулой f ( n ) = n mod 2 (то есть четные целые числа отображаются в 0, а нечетные целые числа — в 1), является сюръективной.
• Функция f  : R → R , определяемая формулой f ( x ) = 2 x + 1, является сюръективной (и даже биективной ), поскольку для каждого действительного числа y у нас есть x такой, что f ( x ) = y : таким подходящим x является ( y − 1)/2.
• Функция f  : R → R , определенная как f ( x ) = x ³ − 3 x, является сюръективной, поскольку прообраз любого действительного числа y является множеством решений кубического полиномиального уравнения x ³ − 3 x − y = 0, и каждый кубический полином с действительными коэффициентами имеет по крайней мере один действительный корень. Однако эта функция не является инъективной (и, следовательно, не биективной ), поскольку, например, прообраз y = 2 равен { x = −1, x = 2}. (На самом деле, прообраз этой функции для каждого y , −2 ≤ y ≤ 2 имеет более одного элемента.)
• Функция g  : R → R, определенная как g ( x ) = x ² , не является сюръективной, поскольку не существует действительного числа x такого, что x ² = −1 . Однако функция g  : R → R _≥0, определенная как g ( x ) = x ² (с ограниченной областью значений), является сюръективной, поскольку для каждого y в неотрицательной действительной области значений Y существует по крайней мере один x в действительной области значений X такой, что x ² = y .
• Функция натурального логарифма ln : (0, +∞) → R является сюръективной и даже биективной (отображение множества положительных действительных чисел во множество всех действительных чисел). Ее обратная функция, экспоненциальная функция , если она определена с множеством действительных чисел в качестве области определения и кодоменом, не является сюръективной (поскольку ее областью определения является множество положительных действительных чисел).
• Матричный экспоненциал не является сюръективным, если рассматривать его как отображение из пространства всех матриц размера n × n в себя. Однако его обычно определяют как отображение из пространства всех матриц размера n × n в общую линейную группу степени n (то есть группу всех обратимых матриц размера n × n ). Согласно этому определению, матричный экспоненциал является сюръективным для комплексных матриц, хотя все еще не сюръективным для действительных матриц.
• Проекция декартова произведения A × B на один из его сомножителей является сюръективной, если только другой сомножитель не пуст.
• В трехмерной видеоигре векторы проецируются на плоский двухмерный экран с помощью сюръективной функции.

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

Функция является биективной тогда и только тогда, когда она одновременно сюръективна и инъективна .

Если (как это часто делается) функция отождествляется с ее графиком , то сюръективность не является свойством самой функции, а скорее свойством отображения . [ ^7] То есть, функция вместе с ее областью значений. В отличие от инъективности, сюръективность не может быть считана из графика функции в одиночку.

Сюръекции как обратимые справа функции

Говорят, что функция g  : Y → X является правой обратной функцией функции f  : X → Y , если f ( g ( y )) = y для каждого y из Y ( g может быть отменена функцией f ). Другими словами, g является правой обратной функцией f , если композиция f o g функций g и f в этом порядке является тождественной функцией в области определения Y функции g . Функция g не обязательно должна быть полной обратной функцией f , поскольку композиция в другом порядке, g o f , может не быть тождественной функцией в области определения X функции f . Другими словами, f может отменить или « обратить » g , но не обязательно может быть ею отменена.

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

Если f  : X → Y сюръективно и B является подмножеством Y , то f ( f ⁻¹ ( B )) = B . Таким образом, B можно восстановить из его прообраза f ⁻¹ ( B ) .

Например, на первой иллюстрации в галерее есть некоторая функция g такая, что g ( C ) = 4. Есть также некоторая функция f такая, что f (4) = C . Неважно, что g не является уникальной (это также сработало бы, если бы g ( C ) равнялось 3); важно только то, что f «переворачивает» g .

Сюръекции как эпиморфизмы

Функция f  : X → Y является сюръективной тогда и только тогда, когда она является правосократимой : ^[8] для любых функций g , h  : Y → Z , всякий раз, когда g o f = h o f , то g = h . Это свойство формулируется в терминах функций и их композиции и может быть обобщено на более общее понятие морфизмов категории и их композиции. Правосократимые морфизмы называются эпиморфизмами . В частности, сюръективные функции являются в точности эпиморфизмами в категории множеств . Префикс epi происходит от греческого предлога ἐπί, означающего над , выше , на .

Любой морфизм с правым обратным является эпиморфизмом, но обратное в общем случае неверно. Правый обратный g морфизма f называется секцией f . Морфизм с правым обратным называется расщепляющим эпиморфизмом .

Сюръекции как бинарные отношения

Любую функцию с доменом X и кодоменом Y можно рассматривать как левостороннее и правостороннее уникальное бинарное отношение между X и Y , отождествляя ее с ее графиком функции . Сюръективная функция с доменом X и кодоменом Y тогда является бинарным отношением между X и Y , которое является правосторонне уникальным и одновременно левосторонне и правосторонне полным .

Мощность области сюръекции

Мощность области сюръективной функции больше или равна мощности ее кодомена: если f :  X → Y — сюръективная функция, то X имеет по крайней мере столько же элементов, сколько и Y , в смысле кардинальных чисел . (Доказательство апеллирует к аксиоме выбора , чтобы показать, что существует функция g  : Y → X, удовлетворяющая f ( g ( y )) = y для всех y из Y . Легко видеть, что g инъективна, поэтому формальное определение | Y | ≤ | X | выполняется.)

В частности, если X и Y конечны с одинаковым числом элементов, то f  : X → Y сюръективно тогда и только тогда, когда f инъективно .

Для двух множеств X и Y запись X ≤ ^* Y используется для того, чтобы сказать, что X пусто или что существует сюръекция из Y на X. Используя аксиому выбора, можно показать, что X ≤ ^* Y и Y ≤ ^* X вместе подразумевают, что | Y | = | X |, вариант теоремы Шредера–Бернштейна .

Состав и разложение

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

Любую функцию можно разложить на сюръекцию и инъекцию : Для любой функции h  : X → Z существуют сюръекция f  : X → Y и инъекция g  : Y → Z такие, что h = g o f . Чтобы увидеть это, определим Y как множество прообразов h ⁻¹ ( z ), где z принадлежит h ( X ) . Эти прообразы не пересекаются и разделяют X . Тогда f переносит каждый x в элемент Y , который его содержит, а g переносит каждый элемент Y в точку в Z , в которую h отправляет свои точки. Тогда f сюръективен, поскольку является проекционным отображением, а g инъективен по определению.

Индуцированная сюръекция и индуцированная биекция

Любая функция индуцирует сюръекцию, ограничивая свою область значений ее областью определения. Любая сюръективная функция индуцирует биекцию, определенную на частном ее области определения, путем свертывания всех аргументов, отображающихся на заданный фиксированный образ. Точнее, каждая сюръекция f  : A → B может быть факторизована как проекция, за которой следует биекция следующим образом. Пусть A /~ — классы эквивалентности A при следующем отношении эквивалентности : x ~ y тогда и только тогда, когда f ( x ) = f ( y ). Эквивалентно, A /~ — множество всех прообразов относительно f . Пусть P (~) : A → A /~ — отображение проекции , которое отправляет каждый x из A в его класс эквивалентности [ x ] _~ , и пусть f _P  : A /~ → B — корректно определенная функция, заданная как f _P ([ x ] _~ ) = f ( x ). Тогда f = f _P o P (~).

Множество сюръекций

При фиксированных конечных множествах A и B можно сформировать множество сюръекций A ↠ B. Мощность этого множества является одним из двенадцати аспектов двенадцатикратного пути Рота и задается формулой , где обозначает число Стерлинга второго рода . ${\textstyle |B|!{\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}$ ${\textstyle {\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}$

Галерея

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

• 
  Сюръективная композиция: первая функция не обязательно должна быть сюръективной.
• 
  Несюръективные функции в декартовой плоскости. Хотя некоторые части функции сюръективны, где элементы y в Y имеют значение x в X, такое что y = f ( x ), некоторые части не являются таковыми. Слева: В Y есть y ₀ , но нет x ₀ в X, такого что y ₀ = f ( x ₀ ). Справа: В Y есть y ₁ , y ₂ и y ₃ , но нет x ₁ , x ₂ и x ₃ в X, таких что y ₁ = f ( x ₁ ), y ₂ = f ( x ₂ ) и y ₃ = f ( x ₃ ).
• 
  Интерпретация сюръективных функций в декартовой плоскости, определяемая отображением f  : X → Y , где y = f ( x ), X = область определения функции, Y = область определения функции. Каждый элемент области отображается на из элемента в области по правилу f . Может быть несколько элементов области, которые отображаются на один и тот же элемент области. То есть, каждый y в Y отображается из элемента x в X , более чем один x может отображаться на один и тот же y . Слева: показана только одна область, что делает f сюръективной. Справа: показаны две возможные области X ₁ и X _{2 .}

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

• Биекция, инъекция и сюръекция
• Крышка (алгебра)
• Карта покрытия
• Перечисление
• Волоконный жгут
• Индекс установлен
• Раздел (теория категорий)

Ссылки

1. "Инъективный, сюръективный и биективный". www.mathsisfun.com . Получено 2019-12-07 .
2. "Биекция, инъекция и сюръекция | Brilliant Math & Science Wiki". brilliant.org . Получено 2019-12-07 .
3. Миллер, Джефф, «Инъекция, сюръекция и биекция», Ранние примеры использования некоторых слов математики, Tripod.
4. Mashaal, Maurice (2006). Бурбаки. Американское математическое общество. стр. 106. ISBN 978-0-8218-3967-6.
5. "Стрелки – Unicode" (PDF) . Получено 2013-05-11 .
6. Фарлоу, С. Дж. «Инъекции, сюръекции и биекции» (PDF) . math.umaine.edu . Получено 06.12.2019 .
7. TM Apostol (1981). Математический анализ . Addison-Wesley. стр. 35.
8. Голдблатт, Роберт (2006) [1984]. Топои, категориальный анализ логики (пересмотренное издание). Dover Publications . ISBN 978-0-486-45026-1. Получено 25.11.2009 .

Дальнейшее чтение

• Бурбаки, Н. (2004) [1968]. Теория множеств. Элементы математики . Т. 1. Springer. doi :10.1007/978-3-642-59309-3. ISBN 978-3-540-22525-6. LCCN  2004110815.