Spring til indhold

Gitter (ordning)

Fra Wikipedia, den frie encyklopædi
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

[redigér | rediger kildetekst]

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 egenskaber

[redigér | rediger kildetekst]

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å gitre

[redigér | rediger kildetekst]

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.

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.