Tralie (wiskunde)

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
Hasse-diagram van de tralie van de partities van {1,2,3,4}

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.

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

Uit de absorptie-eigenschap volgt dat:

Immers, stel en , dan

en

.

Dualiteit[bewerken | brontekst bewerken]

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

Voorbeelden[bewerken | brontekst bewerken]

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 definities[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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

Volledige tralie[bewerken | brontekst bewerken]

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.