Verzamelingen/Deelverzamelingen

Na het bestuderen van dit hoofdstuk:

Weet je wat een deelverzameling is

Ken je de verschillende notaties voor deelverzameling

Weet je wat een machtsverzameling is

Weet je wat een partitie is

Deelverzameling

We zagen in het vorige hoofdstuk dat een Verzameling uit elementen bestaat. Laten we als voorbeeld een eindige verzameling nemen L die bestaat uit de letters van het alfabet zoals we dat in Nederland en België kennen. L={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z} Stel dat we vanuit bovengenoemde L definiëren:

• A={a,b,c}
• E={a,b,c,d,e}
• K={a,e,i,o,u}
• Z={x,y,z}
• Y={v,w,x,y,x}

Omdat alle elementen van A in L voorkomen, noemen we A een deelverzameling van L Hetzelfde geldt voor de hier genoemde verzamelingen E, K, Z en Y. We noteren dat als A ⊂ L. We zeggen dan "A is bevat in L" of “A is een deelverzameling van L”.

Venn-diagram dat het idee van een deelverzameling illustreert. A is een deelverzameling van B,  A⊂B,  en andersom is B een superset van A,  B⊃A.

De notatie A ⊆ L wordt gebruikt om aan te geven dat A een deelverzameling is van L, maar niet noodzakelijk een echte deelverzameling.

Helaas gebruiken niet alle auteurs hier dezelfde betekenis.

1. Sommige schrijvers gebruiken A ⊂ B om aan te geven dat A een deelverzameling van B is, en niet noodzakelijk een echte deelverzameling. Ze gebruiken dit symbool om zowel echte als niet echte deelverzamelingen aan te geven.
2. Een tweede groep gebruikt A ⊂ B om aan te geven dat A een echte deelverzameling van B is. Ze gebruiken A ⊆ B als deelverzameling A gelijk kan zijn aan B.
3. Een derde groep wiskundigen gebruikt A ⊆ B om aan te geven dat A een deelverzameling is van B, maar niet noodzakelijk een echte deelverzameling. Ze gebruiken A ⊊ B om een echte deelverzameling aan te geven.

In dit document gebruiken we zo veel mogelijk:

• A ⊆ B om aan te geven dat A een deelverzameling is van B, maar niet noodzakelijk een echte deelverzameling. Omgekeerd kunnen we dit schrijven als B ⊇ A.
• A ⊊ B om aan te geven dat A een echte deelverzameling is van B. We kunnen dit ook omgekeerd schrijven als B ⊋ A. Let op de streepjes door lage horizontale streep.

Voorbeelden:

• In bovenstaande voorbeeld geldt: A ⊊ L, E ⊊ L, K⊊ L, Y⊊ L en Z ⊊ L
• Z ⊊ Y ⊊ L oftewel Z is bevat in Y is bevat in L.
• $\mathbb {N}$ ⊊ $\mathbb {Z}$
• $\mathbb {Z}$ ⊊ $\mathbb {Q}$

De lege verzameling $\phi$ wordt als deelverzameling van elke verzameling gezien. Elke verzameling wordt ook als deelverzameling van zichzelf gezien.

Machtsverzamelingen

De machtsverzameling van een verzameling is de verzameling van alle deelverzamelingen.

• Voorbeeld 1: Laat B={a,b}

Dan is de machtsverzameling ${\mathcal {P}}$(B) = {{}, {a}, {b}, {a,b}}. De kardinaliteit van deze machtsverzameling is 2^2=4. De ${\mathcal {P}}$ is afkomstig van het Engelse 'powerset'.

• Voorbeeld 2: in bovenstaande Z={x,y,z} is de machtsverzameling P(Z) = {A:A ⊆ Z}

${\mathcal {P}}$(Z)= {{}, {x}, {y}, {z}, {x,y), {x,z}, {y,z}, {x,y,z}}. Merk op dat de kardinaliteit van deze machtsverzameling 2^3=8 is. De kardinaliteit van een machtsverzameling van een verzameling met n elementen is 2^n. Hiervan is het woord machtsverzameling afgeleid. Anders geformuleerd: Als A een eindige verzameling is, dan |${\mathcal {P}}$(A)| = 2^|A| We gaan deze formule hier niet bewijzen, dat valt onder het hoofdstuk w:combinatoriek.

Partities

Wanneer we alle elementen van een verzameling over een aantal deelverzamelingen verdelen, spreken we van een ‘’partitie’’. In een partitie hebben we verschillende deelverzamelingen, die samen alle elementen van de oorspronkelijke verzameling bevatten, zonder dat een element dubbel voorkomt of weggelaten wordt.

Als plaatje een voorbeeld:

Het linker vakje bevat de elementen a en b. Het middelste vakje bevat het element c. Het rechter vakje bevat de elementen d en e.

Voorbeeld 2:

Laat V={a, b, c}. Dan is {{A}, {b,c}} een partitie van V.

We zetten de eisen aan een partitie nog even op een rijtje:

• Een partitie van een verzameling V bestaat uit deelverzamelingen van V
• Elk element van V komt in een van de elementen van de partitie.
• De deelverzamelingen in de partitie bevatten alleen elementen uit V

Daarnaast spreken we af dat de lege verzameling geen deel is van de partitie

Stellingen

1. Als A ⊆ B en B ⊆ A dan A=B . (stelling 2.1)
2. Omgekeerd geldt dat als A=B dan A ⊆ B en B ⊆ A (stelling 2.2)
3. Als a ∈ A en A ⊆ B, dan a ∈ B. (stelling 2.3)
4. Als A ⊆ B en B ⊆ C, dan A ⊆ C. (stelling 2.4)

Bewijs van nr 1: Als A ⊆ B wil dit zeggen dat alle elementen van A in B zitten. Omgekeerd wil B ⊆ A zeggen dat alle elementen van B in A zitten. Kortom, de elementen van beide verzamelingen zijn gelijk, wat de definitie is van gelijke verzamelingen.

De andere 2 bewijzen komen voor als opgave.

Deelverzamelingen en Klassieke logica

Deelverzamelingen vormen de basis van wat vroeger als de Klassieke Logica of Aristotelische Logica werd beschouwd, hoewel John Baez terecht schreef dat Deelverzamelinglogica een betere naam is dan Klassieke logica. Maar de naam klassieke logica is ingeburgerd, en verwijst naar de Klassieke oudheid waarin Aristoteles deze redenering beschreef.

Ons instrumentarium is op dit moment voldoende om twee vormen te beschrijven.

vorm 1

Laat a een element van verzameling A zijn, dus a$\in$A. Laat A ⊆ B. Dan is a niet alleen een element van A, maar ook van B. (stelling 2.3 hierboven) Geïllustreerd:

• Voorbeeld 1: Jan is veeboer, en alle veeboeren zijn boeren. Is Jan een boer?

Laat veeboeren een verzameling zijn. Omdat alle veeboeren boeren zijn, is veeboeren een deelverzameling van boeren. Jan is element van de verzameling veeboeren, deelverzameling van de verzameling boeren, dus Jan is een element van de verzameling boeren.

• Voorbeeld 2: Een hamer is een stuk gereedschap. Alle gereedschappen zijn door mensen gemaakt. Wat kunnen we over een hamer zeggen?

Laat gereedschappen verzameling A zijn. Laat door mensen gemaakte voorwerpen verzameling B zijn. A is een deelverzameling van B. Hamer is een element van A. Dus hamers zijn door mensen gemaakt.

Dit geldt voor alle punten a $\in$A. Elke keer als we dit in onze omgeving tegenkomen, weten we dat deze afleiding juist is. We hoeven dat niet elke keer opnieuw te beredeneren.

Bovenstaande afleidingen zijn correct op grond van hun vorm. Natuurlijk moeten de twee premissen wel waar zijn om de conclusie waar te laten zijn. Het klassieke voorbeeld: (a) Alle mensen zijn sterfelijke wezens (b) Socrates is mens Dus : Socrates is een sterfelijk wezen. (a) en (b) noemen we premissen. De twee premissen zijn waar, en afleiding is correct, dus is de conclusie waar.

Maar als we als nemen: (a) alle zwanen zijn wit (b) Johannianus is een zwaan in de kinderboerderij Dan is hoeft de conclusie 'Johannianus is wit' niet juist te zijn, omdat (a) niet waar is. Er zijn namelijk ook zwarte zwanen.

vorm 2

Bekijk de zinnen:

• alle aanhangers van Socrates zijn filosofen
• alle filosofen zijn mensen
• alle mensen zijn sterfelijk

We herkennen in bovenstaande zinnen drie verzamelingen: A={aanhangers van Socrates}, B={filosofen}, C={mensen} en D={sterfelijke wezens}. De drie zinnen komen dan neer op:

• A ⊆ B
• B ⊆ C
• C ⊆ D

Door herhaaldelijk stelling 2.4 te gebruiken, kunnen we concluderen dat A ⊆ D, en dus alle aanhangers van Socrates sterfelijk zijn.

In een Venn-diagram wordt dat weer heel duidelijk geïllustreerd:

Ook hier geldt dat de premissen waar moeten zijn om de conclusie juist te laten zijn. Bijvoorbeeld:

• Alle boeren zijn veeboeren
• alle veeboeren zijn melkliefhebbers
• alle melkliefhebbers eten graag kaas

Geen van deze 3 premissen zijn juist, dus de conclusie 'alle boeren eten graag kaas' is een te snelle conclusie.

Beide vormen zijn heel elementair, en in het volgende hoofdstuk gaan we hier verder op in en kijken we ook naar ingewikkelder situaties.

Engelse termen

• deelverzameling: subset
• machtsverzameling: powerset
• partitie: partition

Opgaven

• II.1) Geef aan of de volgende beweringen juist of onjuist zijn:
  • 1.i) Elke verzameling is een deelverzameling van zijn Universele verzameling U.
  • 1.ii) Elke verzameling is een deelverzameling van $\phi$
  • 1.iii) De Machtsverzameling van {a, b, c, d} heeft 16 elementen
  • 1.iv) Als A={1, 2, 4}, B={3, 7, 8} en C={5, 6, 9, 10} dan is dit een partitie van {1 2, 3, 4, 5, 6, 7, 8, 9, 10}
• II.2) Als Betsy een koe is, en alle koeien in de wei staan, waar staat Betsy dan?
• II.3) Als Jan een loodgieter is, en alle loodgieters verantwoordelijk werk doen, wat kunnen we dan over Jan zeggen?
• II.4) Dagpauwogen zijn vlindersoorten. Alle vlindersoorten zijn insecten. Wat kunnen we zeggen over dagpauwogen?
• II.5) Beredeneer de waarheid van stelling 3.
• II.6) Beredeneer de waarheid van stelling 4.

Samenvatting: In dit hoofdstuk heb je geleerd

Wat een deelverzameling is

Hoe je een deelverzameling noteert (A ⊆ B)

Wat een machtsverzameling is en hoeveel elementen die bevat

Wat een partitie is