Декартовий добуток множин

 

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

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

 

 

Розглянемо дуже важливу операцію над множинами.

Декартовим (прямим) добутком множин A і B (записується AB) називається множина всіх пар (a, b), в яких перший компонент належить множині A (aA), а другий – множині B (bB).

Тобто

 

AB = { (a, b) | aA і bB } або (a, b) AB   

 

Декартів добуток природно узагальнюється на випадок довільної скінченної сукупності множин. Якщо A1, A2,..., An – множини, то їхнім декартовим добутком називається множина

 

D = { (a1, a2,..., an) | a1A1, a2A2,..., anAn },

 

яка складається з усіх наборів (a1, a2,..., an), в кожному з яких i-й член, що називається i-ю координатою або i-м компонентом набору, належить множині Ai, i=1, 2,..., n. Декартів добуток позначається через A1 A2...  An.

Набір (a1, a2,..., an), щоб відрізнити його від множини, яка складається з елементів a1, a2,..., an, записують не у фігурних, а в круглих дужках і називають кортежем, вектором або впорядкованим набором. Довжиною кортежу називають кількість його координат. Два кортежі (a1, a2,..., an) і (b1, b2,..., bn) однакової довжини вважаються рівними тоді і тільки тоді, коли рівні їхні відповідні координати, тобто ai=bi, i=1, 2,..., n. Отже, кортежі (a, b, c) і (a, c, b) вважаються різними, в той час як множини {a, b, c} і {a, c, b} – рівні між собою.

Декартів добуток множини A на себе n разів, тобто множину AA... A називають n-м декартовим (або прямим) степенем множини A і позначають An.

Прийнято вважати, що A0 =  (n=0) і A1 = A (n=1).

Приклад 1. Якщо A = {a, b} і B = {b, c, d}, то

 

AB = { (a, b), (a, c), (a, d), (b, b), (b, c), (b, d) },

A2 = { (a, a), (a, b), (b, a), (b, b) }.

 

2. Якщо R – множина дійсних чисел або множина точок координатної прямої, то R2 – це множина пар (a, b), де a, bR, або множина точок координатної площини.

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

3. Скінченна множина A, елементами якої є символи (літери, цифри, спеціальні знаки тощо), називається алфавітом. Елементи декартового степеня A називаються словами довжини n в алфавіті A. Множина всіх слів в алфавіті A – це множина

 

A* = {e}  A  A2  A3 ... = {e}  Ai,

 

де e – порожнє слово (слово довжини 0), тобто слово, яке не містить жодного символу алфавіту A.

Замість запису слів з An у вигляді кортежів (a1, a2,..., an) частіше використовують традиційну форму запису слів у вигляді послідовності символів a1a2... an, ajA, j=1, 2,..., n. Наприклад, 010111, 011, 0010, 100, 010 – слова в алфавіті B = {0, 1}, а 67-35, -981, (450+12) /27, 349*2+17 – це слова в алфавіті C = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, /, (,) }.

Операція декартового добутку неасоціативна і некомутативна, тобто множини (AB) C і A (BC), а також множини AB і BA, взагалі кажучи, нерівні між собою.

Зв’язок декартового добутку з іншими теоретико-множинними операціями встановлюється такими тотожностями:

 

(A  B)  C = (AC)  (BC),

(AB)  C = (AC)  (BC),

A  (B  C) = (AB)  (AC),

A  (BC) = (AB)  (AC).

 

Проекцією на i-у вісь (або i-ою проекцією) кортежу w= (a1, a2,..., an) називається i-а координата ai кортежу w, позначається Pri (w) = ai.

Проекцією кортежу w= (a1, a2,..., an) на осі з номерами i1, i2,..., ik називається кортеж (ai1, ai2,..., aik), позначається Рri1, i2,..., ik (w) = (ai1, ai2,..., aik).

Нехай V – множина кортежів однакової довжини. Проекцією множини V на i-у вісь (позначається PriV) називається множина проекцій на i-у вісь усіх кортежів множини V: PriV = { Pri (v) | vV }.

Аналогічно означається проекція множини V на декілька осей:

 

Pri1, i2,..., ikV = { Pri1, i2,..., ik (v) | vV }.

Приклад 2. Pri1, i2,..., ik (A1  A1 ...  An) = Ai1  Ai2 ...  Aik.

Якщо V={ (a, b, c), (a, c, d), (a, b, d) }, то Pr1V={a}, Pr2V={b, c}, Pr2, 3V={ (b, c), (c, d), (b, d) }.

 

 

Відповідністю між множинами A і B називається будь-яка підмножина CAB.

Якщо (a, b) C, то кажуть, що елемент b відповідає елементу a при