Решітки, Детальна інформація

\x20AC

‚

†

\x02C6

\x017D

ue

th

: ( c і c ( b. Стрілки (петлі), що відповідають діагональним парам (a,a) не проводимо.

Приклад 2. 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.

Діаграма будь-якої скінченної лінійно впорядкованої множини 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. є решітками, тому що для їхніх діаграм не виконується жодна з наведених умов. Множина 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.)

Очевидно, що елементи 0 і 1 є відповідно найменшим і найбільшим елементами повної решітки M.