[wiskunde] Verzamelingen en aftelbaarheid
Moderators: ArcherBarry, Fuzzwood
-
- Berichten: 112
Verzamelingen en aftelbaarheid
Toon aan dat de volgende verzamelingen aftelbaar zijn :
a) de verzamelingen van alle binaire bestanden (i.e. computerbestanden, waarvan de inhoud
enkel bestaat uit 0en en 1en
b) de verzameling van alle computerprogramma’s die men kan schrijven in JAVA
Voor a denk ik het volgende:
alle even getallen natuurlijke worden afgebeeld als 0 en alle oneven als een 1 zo ontstaat een bijectie tussen N en alle binaire bestanden.
Voor b weet ik het niet goed.
mvg
a) de verzamelingen van alle binaire bestanden (i.e. computerbestanden, waarvan de inhoud
enkel bestaat uit 0en en 1en
b) de verzameling van alle computerprogramma’s die men kan schrijven in JAVA
Voor a denk ik het volgende:
alle even getallen natuurlijke worden afgebeeld als 0 en alle oneven als een 1 zo ontstaat een bijectie tussen N en alle binaire bestanden.
Voor b weet ik het niet goed.
mvg
- Berichten: 10.179
Re: Verzamelingen en aftelbaarheid
Dus er is maar 1 getal dat op 0 wordt afgebeeld? Immers moet dat om een bijectie te hebben.kunner schreef: ↑do 20 dec 2012, 19:01
alle even getallen natuurlijke worden afgebeeld als 0 en alle oneven als een 1 zo ontstaat een bijectie tussen N en alle binaire bestanden.
Ben je zeker van je opgave? Is ze letterlijk zo?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 112
Re: Verzamelingen en aftelbaarheid
Oei nee volgens mijn (slecht geformuleerde en blijkbaar niet aan te passen) uitleg zijn er oneindig veel getallen die zo op 0 worden afgebeeld. (immers er zijn oneindig veel even getallen). Dan weet ik niet goed hoe je deze oplostDrieske schreef: ↑do 20 dec 2012, 19:16
Dus er is maar 1 getal dat op 0 wordt afgebeeld? Immers moet dat om een bijectie te hebben.
Ben je zeker van je opgave? Is ze letterlijk zo?
Ja de opgave is exact zo.
- Berichten: 10.179
Re: Verzamelingen en aftelbaarheid
Prima. Laten we anders even a) voor waar aannemen. Kun je inzien dat elk programma in Java kan omgezet worden in een binaire string?
Voor a) zelf: helpt dit: neem eerst alle strings van lengte 0, daarna die van lengte 1, dan die van lengte 2, ...
Voor a) zelf: helpt dit: neem eerst alle strings van lengte 0, daarna die van lengte 1, dan die van lengte 2, ...
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 112
Re: Verzamelingen en aftelbaarheid
Nee eigenlijk niet. Ik weet wel dat het zo is en dat alles zo wordt opgeslagen. Is dat genoeg of hoor er meer bij?Drieske schreef: ↑do 20 dec 2012, 20:11
Prima. Laten we anders even a) voor waar aannemen. Kun je inzien dat elk programma in Java kan omgezet worden in een binaire string?
Voor a) zelf: helpt dit: neem eerst alle strings van lengte 0, daarna die van lengte 1, dan die van lengte 2, ...
Bij a zie ik het ook niet echt. Wrs is mijn eerste aanname fout en moet ik niet proberen om een bijectie te vinden tussen de strings en verzameling van de natuurlijke getallen.
- Berichten: 10.179
Re: Verzamelingen en aftelbaarheid
In se vind ik dat genoeg. Het is meer een technische vraag in dat opzicht dan een wiskundige. Essentie is dat b) zich herleidt tot a).kunner schreef: ↑do 20 dec 2012, 20:49
Nee eigenlijk niet. Ik weet wel dat het zo is en dat alles zo wordt opgeslagen. Is dat genoeg of hoor er meer bij?
Jawel hoor . Hoeveel strings heb je van lengte 1? Hoeveel van lengte 2? Algemeen: hoeveel van lengte n? Een exact getal is niet erg belangrijk, maar is het aantal steeds eindig of niet?
Bij a zie ik het ook niet echt. Wrs is mijn eerste aanname fout en moet ik niet proberen om een bijectie te vinden tussen de strings en verzameling van de natuurlijke getallen.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 112
Re: Verzamelingen en aftelbaarheid
In se vind ik dat genoeg. Het is meer een technische vraag in dat opzicht dan een wiskundige. Essentie is dat b) zich herleidt tot a). Jawel hoor . Hoeveel strings heb je van lengte 1? Hoeveel van lengte 2? Algemeen: hoeveel van lengte n? Een exact getal is niet erg belangrijk, maar is het aantal steeds eindig of niet?
Volgens mij altijd 2^n aantal mogelijkheden dus altijd eindig dus aftelbaar?
- Berichten: 10.179
Re: Verzamelingen en aftelbaarheid
Inderdaad. Zie je nu hoe je a) kunt bewijzen?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 112
Re: Verzamelingen en aftelbaarheid
Ik zou terugvallen op de stelling dat elke eindige verzameling aftelbaar is. Is dit voldoende?
- Berichten: 10.179
Re: Verzamelingen en aftelbaarheid
Neen, niet volledig . Stel dat ik het element van lengte 0 afbeeldt op 0. Stel nu dat ik het eerste element van lengte 1 afbeeldt op 1 en het tweede op 2. Nu bij lengte 2; daar heb ik 4 elementen. Ik som ze op, bijvoorbeeld door te ordenen van klein naar groot (dus 00, dan 01, dan 10 en dan 11). Nu beeld ik het kleinste af op 3, het tweede op 4 etc. Zie je nu een patroon?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 112
Re: Verzamelingen en aftelbaarheid
Neen, niet volledig . Stel dat ik het element van lengte 0 afbeeldt op 0. Stel nu dat ik het eerste element van lengte 1 afbeeldt op 1 en het tweede op 2. Nu bij lengte 2; daar heb ik 4 elementen. Ik som ze op, bijvoorbeeld door te ordenen van klein naar groot (dus 00, dan 01, dan 10 en dan 11). Nu beeld ik het kleinste af op 3, het tweede op 4 etc. Zie je nu een patroon?
Dus we maken eigenlijk een rij van allemaal eindige stukken code die is dan ook eindig en zo krijgen we een bijectie van N naar deze rij?
- Berichten: 10.179
Re: Verzamelingen en aftelbaarheid
Mja, ik weet nog niet of je het juist beet hebt hoor... Ik ben in bovenstaande zeer expliciet een bijectie aan het construeren. Kun je ze verderzetten, of misschien zelfs wat veralgemenen?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 112
Re: Verzamelingen en aftelbaarheid
Drieske schreef: ↑vr 21 dec 2012, 17:11
Mja, ik weet nog niet of je het juist beet hebt hoor... Ik ben in bovenstaande zeer expliciet een bijectie aan het construeren. Kun je ze verderzetten, of misschien zelfs wat veralgemenen?
Ik zie het ongeveer zo alle mogelijke rijen achter elkaar en dan een bijectie vanuit N
Oei het kleurtje van mijn laatste lijntje klopt wel niet
- Berichten: 10.179
Re: Verzamelingen en aftelbaarheid
Mja, nee, de pijltjes ook niet volledig. Je hebt er per element maar eentje nodig. Dus 3 hoort bij 10, maar 4 niet meer. Dat hoort bij 11.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 112
Re: Verzamelingen en aftelbaarheid
Ahzo dus per mogelijkheid maar 1 corresponderend cijfer in N?