Gitter (ordning)

Ett gitter eller lattice är inom matematiken en partiellt ordnad mängd i vilken varje par av element har en minsta övre gräns och en största undre gräns. De kan även kategoriseras som algebraiska strukturer som uppfyller vissa axiomatiska identiteter. Varje gitter kan representeras av ett Hassediagram.

Ordbok

Gitter som partiellt ordnade mängder

En partiellt ordnad mängd (L,<) är ett gitter om varje par av element i mängden har en minsta övre gräns och en största undre gräns. För ett sådant par (a, b) betecknas den minsta övre gränsen med a ${\displaystyle \lor }$ b, den största undre gränsen med a ${\displaystyle \land }$ b. På detta vis definierar vi gränserna som binära operationer. Motsvarande mängdoperation, att från en icke-tom ändlig delmängd ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}\subseteq L}$ erhålla minsta övre gräns (respektive största undre gräns) betecknas ${\displaystyle \bigvee A=a_{1}\lor \cdots \lor a_{n}}$ (resp.${\displaystyle \bigwedge A=a_{1}\land \cdots \land a_{n}}$). Gittret är komplett om mängdoperationen kan utsträckas till alla delmängder av L, även den tomma mängden och eventuella oändliga delmängder.

Ett gitter (L, ${\displaystyle {\land },{\lor })}$ kallas en Boolesk algebra om det är distributivt och varje element har ett komplement. Ett slutet gitter har ett största och ett minsta element, vilka normalt betecknas med 1 respektive 0. Ett komplett gitter är alltid slutet, med ${\displaystyle 1=\bigwedge \emptyset }$ och ${\displaystyle 0=\bigvee \emptyset }$. Omvänt är ett ändligt slutet gitter alltid komplett.

Se även

• Gitter (grupp)

Källor

• Birkhoff, G. Lattice Theory, Am. Math. Soc., 1967.
• Bäckström, Karl-Johan, Diskret matematik, Studentlitteratur, 1986.