Krata (porządek)


Krata (matematyka) w encyklopedii

Z Wikipedii, wolnej encyklopedii (Przekierowano z Krata (porządek)) Przejdź do nawigacji Przejdź do wyszukiwania Dzielniki 60 tworzą kratę. Diagram Hassego kraty Tamriego. Warto zauważyć, iż punkty kraty tworzą wielościan, zwany angielskim terminem associahedron, co można przetłumaczyć jako „wielościan asocjacji”.

Kraty (ang. lattice) – struktury matematyczne, które można opisywać albo algebraicznie, albo w sensie częściowych porządków.

Spis treści

Struktura algebraiczna | edytuj kod

Krata w sensie algebraicznym to struktura algebraiczna ( A , , ) , {\displaystyle (A,\land ,\lor ),} gdzie A {\displaystyle A} jest (niepustym) zbiorem, a {\displaystyle \land } i {\displaystyle \lor } są odwzorowaniami z A × A {\displaystyle A\times A} w A {\displaystyle A} spełniającymi dla dowolnych x , y , z A {\displaystyle x,y,z\in A} następujące warunki:

Przykładem kraty jest dowolna algebra Boole’a.

W każdej kracie spełniona jest równoważność: x y = y x y = x . {\displaystyle x\lor y=y\Leftrightarrow x\land y=x.} Relacja , {\displaystyle \leqslant ,} zdefiniowana za pomocą równoważności

x y x y = y {\displaystyle x\leqslant y\Leftrightarrow x\lor y=y}

jest częściowym porządkiem, w którym każda para x , y {\displaystyle x,y} ma kres górny i kres dolny:

sup ( x , y ) = x y , inf ( x , y ) = x y . {\displaystyle \sup(x,y)=x\vee y,\quad \inf(x,y)=x\wedge y.} Krata permutacji zbioru czteroelementowego.

Niekonieczność aksjomatu 1 | edytuj kod

Aksjomat 1 podaje się tradycyjnie w definicji kraty, ale wynika on z aksjomatu 4:

Niech X := x y . {\displaystyle X:=x\lor y.} Wtedy na mocy lewej części aksjomatu 4 otrzymujemy

( X y ) y = y {\displaystyle (X\land y)\lor y=y}

a na mocy prawej:

X y = y {\displaystyle X\land y=y}

co po podstawieniu do poprzedniego wzoru daje:

y y = y . {\displaystyle y\lor y=y.}

Podobnie dowodzi się, że y y = y . {\displaystyle y\land y=y.}

Struktura porządkowa | edytuj kod

Krata w sensie częściowych porządków to (niepusty) częściowy porządek ( A , ) , {\displaystyle (A,\leqslant ),} w którym każda para x , y {\displaystyle x,y} ma kres dolny inf ( x , y ) {\displaystyle \inf(x,y)} i kres górny sup ( x , y ) . {\displaystyle \sup(x,y).}

Jeśli zdefiniujemy

x y := sup ( x , y ) , {\displaystyle x\lor y:=\sup(x,y),} x y := inf ( x , y ) , {\displaystyle x\land y:=\inf(x,y),}

to dostaniemy kratę w sensie algebraicznym, w której oczywiście

x y x y = y . {\displaystyle x\leqslant y\Leftrightarrow x\lor y=y.}

Półkraty | edytuj kod

Półkraty w sensie algebraicznym to dokładnie pasy przemienne, czyli półgrupy ( X , + ) {\displaystyle (X,+)} przemienne, w których równość x + x = x {\displaystyle x+x=x} zachodzi dla dowolnego x X . {\displaystyle x\in X.} Para ( X , ) , {\displaystyle (X,\leqslant ),} gdzie relacja {\displaystyle \leqslant } jest zdefiniowana przez

x y x + y = y , {\displaystyle x\leqslant y\Leftrightarrow x+y=y,}

nazywana jest półkratą górną (lub ∨-półkratą). Innymi słowy, jest to częściowy porządek, w którym każda para x , y {\displaystyle x,y} ma kres górny: sup ( x , y ) = x + y . {\displaystyle \sup(x,y)=x+y.}

Jeśli zdefiniujemy x y x + y = x , {\displaystyle x\leqslant y\Leftrightarrow x+y=x,} to otrzymamy półkratę dolną (lub ∧-półkratę), tzn. częściowy porządek, w którym każda para (x, y) ma kres dolny.

Podkraty | edytuj kod

Podkratą kraty ( K , , ) {\displaystyle (K,\vee ,\wedge )} nazywamy podzbiór P K {\displaystyle P\subseteq K} będący podalgebrą, tzn. dla każdego x , y P {\displaystyle x,y\in P} musimy mieć x y , x y P . {\displaystyle x\land y,x\lor y\in P.}

Zupełność | edytuj kod

Za pomocą indukcji matematycznej można udowodnić, że w kracie każdy skończony i niepusty podzbiór ma kres górny i kres dolny. Własność ta prowadzi do pojęcia kraty zupełnej – nazywamy tak częściowy porządek ( P , ) , {\displaystyle (P,\leqslant ),} w którym każdy podzbiór zbioru P {\displaystyle P} ma kres górny i kres dolny; w szczególności, każda krata zupełna ma najmniejszy i największy element.

Rozdzielność | edytuj kod

Krata jest rozdzielna (dystrybutywna), gdy dla każdego x , y , z : {\displaystyle x,y,z{:}}

( x y ) z = ( x z ) ( y z ) , {\displaystyle (x\land y)\lor z=(x\lor z)\land (y\lor z),} ( x y ) z = ( x z ) ( y z ) . {\displaystyle (x\lor y)\land z=(x\land z)\lor (y\land z).}

Można udowodnić, że w każdej kracie spełnione są nierówności

( x y ) z ( x z ) ( y z ) {\displaystyle (x\land y)\lor z\leqslant (x\lor z)\land (y\lor z)} oraz ( x y ) z ( x z ) ( y z ) , {\displaystyle (x\lor y)\land z\geqslant (x\land z)\lor (y\land z),}

jeśli pierwsze prawo rozdzielności

( x y ) z = ( x z ) ( y z ) {\displaystyle (x\land y)\lor z=(x\lor z)\land (y\lor z)}

jest spełnione dla dowolnych x , y , z , {\displaystyle x,y,z,} to musi też zachodzić również drugie prawo rozdzielności.

Reprezentacja krat rozdzielnych | edytuj kod

Dla każdego zbioru X , {\displaystyle X,} zbiór potęgowy P ( X ) {\displaystyle P(X)} (uporządkowany przez inkluzję {\displaystyle \subseteq } ) jest kratą rozdzielną. Podkrata kraty rozdzielnej jest zawsze sama rozdzielna, więc każda podkrata zbioru potęgowego jest też kratą rozdzielną.

Twierdzenia Birkhoffa-Stone'a o reprezentacji krat rozdzielnych mówi, że każda krata rozdzielna ma tę postać:

Każda krata rozdzielna jest izomorficzna z pewną podkratą kraty P ( X ) {\displaystyle P(X)} (dla pewnego zbioru X {\displaystyle X} ).

Przykłady | edytuj kod

  • Kratami są wszystkie zbiory uporządkowane liniowo oraz relacją inkluzji na każdym zbiorze potęgowym.
  • „Pięciokąt” lub krata N 5 {\displaystyle N_{5}} to krata pięciu elementów a , b , c , d , e , {\displaystyle a,b,c,d,e,} spełniających relacje
c x a {\displaystyle c\leqslant x\leqslant a} dla każdego x {\displaystyle x} d b = e b = c {\displaystyle d\land b=e\land b=c} d b = e b = a {\displaystyle d\lor b=e\lor b=a}
  • „Diament” lub krata M 3 {\displaystyle M_{3}} to krata pięciu elementów a , b , c , d , e , {\displaystyle a,b,c,d,e,} spełniających relacje
c x a {\displaystyle c\leqslant x\leqslant a} dla każdego x {\displaystyle x} x y = c {\displaystyle x\land y=c} dla każdych x y {\displaystyle x\neq y} w zbiorze { b , d , e } {\displaystyle \{b,d,e\}} x y = a {\displaystyle x\lor y=a} dla każdych x y {\displaystyle x\neq y} w zbiorze { b , d , e } {\displaystyle \{b,d,e\}}

Pięciokąt i diament są kratami nierozdzielnymi, więc każda krata zawierająca pięciokąt albo diament jako podkratę musi być też nierozdzielna. Odwrotnie: w każdą kratę nierozdzielną można zanurzyć albo diament albo pięciokąt (lub obydwa) jako podkratę.

  • Rozważmy zbiór liczb całkowitych dodatnich wraz z operacjami NWD i NWW. Jeżeli zinterpretować NWD jako , {\displaystyle \land ,} a NWW jako , {\displaystyle \lor ,} z własności obu operacji wynika, że spełnione są aksjomaty kraty. Z własności NWW i NWD wynika również, że jest to krata rozdzielna. Relacją {\displaystyle \leqslant } w tej kracie jest podzielność: x y {\displaystyle x\leqslant y} wtedy i tylko wtedy, gdy liczba x {\displaystyle x} jest dzielnikiem liczby y . {\displaystyle y.} Przykładem jej podkraty jest podkrata liczb parzystych.
  • Rozważmy zbiór wszystkich uporządkowanych par liczb całkowitych Z 2 {\displaystyle \mathbb {Z} ^{2}} wraz z relacją {\displaystyle \leqslant } określoną następująco:
    ( x 1 , y 1 ) ( x 2 , y 2 ) x 1 x 2  i  y 1 y 2 . {\displaystyle (x_{1},y_{1})\leqslant (x_{2},y_{2})\Leftrightarrow x_{1}\leqslant x_{2}{\text{ i }}y_{1}\leqslant y_{2}.}
    Relacja ta jest częściowym porządkiem i jeśli zdefiniujemy
    inf ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) := ( min ( x 1 , x 2 ) , min ( y 1 , y 2 ) ) {\displaystyle \inf((x_{1},y_{1}),(x_{2},y_{2})):=(\min(x_{1},x_{2}),\min(y_{1},y_{2}))}
    oraz
    sup ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) := ( max ( x 1 , x 2 ) , max ( y 1 , y 2 ) ) , {\displaystyle \sup((x_{1},y_{1}),(x_{2},y_{2})):=(\max(x_{1},x_{2}),\max(y_{1},y_{2})),}
    to otrzymamy kratę. Na przykład
    inf ( ( 2 , 3 ) , ( 1 , 2 ) ) := ( 2 , 2 ) {\displaystyle \inf((-2,3),(1,2)):=(-2,2)}
    oraz
    sup ( ( 2 , 3 ) , ( 1 , 2 ) ) := ( 1 , 3 ) . {\displaystyle \sup((-2,3),(1,2)):=(1,3).}
    Krata ta ma wiele podkrat, jedną z nich jest choćby podkrata złożona z wszystkich par o drugiej współrzędnej parzystej.

Reprezentacja | edytuj kod

Dla każdego zbioru A {\displaystyle A} definiujemy Eq ( A ) = { ρ A × A : ρ {\displaystyle \operatorname {Eq} (A)=\{\rho \subseteq A\times A:\rho } jest relacją równoważności } . {\displaystyle \}.} Wówczas Eq ( A ) , {\displaystyle \operatorname {Eq} (A),} uporządkowany przez relację , {\displaystyle \subseteq ,} jest kratą zupełną.

Można udowodnić, że każda krata jest izomorficzna z podkratą kraty Eq ( A ) {\displaystyle \operatorname {Eq} (A)} (dla pewnego zbioru A {\displaystyle A} ).

Zobacz też | edytuj kod

Na podstawie artykułu: "Krata (porządek)" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy