szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Teoria Krat
PostNapisane: 27 lip 2009, o 20:50 
Użytkownik

Posty: 5745
Lokalizacja: Kraków
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 X zwiemy "częsciowo uporzadkowanym" przez te relację R, wtedy gdy zachodzą w nim takie trzy warunki tj. zwrotność, przechodniosc i antysymetria, tj:
1)\forall  x\in  X x \le x
2) \forall  x,y, z \in  X x \le z  \wedge  z  \le  y  \Rightarrow  x \le y
3) \forall  x,y \in  X x \le y  \wedge  y  \le  x  \Rightarrow  x =y


Zamiast pisać x \leq y można też uzywac notacji (x,y) \in R. Tak więc R \subset X \times X. Relacje porzadkujące oznaczamy zwykle przez \leq. Elementy x, y zwiemy porównywalnymi , gdy x \leq y lub y \leq x. Jesli każde dwa elem. zbioru X sa porównywalne to X zwie się łańcuchem lub zbiorem liniowo uporzadkowanym. Element x_0 jest największy, gdy dla każdego x\in X mamy: x \leq x_0. Podobnie def. ma element najmniejszy. Jeśli teraz E \subset X to mowimy, ze zbiór E ma kres dolny a \in X, piszać a =inf E, gdy:
1. a \leq x dla x \in E
2. jesli b \leq x dla x \in E, to 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ą, x, y \in L, to kres dolny zbioru \{x, y\} oznaczamy x \wedge y, zaś kres górny tegoż zbioru przez x \vee y i zwiemy odpowiednio iloczynem i sumą x i y. A oto dwa "modelowe" przykłady krat:

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

Krata N, Zbiór liczb naturalnych z relacją podzielności stanowi kratę rozdzielna, w której a \wedge b to najwiekszy wspolny dzielnik liczb a,b zaś 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= \{ a,b, c, d \} uporządkowany przez relację S= \{ (a, a), (b,b), (c, c), (d, d), (a, c), (b, c), (c, d), (a, d), (b, d) \} nie jest kratą gdyz podzbiór \{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:

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 \geq. Zachodzi tez ciekawa własnośc (wkw. ) przysługująca tej klasie krat:
jesli x \wedge z = y \wedge z i x \vee z = y \vee z , to x=y



Definicja
Gdy krata (L, \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 x \in L to element a zwiemy uzupełnieniem x, w ograniczonej kracie L gdy: 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 x ma uzupełnienie (oznaczane: -x), nazywamy algebrą Boole'a. Tak wiec mamy w algebrze Boole'a:

x \vee -x =1 \ , x \wedge -x =0


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


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


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

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

Obrazek


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

Obrazek


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

Obrazek


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 (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 R,. Relacja porzadkujaca \leq jest okreslona tak :
f \leq g, wtw., gdy f(x) \leq g(x) dla 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 x \leq y
b x \wedge y = x
c x \vee y =y
5. 1) Dany mamy zbior X = \{ 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, 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 X=\{a, b, c \} Wykazać, ze krata (P(X), \subset) nie ma siedmioelementowej podkraty.

:arrow: Ewentualne, błedy l, literowki, uzupełnienia , etc , prosze kierowac na priv. :D
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Teoria liczb] teoria liczb warsztaty  zbyszek96  1
 [Teoria liczb] Początek zapisu dziesiętnego  mr97  4
 Pasmowa teoria budowy metali  Anonymous  0
 [Teoria liczb][Równania] dwa równania z KMDO  nierozumiemfizy  23
 [Teoria liczb] Znajdz wszystkie n. Silnia  chris139  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl