O pewnych kratach testowych

Teoria krat pojawiła się pod koniec XIX wieku, wyrastając z logiki i algebry. W logice kraty pojawiły się za sprawą George’a Boole’a, a w algebrze kraty pierwszy rozpatrywał Richard Dedekind. Kraty są przedmiotem badań algebraików, stanowią jednocześnie wygodny środek opisu znanych struktur matematycznych, których przykłady przedstawię w dalszej części artykułu.

Kraty można opisać na dwa sposoby: algebraicznie lub przy użyciu częściowych porządków.

Definicja 1. Krata w sensie algebraicznym to struktura algebraiczna $\text{[math]}$ spełniająca dla dowolnych elementów $\text{[math]}$ następujące równości:

$pict$

Krata w sensie częściowych porządków to niepusty częściowo uporządkowany zbiór $\text{[math]}$ w którym każdy dwuelementowy podzbiór ma oba kresy: górny i dolny.

Pojęcia krat w sensie algebraicznym i częściowych porządków są równoważne. Jeśli zdefiniujemy kratę jako zbiór algebraiczny z wymienionymi aksjomatami, to zadając porządek przez $\text{[math]}$ otrzymamy kratę w sensie porządku. Odwrotnie, jeśli w kracie w sensie porządku zdefiniujemy $\text{[math]}$ oraz $\text{[math]}$ to dostaniemy kratę w sensie algebraicznym.

Zanim omówię wybrane przykłady krat, podam kilka użytecznych definicji. Kratę $\text{[math]}$ będziemy zwykle oznaczali literą $\text{[math]}$ identyfikując ją ze zbiorem jej elementów. Jeśli w kracie $\text{[math]}$ istnieje element największy, to nazywamy go jednością kraty i oznaczamy przez $\text{[math]}$ Podobnie, najmniejszy element w kracie (jeśli istnieje) oznaczamy symbolem 0 i nazywamy zerem kraty. Kratę z zerem i jednością nazywamy kratą ograniczoną. Podzbiór $\text{[math]}$ kraty $\text{[math]}$ nazwiemy jej podkratą, jeśli dla dowolnych $\text{[math]}$ mamy $\text{[math]}$ oraz $\text{[math]}$ Powiemy, że kraty $\text{[math]}$ i $\text{[math]}$ są izomorficzne wtedy i tylko wtedy, gdy istnieje bijekcja $\text{[math]}$ taka że $\text{[math]}$ i $\text{[math]}$ zachowują porządek, tj. $\text{[math]}$

Zauważmy, że jeśli $\text{[math]}$ jest kratą, to para $\text{[math]}$ gdzie relacja $\text{[math]}$ zdefiniowana jest wzorem $\text{[math]}$ również jest kratą. Kratę $\text{[math]}$ będziemy nazywać kratą dualną do kraty $\text{[math]}$ i oznaczać symbolem $\text{[math]}$ Łatwo sprawdzić, że jeśli $\text{[math]}$ w kracie $\text{[math]}$ to $\text{[math]}$ w kracie $\text{[math]}$ oraz analogicznie jeśli $\text{[math]}$ w kracie $\text{[math]}$ to $\text{[math]}$ w kracie $\text{[math]}$

Przykład 1. Niech $\text{[math]}$ będzie dowolnym zbiorem. Rodzina $\text{[math]}$ wszystkich podzbiorów zbioru $\text{[math]}$ wraz z porządkiem zadanym przez inkluzję $\text{[math]}$ jest kratą. Mianowicie, jeśli $\text{[math]}$ to $\text{[math]}$ oraz $\text{[math]}$ Jest to krata ograniczona. Zerem tej kraty jest zbiór pusty, a jednością zbiór $\text{[math]}$

Przykład 2. Niech $\text{[math]}$ oznacza relację podzielności w zbiorze $\text{[math]}$ dodatnich liczb całkowitych. Niech $\text{[math]}$ tradycyjnie oznacza największy wspólny dzielnik liczb $\text{[math]}$ i $\text{[math]}$ oraz $\text{[math]}$ ich najmniejszą wspólną wielokrotność. Zbiór uporządkowany $\text{[math]}$ jest kratą z działaniami $\text{[math]}$ oraz $\text{[math]}$ Krata ta ma element najmniejszy równy $\text{[math]}$ i nie ma elementu największego.

Przykład 3. Niech $\text{[math]}$ będzie przestrzenią liniową nad ciałem $\text{[math]}$ i niech $\text{[math]}$ oznacza rodzinę wszystkich jej podprzestrzeni. Zbiór $\text{[math]}$ jest kratą. Jeśli $\text{[math]}$ to $\text{[math]}$ oraz $\text{[math]}$ gdzie $\text{[math]}$ i $\text{[math]}$ Zerem w tej kracie jest wektor zerowy, a jedynką cała przestrzeń $\text{[math]}$ Podobnie, kratami są również: rodzina podgrup zadanej grupy, rodzina jej dzielników normalnych oraz rodzina podpierścieni danego pierścienia, wszystko z relacją inkluzji.

Przykład 4. Niech $\text{[math]}$ będzie rodziną podzbiorów przestrzeni $\text{[math]}$ złożoną ze zbioru pustego, całej przestrzeni $\text{[math]}$ oraz wszystkich punktów i wszystkich prostych w $\text{[math]}$ Zbiór ten z relacją zawierania stanowi kratę ograniczoną. Zerem tej kraty jest zbiór pusty, a jednością $\text{[math]}$

Kraty, tak jak wszystkie porządki, możemy ilustrować za pomocą diagramów, które tworzymy w następujący sposób: elementy kraty $\text{[math]}$ zaznaczamy na płaszczyźnie jako punkty. Jeśli $\text{[math]}$ są elementami kraty $\text{[math]}$ oraz $\text{[math]}$ to punkt odpowiadający elementowi $\text{[math]}$ rysujemy poniżej punktu odpowiadającego elementowi $\text{[math]}$ Jeśli $\text{[math]}$ jest następnikiem $\text{[math]}$ czyli $\text{[math]}$ oraz nie istnieje $\text{[math]}$ taki że $\text{[math]}$ to punkty $\text{[math]}$ i $\text{[math]}$ łączymy odcinkiem.

Przyjrzyjmy się diagramom z rysunku 1. Widzimy, że na diagramie (a) elementy $\text{[math]}$ i $\text{[math]}$ nie mają kresu górnego, a w przypadku diagramu (b) elementy $\text{[math]}$ i $\text{[math]}$ nie mają kresu dolnego. Na diagramie (c) elementy $\text{[math]}$ i $\text{[math]}$ mają dwa ograniczenia górne $\text{[math]}$ i $\text{[math]}$ ale nie mają kresu górnego. Zatem diagramy te nie przedstawiają krat.

Wskażemy teraz diagramy porządków będących kratami. Oczywiście, każdy liniowo uporządkowany zbiór (często nazywany łańcuchem) jest kratą. Łatwo można sprawdzić, że kraty o co najwyżej trzech elementach muszą być łańcuchami.

Kraty o czterech elementach są tylko dwie (z dokładnością do izomorfizmu), a krat pięcioelementowych jest dokładnie pięć (Rys. 3 i 4).

W matematyce ważną rolę spełniają kraty rozdzielne i modularne.

Definicja 2. Kratę $\text{[math]}$ nazywamy modularną, gdy dla dowolnych jej elementów $\text{[math]}$ takich że $\text{[math]}$ zachodzi $\text{[math]}$

Definicja 3. Kratę $\text{[math]}$ nazywamy rozdzielną (dystrybutywną), gdy dla dowolnych jej elementów $\text{[math]}$ spełniona jest równość $\text{[math]}$

Wprost z definicji wynika, iż każda krata rozdzielna jest modularna. Zwróćmy uwagę, że wszystkie łańcuchy są kratami rozdzielnymi. Rozważmy kratę z przykładu 1 – równość z definicji kraty rozdzielnej w przypadku kraty $\text{[math]}$ ma postać dobrze znanego prawa rozdzielności przecięcia zbiorów względem dodawania $\text{[math]}$ zatem krata $\text{[math]}$ jest rozdzielna. W tym przypadku nie napotkaliśmy problemów z wykazaniem tej własności, często jednak sprawdzenie wprost z definicji, czy dana krata jest dystrybutywna bądź modularna, jest dość kłopotliwe. Na szczęście istnieją niezwykle obrazowe i przydatne twierdzenia sprowadzające problem do pytania, czy wśród jej podkrat znajdują się pewne wymienione wcześniej kraty.

Twierdzenie 1. Krata $\text{[math]}$ jest modularna wtedy i tylko wtedy, gdy nie ma podkraty izomorficznej z $\text{[math]}$ (Rys. 4).

Szkic dowodu. Łatwo zauważyć, że jeśli $\text{[math]}$ ma podkratę izomorficzną z $\text{[math]}$ to nie jest modularna. Załóżmy teraz, że $\text{[math]}$ nie jest modularna, tzn. istnieją $\text{[math]}$ takie że $\text{[math]}$ gdzie $\text{[math]}$ i $\text{[math]}$ Z założenia $\text{[math]}$ oraz oczywistych relacji $\text{[math]}$ $\text{[math]}$ i $\text{[math]}$ w prosty sposób wynika $\text{[math]}$ więc $\text{[math]}$ Wykażemy, że $\text{[math]}$ wraz z $\text{[math]}$ i $\text{[math]}$ tworzą kratę izomorficzną z $\text{[math]}$ Najpierw upewnimy się, że $\text{[math]}$ i $\text{[math]}$ są różne od reszty wyszczególnionych elementów – istotnie, gdyby było $\text{[math]}$ to mielibyśmy $\text{[math]}$ co jest niemożliwe; podobnie dowodzimy, że $\text{[math]}$ Ponadto $\text{[math]}$ byłoby równoznaczne z $\text{[math]}$ skąd $\text{[math]}$ czyli $\text{[math]}$ co jak już wiemy, jest niemożliwe; analogicznie $\text{[math]}$ Korzystając z własności działań kratowych, otrzymujemy

display-math

i analogicznie $\text{[math]}$ Ponadto, skoro zachodzi $\text{[math]}$ to

display-math

tak więc $\text{[math]}$ Podobnie dowodzimy $\text{[math]}$ co w połączeniu z wykazanymi wcześniej zależnościami prowadzi nas już do wniosku, że wskazane elementy faktycznie tworzą podkratę izomorficzną z $\text{[math]}$

W analogiczny, choć nieco bardziej skomplikowany sposób, otrzymujemy podobny wynik dla krat rozdzielnych.

Twierdzenie 2. Krata $\text{[math]}$ jest rozdzielna wtedy i tylko wtedy, gdy nie ma podkraty izomorficznej z $\text{[math]}$ lub $\text{[math]}$ (patrz Rys. 4).

Z podanych twierdzeń w prosty sposób wynika, że jeśli krata $\text{[math]}$ jest modularna (rozdzielna), to krata $\text{[math]}$ również jest modularna (rozdzielna).

Weźmy teraz kratę z przykładu 3. Gdyby $\text{[math]}$ nie była modularna, to w kracie tej istniałaby podkrata izomorficzna z $\text{[math]}$ Istniałyby zatem parami różne podprzestrzenie $\text{[math]}$ takie że $\text{[math]}$ $\text{[math]}$ oraz $\text{[math]}$ Nie jest to jednak możliwe, co pozostawiam Czytelnikowi Podejrzliwemu jako nietrudne zadanie z algebry liniowej. Krata $\text{[math]}$ jest zatem kratą modularną, jednocześnie łatwo wykazać, że nie jest to krata rozdzielna. Weźmy przestrzeń $\text{[math]}$ wymiaru dwa i trzy jej różne jednowymiarowe podprzestrzenie $\text{[math]}$ Podprzestrzenie $\text{[math]}$ przecinają się w wektorze zerowym i każde dwie z nich generują $\text{[math]}$ Dostajemy zatem podkratę izomorficzną z $\text{[math]}$

Wykażemy teraz, że krata z przykładu 4 nie jest nawet modularna. Zauważmy, że jeżeli $\text{[math]}$ oznacza punkt leżący na prostej $\text{[math]}$ a przez $\text{[math]}$ oznaczymy prostą nieprzecinającą prostej $\text{[math]}$ to otrzymujemy podkratę:

Kraty modularne i rozdzielne są dokładnie opisane w literaturze i znamy wiele ich własności. Poza nimi rozważa się, oczywiście, wiele innych rodzajów tych struktur. Niektóre z nich dają się scharakteryzować poprzez zawieranie pewnej podkraty lub podkrat. Te charakterystyczne obiekty (np. $\text{[math]}$ oraz $\text{[math]}$ ) to właśnie tytułowe kraty testowe.