Gitter i algebra

Eit gitter er ein matematisk struktur som kan realiserast på to måtar: Eit gitter er ei form for algebra, men òg ein spesiell sort delvis ordna mengd.

Definisjonar

Som algebra

Eit gitter består av ei mengd E som kan vere endeleg eller uendeleg, saman med to binære operasjonar som vert kalla supremum (notert ∨) og infimum (notert ∧). Supremum og infimum vert òg ofte kalla ved dei engelske namna «join» og «meet». Dei to operasjonane fungerer som spegelbilete av einannan og følgjer desse aksioma:

• Supremum og infimum er båe kommutative og assosiative operasjonar. Det tyder at for kvar a, b, c ∈ E gjeld det at a ∨ b = b ∨ a, a ∧ b = b ∧ a, (a ∨ b) ∨ c = a ∨ (b ∨ c), og (a ∧ b) ∧ c = a ∧ (b ∧ c).
• Absorpsjonsregelen: For kvar a, b ∈ E gjeld det at a ∨ (a ∧ b) = a ∧ (a ∨ b) = a.

Dei to neste eigenskapane er òg gjerne tekne som aksiom, men følgjer faktisk frå dei føregåande:

• For kvar a ∈ E gjeld det at a ∨ a = a ∧ a = a.
• for kvar a, b ∈ E gjeld det at a ∨ b = a viss og berre viss a ∧ b = b.

Som ordning

Gjeve ei delvis ordning ≤ over mengda E og to element a, b ∈ E, så er ein øvre skranke av a og b eit element s slik at a ≤ s og b ≤ s. Eit element s^* er den nedste øvre skranken av a og b dersom det for kvar øvre skranke s gjeld at s^* ≤ s. Me kan definere nedre skrankar og øvste nedre skrankar på same viset. I ei vilkårleg, delvis ordna mengd vil ikkje alle par av element naudsynt ha ein nedste øvre eller ein øvste nedre skranke. Dersom no mengda (E, ≤) har den eigenskapen at alle par har både ein øvste nedre og nedste øvre skranke, så kan me definere a ∨ b og a ∧ b som desse skrankane, høvesvis. Ein kan enkelt syne at skrankane lyder aksioma sette ovanfor, og at (E, ∨, ∧) derfor er eit gitter.

Det som kanskje er mindre openbert, er at det òg går motsett veg. Gjeve eit gitter (E, ∨, ∧), kan me definere ein relasjon ≤ over E som følgjer: a ≤ b viss og berre viss a ∧ b = a (eller viss a ∨ b = b; desse er likeverdige). Det syner seg at (E, ≤) er ei delvis ordna mengd, og at a ∨ b og a ∧ b, for eit vilkårleg par a, b ∈ E, høvesvis svarar til nedste øvre og øvste nedre skrankar av a og b. Algebraen og ordninga er derfor likeverdige måtar å definere eit gitter på.

Hassediagram av dei fem moglege gittera med fem element. Femkanten N₅ er heilt til venstre og diamanten M₃ er heilt til høgre.

Nokre eigenskapar

Topp og botn

Viss mengda E er endeleg, så må det finnast ein topp og ein botn i gitteret (E, ∨, ∧): To element t og b med eigenskapen at for kvart element a gjeld det at b ≤ a ≤ t. Det er vanleg å notere toppen og botnen som 1 og 0, høvesvis. Om E er uendeleg, så kan, men må ikkje, (E, ∨, ∧) ha ein topp eller ein botn.

Komplette gitter

Ut frå assosiativiteten åt operasjonane ∨ og ∧, kan me sjå at ikkje berre kvart par av element har ein nedste øvre og øvste nedre skranke under ordninga ≤, men kvar endelege delmengd S ⊆ E har òg slike skrankar. Derimot kan denne innsikta ikkje utvidast til uendelege delmengder. Eit gitter (E, ∨, ∧) vert kalla eit komplett gitter dersom alle delmengder har ein øvste og nedste skranke. Det er dermed openbert at alle endelege gitter òg er komplette, men for uendelege gitter er dette altså ein vesensforskjell.

Undergitter

Gjeve eit gitter (E, ∨, ∧) og ei delmengd S ⊆ E, så utgjer S eit undergitter av (E, ∨, ∧) dersom det for kvart par av element a, b ∈ S gjeld at både a ∨ b og a ∧ b òg ligg i S. Det er då klart at (S, ∨, ∧) er eit gitter (med operasjonane ∨ og ∧ avgrensa til elementa i S).

Gjeve ei undermengd S, kan ein òg avgrense ordninga ≤ til elementa i S. Det som då er viktig å få med seg, er at sjølv om (S, ≤) skulle vere eit gitter, er det ikkje naudsynt eit undergitter av (E, ≤). Eit døme er på sin plass her. Sett at (E, ≤) er eit gitter med topp og botn, men ikkje ei totalt ordna mengd. Det tyder at det finst to element a, b ∈ E som ikkje er samanliknbare ved ≤. Me vel då delmengda S til å vere lik {a, b, 1, 0}. Det er klart at (S, ≤) er eit gitter, men det er berre eit undergitter av (E, ≤) dersom skrankane åt a og b faktisk er 1 og 0 òg i (E, ≤). Om (E, ≤) derimot er ei totalt ordna mengd, vil kvar einaste delmengd av E utgjere eit undergitter.

Intervall

For kvart par a, b ∈ E i eit gitter (E, ∨, ∧) slik at a ≤ b, kan me definere intervallet [a, b] som delmengda {e ∈ E: a ≤ e ≤ b}. Kvart eit intervall i eit gitter er eit undergitter av gitteret.

Modulære og distributive gitter

Alle gitter oppfyller dei såkalla modulære og distributive ulikskapane. I det følgjande er me gjevne eit gitter (E, ∨, ∧) og tre vilkårlege element a,b, c ∈ E.

• Modulær ulikskap: Viss a ≤ c, så er a ∨ (b ∧ c) ≤ (a ∨ b) ∧ c.
• Distributive ulikskapar: (a ∧ b) ∨ c ≤ (a ∨ c) ∧ (b ∨ c), og (a ∧ c) ∨ (b ∧ c) ≤ (a ∨ b) ∧ c.

Viss den modulære ulikskapen er ein likskap for kvar a ≤ c, altså at a ∨ (b ∧ c) = (a ∨ b) ∧ c, så kallar me giteret (E, ∨, ∧) eit modulært gitter. Viss dei distributive ulikskapane er likskapar for kvar a,b, c, så kallar me gitteret eit distributivt gitter.

Namnet «distributivt gitter» kjem av di supremum og infimum då følgjer den distributive lova som gjeld m.a. for addisjon og multiplikasjon: (a + b) ⋅ c = a ⋅ c + b ⋅ c. Det som er spesielt med distributivitet i gitter er at båe operasjonane distribuerer over kvarandre. Dette gjeld ikkje for addisjon og multiplikasjon av tal: Det er vanlegvis ikkje sant at a ⋅ b + c = (a + c) ⋅ (b + c).

Forbodne undergitter

Alle distributive gitter er òg modulære, men det motsette held ikkje. Dette syner seg veldig konkret i dei følgjande resultata, bevist av høvesvis Dedekind og Birkhoff: Eit gitter er modulært viss og berre viss det ikkje inneheld «femkant-gitteret» N₅ som eit undergitter, og det er distributivt viss og berre viss det korkje inneheld «diamant-gitteret» M₃ eller N₅ som undergitter.

Representasjon

Eit system S av mengder som er lukka under union og snitt — altså at for kvart par av mengder a, b ∈ S ligg både a ∪ b og a ∩ b i S — utgjer eit distributivt gitter når det er ordna etter delmengd-relasjonen. Dette er fordi unionen og snittet av to mengder må utgjere høvesvis den nedste øvre og den øvste nedre skranken av mengdene, og union og snitt av mengder distribuerer over einannan, nett som supremum og infimum i eit distributivt gitter. Birkhoffs kjende representasjons-teorem syner at denne slektskapen går begge vegar: Kvart distributive gitter er isomorft til eit gitter av mengder som er lukka under union og snitt.

Boolsk algebra

Eit distributivt gitter (E, ∨, ∧) der kvart element a ∈ E i tillegg har eit komplement a′ — eit element med eigenskapane a ∨ a′ = 1 og a ∧ a′ = 0 — er kalla ein boolsk algebra. Det syner seg at boolske algebraar òg har ein vesentleg representasjon: Kvar endelege boolske algebra er isomorf til potensmengda 2^U av ei mengd U, ordna etter delmengd-relasjonen.

Bakgrunnsstoff

• Birkhoff, Garrett (1967), «Lattice Theory», Archive.org (3. utg.) (American Mathematical Society)

• B. A. Davey; H. A. Priestley (2002), Introduction to Lattices and Order (2. utg.), Cambridge University Press