Springen naar inhoud

Verzamelingen en aftelbaarheid



  • Log in om te kunnen reageren

#1

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 20 december 2012 - 19:01

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 20 december 2012 - 19:16

alle even getallen natuurlijke worden afgebeeld als 0 en alle oneven als een 1 zo ontstaat een bijectie tussen N en alle binaire bestanden.

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?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#3

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 20 december 2012 - 19:30

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?

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 oplost :(

Ja de opgave is exact zo.

#4

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 20 december 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, ...
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#5

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 20 december 2012 - 20:49

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, ...


Nee eigenlijk niet. Ik weet wel dat het zo is en dat alles zo wordt opgeslagen. Is dat genoeg of hoor er meer bij?

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.

Veranderd door kunner, 20 december 2012 - 20:51


#6

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 20 december 2012 - 21: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?

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).

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.

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?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#7

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 20 december 2012 - 23:16

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?

#8

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 20 december 2012 - 23:38

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.

#9

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 21 december 2012 - 13:55

Inderdaad. Zie je nu hoe je a) kunt bewijzen?


Ik zou terugvallen op de stelling dat elke eindige verzameling aftelbaar is. Is dit voldoende?

#10

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 21 december 2012 - 14:29

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.

#11

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 21 december 2012 - 17:08

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?

#12

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 21 december 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?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#13

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 21 december 2012 - 19:19

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 NGeplaatste afbeelding

Oei het kleurtje van mijn laatste lijntje klopt wel niet

#14

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 21 december 2012 - 19:42

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.

#15

kunner

    kunner


  • >100 berichten
  • 112 berichten
  • Ervaren gebruiker

Geplaatst op 21 december 2012 - 19:46

Ahzo dus per mogelijkheid maar 1 corresponderend cijfer in N?






Also tagged with one or more of these keywords: wiskunde

0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures