Композиція відображень

Нехай задано два відображення: f :X→Yтаg:Y→Z. Тоді композицією відображеньfіg(позначаємо символомg○f) будемо називати відображення з множиниXв множинуZ, визначене виразомg○f (x) =g(f (x)) для всіх елементівxз множиниX. Прийняте правило, згідно з яким у композиціїg○fтреба починати з відображенняf, розташованого праворуч.

Наприклад, нехай маємо множини Х = {l, 2, 3, 4},Y = {а, b, c},Z = {u, v}та два відображення

f : Х → Y, , g : Y → Z,

Тоді композиція заданих відображень g○f: Х → Z,

Композиція відображень асоціативна, тобто якщо маємо три відображення f :X→Y,g:Y→Z,h:Z→U, то (h○g) ○f=h○ (g○f) =h○g○f.

Відображення g:Y→Xназивається оберненим до відображенняf :X→Y, якщо виконуються такі умовиf ^-1○f= I_X(I_X- тотожне відображення на множиніX),f○f ^-1=I_Y(I_Y- тотожне відображення на множиніY).

Для відображення fіснує обернене відображенняf ^-1тоді і тільки тоді, коли відображенняfбієктивне. Обернене відображенняf ^-1також є бієктивним.

Якщо f :X→Y- бієкція йg:Y→Z- бієкція, тоg○f- бієкція зХвZ, а її обернена бієкція дорівнюєf ^-1○g ^-1.

Наприклад, нехай задані множини Х ={l, 2, 3}, Y = {а, b, c} та відображенняf : Х → Y, . Це відображення є бієктивним, і тому до нього існує оберненеf ^-1: Y → X, .Дійсно,f ^-1○f== I_X та f○f ^-1==I_Y.

Відношення

Розглянемо декартовий добуток другого степеня множини Х:Х² = Х  Х.Довільну підмножинуRмножиниХ²(R  Х²) будемо називати бінарним відношенням (або просто відношенням), заданим на множиніХ. Вважатимемо, що впорядковані елементиx, х' Хзнаходяться між собою у відношенніR, коли (x, х')  R.Якщо наХзадано відношенняR  X ², то записx R х'означає, щоxіх'знаходяться у відношенніR, тобто (x, х')  R.

Розглянемо кілька прикладів відношень:

1) на множині Nвідношення. Ясно, що впорядковані пари (3, 7) і (5, 5) належать цьому відношенню, а пара (4, 1) не належить;

2) на множині Р(Х) всіх підмножин множиниХ= {1, 3, 5, 7, 9} відношення. Пари підмножин ({1, 3}, {1, 3, 9}) і ({5, 7, 9}, {5, 7, 9}) належать цьому відношенню, а пара підмножин ({1, 5, 7}, {3, 5, 9}) не належить.

Відношення Rна множиніXназивається:

1) рефлективним, якщо довільний елемент множини знаходиться у відношенні сам з собою, тобто для будь-якого хÎХвиконуєтьсяхR х. Прикладами рефлективних відношень можуть бути ≤, ≥, = на множині натуральних чисел;

2) антирефлективним, якщо для будь-якогохÎХпара (х, х) не належить до відношенняR.Прикладами антирефлективних відношень можуть бути<, >, ≠ на множині раціональних чисел;

3) симетричним, якщо для довільнихx, х' Î Хз того, щоx R х'випливаєх' R x;

4) антисиметричним, якщо для довільнихx, х' Î Хз того, щоx R х'іх' R x, випливаєx = х'(наприклад,наN, тому що зx  х'іх'  xвипливаєх= х');

5) транзитивним, якщо для довільнихx, х', х'' Î Хз того, щоx R х'іх' R х'', випливаєx R х'' (наприклад, відношенняна множиніР(Х) чи відношенняна множиніN).

Наведемо деякі приклади відношень:

1) R = {(x, х') |x, х'  Q, | x - х' |  2007}

Відношення рефлективне, бо для будь-якого xQ виконується нерівність | x - х |  2007

Відношення не є антирефлективним, бо скажімо для елемента x=5Qнерівність | x - х |  2007 виконується.

Відношення є симетричним, бо для довільних x, х'  Q, з нерівності | x - х' |  2007 випливає нерівність | x' - х |  2007

Відношення не є антисиметричним, бо для різних елементів x=7 таx'=5 з множиниQодночасно виконуються нерівності | x - х' |  2007 та | x' - х |  2007

Відношення не є транзитивним, бо для елементів x=2010,x'=1 таx''=10 з множиниQнерівності | x - х' |  2007 та | x' - x'' |  2007 виконуються, а нерівність | x - х'' |  2007 не виконується.

2) R = {(x, y) |x, y  С, якщо |x|  |y|  |y²|}

Розглянемо далі відношення, які мають особливе значення.