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

І. Для заданого на множині A={a,b,c,d,e} відношення R побудувати рефлексивне, симетричне, транзитивне замикання, а також R_rst та A/R_rst.

1) R={<a,b>,<c,c>,<d,a>,<d,d>}, 2) R={<b,c>,<c,b>,<a,a>,<b,b>},

3) R={<d,c>,<a,a>,<c,c>,<d,d>}, 4) R={<a,c>,<b,a>,<b,b>,<a,b>},

5) R={<c,b>,<c,d>,<c,a>,<c,c>}, 6) R={<a,d>,<a,a>,<d,b>,<d,c>},

7) R={<c,d>,<c,b>,<b,a>,<d,b>}, 8) R={<a,c>,<b,d>,<d,a>,<c,b>},

9) R={<d,d>,<a,d>,<d,c>,<b,a>}, 10) R={<b,c>,<d,c>,<c,c>,<c,a>}.

II. Довести, що відношення RR²…Rⁿ симетричне для будь-якого n1, якщо R симетричне.

ІІІ. Нехай R – бінарне відношення на множині А. Довести, що:

1) якщо R рефлексивне, то R=R_r;

2) якщо R симетричне, то R=R_s;

3) якщо R транзитивне, то R=R_t.

IV. Нехай R – бінарне відношення на n-елементній множині А. Сформу-лювати правила перетворення матриці відношення R на матрицю відношення: 1) R_r; 2) R_s.

V. Нехай R – перетворення множини А. Чи будуть перетвореннями множини А відношення R_r, R_s, R_t?

VІІ. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) R_r=S_r; 2) R_s=S_s; 3) R_t=S_t? Відповіді обгрунтувати.

Відношення порядку

Бінарне відношення R, задане на множині А, називається відно-шенням часткового порядку (частковим порядком на А), якщо R реф-лексивне, антисиметричне, транзитивне. Множина А, на якій задано від-ношення часткового порядку, називається частково упорядкованою. Множину А, частково упорядковану відношенням R, позначатимемо <A,R>. Часто відношення часткового порядку позначається символом .

Наприклад, відношення R={<1,2>,<2,2>,<1,3>,<3,3>,<1,1>,<4,4>}, задане на множині А={1,2,3,4}, є рефлексивним, антисиметричним та транзитивним, отже, є частковим порядком на А. Прикладами відно-шень часткового порядку є відношення  та  на множині R. Відношення {<1,2>,<1,1>,<2,1>} на множині А={1,2} не рефлексивне (й не транзитивне), отже, воно не є частковим порядком на А. Відношення А² на будь-якій множині А, що має понад один елемент, не антисимет-ричне (містить пари виду <x,y> та <y,x>, де xy), тому не є частковим порядком на А. Відношення і_А на будь-якій множині А є частковим порядком на А. Відношення включення  на булеані деякої множини А є частковим порядком, оскільки воно рефлексивне (ХХ для будь-якої підмножини Х множини А), антисиметричне (якщо Х та Y – підмножи-ни множини А й XY та YX, то X=Y), транзитивне (якщо X, Y – під-множини множини А й XY та YZ, то XZ).

Теорема 12. Нехай R та R₁ – часткові порядки на А. Довести, що:

а) RR₁ – частковий порядок на А;

б) R^-1 – частковий порядок на А.

Доведення. Покажемо, що відношення RR₁ рефлексивне, анти-симетричне, транзитивне. Оскільки R та R₁ – часткові порядки на А, то відношення R та R₁ рефлексивні, а тоді й відношення RR₁ рефлексив-не. Нехай <x,y>RR₁ та <y,x>RR₁. Тоді <х,у>R й <у,х>R, звідки х=у в силу антисиметричності R. Нехай <x,y>RR₁ та <y,z>RR₁. Тоді <x,y>R, <y,z>R, <x,y>R₁, <y,z>R₁, звідки <x,z>R та <x,z>R₁ в силу транзитивності R та R₁. Отже, <x,z>RR₁. Таким чином, RR₁ є частковим порядком на А.

Як відомо (див. задачі V, VIII, X до розділу «Види бінарних відно-шень»), відношення R^-1 рефлексивне, антисиметричне та транзитивне, якщо таким є відношення R, отже, відношення, обернене до часткового порядку, є частковим порядком.

Бінарне відношення R, задане на множині А, називається відно-шенням строгого порядку на А (строгим порядком на А), якщо R антирефлексивне та транзитивне. Часто відношення строгого порядку позначається символом <.

Наприклад, відношення {<1,2>,<1,3>,<1,4>} є строгим порядком на множині {1,2,3,4,5}. Прикладами відношень строгого порядку на множині N є відношення < та >. Відношення Р на множині людей, задане умовою хРу  х є предком у, є антирефлексивним та транзитив-ним, отже, є відношенням строгого порядку. Відношення М на множині людей, задане умовою хМу  х – мати у, є антирефлексивним, але не є транзитивним, отже, й не є відношенням строгого порядку.

Бінарне відношення R, задане на множині А, називається відно-шенням передпорядку на А (передпорядком на А), або відношенням квазіпорядку на А (квазіпорядком на А), якщо R рефлексивне та транзитивне.

Зрозуміло, що будь-який частковий порядок на множині А є та-кож передпорядком на А.

Наприклад, відношення R={<1,1>,<2,3>,<2,2>,<3,2>,<3,3>} та S={<2,2>,<2,3>,<3,3>,<1,1>} є передпорядками на множині А={1,2,3}; S є частковим порядком на А, а R – ні. Відношення строгого порядку не є передпорядком. Відношення {<1,1>,<2,2>,<3,3>,<2,1>,<3,2>} на множи-ні А={1,2,3} не транзитивне, отже, не є передпорядком на А.

Нехай R – частковий порядок на А. Елементи х та у множини А називаються такими, що порівнюються відносно часткового порядку R, якщо <x,y>R або <y,x>R.

Розглянемо, наприклад, частковий порядок R={<1,1>,<1,2>,<2,2>, <3,3>} на множині A={1,2,3}. Оскільки хRх для кожного елемента х з множини А, то 1 та 1, 2 та 2, 3 та 3 порівнюються відносно R. Елементи 1 та 2 також порівнюються відносно R. 1 та 3, а також 2 та 3 не порівню-ються відносно R. Розглянемо відношення включення на булеані мно-жини {a,b,c}. Оскільки {a}{b} й {b}{a}, то {a} та {b} не порівню-ються відносно .

Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються будь-які елементи х та у множини А. Множина, на якій задано лінійний порядок, називається лінійно упорядкованою, або упорядкованою, або ланцюгом.

Наприклад, лінійно упорядкованою є множина А={1,2,3}, на якій задано частковий порядок R={<1,1>,<2,2>,<3,3>,<1,3>,<3,2>,<1,2>}, оскільки R є лінійним порядком на А. Множина N з відношенням  є лінійно упорядкованою. Дійсно, якими б не були невід’ємні цілі числа n та m, завжди принаймні одне з тверджень nm чи mn є істинним, тобто будь-які числа n та m з множини N порівнюються відносно часткового порядку . Булеан множини {a,b,c}, на якому задано відношення включення, не є упоряд-кованою множиною, оскільки він містить елементи, що не порівнюють-ся відносно  (наприклад, {a} та {b}).

Нехай R – частковий порядок на множині А. Елемент х множини А називається мінімальним (максимальним) елементом відносно R, якщо для кожного елемента у множини А, що порівнюється з х, <x,y>R (<y,x>R).

Нехай, наприклад, на множині А={1,2,3} задано частковий поря-док R=і_А{<2,1>,<3,1>}. Знайдемо мінімальні та максимальні елементи множини А відносно заданого порядку R. Елемент 1 порівнюється з еле-ментами 1, 2, 3 й <1,1>, <2,1>, <3,1>R, отже, 1 є максимальним еле-ментом відносно R. Елемент 2 порівнюється з елементами 1 та 2 й <2,2>, <2,1>R, отже, 2 є мінімальним елементом відносно R. Елемент 3 порівнюється з елементами 1 та 3 й <3,3>, <3,1>R, отже, 3 є міні-мальним елементом відносно R. Розглянемо частковий порядок R₁=і_А{<3,1>,<1,2>,<3,2>} на множині А. Елемент 1 порівнюється з еле-ментами 1, 2, 3 й <1,1>, <1,2>R₁, але <1,3>R₁, отже, елемент 1 не є мінімальним відносно R₁. Елемент 1 не є також й максимальним віднос-но R₁, тому що <1,1>,<3,1>R₁, але <2,1>R₁. Мінімальним елементом відносно R₁ є елемент 3, тому що для усіх елементів, з якими він порів-нюється відносно R₁ (тобто для 1, 2 та 3) <3,1>, <3,2>, <3,3>R₁. Макси-мальним елементом відносно R₁ є елемент 2, оскільки <1,2>, <2,2>, <3,2>R₁.

Нехай R – частковий порядок на множині А. Елемент х множини А називається найменшим (найбільшим) елементом відносно R, якщо для кожного елемента у множини А <x,y>R (<y,x>R).

Нехай, наприклад, на множині А={1,2,3} задано частковий поря-док R=i_A{<1,2>,<2,3>,<1,3>}. Найменшим відносно R є елемент 1, ос-кільки він порівнюється з кожним елементом множини А й <1,1>, <1,2>, <1,3>R. Найбільшим відносно R є елемент 3, бо він порівнюється з кожним елементом множини А й <1,3>, <2,3>, <3,3>R. Множина N, лінійно упорядкована відношенням , має найменший елемент відносно . Таким елементом є число 0. Дійсно, для будь-якого nN 0n. Водно-час множина N не має найбільшого елемента відносно . Дійсно, не іс-нує невід’ємного цілого числа m такого, що для будь-якого nN nm. Множина Z, лінійно упорядкована відношенням , не має ні найменшо-го, ні найбільшого елементу відносно  (не існує такого цілого числа z, що для будь-якого хZ zх й не існує такого цілого числа у, що для будь-якого хZ ху). Множина N^- усіх від’ємних цілих чисел, лінійно упорядкована відношенням , має найбільший елемент відносно  (число –1), але не має найменшого елементу відносно .

Відношення лінійного порядку на множині А називається відно-шенням повного порядку (повним порядком) на А, якщо кожна непо-рожня підмножина множини А має найменший елемент відносно R. Множина А, на якій задано відношення повного порядку, називається повністю упорядкованою.

Прикладом відношення повного порядку є відношення  на мно-жині N. Дійсно, множина N має найменший елемент відносно  (це число 0) й кожна непорожня підмножина А множини N містить таке число m, що mx для будь-якого хА. Відношення  на множині Z не є повним порядком, адже Z не має найменшого елементу відносно .

Наведемо без доведення один з важливих результатів теорії множин.

Теорема 13 (теорема Цермело). Будь-яку непорожню множину можна повністю упорядкувати.

Частково упорядковані множини <A₁,R₁> та <A₂,R₂> називаються ізоморфними, якщо існує така бієкція F:A₁A₂, що для будь-яких еле-ментів х та у множини A₁ хR₁у  F(х)R₂F(у). Відображення F назива-ється ізоморфним відображенням множини <А₁,R₁> на множину <А₂,R₂>.

Нехай, наприклад, задані частково упорядковані множини <A₁,R₁>=<{a,b,c},{<a,a>,<b,b>,<c,c>,<a,b>,<a,c>}> та <A₂,R₂>=<{1,2,3}, {<1,1>,<2,2>,<3,3>,<3,2>,<3,1>}> й відображення F:A₁A₂, F={<a,3>, <b,1>,<c,2>}, яке, очевидно, є бієкцією. для кожної пари <x,y>, що нале-жить R₁, перевіримо, чи належить R₂ пара <F(x),F(y)>. Для пари <a,a> маємо:<F(a),F(a)>=<3,3,> й <3,3>R₂. Для пари <b,b>: <F(b),F(b)> =<1,1> й <1,1>R₂; для пари <c,c>: <F(c),F(c)>=<2,2> й <2,2>R₂; для пари <a,b>: <F(a),F(b)>=<3,1> й <3,1>R₂; для пари <a,c>: <F(a),F(c)>= =<3,2> й <3,2>R₂. Тепер для кожної пари <x,y>, що належить R₂, перевіримо, чи належить R₁ пара <F^-1(x),F^-1(y)>. Маємо для пари <1,1>: <F^-1(1),F^-1(1)>=<b,b,> й <b,b>R₁; для пари <2,2>: <F^-1(2),F^-1(2)>=<с,с> й <с,с>R₁; для пари <3,3>: <F^-1(3),F^-1(3)>=<а,а> й <а,а>R₁; для пари <3,2>: <F^-1(3),F^-1(2)>=<а,с> й <а,с>R₁; для пари <3,1>: <F^-1(3),F^-1(1)>= =<а,b> й <а,b>R₁. Отже, множини <A₁,R₁> та <A₂,R₂> ізоморфні.

Наведемо приклад неізоморфних частково упорядкованих мно-жин. Нехай <A,R>=<{a,b,c}, i_A{<a,c>,<a,b>}>, <B,S>=<{1,2,3}, i_B {<2,1>,<3,1>}>. Припустимо, що існує ізоморфне відображення F A на B. Позначимо х₁=F(a), x₂=F(b), x₃=F(c), де х₁, х₂, х₃ – різні елементи множини В. Оскільки <a,c>R, <a,b>R, то пари <х₁,х₃> та <х₁,х₂> мають належати S, але S не містить пар, що складаються з різних елементів й мають однакові перші компоненти, отже, наше припущення призвело до суперечності. Таким чином, <A,R> та <B,S> не ізоморфні.

Теорема 14. Будь-яка частково упорядкована множина <A,R> ізоморфна деякій множині множин, частково упорядкованій включенням.

Доведення. Нехай аА. Позначимо через S_a множину {x| xA, xRa}, а через S – множину {S_a| aA}. Покажемо, що відображення F:AS таке, що F(a)=S_a, є ізоморфним відображенням множини <A,R> на множину <S,>. Доведемо спочатку, що F є взаємно однозначним відображенням А на S. За побудовою кожен елемент а множини А має єдиний образ S_a. Покажемо, що відображення F ін’єктивне. Нехай а,bА й аb. Припустимо, що при цьому S_a=S_b. Оскільки відношення R рефлексивне, то аS_a, bS_b. S_a=S_b  bS_a, аS_b  bRa, aRb  a=b, але за припущенням аb, тобто маємо суперечність. Отже, F ін’єктивне. Покажемо, що F сюр’єктивне. Оскільки для довільного елементу а з А аS_a, то F^-1(S_a). Таким чином, F – взаємно однозначне відображення А на S. Нехай <a,b>R. Маємо: <F(a),F(b)>=<S_a,S_b>. Покажемо, що S_aS_b. zS_a  zRa. Оскільки <a,b>R й R транзитивне, то zRb, отже, zS_b. Таким чином, S_aS_b. Нехай S_aS_b. Покажемо, що <a,b>R. Зауважимо, що аS_a для будь-якого аА, адже відношення R рефлек-сивне. аS_a  аS_b  aRb. Таким чином, F є ізоморфним відображен-ням множини <A,R> на множину <S,>.

Дана теорема означає, що вивчення довільних частково упорядко-ваних множин можна без втрати загальності звести до вивчення систем множин, частково упорядкованих включенням. На практиці подібний перехід зазвичай не здійснюється, тому що в результаті були б втрачені властивості конкретних частково упорядкованих множин.