Tralie (wiskunde)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Hasse-diagram van een tralie als een partieel geordende verzameling

In de wiskunde is een tralie een partieel geordende verzameling waarin elke eindige deelverzameling zowel een supremum als een infimum heeft. De naam is afkomstig van de voorstelling van een tralie in een Hasse-diagram, waarin de in de ordening vergelijkbare elementen door een lijn zijn verbonden en het kleinere element lager geplaatst is dan het grotere. De zo ontstane figuur doet in sommige gevallen aan een traliewerk denken.

Definitie[bewerken]

Een tralie (L, \le, \or, \and) is een partieel geordende verzameling (L, ≤), waarin voor elk tweetal elementen x en y de verzameling {x,y} zowel een supremum (= kleinste bovengrens) x \or y als een infimum (= grootste ondergrens) x \and y heeft.

Uit de definitie volgt direct dat elke eindige (niet-lege) deelverzameling ook een supremum en een infimum heeft.

Een tralie met zowel een grootste als een kleinste element, gewoonlijk aangeduid met respectievelijk 1 en 0, heet begrensd.

Door aan een partieel geordende verzameling een grootste en een kleinste element toe te voegen ontstaat een begrensde tralie.

Dualiteit[bewerken]

Door omkering van de ordening ontstaat uit een tralie een andere tralie, waarin als het ware de begrippen groter en kleiner omgewisseld zijn. Is (L, \le, \or, \and) een tralie, dan is ook (L, \ge, \and, \or) er een.

Ordening[bewerken]

De ordening en de begrippen supremum en infimum zijn erg met elkaar verbonden. In feite leggen supremum en infimum de ordening vast. Als namelijk (L, \le, \or, \and) en (L, \le', \or, \and) beide tralies zijn, is ≤ = ≤', dat wil zeggen beide tralies hebben dezelfde partiële ordening. De ordening wordt immers bepaald door:

x \le y \Leftrightarrow x = x \and y

of equivalent door

x \le y \Leftrightarrow y = x \or y

Dus:

x \le y \Leftrightarrow x = x \and y \Leftrightarrow x \le' y .

Algebraïsche structuur[bewerken]

Doordat in een tralie bij elk tweetal elementen x en y de elementen x \or y en x \and y bestaan, zijn \and ("en") en \or ("of") binaire bewerkingen. Een tralie kan daarom ook opgevat worden als een algebraïsche structuur met deze beide bewerkingen.

Definitie[bewerken]

Een algebraïsche structuur (L, \or, \and), gevormd door een verzameling L met daarop gedefinieerd twee binaire bewerkingen, \or ("of") en \and ("en") heet een tralie als voldaan is aan:

associativiteit

 a \or (b \or c) = (a \or b) \or c
 a \and (b \and c) = (a \and b) \and c

commutativiteit

 a \or b = b \or a
 a \and  b = b \and a

absorptie

 a  \or (a \and b) = a
 a  \and (a \or b) = a

Van deze eigenschappen zijn associativiteit en commutativiteit tamelijk gewoon voor binaire bewerkingen. Het bijzondere schuilt hier in de eigenschap absorptie; deze bepaalt het karakter van de bewerkingen.

Idempotentie[bewerken]

We kunnen uit de absorptie-eigenschap afleiden:

 a  \or a = a
 a  \and a = a

Immers:

 a  \or a = a \or (a  \and (a \or b)) = a \and (a \or b) = a

en

 a  \and a = a \and (a  \or (a \and b)) = a \or (a \and b) = a .

Dualiteit[bewerken]

Ook hier is sprake van dualiteit. Als (L, \or, \and) een tralie is, is ook (L, \and, \or) er een.

Voorbeeld[bewerken]

De machtsverzameling van een verzameling V, dus de verzameling van alle deelverzamelingen van V, is een tralie. In de zin van de eerste definitie is de ordening bepaald door het begrip deelverzameling, dus:

 A \le B \Leftrightarrow  A \sub B

Supremum en infumum zijn vanzelfsprekend vereniging en doorsnede:

 A \or B = A \cup B

en

 A \and B = A \cap B.

De tralie is begrensd, met 0 = ∅ en 1 = V.

Equivalentie van beide definities[bewerken]

Het is gemakkelijk te verifiëren dat de bewerkingen in een tralie volgens de eerste definitie voldoen aan de verlangde eisen in de tweede definitie. Omgekeerd kan een partiële ordening (≤) gedefinieerd worden in een tralie (L,\or, \and ) volgens de tweede definitie, door:

x \le y als  x = x \and y.

Dan is ook:

x \le y dan en slechts dan als  y = x \or y,

want

y = x \or y \Rightarrow x \and y = x \and (x \or y) = x, dus x \le y

en

x \le y \Rightarrow x = x \and y, dus  x \or y = (x \and y) \or y = y.

Het is niet moeilijk in te zien dat de zo bepaalde relatie inderdaad een partiële ordening op L is. Verder is nu bij elk tweetal elementen x en y van L het element x \or y het verlangde supremum en x \and y het verlangde infimum, immers vanwege de absorptie-eigenschappen is:

x = x \and (x \or y), dus x \le x \or y
y = y \and (y \or x), dus y \le y \or x = x \or y .

en

 x = (x \and y) \or x, dus x \and y \le x
 y = (x \and y) \or y, dus x \and y \le y.

Dus x \or y is een majorant van {x,y} en x \and y een minorant. Het zijn ook respectievelijk de kleinste en de grootste, want stel:

x \le z \le x \or y

en

y \le z \le x \or y,

dan:

z=z\or y=(z\or x)\or y=z\or(x\or y)=(z\and(x\or y))\or(x\or y)=x\or y,

En analoog, stel:

x \and y \le z \le x

en

x \and y \le z \le y ,

dan:

z=z\and y=(z\and x)\and y=z\and(x\and y)=(z\or(x\and y))\and (x\and y)=x\and y.

We zien dus dat een tralie in de eerste zin ook een tralie in de tweede zin is en omgekeerd. Bovendien hebben we gezien dat als de bewerkingen in de algebraïsche tralie overeenkomen met die in de ordeningstralie, de door de bewerkingen geïnduceerde partiële ordening dezelfde is als de oorspronkelijke. Daarmee zijn de twee begrippen tralie geheel uitwisselbaar en kan al naargelang de toepassing de daartoe meest geschikte vorm gekozen worden.

Toepassingen[bewerken]

In de formeleconceptanalyse maakt men gebruikt van tralies voor het analyseren van gegevens die voorliggen als een binaire relatie: "object x heeft eigenschap y".