Przejdź do zawartości

Krata (matematyka)

Z Wikipedii, wolnej encyklopedii
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) – struktury matematyczne, które można opisywać albo algebraicznie, albo w sensie częściowych porządków[1].

Struktura algebraiczna

[edytuj | edytuj kod]

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

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

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

Półkraty w sensie algebraicznym to dokładnie pasy przemienne, czyli półgrupy przemienne, w których równość zachodzi dla dowolnego [2]. 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 | edytuj kod]

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

Zupełność

[edytuj | edytuj kod]

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[potrzebny przypis]; w szczególności, każda krata zupełna ma najmniejszy i największy element.

Rozdzielność

[edytuj | edytuj kod]

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

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

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

Przykłady

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

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

Przypisy

[edytuj | edytuj kod]
  1. krata, [w:] Encyklopedia PWN [dostęp 2021-10-02].
  2. półkrata, [w:] Encyklopedia PWN [dostęp 2022-10-12].

Linki zewnętrzne

[edytuj | edytuj kod]
  • Eric W. Weisstein, Lattice, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2024-03-25].
  • publikacja w otwartym dostępie – możesz ją przeczytać Lattice (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].
  • publikacja w otwartym dostępie – możesz ją przeczytać Semi-lattice (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].