Krata (matematyka)
Kraty – 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:
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.
- „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]- ↑ 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
[edytuj | edytuj kod]- Małgorzata Jastrzębska , O pewnych kratach testowych, „Delta”, styczeń 2014, ISSN 0137-3005 [dostęp 2024-11-03] .
- Eric W. Weisstein , 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].