Відповідності, функції, відображення

Відповідністю між множинами A і B називається будь-яка підмножина C Í A´B. Якщо (a,b)ÎC, то кажуть, що елемент b відповідає елементу a при відповідності C.

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

Крім того, відповідність можна задавати (або ілюструвати) за допомогою так званого графіка відповідності. Нехай А={1,2,3,4,5} і B={a,b,c,d}, а C={(1,a),(1,d),(2,с),(2,d),(3,b), (5,а),(5,b)} - відповідність між A і B. Позначимо через 1,2,3,4,5 вертикальні прямі, а через a,b,c,d - горизонтальні прямі на координатній площині (рис.1.3а). Тоді виділені вузли на перетині цих прямих позначають елементи відповідності C і утворюють графік відповідності

Зручним методом задання невеликих скінченних відповідностей є діаграма або граф відповідності. В одній колонці розташовують точки, позначені елементами множини A, у колонці праворуч - точки, позначені елементами множини B. З точки a першої колонки проводимо стрілку в точку b другої колонки тоді і тільки тоді, коли пара (a,b) належить заданій відповідності. На рис.1.3б зображено діаграму відповідності C із попереднього абзацу.

Нехай C деяка відповідність. Множина Pr₁C називається областю визначення, а множина Pr₂С - областю значень відповідності C.

Образом елемента aÎPr₁C при відповідності C називається множина всіх елементів bÎPr₂C, які відповідають елементу a; позначається C(a). Прообразом елемента bÎPr₂C при відповідності C називається множина всіх тих елементів aÎPr₁C, яким відповідає елемент b; позначається
C ^-1(b). Якщо DÍPr₁C, то образом множини D при відповідності C називається об’єднання образів усіх елементів із D; позначається C(D). Аналогічно означається прообраз деякої множини G Í Pr₂C; позначається C ^-1(G).

а) б)

Рис.1.3

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

Додатково для відповідностей введемо дві специфічні операції. Відповідністю, оберненою до заданої відповідності C між множинами A і B, називається відповідність D між множинами B і A така, що D={ (b,a) | (a,b)ÎC }. Відповідність, обернену до відповідності C, позначають C ^-¹.

Якщо задано відповідності CÍA´B і DÍB´F, то композицією(суперпозицією, добутком) відповідностей C і D (позначається C°D) називається відповідність H між множинами A і F така, що

H={(a,b) | існує елемент cÎB, для якого (a,c)ÎC і (c,b)ÎD }.

Розглянемо окремі важливі випадки відповідностей C між множинами A і B.

Якщо Pr₁C=A, то відповідність C називається всюдиабо скрізь визначеною. У противному разі відповідність називається частковою.

Відповідність f Í A´B називається функціональною відповідністю, або функцією з A в B, якщо кожному елементові aÎPr₁ f відповідає тільки один елемент з Pr₂ f, тобто образом кожного елемента aÎPr₁ f є єдиний елемент b з Pr₂ f. Якщо f - функція з A в B, то кажуть, що функція має тип A®B і позначають f : A®B або A B.

Всюди визначена функціональна відповідність fÍA´B називається відображенням з A в B і записується як і функція f:A®B або A B. Відображення називають також усюди або скрізь визначеними функціями.

Відображення типу A®A називають перетвореннями множини A.

Через B^A позначається множина всіх відображень з A в B.

Оскільки функція і відображення є окремими випадками відповідності, то для них мають місце всі наведені вище означення: поняття областей визначення та значень, поняття образу та прообразу елементів і множин тощо. Зокрема, для функції f елементи множини Pr₁f називають аргументами функції, образ f(a) елемента aÎPr₁f називають значенням функції f на a.

Відповідність C називається сюр’єктивною (сюр’єкцією), або відповідністю на множину B, якщо Pr₂C =B.

Відповідність C називається ін’єктивною (ін’єкцією), або різнозначною відповідністю, якщо для кожного елемента bÎPr₂C його прообраз C ^-¹(b) складається тільки з одного елемента. Іншими словами, різним елементам множини A відповідають різні елементи множини B. Іноді ін’єкцію називають 1-1 відповідністю.

Відображення, яке є одночасно сюр’єктивним та ін’єктивним, називається бієктивним, або бієкцією. Бієктивні відображення називають часто також взаємно однозначними відображеннями або взаємно однозначними відповідностями між множинами A і B.

Таким чином, відповідність є взаємно однозначною тоді і лише тоді, коли вона функціональна, всюди визначена, сюр’єктивна та ін’єктивна.

Відповідність i_A= { (a,a) | aÎA } називається тотожним перетворенням, діагональною відповідністю або діагоналлю в A.

Взаємно однозначне відображення з A в A називають підстановкою множини A.

Для довільної відповідності C між A і A позначимо через C⁽ⁿ⁾ відповідність C °C °...°C (n входжень літери C). Вважатимемо C⁽⁰⁾=i_A і C⁽¹⁾=C.