Gitter

Et gitter er en ordnet mengde som i tillegg har den egenskapen at det for hvert par av elementer i gitteret må finnes et supremum og et infimum, som også tilhører gitteret.

Øvre og nedre kjegle

Til å begynne med har vi en mengde M med en ordning ≤ definert på den. Denne ordningen kan være vilkårlig, men den må oppfylle betingelsene for en ordningsrelasjon.

Videre tar vi et element a fra mengden M. Den øvre kjeglen til elementet a i mengden M definerer vi som alle x ∈ M som er større enn eller lik a, altså slik at a ≤ x.

Hvis vi tar de naturlige tallene som mengde og a = 7 som element, er den øvre kjeglen mengden av tall {7, 8, 9, …}. På de reelle tallene ville vi fått intervallet [7, → ⟩.

La oss si at vi tar mengden M = 2^ℕ — det er potensmengden, altså mengden av alle delmengder av de naturlige tallene. Det er alle mengdene vi kan konstruere av naturlige tall. Ordningen genereres av delmengderelasjonen. Det gjelder altså at {3, 5} ≤ {3, 4, 5} og så videre.

Den øvre kjeglen til mengden {1, 2, 3, 4} blir alle mengder som inneholder elementene 1, 2, 3, 4. For eksempel mengden {1, 2, 3, 4, 5, 6, 9} eller {1, 2, 3, 4, 2323, 454645}. I den øvre kjeglen er også selve mengden {1, 2, 3, 4}.

Den nedre kjeglen definerer vi tilsvarende — den inneholder elementene som er mindre enn eller lik elementet a. For a = 7 og M de naturlige tallene får vi mengden {1, 2, 3, 4, 5, 6, 7}. Det er de naturlige tallene som er mindre enn eller lik sju.

For mengden {1, 2, 3, 4} får vi alle delmengder av denne mengden.

Øvre og nedre kjegle til flere elementer

I forrige del definerte vi kjegler for ett element. Men vi kan også definere en kjegle for flere elementer. Hvis vi har en mengde M og elementene a, b, inneholder den felles øvre kjeglen deres elementene som er større enn eller lik begge elementene a og b samtidig. Med andre ord regner vi ut de øvre kjeglene til begge elementene og tar snittet av dem. Da får vi elementene som sikkert er større enn a og samtidig større enn b.

Hvis vi holder oss til de naturlige tallene: a = 3, b = 5. Alle elementer større enn eller lik a er lik mengden {3, 4, 5, 6, …} og større enn eller lik b: {5, 6, 7, 8, …}. Nå tar vi snittet, og får igjen mengden {5, 6, 7, 8, …}. Hvis vi har en totalt ordnet mengde, er det nok å finne det største av de to elementene og regne ut den øvre kjeglen til det.

For mengder blir det ikke så enkelt. Vi kan prøve å regne ut den nedre kjeglen til mengdene: a = {1, 2, 3} og b = {2, 3, 4}. Det er alle mengder som samtidig er delmengder av både a og b. Er for eksempel mengden {1, 2, 3} en delmengde av a? Ja. Er den også en delmengde av b? Nei. Denne mengden er ikke i den nedre kjeglen.

Vi kan prøve å se på hva som er den største mengden som er en delmengde av både a og b. Det er åpenbart mengden {2, 3}, som er mengden som dannes av snittet av mengdene a ∩ b. Den er i den nedre kjeglen. Og alle delmengder av denne mengden er det også. For hvis for eksempel ∅ ⊆ {2, 3} og samtidig {2, 3} ⊆ a ∧ {2, 3} ⊆ b, så gjelder sikkert også ∅ ⊆ a ∧ ∅ ⊆ b. Det følger av transitivitet.

Til slutt definerer vi øvre og nedre kjegle for en hel mengde, ikke bare for et par av elementer. La oss si at vi har en mengde M og en mengde A ⊆ M som vi vil regne ut øvre og nedre kjegle for. Da gjelder:

$$\begin{array}{rcl}H(A)& =& \{x|\mathrm{\forall }a\in A:x\ge a\}\\ D(A)& =& \{x|\mathrm{\forall }a\in A:x\le a\}\end{array}$$

Supremum og infimum

Ved hjelp av kjeglene kan vi lett definere infimum og supremum. Hvis vi har en mengde M og et element a ∈ M, er både supremum og infimum til elementet a igjen det samme elementet a.

Hvis vi derimot vil finne supremum til to elementer i M, elementene a, b, må vi gå fram på en annen måte. Supremum til elementene a, b, som vi skriver a ∨ b eller sup(a, b), er lik det minste elementet i den øvre kjeglen til elementene a, b. Vi regner altså ut alle elementer som er større enn eller lik elementene a, b, og av disse elementene tar vi det minste. Ikke det minimale, det minste. Et minste element trenger ikke generelt å finnes, så heller ikke supremum trenger generelt å finnes.

Hvis vi regner ut infimum, finner vi først den nedre kjeglen til begge elementene og så finner vi det største elementet.

Eksempel: vi vet allerede at den øvre kjeglen til tallene 3 og 5 er mengden {5, 6, 7, …}. Det minste elementet er lik fem. Det gjelder altså at sup(3, 5) = 5.

Videre vet vi at den nedre kjeglen til mengdene a = {1, 2, 3} og b = {2, 3, 4} er lik mengden av alle delmengder av mengden {2, 3}. Det er mengdene: {2, 3}, {2}, {3}, ∅. Den største av dem er nettopp mengden {2, 3}. Denne mengden er altså infimum til mengdene a, b. Vi skriver a ∧ b = {2, 3} eller inf(a, b) = {2, 3}.

Definisjon av gitter

Et gitter S er en ordnet mengde der det til hvert par av elementer a, b ∈ S finnes et supremum og et infimum, og dette infimumet og supremumet hører til mengden S. Vi kan altså skrive at en ordnet mengde S er et gitter hvis

$$\mathrm{\forall }a,b\in S:sup(a,b)\in S\text{og}inf(a,b)\in S$$

Et enkelt eksempel på et gitter er de reelle tallene med den vanlige ordningen. Det gjelder at sup(a, b) = max(a, b) og inf(a, b) = min(a, b), som alltid er reelle tall.

En mengdefamilie med ordning etter delmengderelasjonen, som vi innførte tidligere, er også et gitter. Det gjelder at sup(a, b) = a ∪ b og inf(a, b) = a ∩ b. Det er igjen mengder fra mengdefamilien.

Hvis vi som mengdefamilie S tar alle delmengder med to elementer av de naturlige tallene (for eksempel {1, 2}, {7, 19}, …), er ikke denne mengden et gitter, for for eksempel sup({1, 2}, {3, 4}) = {1, 2, 3, 4}, og mengden {1, 2, 3, 4} er ikke et element i mengden av alle delmengder med to elementer av de naturlige tallene.