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

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.

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.