Krata (porządek)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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".

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:

, .
Krata permutacji zbioru czteroelementowego.

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]