Приклад 1.18. 1. У множині Z цілих чисел множина N натуральних чисел має найменший елемент (число 1) і не має найбільшого елемента.
2. У довільній множині M з тривіальним порядком iM (відношенням рівності) кожен елемент aÎM є одночасно максимальним і мінімальним елементом. Найбільший і найменший елементи в множині M відсутні.
3. Булеан b(A) множини A з відношенням часткового порядку містить найменший елемент - порожню множину і найбільший елемент - саму множину A. У множині D всіх непорожніх підмножин множини A (тобто в множині b(A)\{Æ}) не існує найменшого елемента, але всі одноелементні множини {a}, aÎA є мінімальними елементами множини D.
4. У множині N натуральних чисел, частково впорядкованій за відношенням "ділить", число 1 є найменшим елементом, а найбільшого елемента не існує. Якщо ж множину N доповнити числом 0, тобто розглянути множину невід'ємних цілих чисел із відношенням часткового порядку "ділить", то окрім найменшого елемента (як і раніше, число 1) з'являється найбільший елемент - число 0.
Лінійно впорядкована множина (ланцюг) M називається цілком впорядкованою множиною, якщо кожна непорожня підмножина AÍM має найменший елемент.
Зокрема, множина N натуральних чисел з традиційним відношенням порядку є цілком впорядкованою, а множина Z цілих чисел - не є цілком впорядкованою, оскільки будь-яка її нескінченна підмножина від'ємних чисел не має найменшого елемента.
Якщо M - частково впорядкована множина, то множина L всіх її ланцюгів (тобто лінійно впорядкованих підмножин множини M) є також частково впорядкованою за відношенням теоретико-множинного включення. Максимальні елементи множини L називають максимальними ланцюгами множини M.
Наведемо ряд важливих тверджень про частково впорядковані множини, які часто застосовуються у вищій алгебрі, математичному аналізі, топології та інших розділах сучасної математики.
Теорема Куратовського-Цорна або лема Цорна. Якщо в частково впорядкованій множині M будь-який ланцюг має верхню (нижню) грань, то множина M має максимальний (мінімальний) елемент.
Теорема Хаусдорфа. Будь-який ланцюг частково впорядкованої множини M міститься в деякому максимальному ланцюзі множини M.
Теорема Цермело. Будь-яку множину M можна цілком впорядкувати.
Можна довести, що всі три наведені теореми еквівалентні між собою (тобто зі справедливості будь-якої з них випливає справедливість двох інших), і що всі вони в свою чергу еквівалентні одній з фундаментальних аксіом сучасної аксіоматичної теорії множин, так званій аксіомі вибору.
Аксіома вибору. Якщо дано множину M, то існує функція w:( b(M)\{Æ}) ®M, яка кожній непорожній підмножині AÍM ставить у відповідність певний елемент a = w(A) цієї підмножини, aÎA.
Iнакше кажучи, функція w обирає по одному елементу з непорожніх підмножин множини M.
Зокрема, аксіомою вибору ми неявно користувались при доведенні теореми 1.2.
Будь-яке твердження T відносно елементів деякої цілком впорядкованої множини M можна доводити, використовуючи так звану трансфінітну індукцію, яка є узагальненням відомого методу математичної індукції.
База індукції. Доводимо справедливість твердження T для найменшого елемента множини M.
Iндукційний крок. Робимо припущення, що твердження T виконується для будь-якого елемента a такого, що a<b і доводимо справедливість твердження T для елемента b.
Якщо виконуються умови бази і індукційного кроку, то твердження T справедливе для довільного елемента aÎM.
Припустімо, що це не так. Нехай в множині M існують елементи, для яких не виконується твердження T і KÍM - сукупність усіх таких елементів. Множина M цілком впорядкована, отже K має найменший елемент bÎK. Зі справедливості умови бази індукції випливає, що b не є найменшим елементом у множині M. Це означає, що в множині M існують елементи a<b і для всіх таких елементів a виконується твердження T. Згідно з індукційним кроком твердження T повинно виконуватись і для елемента b, що призводить до суперечності.
14. Решітки
Серед частково впорядкованих множин винятково важливу роль відіграють так звані решітки або структури.
Точною верхньою гранню підмножини A частково впорядкованої множини M (позначається supA) називають найменшу з верхніх граней підмножини A. Відповідно, точною нижньою гранню підмножини A частково впорядкованої множини M (позначається infA) називають найбільшу з нижніх граней підмножини A.
Частково впорядкована множина M називається решіткою (структурою), якщо для будь-якої пари елементів a,bÎM (тобто для будь-якої двоелементної підмножини множини M ) існують sup{a,b} і inf{a,b}.
Приклад 1.19. 1. Будь-яка лінійно впорядкована множина M (наприклад, числові множини N, Z, Q і R з традиційними відношеннями порядку) є решіткою. Якщо 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. Частково впорядкована за відношенням включення множина b(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;
б) булеана b (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 має вигляд