[WI] Discrete wiskunde vragen

[Zink]

Ik heb geen enkel idee hoe ik dit moet bewijzen.

Is hier iemand zo vriendelijk om mij misschien te helpen ?

1) Laat zien dat de verzameling van eindige deelverzamelingen van N telbaar zijn.

2) Laat zien dat de verzameling van alle deelverzamelingen van N niet telbaar zijn


alvast bedankt.

Laat N lopen van 1 tot 10. Dit aantal is eindig, je kan de uitkomsten bij elkaar tellen.
Laat N lopen van 1 tot oneindig. Je kan geen uitkomst geven aangezien er steeds weer een N bijkomt.

[bulbanos]

deze redenering klopt volgens mij niet

omdat er N bijkomt wil het juist zeggen dat het aftelbaar is.
Hij heeft het over eindige verzamelingen, niet over een eindig aantal verzamelingen.
Zo zijn de 'breuken' ook aftelbaar hoewel er altijd maar meer lijken bij te komen.
Maar ben zelf niet thuis in die materie

[Young Grow Old]

bulbanos schreef op 04-10-2004 @ 19:59 :
deze redenering klopt volgens mij niet

omdat er N bijkomt wil het juist zeggen dat het aftelbaar is.
Hij heeft het over eindige verzamelingen, niet over een eindig aantal verzamelingen.
Zo zijn de 'breuken' ook aftelbaar hoewel er altijd maar meer lijken bij te komen.
Maar ben zelf niet thuis in die materie

bedoelt TS niet te zeggen dat |N aftelbaar is dan?

[Zink]

t voorbeeld dat in mijn boek staat is het volgende : Ze laten hier zien dat de deelverzamelingen van R niet telbaar zijn.

Veronderstel dat R telbaar is, dan kan je elk element zo voorstellen :

0.a11a12a13a14...
0.a21a22a23a24...
0.a31a32a33a34...

.
.
.
0.ai1ai2ai3ai4...


aij waarbij j het zoveelste getal van het i-ste nummer op eeb lijst is

Stel nu het nummer :

b = 0.b1b2b3b4...


waarbij


bi = [1 als aii = 9
[9 - aii als aii = 0, 1, 2, 3, ..., 8

In het boek zeggen ze nu dat dit getal b niet op de lijst staat b1 verschillend is van a11, b2 verschillend is van a22, etc. Dus de verzameling van nummer tussen 0 en 1 is niet telbaar , dus een deelverzameling van R is niet telbaar, dus R zelf is ook niet telbaar.


Ikzelf snap niet precies hoe ze bij die stelling komen van bii en waarom b niet op de lijst staat. Maar k denk wel dat ik het op zon manier moet bewijzen.

Zink schreef op 04-10-2004 @ 18:11 :
1) Laat zien dat de verzameling van eindige deelverzamelingen van N telbaar zijn.

Alle eindige deelverzamelingen van N zijn in feite gewoon eindige verzamelingen integers. Het gaat er dan dus om of de integers wel of niet in de deelverzameling zitten. Je zou dan als volgt kunnen redeneren:

Integer 1 wel in de verzameling, 2 t/m N niet.
Integer 1 en 2 wel in de verzameling, 3 t/m N niet.
Integer 1 niet, 2 wel, 3 t/m N niet.
1, 2 en 3 wel, 4 t/m N niet.
1 niet, 2 en 3 wel, 4 t/m N niet.
1 en 3 wel, 2 niet, 4 t/m N niet.
3 wel, 1, 2 niet, 4 t/m N niet.
Enzovoorts. (met N een willekeurige integer groter dan 4, dit geldt dus voor iedere N)

Op deze manier zijn alle eindige deelverzamelingen aftelbaar.

Nummer 2) kan ik je niet mee helpen. Misschien (vast wel ) weet Mathfreak het.

Edit: misschien geldt bij nummer 2) dat je oneindig lang moet tellen voor dat je bij oneindig bent en dat daardoor de verzamelingen niet aftelbaar zijn.

[mathfreak]

Zink schreef op 04-10-2004 @ 18:11 :
Ik heb geen enkel idee hoe ik dit moet bewijzen.

Is hier iemand zo vriendelijk om mij misschien te helpen ?

1) Laat zien dat de verzameling van eindige deelverzamelingen van N aftelbaar zijn.

Laat V een eindige deelverzameling van N zijn, dan kun je voor iedere V het kardinaalgetal (het aantal elementen van V) bepalen. Omgekeerd kun je voor ieder natuurlijk getal n een eindige verzameling V definiëren waarvan het kardinaalgetal gelijk is aan n. Hiermee is de aftelbaarheid van de verzameling eindige deelverzamelingen van N bewezen.

Zink schreef op 04-10-2004 @ 18:11 :
2) Laat zien dat de verzameling van alle deelverzamelingen van N niet aftelbaar zijn.

Laat P(N) de machtsverzameling van N, dus de verzameling van alle deelverzamelingen van N, zijn. Er geldt dan dat het kardinaalgetal van P(N) groter is dan het kardinaalgetal van N. Omdat een verzameling alleen maar aftelbaar is als het kardinaalgetal daarvan kleiner of gelijk is aan het kardinaalgetal van N, betekent dit dat P(N) niet aftelbaar is. Hiermee is de overaftelbaarheid van de verzameling van alle deelverzamelingen van N bewezen.

[liner]

Zink schreef op 04-10-2004 @ 20:40 :


Ikzelf snap niet precies hoe ze bij die stelling komen van bii en waarom b niet op de lijst staat. Maar k denk wel dat ik het op zon manier moet bewijzen.

dit is volgens mij het bewijs van cantor:


Het diagonaal bewijs van Cantor.
Stel dat er aftelbaar veel elementen zijn in de verzameling <0,1>. Dan kun je een tabel maken met alle getallen erin en wel als volgt:

0,0000000000000100010100...
0,1110001101123450452874...
0,7439871982349873498743...
0,8102938876428761243987...
0,9000000000000000000000...
.


Wanneer een getal een rationaal getal is (dit is een "echte" breuk, bv 1/2), dan vullen we dit getal aan met oneindig veel nullen (dus 1/2 = 0,500000...). Op deze manier zouden we alle getallen uit <0,1> kunnen opschrijven. De vraag is nu of we wel alle getallen hebben. Cantor bewees van niet. Hij paste de volgende truc toe: Verhoog de n-e decimaal van het n-e getal met 1,behalve als deze decimaal een 9 is, dan wordt deze decimaal 0. Dus de eerste decimaal van het eerste getal wordt in ons voorbeeld een 1, de tweede decimaal van het tweede getal in ons voorbeeld wordt een 2 etcetera. We krijgen nu het getal W = 0,12431.... . Het getal W kan niet in onze tabel staan om de volgende reden: W kan niet het eerste getal zijn, want de eerste decimaal verschilt, W kan ook niet het tweede getal zijn, want de tweede decimaal verschilt, W kan ook niet het n-e getal zijn, want de n-e decimaal verschilt. Conclusie: W staat niet in onze tabel, dus kunnen we niet een aftelbaar oneidige tabel maken zoals aangenomen en dus moet de verzameling <0,1> machtiger zijn dan Alef-nul. Maar dan is ook de verzameling der reële getallen machtiger dan Alef-nul, daar <0,1> slechts een deelverzameling was van de verzameling der reele getallen. De verzameling der reele getallen heeft een machtigheid die we Alef-een zullen noemen. Er resten ons nu drie vragen: Zijn er meer verzamelingen met machtigheid Alef-een?, zijn er verzamelingen met een nog hogere machtigheid dan Alef-een?, en zijn er verzamelingen met een machtigheid die ligt tussen Alef-nul een Alef-een? De eerste twee vragen zijn gemakkelijk met ja te beantwoorden, de laatste vraag is tot nog toe onbeantwoord gebleven.


'gekopieerd en geplakt van een site'
maar dit heeft waarschijnlijk niets te maken met N

[mathfreak]

liner schreef op 05-10-2004 @ 19:28 :
dit is volgens mij het bewijs van cantor:

Het gaat daar inderdaad om het diagonaalargument van Cantor. Met behulp van dit diagonaalargument kun je laten zien dat de verzameling Q van de rationale getallen net als de verzameling Z van de gehele getallen aftelbaar is en dat IR overaftelbaar is. Wat je in ieder geval kunt zeggen is dat een gegeven verzameling aftelbaar is als er een bijectie tussen deze verzameling en IN gedefinieerd kan worden.

[liner]

mathfreak schreef op 05-10-2004 @ 20:19 :
Het gaat daar inderdaad om het diagonaalargument van Cantor. Met behulp van dit diagonaalargument kun je laten zien dat de verzameling Q van de rationale getallen net als de verzameling Z van de gehele getallen aftelbaar is en dat IR overaftelbaar is. Wat je in ieder geval kunt zeggen is dat een gegeven verzameling aftelbaar is als er een bijectie tussen deze verzameling en IN gedefinieerd kan worden.

precies, dat is de definitie van een aftelbare verzameling, als er een bijectie is tussen IN en die verzameling. Dit is voglens mij wo stof in nederland, hoe zit het dan bij belgie? ik denk iets voor de 5e of 6e klas.

[mathfreak]

liner schreef op 05-10-2004 @ 20:50 :
precies, dat is de definitie van een aftelbare verzameling, als er een bijectie is tussen IN en die verzameling. Dit is voglens mij wo stof in nederland, hoe zit het dan bij belgie? ik denk iets voor de 5e of 6e klas.

Het begrip bijectie komt in België in ieder geval wel in het middelbaar onderwijs aan de orde, en zelfs al in het eerste jaar, in België het Eerste Middelbaar genoemd. Het definiëren van aftelbaarheid van verzamelingen door middel van een bijectie tussen IN en dergelijke verzamelingen komt daar verder pas na het middelbaar onderwijs aan de orde.