Tralie (wiskunde)

gedeeltelijk geordende verzameling elementparen

In de wiskunde is een tralie 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.

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

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.

GeschiedenisBewerken

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]

DefinitieBewerken

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.

DualiteitBewerken

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 structuurBewerken

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.

DefinitieBewerken

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.

IdempotentieBewerken

Uit de absorptie-eigenschap volgt dat:

 
 

Immers, stel   en  , dan

 

en

 .

DualiteitBewerken

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

VoorbeeldenBewerken

 
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.

  1.   en   hebben geen gezamenlijke bovengrens.
  2.   en   hebben de gezamenlijke bovengrenzen   en  , maar die kunnen niet met elkaar worden vergeleken, dus hebben   en   geen supremum.
  3.   en   hebben de gezamenlijke ondergrenzen   en  , maar die kunnen niet met elkaar worden vergeleken, dus hebben   en   geen infimum.

Equivalentie van beide definitiesBewerken

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.

ToepassingenBewerken

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

Volledige tralieBewerken

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.