Задачі та вправи

І. Побудувати усі підмножини множини:

1) {C,T,O}, 2) {+,-,,/},

3) {x,xy}, 4) {a,A},

5) {x,y,{x}}, 6) {1,{1},{{1}}},

7) {{1,2}, {2,3}, {4,5}}, 8) {{0,2}, {2,4}, {4,6}},

9) {01,{0},1}, 10) {x,a,{x},{a}},

11) {X,,Y}, 12) {1,2,,{3}},

13) {0,{{}},}, 14) {{},a,ba},

15) {,{1,2},12}, 16) {,1,2},

17) {x{x}, y, z}, 18) {A,{,A},B},

19) {, XY, AB}, 20) {{x,y}, (x,y)}.

II. Задані множини U={1,2,3,4,5,6}, A={2,5,6}, B={1,3,4,5,}, C={1,2,4,6}. Побудувати P(AC), P((A\B)C'), P(BC), P(C'B), P(BA'), P(AB'), P((B\C)A'), P((A\C)(C\B)).

III. Довести, що для будь-яких множин А, С

1) В(АС)={XY| XВ(А), YВ(С)}, 2) В(АС)=В(А)В(С).

ІV. Довести, що

1) В(_iIА_i)=_iIС_і: С_iВ(А_i), 2) В(_iIА_i)=_iI B(A_i).

Покриття та розбиття множини

Покриттям множини Х називається така сукупність Х₁,…,Х_k,… підмножин множини Х, що Х=Х₁…Х_k… .

Наприклад, множини Х₁={2,4}, Х₂={2,3,5}, Х₃=X₄={1,2,4} утво-рюють покриття множини Х={1,2,3,4,5}, тому що Х₁Х, Х₂Х, Х₃Х, Х₄Х, а також Х=Х₁Х₂Х₃Х₄. Множини Y₁={1,2}, Y₂={2,4}, Y₃={2,3}, Y₄={1,2,3} не утворюють покриття множини Х (хоча усі вони є підмножинами Х), тому що Х≠Y₁Y₂Y₃Y₄. Множини Z₁={1,2,5,6}, Z₂={2,3,5}, Z₃={1,4} теж не утворюють покриття множини Х, оскільки не кожна з них є підмножиною множини Х (Z₁Х).

Розбиттям множини Х називається множина таких непорожніх підмножин множини Х, що попарно не перетинаються й утворюють її покриття.

Наприклад, множина {{1}, {2,3}, {4,6}, {5}} є розбиттям множи-ни Х={1,2,3,4,5,6}. Множина {{1,4}, {2,3}, {4,6}, {1,5}} не є розбиттям множини Х, оскільки, зокрема, множини {1,4} та {4,6} перетинаються. Множина {{1,4}, {2}, {6}, {3}} також не є розбиттям множини Х, тому що сукупність {1,4}, {2}, {6}, {3} не є покриттям множини Х.

Задачі та вправи

І. Знайти такі покриття множини {a,b,c,d,e,f} (принаймні два), які не є розбиттями цієї множини.

ІІ. Чи можна побудувати 10 різних покриттів множини {1,2,3}?

ІІІ. Знайти усі розбиття множини {1,2,3}.

ІV. Скільки існує розбиттів множини {1,2,3,4}?

V. Побудувати покриття та розбиття множин N, Z, Q, R.

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

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