Декартів (прямий) добуток множин

Поряд з операціями (1.2) – (1.8) впроваджується операція декартова (прямого) добутку множин.

Визначення 2.3. Прямий (декартів) добуток двох множин A і B є множина всіх пар таких, що , :

. (2.1)

Приклад 2.3. Дано множини , . Складемо їх декартів добуток за правилом (2.1): .

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

Приклад 2.5. Координатне подання точок площини, що ввів Рене Декарт – французький математик і філософ, – є історично першим прикладом прямого добутку. Множина точок площини , тобто множина пар виду , : .

Декартів добуток множин не є комутативним: .

Визначення 2.4. Якщо , тобто – декартів квадрат.

Визначення 2.5. Прямий добуток n множин є сукупність всіх векторів довжини таких, що , ,..., , тобто

, (2.2)

Ототожнивши множини в декартовому добутку (2.3), одержимо декартову ступінь множини.

Визначення 2.6. Декартів добуток n однакових множин є декартова ступінь:

. (2.3)

Декартова ступінь множини поряд з іншими n-мірними векторами містить вектори, що складаються з однакових координат, тобто -мірні вектори виду . Кількість таких векторів визначається потужністю множини й дорівнює n.

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

Нехай – кінцеві множини, потужності яких відповідно дорівнюють . Тоді потужність декартова добутку множин дорівнює добутку потужностей цих множин:

. (2.4)

З формули (2.4) випливає, що потужність декартова ступеня визначається як ступінь потужності множини :

. (2.5)

2.3 Відповідності

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

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

При цьому називають областю визначення (множиною відправлення) відповідності : ; – областю значень (множиною прибуття) відповідності : .

Визначення 2.8. Множина всіх елементів , що відповідають елементу , називається образом елемента у множині при відповідності .

Визначення 2.9. Множина всіх елементів , яким відповідає елемент , називається прообразом елемента в множині при відповідності .

Приклад 2.6. Дано множини і . Для відповідності область визначення є проекція на першу вісь: ; область значень – проекція на другу вісь: ;
– образ елементів 1, 2 у множині при відповідності ; 1, 2 є прообразами елемента при відповідності .

Відповідності прийнято ілюструвати за допомогою діаграм. Для прикладу 2.6 діаграма наведена на рис. 2.1.

Рисунок 2.1 – Діаграма відповідності із прикладу 2.6

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

Приклад 2.6 ілюструє часткову відповідність, тому що .

Приклад 2.7. Для відповідності
(рис. 2.2), де , , проекція на першу вісь співпадає
з множиною відправлення : .

S

Рисунок 2.2 – Діаграма відповідності S із прикладу 2.7

Визначення 2.11. Відповідність називається сур’єктивною, якщо її проекція на другу вісь співпадає з множиною прибуття: , тобто у відповідності задіяні всі елементи з області значень .

Приклад 2.8. Для відповідності
(рис. 2.3), де , , проекція на другу вісь співпадає
з множиною прибуття : .

Т

Рисунок 2.3 – Діаграма відповідності Т із прикладу 2.8

Визначення 2.12. Відповідність називається ін’єктивною (in), якщо різні елементи з його області визначення мають різні образи в його області значень , тобто прообразом будь-якого елемента з області значень є єдиний елемент із області визначення (інакше – різні елементи з області визначення мають різні образи):

. (2.6)

Отже, при ін’єктивній відповідності кожний образ має єдиний прообраз. Це означає, що в діаграмі ін’єктивної відповідності нема збіжних стрілок.

Приклад 2.9. Відповідності , і із прикладів 2.6 – 2.8 не є ін’єктивними, оскільки образ має два прообрази – елементи 1, 2 у множині . До того ж у відповідності образ також має два прообрази – елементи 2 і 3.

Приклад 2.10. Відповідність де , , є ін’єктивною, оскільки образи з множини мають єдині прообрази в множині (рис. 2.4).

Р

Рисунок 2.4 – Діаграма відповідності Р із прикладу 2.10

Визначення 2.13. Відповідність називається функціональною (однозначною), якщо образом будь-якого елемента з області визначення є єдиний елемент із області значень, тобто – функціонально, якщо

. (2.7)

Діаграма функціональної відповідності не має розбіжних стрілок.

Приклад 2.11. Відповідність із прикладу 2.6 є функціональною, тому що кожному прообразу відповідає єдиний образ: прообразу 1 відповідає образ , прообразу 2 відповідає також один образ – . Відповідність із прикладу 2.7. не є функціональною, оскільки існує прообраз – елемент 2, у якого одночасно два образи – елементи й .

Визначення 2.14. Бієктивна (взаємо-однозначна) відповідність – це відповідність, що є всюди визначеною, сур’єктивною, ін’єктивною, функціональною, тобто має всі властивості одночасно.

Біекцію (бієктивну або взаємо-однозначну відповідність) можна встановити тільки між множинами однакових потужностей.

Приклад 2.12. Для відповідності (рис. 2.5), де , , характерні всі властивості, отже, вона є бієктивною.

Рисунок 2.5 – Діаграма відповідності із прикладу 2.12

Приклад 2.13. Розглядається відповідність , що геометрично зображена на рис. 2.6. Вона переводить відрізок дійсної осі у відрізок дійсної
осі : . Відповідність не є функціональною, тому що образом числа 3, що лежить на осі абсцис, є відрізок осі ординат, а не єдиний елемент: . Дуга є прикладом функціональної відповідності.

Рисунок 2.6 – Ілюстрація відповідності до прикладу 2.13

2.4 Функції. Відображення

Визначення 2.15. Функцією називається функціональна відповідність

, (2.8)

де х – аргумент; у – значення функції на елементі х.

Визначення 2.16. Відображенням множини в множину називається всюди визначена функція; – образ множини при відображенні .

Приклад 2.14. Відповідність (рис. 2.7) є функціональною (функцією), оскільки кожному прообразу відповідає єдиний образ; всюди визначеною, тому що ; отже, f – відображення; не є сур’єктивною: (елемент d не має прообразу в множині ).

Рисунок 2.7 – Приклад функції і відображення

Визначення 2.17. Якщо для відповідності існує відповідність така, що тоді й тільки тоді, коли , тоді відповідність називається зворотною до і позначається , тобто

.

Визначення 2.18. Зворотною функцією називається відповідність, зворотна до функції , тобто якщо зворотна до відповідність є функціональною, то вона називається зворотною функцією й позначається .

Приклад 2.15. Різні види кодування (кодування букв абеткою Морзе, подання чисел у різних системах числення, секретні шифри, вхідні та вихідні номери в діловій переписці) є відповідностями між кодованими об’єктами й кодами, що привласнюються їм. Ці відповідності, як правило, мають всі властивості взаємо-однозначної відповідності, крім сур’єктивності. Єдиність образу й прообразу в кодуванні гарантує однозначність шифрування й дешифрування. Відсутність сур’єктивності означає, що не кожний код має сенс. Наприклад, кодування телефонів сьомизначними номерами не є сур’єктивним, оскільки деякі номери не відповідають ніяким телефонам. Для кодувальної функції, що кожному об'єкту зі своєї області значень ставить у відповідність деякий код, зворотною буде декодувальна функція, що кожному коду ставить у відповідність закодований цим кодом об’єкт. Якщо кодувальна функція, не є сур’єктивною, то декодувальна функція не всюди визначена.

Визначення 2.19. Нехай дані функції й . Функція називається композицією функцій і (позначення ), якщо має місце рівність , де . Композиція є послідовне застосування функцій і , при цьому застосовується до результату функції .

Приклад 2.16. Розглядається триелементна множина і два перетворення й цієї множини: і , де запис означає, що елементу ставиться у відповідність елемент , тобто переходить у . Для задання перетворення кінцевих множин використовується запис: , . Композиція перетворень – є нове перетворення: , .

Приклад 2.17. При діагностуванні мікросхем напівпровідникової пам’яті роботу дешифратора адреса можна подати у вигляді графа адресної дешифрації, що показує відповідність між адресами й елементами пам’яті. При правильній роботі спостерігається взаємо-однозначна відповідність між призначеною адресою ліворуч і місцем елемента праворуч (рис. 2.8, а). При несправності дешифратора спостерігається порушення взаємо-однозначної відповідності в графі адресної дешифрації (рис. 2.8, б).

а б

Рисунок 2.8 – Граф адресної дешифрації: а – випадок справної схеми;

б – випадок з несправністю

2.5 Контрольні запитання

1. Чи можуть повторюватися елементи вектора?

2. Як визначається довжина вектора?

3. Як визначається декартів добуток двох множин?

4. Як визначається декартів добуток множин?

5. Що є елементами декартова добутку двох множин?

6. Що є об'єктами декартова добутку множин?

7. Як визначається вектор?

8. Як визначається довжина (розмірність) вектора?

9. Чому дорівнює потужність декартова добутку множин?

10. Чи є декартів добуток множин комутативним?

11. Що являє собою декартовий ступінь?

12. Чи правильно: ?

13. Що таке відповідність?

14. Що називається проекцією вектора на -у вісь?

3 ВІДНОШЕННЯ. АЛГЕБРА ВІДНОШЕНЬ