Funzione iniettiva tra un insieme infinito e $NN$

[andreadel1988]

Mi chiedevo se fosse possibile costruire sempre una funzione iniettiva da $NN$ a un insieme $X$ infinito, e mi sono risposto così:

si può fare, basta definire la funzione in modo che $0$ lo mandiamo in un elemento qualsiasi di $X$, poi $1$ lo mandiamo in un elemento di $X$ diverso da quello scelto per $0$, poi $2$ lo mandiamo in un elemento di $X$ diverso da quello scelto per $0,1$ e cosi via, il fatto che $X$ sia infinito mi permette di scegliere per ogni numero naturale un elemento di $X$ diverso da quelli scelti per i naturali precedenti e quindi la funzione è iniettiva.

[megas_archon]

In generale non si può fare: ti serve (abbastanza ovviamente) una forma di assioma della scelta.

Il fatto dipende anche un po' dalla tua definizione di "infinito": quella di Dedekind è solitamente quella usata (un insieme $X$ è infinito se esiste una endofunzione iniettiva ma non suriettiva $X\to X$). Per mostrare che \(|X| > n\) implica che $X$ è Dedekind-infinito serve l'assioma della scelta numerabile.

[andreadel1988]

In generale non si può fare: ti serve (abbastanza ovviamente) una forma di assioma della scelta.

Il fatto dipende anche un po' dalla tua definizione di "infinito": quella di Dedekind è solitamente quella usata (un insieme $X$ è infinito se esiste una endofunzione iniettiva ma non suriettiva $X\to X$). Per mostrare che \(|X| > n\) implica che $X$ è Dedekind-infinito serve l'assioma della scelta numerabile.

Più che altro mi serve per mostrare che un insieme infinito al più numerabile è numerabile, perciò mi serviva una funzione iniettiva da $NN$ a $X$.