Пример 1.17

1)        Отношение {<1, 2>, <a, b>, <, >} – функция.

2)        Отношение {<a, 1>, <a, 2>, <b, 3>} – не является функцией.

3)        Отношение  {<x, x²>  x – действительное число} – функция, которую обозначают  y = x².

Свойства функции

Пусть f: X  Y.

1)        Функция (отображение)  f  называется инъективной (инъективным), если для любых х₁, х₂, y из <x₁, y>  f  и <x₂, y>  f  следует, что х₁ = х₂.

2)        Функция (отображение)  f  называется сюръективной (сюръективным), если для любого  элемента y  Y  существует элемент x  X, такой, что <x, y>  f.

3)        Функция (отображение)  f  называется биективной (биективным), если  f  одновременно инъективна и сюръективна.

Если  существует биективная функция f: X  Y, то говорят, что f осуществляет    взаимно однозначное соответствие между множествами X и Y. Биективную функцию называют также биекцией.

Пример 1.18

Рассмотрим функции  f: R  R, R – множество действительных чисел.

1) f = {<x, e^x>  x  R},  иначе  f(x) = e^x – инъективна, но не сюръективна.

2) f = {<x, x³-x>  x  R}, иначе  f(x) = x³ – x – сюръективна, но не инъективна.

3) f = {<x, 2x + 1>  x  R}, иначе  f(x) = 2x + 1 – биективна.

Композиция функций

Композиция двух функций f  и  g  определяется так же, как и двух отношений, т.е. f  g = {<x, z>  существуют y, такой, что  <x, y>  f,  <y, z>  g}.

Утверждение 1.2. Композиция двух функций есть функция. При этом если           f: X  Y, g: Y  Z, то f  g: X  Z.

Действительно, чтобы композиция f  g  была функцией, необходимо, чтобы из  <x, y>  f  g  и  <x, z>  f  g   следовало, что y = z..

Из определения композиции, имеем: 

              f  g  = {<x, z>  существует  u  такое, что <x, u>  f  и  <u, z>  g}       или

f  g  = {<x, y>  существует  v  такое, что <x, v>  f  и  <v, y>  g}.

Отсюда заключаем, что существуют такие  v  и  u, что <x, u>  f  и <x, v>  f. Так  как  f – функция, то  u = v. Можно также убедиться, что y = z. Первая часть утверждения доказана, т.е.  f  g – функция.

Вторая часть утверждения вытекает из определения композиции функций.

Утверждение 1.3. Композиция двух биективных функций есть биективная функция. (Доказать самостоятельно).

Тождественное отображение

Тождественным отображением множества X в себя называется отображение e_X: X  X,  такое, что для любого x  X, <x, x>  e_X, т.е.

e_X = {<x, y>  x, y  X  и  y = x} = id_X  или  e_X (x) = x.

Нетрудно видеть, что если f: X  Y, то  f  e_Y   = f   и    e_X  f = f.

Действительно, f  e_Y  = {<x, z>  существует y  такое, что <x, y>  f  и <y, z>  e_Y}.

По определению e_Y: y = z,  т.е. <x, z>  f, следовательно,

f  e_Y  = {<x, z>  <x, z>  f} = f.

Равенство e_X  f  = f  доказать самостоятельно.

Так как функция f  является бинарным отношением, то для нее, как для бинарного отношения, определено обратное отношение  f ^-1 . Естественно поставить вопрос о том, каким условиям должна удовлетворять функция f, чтобы отношение f ^-1 являлось функцией.

Утверждение 1.4. Если  f  инъективная функция, то f ^-1  есть функция. При этом

, .

Доказательство. По определению: f ^-1 = {<x, y>  <y, x>  f }. Так как f – инъективная функция, то для любых y₁, y₂,  x  из <y₁, x>  f  и <y₂, x>  f следует, что y₁ = y₂, т.е.  из  <x, y₁>  f ^-1 и <x, y₂>  f ^–1 следует y₁ = y₂, то есть  доказывает что    f ^–1  –  функция.

Замечание. Для того чтобы отображение f: X  Y имело обратное отображение, требуется более сильное условие, а именно  f  должна быть биекцией.

Так как  f есть бинарное отношение и справедливо утверждение 1.4, то для инъективных функций f  и g справедливы свойства:

1) (f ^-1) ^-1  = f;

2) (f g) ^-1 = g ^-1  f ^-1

Кроме того, если f:  X  Y биекция, и определены тождественные отображения, то

3) (f  f ^-1) = e_X;

4) (f ^-1  f ) = e_Y.

Приведем доказательство свойства 3: f  f ^–1 = {<x, z>  существует y такой ,что <x, y>  f  и < y, z>  f ^-1}.

По определению: f ^–1 = {<y, z>  <z, y>  f }, т.е. f  f ^–1  = {<x, z>  существует y  такой, что <x, y>  f и <z, y>  f }. Так как f – инъективна то z = x, а так как f – сюръективна, то это справедливо для любого y  Y,  т.е.:

f  f ^–1  = {<x, z>  z = x} = e_X.

Аналогично доказывается свойство 4.

1.4. Отношение эквивалентности

           Типы отношений

           Эквивалентность

           Разбиение множеств

 

Типы отношений

Бинарное отношение  на множестве  называется рефлексивным, если <x, x>    (x  x)   для всех  x  , то есть id_X  . и называется иррефлексивным, если <x, x>   для всех  x  , то есть id_X   = .

Бинарное отношение   на множестве  называется симметричным, если для всех  x, y    из  <x, y>    следует, что  <y, x>  , и называется антисимметричным, если для всех  x, y    из  <x, y>    и  <y, x>    следует, что  x = y.

Бинарное отношение  называется транзитивным, если  для всех  x, y, z   

из  <x, y>    и <y, z>    следует, что  <x, z>  .

Эквивалентность

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