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

Упорядкованою парою об’єктів х та 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. Отже, у кожному випадку доведено, що (А´С)È(В´С)Í(АÈВ)´С. Таким чином, рівність виконується.