Gitre

Et gitter er en ordnet mængde, som er udvidet med den egenskab, at der for ethvert par af elementer i det givne gitter skal findes et supremum og et infimum, som også tilhører det givne gitter.

Øvre og nedre kegle

Til at begynde med har vi en mængde M, som vi har defineret en ordning ≤ på. Denne ordning kan være vilkårlig, men skal opfylde betingelserne for en ordningsrelation.

Videre tager vi et element a fra mængden M. Den øvre kegle af elementet a i mængden M definerer vi som alle x ∈ M, der er større end eller lig med a, altså for dem gælder a ≤ x.

Hvis vi som mængde tager de naturlige tal og som element a = 7, så er den øvre kegle mængden af tal {7, 8, 9, …}. På de reelle tal ville vi få intervallet [7; ∞[.

Hvis vi tog mængden M = 2^ℕ — det er potensmængden, altså mængden af alle delmængder af de naturlige tal. Det er altså alle de mængder, som vi kan konstruere ved hjælp af de naturlige tal. Ordningen genereres ved hjælp af delmængderelationen. Der gælder altså, at {3, 5} ≤ {3, 4, 5} osv.

Den øvre kegle af mængden {1, 2, 3, 4} bliver alle de mængder, som indeholder elementerne 1, 2, 3, 4. For eksempel mængden {1, 2, 3, 4, 5, 6, 9} eller {1, 2, 3, 4, 2323, 454645}. I den øvre kegle vil også selve mængden {1, 2, 3, 4} være.

Den nedre kegle definerer vi tilsvarende — den indeholder de elementer, som er mindre end eller lig med elementet a. For a = 7 og M de naturlige tal får vi mængden {1, 2, 3, 4, 5, 6, 7}. Det er de naturlige tal, som er mindre end eller lig med syv.

For mængden {1, 2, 3, 4} får vi alle delmængder af denne mængde.

Øvre og nedre kegle af flere elementer

I det foregående afsnit definerede vi keglerne for ét element. Men vi kan også definere en kegle for flere elementer. Hvis vi har en mængde M og elementerne a, b, så vil deres fælles øvre kegle indeholde de elementer, som er større end eller lig med begge elementer a og b samtidig. Med andre ord beregner vi de øvre kegler af begge elementer og finder deres fællesmængde. Derved får vi de elementer, som helt sikkert er større end a og samtidig større end b.

Hvis vi bliver ved de naturlige tal: a = 3, b = 5. Alle elementer større end eller lig med a er lig med mængden {3, 4, 5, 6, …} og med b: {5, 6, 7, 8, …}. Nu danner vi fællesmængden, og vi får igen mængden {5, 6, 7, 8, …}. Hvis vi har en totalt ordnet mængde, er det nok at finde det største af de to elementer og beregne dets øvre kegle.

I tilfældet med mængder bliver det ikke så enkelt. Vi kan prøve at beregne den nedre kegle af mængderne: a = {1, 2, 3} og b = {2, 3, 4}. Det er alle de mængder, som samtidig er delmængder af både a og b. Er for eksempel mængden {1, 2, 3} en delmængde af a? Ja. Er den også en delmængde af b? Nej. Denne mængde vil ikke være i den nedre kegle.

Vi kan prøve at se på, hvad den største mængde bliver, som er en delmængde af både a og b. Det bliver åbenbart mængden {2, 3}, som er den mængde, der opstår som fællesmængden af mængderne a ∩ b. Den vil være i den nedre kegle. Og alle delmængder af denne mængde også. For hvis for eksempel ∅ ⊆ {2, 3} og samtidig {2, 3} ⊆ a ∧ {2, 3} ⊆ b, så gælder helt sikkert også ∅ ⊆ a ∧ ∅ ⊆ b. Det følger af transitiviteten.

Til sidst definerer vi den øvre og nedre kegle for en hel mængde, ikke kun for et par af elementer. Lad os have en mængde M og en mængde A ⊆ M, som vi vil beregne den øvre og nedre kegle for. Så gælder:

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

Supremum og infimum

Ved hjælp af keglerne kan vi let definere infimum og supremum. Hvis vi har en mængde M og et element a ∈ M, så er både supremum og infimum af elementet a igen det samme element a.

Hvis vi derimod vil finde supremum af to elementer fra M, elementerne a, b, så må vi gøre det anderledes. Supremum af elementerne a, b, som vi skriver a ∨ b eller sup(a, b), er lig med det mindste element i den øvre kegle af elementerne a, b. Vi beregner altså alle de elementer, som er større end eller lig med elementerne a, b, og af disse elementer tager vi det mindste element. Ikke det minimale, det mindste. Et mindste element behøver generelt ikke at findes, så heller ikke supremum behøver generelt at findes.

Hvis vi beregner infimum, så finder vi først den nedre kegle af begge elementer og derefter finder vi det største element.

Eksempel: vi ved allerede, at den øvre kegle af tallene 3 og 5 er mængden {5, 6, 7, …}. Det mindste element er lig med fem. Der gælder altså, at sup(3, 5) = 5.

Videre ved vi, at den nedre kegle af mængderne a = {1, 2, 3} og b = {2, 3, 4} er lig med mængden af alle delmængder af mængden {2, 3}. Det svarer til mængderne: {2, 3}, {2}, {3}, ∅. Og den største mængde er netop mængden {2, 3}. Denne mængde er altså infimum af mængderne a, b. Vi skriver a ∧ b = {2, 3} eller inf(a, b) = {2, 3}.

Definition af gitter

Et gitter S er en ordnet mængde, hvor der til ethvert par af elementer a, b ∈ S findes et supremum og et infimum, og dette infimum og supremum tilhører mængden S. Vi kan altså skrive, at den ordnede mængde 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 tal med den klassiske ordning. Der gælder, at sup(a, b) = max(a, b) og inf(a, b) = min(a, b), som altid er reelle tal.

Et system af mængder med ordning efter relationen at være delmængde, som vi har indført tidligere, er også et gitter. Der gælder, at sup(a, b) = a ∪ b og inf(a, b) = a ∩ b. Det er igen mængder fra mængdesystemet.

Hvis vi som mængdesystem S tager alle to-elementsdelmængder af de naturlige tal (f.eks. {1, 2}, {7, 19}, …), så er denne mængde ikke et gitter, fordi for eksempel sup({1, 2}, {3, 4}) = {1, 2, 3, 4}, og mængden {1, 2, 3, 4} ikke er et element i mængden af alle to-elementsdelmængder af de naturlige tal.