Как найти биективное отображение

Виды отображений

Пусть %%f%% — отображение множества %%X%% в множество %%Y%%.

Инъективное отображение

Отображение %%f%% называется инъективным,

если для любых элементов %%x_1, x_2 in X%%, %%x_1 neq x_2%%, следует, что %%f(x_1) neq f(x_2)%%.
$$
forall x_1, x_2 in X~~x_1 neq x_2 rightarrow f(x_1) neq f(x_2).
$$

Другими словами, отображение %%f%% инъективно, если образы различных элементов из %%X%% также различны.

Пример

Функция %%f(x) = x^2%%, определенная на множестве %%mathbb{R}%%, не является инъективной, так как при %%x_1 = -1, x_2 = 1%% получаем одно и тоже значение функции %%f(x_1) = f(x_2) = 1%%.

Сюръективное отображение

Отображение %%f%% называется сюръективным,
если для всякого элемента %%y in Y%% существует элемент %%x in X%% с условием, что %%f(x) = y%%.
$$
forall y in Y~exists x in X : f(x) = y.
$$

Другими словами, отображение %%f%% сюръективно, если каждый элемент %%y in Y%% является образом хотя бы одного элемента %%x in X%%.

Пример

Отображение %%f(x) = sin(x)%%, определенное на множестве %%mathbb R%%, с множеством %%Y = [-2,2]%% не является сюръективным, т.к. для элемента %%y = 2 in Y%% нельзя найти прообраз %%x in X%%.

Биективное отображение

Отображение %%f%% называется биективным,
если оно инъективно и сюръективно. Биективное отображение также называется взаимно однозначным или преобразованием.

Обычно, словосочетания «инъективное отображение», «сюрьективное отображение» и «биективно отображение» заменяют на «инъекция», «сюръекция» и «биекция» соответственно.

Обратное отображение

Пусть %%f: X to Y%% — некоторая биекция и пусть %%y in Y%%. Обозначим через %%f^{-1}(y)%% единственный элемент %%x in X%% такой, что %%f(x) = y%%. Тем самым мы определим некоторое новое отображение %%g: Y to X%%, которое снова является биекцией. Ее называют обратным отображением.

Пример

Пусть %%X, Y = mathbb R%% — множество действительных чисел. Функция %%f%% задана формулой %%y = 3x + 3%%. Имеет ли данная функция обратную? Если да, то какую?

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

1. Проверим инъекцию. Пусть %%x_1 neq x_2%%. Проверим, что %%f(x_1) neq f(x_2)%%, то есть %%3 x_1 + 3 neq 3 x_2 + 3%%. Предположим противное, %%3 x_1 + 3 = 3 x_2 + 3%%. Тогда получается, что %%x_1 = x_2%%. Получили противоречие, т.к. %%x_1 neq x_2%%. Следовательно, %%f%% — инъекция.
2. Проверим сюръекцию. Пусть %%y in Y = mathbb{R}%%. Найдем элемент %%x in X = mathbb{R}%% c условием, что %%f(x) = y%%, то есть %%3x + 3 = y%%. В данном равенстве задан элемент %%y in mathbb{R}%% и нужно найти элемент %%x%%. Очевидно, что
   $$
   x = frac{y-3}{3} text{ и } x in mathbb R
   $$
   Следовательно, отображение %%f%% сюръективно.

Так как %%f%% — инъекция и сюръекция, то %%f%% — биекция. И, соответственно, обратным отображением является %%x = frac{y-3}{3}%%.

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 20 мая 2022 года; проверки требуют 2 правки.

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

Биективное отображение, являющееся гомоморфизмом, называют изоморфным соответствием.

Если между двумя множествами можно установить взаимно однозначное соответствие (биекцию), то такие множества называются равномощными. С точки зрения теории множеств, равномощные множества неразличимы.

Взаимно однозначное отображение конечного множества на себя называется перестановкой (или подстановкой) элементов этого множества.

Формально, функция называется биекцией (и обозначается ), если она:

Примеры:

Функция является биективной тогда и только тогда, когда существует обратная функция такая, что:

и

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

Литература[править | править код]

• Верещагин Н. К., Шень А. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.
• Ершов Ю. Л., Палютин Е. А. Математическая логика: Учебное пособие. — 3-е изд., стереотип.. — СПб.: Лань, 2004. — 336 с.

Содержание:

1. Сюръекция, инъекция и биекция
2. Произведение множеств

Сюръекция, инъекция и биекция

По этой ссылке вы найдёте полный курс лекций по математике:

Правило, задающее отображение f: X (или функцию /), можно условно изобразить стрелками (рис. 2.1). Бели в множестве У есть хотя бы один элемент) на который не указывает ни одна из стрелок, то это свидетельствует о том, что область значений функции f не заполняет все множество У, т.е. f(X) С У. Если же область значений / совпадает с У, т.е. f{X) = У, то такую функцию называют сюръективной} или короче — сюръекцией, и говорят, что функция / отображает множество X на множество У (в отличие от общего случая отображения множества X в множество У согласно определению 2.1). Итак, / : X есть сюръекция, если Vy 6 У Зх € X : /(х) = у. На рисунке в таком случае к каждому элементу множества У ведет хотя бы одна стрелка (рис. 2.2). При этом к некоторым элементам из У могут вести несколько стрелок. Если к любому элементу у € У ведет не более одной стрелки, то / называют инъективной функцией, или инъекцией. Эта функция не обязательно сюръективна, т.е. стрелки ведут не ко всем элементам множества У (рис. 2.3).

• Итак, функция /: X —У У представляет собой инъекцию, если два любых различных элемента из X имеют своими образами при отображении / два различных элемента из У, или Vy £ f{X) С У 3хеХ: f{x) = y. Сюръекция, инъекция и биекция. Обратное отображение. Композиция отображений произведение множеств. График отображения. Отображение /: X->У именуют биективным, или би-екцией, если каждый элемент у 6 У является образом некоторого и призом единственного элемента из X, т.е. Vy € f(X) = У Э!х € X : f(x) = у.

По сути, функция / в этом случае устанавливает взаимно однозначное соответствие между множествами X и У, и потому ее часто называют взаимно однозначной функцией. Очевидно, что функция / биективна тогда и только тогда, когда она одновременно инъективна и сюръективна. В этом случае стрелки (рис. 2.4) соединяют попарно каждый элемент из X с каждым элементом из У.

При этом никакие два элемента из X не могут быть соединены стрелкой с одним и тем же элементом из У, ибо / инъективна, и никакие два элемента из У не могут быть соединены стрелками с одним и тем же элементом из X из-за требования единственности образа в определении 2.1 отображения.

Каждый элемент из X участвует в попарном соединении, поскольку X — область определения функции /. Наконец, каждый элемент из У тоже участвует в одной из пар, ибо / сюръективна. Роли X и У в этом случае как бы совершенно одинаковы, и если повернуть все стрелки вспять (рис. 2.5), то получим иное отображение или иную функцию д), которое тоже и инъективно, в сюръективно. Отображения (функции), допускающие такое обращение, будут играть большую роль в дальнейшем.

В частном случае множества X и У могут совпадать (X = У).

Тогда биективная функция будет осуществлять отображение множества X на себл. Биекцию множества на себя называют также пре-образов анием. 2.3. Обратное отображение Пусть /: X —? У — некоторая биекция и пусть у € У. Обозначим через /_1(у) единственный элемент х€Х, такой, что /(г) = у. Тем самым мы определим некоторое отображение 9 : Y Xу которое является снова биекцией. Ее называют обратным отображением, или обратной биекцией к /. Часто ее также называют просто обратной функцией и обозначают /”*. На рис. 2.5 функция д как раз и является обратной к /, т.е. д = f’1.

Возможно вам будут полезны данные страницы:

Функция /, определяемая формулой у = За – 2, я,у € R, является биекцией. Обратной функцией будет х = (у + 2)/3. б. Действительная функция f(x) = х2 действительного переменного х не является сюръективной, поскольку отрицаг тельные числа из У = R не являются образами элементов из Х=К при /: ЛГ->У. Пример 2.2. Пусть Л” = R, а У = R+ — множество положительных действительных чисел. Функция f(x) = ах, а > 0, аф 1, является биекцией. Обратной функцией будет Z”1 (У) = 1°8а У • Отображения (функции) / и являются взаимно обратными. Ясно, что>если функция не является биекцией, то обратной к ней функции не существует. Действительно, если / не инъек-тивна, то некоторому элементу у € У могут соответствовать несколько элементов х из множества X, что противоречит определению функции. Если же / не сюръективна, то в У найдутся элементы, для которых в X нет прообразов, т.е. для этих элементов обратная функция не определена. Пример 2.1. а. Пусть X = У = R — ^комсество действительных чисел.

• Сюръекция, инъекция и биекция. Обратное отображение. Композиция отображений произведение множеств. График отображения. 2.4. Композиция отображений Если f:X-*Y и g:Y-*Zy то отображение (р:Х -+Z, заданное для каждого а: 6 А” формулой =, именуют композицией (суперпозицией) отображений (функций) / и д> или сложной функцией, и обозначают ро/ (рис. 2.6).
• Таким образом, сложная функция до f реализует правило: я Применяй сначала /, а затем ди, т.е. в композиции операций «до/ надо начинать с операции /, расположенной справа. Отметим, что композиция Рис. 2.6 отображений ассоциативна, т.е.если /: X -+Y , д: Y Z и h: Z-*H> то тогда (hog)of = = ho(gof)i что проще записывают в виде ho до /. Проверим это следующим образом: На любом wK«oaicecmee X определено отображение 1х -X X, называемое тождественным, обозначаемое часто также idx и задаваемое формулой Ix(x) = x Vx € А”. Его -действие состоит в том, что оно оставляет все на своих местах.

Так, если является биекцией, обратной к биекции /: Х-+У, то /”1о/ = /х, а /о/-1 = /у, где и /у — тождественные отображения множеств X и У соответственно. Обратно, если отображения f: X ->Y и р : У Л” таковы, что gof = Ix и fog = /у, то функция / является биекцией, а у — ее обратной биекцией.

Очевидно, что если / — биекция Л” на У, а $ — биекция У на Z, то gof является биекцией X на Z, а будет по отношению к ней обратной биекцией. 2.5. Произведение множеств. График отображения Напомним, что две взаимно перпендикулярные координатные оси с масштабом, одинаковым для обеих осей, задают на плоскости прямоугольную декартову систему координат (рис. 2.7). Точку О пересечения координатных осей называют начало* координат. Каждой точке М можно поставить в соответствие пару (я, у) действительных чисел где х — координата точки Мх на ко-ординатной оси Ох, а у — координата точки Му на координатной оси Оу. Точки Мх и Му являются основаниями перпендикуляров, опущенных из точки М соответственно на оси Ох и Оу. Числа х и у называют координатами точки М ( в выбранной системе координат), причем х называют абсциссой точки М, а у — ординатой этой точки.

Очевидно, что каждой паре (а, Ь) действительных чисел а, 6 6R соответствует на плоскости точка М, имеющая эти числа своими координатами. И обратно, каждой точке М плоскости соответствует пара (а, 6) действительных чисел а и 6. В общем случае пары (а, Ь) и (6, а) определяют разные точки, т.е. существенно, какое из двух чисел а и b стоит в обозначении пары на первом месте. Таким образом, речь идет об упорядоченной паре. В связи с этим пары (а, 6) и (6, а) считают равными между собой, и они определяют одну и ту же точку на плоскости, если только а = 6. Сюръекция, инъекция и биекция. Обратное отображение. Композиция отображений произведение множеств. График отображения. Множество всех пар действительных чисел, а также множество точек плоскости обозначают R2. Это обозначение связано с важным в теории множеств понятием прямого (или дек ар-това) произведения множеств (часто говорят просто о произведении множеств). Определение 2.2.

Произведением множеств А и В называют множество Ах В возможных упорядоченных пар (ж, у), где первый элемент взят из А, а второй — из В, так что Равенство двух пар (х, у) и (&’, у’) определяют условиями х = х’ и у = у7. Пары (я, у) и (у, х) считают различными, если хфу. Это особенно важно иметь в виду, когда множества А и В совпадают. Поэтому в общем случае А х В ф В х Л, т.е. произведение произвольных множеств не коммутативно, но оно дистрибутивно по отношению к объединению, пересечению и разности множеств: где обозначает одну из трех названных операций.

Произведение множеств

Произведение множеств существенно отличается от указанных операций над двумя множествами. Результатом выполнения этих операций является множество, элементы которого (если оно не пустое) принадлежат одному или обоим исходным множествам. Элементы же произведения множеств принадлежат новому множеству и представляют собой объекты иного рода по сравнению с элементами исходных множеств. Аналогично определению 2.2 можно ввести понятие произведения более чем двух множеств. Множества (А х В) х С и А*х (В х С) отождествляют и обозначают просто А х В х С, так что . Произведения Ах Ау Ах Ах А и т.д. обозначают, как правило, через А2 , А3 и т.д. Очевидно, плоскость R2 можно рассматривать как произведение R х R двух экземпляров множества действительных чисел (отсюда и происходит обозначение множества точек плоскости как произведения двух множеств точек числовой прямой). Множеству точек геометрического (трехмерного) пространства соответствует произведение R х R х R трех экземпляров множества точек числовой прямой, обозначаемое R3.

• Произведение п множеств действительных чисел обозначают Rn. Это множество представляет собой всевозможные наборы (xj, Х2, хп) из п действительных чисел Х2) хп £ R, а любая точка х* из Rn есть такой набор (xj, х, х*) действительных чисел хп € К*
• Произведение п произвольных множеств есть множество упорядоченных наборов из п (в общем случае разнородных) элементов. Для таких наборов употребляют названия кортеж или n-ка (произносят „энка”). Пример 2.3. Пусть А = { 1, 2} и В = {1, 2}. Тогда , и множество А х В можно отождествить с четырьмя точками плоскости R2, координаты которых указаны при перечислении элементов этого множества. Если С={ 1,2} и D={3,4}, то . Пример 2.4. Пусть Тогда Геометрическая интерпретация множеств Е х F и F х Е представлена на рис. 2.8. # Для отображения /: X можно составить множество упорядоченных пар (г, у), которое является подмножеством прямого произведения X х У.
• Такое множество называют графиком отображения f (или графиком функции я*»- Пример 2.5. В случае XCR и Y = К каждая упорядоченная пара задает координаты точки на плоскости R2. Если при этом X является промежутком числовой прямой R, то график функции может представлять некоторую линию (рис. 2.9). Пример 2.6. Ясно, что при XCR2 и У = R график функции есть некоторое множество точек в R3, которое может представлять некоторую поверхность (рис. 2.10).

Если же X С R, а У = R2, то график функции также есть множество точек в R3, которое может представлять некоторую линию, пересекаемую плоскостью х = const лишь в одной точке М с тремя координатами х} yi, у2 (рис. 2.11). # Все упомянутые примеры графиков функции являются важнейшими объектами математического анализа, и в дальнейшем они будут подробно рассмотрены.

Биективные отображения

Высшее
назначение математики – нахо­дить
скрытый порядок в мире хаоса, который
нас окружает.

Н.
Винер.
«Я – математик»

Знакомясь
с историей основных понятий математики,
хотя бы таких, как теория множеств и
отображений, мы видим, что она совсем
непроста и даже драматична, а метод
дедуктивных рассуждений – основа
математических дока­зательств,
приводит к следствиям из очевидных
утверждений, которые иногда кажутся
противоречащими интуиции и здравому
смыслу. Из известной аксиомы Цермелло
(Пусть да­но множество М
состоящее из попарно непересекающихся
множеств М_
,
тогда существует множество М, каждый
элемент m_
которого
принадлежит неко­торому М_

причем
М 
М_

= m_
)
вытекает уди­вительная возможность
разбиения шара на конечное число частей,
из которых движениями в пространстве
(т. е. сохраняя расстояния) можно составить
два та­ких же шара.

Иногда
такие «противоречия» говорят о
несовершенстве дедуктивного ме­тода
или системы аксиом, но зачастую открывают
совершенно неочевидные, но истинно
глубинные и глобальные закономерности.

К
таким кажущимся противоречиям относится
равномощность множеств точек прямой и
ее любого интервала. Посмотрим на эту
проблему с другой сто­роны. Понятно,
что точек, как прямой, так и плоскости
бесконечно много, но где больше? После
того, как мы установили биективность
отображения прямой в интервал, поспешного
ответа, видимо, стоит остеречься. Прежде
всего, оче­видно, что способом,
аналогичным доказательству равномощности
прямой и интервала, можно показать
равномощность множеств точек плоскости
и квадра­та без ограничивающих его
отрезков. Это сведет задачу сравнения
мощностей прямой и плоскости к сравнению
равномощных им интервала и квадрата.
При­ведем рассуждения Кантора.

Множество
точек квадрата естественным образом
отождествимо с множе­ством кортежей
<х,у>
с бесконечными десятичными дробями
вида 0,
a₁,a₂,a_3…,
которые мы предполагаем записанными в
бесконечном виде (см. пример 12.1, т.е. не
принимается запись дробей с конечным
числом значащих цифр). Идея Кантора
заключается в том, чтобы слить эти дроби
в одну десятичную дробь, по которой
однозначно восстанавливались бы х и у
(in),
и которая принимала бы все положительные
значения, не превосходящие 1 (sur),
по одному разу (ото­бражение), когда
точка
<х,
у>
пробегает по всему квадрату (Dom).
Тем самым было бы получено биективное
отображение квадрата на единичный
отрезок.

Казалось
бы, такое соответствие просто установить,
положив f(<0,a₁,a₂,a₃…,
0,b₁,b₂,b₃
>) ⁼
0,а₁b₁а₂b₂a₃b_3
,…
(Отметим,
что отношение F
= {<<0,a₁,a₂,a₃…,
0,b₁,b₂,b₃
>,
0,а₁b₁а₂b₂a₃b_{3
, …}>},
очевидно
есть отображение, так как кортежем
<0,a₁,a₂,a₃…,
0,b₁,b₂,b₃
> однозначно
определяется число 0,а₁b₁а₂b₂a₃b₃…).
И по дроби 0,а₁b₁а₂b₂a₃b₃…,
отделяя
числа на четных и нечетных местах после
запятой, можно восстановить х=
0,a₁,a₂,a₃…,
и у= 0,b₁,b₂,b₃…
однозначно, что и означает инъективность
отображения: кортеж
<<х,у>,
0,а₁b₁а₂b₂a₃b₃…
>

F
с произвольным фиксированным
0,а₁b₁а₂b₂a₃b₃…единствен.

Однако
оказывается, что определенное так
отображение не сюръективно, потому что
образом элемента <х,у> хотя и является
бесконечная десятичная дробь, не
превосходящая 1, но существуют бесконечные
десятичные дроби, (например, вида
0,с₁с₂0с₄0с₆…
), которые получаются только из конечных
дробей. Для однозначности представления
чисел в десятичной записи такое
представление мы исключили из рассмотрения
(так при z
= 0,с₁с₂0с₄0с₆…
по­лучим х= 0, с₁,
00… – с конечным числом ненулевых значащих
цифр после за­пятой, а у=0,с₂с₄с₆…).
Обойти это противоречие можно, взяв за
a₁,a₂,a₃…,
b₁,b₂,b₃…
не отдельные цифры, а, как назвал их
Кантор, «молекулы десятич­ной дроби»,
соединяя в одно целое любую ненулевую
значащую цифру с пред­шествующим
нулем. Например, если z
= 0,3208007000302405… , то с₁
= 3, с₂
=
1, c₃
= 08, с₄
= 007, с₅
= 0003, c₆
=
2,
c₇
=
4, C_g
= 05,…. Несколько изменим пра­вило:
пусть теперь а₁,b₁,а₂,b₂,a₃,b₃
и
т. д. обозначают не числа, стоящие,
со­ответственно, на нечетных и четных
местах после запятой, а такие «молекулы».
Тогда любому <x,
y>
однозначно соответствует бесконечная
дробь z, которая, в свою очередь, однозначно
определяет и х
и у,
распадаясь на две дроби с беско­нечным
числом «молекул», т. е. бесконечные
десятичные дроби. Такое отобра­жение
инъективно, т. е. по х
и у
число z
получается однозначно, и всякое z
]0,l[
может возникнуть только однажды.

Это
биективное отображение и устанавливает
равномощность квадрата и интервала,
что, в конечном счете, приводит к
утверждению, что плоскость и пря­мая
имеют одинаковую мощность континуум,
или равномощность множеств R
и
R²
.

Обобщение
этого доказательства на произвольную
степень Rⁿ
вполне очевидно. Г. Кантор в течение
трех лет с 1874 года пытался доказать
невозмож­ность биективного соответствия
между множествами R
и R²
при n>1,
пока он к своему удивлению не построил
его. «Я это вижу, но не верю в это» – писал
он
Дедекинду…

Соседние файлы в папке 2_kurs_3_semestr

• #
• #
• #
• #
• #
• #
• #
• #