Verzamelingen, relaties & functies: oefenopgaven met stapsgewijze oplossingen

1Verzamelingen en verzamelingsoperaties

Een verzameling is een collectie verschillende elementen: A = {1, 2, 3}. Volgorde en herhaling doen er niet toe. |A| is het aantal elementen, en U is de universele verzameling die alles bevat wat besproken wordt.

• A ∪ B (vereniging): de elementen in A of B of beide.
• A ∩ B (doorsnede): de elementen in beide.
• A − B (verschil): de elementen van A die niet in B zitten.
• A′ (complement): de elementen van U die niet in A zitten.

In een venndiagram verdelen twee cirkels U in vier gebieden: alleen A, beide, alleen B, en geen van beide. Elke verzamelingsuitdrukking is een vereniging van enkele van deze gebieden, dus je kunt altijd gebied voor gebied tellen.

Hier is |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 en |(A ∪ B)′| = 15.

2Tellen met inclusie–exclusie

Als je |A| en |B| optelt, wordt de overlap twee keer geteld, dus trek hem één keer af:

Bij drie verzamelingen worden de paarsgewijze overlappen afgetrokken, maar dan is het midden drie keer verwijderd, dus wordt het weer opgeteld:

Bij tekstopgaven is het meestal veiliger om een venndiagram van binnen naar buiten in te vullen: eerst de elementen in alle drie de verzamelingen, dan elk paar min het midden, dan elke losse verzameling min wat al geplaatst is.

Twee andere tellingen komen vaak voor: een verzameling met n elementen heeft 2ⁿ deelverzamelingen (zijn machtsverzameling 𝒫(A)), en |A × B| = |A|·|B| geordende paren.

3Een uitgewerkt voorbeeld

Volg elke stap. Probeer de volgende stap te voorspellen voordat je hem opent.

4Relaties

Een relatie R op een verzameling X is een verzameling geordende paren (x, y) met x en y in X. Getekend als gerichte graaf is elk paar een pijl en is (x, x) een lus.

• Reflexief: (x, x) ∈ R voor elke x: een lus bij elk hoekpunt.
• Symmetrisch: (x, y) ∈ R hoort altijd bij (y, x) ∈ R.
• Antisymmetrisch: (x, y) en (y, x) zitten alleen in R als x = y.
• Transitief: (x, y) en (y, z) in R dwingen (x, z) ∈ R af.

Een relatie die reflexief, symmetrisch en transitief is, is een equivalentierelatie. Ze verdeelt X in disjuncte klassen, zoals de resten 0, 1 en 2 bij “x ≡ y (mod 3)”. Een klasse met s elementen levert s² geordende paren op.

Om een eigenschap te weerleggen is één tegenvoorbeeld genoeg; om haar te bewijzen controleer je elk paar.

5Functies

Een functie f: A → B geeft elk element van A precies één beeld in B.

• Injectief (één-op-één): verschillende elementen hebben verschillende beelden; geen element van B ontvangt twee pijlen.
• Surjectief (op): elk element van B ontvangt minstens één pijl.
• Bijectief: beide. Alleen dan heeft f een inverse f⁻¹.

De functie in de figuur is injectief maar niet surjectief: d ontvangt geen pijl. Een injectie heeft |A| ≤ |B| nodig en een surjectie |A| ≥ |B|.

Met |A| = m en |B| = n zijn er nᵐ functies en n!/(n − m)! injectieve. De samenstelling (g ∘ f)(x) = g(f(x)) past eerst f toe.

6Veelgemaakte fouten

• |A| + |B| optellen zonder de overlap af te trekken.
• Vergeten het midden weer op te tellen bij inclusie–exclusie met drie verzamelingen.
• mⁿ schrijven in plaats van nᵐ voor het aantal functies van m elementen naar n elementen.
• Denken dat een relatie niet tegelijk symmetrisch en antisymmetrisch kan zijn: de relatie {(1, 1)} is beide.
• g ∘ f in de verkeerde volgorde toepassen: f werkt eerst.

7Hoe tentamenvragen eruitzien

• Makkelijk: venndiagrammen en deelverzamelingen. Je telt een verzamelingsuitdrukking uit een venndiagram, klikt het gebied van een uitdrukking aan, of vindt de grootte van een machtsverzameling, een cartesisch product of een familie van deelverzamelingen.
• Gemiddeld: inclusie–exclusie en relaties. Je lost telproblemen met twee en drie verzamelingen op, telt uitdrukkingen uit gebiedstotalen, beslist welke eigenschap een relatie heeft, of telt de paren die nodig zijn voor een afsluiting.
• Moeilijk: functies en tellen. Je classificeert een functie als injectief, surjectief of bijectief, telt functies, injecties en surjecties, berekent samenstellingen en inversen, en telt paren in equivalentierelaties.