Gitter (ordning)

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.

Gitteroperationerne

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

Kommutative love $a\lor b=b\lor a$, $a\land b=b\land a$.

Associative love $a\lor (b\lor c)=(a\lor b)\lor c$, $a\land (b\land c)=(a\land b)\land c$.

Absorptionlove $a\lor (a\land b)=a$, $a\land (a\lor b)=a$.

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

Idempotente love $a\lor a=a$, $a\land a=a$.

Gitre med særlige egenskaber

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 $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$, $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$.

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

Et gitter med et største og et mindste element siges at være ortofuldstændigt dersom der findes en afbildning $\neg$ således at $A\wedge \neg A=0$ og $A\vee \neg A=1$.

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 $a\leq c$ medfører at $a\vee (b\wedge c)=(a\vee b)\wedge c$.

Et gitter siges at være semi-konvekst, dersom $a\wedge b=a\wedge c$ og $a\vee c=b\vee c$ medfører at $a\leq b\leq c$.

Eksempler på gitre

De hele tal ordnet på den sætdvanlige måde udgør, ligesom enhver anden totalt ordnet mængde, et gitter hvor $a\wedge b=\max {a,b}$ og $a\vee b=\min {a,b}$.

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

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 $\wedge$ det samme som fællesmængde mens $\vee$ 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.

Historie

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.