Teoria Krat

Zbiór wzorów, definicji i najczęściej poruszanych problemów ze Zbiór-ki.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 8433
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2744 razy
Pomógł: 702 razy

Teoria Krat

Post autor: mol_ksiazkowy » 27 lip 2009, o 21:50

Teoria krat jest niezwykle ciekawą ideą algebraiczną i celem tego omówienia jest podanie podstaw i głownych zagadnień dla tego działu. Opiera się ona na pojęciu relacji (porządku), jakie jest ogólnie znane, ale tym niemniej wszystko należy wprowadzic "od początku". Dość duża ilość przykłądow i ćwiczen pozwoli nam, szybko zrozumiec na czym rzecz polega. Także -co ważne pewne prawidła dotyczace zbiorów i liczb naturalnych zostaną zapisane w jezyku nieco innym.
Wpierw trochę definicji czyli małe wprowadzenie:
Zbiór \(\displaystyle{ X}\) zwiemy "częsciowo uporzadkowanym" przez te relację \(\displaystyle{ R}\), wtedy gdy zachodzą w nim takie trzy warunki tj. zwrotność, przechodniosc i antysymetria, tj:
1)\(\displaystyle{ \forall x\in X}\) \(\displaystyle{ x \le x}\)
2) \(\displaystyle{ \forall x,y, z \in X}\) \(\displaystyle{ x \le z \wedge z \le y \Rightarrow x \le y}\)
3) \(\displaystyle{ \forall x,y \in X}\) \(\displaystyle{ x \le y \wedge y \le x \Rightarrow x =y}\)


Zamiast pisać \(\displaystyle{ x \leq y}\) można też uzywac notacji \(\displaystyle{ (x,y) \in R}\). Tak więc \(\displaystyle{ R \subset X \times X}\). Relacje porzadkujące oznaczamy zwykle przez \(\displaystyle{ \leq}\). Elementy x, y zwiemy porównywalnymi , gdy \(\displaystyle{ x \leq y}\) lub \(\displaystyle{ y \leq x}\). Jesli każde dwa elem. zbioru X sa porównywalne to X zwie się łańcuchem lub zbiorem liniowo uporzadkowanym. Element \(\displaystyle{ x_0}\) jest największy, gdy dla każdego \(\displaystyle{ x\in X}\) mamy: \(\displaystyle{ x \leq x_0}\). Podobnie def. ma element najmniejszy. Jeśli teraz \(\displaystyle{ E \subset X}\) to mowimy, ze zbiór E ma kres dolny \(\displaystyle{ a \in X}\), piszać \(\displaystyle{ a =inf E}\), gdy:
1. \(\displaystyle{ a \leq x}\) dla \(\displaystyle{ x \in E}\)
2. jesli \(\displaystyle{ b \leq x}\) dla \(\displaystyle{ x \in E}\), to \(\displaystyle{ b \leq a}\) .
Mówiąc "opisowo" kres dolny to największe z "ograniczeń" dolnych zbioru-i analogicznie całkiem okreslamy kres górny zbioru, tj. jako najmniejsze z ograniczeń górnych, co jest intuicyjnie jasne.


Definicja
Zbiór L uporządkowany przez relację porządku nazwywa się kratą (ang. lattice) względem tej relacji, jeśli każdy dwuelementowy podzbiór L ma oba kresy: górny i dolny. Gdy L jest kratą, \(\displaystyle{ x, y \in L}\), to kres dolny zbioru \(\displaystyle{ \{x, y\}}\) oznaczamy \(\displaystyle{ x \wedge y}\), zaś kres górny tegoż zbioru przez \(\displaystyle{ x \vee y}\) i zwiemy odpowiednio iloczynem i sumą x i y. A oto dwa "modelowe" przykłady krat:

Krata \(\displaystyle{ P(X)}\), z relacją inkluzji \(\displaystyle{ \subset}\)- to rodzina wszystkich podzbiorów zbioru X. Jest to algebra Boole'a, w której działaniami \(\displaystyle{ \wedge, \ \vee , -}\), są tutaj zwykłe operacje teoriomnogosciowe: iloczynu sumy i uzupełnienia, a elementy wyróznione to \(\displaystyle{ 0=\emptyset , \ 1=X}\).

Krata N, Zbiór liczb naturalnych z relacją podzielności stanowi kratę rozdzielna, w której \(\displaystyle{ a \wedge b}\) to najwiekszy wspolny dzielnik liczb a,b zaś \(\displaystyle{ a\vee b}\) to najmniejsza wspolna wielokrotnosc a i b. Zerem tej kraty jest 1, jedności ta krata nie ma.

Przykład
Zbior X= \(\displaystyle{ \{ a,b, c, d \}}\) uporządkowany przez relację S= \(\displaystyle{ \{ (a, a), (b,b), (c, c), (d, d), (a, c), (b, c), (c, d), (a, d), (b, d) \}}\) nie jest kratą gdyz podzbiór \(\displaystyle{ \{a, b \}}\) nie ma kresu dolnego. Elementem największym w zbiorze X jest d, elem. najmniejszego brak. Z kolei przykładem nieskończnonego zbioru uporzadkowanego, który nie jest kratą jest zbior wszystkich kół na płaszczyznie z relacją inkluzji.


Klasyfikacje Krat
Zaopatrzeni w stosowne narzedzia mozemy w tym miejscu wprowadzić jeden z najważniejszych rodzajów krat. Mają one szeczególnie ciekawe wlasnosci. I tak mówimy że krata L jest dystrybutywna (lub rozdzielna), jesli dla dowolnych jej trzech elementów x, y, z zachodzi wzór:

\(\displaystyle{ x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)}\).

Uwaga: W dowolnej kracie można napisać- miedzy elementami wystepującymi w powyższym wzorze po obu stronach rownania- znak \(\displaystyle{ \geq}\). Zachodzi tez ciekawa własnośc (wkw. ) przysługująca tej klasie krat:
jesli \(\displaystyle{ x \wedge z = y \wedge z}\) i \(\displaystyle{ x \vee z = y \vee z}\) , to x=y



Definicja
Gdy krata (L, \(\displaystyle{ \leq}\)) na element najmniejszy, to zwie się on zerem tej kraty i oznaczamy go 0, a gdy L ma element największy, to zwiemy go jednością kraty L i oznaczamy 1. Kratę z zerem i jednością nazywamy ograniczoną.
Jesli \(\displaystyle{ x \in L}\) to element a zwiemy uzupełnieniem x, w ograniczonej kracie L gdy: \(\displaystyle{ a \vee x =1 \ , a \wedge x =0}\). Łatwo pokazać, że w kracie dystrybutywnej, takie uzupełnienie-o ile istnieje, jest jedyne. Wynika to wprost z definicji kraty. Kratę dystrybutywną z zerem i jednością, której każdy element \(\displaystyle{ x}\) ma uzupełnienie (oznaczane: \(\displaystyle{ -x}\)), nazywamy algebrą Boole'a. Tak wiec mamy w algebrze Boole'a:

\(\displaystyle{ x \vee -x =1 \ , x \wedge -x =0}\)


Poprzednik, atom i koatom
Niech \(\displaystyle{ L}\) będzie kratą, \(\displaystyle{ a, b \in L}\), \(\displaystyle{ a \leq b}\) i \(\displaystyle{ a \neq b}\). Mówimy, że \(\displaystyle{ a}\) poprzedza \(\displaystyle{ b}\) jeśli nie istnieje element \(\displaystyle{ c}\), który byłby różny od \(\displaystyle{ a}\) i od \(\displaystyle{ b}\) i taki, że \(\displaystyle{ a \leq c \leq b}\). Zapisujemy wtedy \(\displaystyle{ a \prec b}\). Z kolei zapis \(\displaystyle{ a \preceq b}\) oznacza iż \(\displaystyle{ a \prec b}\) lub \(\displaystyle{ a= b}\).
Element \(\displaystyle{ p}\) kraty \(\displaystyle{ L}\) z \(\displaystyle{ 0}\) (zerem), nazywamy atomem, gdy \(\displaystyle{ 0 \prec p}\). Zbiór wszystkich atomów kraty \(\displaystyle{ L}\) oznaczamy \(\displaystyle{ AtL}\). Jesli zaś krata \(\displaystyle{ L}\) ma \(\displaystyle{ 1}\) (jedność) , to gdy element \(\displaystyle{ q}\) spełnia \(\displaystyle{ q \prec 1}\) to zwie się koatomem kraty \(\displaystyle{ L}\). Mówimy iż krata \(\displaystyle{ L}\) z zerem \(\displaystyle{ 0}\) jest atomowa, jeśli zbiór \(\displaystyle{ \{ x: 0 \leq x \leq b \}}\) ma atom przy dowolnym \(\displaystyle{ b \neq 0}\)
Przykład
Atomami w kracie \(\displaystyle{ P(x)}\) z realacja inkluzji \(\displaystyle{ \subset}\) są wszystkie jednoelementowe podzbiory \(\displaystyle{ X}\). W kracie \(\displaystyle{ N}\) z relacją podzielności atomami są liczby pierwsze.


UCC i LCC w kracie
Mówi się, ze krata \(\displaystyle{ L}\) spełnia warunek UCC (ang. upper covering condition), gdy dla dowolnych \(\displaystyle{ a,b,c \in L}\) jeśli \(\displaystyle{ a \prec b}\) to \(\displaystyle{ a \vee c \preceq b \vee c}\).
Dualnie krata \(\displaystyle{ L}\) spełnia warunek LCC (ang. lower covering condition), gdy dla dowolnych \(\displaystyle{ a,b,c \in L}\) jeśli \(\displaystyle{ a \prec b}\) to \(\displaystyle{ a \wedge c \preceq b \wedge c}\).
Przykład
Dowolna krata modularna spełnia UCC i LCC. Krata \(\displaystyle{ N_5}\) nie spełnia UCC ani LCC.


Definicja
Jeżeli krata (L, \(\displaystyle{ \leq}\)) przy założeniu \(\displaystyle{ y \leq x}\) spełnia warunek \(\displaystyle{ x \wedge (y \vee z) = y \vee (x \wedge z)}\) to zwiemy ją modularną.
:arrow: Dowolna krata dystrybutywna jest modularna.
Krata \(\displaystyle{ M_3}\) jest modularna, krata \(\displaystyle{ N_5}\) nie jest modularna, gdyż \(\displaystyle{ c \leq a}\) i \(\displaystyle{ a \wedge (b \vee c)= a}\), ale \(\displaystyle{ (a \wedge b ) \vee c= c}\)
Kratę \(\displaystyle{ L}\) nazywamy półmodularną, jeśli dla jej dowolnych elementów \(\displaystyle{ x, y \in L}\) zachodzi implikacja \(\displaystyle{ x \wedge y \prec x \Rightarrow y \prec x \vee y}\)
Przykłady
Dowolna krata modularna jest półmodularna.
Krata \(\displaystyle{ S_7}\) (tzw. sześciokąt) jest półmodularna.
Krata \(\displaystyle{ Part(X)}\) też jest półmodularna

Wizualizacja -przyklady krat skończonych
:arrow: Rys 1 diagram kraty \(\displaystyle{ N_5}\) zwanej pięciokątem- lewy, diagram kraty \(\displaystyle{ M_3}\) zwanej diamentem- prawy




:arrow: Rys 2 diagram kraty \(\displaystyle{ S_7}\) zwanej sześciokątem- górny,
dwa przykłady skończonych krat półmodularnych-dolny




:arrow: Rys 3 diagram kraty \(\displaystyle{ M_2}\) -lewy, krata konfgruencji \(\displaystyle{ Con(N_5)}\)- prawy




Szersze omówienie terii krat znalezc mozna m.in w ksiazkach: G. Birkhoff, Lattice Theory, G. Gratzer General Lattice theory, G. Szasz, Introduction to lattice theory, Z. Moszner, O teorii relacji, i T. Traczyk, Wstep do teorii algebr Boole'a oraz A. Walendziak Podstawy algebry ogólnej i teorii krat .


Zadania do samodzielnego rozwiazania
1. Niech symbol \(\displaystyle{ (Part(X), \subset)}\) oznacza zbior wszystkich relacji równowaznosci na zb. X. Wykaż iż jest to krata-ze wzgledu na relacje inkluzji- i zbadaj jej własnosci, np czym są relacje totalna i pusta w tej kracie ?!
2. Wezmy jako F zbior wszystkich funkcji rzeczywistych o dziedzinie \(\displaystyle{ R}\),. Relacja porzadkujaca \(\displaystyle{ \leq}\) jest okreslona tak :
\(\displaystyle{ f \leq g}\), wtw., gdy \(\displaystyle{ f(x) \leq g(x)}\) dla \(\displaystyle{ x \in R}\). Wykaz, iz w F nie ma elementow najwiekszego i najmniejszego, ale jest to krata.
3. Okreslmy Y jako rodzinę utworzoną ze zbioru pustego i wszystkich przedziałow. Jest to krata (relacja inkluzji). Wykaż ze nie jest ona dystrybutywna.
4. Zauwaz, iz kazdy zbior liniowo uporzadkowany jest krata, (czy musi byc rozdzielna ?) a nastepnie wykaz ze w dowolnej kracie ma miejsce fakt: nastepujace trzy warunki sa sobie rownowazne
a \(\displaystyle{ x \leq y}\)
b \(\displaystyle{ x \wedge y = x}\)
c \(\displaystyle{ x \vee y =y}\)
5. 1) Dany mamy zbior X = \(\displaystyle{ \{ a, b, c, d, e \}}\) wykaz ze z relacją R okresloną ponizej X jest algebra Boole'a., podaj zero i jedność, a nastepnie znajdz uzupełnienie każdego elementu. Wreszcie narysuj jaj diagram (graf) *
R= {(a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (b,c), (b,d), (c,d), (e,d) }
2) Wróć do przykłądu z relacją S (nie kraty- skończonej). Podaj jej graf i przekonaj sie ze ma on kształt "trójnogu" tj. "odwroconej litery Y", zwroc uwage na połozenie elem. a i b.
*Uwaga: Graf relacji porzadkujacej określonej na skończonym zbiorze X rysuje się jak ponizej: gdy x,y są różne, \(\displaystyle{ x \leq y}\) i nie mozna "wcisnąć" miedzy nie żadnego elementu z, to fakt ten oznacza sie łaczac punkty x i y odcinkiem i zaznaczajac y powyzej x.
6. Zbadaj które z wyzej omawianych tu przykładów krat są modularne.
7. Narysuj diagramy pięciu nieizomorficznych krat pięcioelementowych. Narysuj diagram kraty wszystkich podzbiorów zbioru czteroelementowego.
8. Niech \(\displaystyle{ X=\{a, b, c \}}\) Wykazać, ze krata \(\displaystyle{ (P(X), \subset)}\) nie ma siedmioelementowej podkraty.

:arrow: Ewentualne, błedy l, literowki, uzupełnienia , etc , prosze kierowac na priv. :D

ODPOWIEDZ