Tralie (wiskunde)
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 , waarin voor elk tweetal elementen  en  de verzameling  zowel een supremum (kleinste bovengrens)  als een infimum (grootste ondergrens)  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  een tralie, dan is ook  er een, waarbij voor elk tweetal elementen het supremum en infimum omgewisseld zijn.

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

Definitie 
Een algebraïsche structuur , gevormd door een verzameling  met daarop gedefinieerd twee binaire bewerkingen,  en , heet een tralie als de bewerkingen voldoen aan:

associativiteit
 
 

commutativiteit

absorptie

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:

Immers, stel  en , dan 

en
.

Dualiteit 
Ook hier is sprake van dualiteit. Als  een tralie is, is ook  er een.

Voorbeelden 

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

Gegeven deze ordening zijn supremum en infimum gelijk aan vereniging en doorsnede:
 en 
want:
 is de kleinste verzameling waar zowel  als  een deelverzameling van is, en
 is de grootste verzameling die zowel een deelverzameling van  als een deelverzameling van  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
 als .
Deze ordening blijkt precies overeen te komen met de deelverzameling-orde, want als  dan moeten alle elementen van  ook in  liggen, en geldt dus dat .

Deze tralie is begrensd, met  en .

 Partities
Het hasse-diagram in het begin van dit artikel toont de tralie van de partities van . Daarin is de orderelatie gegeven door:

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

want  en  zijn delen van .

 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.

  en  hebben geen gezamenlijke bovengrens.
  en  hebben de gezamenlijke bovengrenzen  en , maar die kunnen niet met elkaar worden vergeleken, dus hebben  en  geen supremum.
  en  hebben de gezamenlijke ondergrenzen  en , maar die kunnen niet met elkaar worden vergeleken, dus hebben  en  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  een tralie is. Voor het supremum  en het infimum  als binaire bewerkingen geldt de commutativiteit. Verder zijn de bewerkingen associatief:
 

en
 

Ook gelden de absorpte-eigenschappen:

en

Als omgekeerd de algebraïsche structuur  een tralie is, kan een partiële ordening  gedefinieerd worden door:

 als 

Dan is ook:
 dan en slechts dan als , 

want als  dan is , dus 

en als , dan is , dus .

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

en als 
 en , dan is 

Ook volgt uit 
 en , dat  en , zodat , dus 

Verder is
 en ,

want 
 en , 
en
 en .

zodat  een bovengrens van  is en  een ondergrens. Het zijn ook respectievelijk de kleinste en de grootste, want stel:
 en ,
dan:
.

En analoog, stel:
 en ,
dan:
.

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  heeft eigenschap ".

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

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

.

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

 
Abstracte algebra
Discrete wiskunde
Ordetheorie
Wiskundige structuur