Обернені функції. Введемо важливі відношення на множинах функцій, які викори­сто­вуються в процесі аналізу функцівональних залежностей, що описують конкретні об’єкти і системи.

Визначення. Якщо ліва композиція gf функцій f: S T і g: T S співпадає з тотож­ною функцією 1_S на множині S, ми будемо говорити, що функція g – ліва обернена до функції f,а функція f – права обернена до функції g, функція f - оборотна зліва,функція g - оборотна справа. Якщо, крім того, f g = 1_T, ми будемо говорити, що функція g – двобічно оборотна до f і, за симетрією, функція f – двобічно оборотна до g. Функція, яка має двобічно оборотну, називається оборотною.

Теорема 2.Функція оборотна зліва тоді і тільки тоді, коли вона ін’єктивна. Функція оборотна справа тоді і тільки тоді, коли вона сюр’єктивна.

Доведення. Покажемо спочатку, що будь-яка оборотна зліва функція ін’єктивна. Нехай g: T S – функція, обернена зліва до f:S T. Припустимо, що f(s) = f(s'). То­ді за озна­ченням,

s=1_S(s) =g(f (s)) = g(f (s')) =1_S(s')=s'

Таким чином, виходячи з припущення, що f(s) = f(s'), ми встановили, що s = s'. Це доводить ін’єктивність f. Залишається перевірити обернене твердження, щоб закінчити доведення першої частини теореми: нам потрібно показати, що якщо f ін’єктивна, то для неї існує ліва обернена g₁ функція, тобто g₁ f = 1_S. З цією метою виберемо елемент s₁ ÎS і визначимо g₁:T S таким чином:

Тоді (g₁f)(s)= g₁(f (s)) = sдля всіх sÎS, так що, за означенням, g₁f = 1_S і g₁ є лівою оберненою до f.

Аналогічно перевіряється друга частина теореми. Якщо tÎT і fh = 1_T, то t = 1_T(t) = f(h(t)), тому що будь-який елемент tÎT є образом f(s) певного елемента s = h(t) Î S, і f сю­р’єк­тивна. В інший бік, якщо f:S T сюр’єктивна, то кожен елемент tÎT є образом t = f(s)хоча б одного елемента s Î S. Для кожного елемента t Î T виберемо з множини всіх s, що переходять в t, одного представника і позначимо його, скажімо, через h(t). Тоді ми отрима­ємо функцію h:T S,таку, що f(h(t)) = t для всіх tÎT, тобто fh = 1_T, як стверджувалось. Теорема доведена.

Наслідок. Функція f: S T є бієкцією тоді і тільки тоді, коли вона є оборотною зліва і справа.

Теорема 3.Наведені нижче властивості функції f: S T еквівалентні:

(i) функція f – бієкція;

(ii) функція f має ліву обернену функцію g і праву обернену функцію h.

Якщо ці властивості виконуються, то

(iii) всі обернені до f функції (ліві, праві і двобічні) співпадають. Ця єдина обернена до функції f функція f ^–1, бієктивна, і

(f ^–1) ^–1 = f. (2)

Доведення. Еквівалентність властивостей (i) і (ii) є просто переформулюванням попереднього наслідку. Наслідком умови (ii) є

g = g1_T = g(fh) = (gf)h =1_s h = h.

Це показує, що всі ліві і праві обернені до функції f функції співпадають, і доводить властивість (iii). Нарешті, бієктивна функція f обернена до своєї оберненої функції g = h, оскільки gf =1_s і fh = 1_T. Отже, обернена функція бієктивна і має функцію f своєю єдиною оберненою функцією, тобто (f ^–1)^–1 = f.

Визначення. Квадрат будь-якої функції f: S S визначається як функція f ² = f ° f = f f,тобто як результат дворазового застосування функції f. Коли f² = f, функція f називається ідемпотентом чи проектором.

Наприклад, ортогональний проектор (x,y)-площини на x-вісь або y-вісь є ідем­по­тен­том. Відзначимо також, що ці два проектори мають властивість fg=gf(чи, що те ж саме, g f = f g), оскільки fgіgf відібражують будь-яку точку площини у початок координат (0,0).

Визначення. Пари функцій f, g з властивістю fg=gf називаються комутуючими чи перестановочними.

Стосовно будь-якої з двух композицій ми можемо назвати функцію g ÎS² лівою оберненою до функції f Î S², якщо fg =1_S. Аналогічно, права обернена до f — це функція h така, що fh = 1_S. Згідно теореми 2, функція f має ліву обернену функцію відносно лівої композиції, і тільки тоді, коли f є ін’єкцією. Значить, те ж відноситься до існування правої оберненої функції до f відносно правої композиції. Аналогічно, функція f має обернену справа функцію відносно лівої композиції тоді і тільки тоді, коли f - сюр’єкція.

Двобічна обернена існує в точності для бієктивних функцій незалежно від того, яку з композицій (ліву чи праву) ми розглядаємо. Функція, обернена до f, позначається через f ^–1 . Вона існує у тому і тільки у тому випадку, коли функція f бієктивна, і задовільняє відношенням

f ^–1 f = f f ^–1 = 1_s (і для лівої і для правої композиції).

Деякі спеціальні класи функцій. На закінчення лекції ми коротко розглянемо такі чо­ти­ри важливих класи функцій: підстановки; послідовності; функціонали і відображення, що зберігають еквівалентність. Ці функції часто використовуються, в теорії графів, теорії гра­ма­тик для визначення мов програмування і перекладу, в машинній графіці.

Визначення. Підстановкою множини А називається будь-яка бієкція на А.

Підстановкискінченних множин становляють особливий інтерес для розрахунків. Коли А визначене, ми в змозі розрахувати число різних підстановок А.

Нехай |А| = n Î N. Позначимо через nPn число таких підстановок. Значення nPn легко ро­зрахувати. Можемо розглянути задачу побудови бієкції на А як задачу заповнення ящиків, за­нумерованих від 1 до n, a₁,...,a_n (рис.8). Порядок, в якому заповнюються ящики, не сут­тєвий (будь-який інший порядок можна отримати перемішуванням ящиків). Тому будемо за­по­в­ню­вати їх зліва направо. Перший ящик може бути заповнений n способами, тому що ми ма­ємо вільний вибір з усієї множини А. Забираючи обраний елемент з А, отримаємо множи­ну з n–1

1 2 n – 1 n

...

Рис. 8.

 

елементів. Отже, другий ящик може бути заповнений n – 1 способами, третій ящик – n – 2 способами і т.д. Продовжуючи цей процес, отримаємо, що (n - 1)-й ящик може бути заповнений двома способами, а ящик з номером n – єдиним элементом з А, що залишився. Отже, число різних підстановок з А рівне

n × (n–1) × (n-2)× ... ×3 × 2 ×1.

Цей добуток називається факторіалом n (позначається n!). Отже, nPn = n!.

Нехай Nn підмножина перших n натуральних чисел множини N. Тому що А і Nn мають однакову кількість елементів, можна звести множину А до множини Nn. Будь-яка під­становка на Nn повинна визначати образ кожного элемента в Nn (який, звичайно, повинен бути єдиним і відрізнятися від інших). Нехай підстановка на Nn. Тоді можна визначити як множину з n пар наступним чином:

{(1, x₁), (2, x₂),...,(n, x_n)}, де {x₁,...,x_n} = Nn.

Не обов’язково, звичайно, повинно бути x₁ = 1 і т.д. Можна також представити таким чином:

Приклад 1. Нехай підстановка на N6:

Тоді s(1) = 5, s(2) = 6, s(3) = 3 і т.д.

Перевагою цього позначення є простота, з якою можуть бути розраховані важкі під­ста­новки. Припустимо, що - підстановка на Nn, визначена вище, а інша підстановка на тій же самій множині. Тоді підстановка може бути записана як сукупність пар в порядку, що визначається x₁, x₂,...x_n. Якщо дві послідовності записати одна над іншою (перша застосована підстановка повинна бути записана першою), то верхній і нижній рядки утворять результуючу підстановку.

Приклад 2. Нехай підстановка з прикладу 1 і

r

Можна переписати r у вигляді

r

Тому r ° sможе бути розраховане наступним чином :

r однакові

r ° s

Отже, наприклад, r ° s(2) = r(s(2)) = r(6) = 5 і т. д. Звідси робимо висновок, що зо­бра­ження оберненої (скінченної) підстановки отриму­є­ть­ся перестановкою рядків, що зобра­жують початкову підстановку. Хоча таке зображення краще в розрахунках, воно потребує багато зайвого місця, особливо в тих випадках, коли багато елементів не міняються в процесі підстановки. Існує більш просте позначення, котре може вживатися безпосередньо для дея­ких простих підстановок і опосередковано для всіх скінченних.

Визначення. Нехай А = {а₁,…,а_n}. Підстановку r називають циклом (циклічною підста­нов­кою), якщо

r

Припустимо, що А Í В і множина В проста. Розширюючи підстановку r на всі елементи В, можна визначити підстановку s так, що

r(x), якщо х ÎА,

s : х ® x, якщо х Î В\А.

В цьому випадку підстановка s поводить себе подібно підстановці r у всіх випадках, коли елементи В не лишаються на місці. Застосування підстановки s до А пересуває елемен­ти по колу циклічним чином, і, якщо відома область А, ми можемо позначити підстановку як (a₁, a₂,…,а_n). Ця підстановка називається циклом довжини n.

Приклад 3. Розглянемо знову підстановку

r

Підстановка є циклом довжини 5 і може бути записана як (1, 3, 6, 5, 4).

Не всі підстановки є циклами. Наприклад, підстановка s в прикладі 1 не є циклом. Нагадаємо, що підстановка s має вигляд

Тому s(1) = 5, s(5) = 4, s(4) = 1, звідки робимо висновок, що підстановка s містить цикл (1, 5, 4). Починаючи з 2, отримуємо інший цикл – (2, 6). Таким чином, маємо

s = (1, 5, 4) ° (2, 6) і s = (2, 6) ° (1, 5, 4).

В дійсності будь-яка скінченна підстановка може бути зображена як добуток циклів, при цьому цикли можуть міститись в будь-якому порядку. З побудови робимо висновок, що один еле­мент не може зустрітись більш ніж в одному циклі, тобто цикли не перетинаються.

Теорема 4.Кожна підстановка r на скінченній множині А виражається у вигляді добутку циклів, що не перетинаються.

Доведення.Оскільки |A| = n ÎN, то А має таку ж кількість елементів, що й N_n . Тому без втрати загальності ми можемо обмежитись розгляданням підстановки r на N_n .У теоремі стверджується, що r = s₁ ° s₂ ° …° s_r, де кожне s_i, i = 1,2,…,r, є циклом і цикли не пере­ти­на­ю­ть­ся. Для доведення теореми наведемо потрібні цикли.

Спочатку знайдемо найменший елемент х₁Î N_n такий, що r(х₁) ¹ х₁ і r(х) = х для всіх х, 1 £ х < х_1. Якщо такого х₁ не існує, то r = I (тобто r є тривіальним порожнім добутком циклів). В іншому випадку розрахуємо х₁, r(х₁), r²(х₁), r³(х₁) і т. д. Всі ці елементи знахо­дять­ся в N_n. Тому елементи в цій послідовності повинні містити повторення. Припус­ти­мо, що r^k(х₁) – перший такий елемент. Покажемо, що r^k(х₁) = х₁. Припустимо, що це спів­відношення не виконується. Тоді r^l(х₁) = r^k(х₁) для деякого l, 0<l<k. Отже r^l-1(х₁) = r^-1 ° r^l(х₁) = r^-1 ° r^k(х₁) = r^k-1(х₁) і т. д.

Тому r^l-1(х₁) = r^k-1(х₁), тобто r^k-l(х₁) = r⁰(х₁) = х₁, що суперечить мінімальності k (тому що k-l < k). Таким чином, r^k(х₁) = х₁ і підстановка s₁ = (х₁, r(х₁), r²(х₁),…,r^k-1(х₁)) задає цикл всередині r.

Якщо всі елементи х ÎN_n такі, що r(х) ¹ х (будемо називати такі елементи неста­ціо­нар­ними), містяться в s₁, то r = s₁ – єдиний цикл (який не перетинаєтся). В іншому випадку знайдемо наступний найменший елемент х₂ ÎN_n такий, що r(х₂) ¹ х₂ і х₂ не зустрічається в s₁. З х₂ будуємо множину різних ступенів r : s₂ = (х₂, r(х₂), r²(х₂),…, r^m(х₂)). Це цикл довжи­ни не менше 2 і він не перетинаєтся з s₁.

Якщо всі нестацівонарні елементи вичерпані, то r = s₁ ° s₂ = s₂ ° s₁. Очевидно, що мно­жину нестаціонарних елементів, що не входять в ці цикли, можна зменшити, і в кінці кін­ців ми прийдемо до Æ. Отже, r = s₁ ° s₂ ° s₃°… ° s_r для деякого r ÎN.

Розглянемо тепер ситуацію з множинами А: |A| = n і B Í A, |B| = r £ n, взявши за проблему визначити число бієктивних функцій з А в В чи, що еквівалентно, число ін’єк­тив­них відображень з В в А.

Число перестановок (без повторів) з n елементів по r позначається _nP_r і розраховується так же, як і _nP_n, за винятком того факту, що процес припиняється після заповнення r ящиків. Таким чином,

_nP_r = n×(n–1)×…×(n–r+1).

Легко бачити, що, продовжуючи процес заповнення ящиків, n – rелементів, що зали­ши­лися, можна розмістити по останнім n – rящикам _n-rP_n-r способами. Тому і

_nP_r = (_nP_n)/ _(n-rP_n-r) = n! / (n–r)!

При розрахунку _nP_r ми знаходимо число бієктивних функцій з А в В. Підрахуємо число таких функцій.

Визначення.Нехай А – скінченна множина і B Í A, |А| = n ³ r = |B|. Множина В нази­ва­є­ться з’єднанням (без повторів) з n елементів по r. Число таких з’єднань позначається С^r_n.

Розрахунок С^r_n відбувається наступним чином. Покладемо |A| = n. Візьмемо випадкову підмножину B Í Aтаку, що |В| = r. Тоді В є шляхом підстановки з n елементів по r. Число ін’єктивних функцій на А, що мають B своим шляхом, є _nP_r . Якщо f є такою функцією і g –інша така функція, яка має ту ж саму область значень, то g пов’язане з f спввідношенням g = j°f, де j – підстановка на В.

Функції g і f визначають одну і ту ж комбінацію, і в дійсності число функцій, що виз­на­чають цю комбінацію, рівне числу підстановок j на B. Отже, _nP_r = С^r_n× _rP_r, звідки С^r_n = (_nP_r)/(_rP_r) = n!/r!×(n–r)!

Оскільки відносні доповнення єдині і |A\B| = n – r , то звідси робимо висновок, що С^r_n= С^n–r_n.

Розглянемо як функції деякі відомі матаматичні об’єкти.

Визначення.Послідовністю на множині S називається всюду визначена функція N ® Z.

Якщо s: N ® Z– задана послідовність і s(n) = s_n, то звичайно позначають послідов­ність не s, а (s_n) чи (s₁,s₂,…,s_n,…). В цьому випадку s_n називають n-м членом послідовності.

Особливий інтерес в задачах, пов’язаних з трансляцією мов програмування, станов­лять функціонали. Іх особливість полягає в тому, що їх значення належать множині функцій.

Визначення.Нехай дані множини А, В і C. Позначимо через [В®C] множину всіх фун­к­цій з множини В в множину C. Функція F: А®[B®C] називається функціоналом.

Приклад 4.Нехай Р – множина програм, тобто текстів програм, які повинні бути об­роб­лені компілятором. Аналогічно нехай I і О – множини відповідно вихідних і вхідних зна­чень, які доступні програмі для вводу і виводу. Тоді компілятор (з відповідної мови) є функ­ці­оналом типу P®[I®O]; для даної р Î Р він намагається створити машинний код, який при виконанні буде читати i Î I і видавати оÎО.

Приклад 5.Нехай всі дані належать R. Тоді якщо f: a®[x®a + x], то f(2): x®2 + x і f(2)(3) = 5, тоді як f(3): x®3 + x і f(3)(3) = 6 і т. д.

Будемо розглядати функціонали просто як функції, що мають нетривіальні області значень і будемо поводитись з ними відповідним чином.

На завершення визначимо функції, які зберігають певні структури. Спочатку знову розглянемо відоме нам співвідношення відношення еквівалентності і роз­биття.

Визначення.Нехай Х – множина, на якїй задано відношення еквівалентності r. Тоді Х розбивається відношенням r на r-еквівалентні класи; множина r-еквівалентних класів на Х позначається Х/r.

Визначення.Нехай Х і Y – множини, r_х і r_y – відношення еквівалентності на них і f: Х®Y – всюду визначена функція. Позначимо через`f відношення`f: X/r_х ® Y/r_y таке, що`f ={([x], [f(x)]) : x Í X}, де [x] – клас еквівалентності х. Якщо`f – функція то х₁r_хх₂ Þ`f([х<sub>1</sub>]) =`f([х₂]) і f є відображенням, що зберігає еквівалентність. В цьому випадку говорять, що f: X ® Y індукує відображення `f: X/r_х ® Y/r_y.

Наочний спосіб зображення такого відображення наведено на рис. 9.

Якщо розглянути відображення f, погоджене з відношенням еквівалентності, то мож­на переходить від х₁ до у₁ чи через х₂, використовуючи співвідношення y₂ = f(х₂) і х₁r_хх₂, чи через y₂, використовуючи співвідношення y₁ = f(х₁) і y₂r_хy₁.

Приклад 6.Нехай Х = {1, 2, 3}, Y = {1, 4, 9} і r_х і r_y такі, що X/r_х = {{1},{2,3}}, Y/r_y = {{1},{4,9}}, і f: X ® Y таке, що х ® х². Тоді

`f([1]) = [f(1)] = [1] = {1},

`f([2]) = [4] = {4, 9},

`f([3]) = [9] = {4, 9}.

В цьому випадку {2,3} Î X/r_х Þ 2r_х3 Þ [2] = [3] і `f ([2]) =`f([3]). Тому `f є функцією і f зберігає відношення еквівалентності.

Приклад 7.Нехай Х, Y і f є ті ж, що і в прикладі 6, і відношення еквівалентності s _x і s_y індукують розбиття {{1},{2,3}} і {{1,4},{9}} відповідно. В цьому випадку індуковані відно­шен­ня дають

`f([2]) = [f(2)] = [4] = {1 ,4},

`f([3]) = [f(3)] = [9] = {9}.

Через те, що 2s_х3, то [2] = [3] в X/s_х , але (4, 9) Ï s_r, оскільки [4] ¹ [9] в Y/s _r. В по­рів­нян­ні з рис.9 цей приклад дає відношення, зображені на рис.10. Через те, що не можна з’єд­нати сторони прямокутника у всіх випадках, то відношення еквівалентності не збері­га­ю­ть­ся.

r_x s_х

x₁ x₂ 2 3

f f s_х

f s_r f

y₁ y₂ 4

r_y 4 s_r 9

рис. 9 рис 10