Gitter (ordning)

Disambig bordered fade.svg For alternative betydninger, se Gitter. (Se også artikler, som begynder med Gitter)

Begrebet gitter bruges i matematik om en mængde hvis elementer er ordnet på en særlig måde. Til et vilkårligt par af elementer i et gitter findes et mindste element som dominerer dem og et største element som de dominerer. Dette giver anledning til de såkaldte gitteroperationer, som tillader en algebraisk karakterisering af et gitter. Teorien for gitre har anvendelser inden for logik, mængdelære, talteori, lineær algebra, operatorteori og mange andre dele af matematikken.

GitteroperationerneRediger

Gitre kan karakteriseres ved de to gitteroperationer   og  , som giver gitteret en særlig algebraisk struktur. I et gitter med en ordning   betegner   det største element mindre end både   og  . Tilsvarende betegner   det mindste element større end   og  . Gitteroperationerne opfylder følgende regler.

Kommutative love
 ,
 .
    
Associative love
 ,
 .
    
Absorptionlove
 ,
 .

Omvendt vil ethvert par af operationer   og  , som opfylder ovenstående regler, give anledning til et gitter ved at definere   dersom  . Sammen med ovenstående love nævnes ofte også de idempotente love, som dog kan bevises ud fra absorbtionslovene.

Idempotente love
 ,
 .

Gitre med særlige egenskaberRediger

Man kan kræve, at gitteroperationerne opfylder yderligere algebraiske egenskaber.

Et gitter siges at være begrænset dersom det har et mindste og et største element. Det mindste element betegnes ofte 0 og det største element betegnes ofte 1.

Et gitter siges at være distributivt dersom følgende distributive love gælder

Distributive love
 ,
 .

En Heyting-algebra er et begrænset gitter hvor der for alle elementer a og b findes et element x så  

Et gitter med et største og et mindste element siges at være ortofuldstændigt dersom der findes en afbildning   således at   og  .

Et gitter med et mindste og et største element kaldes en Boolsk algebra dersom det er distributivt og ortofuldstændigt.

Et gitter siges at være modulært dersom   medfører at  .

Et gitter siges at være semi-konvekst, dersom   og   medfører at  .

Eksempler på gitreRediger

De hele tal ordnet på den sætdvanlige måde udgør, ligesom enhver anden totalt ordnet mængde, et gitter hvor   og  .

De naturlige tal hvor   betyder at   går op i   udgør et gitter, hvor   er mindste fælles multiplum af   og  , og   største fælles divisor i   og  .

Delmængder af en given mængde udgør et gitter hvor ordningen er delmængderelationen og gitteroperationerne er fællesmængde og foreningsmængde.

En topologi på en mængde er et gitter af delmængder, hvor det er tilladt at danne ikke blot endelige men vilkårlige foreningsmængder.

En σ-algebra på en mængde en Boolsk algebra, hvor det er tilladt at lave tællelige foreningsmængder.

Udsagnslogik udgør et gitter hvor implikation er ordningen og gitteroperationerne er konjunktion og disjunktion.

Underrummene af et vektorrum udgør et gitter hvor ordningen er underrumsrelationen. I et vektorrum er   det samme som fællesmængde mens   angiver span af foreningsmængden.

I begrebsteori kan man ud fra et antal objekter og attributer danne et antal begreber som er organiseret som et gitter.

HistorieRediger

Teorien for gitre startede med G. Booles indførsel af symbolsk logik. Som selvstændigt forskningsområde blev gitterteori udviklet af G. Birkhoff, hvis bog fra 1940 stadig er værd at læse. Siden Birkhoff har gitre med specielle egenskaber været studeret med henblik på særlige anvendelser.