Krata (matematyka)

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

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.

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$ ^[2]. 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^{[potrzebny przypis]}; 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ż

Przypisy

↑ krata, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-10-02] .
↑ półkrata, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-10-12] .

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

[epwn-1] krata, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-10-02] .

[2] półkrata, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-10-12] .

[1]

[2]

Fahrer / Team für die Suche eingeben: