Инъекция биекция сюръекция примеры: Дискретная математика, комбинаторика, теория чисел

Содержание

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

Отношение называется функцией или отображением из множества А в множество В, если и из (x,y₁) є f, (x,y₂) є f следует y₁=y₂. Если вместо выполняется , то f называется частичной функцией. Функция f из А в В обозначается через или . Если (x,y) є f, то пишем y=f(x) или . Функция называется разнозначной инъективной (инъекцией) или 1-1 функцией если из условия, что выполняется х₁≠х₂, следует y₁≠y₂. Функция называется функцией из А на В или сюръекцией, если . Функция называется взаимно однозначным соответствием между множествами А и В или биекцией, если она инъективна и сюръективна одновременно.

Биекция называется подстановкой.

Утверждения:

Если , , то
Если , то
Если f и g — инъекции, то f•g – инъекция.

Доказательство: Предположим противное, т.е. найдутся элементы x₁, x₂, y такие, что х₁≠х₂, (x₁,y) є f•g и (x₂,y) є f•g, т.е. g(f(x₁))=y=g(f(x₂)). В силу разнозначности f имеем f(x₁)≠f(x₂). Отсюда в силу разнозначности g получаем g(f(x₁))≠g(f(x₂)), а это противоречит предположению.

Если f,g – сюръекции, то f•g – сюръекция

Доказательство: Нужно доказать, что для любого с существует а такое, что f•g(a)=c. Т.к. g – сюръекция, то существует b, для которого g(b)=c, а т.к. f – сюръекция, то для любого b существует а такое, что f(a)=b. Тогда f•g(a)=g(f(a))=c

Если f и g – биекции, то f•g – биекция

Если , то

Функция называется последовательностью. Её можно представить в виде f(0)=b₀, f(1)=b₁,…, f(n)=b_n.

Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.

Два подхода к определению множества натуральных чисел:

Конструктивный.

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

Положим по определению . Множества 0, 1, 2,… называются натуральными числами. Объединение этих чисел N={0, 1, 2,…, n,…} называется множеством натуральных чисел.

Замечание: А^В – множество всех функций из В в А. Если В=n={0,1,2…,n-1}, A=2={0,1}, то А^В=2ⁿ.

Аксиоматический подход.

Рассмотрим аксиоматику Дедекинда Пеано:

Пусть имеется некоторое множество N, в котором выбран элемент 0 и функция, которая элементу n из N ставит в соответствие элемент n’ из N, называемый непосредственно следующим (элемент n’ играет роль числа n+1).

Множество N называется множеством натуральных чисел, если система <N,0,’> удовлетворяет аксиомам:

— для любого m≠0 найдется n из N такой, что n’=m.

— для любых m,n из N, если m’=n’, то m=n.

— n’≠0 для любого n из N.

— на множестве N выполняется аксиома математической индукции.

Принцип (аксиома) математической индукции:

Для любого свойства Р (унарного отношения на множестве N), если Р выполняется на элементе 0 (т.е. 0 обладает свойством Р), и для любого n из N из выполнимости Р на элементе n следует выполнимость Р на элементе n’, то свойство Р выполняется на любом элементе n из N.

или или

Иногда удается установить только выполнение Р(к) для некоторого к>0 и свойство Р(n)=>Р(n+1) для всех n≥к:

Принцип полной индукции:

Если для всякого n из N из предположения, что P(k) верно при любом натуральном k<n, следует, что P(k) верно также при k=n, то P(n) верно при любом натуральном n:

Биективная функция

В математике биективная функция или биекция — это функция f : A → B, которая является одновременно инъекцией и сюръекцией. Это означает: для каждого элемента b в кодомене

B существует ровно один элемент a в домене A такой, что f(a)=b. Другое название биекции — соответствие 1-1.

Термин биекция и связанные с ним термины сюръекция и инъекция были введены Николасом Бурбаки. В 1930-х годах он и группа других математиков опубликовали серию книг по современной высшей математике.

Основные свойства

Формально:

f : A → B {\displaystyle f:A\rightarrow B} является биективной функцией, если ∀ b ∈ B {\displaystyle \forall b\in B} существует единственное a ∈ A {\displaystyle a\in A} такое, что f ( a ) = b . {\displaystyle f(a)=b\,. }

Элемент b {\displaystyle b} называется образом элемента a {\displaystyle a} .

Формальное определение означает: Каждый элемент кодомена B является образом ровно одного элемента в домене A.

Элемент a {\displaystyle a} называется пред-образом элемента b {\displaystyle b} .

Формальное определение означает: Каждый элемент кодомена B имеет ровно один преобраз в домене A.

Примечание: Суръекция означает минимум одно предварительное изображение. Инъекция означает максимум один предварительный образ. Таким образом, биекция означает ровно один предварительный образ.

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

Кардинальность — это количество элементов в множестве. Кардинальность множества A={X,Y,Z,W} равна 4. Мы пишем #A=4.

Определение: Два множества A и B имеют одинаковую кардинальность, если между ними существует биекция. Таким образом, #A=#B означает, что существует биекция из A в B.

Биекции и обратные функции

Биекции инвертируются путем перестановки стрелок. Новая функция называется обратной функцией.

Формально: Пусть f : A → B — биекция. Обратная функция g : B → A определяется следующим образом: если f(a)=b, то g(b)=a. {-1}={\frac {1}{x}}} обозначает обратное значение числа x.

Примеры

Элементарные функции

Пусть f(x):ℝ→ℝ — вещественная функция y=f(x) от вещественного аргумента x. (Это означает, что и вход, и выход — числа).

Графическое значение: Функция f является биекцией, если каждая горизонтальная линия пересекает график f ровно в одной точке.
Алгебраический смысл: Функция f является биекцией, если для каждого действительного числа y_o можно найти хотя бы одно действительное число x_o такое, что y_o =f(x_o ) и если f(x_o )=f(x₁ ) означает x_o =x₁ .

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

Пример: Линейная функция наклонной линии является биекцией. То есть y=ax+b, где a≠0 — биекция.

Обсуждение: Каждая горизонтальная прямая пересекает наклонную прямую ровно в одной точке (доказательства см. в разделах «Сюръекция» и «Инъекция»). Изображение 1.

Пример: Полиномиальная функция третьей степени: f(x)=x³ является биекцией. Изображение 2 и изображение 5 — тонкая желтая кривая. Обратной функцией является функция кубического корня f(x)= ∛x, и она также является биекцией f(x):ℝ→ℝ. Изображение 5: толстая зеленая кривая.

Пример: Квадратичная функция f(x) = x²не является биекцией (из ℝ→ℝ). Изображение 3. Это не сюръекция. Это не инъекция. Однако мы можем ограничить его область и кодомен множеством неотрицательных чисел (0,+∞), чтобы получить (инвертируемую) биекцию (см. примеры ниже).

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

домен
функциональный аппарат
кодомен

Пример: Предположим, что наш автомат функций имеет вид f(x)=x².

Эта машина и domain=ℝ и codomain=ℝ не является сюръекцией и не является инъекцией. Однако,
этот же автомат и домен=[0,+∞) и кодомен=[0,+∞) является одновременно сюръекцией и инъекцией и, следовательно, биекцией.

Биекции и их инверсии

Пусть f(x):A→B, где A и B — подмножества ℝ.

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

Графики обратных функций симметричны относительно линии y=x.

{x}\,,\,\,\,a>1}.

является биекцией. Изображение 4: тонкая желтая кривая (a=10).

Пример: Основание логарифмической функции a определено на ограниченной области (0,+∞) и кодомене ℝ.

f ( x ) : ( 0 , + ∞ ) → R {\displaystyle f(x):(0,+\infty )\,\,\rightarrow \,\,\,\mathbf {R} } определяется f ( x ) = log a x , a > 1 {\displaystyle f(x)=\log _{a}x\,,\,\,\,a>1}

является биекцией, определяемой как обратная функция экспоненциальной функции: a^x . Изображение 4: толстая зеленая кривая (a=10).

Биекция: каждая вертикальная линия (в домене) и каждая горизонтальная линия (в кодомене) пересекают ровно одну точку графа.

1. Биекция. Все наклонные прямые являются биекциями f(x):ℝ→ℝ.

2. Биекция. f(x):ℝ→ℝ. f(x)=x³.

3. Не является биекцией. f(x):ℝ→ℝ. f(x)=x² не является сюръекцией. Это не инъекция.

4. Биекции. f(x):ℝ→ (0,+∞). f(x)=10^x (тонкий желтый) и ее обратная f(x):(0,+∞)→ℝ. f(x)=log₁₀x (толстый зеленый).

5. Биекции. f(x):ℝ→ℝ. f(x)=x³ (тонкий желтый) и его обратная f(x)=∛x (толстый зеленый).

6. Биекции. f(x):[0,+∞)→[0,+∞). f(x)=x² (тонкий желтый) и его обратная f(x)=√x (толстый зеленый).

комбинаторика — Разница между сюръекциями, инъекциями и биекциями

спросил 5 лет, 2 месяца назад

Изменено 5 лет, 2 месяца назад

Просмотрено 2к раз

$\begingroup$

Меня немного смущают определения этих разных типов функций:

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

Но меня немного смущает разница между инъекцией и биекцией. Инъекция отображает элемент x в

не более чем один y, а биекция отображает элемент x в ровно один y. Означает ли это, что инъекция может иметь элемент x, который не отображается ни в один элемент y, тогда как биекция всегда имеет ровно один сопоставление?

Значит ли это, что все биекции — инъекции, а все инъекции и биекции — сюръекции? Или функция может быть только одной из трех?

Любая помощь?

комбинаторика
теория чисел
функции
дискретная математика

$\endgroup$

$\begingroup$

означает ли это, что все биекции являются инъекциями

Все биекции обе инъекции и сюръекции.

и все инъекции и биекции являются сюръекциями?

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

Или функция может быть только одной из трех?

Пусть $\mathbb{N}_{0} = \mathbb{N} \cup \{0\}\,$, и возьмем, например, функцию абсолютного значения $f(x)=|x|\,$ :

, если определено как $f : \mathbb{N}_0 \to \mathbb{N}_0\,$, это биекция (и, следовательно, и инъекция, и сюръекция), поскольку это действительно тождественная функция на $\mathbb{N}_0$
, если определено как $f : \mathbb{N}_0 \to \mathbb{Z}\,$, это инъекция, но не сюръекция, поскольку, например, нет $x \in \mathbb{N}_0$ такой, что $f(x)=-1 \in \mathbb{Z}$
, если определено как $f : \mathbb{Z} \to \mathbb{N}_0\,$, это сюръекция, но не инъекция, поскольку, например, $-1 \ne 1$, но $f(-1) =f(1)=1$

$\endgroup$

$\begingroup$

Вы используете «карты в» наоборот. Мы имеем дело с функциями, которые отображают из X в Y.

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

Внедрение — это функция, в которой каждый элемент Y сопоставляется с не более чем одним элементом X.

Биекция — это функция, в которой каждый элемент Y отображается из ровно в один элемент X. Должно быть ясно, что «биекция» — это просто еще одно слово для обозначения инъекции, которая также является сюръекцией.

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

$\endgroup$

$\begingroup$

Дополнение к ответам выше, есть еще один способ их различать, когда множества счетные (указываю это по тегу дискретный ):

Пусть $A$,$B$ — счетные множества и $f: A \to B$ — функция. Тогда

Если $f$ является инъекцией, мы должны иметь $|A| \le |B|$ (необходимое условие).
Если $f$ — сюръекция, мы должны иметь $|A| \ge |B|$ (необходимое условие).
Если $f$ биекция, мы должны иметь $|A| = |B|$ (необходимое условие).

Достаточные условия выводятся из определений:

$f$ является инъекцией тогда и только тогда, когда для каждого $b \in B$ существует не более одного соответствующего элемента $a \in A$ с $f(a) = b$ (означает, что может быть элементы в $B$, которые не совпадают с элементом в $A$).
$f$ является сюръекцией тогда и только тогда, когда для каждого $b \in B$ существует по крайней мере один соответствующий элемент $a \in A$ с $f(a) = b$ (означает, что может существовать элементы в $B$, которые соответствуют более чем одному элементу в $A$).
$f$ является биекцией тогда и только тогда, когда $f$ является инъекцией и сюръекцией, то есть для каждого $b \in B$ существует ровно одного соответствующего элемента $a \in A$ с $ f(a) = b$ (означает, что для каждого $a \in A$ значение $f(a)$ уникально ).

$\endgroup$

Инъекция, Сюръекция, Биекция | Меньше лакун

18 ноября 2014 г. 21 февраля 2017 г. kevinbinz

Часть : алгебраическая последовательность
Краткое содержание : 600 слов, 6 минут чтения

Функция как оператор

Функцию можно представить как машину, которая преобразует ввод в вывод. Например:

Кое-что интересное, подмеченное давно геометрами:

Если я передам приведенной выше функции ВСЕ ВОЗМОЖНЫЕ ЧИСЛА, я получу строку!

Функция как карта

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

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

Счет ребер

Как можно классифицировать различные функции? Одна очевидная вещь — подсчитать количество ребер, входящих в узел или выходящих из него:

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

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

Внедрение и Surjection (& Bijection)

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

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

Если не существует ни популярных, ни непопулярных выходов — если все выходы «нормальные» 🙂 — мы можем назвать такие функции биективными функциями .

Приведенный выше пример не является ни инъективным, ни сюръективным:

Примеры всех четырех исходов:

Кардинальность и биекция

Рассмотрим нижний левый пример. Обратите внимание, что его домен меньше, чем его кодовый домен (3 < 4). Если я позволю тебе переставить стрелки как угодно, сможешь ли ты произвести сюръекцию? Потратьте минуту, чтобы убедить себя, что вы не можете. Вы понимаете, почему всегда будет как минимум один непопулярный выход? Рассмотрим пример в правом верхнем углу. Обратите внимание, что его домен больше, чем его кодовый домен (4 > 3). Если я позволю вам переставить стрелки как угодно, не могли бы вы изготовить инъекцию?

Найдите минутку, чтобы убедить себя, что вы не можете. Вы понимаете, почему всегда будет хотя бы один популярный выход?

Аргумент, который вы должны использовать, чтобы убедиться в вышеизложенном, является аналогом принципа «сортировки по полочкам».

В более общем плане мы находим, что:

Вы также можете использовать вышеуказанные свойства для «обратной работы»: например, если два набора обеспечивают хотя бы одну биекцию, их относительные размеры (мощности) должны быть равны.

Обобщение на морфизмы

Если сомневаетесь, уменьшите масштаб! Пора влюбиться в теорию категорий. 🙂

Функции, основанные на теории множеств. Но были изучены и другие типы карт, сохраняющих структуру:

Injection/Surjection/Bijection были названы в контексте функций. Было бы неплохо иметь имена для любого морфизма, удовлетворяющего таким свойствам? Что ж, тебе повезло!

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

Инъекция биекция сюръекция примеры: Дискретная математика, комбинаторика, теория чисел

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

Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.

Биективная функция

Основные свойства

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

Биекции и обратные функции

Примеры

Элементарные функции

Биекции и их инверсии

Похожие страницы

Автор

Библиографические ссылки

комбинаторика — Разница между сюръекциями, инъекциями и биекциями

Инъекция, Сюръекция, Биекция | Меньше лакун

Добавить комментарий Отменить ответ