Krata (matematyka)

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 – struktury matematyczne, które można opisywać albo algebraicznie, albo w sensie częściowych porządków.

Struktura algebraiczna

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

1.	$x\land x=x$	$x\lor x=x$
2.	$(x\land y)\land z=x\land (y\land z)$	$(x\lor y)\lor z=x\lor (y\lor z)$
3.	$x\land y=y\land x$	$x\lor y=y\lor x$
4.	$(x\land y)\lor y=y$	$(x\lor y)\land y=y$

Przykładem kraty jest dowolna algebra Boole’a.

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

$x\leqslant y\Leftrightarrow x\lor y=y$

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

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

Krata permutacji zbioru czteroelementowego.

Niekonieczność aksjomatu 1

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

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

$(X\land y)\lor y=y$

a na mocy prawej:

$X\land y=y$

co po podstawieniu do poprzedniego wzoru daje:

$y\lor y=y.$

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

Struktura porządkowa

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

Jeśli zdefiniujemy

$x\lor y:=\sup(x,y),$

$x\land y:=\inf(x,y),$

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

$x\leqslant y\Leftrightarrow x\lor y=y.$

Półkraty

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

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

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

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

Zupełność

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

Rozdzielność

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

$(x\land y)\lor z=(x\lor z)\land (y\lor z),$

$(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\land y)\lor z\leqslant (x\lor z)\land (y\lor z)$ oraz $(x\lor y)\land z\geqslant (x\land z)\lor (y\land z),$

jeśli pierwsze prawo rozdzielności

$(x\land y)\lor z=(x\lor z)\land (y\lor z)$

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

Reprezentacja krat rozdzielnych

Dla każdego zbioru $X,$ zbiór potęgowy $P(X)$ (uporządkowany przez inkluzję $\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 $P(X)$ (dla pewnego zbioru $X$).

Przykłady

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

$c\leqslant x\leqslant a$ dla każdego $x$

$d\land b=e\land b=c$

$d\lor b=e\lor b=a$

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

$c\leqslant x\leqslant a$ dla każdego $x$

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

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

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

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

Zobacz też

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

Linki zewnętrzne

• 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].