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

Упорядкованою парою об’єктів х та y (позначається < x, y >) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у певному порядку. Поняття упорядкованої пари можна поширити й розглядати для будь-якого цілого додатного числа n ³2 упорядковану n -ку об’єктів х ₁,…, х_n (позначається < х ₁,…, х_n >). Об’єкт х_і називається і -м компонентом упорядкованої n -ки. Упорядковані n -ки називають також кортежами.

Декартовим добутком множин А та В (позначається А * В або А ´ В) називається множина

А ´ В ={< a, b >| a Î A, b Î B },

тобто множина усіх упорядкованих пар, побудованих з елементів множин А та В таким чином, що перший компонент кожної пари – це елемент множини А, а другий – елемент множини В.

Наприклад, декартовим добутком множин А ={ a, b } та В ={1,2,3} є множина A ´ B ={< a,1>,< a,2>,< a,3>,< b,1>,< b,2>,< b,3>}. Побудуємо декартів добуток множин В та А. Маємо: В ´ А ={<1, a >,<2, a >,<3, a >,<1, b >, <2, b >,<3, b >}. Як бачимо, А ´ В ≠ В ´ А, отже, операція ´ не комутативна.

Декартовим добутком множин А ₁ ,…,А_n (позначається А ₁´…´ А_n або А ₁*…* А_n) називається множина

А ₁´…´ А_n ={< a ₁,…, a_n >| a ₁Î A ₁,…, a_n Î A_n },

тобто множина усіх упорядкованих n -ок, побудованих з елементів множин А ₁,…, А_n таким чином, що і -й компонент кожної n -ки належить множині А_і (і =1,…, n).

Наприклад, декартовим добутком множин А ₁={ a, b }, A₂={ b, c }, A ₃={ b, d } є множина А ₁´ А ₂´ А ₃={< a, b, b >,< a, b, d >,< a, c, b >,< a, c, d >,< b, b, b >, < b, b, d >,< b, c, b >,< b, c, d >}.

Якщо для деякого і (і =1,…, n) А_і =Æ, то А ₁´…´ А_n =Æ.

Якщо А ₁=…= А_n = А, то А ₁´…´ А_n позначається Аⁿ й називається n-м декартовим степенем множини А.

Наприклад, якщо А ={1,2}, то А ³={<1,1,1>,<1,1,2>,<1,2,1>,<1,2,2>, <2,1,1>,<2,1,2>,<2,2,1>,<2,2,2>}.

Між операцією декартова добутка та іншими операціями над множинами існують зв’язки. Доведемо, зокрема, що (А È В)´ С =(А ´ С)È(В ´ С).

Для цього покажемо спочатку, що (А È В)´ С Í(А ´ С)È(В ´ С). Множина (А È В)´ С є декартовим добутком двох множин ((А È В) та С), отже, елементи цієї множини – це упорядковані пари. Таким чином, маємо: < x,y>Î(А È В)´ С Þ x Î A È B, y Î C Þ x Î A або x Î B, y Î C Þ x Î A та y Î C або x Î B та y Î C Þ < x, y >Î A ´ C або < x, y >Î B ´ C, отже, доведено, що (А È В)´ С Í(А ´ С)È(В ´ С). Тепер покажемо, що (А ´ С)È(В ´ С)Í(А È В)´ С. < x, y >Î(А ´ С)È(В ´ С) Þ < x, y >Î(A ´ C) або < x, y >Î(B ´ C) Þ (x Î A та y Î C) або (х Î В та y Î C). Розглянемо випадок x Î A та y Î C. Маємо: x Î A та y Î C Þ х Î А È В, y Î C Þ < x, y >Î(A È B)´ C. Якщо х Î В та y Î C, то маємо: х Î В та y Î C Þ х Î(А È В), y Î C Þ < x, y >Î(A È B)´ C. Отже, у кожному випадку доведено, що (А ´ С)È(В ´ С)Í(А È В)´ С. Таким чином, рівність виконується.