Gitter (ordning)

Från Wikipedia
Hoppa till navigering Hoppa till sök

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.

Gitter som partiellt ordnade mängder[redigera | redigera wikitext]

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 b, den största undre gränsen med a b. På detta vis definierar vi gränserna som binära operationer. Motsvarande mängdoperation, att från en icketom ändlig delmängd erhålla minsta övre gräns (respektive största undre gräns) betecknas (resp.). 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, 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 och . Omvänt är ett ändligt slutet gitter alltid komplett.

Se även[redigera | redigera wikitext]

Källor[redigera | redigera wikitext]

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