Tralie (wiskunde)

Hasse-diagram van de tralie van de partities van {1,2,3,4}

In de wiskunde is een tralie (Engels: lattice) een partieel geordende verzameling waarvan elke eindige deelverzameling zowel een supremum als een infimum heeft. Supremum en infimum kunnen buiten de gekozen deelverzameling liggen. 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.

Het hasse-diagram van een eindige tralie bestaat uit een graaf met één component, omdat ieder paar elementen zowel een supremum als een infimum heeft. Twee elementen uit verschillende componenten van een graaf hebben geen gezamenlijk supremum of infimum.

Naast de definitie van een tralie als een bijzondere partieel geordende verzameling, is er een equivalente definitie als speciale algebraïsche structuur met twee binaire bewerkingen die een partiële orde induceren.

Geschiedenis

Aan het einde van de negentiende eeuw introduceerden Charles Sanders Peirce en Ernst Schröder het begrip tralie toen zij probeerden axioma's voor de Booleaanse algebra op te stellen. Richard Dedekind kwam onafhankelijk van hen tot de ontdekking van hetzelfde begrip via zijn onderzoek naar idealen van algebraïsche getallen. Hun ideeën trokken evenmin als de vroege resultaten van Edward Huntington veel aandacht. De ontwikkeling van de theorie, waarin tralies worden gebruikt, begon met het werk van Garrett Birkhoff in het midden van de jaren 1930.

Definitie

Een tralie is een partieel geordende verzameling $(L,\leq )$, waarin voor elk tweetal elementen $x$ en $y$ de verzameling $\{x,y\}$ zowel een supremum (kleinste bovengrens) $x\lor y$ als een infimum (grootste ondergrens) $x\land 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

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,\leq )$ een tralie, dan is ook $(L,\geq )$ er een, waarbij voor elk tweetal elementen het supremum en infimum omgewisseld zijn.

Algebraïsche structuur

Doordat in een tralie bij elk tweetal elementen $x$ en $y$ de elementen $x\lor y$ en $x\land y$ bestaan, zijn $\land$ en $\lor$ binaire bewerkingen. Een tralie kan daarom ook opgevat worden als een algebraïsche structuur met deze beide bewerkingen.

Definitie

Een algebraïsche structuur $(L,\lor ,\land )$, gevormd door een verzameling $L$ met daarop gedefinieerd twee binaire bewerkingen, $\lor$ en $\land$, heet een tralie als de bewerkingen voldoen aan:

associativiteit

$a\lor (b\lor c)=(a\lor b)\lor c$

$a\land (b\land c)=(a\land b)\land c$

commutativiteit

$a\lor b=b\lor a$

$a\land b=b\land a$

absorptie

$a\lor (a\land b)=a$

$a\land (a\lor b)=a$

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

Idempotentie

Uit de absorptie-eigenschap volgt dat:

$a\lor a=a$

$a\land a=a$

Immers, stel $a\lor b=c$ en $a\land b=d$, dan

$a\lor a=a\lor (a\land (a\lor b))=a\lor (a\land c)=a$

en

$a\land a=a\land (a\lor (a\land b))=a\land (a\lor d)=a$.

Dualiteit

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

Voorbeelden

Hasse-diagram van een tralie isomorf aan dat van de machtsverzameling van een verzameling met vier elementen

Machtsverzameling

De machtsverzameling van een verzameling $V$, 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\leq B\Leftrightarrow A\subseteq B$

Gegeven deze ordening zijn supremum en infimum gelijk aan vereniging en doorsnede:

$A\lor B=A\cup B$ en $A\land B=A\cap B$

want:

$A\cup B$ is de kleinste verzameling waar zowel $A$ als $B$ een deelverzameling van is, en

$A\cap B$ is de grootste verzameling die zowel een deelverzameling van $A$ als een deelverzameling van $B$ is.

Alternatief zouden we, in de zin van de uit de abstracte algebra stammende definitie, ook eerst de twee operaties kunnen vastleggen. Dan kunnen we een ordening definiëren als

$A\leq B$ als $A=A\land B$.

Deze ordening blijkt precies overeen te komen met de deelverzameling-orde, want als $A=A\cap B$ dan moeten alle elementen van $A$ ook in $B$ liggen, en geldt dus dat $A\subseteq B$.

Deze tralie is begrensd, met $0=\varnothing$ en $1=V$.

Partities

Het hasse-diagram in het begin van dit artikel toont de tralie van de partities van $\{1,2,3,4\}$. Daarin is de orderelatie gegeven door:

$P'\leq P$

als de partitie $P'$ een verfijning is van $P$, d.w.z. dat de elementen in $P'$ deelverzamelingen zijn van de elementen van $P$. Er geldt bijvoorbeeld:

$\{\{1\},\{2,3\},\{4\}\}\leq \{\{1\},\{2,3,4\}\}$

want $\{2,3\}$ en $\{4\}$ zijn delen van $\{2,3,4\}$.

Tegenvoorbeelden

Veel partieel geordende verzamelingen zijn geen tralie. Er zijn daarin bij twee verschillende elementen meer gezamenlijke boven- of ondergrenzen te vinden, maar die kunnen in de gegeven orde niet met elkaar worden vergeleken, dus is er geen supremum of infimum.

• 
  geen tralie 1
• 
  geen tralie 2
• 
  geen tralie 3

1. $c$ en $d$ hebben geen gezamenlijke bovengrens.
2. $b$ en $c$ hebben de gezamenlijke bovengrenzen $d$ en $e$, maar die kunnen niet met elkaar worden vergeleken, dus hebben $b$ en $c$ geen supremum.
3. $a$ en $b$ hebben de gezamenlijke ondergrenzen $d$ en $i$, maar die kunnen niet met elkaar worden vergeleken, dus hebben $a$ en $b$ geen infimum.

Equivalentie van beide definities

De beide definities van een tralie zijn equivalent in de zin dat in een tralie als partieel geordende verzameling het supremum en het infimum twee binaire bewerkingen zijn die voldoen aan de daaraan gestelde eisen voor een tralie als algebraïsche structuur, en omgekeerd de binaire bewerkingen in een tralie als algebraïsche structuur een partiële orde induceren met de verlangde eigenschap.

Stel dat de partieel geordende verzameling $(L,\leq )$ een tralie is. Voor het supremum $\lor$ en het infimum $\land$ als binaire bewerkingen geldt de commutativiteit. Verder zijn de bewerkingen associatief:

$x\lor (y\lor z)=\sup\{x,y\lor z\}=\sup\{x,y,z\}=(x\lor y)\lor z$

en

$x\land (y\land z)=\inf\{x,y\land z\}=\inf\{x,y,z\}=(x\land y)\land z$

Ook gelden de absorpte-eigenschappen:

$x\lor (x\land y)=\sup\{x,\inf\{x,y\}\}=x$

en

$x\land (x\lor y)=\inf\{x,\sup\{x,y\}\}=x$

Als omgekeerd de algebraïsche structuur $(L,\lor ,\land )$ een tralie is, kan een partiële ordening $\leq$ gedefinieerd worden door:

$x\leq y$ als $x=x\land y$

Dan is ook:

$x\leq y$ dan en slechts dan als $y=x\lor y$,

want als $x\leq y$ dan is $x=x\land y$, dus $x\lor y=(x\land y)\lor y=y\lor (y\land x)=y$

en als $y=x\lor y$, dan is $x\land y=x\land (x\lor y)=x$, dus $x\leq y$.

Inderdaad is $\leq$ een parttiële orde, want er geldt:

$x\leq x$, want $x\land x=x$

en als

$x\leq y$ en $y\leq x$, dan is $x=x\land y=y\land x=y$

Ook volgt uit

$x\leq y$ en $y\leq x$, dat $x=x\land y$ en $y=y\land z$, zodat $x=x\land (y\land z)=(x\land y)\land z=x\land z$, dus $x\leq z$

Verder is

$x\lor y=\sup\{x,y\}$ en $x\land y=\inf\{x,y\}$,

want

$x\leq x\lor y$ en $y\leq x\lor y$,

en

$x\land y\leq x$ en $x\land y\leq y$.

zodat $x\lor y$ een bovengrens van $\{x,y\}$ is en $x\land y$ een ondergrens. Het zijn ook respectievelijk de kleinste en de grootste, want stel:

$x\leq z\leq x\lor y$ en $y\leq z\leq x\lor y$,

dan:

$z=z\lor y=(z\lor x)\lor y=z\lor (x\lor y)=(z\land (x\lor y))\lor (x\lor y)=x\lor y$.

En analoog, stel:

$x\land y\leq z\leq x$ en $x\land y\leq z\leq y$,

dan:

$z=z\land y=(z\land x)\land y=z\land (x\land y)=(z\lor (x\land y))\land (x\land y)=x\land y$.

De twee begrippen tralie zijn dus geheel uitwisselbaar en al naargelang de toepassing kan de daartoe meest geschikte vorm gekozen worden.

Toepassingen

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

Volledige tralie

Een tralie $V$ heet volledig, als iedere deelverzameling (ook de lege en eventueel oneindige) een supremum en een infimum heeft.

Het is voldoende voor elke deelverzameling $M$ het bestaan van het supremum te eisen, want

$\inf(M)=\sup\{x\in V:(\forall \,y\in M:x\leq y)\}$.

Iedere volledige tralie is begrensd en iedere eindige niet-lege tralie is volledig, dus ook begrensd.

Voetnoten