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

Функция такая, что каждый элемент имеет прообраз (математика)

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

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

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

Определение

Сюръективная функция — это функция , образ которой равен ее кодомену . Эквивалентно, функция с доменом и кодоменом является сюръективной, если для каждого in существует хотя бы один in с . ^[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 есть ( у - 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 ^{2 ,} не является сюръективной, поскольку не существует вещественного числа 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 на один из его факторов сюръективна, если только другой фактор не пуст.
• В 3D-видеоигре векторы проецируются на плоский 2D-экран с помощью сюръективной функции.

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

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

Если (как это часто делается) функция отождествляется со своим графиком , то сюръективность является не свойством самой функции, а скорее свойством отображения . ^[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 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 . Это свойство формулируется в терминах функций и их композиции и может быть обобщено до более общего понятия морфизмов категории и их композиции . Правосократительные морфизмы называются эпиморфизмами . В частности, сюръективные функции — это в точности эпиморфизмы в категории множеств . Префикс эпи происходит от греческого предлога ἐπί, означающего «над » , «над» , «на ».

Любой морфизм с правым обратным является эпиморфизмом, но обратное, вообще говоря, неверно. Правый обратный 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 вместе следует, что | Ю | = | 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 ([ Икс ] _~ ) знак равно ж ( Икс ). Тогда 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 → Y , где y = f ( x ), X = область определения функции, Y = диапазон функции. Каждый элемент диапазона сопоставляется с элементом домена по правилу f . Может существовать несколько элементов домена, которые сопоставляются с одним и тем же элементом диапазона. То есть каждый y в Y отображается из элемента x в X , более одного x может отображаться в один и тот же y . Слева: показан только один домен, что делает f сюръективным. Справа: показаны два возможных домена X ₁ и X _{2 .}

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

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

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

1. «Инъективное, сюръективное и биективное». www.mathsisfun.com . Проверено 7 декабря 2019 г.
2. «Биекция, инъекция и сюръекция | Блестящая математическая и научная вики» . блестящий.орг . Проверено 7 декабря 2019 г.
3. Миллер, Джефф, «Инъекция, сюръекция и биекция», «Самое раннее использование некоторых математических слов», штатив..
4. Машаал, Морис (2006). Бурбаки. Американское математическое соц. п. 106. ИСБН 978-0-8218-3967-6.
5. «Стрелки – Юникод» (PDF) . Проверено 11 мая 2013 г.
6. Фарлоу, С. Дж. «Инъекции, сюръекции и биекции» (PDF) . math.umaine.edu . Проверено 6 декабря 2019 г.
7. ТМ Апостол (1981). Математический анализ . Аддисон-Уэсли. п. 35.
8. Голдблатт, Роберт (2006) [1984]. Топои, Категориальный анализ логики (пересмотренная ред.). Дуврские публикации . ISBN 978-0-486-45026-1. Проверено 25 ноября 2009 г.

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

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