Verzamelingen/Relaties

Na het bestuderen van dit hoofdstuk:

Weet je wat een afbeelding is

Weet je wat een operator is

Weet je wat een relatie is

weet je wat een equivalentieklasse is

weet je wat een partiele ordening is

Relaties

Met een relatie bedoelen we een verband (de relatie) tussen 2 verzamelingen. Voorbeeld:

Afb. 5.1

Vaak worden relaties gedefinieerd op basis van gemeenschappelijke eigenschappen of kenmerken. De wiskundige en logicus De Morgan, die we in het vorige hoofdstuk tegen kwamen, definieerde relaties als:

"When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation."

of in het Nederlands:

Wanneer twee objecten, kenmerken, attributen, of klassen samen beschouwd worden, en hier een verband gezien wordt, dan wordt dat verband een relatie genoemd.

Merk op dat hier strikt genomen enkel op tweeplaatsige relaties gedoeld wordt.

Tegenwoordig gebruiken we een exactere definitie: Een relatie R tussen een aantal verzamelingen A₁, A₂ ... A_n definiëren we als een aantal n-tupels (rijen) (a₁, a₂, ... a_n) waarin a₁ $\in$A₁ etc. Zo'n rij is een element van van het cartesisch product A_1> X A₂ X ... X A_n is dan een element van de verzameling R.

Illustratie:

We kunnen tussen deze twee verzamelingen 3 voor de hand liggende relaties definiëren. We illustreren twee hiervan:

De linker relatie is gelegd op grond van de vorm (driehoek met driehoek, etc), de rechter is gelegd op grond van de vulling van het vlak.
Afb. 5.2

Opgave Kun je zelf de 3e relatie schetsen?

Het aantal verzamelingen noemen we de plaatsigheid van een relatie.

Sommige wiskundigen gaan nog een stap verder in het formaliseren. We schreven hierboven dat een relatie bestaat uit een aantal n-tuples op het cartesisch product van n- verzamelingen. Sommigen noemen deze verzameling n-tuples G en definiëren een relatie R als bestaande uit G en het cartesisch product, dus R={G, A₁, A₂ ... A_n}. Het verschil is wat theoretisch semantisch, maar met beiden wordt hetzelfde bedoeld. Zo volgt de Engelstalige wikipedia in haar artikel de definitie wara we mee begonnen, terwijl de Nederlandstalige wikipedia in het artikel over relaties de laatste vorm kiest.

Er zijn 3 soorten relaties die we bijzonder aandacht geven:

• Afbeeldingen:
• (Partiele) ordeningen
• Equivalentie relaties

Deze 3 soorten relaties worden in dit hoofdstuk hierna verder uitgewerkt.

Afbeeldingen

Een afbeelding is een vorm van een relatie, zoals hierboven beschreven. Het verschil is dat een afbeelding een richting heeft. Wanneer we met getallen werken, gebruiken we het woord functie.

Grafische illustratie van een afbeelding:

Afb. 5.3

De linker verzameling heeft 3 elementen, de letters a, b en c, de rechter 2, namelijk de cijfers 1 en 2. De afbeelding beeldt a en b op 2 af, en de letter c op 1.

De 'van' verzameling A wordt het domein genoemd, de 'naar' verzameling B wordt het codomeinof Bereik genoemd. We spreken van een afbeelding in als er elementen in B zijn waarop geen enkel element van A wordt afgebeeld, en van afbeelding op als er voor alle elementen in B een element van A bestaat dat hierop wordt afgebeeld. In dit geval wordt met het bereik de verzameling waarden van f(x) bedoeld, dus het bereik=:F(x)|x$\in$A}.

Definitie:
Een afbeelding F van verzameling A naar verzameling B is een deelverzameling van het Cartesisch product A X B. De paren zijn geordend. Hierbij geldt

(a) Een afbeelding gaat altijd naar 1 element van het bereik.

(b) meerdere elementen uit het domein mogen worden afgebeeld op 1 element van het bereik.

Notatie: Een afbeelding F van A naar B wordt genoteerd als:

$f\colon A\to B$

of ook als

$A\ {\stackrel {f}{\longrightarrow }}\ B$

of als

f=(G, A, B) waarbij G de verzameling geordende paren is.

Wanneer we het over afbeeldingen met getallen hebben, spreken we meestal over functies.

meerplaatsige afbeeldingen
Bovenstaande definitie gaat uit van een tweeplaatsige afbeelding. We kunnen meerplaatsige functies definiëren, bijvoorbeeld een functie $f\colon AXB\to C$

Voorbeelden van afbeeldingen:

• Laat A = B =$\mathbb {N}$. Definieer f(x)=2x+3.
• Laat A={Verzameling geometrisch figuren}, en B=$\mathbb {N}$. Definieer f(x) als {f(x):aantal rechte lijnstukken van x waarbij x$\in$A}
• Laat A={Verzameling driehoeken}, en B=$\mathbb {N}$. Definieer f(x) als f(x)=de oppervlakte van driehoek x.
• f(x)=3^x
• f(x)=sin(x)/x

Operatoren

Bij het gewone rekenen kennen we operaties als optellen, aftrekken, vermenigvuldigen, delen, machtsverheffen en worteltrekken. We noemen de "+", "-", "x" en "/" operatoren. Met bovenstaande kennis kunnen we nu zien dat de optelling "+" een afbeelding is van $\mathbb {N}$ X $\mathbb {N}$ op $\mathbb {N}$. Hetzelfde geldt voor de operatoren "-", "x" en "/" en machtsverheffen en worteltrekken.

En we hebben inmiddels meer operatoren voorbij zien komen, zoals $\land$ en $\lor$ in de propositielogica. Een ander voorbeeld is de doorsnede ∩ tussen twee verzamelingen .

De operatoren "+", "-", "x" en "/" zijn net als ∩ en $\mathbb {N}$ X $\mathbb {N}$ tweeplaatsige operatoren. Het complement A^c en de ontkenning $\neg A$ zijn eenplaatsige operatoren.

Definitie:
Een operatie R is een afbeelding van A X B in C en we noteren deze als aRb waarbij a en b elementen van A respectievelijk B zijn. Vaak zullen A en B identieke verzamelingen zijn, zoals in bovenstaande voorbeelden, maar dit is niet noodzakelijk.

Generalisatie
We kunnen een operator definiëren van A₁ X ... X A_n naar B. We spreken dan van een n-plaatsige operator.

Equivalentie relaties

Een equivalentierelatie is een relatie die elementen met een gemeenschappelijk kenmerk aan elkaar koppelt.

Voorbeeld: bij de meetkundige figuren kunnen we een equivalentierelatie definieren "heeft n hoeken". Dan zijn de volgende figuren equivalent:

Afb. 5.4

Definitie
Een equivalentierelatie R op een verzameling X is een tweeplaatsige relatie a$\sim _{R}$b op X met de eigenschappen:

• reflexiviteit: voor alle x$\in$ X geldt: x$\sim$x (elke x is equivalent met zichzelf)
• symmetrie: voor alle x,y$\in$X geldt: als x$\sim$y, dan y$\sim$x (als x equivalent is met y, dan is y dit ook met x)
• transitiviteit: voor alle x,y,z$\in$X geldt: als x$\sim$y en y$\sim$z, dan x$\sim$z

Een equivalentie relatie R op een verzameling V is dus een deelverzameling van V X V.

Notatie:
Er zijn verschillende notaties in gebruik. Zowel de hierboven genoemde a$\sim _{R}$b als a$\sim$b en a$\equiv$b worden gebruikt. Om de relatie R expliciet aan te geven, kunnen we aRb gebruiken. Het niet equivalent zijn van a en b kunnen we aangeven met a≁b of a$\not \equiv$b.

Voorbeelden van equivalentie relaties:

• De kleur van de schoenen van leerlingen op een school
• Musici die op dezelfde datum geboren zijn
• De restwaarde van natuurlijke getallen bij delen door n.
• Functies f(x)=ax+b met f(2)=3
• De waarden x die dezelfde waarde f(x)=sin(x) hebben
• Congruente driehoeken
• Gelijkvormige driehoeken

De waarden van een equivalentie relaties groeperen de elementen van een verzameling in een aantal equivalentierelaties. Dus als x$\sim$y, dan zitten x en y in dezelfde equivalentieklasse. We noteren de quivalentieklasse van x met $[x],$.

Omdat een equivalentierelatie reflexief is, zit elk element van een verzameling in een van de equivalentieklassen. Equivalentieklassen zijn onderling disjunct (niet overlappend), want als y in twee equivalentieklassen $[x]$ en $[z]$ zou zitten, zou x$\sim$y en y$\sim$z, wat volgens de transitiviteit betekent x$\sim$z, dus $[x]$ = $[z]$. De equivalentieklassen vormen samen dus een partitie (zie hoofdstuk 2) van de verzameling waarop de equivalentierelatie gedefinieerd is.

(Partiele) ordening

Ordenen is een heel elementaire activiteit van het menselijk brein. De eerste ordening die we als kind leren is vaak van klein naar groot, bijvoorbeeld houten blokjes van klein naar groot leggen. Of dominostenen van 0 naar 6 leggen. We leren dat 2 minder is dan 3, en iemand die 2 koekjes heeft, heeft er minder dan iemand die 5 koekjes heeft. OOk in de wiskunde komen we verschillende ordeningen tegen.

In het eerste hoofdstuk benadrukten we dat een verzameling geen ordening bezat. Dus de verzameling {1,2} is hetzelfde als de verzameling {2,1}. Daarmee bedoelden we dat een verzameling geen ordening in zichzelf bezit. We kunnen wel een ordening op een verzameling definiëren. Die is dan geen deel van de verzameling, maar daar bovenop gedefinieerd. Is dat nuttig? Ja, want soms zijn er verschillende ordeningen mogelijk op 1 zelfde verzameling.

Voorbeelden van ordeningen:

• Een verzameling letters of woorden kunnen we alfabetisch ordenen.
• Een verzameling meetkundige figuren kan geordend worden door naar de oppervlakte te kijken, of naar het aantal hoeken.
• Laat A={0, 1, 2, 3}. Hierop definiëren we de standaard ordening van de natuurlijke getallen, 0<1<2,3.
  Een tweede ordening die we hierop kunnen definiëren is 0<1, 0<2, 1<3, 2<3.
  

Schematisch:

Afb. 5.5

• Neem de natuurlijke getallen. Hierop kunnen we de standaard ordening 0<1<2,3<4 etc definieren, maar we zouden die ook kunnen ordenen door eerste de oneven getallen en dan de even getallen te nemen, als volgt:{1 < 3 < 5 < 5 < 7 < ..., 0 < 2 < 4 < 6 ... te ordenen.

Definitie
Ordeningen zijn een vorm van binaire relaties. Laat V een verzameling zijn en R een relatie op V, d.w.z. een relatie op de elementen van V X V. We noemen R een ordening als de relatie reflectief, antisymmetrisch en transitief is.

Voor alle a$\in$ V geldt aRa (reflectief).

als aRb en bRa dan a = b (antisymmetrisch of asymmetrisch)

als aRb en bRc dan aRc (transitief).

Deze definitie lijkt dus sterk op die van equivalentieklasse, en het verschil is dat deze relatie a-symmetrisch in plaats van symmetrisch is.

Definitie
We noemen een ordening een partiele ordening als niet tussen alle elementen een < of ≤ bestaat. Met andere woorden: niet alle elementen zijn vergelijkbaar. Een ordening waarbij wel alle elementen van een verzameling vergelijkbaar zijn, noemen we een totale orde.

Binnen de partiele ordeningen worden nog 2 vormen onderscheiden: strikt en niet strikt.
Definitie
Een ordening P=(V,<) noemen we een strikte partiele ordening wanneer voor alle vergelijkbare paren (a,b) van V X V geldt:

a < b of b < a (antisymmetrisch of asymmetrisch)

als a < b en b < c dan a < c (transitief).

Kortom, de reflectiviteit geldt dan niet. Een strikte ordening wordt ook wel een sterke of niet-reflexieve ordening genoemd, een niet strikte ordening wordt ook wel zwak of reflexief genoemd.

Als voor elk tweetal elementen a en b van V geldt dat ze vergelijkbaar zijn, dus a ≤ b of b ≤ a, dan noemen we de ordening totaal. Deze worden ook lineaire ordeningen of ketting ordeningen genoemd.

Voorbeelden van partiele ordeningen
Omdat je je misschien in eerste instantie niet zo veel kunt voorstellen bij een partiele ordening, geven we enkele voorbeelden:

1. Blokfluiten zijn een deelverzameling van de verzameling blaasinstrumenten. Dat geldt ook voor trombones. Maar blokfluiten en trombones zijn geen deelverzameling van elkaar en hebben niet direct een onderlinge vergelijking.
2. Neem de verzameling van de natuurlijke getallen $\mathbb {N}$. Orden deze op deelbaarheid. Daarmee bedoelen we 1<2, want 1 deelt 2. 1<3, want 1 deelt 3. 1<4 en 2<4, want zowel 1 als 2 delen 4. Dit is een voorbeeld van een partiele ordening, want bijvoorbeeld 2 en 3 zijn niet vergelijkbaar.
3. Neem een verzameling A, laat P(A) de machtsverzameling van A zijn. Dan kunnen we een ordening op de deelverzamelingen van P(A) definiëren door A₁ ≤ A₂ dan en slechts dan als A₁ ⊆ A₁. We noemen dit een ordening op inclusie. Dit is een partiele ordening, want als we van {1, 2, 3} de deelverzamelingen {1,2} en {1,3} bekijken, zijn deze niet vergelijkbaar.
4. Een ander voorbeeld van een partiele ordening door inclusie is lokatie. Bijvoorbeeld de Kalvermarkt en het Waterlooplein liggen in Amsterdam. Amsterdam ligt in Noord-Holland. Noord-Holland ligt in Nederland. Nederland ligt in Europa. Europa ligt op de Aarde. We noteren Kalvermarkt < Amsterdam, Waterlooplein < Amsterdam, Amsterdam < Noord-Holland, etc. Het Binnenhof ligt in Den Haag. Den Haag ligt in Zuid-Holland. Zuid-Holland ligt in Nederland.
   Amsterdam is in deze ordening niet < of > dan Den Haag, ze zijn in deze ordening niet vergelijkbaar. Amsterdam is wel vergelijkbaar met de Kalvermarkt en met de provincie Noord-Holland. Kalvermarkt en Waterlooplein liggen allebei in Amsterdam, maar zijn onderling niet vergelijkbaar.
5. Kijk naar familierelaties. We kunnen "Is kind van" noteren als "<" .
   

Afb. 5.6

In dit voorbeeld geeft de pijl "<" dan aan, en staat voor "is kind van". De transitiviteit geldt, al moeten we dan lezen "stamt af van". Niemand is kind van zichzelf, dus de ordening is strikt. Het is duidelijk dat er niet-vergelijkbare elementen zijn, zoals Jan en Abdul, en Mike en Achoura.

Extremen

Als er een element m is waarvoor geldt dat m ≤ a voor alle a in de ordening, dan wordt m het kleinste element van de verzameling genoemd.

Als er een element m is waarvoor geldt dat a ≤ m voor alle a in de ordening, dan wordt m het grootste element van de verzameling genoemd.

Merk op dat er voor elke ordening maar 1 grootste en 1 kleinste element in een verzameling kan zijn.
Bewijs: Stel dat er twee grootste elementen, m₁ en m₂ zijn.
Omdat m₁ het grootste element is, is m₂ ≤ m₁.
Omdat m₂ het grootste element is, is m₁ ≤ m₂. Dus m₂ ≤ m₁ en m₁ ≤ m₂. Volgens de 2e eigenschap bij de definitie van een ordening hierboven geldt dus m₁ = m₂.
Merk op dat niet elke verzameling een grootste of kleinste element heeft. Neem bijvoorbeeld A={x$\in \mathbb {Q}$| X.0 en x<1}. Dat is dus de verzameling van alle breuken die > 0 en < 1 zijn. 0 zit daar zelf niet in, en voor elke breuk 1/n kunnen we een element 1/(n+1) bedenken dat nog kleiner is. Op dezelfde manier kunnen we voor elke breuk n/(n+1) een breuk (n+1)/(n+2) bedenken die nog dichter bij 1 ligt.

We noemen een element p van verzameling V maximaal als er geen element a$\in$ bestaat zo dat a >p. Omgekeerd noemen we een element p minimaal als er geen element a bestaat zo dat a>p.

Notatie
Er zijn een aantal manieren gebruikelijk om (eindige) partiele ordeningen aan te geven. De minst overzichtelijke methode is het opsommen van paren zoals aa, ab, ac, ad, bd, etc. Het werkt al een stuk overzichtelijker wanneer we de paren in een matrix weergeven.

Afb. 5.7
Nog iets beter wordt het wanneer we het weergeven als Hasse diagram:

Afb. 5.8
Een laatste mogelijkheid biedt een weergave in de vorm van bolletjes:

Afb. 5.9
Deze vorm wordt ook wel een vergelijkbaarheidsgraaf genoemd.

Een Hassediagram heeft een paar regels:

• de kleine elementen staan onderaan, en dan oplopend naar boven.
• pijlen zijn dus niet nodig.
• er worden alleen relaties aangegeven tussen elementen en de elementen die 1 stap groter zijn. Dus niet met zichzelf, en niet met elementen die weer boven heet eerst grotere element liggen.

In de 2e helft van de 20e eeuw is de theorie over ordeningen dermate gegroeid dat ze een aparte tak van de wiskunde is geworden, de w:Ordetheorie.

Ordeningen spelen een belangrijk rol in de universele algebra, in de topologie en in de categorie theorie.

Engels

• Afbeelding: mapping of gewoon map
• Equivalentierelatie: Equivalence relation
• Operatie: operator, operation
• Ordening: ordering
• Partiele ordening: partial ordening of afgekort poset (partially ordered set).
• Plaatsigheid: ary
• Relatie: relation

Opgaven

Opgaven Relaties

V.1 Zijn de volgende beweringen Waar of niet waar?

V.1.a Een relatie tussen elementen van verzameling V en verzameling W is een deelverzameling van het Cartesisch product V X W

V.1.b Een relatie tussen elementen van een verzameling V raakt altijd alle elementen van die verzameling

V.2: schets een derde relatie tussen A en B in het voorbeeld van relaties (fig 5.2).

Opgaven Afbeeldingen

V.11 Zijn de volgende beweringen Waar of niet waar?

V.11.a elke afbeelding van A in B is een relatie tussen A en B

V.11.b elke relatie tussen 2 verzamelingen A en B is een functie van A naar B.

V.11.c Afbeeldingen kunnen alleen op eindige verzamelingen gedefinieerd worden.

V.11.d Het Domein van een afbeelding is altijd gelijk aan het codomein.

Opgaven Operaties

V.21 Zijn de volgende beweringen Waar of niet waar?

V.21.a Optellen is een operatie op de verzameling Natuurlijke getallen.$\mathbb {N}$

V.21.b Vermenigvuldigen is een operatie op de verzameling Gehele getallen$\mathbb {Z}$

V.21.c Optellen is geen operatie op de verzameling rationele getallen $\mathbb {R}$

V.21.d Een operatie is altijd gedefinieerd voor elk element van zijn domein.

V.22 In de automatiseringen plakken programmeurs vaak teksten achter elkaar met een operatie die ze concatenatie noemen. Twee teksten (in de automatisering meestal "strings" genoemd) worden dan achter elkaar geplaatst. Als operatie symbool wordt meestal "&" gebruikt. "Plein" & " 2" levert dan "Plein 2". Geef aan wat "Abc " & "cbA" oplevert.

V.23 Is deze concatenatie operatie associatief? Is deze operatie commutatief?

Opgaven Equivalentie klassen

V.31 Zijn de volgende beweringen Waar of niet waar?

V.31.a Binnen een equivalentieklasse is elke element equivalent met zichzelf.

V.31.b Congruente driehoeken zijn een voorbeeld van een equivalentieklasse

V.31.c Je kunt rode bloemen als equivalentieklasse definiëren.

V.31.d $\varnothing$ is een element in een equivalentieklasse.

V.32 Geef twee mogelijke equivalentieklasse indelingen van {a, b, c}

V.33 Welke deelverzamelingen zijn mogelijke equivalentieklassen van {a, b}?

V.34 De volgende relatie is gedefinieerd op {a, b, c}: {(a,a), (b,b), (a,c), (c,c)}. Welke equivalentieklassen horen hier bij?

Opgaven Ordeningen

V.41.a Elke partiele ordening is een afbeelding.

V.41.b Elke partiele of volledige ordening op verzameling A is een deelverzameling van A X A.

V.41.c Een partiele ordening kan alleen op eindige verzamelingen worden gedefinieerd

V.41.d Een verzameling met een partiele ordening kan een grootste element hebben, maar hoeft dat niet

V.41.e Een eindige verzameling heeft altijd maar 1 grootste element.

V.42: Laat zien dat voorbeeld 3, de partiele ordening van plaatsen en gebieden, een ordeningsrelatie is.

V.43: Laat zien dat de partiele ordening van P(A) door inclusie een partiele ordening is.

V.44: Teken een Hassediagram van alle elementen waarbij de ordeningsrelatie a|b (a deelt b) is voor de getallen 1 t/m 9.

Samenvatting: In dit hoofdstuk heb je geleerd dat:

Wat een afbeelding is

Wat een equivalentieklasse is

wat een operator is

wat een partiele ordening is

en je hebt gezien hoe functies gebaseerd zijn op de theorie van verzamelingen.