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

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

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

f o g = {< x, z > | существует u такое, что <x, u > Î f и <u, z > Î g } или

f o g = {< x, y > | существует v такое, что <x, v > Î f и <v, y > Î g } .

Отсюда заключаем, что существуют такие v и u, что <x, u > Î f и <x, v > Î f. Так как f – функция, то u = v. Можно также убедиться, что y = z. Первая часть утверждения доказана, т.е. f o 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 o e_Y = f и e_X o f = f.

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

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

f o e_Y = {< x, z > | < x, z > Î f } = f.

Равенство e_X o 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 o g) ^-1 = g ^-1 o f ^-1

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

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

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

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

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

f o f ^–1 = {< x, z > | z = x } = e_X.

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

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

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

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

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

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

Бинарное отношение r на множестве C называется рефлексивным, если
< x, x > Î r (x r x) для всех x Î C, то есть id _X Í r. и называется иррефлексивным, если < x, x > Ï r для всех x Î C, то есть id _X Ç r = Æ.

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

Бинарное отношение r называется транзитивным, если для всех x, y, z Î C

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

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

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

Дата добавления: 2015-07-20