Декартово произведение на множества. Индексиране на множества

До момента се запознахме с основните операции с множества - сечение, обединение и разлика на множества (можете да разгледате статията тук). Сега ще разгледаме декартовото произведение на две множества $A$ и $B$, което ще отбелязваме с $A\times B$.

Опредление 1: Нека $a$ и $b$ са произволни елементи. Множеството $\{\{a\},\{a,b\}\}$ се нарича наредена двойка от елементите $a$ и $b$. 

Вместо този запис ние ще използваме записът $(a,b)$, като изришно споменем, че $(a,b)\neq (b,a).$ Тук казваме, че $a$ е първи елемент, а $b$ втори елемент.

Определение 2: Нека $A$ и $B$ са множества. Множеството $A\times B=\{(a,b):a\in A, b\in B\}$ наричаме декартово произведение на множествата $A$ и $B$.

Пример за декартово произведение е множеството от точките в евклидовата равнина, в която е въведена правоъгълна координатна система. В този случай, ако с $x$ означим ортогонална проекция на дадена точка върху правата $O_{x}$, а с $y$ означим ортогоналната проекция на същата точка върху правата $O_{y}$, тогава  всяка точка от координатната система се определя еднозначно от наредената двойта $(x,y)$. Така от казаното до тук можем да кажем, че евклидовата равнина $E$ представлява декартовото произведение $O_{x}\times O_{y}.$ 

Например, нека разгледаме множеството $A=\{2,8,9\}$ и $B=\{1.3.7\}$. Следователно 

$A\times B=\{(2,1),(2,3),(2,7),(8,1),(8,3),(8,7), (9,1),(9,3),(9,7)\}.$ и 

$B\times A=\{(1,2), (1,8),(1,9),(3,2),(3,8),(3,9),(7,2),(7,8),(7,9)\}.$

Очевидна двете множества $A\times B$ и $B\times A$ съдържат различни елементи.

Определение 3: Декартовото произведение $A_1\times A_{2}\times\ldots\times A_{n}=\{(a_1,a_2,\ldots, a_n):a_i\in A_i\}$, където $(a_1,a_2,\ldots, a_n)$ е наредена $n$ - орка ще наричаме $n$ - кратно декартово произведение.

Нека да разгледаме множеството $I_n=\{i:i\in\mathbb{N}, 1\leq i\leq n\}$. Можем да използваме елементите на $I_n$ за да ознамич елементите на множеството $A=\{a_i:i\in I_n\}$. Тогава $I_n$ ще наричаме индексно множество на $A$. Ясно е, че $|A|=n$, защото $A=\{a_1,a_2,\ldots, a_i,\ldots, a_n\}$, т.е. $A$ се състои от $n$ на брой елементи.

Определение 4: Обединението на множествата $A_1, A_2,\ldots, A_n$ ще дефинираме по следният начин $A_1\cup A_2\cup\ldots\cup A_n=\bigcup_{i\in I_n}A_i=\{a: \ съществува \ i\in I_n, \  такова, че \ a\in A_i\}$.

Определение 5: Сечение на множествата $A_1, A_2,\ldots, A_n$ ще дефинираме по следният начин $A_1\cap A_2\cap\ldots\cap A_n=\bigcap_{i\in I_n}A_i=\{a: \ за всяко \ i\in I_n, \  е \ изпълнено \ a\in A_i\}.$

Операциите обединение и сечение на множества са асоциативни и именно това ни позволява да дефинираме обединение и сечение на повече от две множества. Не така стои въпросът, ако разгледаме разликата на множества. Тази операция не може да се дефинира за повече от две множества, защото асоциативността не е в сила.

Определение 6: Фамилията от множества $F=\{A_i:i\in I, A_i\subseteq A\}$ се нарича разбиване на $A$, ако са изпълнени следните три условия:

1) $A_i\neq\emptyset$ за всяко $i\in I$;

2) $A_i\cap A_j\neq\emptyset$ за всеки $i\neq j$;

3) $\bigcup_{i\in I}A_i=A$.

Нека да разгледаме множеството $A=\{a,b,c,d,e,f,g,h,i,j,k\}$. Тогава множеството $B=\{\{a,b,c\},\{\d,e,f,g,h},\{i,j,k\}\}$ е разбиване на $A$, докато множеството $C=\{\{a,b,c\},\{d,f,g,h,\}.\{i,j,k\}\}$ не е разбиване на множеството $A$, защото $e\in A$, но не принадлежи на никое подмножество.

С напредъка на компютърните технологии, възниква и нуждата множествата да се представят чрез двоичен код. Нека разгледаме следната дефиниция, която ще ни даде възможност да представим всяко крайно множество (компютрите на работят с безкрайни множества), чрез така нареченият бит-вектор. 

Дефиниция 7: Нека $A\subseteq U$. За множеството $A$ дефинираме бит-вектор по следният начин $b_i=1$, ако $a_i\in A$ и $b_i=0$, ако $a_i\notin A$, за $i=1,2,\ldots n.$

Нека разгледаме $U=\{a,b,c,d,e,f,h,i,j,k\}$ и $A=\{a,b,d,h,i,k\}$, тогава бит-векторът, който съответства на множеството $A$ ще има вида $1 \ 1 \ 0 \ 1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 1$.

Задачи са самостоятелна работа

1. Да се намери $A\times B$ и $B\times A$, ако $A=\{a,b,c\}$ и $B=\{d,e\}.$

2. Да се намерят всички възможни разбивания на множеството $A=\{a,b,c\{a,b,c\}\}$.

Използвана литература:

1. Дискретна математика, Светла Бойчева, Стефка Толева-Стоименова, изд. Сиела 2018 г.

2. Увод в дискретната математика, Красимир Манев, изд. КЛМН 2012 г.

3. Въведение в дискретната математика, Христо Кискинов, Пловдивско университетско издателство