Re: Ammorteeee!
Inviato: 13 lug 2013, 09:54
Ah, per la numerabilità di \(\mathbb{N}^k\) mi è venuta un'idea carina. E' stato detto che se \(A \subseteq B\) e \(B\) è numerabile, allora \(A\) è numerabile.
Detti \(p_1, \ldots, p_k\) i primi \(k\) numeri primi, allora metto in corrispondenza biunivoca \((a_1, \ldots,a_k ) \in \mathbb{N}^k\) con \(p_1^{a_1} \cdot \ldots p_k ^{a_k}\). Visto che i numeri della forma \(p_1^{a_1} \cdot \ldots p_k ^{a_k}\) sono un sottoinsieme dei numeri naturali, sono anch'essi numerabili. Che sia biunivoca è naturale: ad ogni \(k\)-upla di naturali corrisponde un solo numero, e ad ogni numero divisibile solo per primi tra \(p_1, \ldots p_k\) corrisponde una sola \(k\)-upla di naturali.
A questo punto posso numerare tutto facilmente:
1.\((a_1, \ldots, a_k) \in \mathbb{Z}^k\) lo metto in corrispondenza biunivoca con \(\displaystyle (|a_1|, \ldots, |a_k|, \frac{sgn(a_1) + 1}{2}, \ldots, \frac{sgn(a_k)+1}{2}) \in \mathbb{N}^{2k}\);
2.\(\displaystyle (\frac{a_1}{b_1}, \ldots, \frac{a_k}{b_k}) \in \mathbb{Q}^k\) lo metto in corrispondenza biunivoca con \(\displaystyle (|a_1|, \ldots, |a_k|, |b_1|, \ldots, |b_k|, \frac{sgn(a_1/b_1)+1}{2}, \ldots, \frac{sgn(a_k / b_k)}{2}) \in \mathbb{N}^{3k}\).
3. Per l'insieme dei polinomi a coefficienti razionali, servono alcune piccole considerazioni. Nella dimostrazione della numerabilità di \(\mathbb{N}^k\), non abbiamo imposto limiti superiori su \(k\). Di fatto, anche prendendo un \(k\) ENORME, ho comunque sempre abbastanza primi. In particolare, anche un \(k\) infinito va bene, perchè i numeri primi sono infiniti. Sia \(Q_k[x]\) l'insieme polinomi a coefficienti razionali che ha al massimo grado \(k\). Dato
\(\displaystyle P(x) \in Q_n[x]\ |\ P(x) = \sum_{i=0}^{n} c_i x^i \)
posso metterlo in corrispondenza con \( (c_0, \ldots, c_n) \in \mathbb{Q}^{n+1}\), che può essere messo in corrispondenza biunivoca con \(\mathbb{N}^{3n+3}\). Dunque l'insieme dei polinomi di grado \(n\)-esimo è numerabile. Prendendo \(n\) sempre più grande, abbraccerò una classe di polinomi sempre più grande, e per \(n\) che va all'infinito abbraccerò tutti i polinomi a coefficienti razionali.
Per convincersene, basta accorgersi che preso un numero naturale qualsiasi che rispetti le condizioni per essere messo in corrispondenza con \(\mathbb{Q}^k\) (e lo si può fare in un modo solo), allora può essere messo in corrispondenza con un solo polinomio di grado \(k-1\); viceversa, ogni polinomio di grado \(k+1\) si può mettere in corrispondenza con una \(k\)-upla di numeri razionali, che a sua volta può essere messa in corrispondenza con uno e un solo numero naturale.
P.S. Ehm...il passaggio all'infinito l'ho fatto con molta indifferenza (e mettendoci parole suggestive come ENORME), ma non so se è giusto xD
Detti \(p_1, \ldots, p_k\) i primi \(k\) numeri primi, allora metto in corrispondenza biunivoca \((a_1, \ldots,a_k ) \in \mathbb{N}^k\) con \(p_1^{a_1} \cdot \ldots p_k ^{a_k}\). Visto che i numeri della forma \(p_1^{a_1} \cdot \ldots p_k ^{a_k}\) sono un sottoinsieme dei numeri naturali, sono anch'essi numerabili. Che sia biunivoca è naturale: ad ogni \(k\)-upla di naturali corrisponde un solo numero, e ad ogni numero divisibile solo per primi tra \(p_1, \ldots p_k\) corrisponde una sola \(k\)-upla di naturali.
A questo punto posso numerare tutto facilmente:
1.\((a_1, \ldots, a_k) \in \mathbb{Z}^k\) lo metto in corrispondenza biunivoca con \(\displaystyle (|a_1|, \ldots, |a_k|, \frac{sgn(a_1) + 1}{2}, \ldots, \frac{sgn(a_k)+1}{2}) \in \mathbb{N}^{2k}\);
2.\(\displaystyle (\frac{a_1}{b_1}, \ldots, \frac{a_k}{b_k}) \in \mathbb{Q}^k\) lo metto in corrispondenza biunivoca con \(\displaystyle (|a_1|, \ldots, |a_k|, |b_1|, \ldots, |b_k|, \frac{sgn(a_1/b_1)+1}{2}, \ldots, \frac{sgn(a_k / b_k)}{2}) \in \mathbb{N}^{3k}\).
3. Per l'insieme dei polinomi a coefficienti razionali, servono alcune piccole considerazioni. Nella dimostrazione della numerabilità di \(\mathbb{N}^k\), non abbiamo imposto limiti superiori su \(k\). Di fatto, anche prendendo un \(k\) ENORME, ho comunque sempre abbastanza primi. In particolare, anche un \(k\) infinito va bene, perchè i numeri primi sono infiniti. Sia \(Q_k[x]\) l'insieme polinomi a coefficienti razionali che ha al massimo grado \(k\). Dato
\(\displaystyle P(x) \in Q_n[x]\ |\ P(x) = \sum_{i=0}^{n} c_i x^i \)
posso metterlo in corrispondenza con \( (c_0, \ldots, c_n) \in \mathbb{Q}^{n+1}\), che può essere messo in corrispondenza biunivoca con \(\mathbb{N}^{3n+3}\). Dunque l'insieme dei polinomi di grado \(n\)-esimo è numerabile. Prendendo \(n\) sempre più grande, abbraccerò una classe di polinomi sempre più grande, e per \(n\) che va all'infinito abbraccerò tutti i polinomi a coefficienti razionali.
Per convincersene, basta accorgersi che preso un numero naturale qualsiasi che rispetti le condizioni per essere messo in corrispondenza con \(\mathbb{Q}^k\) (e lo si può fare in un modo solo), allora può essere messo in corrispondenza con un solo polinomio di grado \(k-1\); viceversa, ogni polinomio di grado \(k+1\) si può mettere in corrispondenza con una \(k\)-upla di numeri razionali, che a sua volta può essere messa in corrispondenza con uno e un solo numero naturale.
P.S. Ehm...il passaggio all'infinito l'ho fatto con molta indifferenza (e mettendoci parole suggestive come ENORME), ma non so se è giusto xD