Решетки

Решетката е наредено множество, допълнено със свойството, че за всеки два елемента от дадената решетка трябва да съществуват супремум и инфимум, които също принадлежат на дадената решетка.

Горен и долен конус

В началото имаме множество M, върху което е определена някаква наредба ≤. Тази наредба може да е произволна, но трябва да удовлетворява условията за релация на наредба.

След това вземаме някакъв елемент a от множеството M. Горния конус на елемента a в множеството M определяме като всички x ∈ M, които са по-големи или равни на a, тоест за тях е изпълнено a ≤ x.

Ако за множество вземем естествените числа, а за елемент a = 7, горният конус е множеството от числа {7, 8, 9, …}. При реалните числа бихме получили интервала [7; +∞).

Да вземем множеството M = 2^ℕ – това е булеанът, тоест множеството на всички подмножества на естествените числа. Така това са всички множества, които можем да построим с естествени числа. Наредбата ще се породи от релацията подмножество. Така е изпълнено {3, 5} ≤ {3, 4, 5} и т.н.

Горният конус на множеството {1, 2, 3, 4} ще бъдат всички множества, които съдържат елементите 1, 2, 3, 4. Например множеството {1, 2, 3, 4, 5, 6, 9} или {1, 2, 3, 4, 2323, 454645}. В горния конус ще бъде и самото множество {1, 2, 3, 4}.

Долния конус определяме по аналогичен начин – той съдържа елементите, които са по-малки или равни на елемента a. За a = 7 и M естествените числа получаваме множеството {1, 2, 3, 4, 5, 6, 7}. Това са естествените числа, които са по-малки или равни на седем.

За множеството {1, 2, 3, 4} получаваме всички подмножества на това множество.

Горен и долен конус на няколко елемента

В предишната част определихме конусите за един елемент. Можем обаче да определим конус и за няколко елемента. Ако имаме множество M и елементи a, b, общият им горен конус ще съдържа елементите, които са по-големи или равни и на двата елемента a и b едновременно. С други думи, пресмятаме горните конуси на двата елемента и намираме сечението им. Така получаваме елементите, които със сигурност са по-големи от a и по-големи от b.

Ако останем при естествените числа: a = 3, b = 5. Всички елементи, по-големи или равни на a, образуват множеството {3, 4, 5, 6, …}, а на b: {5, 6, 7, 8, …}. Сега правим сечение и отново получаваме множеството {5, 6, 7, 8, …}. Ако имаме напълно наредено множество, достатъчно е да установим по-големия от двата елемента и да пресметнем неговия горен конус.

При множествата вече няма да е толкова просто. Можем да опитаме да пресметнем долния конус на множествата: a = {1, 2, 3} и b = {2, 3, 4}. Това са всички множества, които са едновременно подмножества на a и на b. Подмножество на a ли е например множеството {1, 2, 3}? Да. Подмножество на b ли е? Не. Това множество няма да е в долния конус.

Можем да опитаме да видим кое е най-голямото множество, което ще е подмножество и на a, и на b. Очевидно това е множеството {2, 3}, което се получава като сечение на множествата a ∩ b. То ще е в долния конус. И всички подмножества на това множество също. Защото ако например ∅ ⊆ {2, 3} и {2, 3} ⊆ a ∧ {2, 3} ⊆ b, то със сигурност и ∅ ⊆ a ∧ ∅ ⊆ b. Това следва от транзитивността.

Накрая определяме горния и долния конус за цяло множество, не само за двойка елементи. Нека имаме множество M и някакво множество A ⊆ M, за което искаме да пресметнем горния и долния конус. Тогава е изпълнено:

$$\begin{array}{rcl}H(A)& =& \{x|\mathrm{\forall }a\in A:x\ge a\}\\ D(A)& =& \{x|\mathrm{\forall }a\in A:x\le a\}\end{array}$$

Супремум и инфимум

С помощта на конусите лесно можем да определим инфимум и супремум. Ако имаме множество M и елемент a ∈ M, то супремумът и инфимумът на елемента a са отново същият елемент a.

Ако обаче искаме да намерим супремума на два елемента от M, елементите a, b, вече трябва да действаме по друг начин. Супремумът на елементите a, b, означаваме го с a ∨ b или sup(a, b), е равен на най-малкия елемент от горния конус на елементите a, b. Тоест пресмятаме всички елементи, които са по-големи или равни на елементите a, b, и от тях вземаме най-малкия елемент. Не минималния, а най-малкия. В общия случай най-малък елемент не е задължително да съществува, така че и супремум не е задължително да съществува.

Ако пресмятаме инфимум, първо намираме долния конус на двата елемента и после намираме най-големия елемент.

Пример: вече знаем, че горният конус на числата 3 и 5 е множеството {5, 6, 7, …}. Най-малкият елемент е равен на пет. Така sup(3, 5) = 5.

Освен това знаем, че долният конус на множествата a = {1, 2, 3} и b = {2, 3, 4} е равен на множеството на всички подмножества на множеството {2, 3}. Това са множествата: {2, 3}, {2}, {3}, ∅. Най-голямото от тях е множеството {2, 3}. Това множество е инфимумът на множествата a, b. Означаваме a ∧ b = {2, 3} или inf(a, b) = {2, 3}.

Определение на решетка

Решетката S е наредено множество, в което за всеки два елемента a, b ∈ S съществуват супремум и инфимум, като този инфимум и супремум принадлежат на множеството S. Можем да запишем, че наредено множество S е решетка, ако

$$\mathrm{\forall }a,b\in S:sup(a,b)\in S\text{и}inf(a,b)\in S$$

Прост пример за решетка са реалните числа с класическата наредба. Изпълнено е sup(a, b) = max(a, b) и inf(a, b) = min(a, b), които са винаги реални числа.

Система от множества с наредба по релацията „да бъдеш подмножество“, каквато въведохме по-рано, също е решетка. Изпълнено е sup(a, b) = a ∪ b и inf(a, b) = a ∩ b. Това отново са множества от системата от множества.

Ако за система от множества S вземем всички двуелементни подмножества на естествените числа (напр. {1, 2}, {7, 19}, …), това множество не е решетка, защото например sup({1, 2}, {3, 4}) = {1, 2, 3, 4}, а множеството {1, 2, 3, 4} не е елемент на множеството на всички двуелементни подмножества на естествените числа.