Wikisage is op 1 na de grootste internet-encyclopedie in het Nederlands. Iedereen kan de hier verzamelde kennis gratis gebruiken, zonder storende advertenties. De Koninklijke Bibliotheek van Nederland heeft Wikisage in 2018 aangemerkt als digitaal erfgoed.
- Wilt u meehelpen om Wikisage te laten groeien? Maak dan een account aan. U bent van harte welkom. Zie: Portaal:Gebruikers.
- Bent u blij met Wikisage, of wilt u juist meer? Dan stellen we een bescheiden donatie om de kosten te bestrijden zeer op prijs. Zie: Portaal:Donaties.
Gebruiker:H/Tweeplaatsige relatie
In de wiskunde koppelt een tweeplaatsige relatie oftewel binaire relatie elementen uit een verzameling aan elementen uit een andere (of dezelfde) verzameling. Een tweeplaatsige relatie is een specifiek geval van een relatie, namelijk een relatie met een plaatsigheid of ariteit van 2. Anders geformuleerd is een tweeplaatsige relatie de wiskundige beschrijving van het al dan niet bestaan van een zeker verband tussen twee objecten.
Tweeplaatsige relaties worden vaak simpelweg "relaties" genoemd. Historisch gezien werden met "relaties" oorspronkelijk ook enkel tweeplaatsige relaties aangeduid. Later is het begrip uitgebreid. Zie het artikel Relatie voor meer over de oorsprong en de geschiedenis van het begrip.
Een intuïtief alledaags voorbeeld van een tweeplaatsige relatie is het begrip bezitten. De tweeplaatsige relatie bezitten koppelt mensen aan objecten, oftewel elementen uit de verzameling van alle mensen aan elementen uit de verzameling van alle objecten. De koning wordt door deze relatie aan de kroon gekoppeld en als Dirk en Anna samen een huis gekocht hebben, dan worden zij beiden aan dat huis gekoppeld. Niemand is aan de zon of de maan gekoppeld en mensen die niets bezitten worden door de relatie bezitten nergens aan gekoppeld.
Een voorbeeld van een tweeplaatsige relatie die elementen uit een verzameling koppelt aan elementen uit dezelfde verzameling is de relatie houden van, die mensen aan mensen koppelt. Deze relatie koppelt personen die van elkaar houden aan elkaar. Iets preciezer geformuleerd koppelt houden van persoon X aan persoon Y indien (en enkel indien) persoon X van persoon Y houdt. Aldus wordt Werther bijvoorbeeld aan Charlotte gekoppeld, maar Charlotte niet aan Werther. Werther houdt, met andere woorden, van Charlotte, maar Charlotte houdt niet van Werther. De koppeling is in zekere zin dus gericht. Er zijn ook paren die wel in beide richtingen aan elkaar gekoppeld zijn, zoals Romeo en Julia. Casanova is een voorbeeld van iemand die aan vele personen gekoppeld is (en aan wie vele personen gekoppeld zijn) en het is voorstelbaar dat er mensen zijn die aan niemand gekoppeld zijn. Narcissus, ten slotte, is iemand die aan zichzelf gekoppeld is.
In de wiskunde zijn tweeplaatsige relaties alomtegenwoordig. Ze worden gebruikt om is groter dan en is deelbaar door in de rekenkunde, is congruent aan in de meetkunde en vele andere begrippen mee te definiëren. Daarnaast wordt de functie, een van de belangrijkste begrippen in de wiskunde, meestal gedefinieerd als een speciaal geval van een tweeplaatsige relatie. Ook andere exacte wetenschappen passen tweeplaatsige relaties veelvuldig toe in uiteenlopende gebieden. In de informatica worden ze onder andere gebruikt in het relationele model voor databases, maar ook in de economie, biologie, natuurkunde en andere wetenschappen worden diverse fenomenen met tweeplaatsige relaties gemodelleerd.
Definitie
Een tweeplaatsige relatie R is formeel gedefinieerd als een 3-tupel (G, A, B) waarbij A en B willekeurige verzamelingen zijn en
- G <math>\subseteq</math> A × B.
Deze voorwaarde betekent dat G een deelverzameling is van het Cartesisch product van A en B.
De volgorde van de leden van het 3-tupel in de definitie kan variëren. Soms wordt een tweeplaatsige relatie bijvoorbeeld gedefinieerd als het 3-tupel (A, B, G) in plaats van (G, A, B).
Soms wordt de tweeplaatsige relatie simpelweg gedefinieerd als een verzameling geordende paren, overeenkomstig met de G uit de eerste definitie. Uit welke verzamelingen de leden van de geordende paren komen, moet in dat geval expliciet genoemd worden of uit de context blijken. Strikt genomen wordt in dit geval niet het begrip tweeplaatsige relatie gedefinieerd, maar het begrip tweeplaatsige relatie over ... en ..., omdat een verzameling paren enkel een tweeplaatsige relatie is in de context van de verzamelingen waaruit de leden van de paren komen.[1] De verzameling { (1, 2), (2, 3) } is bijvoorbeeld wel een tweeplaatsige relatie over N, maar niet over de verzameling van alle meetkundige figuren. Een verzameling paren is, met andere woorden, niet een tweeplaatsige relatie zonder meer.
Het belangrijkste verschil tussen deze definities komt aan het licht wanneer tweeplaatsige relaties op gelijkheid getoetst worden. Neem de relaties R = (G, X, Y) en S = (G, X, Z), waarbij Y ≠ Z. Het is evident dat in dit geval R ≠ S, hoewel de verzameling geordende paren G in beide relaties hetzelfde is. Onder de tweede definitie zouden dezelfde relaties echter als volgt gedefinieerd worden: R = G en S = G, waaruit volgt dat R = S.
In sommige systemen van de axiomatische verzamelingenleer worden relaties gedefinieerd op klassen in plaats van verzamelingen. Deze aanpassing is onder andere nodig om de begrippen is een element van en is een deelverzameling van te kunnen beschrijven, zonder dat dit tot de Russell-paradox leidt.
Terminologie
Als R = (G, A, B) een tweeplaatsige relatie is dan wordt G de grafiek van R genoemd. A wordt het domein van R genoemd en B wordt het codomein van R genoemd. Men zegt ook dat R een relatie over A en B is. Van een tweeplaatsige relatie R = (G, A, A), waarbij zowel het domein als het codomein de verzameling A is, wordt gezegd dat R een tweeplaatsige relatie over A is of dat R een tweeplaatsige relatie op A is.
Als (a, b) <math>\in</math> G dan worden a en b argumenten van R genoemd. Daarbij is a een linker argument en b een rechter argument. Verder zegt men in dit geval dat a in R-relatie staat tot b. Als uit de context duidelijk is welke relatie bedoeld wordt dan zegt men ook simpelweg dat a in relatie tot b staat. Wanneer de definitie gebruikt wordt waarbij een tweeplaatsige relatie een verzameling geordende paren is, dan zegt men dat a in relatie tot b staat als (a, b) <math>\in</math> R.
De lege relatie over A en B is de tweeplaatsige relatie over A en B waarvan de grafiek de lege verzameling is. Als R de lege relatie over A en B is, dan geldt dat er geen a <math>\in</math> A en b <math>\in</math> B zijn zodanig dat a in R-relatie staat tot b.
De universele relatie over A en B is de tweeplaatsige relatie waarvan de grafiek het Cartesisch product van A en B is. Als R de universele relatie over A en B is, dan geldt voor alle a <math>\in</math> A en b <math>\in</math> B dat a in R-relatie staat tot b.
Notatie
De uitspraak "a staat in R-relatie tot b" wordt op verschillende manieren genoteerd:
- (functienotatie) R(a, b)
- (infixnotatie) a R b
- (Poolse notatie) R a b
De functienotatie komt overeen met de karakteristieke functie van de grafiek van R.
Voorbeelden
Een voorbeeld van een tweeplaatsige relatie over de verzameling van alle mensen is houden van. Wanneer we deze relatie aanduiden met de letter L (van liefde) dan betekent L(Romeo, Julia) dat Romeo van Julia houdt. L(Julia, Romeo) zou betekenen dat Julia van Romeo houdt.[2]
Voor een ander voorbeeld beschrijven we eerst de verzamelingen waarover we de relatie definiëren.
- X = { Anna, Boris, Christine, Dirk }
is een verzameling van vier willekeurige mensen en
- Y = { Boek, Bal, Fiets, Zon, Maan }
is een verzameling van vijf objecten. Verder definiëren we
- G = { (Anna, Bal), (Christine, Boek), (Dirk, Boek), (Dirk, Fiets) }.
Merk op dat alle linker leden van de paren in G uit X komen en alle rechter leden uit Y komen, waaruit volgt dat
- G <math>\subseteq</math> X × Y.
B = (G, X, Y) is dus een tweeplaatsige relatie over X en Y.
Als we met de relatie B het begrip bezitten willen beschrijven dan betekent B(Dirk, Fiets) dat Dirk de fiets bezit en B(Anna, Boek) dat Anna het boek bezit. Het eerste is volgens de door ons geconstrueerde relatie waar en het tweede niet waar. Merk op dat volgens onze relatie niemand de zon en de maan bezit, dat het boek in bezit is van zowel Christine als Dirk en dat Boris helemaal niets bezit.
Eigenschappen van tweeplaatsige relaties
Zij R een willekeurige tweeplaatsige relatie over A en B.
- R is links-volledig desda er voor alle a <math>\in</math> A een b <math>\in</math> B is, zodanig dat a R b.
- R is rechts-volledig of surjectief desda er voor alle b <math>\in</math> B een a <math>\in</math> A is, zodanig dat a R b.
- R is links-definiet of injectief desda geen twee verschillende linker argumenten van R in relatie staan tot hetzelfde rechter argument van R. Dat wil zeggen dat voor alle a1, a2 <math>\in</math> A en b <math>\in</math> B geldt: als a1 R b en a2 R b dan a1 = a2.
- R is rechts-definiet of functioneel desda geen enkel linker argument van R in relatie staat tot twee verschillende rechter argumenten van R. Dat wil zeggen dat voor alle a <math>\in</math> A en b1, b2 <math>\in</math> B geldt: als a R b1 en a R b2 dan b1 = b2.
- R is bijectief desda R links-volledig, rechts-volledig, links-definiet en rechts-definiet is.
Een functionele tweeplaatsige relatie wordt een afbeelding genoemd. Een afbeelding waarvan het het codomein een lichaam (ook wel veld) is, is een functie.[3]
Een tweeplaatsige relatie die links- en rechts-volledig is wordt een correspondentierelatie genoemd. De combinatie van functionaliteit en injectiviteit wordt één-éénduidigheid genoemd. Een één-éénduidige relatie heet ook wel een één-op-één-relatie. Een bijectieve tweeplaatsige relatie wordt een één-op-één-correspondentie genoemd. Soms wordt "correspondentierelatie" echter als synoniem voor "(tweeplaatsige) relatie" gebruikt en het onderscheid tussen één-op-één-relatie en één-op-één-correspondentie wordt ook niet altijd gemaakt. Wanneer dit laatste niet het geval is dan moet uit de context blijken of met beide begrippen een bijectieve tweeplaatsige relatie bedoeld wordt, of een functionele en injectieve tweeplaatsige relatie.
Operaties op tweeplaatsige relaties
Doorsnede en vereniging
Zie ook: Zie Doorsnede en Vereniging voor de doorsnede en de vereniging van verzamelingen in plaats van relaties.
Zij R en S tweeplaatsige relaties over A en B. De doorsnede van R en S, genoteerd als R ∩ S, is de tweeplaatsige relatie over A en B waarvoor geldt dat
- voor alle a <math>\in</math> A en b <math>\in</math> B geldt: a (R ∩ S) b desda a R b en a S b.
De vereniging van R en S, genoteerd als R ∪ S, is de tweeplaatsige relatie over A en B waarvoor geldt dat
- voor alle a <math>\in</math> A en b <math>\in</math> B geldt: a (R ∪ S) b desda a R b of a S b (of beide).
Wanneer de definitie van tweeplaatsige relatie gebruikt wordt waarbij de relatie een verzameling geordende paren is, overeenkomstig met de grafiek van dezelfde relatie onder de andere genoemde definitie, dan zijn de doorsnede en vereniging van tweeplaatsige relaties simpelweg de doorsnede en de vereniging zoals gedefinieerd op verzamelingen in het algemeen.
Complement
Zie ook: Zie Complement voor het complement van verzamelingen in plaats van relaties.
Zij R een tweeplaatsige relatie over A en B. Het complement van R, genoteerd als R C of als R, is de tweeplaatsige relatie over A en B waarvoor geldt dat
- voor alle a <math>\in</math> A en b <math>\in</math> B geldt: a R C b desda niet a R b.
Merk op dat voor alle tweeplaatsige relaties R geldt dat
- (R C) C = R.
Compositie of samenstelling
Zie ook: Zie ook: Samengestelde relatie
Zij R een tweeplaatsige relatie over A en B, en S een tweeplaatsige relatie over B en C. De compositie of samenstelling van R en S, genoteerd als R <math>\circ</math> S, is de tweeplaatsige relatie over A en C waarvoor geldt dat
- voor alle a <math>\in</math> A en c <math>\in</math> C geldt: a (R <math>\circ</math> S) c desda er een b <math>\in</math> B is zodanig dat a R b en b S c.
Voor alle tweeplaatsige relaties R over A en B, S over B en C, en T over C en D geldt dat
- (associativiteit) (R <math>\circ</math> S) <math>\circ</math> T = R <math>\circ</math> (S <math>\circ</math> T).
Daarom wordt meestal simpelweg R <math>\circ</math> S <math>\circ</math> T geschreven in plaats van (R <math>\circ</math> S) <math>\circ</math> T of R <math>\circ</math> (S <math>\circ</math> T).
Vaak wordt de compositie van R en S genoteerd als S <math>\circ</math> R in plaats van R <math>\circ</math> S, zodat de notatie in overeenstemming is met de notatie voor functie-compositie. Deze keuze doet recht aan het inzicht dat compositie van tweeplaatsige relaties en compositie van functies hetzelfde inhouden, omdat functies bijzondere gevallen van tweeplaatsige relaties zijn.
Inverse of converse
Zie ook: Zie ook: Inverse
Zij R een tweeplaatsige relatie over A en B. De inverse of converse van R, genoteerd als R −1, is de tweeplaatsige relatie over B en A waarvoor geldt dat
- voor alle a <math>\in</math> A en b <math>\in</math> B geldt: b R −1 a desda a R b.
Merk op dat voor alle tweeplaatsige relaties R het volgende geldt:
- (R −1) −1 = R.
- Als R links-volledig is, dan is R −1 rechts-volledig.
- Als R rechts-volledig is, dan is R −1 links-volledig.
- Als R links-definiet is, dan is R −1 rechts-definiet.
- Als R rechts-definiet is, dan is R −1 links-definiet.
- Als R bijectief is, dan is R −1 ook bijectief.
Eigenschappen van deze operaties
Zij R een tweeplaatsige relatie over A en B.
- De inverse van het complement van R is hetzelfde als het complement van de inverse van R, oftewel: (R C) −1 = (R −1) C.
- De doorsnede van R en het complement van R is de lege relatie over A en B.
- De vereniging van R en het complement van R is de universele relatie over A en B.
Eén-op-één-correspondenties
Een één-op-één-correspondentie of bijectie is een bijectieve tweeplaatsige relatie. De één-op-één-correspondentie is een veelgebruikte soort tweeplaatsige relatie. In de algebra is het isomorfisme bijvoorbeeld (een specifiek geval van) een één-op-één-correspondentie en in de topologie is het homeomorfisme (een specifiek geval van) een één-op-één-correspondentie.
In wiskundige bewijzen worden één-op-één-correspondenties geconstrueerd om uiteenlopende feiten aan te tonen. Een voorbeeld hiervan is het aantonen van de gelijkmachtigheid van twee verzamelingen. Twee verzamelingen zijn namelijk gelijkmachtig desda er een één-op-één-correspondentie tussen deze verzamelingen bestaat.
Homogene tweeplaatsige relaties
In het algemeen is een homogene relatie of endorelatie een relatie waarvan alle domeinen door één en dezelfde verzameling uitgemaakt worden. Een homegene tweeplaatsige relatie of tweeplaatsige endorelatie is dan ook een tweeplaatsige relatie waarvan het domein en het codomein dezelfde verzameling zijn. Als R een homogene tweeplaatsige relatie over X is, dan wordt R soms gedefinieerd als het het tupel (G, X) in plaats van het 3-tupel (G, X, X). Deze wijze van definiëren is bijvoorbeeld gebruikelijk in de grafentheorie.
Eigenschappen van homogene tweeplaatsige relaties
Zij R een homogene tweeplaatsige relatie op X.
- R is voortzettend desda voor alle x <math>\in</math> X er een y <math>\in</math> X is zodanig dat x R y.
- R is reflexief desda voor alle x <math>\in</math> X geldt dat x R x.
- R is irreflexief desda er geen x <math>\in</math> X is zodanig dat x R x.
- R is symmetrisch desda voor alle x, y <math>\in</math> X geldt: als x R y dan y R x.
- R is asymmetrisch desda er geen x, y <math>\in</math> X zijn zodanig dat x R y en y R x.
- R is antisymmetrisch desda voor alle x, y <math>\in</math> X geldt: als x R y en y R x, dan x = y.
- R is transitief desda voor alle x, y, z <math>\in</math> X geldt: als x R y en y R z, dan x R z.
- R is intransitief desda er geen x, y, z <math>\in</math> X zijn zodanig dat x R y, y R z en x R z.
- R is dicht desda voor alle x, y <math>\in</math> X geldt: als x R y dan is er een z <math>\in</math> X zodanig dat x R z en z R y.
- R is Euclidisch desda voor alle x, y, z <math>\in</math> X geldt: als x R y en x R z, dan y R z.
- R is samenhangend desda voor alle x, y, z <math>\in</math> X geldt: als x R y en x R z, dan y R z of z R y.
- R is connex of totaal desda voor alle x, y <math>\in</math> X geldt dat x R y of y R x (of beide).
- R is trichotoom desda voor alle x, y <math>\in</math> X precies één van de volgende uitspraken waar is: x R y, y R x of x = y.
- R is deterministisch desda voor alle x, y, z <math>\in</math> X geldt: als x R y en x R z, dan y = z. (Vgl. rechts-definitiet of functioneel.)
- R is convergent desda voor alle x, y, z <math>\in</math> X geldt: als x R y en x R z, dan is er een u <math>\in</math> X zodanig dat y R u en z R u.
- R is divergent desda voor alle x, y, z <math>\in</math> X geldt: als x R y, x R z en y ≠ z dan is er geen u <math>\in</math> X zodanig dat y R u en z R u.
Operaties op homogene tweeplaatsige relaties
Restrictie en extensie
Zie ook: Zie Restrictie voor de restrictie van functies in plaats van relaties.
Zij R een homogene tweeplaatsige relatie op X. Als Y <math>\subseteq</math> X dan is de restrictie van R tot Y de homogene tweeplaatsige relatie S op Y waarvoor geldt dat
- voor alle x, y <math>\in</math> Y geldt: x S y desda x R y.
Informeel gesproken is een restrictie van een homogene tweeplaatsige relatie het resultaat van het inperken van zijn domein.
Als R één of meer van de eigenschappen reflexief, irreflexief, symmetrisch, asymmetrisch, antisymmetrisch, transitief, intransitief, Euclidisch, totaal, trichotoom, deterministisch of divergent heeft, dan heeft iedere restrictie van R dezelfde eigenschappen ook. Als gevolg is iedere restrictie van een equivalentierelatie ook een equivalentierelatie, iedere restrictie van een partiële orde ook een partiële orde, enz.
Als S een restrictie van R is, dan is R een extensie van S.
Afsluiting en reductie
Zie ook: Zie ook: Afsluiting
Zij R een homogene tweeplaatsige relatie op X.
- R = is de reflexieve afsluiting van R, waarbij voor alle x, y <math>\in</math> X geldt dat x R = y desda x R y of x = y.
- R ≠ is de reflexieve reductie van R, waarbij voor alle x, y <math>\in</math> X geldt dat x R ≠ y desda x R y en x ≠ y.
- R + is de transitieve afsluiting van R, gedefinieerd als de kleinste transitieve tweeplaatsige relatie over X is zodanig dat voor alle x, y <math>\in</math> X geldt: als x R y dan x R + y.
- R − is de transitieve reductie van R, gedefinieerd als de kleinste tweeplaatsige relatie over X is met dezelfde transitieve afsluiting als R.
- R * is de reflexief-transitieve afsluiting van R, waarbij R * = (R +) = = (R =) +.
- (R −) ≠ wordt de transitief-reflexieve reductie van R genoemd. Merk op dat (R −) ≠ = (R ≠) −.
Equivalentierelaties
Zie ook: Zie ook: Equivalentierelatie
Een homogene tweeplaatsige relatie ~ op X is een equivalentierelatie desda ~ reflexief, symmetrisch en transitief is.
Gegeven een equivalentierelatie ~ op X, kan voor iedere x <math>\in</math> X de verzameling van alle elementen waarmee x in ~-relatie staat gedefinieerd worden:
- [x] = { y <math>\in</math> X | x ~ y }.
Deze verzameling wordt de equivalentieklasse van x genoemd, of een equivalentieklasse van X.
Equivalentieklassen hebben de volgende eigenschappen:[4]
- Voor alle x <math>\in</math> X geldt dat x <math>\in</math> [x].
- Iedere x <math>\in</math> X zit in precies één equivalentieklasse van X.
- Voor alle x, y <math>\in</math> X geldt: x ~ y desda x en y in dezelfde equivalentieklasse van X zitten.
De verzameling
- X/~ = { [x] | x <math>\in</math> X }
van alle equivalentieklassen van X wordt de quotiëntverzameling van X onder ~ genoemd.
Quotiëntverzamelingen hebben de volgende eigenschappen:[4]
- Iedere equivalentierelatie op X levert een unieke quotiëntverzameling op. Er zijn, met andere woorden, geen twee verschillende equivalentierelaties op X die dezelfde quotiëntverzameling van X opleveren.
- X/~ is een partitie van X. Dat wil zeggen dat ieder element van X in precies één van de equivalentieklassen [x] <math>\in</math> X/~ zit, de vereniging van alle equivalentieklassen [x] <math>\in</math> X/~ gelijk is aan X en dat de lege verzameling geen element van X/~ is.
Het blijkt bovendien dat iedere partitie van X ook een quotiëntverzameling van X is onder een zekere equivalentierelatie op X. Hieruit volgt, samen met de bovenstaande eigenschappen, dat er een één-op-één-correspondentie is tussen alle mogelijke partities van X en alle mogelijke equivalentierelaties op X.
Orderelaties
Zie ook: Zie ook: Ordetheorie
Een belangrijke toepassing van (homogene) tweeplaatsige relaties is het beschrijven van orde door middel van orderelaties. Vier basale soorten orderelaties zijn partiële ordes, totale ordes, preordes en strikte zwakke ordes, maar er zijn ook andere soorten orderelaties.
Partiële orde
Een homogene tweeplaatsige relatie ≤ op X is een partiële orde desda ≤ reflexief, antisymmetrisch en transitief is.
Een homogene tweeplaatsige relatie < op X is een strikte partiële orde desda < asymmetrisch en transitief is. Asymmetrie impliceert bovendien irreflexiviteit. Een strikte partiële orde kan ook gedefinieerd worden als een irreflexieve, transitieve, homogene tweeplaatsige relatie, want irreflexiviteit en transitiviteit impliceren samen asymmetrie.
Er is een één-op-één-correspondentie tussen alle partiële ordes op een verzameling X en alle strikte partiële ordes op dezelfde verzameling X, die verkregen wordt door iedere partiële orde af te beelden op zijn reflexieve reductie. Van iedere partiële orde op X is zijn reflexieve reductie namelijk een strikte partiële orde op X. Verder is het zo dat de inverse van deze één-op-één-correspondentie iedere strikte partiële orde afbeeldt op zijn reflexieve afsluiting.[5] De reflexieve afsluiting van een strikte partiële orde op X is een partiële orde op X. Merk op dat de inverse van het complement van een partiële orde ≤ de reflexieve reductie van ≤ is en dat de inverse van het complement van een strikte partiële orde < de reflexieve afsluiting van < is.
De inverse van een partiële orde ≤ wordt vaak genoteerd als ≥ en is zelf ook een partiële orde. De inverse van een strikte partiële orde < wordt vaak genoteerd als > en is zelf ook een strikte partiële orde. Het complement van een partiële orde is een strikte partiële orde en vice versa.
Een partiële orde waarbij ieder paar argumenten een uniek infimum en een uniek supremum heeft, heet een tralie.
Totale orde
Een homogene tweeplaatsige relatie ≤ op X is een totale orde of lineaire orde desda ≤ antisymmetrisch, transitief en totaal is. Totaliteit impliceert reflexiviteit, dus is de totale orde een specifiek geval van de partiële orde.
Een homogene tweeplaatsige relatie < op X is een strikte totale orde of strikte lineaire orde desda < transitief en trichotoom is. Trichotomie impliceert asymmetrie, dus is de strikte totale orde een specifiek geval van de strikte partiële orde.
Op dezelfde wijze als bij partiële ordes kan er een één-op-één-correspondentie geconstrueerd worden tussen alle totale ordes op een verzameling X en alle strikte totale ordes op dezelfde verzameling X. Ook hierbij geldt dat de inverse van het complement van een totale orde ≤ de reflexieve reductie van ≤ is en dat de inverse van het complement van een strikte totale orde < de reflexieve afsluiting van < is.
De inverse van een totale orde ≤ wordt vaak genoteerd als ≥ en is zelf ook een totale orde. De inverse van een strikte totale orde < wordt vaak genoteerd als > en is zelf ook een strikte totale orde. Het complement van een totale orde is een strikte totale orde en vice versa.
Preorde
Een homogene tweeplaatsige relatie <math>\lesssim</math> op X is een preorde desda <math>\lesssim</math> reflexief en transitief is. Van iedere homogene tweeplaatsige relatie R is de reflexief-transitieve afsluiting R * een preorde.
Een homogene tweeplaatsige relatie <math>\lesssim</math> op X is een totale preorde desda <math>\lesssim</math> transitief en totaal is. Merk op dat totaliteit reflexiviteit impliceert en iedere totale preorde dus een specifiek geval van een preorde is.
Een partiële orde is een antisymmetrische preorde en een equivalentierelatie is een symmetrische preorde. Een totale orde is een antisymmetrische totale preorde.
Voor iedere preorde <math>\lesssim</math> op X kan de equivalentierelatie ~ op X gedefinieerd worden waarvoor geldt dat voor alle x, y <math>\in</math> X:
- x ~ y desda x <math>\lesssim</math> y en y <math>\lesssim</math> x.
Als vervolgens een relatie ≤ op X/~ afgeleid wordt door te stellen dat voor alle x, y <math>\in</math> X geldt dat
- [x] ≤ [y] desda x <math>\lesssim</math> y,
dan is ≤ een partiële orde op X/~. Hieruit kan vervolgens een strikte partiële orde < op X afgeleid worden, zodanig dat voor alle x, y <math>\in</math> X geldt dat
- x < y desda [x] ≤ [y] en [x] ≠ [y],
ofwel (de equivalente uitspraak) dat
- x < y desda x <math>\lesssim</math> y en niet x ~ y.
Onder deze constructies geldt voor alle x, y <math>\in</math> X dat
- x <math>\lesssim</math> y desda x < y of x ~ y.
Dit verklaart de notatie <math>\lesssim</math> en geeft inzicht in de wijze waarop preordes zich verhouden tot (strikte) partiële ordes. Totale preordes verhouden zich tot (strikte) totale ordes zoals preordes zich tot (strikte) partiële ordes verhouden.
De term "strikte preorde" is niet gedefinieerd. Dit zou immers zoiets als een irreflexieve en transitieve homogene tweeplaatsige relatie moeten zijn, maar irreflexiviteit en transitiviteit impliceren samen asymmetrie, wat een strikte partiële orde op zou leveren. Hetzelfde geldt voor de term "strikte totale preorde". Irreflexiviteit en transitiviteit impliceren samen met de voorwaarde
- voor alle x, y <math>\in</math> X geldt: als x ≠ y dan x R y of y R x (vgl. totaliteit)
namelijk trichotomie, wat een strikte totale orde op zou leveren.
Het is uiteraard wel mogelijk om (de inverse van) het complement van een preorde te nemen. Bij een totale preorde levert dit een strikte zwakke orde op.
Strikte zwakke orde
Een strikte partiële orde < op X is een strikte zwakke orde desda de relatie "noch x < y, noch y < x" transitief is. Deze voorwaarde wordt ook wel transitiviteit van onvergelijkbaarheid genoemd. Een alternatieve, equivalente, manier om deze voorwaarde te formuleren is:
- Voor alle x, y <math>\in</math> X geldt: als x < y dan geldt voor alle z <math>\in</math> X dat x < z of z < y (of beide).
Het complement van een strikte zwakke orde is een totale preorde en vice versa.
Grafen
Zie ook: Zie ook: Grafentheorie
Een homogene tweeplaatsige relatie kan ook geïnterpreteerd worden als een graaf. De elementen uit het domein komen dan overeen met de knopen van de graaf en de elementen uit de grafiek met de zijden van de graaf.
Voorbeelden van homogene tweeplaatsige relaties
De al eerder genoemde relatie houden van is een voorbeeld van een homogene tweeplaatsige relatie op de verzameling van alle mensen.[6] Voorbeelden uit de wiskunde zijn legio. Hier volgen er enkele.
- Is-groter-dan is een overbekend voorbeeld van een homogene tweeplaatsige relatie op getallen of, meer in het algemeen, op numerieke expressies. Merk op dat is-groter-dan een strikte totale orde is.
- Is-gelijk-aan is zonder twijfel het meest voorkomende voorbeeld van een homogene tweeplaatsige relatie. De relatie is-gelijk-aan is bovendien het meest voor de hand liggende voorbeeld van een equivalentierelatie. Naïef bezien zou het domein van deze relatie de verzameling van alle objecten moeten zijn, of ten minste de verzameling van alle wiskundige objecten. Dit leidt echter tot de Russell-paradox. Om dit te omzeilen zouden er verschillende is-gelijk-aan-relaties gedefinieerd kunnen worden voor verschillende domeinen: een is-gelijk-aan voor getallen, een is-gelijk-aan voor geometrische figuren, etc. Een andere oplossing is de (tweeplaatsige) relatie te herdefiniëren in termen van klassen in plaats van verzamelingen.
- Omdat afbeeldingen ook tweeplaatsige relaties zijn, is iedere identiteitsafbeelding idX een homogene tweeplaatsige relatie op X. Iedere identiteitsafbeelding idX is zowel een één-op-één-correspondentie als een equivalentierelatie. Bovendien is de identiteitsafbeelding van X de enige relatie op X die zowel een één-op-één-correspondentie als een equivalentierelatie is. Overigens is de identiteitsafbeelding van X de kleinst mogelijke equivalentierelatie op X. De grootst mogelijke equivalentierelatie op X is de universele tweeplaatsige endorelatie op X.
Het aantal mogelijke homogene tweeplaatsige relaties
| Aantal mogelijke tweeplaatsige relaties op een verzameling met n elementen | ||||||||
|---|---|---|---|---|---|---|---|---|
| n | Alle relaties | Reflexieve relaties | Transitieve relaties | Preordes | Partiële ordes | Totale preordes | Totale ordes | Equivalentierelaties |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
| 2 | 16 | 4 | 13 | 4 | 3 | 3 | 2 | 2 |
| 3 | 512 | 64 | 171 | 29 | 19 | 13 | 6 | 5 |
| 4 | 65536 | 4096 | 3994 | 355 | 219 | 75 | 24 | 15 |
| OEIS | A002416 | A053763 | A006905 | A000798 | A001035 | A000670 | A000142 | A000110 |
- Het aantal irreflexieve relaties is gelijk aan het aantal reflexieve relaties.
- Het aantal intransitieve relaties is gelijk aan het aantal transitieve relaties.
- Het aantal strikte partiële ordes is gelijk aan het aantal partiële ordes.
- Het aantal strikte totale ordes is gelijk aan het aantal totale ordes.
- Het aantal strikte zwakke ordes is gelijk aan het aantal totale preordes.
- Het aantal equivalentierelaties is gelijk aan het aantal partities van dezelfde verzameling.
Toepassingen buiten de wiskunde
In de economische wetenschap wordt het begrip voorkeur vaak gemodelleerd met tweeplaatsige relaties, namelijk met strikte zwakke ordes.
Zie ook
- º Ook eigenschappen als links- en rechts-volledigheid (zie Eigenschappen van tweeplaatsige relaties) zijn enkel te definiëren in deze context.
- º Merk op dat houden van strikt genomen geen tweeplaatsige relatie is (in de wiskundige zin van het woord), maar een niet-wiskundig begrip dat met een tweeplaatsige relatie beschreven kan worden. De genoemde wiskundige relatie L is bedoeld een beschrijving te zijn van het alledaagse begrip houden van.
- º Soms worden de termen "functie" en "afbeelding" ook op andere wijzen gebruikt. Zie de betreffende artikelen voor een uitgebreidere beschrijving van de verschillende manieren waarop deze begrippen gebruikt worden.
- ↑ 4,0 4,1 Zie voor de bewijzen het hoofdartikel over dit onderwerp: Equivalentierelatie.
- º Voor partiële ordes ≤ geldt (≤ ≠) = = ≤. In het algemeen is het echter niet zo dat voor een willekeurige homogene tweeplaatsige relatie R geldt dat (R ≠) = = R. Om precies te zijn geldt (R ≠) = = R desda R reflexief is.
- º Merk wederom op dat houden van eigenlijk geen tweeplaatsige relatie is (in de wiskundige zin van het woord), maar een niet-wiskundig begrip dat met een tweeplaatsige relatie beschreven kan worden.