Krata (matematyka)

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

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”.

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