Tralie (wiskunde)

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. Dit houdt onder meer in dat weliswaar niet van elk tweetal elementen uitgemaakt kan worden welke de grotere is, maar wel dat er een element is dat groter is en een dat kleiner is dan beide. 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.

Inhoud

1 Definitie
- 1.1 Dualiteit
- 1.2 Ordening
2 Algebraïsche structuur
3 Equivalentie van beide definities

[bewerk] Definitie

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.

[bewerk] Dualiteit

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.

[bewerk] Ordening

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 ≤ = ≤', d.w.z. beide tralies hebben dezelfde partiële ordening. De ordening wordt immers bepaald door:

$x \le y \Leftarrow\Rightarrow x = x \and y$

of equivalent door

$x \le y \Leftarrow\Rightarrow y = x \or y$

Dus:

$x \le y \Leftarrow\Rightarrow x = x \and y \Leftarrow\Rightarrow x \le' y$ .

[bewerk] Algebraïsche structuur

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.

[bewerk] Definitie

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.

[bewerk] Idempotentie

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$

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

[bewerk] Dualiteit

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

[bewerk] Voorbeeld

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 \Leftarrow\Rightarrow A \sub B$

Supremum en infumum zijn vanzelfsprekend vereniging en doorsnede:

$A \or B = A \cup B$

$A \and B = A \cap B$ .

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

[bewerk] Equivalentie van beide definities

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$

$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$ .

$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$

$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$

$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 naar gelang de toepassing de daartoe meest geschikte vorm gekozen worden.

Categorieën: Discrete wiskunde | Algebra

Tralie (wiskunde)

Inhoud

[bewerk] Definitie

[bewerk] Dualiteit

[bewerk] Ordening

[bewerk] Algebraïsche structuur

[bewerk] Definitie

[bewerk] Idempotentie

[bewerk] Dualiteit

[bewerk] Voorbeeld

[bewerk] Equivalentie van beide definities

Views

Navigatie

Informatie

Zoeken

in andere talen