WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Множини і відношення - Курсова робота

Множини і відношення - Курсова робота

порядку) є решіткою. Якщо a,b M, то sup{a,b} = max(a,b) і inf{a,b} = min(a,b).
2. Розглянемо множину N натуральних чисел з відношенням часткового порядку "ділить". Для a,b N означимо sup{a,b} = НСК(a,b) і inf{a,b) = НСД(a,b) (НСК - найменше спільне кратне, НСД - найбільший спільний дільник). Тоді sup{12,32 }=96, inf{12,32}= 4, inf{16,27}=1.
3. Частково впорядкована за відношенням включення множина (M) всіх підмножин множини M є решіткою: sup{A,B}=A B і inf{A,B}= A B, A,B M.
4. Розглянемо множину R кортежів дійсних чисел довжини n з відношенням часткового порядку, означеним у прикладі 1.17(4), тобто (a1,a2,...,an) (b1,b2,...,bn) тоді і тільки тоді, коли ai bi, i=1,2,...n. Частково впорядкована у такий спосіб множина R є решіткою:
sup{( a1,a2,...,an),( b1,b2,...,bn)} = (c1,c2,...,cn),
де ci = max(ai,bi ), i=1,2,...n,
inf{( a1,a2,...,an),( b1,b2,...,bn)} = (d1,d2,...,dn),
де di = min(ai,bi ), i=1,2,...,n.
Аналогічно можуть бути перетворені на решітки множини кортежів Nn, Zn, Qn і Bn, де B = {0,1 } - множина двійкових цифр.
Множина P = {R1,R2,...,Rm} всіх можливих розбиттів деякої скінченної множини M може бути перетворена в решітку в такий спосіб. Вважаємо, що розбиття Ri={Ai1,Ai2,..., Aik} і Rj={Aj1,Aj2,...,Ajk} знаходиться у відношенні Ri < Rj, якщо кожен клас Ait, t=1,2,...,k розбиття Ri міститься в деякому класі Ajt розбиття Rj. Наприклад, для M ={1,2,3,4,5} розбиття R'={{1,2},{3},{4,5}} менше розбиття R''={{1,2,3},{4,5}} і менше розбиття R'''={{1,2},{3,4,5}}, а розбиття R'' і R''' непорівнювані.
Мінімальним елементом частково впорядкованої множини P є розбиття { {a} | a M}, а максимальним елементом - {M}. Тоді sup{Ri,Rj} = Rk, де Rk - розбиття, в якому елементи a,b M входять в один клас тоді і тільки тоді, коли існує такий c M, що кожна з пар елементів a і c та c і b належить одному класу або в Ri, або в Rj ; inf{Ri,Rj} = Rl, де Rl - розбиття, в якому елементи a,b M належать одному класу тоді і тільки тоді, коли вони належать одному класу і в Ri, і в Rj.
Наприклад,
sup{R'',R'''} = {{1,2,3,4,5}}, sup{R',R''} = {{1,2,3},{4, 5}},
inf{R'',R'''} = {{1,2},{3},{4,5}}, inf{R',R''} = {{1,2},{3},{4,5}}.
Оскільки за теоремою 1.10 існує взаємно одозначна відповідність між усіма розбиттями даної множини M і всіма відношеннями еквівалентності на M, то множина всіх відношень еквівалентності на M може бути перетворена в решітку.
Скінченну частково впорядковану множину M зручно зображати у вигляді діаграми або структурного графа, вершини якого відповідають елементам множини M. З вершини a проводимо стрілку у вершину b, якщо a b і не існує такого c, що a c і c b. Стрілки (петлі), що відповідають діагональним парам (a,a) не проводимо.
Приклад 1.20. 1. На рис.1.6 зображено діаграми для чотирьох частково впорядкованих множин:
а) множини двійкових кортежів B3;
б) булеана (M) множини M = {a,b,c} з відношенням включення ;
в) множини натуральних чисел C={2,5,7,10,28,70} з відношенням "ділить";
г) множини D={a,b,c,d} з відношенням часткового порядку R={(a,a),(b,b),(c,c), (d,d),(a,c),(b,c),(a,d), (b,d)}.
а) б) в) г)
Рис.1.6.
2. Діаграма будь-якої скінченної лінійно впорядкованої множини M={a1,a2,...,an}, ai ai+1, i=1,2,...,n-1 має вигляд
______________________ ...... __________
a1 a2 a3 an-1 an
Неважко переконатись, що a b, a,b M тоді і тільки тоді, коли в діаграмі частково впорядкованої множини M існує складений зі стрілок шлях, що веде з вершини a у вершину b. Верхня грань для {a,b} - це елемент, в який ведуть шляхи з a і з b. Нижня грань {a,b} - це елемент, з якого існують шляхи і в a, і в b.
Частково впорядкована множина не є решіткою тоді, коли
1) деяка пара елементів не має верхньої або нижньої грані;
2) для деякої пари елементів найменша верхня (або найбільша нижня) грань не існує.
Наприклад, перші дві множини B і (M) з прикладу 1.20 є решітками, тому що для їхніх діаграм не виконується жодна з наведених умов. Множина C не є решіткою, оскільки, наприклад, для пар {2,5}, {5,7}, {7,10} не існують нижні грані, а пари {10, 28} і { 28,70} не мають верхніх граней. Пара елементів {a,b} ({c,d}) множини D має дві верхні (дві нижні) грані c і d (відповідно a і b), однак не має найменшої верхньої (найбільшої нижньої) грані, оскільки елементи c і d (a і b) непорівнювані між собою.
Частково впорядкована множина M називається повною решіткою, якщо для будь-якої непорожньої підмножини A M в множині M існують найменша верхня грань sup A і найбільша нижня грань inf A. Очевидно, що довільна повна решітка є решіткою, але не будь-яка решітка є повною решіткою. Якщо M - повна решітка, то найменша верхня грань усієї множини M (sup M) називається одиницею даної решітки і позначається 1, а найбільша нижня грань множини M (inf M) називається нулем решітки і позначається 0. Вибір цих назв для sup M і inf M пояснюється такими властивостями елементів 1 і 0.
Для довільного елемента a M виконується
sup {1,a} = 1, sup {0,a} = a, a 1,
inf {1,a} = a, inf {0,a} = 0, a 0. (1.10)
Очевидно, що елементи 0 і 1 є відповідно найменшим і найбільшим елементами повної решітки M.
Приклад 1.21. 1. Решітки B, (M) і P з прикладу 1.19 є повними решітками. Одиницями цих решіток будуть відповідно (1,1,1), M і {M}, а нулями - (0,0,0), і { {a} | a M }.
2. Множина N натуральних чисел не є повною решіткою, оскільки будь-яка її нескінченна підмножина на має найменшої верхньої грані.
3. Множина всіх дільників натурального числа n, частково впорядкована за відношенням "ділить", є повною решіткою. Одиницею в такій решітці є число n, а нулем - число 1.
15. Парадокси теорії множин
Слово "парадокс" грецького походження і перекладається українською мовою - несподіваний, дивний. Вживають це слово у відношенні до висловлювання (положення, ідеї), яке суттєво різниться від загальноприйнятого традиційного уявлення з даного приводу. Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені різними математиками в теорії множин Г.Кантора, є наївною спробою зменшити їхнє значення і надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Більш точно суть явища передає назва, "антиномії теорії множин", оскільки термін антиномія є синонімом терміна суперечність. Але за традицією, будемо називати сформульовані нижче положення парадоксами.
Парадокс Б.Рассела. Для будь-якої множини M коректним є питання: чи множина M належить собі як окремий елемент, тобто чи є множина M елементом самої себе, чи ні? Наприклад, множина всіх множин є множиною і тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.
Отже коректно поставити сформульоване питання і щодо множини всіх множин, які не будуть власними елементами. Нехай M - множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а сама множина M є елементом самої себе чи ні? Якщо припустити, що M M, то з означення множини M випливає M M. Якщо ж припустимо, що M M, то з того ж таки означення дістанемо M M.
Близьким до парадокса Рассела є так званий
Loading...

 
 

Цікаве