Krata - porządek - Polski Serwis Naukowy

Kraty (ang. lattice) są strukturami matematycznymi, 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:

Przykładem kraty jest dowolna algebra Boole'a.

Najmniejsza wspólna wielokrotność dwóch lub więcej liczb naturalnych a1, a2,... ,an - najmniejsza liczba naturalna ze zbioru wszystkich liczb naturalnych, których dzielnikiem jest każda z liczb a1,...,an, i na przykład dla liczb 15 i 240 jest to liczba 240, a dla liczb 192 i 348 - liczba 5568. Najmniejszą wspólną wielokrotność oznacza się często symbolem NWW(a1,...,an).
Kres (kraniec) dolny (również łac. infimum) oraz kres (kraniec) górny (także łac. supremum) – w matematyce pojęcia oznaczające odpowiednio: największe z ograniczeń dolnych oraz najmniejsze z ograniczeń górnych danego zbioru, o ile takie istnieją.

W każdej kracie spełniona jest równoważność: $x \lor y = y \Leftrightarrow x \land y = x.\;$ Relacja $\le,\;$ zdefiniowana za pomocą równoważności $x \le y \Leftrightarrow x \or 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$ .

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

W matematyce, termin indukcja matematyczna używany jest na określenie szczególnej metody dowodzenia twierdzeń (w najbardziej typowych przypadkach o liczbach naturalnych) ale także jest on używany na oznaczenie konstrukcji pewnych obiektów.
Półgrupa to struktura algebraiczna, na którą składa się pewien zbiór wraz z określonym w nim działaniem, przy czym działanie to musi być łączne i wewnętrzne. Szczególnymi przypadkami półgrup są monoid i grupa.

$(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, \le)\;$ , 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

Kres (kraniec) dolny (również łac. infimum) oraz kres (kraniec) górny (także łac. supremum) – w matematyce pojęcia oznaczające odpowiednio: największe z ograniczeń dolnych oraz najmniejsze z ograniczeń górnych danego zbioru, o ile takie istnieją.
Porządek liniowy – częściowy porządek będący zarazem łańcuchem, czyli taki, w którym każde dwa elementy rozpatrywanego zbioru są porównywalne.

$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,\le),\;$ gdzie relacja $\le\;$ jest zdefiniowana przez $x\le 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.

Relacja – w teorii mnogości dowolny podzbiór iloczynu kartezjańskiego skończonej liczby zbiorów; definicja ta oddaje intuicję pewnego związku, czy zależności między elementami wspomnianych zbiorów (elementy wspomnianych zbiorów pozostają w związku albo łączy je pewna zależność, czy też własność lub nie). Najważniejszymi relacjami są relacje dwuargumentowe, tj. między elementami pary zbiorów (opisane w osobnym artykule, w tym funkcje i działania jednoargumentowe); relacje jednoargumentowe to po prostu podzbiory pewnego zbioru.
Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)