Gitter

Ett gitter är en ordnad mängd som har den extra egenskapen att det för varje par av element i gittret måste finnas ett supremum och ett infimum, som också tillhör gittret.

Övre och undre kon

Till att börja med har vi en mängd M där vi har definierat någon ordning ≤. Ordningen kan vara godtycklig, men den måste uppfylla villkoren för en ordningsrelation.

Sedan tar vi något element a ur mängden M. Den övre konen till elementet a i mängden M definierar vi som alla x ∈ M som är större än eller lika med a, alltså de för vilka a ≤ x.

Om vi som mängd tar de positiva heltalen och som element a = 7, så är den övre konen mängden av talen {7, 8, 9, …}. På de reella talen skulle vi få intervallet [7, +∞[.

Om vi i stället tog mängden M = 2^ℤ+ — det är en potensmängd, alltså mängden av alla delmängder av de positiva heltalen. Det är alltså alla mängder som vi kan konstruera med hjälp av de positiva heltalen. Ordningen genereras av delmängdsrelationen. Det gäller alltså att {3, 5} ≤ {3, 4, 5} osv.

Den övre konen till mängden {1, 2, 3, 4} blir alla mängder som innehåller elementen 1, 2, 3, 4. Till exempel mängden {1, 2, 3, 4, 5, 6, 9} eller {1, 2, 3, 4, 2323, 454645}. I den övre konen finns också själva mängden {1, 2, 3, 4}.

Den undre konen definierar vi på liknande sätt — den innehåller de element som är mindre än eller lika med elementet a. För a = 7 och M de positiva heltalen får vi mängden {1, 2, 3, 4, 5, 6, 7}. Det är de positiva heltal som är mindre än eller lika med sju.

För mängden {1, 2, 3, 4} får vi alla delmängder av den här mängden.

Övre och undre kon till flera element

I föregående avsnitt definierade vi koner för ett element. Men vi kan också definiera en kon för flera element. Om vi har en mängd M och elementen a, b, så innehåller deras gemensamma övre kon de element som är större än eller lika med både a och b samtidigt. Med andra ord räknar vi ut de övre konerna för båda elementen och tar deras snitt. Då får vi de element som säkert är större än a och samtidigt större än b.

Om vi stannar vid de positiva heltalen: a = 3, b = 5. Alla element som är större än eller lika med a bildar mängden {3, 4, 5, 6, …} och de som är större än eller lika med b: {5, 6, 7, 8, …}. Nu tar vi snittet, och får återigen mängden {5, 6, 7, 8, …}. Om vi har en totalt ordnad mängd räcker det att ta reda på det större av de två elementen och räkna ut dess övre kon.

För mängder blir det inte lika enkelt. Vi kan försöka räkna ut den undre konen till mängderna a = {1, 2, 3} och b = {2, 3, 4}. Det är alla mängder som samtidigt är delmängder av både a och b. Är till exempel mängden {1, 2, 3} en delmängd av a? Ja. Är den också en delmängd av b? Nej. Den här mängden kommer inte att ligga i den undre konen.

Vi kan försöka se efter vilken som är den största mängden som är en delmängd av både a och b. Det blir uppenbarligen mängden {2, 3}, som uppstår som snittet av mängderna a ∩ b. Den ligger i den undre konen. Och alla delmängder av den här mängden också. För om till exempel ∅ ⊆ {2, 3} och samtidigt {2, 3} ⊆ a ∧ {2, 3} ⊆ b, så gäller säkert också ∅ ⊆ a ∧ ∅ ⊆ b. Det följer av transitiviteten.

Till sist definierar vi övre och undre kon för en hel mängd, inte bara för ett par av element. Låt M vara en mängd och A ⊆ M någon mängd för vilken vi vill räkna ut övre och undre kon. Då gäller:

$$\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 och infimum

Med hjälp av konerna kan vi lätt definiera infimum och supremum. Om vi har en mängd M och ett element a ∈ M, så är supremum och infimum av elementet a återigen samma element a.

Men om vi vill ta reda på supremum för två element ur M, elementen a, b, så måste vi göra på ett annat sätt. Supremum av elementen a, b, som vi betecknar a ∨ b eller sup(a, b), är lika med det minsta elementet i den övre konen till elementen a, b. Vi räknar alltså ut alla element som är större än eller lika med elementen a, b, och av de elementen tar vi det minsta. Inte det minimala, det minsta. Ett minsta element behöver i allmänhet inte finnas, och därför behöver inte heller supremum alltid finnas.

Om vi räknar ut infimum, så hittar vi först den undre konen till båda elementen och sedan hittar vi det största elementet.

Exempel: vi vet redan att den övre konen till talen 3 och 5 är mängden {5, 6, 7, …}. Det minsta elementet är lika med fem. Det gäller alltså att sup(3, 5) = 5.

Vidare vet vi att den undre konen till mängderna a = {1, 2, 3} och b = {2, 3, 4} är lika med mängden av alla delmängder av mängden {2, 3}. Det motsvarar mängderna: {2, 3}, {2}, {3}, ∅. Den största mängden är just mängden {2, 3}. Den här mängden är alltså infimum av mängderna a, b. Vi skriver a ∧ b = {2, 3} eller inf(a, b) = {2, 3}.

Definition av gitter

Ett gitter S är en ordnad mängd där det till varje par av element a, b ∈ S finns ett supremum och ett infimum, och där detta infimum och supremum tillhör mängden S. Vi kan alltså skriva att en ordnad mängd S är ett gitter, om

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

Ett enkelt exempel på ett gitter är de reella talen med den vanliga ordningen. Där gäller att sup(a, b) = max(a, b) och inf(a, b) = min(a, b), vilket alltid är reella tal.

Ett system av mängder med ordning efter delmängdsrelationen, som vi har infört tidigare, är också ett gitter. Det gäller att sup(a, b) = a ∪ b och inf(a, b) = a ∩ b. Det är återigen mängder ur systemet av mängder.

Om vi som mängdsystem S tar alla tvåelementiga delmängder av de positiva heltalen (t.ex. {1, 2}, {7, 19}, …), så är den här mängden inte ett gitter, eftersom till exempel sup({1, 2}, {3, 4}) = {1, 2, 3, 4} och mängden {1, 2, 3, 4} inte är ett element i mängden av alla tvåelementiga delmängder av de positiva heltalen.