Krata (porządek)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Kraty (ang. lattice) są strukturami matematycznymi, które można opisywać albo algebraicznie, albo w sensie częściowych porządków:

Struktura algebraiczna[edytuj]

Krata w sensie algebraicznym to struktura algebraiczna , gdzie jest (niepustym) zbiorem, a i są odwzorowaniami z w spełniającymi dla dowolnych następujące warunki:

1.
2.
3.
4.

Przykładem kraty jest dowolna algebra Boole’a.

W każdej kracie spełniona jest równoważność: Relacja zdefiniowana za pomocą równoważności

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

, .

Niekonieczność aksjomatu 1[edytuj]

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

Niech . Wtedy na mocy lewej części aksjomatu 4 otrzymujemy

a na mocy prawej:

co po podstawieniu do poprzedniego wzoru daje:

.

Podobnie dowodzi się, że .

Struktura porządkowa[edytuj]

Krata w sensie częściowych porządków to (niepusty) częściowy porządek , w którym każda para ma kres dolny i kres górny .

Jeśli zdefiniujemy

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

Półkraty[edytuj]

Półkraty w sensie algebraicznym to dokładnie pasy przemienne, czyli półgrupy przemienne, w których równość zachodzi dla dowolnego . Para gdzie relacja jest zdefiniowana przez

nazywana jest półkratą górną (lub ∨-półkratą). Innymi słowy, jest to częściowy porządek, w którym każda para ma kres górny:

Jeśli zdefiniujemy , 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[edytuj]

Podkratą kraty nazywamy podzbiór będący podalgebrą, tzn. dla każdego musimy mieć .

Zupełność[edytuj]

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

Rozdzielność[edytuj]

Krata jest rozdzielna (dystrybutywna), gdy dla każdego

Można udowodnić, że

  • w każdej kracie spełnione są nierówności
oraz
  • jeśli pierwsze prawo rozdzielności

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

Reprezentacja krat rozdzielnych[edytuj]

Dla każdego zbioru zbiór potęgowy (uporządkowany przez inkluzję ) jest kratą rozdzielną. Podkrata kraty rozdzielnej jest zawsze sama rozdzielna, więc każda podkrata zbioru potęgowego jest też kratą rozdzielną.

Twierdzenia 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 (dla pewnego zbioru ).

Przykłady[edytuj]

  • Kratami są wszystkie zbiory uporządkowane liniowo oraz relacją inkluzji na każdym zbiorze potęgowym.
  • Przykłady krat nierozdzielnych
    „Pięciokąt” lub krata to krata pięciu elementów spełniających relacje
dla każdego
  • „Diament” lub krata to krata pięciu elementów spełniających relacje
dla każdego
dla każdych w zbiorze
dla każdych w zbiorze


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 , a NWW jako , 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ść: wtedy i tylko wtedy, gdy liczba jest dzielnikiem liczby . Przykładem jej podkraty jest podkrata liczb parzystych.
  • Rozważmy zbiór wszystkich uporządkowanych par liczb całkowitych wraz z relacją określoną następująco:
    .
    Relacja ta jest częściowym porządkiem i jeśli zdefiniujemy

    oraz
    ,
    to otrzymamy kratę. Na przykład

    oraz

    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[edytuj]

Dla każdego zbioru definiujemy jest relacją równoważności Wówczas uporządkowany przez relację , jest kratą zupełną.

Można udowodnić, że każda krata jest izomorficzna z podkratą kraty (dla pewnego zbioru ).

Zobacz też[edytuj]