Krata (matematyka)

Krata w sensie algebraicznym to struktura algebraiczna ${\displaystyle (A,\land ,\lor ),}$  gdzie ${\displaystyle A}$  jest (niepustym) zbiorem, a ${\displaystyle \land }$  i ${\displaystyle \lor }$  są odwzorowaniami z ${\displaystyle A\times A}$  w ${\displaystyle A}$  spełniającymi dla dowolnych ${\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ść: ${\displaystyle x\lor y=y\Leftrightarrow x\land y=x.}$  Relacja ${\displaystyle \leqslant ,}$  zdefiniowana za pomocą równoważności

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

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

${\displaystyle \sup(x,y)=x\vee y,\quad \inf(x,y)=x\wedge y.}$ 

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

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

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

a na mocy prawej:

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

co po podstawieniu do poprzedniego wzoru daje:

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

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

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

Jeśli zdefiniujemy

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

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

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

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

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

${\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 ${\displaystyle x,y}$  ma kres górny: ${\displaystyle \sup(x,y)=x+y.}$ 

Jeśli zdefiniujemy ${\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.

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

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 ${\displaystyle (P,\leqslant ),}$  w którym każdy podzbiór zbioru ${\displaystyle P}$  ma kres górny i kres dolny^{[potrzebny przypis]}; w szczególności, każda krata zupełna ma najmniejszy i największy element.

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

${\displaystyle (x\land y)\lor z=(x\lor z)\land (y\lor 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

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

jeśli pierwsze prawo rozdzielności

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

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

Dla każdego zbioru ${\displaystyle X,}$  zbiór potęgowy ${\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ą.

Twierdzenie 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 ${\displaystyle P(X)}$  (dla pewnego zbioru ${\displaystyle X}$ ).

• Kratami są wszystkie zbiory uporządkowane liniowo oraz relacją inkluzji na każdym zbiorze potęgowym.
•   „Pięciokąt” lub krata ${\displaystyle N_{5}}$  to krata pięciu elementów ${\displaystyle a,b,c,d,e,}$  spełniających relacje

${\displaystyle c\leqslant x\leqslant a}$  dla każdego ${\displaystyle x}$ 

${\displaystyle d\land b=e\land b=c}$ 

${\displaystyle d\lor b=e\lor b=a}$ 

• „Diament” lub krata ${\displaystyle M_{3}}$  to krata pięciu elementów ${\displaystyle a,b,c,d,e,}$  spełniających relacje

${\displaystyle c\leqslant x\leqslant a}$  dla każdego ${\displaystyle x}$ 

${\displaystyle x\land y=c}$  dla każdych ${\displaystyle x\neq y}$  w zbiorze ${\displaystyle \{b,d,e\}}$ 

${\displaystyle x\lor y=a}$  dla każdych ${\displaystyle x\neq y}$  w zbiorze ${\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ść: ${\displaystyle x\leqslant y}$  wtedy i tylko wtedy, gdy liczba ${\displaystyle x}$  jest dzielnikiem liczby ${\displaystyle y.}$  Przykładem jej podkraty jest podkrata liczb parzystych.
• Rozważmy zbiór wszystkich uporządkowanych par liczb całkowitych ${\displaystyle \mathbb {Z} ^{2}}$  wraz z relacją ${\displaystyle \leqslant }$  określoną następująco:
  ${\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
  ${\displaystyle \inf((x_{1},y_{1}),(x_{2},y_{2})):=(\min(x_{1},x_{2}),\min(y_{1},y_{2}))}$ 
  oraz
  ${\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
  ${\displaystyle \inf((-2,3),(1,2)):=(-2,2)}$ 
  oraz
  ${\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.

Dla każdego zbioru ${\displaystyle A}$  definiujemy ${\displaystyle \operatorname {Eq} (A)=\{\rho \subseteq A\times A:\rho }$  jest relacją równoważności ${\displaystyle \}.}$  Wówczas ${\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 ${\displaystyle \operatorname {Eq} (A)}$  (dla pewnego zbioru ${\displaystyle A}$ ).

• algebra Heytinga
• twierdzenie Stone’a o reprezentacji algebr Boole’a

• MałgorzataM. Jastrzębska MałgorzataM., O pewnych kratach testowych, „Delta”, styczeń 2014, ISSN 0137-3005 [dostęp 2024-11-03] .
• Eric W.E.W. Weisstein Eric W.E.W., Lattice, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-03-25].
•   Lattice (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].
•   Semi-lattice (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].