Hasse-diagram van de tralie van de partities van {1,2,3,4}
In de wiskunde is een tralie (Engels: lattice) een partieel geordendeverzameling waarvan elke eindigedeelverzameling 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.[1]
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:
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
Hasse-diagram van een tralie isomorf aan dat van de machtsverzameling van een verzameling met vier elementen
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.
geen tralie 1
geen tralie 2
geen tralie 3
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: