Krata (matematyka)

Dzielniki 60 tworzą kratę.

Diagram Hassego kraty Tamriego. Warto zauważyć, iż punkty kraty tworzą wielościan, zwany angielskim terminem Szablon:K, 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,\wedge ,\vee ),$ gdzie $A$ jest (niepustym) zbiorem, a $\wedge$ i $\vee$ są odwzorowaniami z $A\times A$ w $A$ spełniającymi dla dowolnych $x,y,z\in A$ następujące warunki:

1.	$x\wedge x=x$	$x\vee x=x$
2.	$(x\wedge y)\wedge z=x\wedge (y\wedge z)$	$(x\vee y)\vee z=x\vee (y\vee z)$
3.	$x\wedge y=y\wedge x$	$x\vee y=y\vee x$
4.	$(x\wedge y)\vee y=y$	$(x\vee y)\wedge y=y$

Przykładem kraty jest dowolna algebra Boole’a.

W każdej kracie spełniona jest równoważność: $x\vee y=y\iff x\wedge y=x.$ Relacja $⩽,$ zdefiniowana za pomocą równoważności

$x⩽y\iff x\vee 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,\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\vee y.$ Wtedy na mocy lewej części aksjomatu 4 otrzymujemy

$(X\wedge y)\vee y=y$

a na mocy prawej:

$X\wedge y=y$

co po podstawieniu do poprzedniego wzoru daje:

$y\vee y=y.$

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

Struktura porządkowa

Krata w sensie częściowych porządków to (niepusty) częściowy porządek $(A,⩽),$ 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\vee y:=\sup (x,y),$

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

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

$x⩽y\iff x\vee 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,⩽),$ gdzie relacja $⩽$ jest zdefiniowana przez

$x⩽y\iff 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⩽y\iff 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\wedge y,x\vee 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,⩽),$ w którym każdy podzbiór zbioru $P$ ma kres górny i kres dolnySzablon:Fakt; 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\wedge y)\vee z=(x\vee z)\wedge (y\vee z),$

$(x\vee y)\wedge z=(x\wedge z)\vee (y\wedge z).$

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

$(x\wedge y)\vee z⩽(x\vee z)\wedge (y\vee z)$ oraz $(x\vee y)\wedge z⩾(x\wedge z)\vee (y\wedge z),$

jeśli pierwsze prawo rozdzielności

$(x\wedge y)\vee z=(x\vee z)\wedge (y\vee 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⩽x⩽a$ dla każdego $x$

$d\wedge b=e\wedge b=c$

$d\vee b=e\vee b=a$

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

$c⩽x⩽a$ dla każdego $x$

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

$x\vee y=a$ dla każdych $x\ne 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 $\wedge ,$ a NWW jako $\vee ,$ 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ą $⩽$ w tej kracie jest podzielność: $x⩽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ą $⩽$ określoną następująco:
  $(x_1,y_1)⩽(x_2,y_2)\iff x_1⩽x_2\text{ i }{y}_1⩽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 $\mathrm{Eq}(A)=\{\rho \subseteq A\times A:\rho$ jest relacją równoważności $\}.$ Wówczas $\mathrm{Eq}(A),$ uporządkowany przez relację $\subseteq ,$ jest kratą zupełną.

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

Zobacz też

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

Linki zewnętrzne

• Szablon:MathWorld [dostęp 2024-03-25].
• Szablon:Otwarty dostęp Lattice Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].
• Szablon:Otwarty dostęp Semi-lattice Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].