Is de verzameling injectieve functies met signatuur N -> N niet aftelbaar?

Bewijs dat de verzameling injectieve functies met signatuur N -> N niet aftelbaar is.

Ik weet dat een injectieve functie f :A -> B een functie is zo dat voor iedere x en y uit A geldt:
als f (x ) = f (y) dan x = y (dus ieder beeld heeft een uniek origineel).

Maar ik heb geen idee hoe ik moet aantonen dat deze verzameling niet aftelbaar is.

Kan iemand mij helpen?

Weet jij het antwoord?

/2500

Nee, de verzameling injectieve functies van N naar N is niet aftelbaar. Als je met deze materie bezig bent, ken je wellicht het diagonaalargument (van Cantor); dat kan ook hier in aangepaste gebruikt worden. Een functie N->N kan je immers schrijven als een rij: a(1), a(2), a(3) , ... waarbij a(n) verschilt van a(m) voor n en m verschillend, indien de functie injectief is. Veronderstel dus dat de verzameling wel aftelbaar is en nummer al deze functies: f1: a1(1), a1(2), a1(3) , ... f2: a2(1), a2(2), a2(3) , ... f3: a3(1), a3(2), a3(3) , ... f4: ... ... Maak dan, geïnspireerd op het klassieke diagonaalargument, een nieuwe functie als volgt: f: a(1), a(2), a(3), ... Nu moet je wel opletten dat je deze functie construeert op zo'n manier dat deze f injectief is: - kies voor a(1) een natuurlijk getal verschillend van a1(1), - kies voor a(2) een natuurlijk getal verschillend van a1(1) en a2(2), ... - (algemeen) kies voor a(n) een natuurlijk getal dat verschilt van ai(i) voor alle i van 1 tot n-1, - ... Op deze manier is ook f injectief van N naar N en zo blijkt dat het onmogelijk is om alle injectieve functies van N naar N op te lijsten; de verzameling is dus overaftelbaar. Duidelijk zo? Anders vraag je maar.

Bronnen:
http://en.wikipedia.org/wiki/Cantor's_diag...

Het kan ook zonder een diagonaalelement. Zij S de verzameling van injectieve functies N->N en zij T de verzameling van bijectieve functies N->N. Het is nu duidelijk dat T een deelverzameling is van S. Iedere bijectieve f:N->N kan opgevat worden als een permutatie op N. Zij nu R de verzameling van die permutaties op N die te schrijven zijn als één cykel, waarbij de cykelelementen de canonieke ordening op N volgen. Nu is R een deelverzameling van T en dus van S, maar in het bijzonder is R reeds overaftelbaar. Dit tonen we aan door een expliciete bijectie te geven tussen R en P(N). Iedere X = {x_1, x_2, ...} in P(N) erft de ordening van N (Trek '<' terug onder de injectie X->N) , zodat X = {x_{i_1} < x_{i_2} < ...} Uit X vormen we nu een unieke permutatie in R: de cykel (x_{i_1} x_{i_2} ...). Omgekeerd vormen we een unieke deelverzameling van N van een cykel uit R, door te 'vergeten' dat het een permutatie is. Nu R en P(N) in bijectieve correspondentie staan is het voldoende te laten zien dat P(N) overaftelbaar is. We weten dat voor elke verzameling X, P(X)>X en aangezien N aftelbaar oneindig is moet P(N) dus wel overaftelbaar zijn. Conclusie: P(N) overaftelbaar => R overaftelbaar => T overaftelbaar => S overaftelbaar. Je ziet in het bijzonder dat de voorwaarde van injectieve functies niet eens zó sterk is om een overaftelbare verzameling te construeren.

Stel zelf een vraag

Ben je op zoek naar het antwoord die ene vraag die je misschien al tijden achtervolgt?

/100