Krata (matematyka)

Ten artykuł dotyczy matematyki. Zobacz też: inne znaczenia słowa „krata”.
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.

Struktura algebraicznaEdytuj

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 1Edytuj

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

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ółkratyEdytuj

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.

PodkratyEdytuj

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 rozdzielnychEdytuj

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ładyEdytuj

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

ReprezentacjaEdytuj

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