Введение

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

В математике сюръективная функция (также известная как сюръекция или отображение «на» /ɒnˈtuː/) — это функция f, для которой для каждого элемента y из кообласти функции существует по крайней мере один элемент x из области определения функции, такой что f(x) = y. Иными словами, для функции f : X → Y кообласть Y является образом области определения X. Не требуется, чтобы x был единственным; функция f может отображать один или несколько элементов X в один и тот же элемент Y. Термины «сюръективная», «инъективная» и «биективная» были введены Николасом Бурбаки, группой преимущественно французских математиков XX века, которые под этим псевдонимом написали серию книг, представляющих изложение современной высшей математики, начиная с 1935 года. Французское слово *sur* означает «над» или «выше» и связано с тем фактом, что образ области определения сюръективной функции полностью покрывает кообласть функции. Любая функция индуцирует сюръекцию, ограничивая свою кообласть образом своей области определения. Каждая сюръективная функция имеет правый обратный при условии аксиомы выбора, и каждая функция с правым обратным является сюръекцией по необходимости. Композиция сюръективных функций всегда сюръективна. Любую функцию можно разложить на сюръекцию и инъекцию.

Свойства

Функция является биективной тогда и только тогда, когда она одновременно сюръективна и инъективна. Если (что часто делают) функцию отождествляют с её графиком, то сюръективность является не свойством самой функции, а свойством отображения, то есть функции вместе с её кообластью. В отличие от инъективности, сюръективность нельзя определить, рассматривая только график функции.

Сурьекты как правые инвертируемые функции

Функция 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, но g не обязательно может "отменить" f. Любая функция, имеющая правый обратный, обязательно является сюръекцией. Утверждение о том, что любая сюръективная функция имеет правый обратный, эквивалентно аксиоме выбора. Если 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 является сюръективной тогда и только тогда, когда она правообратима: для любых функций 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 вместе имплицируют |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−1(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]~, и пусть fP : A/~ → B – это корректно определенная функция, заданная как fP([x]~) = f(x). Тогда f = fP ∘ P(~).

Набор сюжетов

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