Основні властивості відображень

1. Повний прообраз об’єднання дорівнює об’єднанню повних прообразів: f ^-1(A B) = f ^-1(A) f ^-1(B).

2. Повний прообраз перерізу дорівнює перерізу повних прообразів: f ^-1(A B) = f ^-1(A) f ^-1(B).

3. Образ об’єднання дорівнює об’єднанню образів: f(A B) = f(A) f(B).

4. Образ перерізу є підмножиною перерізу образів: f(A B)  f(A) f(B).

Звуження та продовження функції. Нехай функція f: X  Y задана на X, f₁ – на множині Q  X, причому для кожного x  Q, f(x) = f₁(x). Тоді f₁ називається обмеженням (звуженням) функції f на Q, а f – продовженням f₁ на X.

Приклад. f(x) = x³ – задана на R, f : R  R. Якщо ввести обмеження Q = Z, то дістанемо звуження f₁(x) функції f(x) на Z, причому f₁: Z  не на Z, оскільки не кожне ціле число є кубом цілого числа.

Композиція відображень. Якщо f : X  Y, q : Y  Z, то їх композиція qf : X  Z, причому (qf)(x) = q(f(x)).

Приклад. f = sin, q = ln, (qf)(x) = (ln  sin)(x) = ln(sinx).

Теорема 1. Функція f є взаємно однозначним функціональним відношенням тоді й тільки тоді, коли f ^-1 – взаємно однозначне функціональне відношення.

Доведення. Доведемо, що f ^-1 – функція. Нехай (y, x₁)  f ^-1, (y, x₂)  f ^-1, (x₁, y)  f, (x₂, y)  f. Оскільки f – взаємно однозначне відношення, то x₁ = x₂, а це означає, що f ^-1 – функціональне відношення.

Нехай (y₁, x)  f ^-1, (y₂, x)  f ^-1  (x, y₁)  f, (x, y₂)  f  y₁ = y₂  f ^-1 – взаємно однозначне функціональне відношення.

Теорема 2. Композиція двох функціональних відношень є функціональним відношенням.

Доведення. Нехай f  b  B, a q: B  С. За означенням композиції h qf = {(a, c)  (a, b)  f і (b, c)  q} – це підмножина декартового добутку A  C.

Доведемо, що h – функціональне відношення:

(a, c₁)  h   b₁  B ((a, b₁)  f і (b₁, c₁)  q),

(a, c₂)  h   b₂  B ((a, b₂)  f і (b₂, c₂)  q).

Оскільки f – функціональне відношення, то b₁ = b₂  q – функціональне відношення по с₁ = с₂  h – функціональне відношення.

Означення. Функція, що утворюється з функцій f₁, …, f_n деякою підстановкою їх одна в одну і перейменуванням аргументів, називається суперпозицією f₁, …, f_n.

Відношення еквівалентності

Означення. Бінарне відношення в множині X називається відношенням еквівалентності (позначається „~”), якщо виконуються такі властивості:

• рефлективність (x ~ x);

• симетричність (x ~ y  y ~ x);

• транзитивність (x ~ y і y ~ z  x ~ z).

Приклад. „Подібність трикутників” у множині всіх трикутників на площині.

Універсальне, одиничне і порожнє – відношення еквівалентності.

Називатимемо класом еквівалентності елемента a множину всіх елементів множини X, які еквівалентні елементу a: [a] = {x X  a ~ x}.

Нехай на множині A задано відношення еквівалентності R. Виберемо елемент a₁  A і утворимо клас A₁ (підмножину A), який складається з a₁ та всіх елементів, еквівалентних a₁; потім виберемо елемент a₂  A₁ і утворимо клас A₂, що складається з a₂ та всіх елементів, еквівалентних a₂ і т.д. Отримаємо систему класів A₁, A₂, …, таку, що . Ця система має такі властивості: вона створює класи, які попарно не перетинаються; будь-які елементи різних класів не еквівалентні, а з одного класу – еквівалентні.

Довільні два класи еквівалентності за відношенням R або не мають спільних елементів, або збігаються.

Побудоване розбиття називається системою класів еквівалентності за відношенням R.

Приклад. Відношення „проживати в одному будинку” на множині жителів міста є відношенням еквівалентності й розбиває цю множину на неперерізні підмножини людей, які є сусідами в будинку.

Матриця і граф відношення еквівалентності. Нехай відношення еквівалентності задано в множині X. Елементи, що належать одному класу еквівалентності, попарно еквівалентні між собою. Отже, стовпці матриці відношення еквівалентності для елементів одного класу еквівалентності однакові та містять одиниці у всіх рядках, що відповідають цим елементам. Оскільки класи еквівалентності не перерізаються, у стовпцях, які відповідають елементам різних класів, не буде одиниць в одних і тих самих рядках.

При побудові матриці відношення розташуємо елементи множини так, щоб ті елементи, які належать одному класу еквівалентності, були поруч.

Приклад. Для відношення еквівалентності, заданого класами еквівалентності X₁ = {x₁, x₂, x₃}, X₂ = {x₃, x₈}, X₃ = {x₅, x₆, x₇, x₈}, матриця матиме такий вигляд:

Граф відношення еквівалентності в цьому випадку має вигляд:

x₅

x₃

x₆

x₉

x₁

x₂

x₄

x₄

x₇