OliForum Matematico

jordan ha scritto: In ordine:

1) Come dimostri che l'insieme degli interi pari positivi è numerabile?

2) Come dimostri che l'insieme degli interi è numerabile?

3) Come dimostri che l'insieme degli interi pari è numerabile?

4) Come dimostri che l'insieme dei razionali positivi è numerabile?

5) Come dimostri che l'insieme dei razionali è numerabile?


Ps. Non è quello per cui è nato il problema, nè la sezione giusta, ma sapere queste cose non fa sicuro male!

1) Ad ogni numero pari positivo $ 2n $ associo il numero naturale $ n $

2) Ad ogni numero naturale $ n $ associo $ (-1)^n \lceil\frac{n}{2}\rceil $

3) Ad ogni numero naturale $ n $ associo l'intero pari $ 2(-1)^n \lceil\frac{n}{2}\rceil $

E qui comincio a usare "due volte" variabili naturali:

4) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale positivo $ \displaystyle\frac{n}{d} $ (qui posso semplicemente dire di escludere frazioni uguali e che $ d $ debba essere diverso da $ 0 $?)

5) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale $ \displaystyle \frac{n}{(-1)^n \lceil\frac{n}{2}\rceil} $

Boh...

simone256 ha scritto:1) Ad ogni numero pari positivo $ 2n $ associo il numero naturale $ n $

2) Ad ogni numero naturale $ n $ associo $ (-1)^n \lceil\frac{n}{2}\rceil $

3) Ad ogni numero naturale $ n $ associo l'intero pari $ 2(-1)^n \lceil\frac{n}{2}\rceil $

Ok, dovresti essere convinto ora che almeno la 2) e la 3) sono funzioni biettive. Riguardo la 1), $0$ è un numero naturale, e non viene associato ad alcun intero positivo pari (anche se, ci vuole poco a correggere).

Piu' in generale, una volta che hai dimostrato che dati due insiemi non finiti $A \subseteq B$ tale che $B$ è numerabile, allora anche $A$ è numerabile (E' vero? Corollario: la domanda 5 implica tutte le altre..)

simone256 ha scritto:E qui comincio a usare "due volte" variabili naturali:

4) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale positivo $ \displaystyle\frac{n}{d} $ (qui posso semplicemente dire di escludere frazioni uguali e che $ d $ debba essere diverso da $ 0 $?)

5) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale $ \displaystyle \frac{n}{(-1)^n \lceil\frac{n}{2}\rceil} $

No, non ci siamo qui, non puoi usare coppie di numeri naturali. Come prima devi soltanto creare una funzione biettiva tra l'insieme richiesto e $\mathbb{N}:=\{0,1,2,\ldots\}$.

Sarebbe anche sufficiente che mostri che $\mathbb{N}^k$ è numerabile per ogni intero $k\ge 1$, e poi dire perchè è sufficiente..

Tornando in topic, non ho ancora risolto il problema dei cappelli con infiniti condannati; qualcuno ha avuto qualche idea?

jordan ha scritto: 4) Come dimostri che l'insieme dei razionali positivi è numerabile?

Io qui assocerei semplicemente alla sequenza dei numeri naturali
$ N=(1,2,3..) $
la sequenza dei numeri razionali $ n/d $, $ n $ e $ d $ interi, ordinandoli mettendo prima i razionali la cui somma $ n+d $ è minore, a parità di somma mettendo prima i razionali con $ d $ minore, a parità di $ d $ prima i razionali il cui $ n $ è minore. Da questa sequenza toglierei tutti i razionali in cui $ n $ e $ d $ non sono primi tra loro e tutti i razionali in cui $ d=0 $. Avendoli ordinati quindi è possibile associare a ciascun razionale un numero naturale, contando la posizione che occupa nella sequenza ordinata. Però non credo che si possa dimostrare solo così, infatti non ho trovato nessuna formula con cui partendo da un numero naturale posso trovare il corrispettivo razionale..(sarebbe molto più facile se non ci fossero da togliere tutte le frazioni equivalenti )

jordan ha scritto:Tornando in topic, non ho ancora risolto il problema dei cappelli con infiniti condannati; qualcuno ha avuto qualche idea?

Io sono solo arrivata a notare che dividendoli in gruppi in cui il primo del gruppo salva tutti gli altri si possano salvare infiniti condannati, ma non se ne salverebbero altrettanti.. eppure il rapporto dei non salvati potrebbe essere piccolissimo..

_Ipazia_ ha scritto:sarebbe molto più facile se non ci fossero da togliere tutte le frazioni equivalenti

Se dimostri che l'insieme è numerabile quando contiene anche altre frazioni "equivalenti", allori dimostri qualcosa di piu' forte, no?

jordan ha scritto:

_Ipazia_ ha scritto:sarebbe molto più facile se non ci fossero da togliere tutte le frazioni equivalenti

Se dimostri che l'insieme è numerabile quando contiene anche altre frazioni "equivalenti", allori dimostri qualcosa di piu' forte, no?

Si ma trovando una funzione che associa a ogni numero naturale un razionale, se ci fossero le frazioni equivalenti la funzione non sarebbe più biiettiva, o no?


Comunque provo a scrivere questa "funzione" considerando solo l'intervallo da 0 a 1 di Q, dato che se un insieme è numerabile lo è anche un suo sottoinsieme infinito (vale anche il contrario vero? )
Ho ordinato i razionali in questo modo:
$ N(n): 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , ... $
$ Q(q): 0 , \frac{1}{1} , \frac{1}{2}, \frac{2}{2} , \frac{1}{3}, \frac{2}{3} , \frac{3}{3}, \frac{1}{4} , ... $
Osservando i denominatori, noto che quando nella sequenza cambia il denominatore (cioè al numero naturale 2, al 4, al 7, all'11..), il corrispondente n è dato da:
(indico con d il denominatore)
$ n=\frac{d(d+1)}{2} $
quindi trovo d:
$ d_{1,2}=\frac{-1\pm\sqrt{1+8n}}{2} $
posso eliminare la soluzione con d negativo, dato che considero solo razionali positivi, quindi:
$ d=\frac{-1+\sqrt{1+8n}}{2} $
Quindi, facendo in modo che la formula valga per tutti gli n:
$ d=\lceil\frac{-1+\sqrt{1+8n}}{2}\rceil $
Per il numeratore (lo chiamo m) invece:
$ m=n-\frac{d(d-1)}{2} $
Ho così associato ad ogni numero naturale un razionale dell'intervallo [0,1], lasciando però le frazioni equivalenti e quelle con denominatore=0..

jordan ha scritto:Sarebbe anche sufficiente che mostri che $ \mathbb{N}^k $ è numerabile per ogni intero $ k \ge 1 $, e poi dire perchè è sufficiente..

Ah ok chiaro! Ho capito come funziona la dimostrazione ma ora devo cercare di sparare fuori una legge analitica! D:

Anche se probabilmente non interessa a nessuno, posto la mia soluzione per infiniti condannati:
Definizioni e imprecisioni varie(per far sembrare la soluzione pomposa. Se stai leggendo questo hai perso):
1) "Un prigioniero muore/non si salva/si sacrifica"= l'algoritmo NON garantisce la sua vita, ma potrebbe capitare che il colore detto corrisponde al proprio e quindi si salva
2) Sia $ \Omega $ l'insieme dei prigionieri che si salvano e $ \Psi $ di quelli che muoiono
3) Fatto su cui gira la dimostrazione: il primo prigioniero NON può dare l'informazione per tutti gli altri prigionieri (non solo considerando la somma: se ci fosse un altro modo, l'informazione data dal primo è limitata mentre l'informazione su "tutti" è infinita)[Ovviamente se questo pseudo-assioma è falso crolla tutto]
4) Sia $ n $ il numero di prigionieri su cui il primo può dare/dà un informazione
5) Sia $ k $ il numero di colori
6) Sia $ N $ l'insieme dei prigionieri che NON ottengono l'informazione dal primo prigioniero .

Presuppongo di aver trovato un algoritmo funzionante. Distinguo tre casi:
1) $ \Psi $ è infinito
2) $ \Psi $ ha un solo elemento, ovvero il primo prigioniero.
3) $ \Psi $ ha più di un elemento, ma è limitato

Caso №1:
Banalmente, si può riutilizzare l'algoritmo per un numero di prigionieri limitato e fare in modo che il 1°, il $ (n+1) $°, il $ (n+2) $° si sacrifichino per dare l'informazione agli altri; in tal modo con $ n $ tendente a infinito $ \frac{|\Psi|}{|\Omega|} $ tende a $ 0 $.

Caso №2:
Siano $ X,Y \in N $ e $ a,b $ due "situazioni" (ovvero corrispondenza di colori per prigioniero) identiche tranne per $ X $ e $ Y $ (ovvero il colore del primo in $ a $ è uguale a quello del primo in $ b $, ecc.).
Notiamo che se esiste un siffatto algoritmo, tutti i prigionieri tranne $ X $ e $ Y $ diranno gli stessi colori, quindi in entrambi $ X_a $ può capire di trovarsi nel caso $ a $ solo grazie al colore detto dal 1°. Le possibili combinazioni di colori tra $ X $ e $ Y $ sono $ k^2 $, mentre il primo può dare un informazione per soli $ k $ casi, ovvero per il pigeonhole $ X $ e $ Y $ non possono capire in quale caso si trovano.

Caso №3:
Sia $ h $ il numero di prigionieri che si sacrificano. Prendiamo $ Z_1,Z_2,Z_3...Z_{h+1} \in N $. Analogamente al caso precedente, l'informazione data dai sacrificati "è" $ k^{h} $ mentre quella necessaria è $ k^{h+1} $, quindi questo caso non è possibile.

Spero sia corretta e decentemente comprensibile

Era stato detto che si riusciva a salvarli tutti tranne il primo, non sprechiamo vite umane così a cuor leggero quindi. In particolare il fatto su cui gira la dimostrazione (cit.) è quindi falso (non sono andato avanti a leggere).
Comunque la soluzione che conosco usa qualche fatterello non elementare.

ndp15 ha scritto:Era stato detto che si riusciva a salvarli tutti tranne il primo, non sprechiamo vite umane così a cuor leggero quindi. In particolare il fatto su cui gira la dimostrazione (cit.) è quindi falso (non sono andato avanti a leggere).
Comunque la soluzione che conosco usa qualche fatterello non elementare.

D:
Per curiosità, perché(è falso)?

karlosson_sul_tetto ha scritto: D:
Per curiosità, perché(è falso)?

Perché dire che c'è una soluzione in cui si salvano tutti tranne il primo equivale proprio a dire che con l'informazione di quanto detto dal primo condannato si innesta un procedimento in cui tutti gli altri si salvano.

Sveliamo il mistero?

jordan ha scritto:Sveliamo il mistero?

Copio e incollo da altro forum:"Possiamo vedere una disposizione dei nanetti come la rappresentazione in binario di un reale, con 0 indicato da un cappello nero ed 1 da un cappello bianco.

Poniamo la seguente relazione di equivalenza fra reali: a ~ b se, definitivamente, hanno la stessa rappresentazione in base due.

Una volta dimostrato che questa è una relazione di equivalenza otteniamo che l'insieme dei reali è partizionato in infinite classi di congruenza.

Per l'assioma della scelta (http://it.wikipedia.org/wiki/Assioma_della_scelta), possiamo prendere da ogni classe di congruenza un rappresentante privilegiato.

Ogni nanetto, guardando la stringa di fronte a sé, è in grado di capire in che classe di congruenza si trova la stringa intera, quindi conosce il rappresentante privilegiato di ogni classe. Il primo nanetto indica quindi (analogamente al caso finito) la parità del numero di cappelli neri fra i nanetti che hanno un cappello di colore diverso rispetto alla configurazione di cappelli del rappresentante privilegiato.

E' facile convincersi che, dal secondo in poi, tutti si salvano: ogni nano, poiché conosce il rappresentante privilegiato, è in grado di ricostruire se è uno dei nanetti con colore del cappello errato oppure no e di agire di conseguenza".

Il che, funziona bene anche con un numero qualsiasi (finito) di colori.. :O

[modalità mne on]
Della versione infiniti prigionieri e 2 cappelli mi piace più la soluzione con l'ultrafiltro (che comunque richiede l'assioma della scelta e non è molto dissimile come soluzione a quella di prima):

Sia $s_{n} \equiv \sum_{k=2}^n x_k$ modulo $2$ dove $x_k =0$ se il $k$-esimo cappello è nero mentre $x_k=1$ se esso è bianco. $s_n$ è una successione a valori in $\{0,1\}$ e quindi posso prendere il limite lungo un ultrafiltro non principale (su $\mathbb{N}$; esso dipende solo dalla successione da un certo punto in poi. Sia $l$ questo limite e diciamo che il primo condannato dice $l$. A questo punto il secondo condannato vede solo i cappelli dal $3$ in poi e quindi sa che $s_n=x+s'_n$ dove $x$ è il suo cappello e $s'_n$ è la somma di tutti i cappelli che vede fino all'n-esimo. Prendendo il limite lungo lo stesso ultrafiltro di questa successione ottengo $l=x+l'$ da cui posso ricavare chi è $x$.

Allo stesso modo fanno gli altri. In questo modo posso risolvere il problema se ho una quantità non numerabile di colori, perché li indicizzo con $\mathbb{R} / \mathbb{Z}$ (in pratica faccio i reali mod 1) e poi li sommo e succede la stessa cosa.
[modalità mne off]