Domanda SNS orale

[Sebastiano Marchi]

Mi sono imbattuto nella seguente domanda:
Trovare una bigezione esplicita di Q+ in Z (non il serpentone sul piano
ma qualcosa con i primi).
Ho associato ogni razionale positivo a una successione di esponenti interi, mi rimarrebbe da dimostrare che le successioni di esponenti interi sono numerabili. Qualcuno sa la risposta?

[Sirio]

Occhio che non è vero che le successioni di interi sono numerabili. Però è vero che le successioni di interi che da un certo punto in poi sono costantemente zero sono numerabili.

[Sebastiano Marchi]

Ah, sì, mi ero dimenticato di scriverlo.

[Sebastiano Marchi]

Quello che mi manca è proprio come numerarle, senza usare Cantor.

[Sirio]

In questo momento una bigezione esplicita (che non usi mai "il serpentone") non mi viene, però una funzione suriettiva esplicita $\mathbb Z_{>0}\rightarrow\mathbb Q_{>0}$ sì, e magari va abbastanza bene, idk.

Testo nascosto:

Chiamo $(p_i)_{i\in\mathbb N}$ la successione dei numeri primi, con $p_0=2$, $p_1=3$, etc.

La funzione che ho in mente sarebbe:
\[
\prod_{i=0}^N p_i^{e_i}\mapsto\prod_{i=0}^{e_0-1} p_i^{e_{i+2}-e_1}
\]
Che evidentemente non è iniettiva perché per esempio manda a 1 tutte le potenze di 2, però è suriettiva perché ammette come inversa destra:
\[
\prod_{i=0}^M p_i^{\epsilon_i}\mapsto 2^{M+1}3^{E}\prod_{i=2}^{M+2} p_i^{\epsilon_{i-2}+E}
\]
Dove assumiamo $\epsilon_M\ne 0$ (e prendiamo $M=-1$ se partiamo da $1$) e definiamo $E=\max(\{0\}\cup\{-\epsilon_i| i\ge 0\})$.

[Sebastiano Marchi]

Mi è venuta in mente una soluzione: consideriamo le successioni finite di numeri naturali. Sono numerabili (associo ad ognuna il rispettivo numero intero positivo usandole come successioni di esponenti). Ad esempio 3,0,11,9 ha posizione [math]2^3 5^{11} 7^9. La funzione è biunivoca. A questo punto dico che per le successioni finite con numeri negativi e positivi (in relazione biunivoca con i razionali positivi), le ordino come ho ordinato quelle contenenti solo naturali, ma metto in mezzo tra una solo positiva e l'altra poi tutte le combinazioni (finite) usando i meno. Ad esempio: dopo la 3,0,11,9 metto la -3,0,11,9, poi la 3,0,-11,9, ecc. Fin quando non sono finite, a quel punto prendo la successione di naturali successive. Fatto questo, ho una biunivoca da [math]\mathbb{Q^+} agli interi positivi, facilmente trasformabile in una biunivoca da [math]\mathbb{Q^+} a [math]\mathbb{Z}. Ho fatto errori? Se no, il trucco era considerare entrambi in fattori primi, e non solo i razionali positivi.

[Sebastiano Marchi]

Però devo dire che non è affatto scontata come domanda, anche rispetto alle altre poste agli orali (come il lemma di Sperner a una dimensione). Soprattutto perché online non si trova da nessuna parte qualcuno che non usi Cantor.

[Sirio]

Mi è venuta in mente una soluzione: consideriamo le successioni finite di numeri naturali. Sono numerabili (associo ad ognuna il rispettivo numero intero positivo usandole come successioni di esponenti). Ad esempio 3,0,11,9 ha posizione [math]2^3 5^{11} 7^9. La funzione è biunivoca. A questo punto dico che per le successioni finite con numeri negativi e positivi (in relazione biunivoca con i razionali positivi), le ordino come ho ordinato quelle contenenti solo naturali, ma metto in mezzo tra una solo positiva e l'altra poi tutte le combinazioni (finite) usando i meno. Ad esempio: dopo la 3,0,11,9 metto la -3,0,11,9, poi la 3,0,-11,9, ecc. Fin quando non sono finite, a quel punto prendo la successione di naturali successive. Fatto questo, ho una biunivoca da [math]\mathbb{Q^+} agli interi positivi, facilmente trasformabile in una biunivoca da [math]\mathbb{Q^+} a [math]\mathbb{Z}. Ho fatto errori? Se no, il trucco era considerare entrambi in fattori primi, e non solo i razionali positivi.

Mi sembra che funzioni

[fph]

Diciamo, il punto cruciale è capire cosa vuol dire "bigezione esplicita" nella richiesta. Se non va bene "faccio una lista dei razionali e cancello i doppioni", allora non so se va bene "faccio una lista delle successioni e poi cambio i segni". In confronto, una funzione N^2 -> N (o Z^2 -> Z) biiettiva si può scrivere proprio come una formula esplicita, e secondo me chi ha fatto la domanda intendeva quello.

[fph]

Detto questo, comunque concordo che non è una domanda facile: se la facessi a un orale sarebbe per vedere come la approcci e ragionare insieme a te; non credo che la commissione si aspetti che tu pensi due minuti e poi arrivi con una soluzione pronta interamente da solo/a.

[Sebastiano Marchi]

Io con mia madre (algebrista dell'Unipd che ha insegnato alla galileiana) non eravamo riusciti a risolverlo la prima volta.