ETC esercizio sugli insiemi non numerabili
Salve ragazzi, trovo difficoltà con questo esercizio.
Dimostrare che l' insieme di tutte le stringhe di lunghezza infinita sull' alfabeto{a,b,c} risulta non numerabile.
Per dimostrare che un insieme non è numerabile bisogna usare la diagonalizzazione , oppure mettere in relazione biunivoca l' insieme con quello dei numeri reali R.Quindi devo scrivere che :
{a,b,c}^0 = insieme vuoto;
{a,b,c}^1= {a,b,c};
{a,b,c}^2={ab,ac,bc,ba,ca,cb};
E cosi via , per tutti i numeri naturali, però come concludo la dimostrazione??
Dimostrare che l' insieme di tutte le stringhe di lunghezza infinita sull' alfabeto{a,b,c} risulta non numerabile.
Per dimostrare che un insieme non è numerabile bisogna usare la diagonalizzazione , oppure mettere in relazione biunivoca l' insieme con quello dei numeri reali R.Quindi devo scrivere che :
{a,b,c}^0 = insieme vuoto;
{a,b,c}^1= {a,b,c};
{a,b,c}^2={ab,ac,bc,ba,ca,cb};
E cosi via , per tutti i numeri naturali, però come concludo la dimostrazione??
Risposte
Esiste una relazione biunivoca tra il tuo insieme e l'insieme è [0, 3) dei numeri reali dato dalla rappresentazione ternaria dei numeri. Hai cioè che la tua stringa \( ( s_i )_{i \in \mathbb N} \mapsto \sum_{i=0}^{\infty} f(s_i)\,3^{-i} \) dove \(f\) è una qualsiasi biezione tra \(\{ a, b, c\}\) e \( \{0, 1, 2\}. \) Tale insieme è in biezione con l'insieme dei numeri reali e hai quindi dimostrato la tua tesi.
E se invece volessi usare la diagonalizzazione? Cosa dovrei fare?
Se ricordo bene, sono tutt'altro che un esperto in questo genere di argomenti, la dimostrazione segue la seguente idea.
Sia \(s_1, s_2, \dots\) una qualsiasi successione di stringhe di lunghezza infinita. Vogliamo dimostrare che esiste almeno un elemento nel tuo insieme che non è presente in questa successione. Per farlo creiamo una stringa \(s\) il cui carattere \(i-\)esimo differisce dal carattere \(i-\)esimo di \(s_i\). Possiamo per esempio scegliere una \(b\) se il valore era una \(a,\) una \(c\) se era una \(b\) e una \(a\) se era una \(c\). Questa stringa \(s\) non è nella successione perché differisce per almeno un carattere da ogni stringa nella successione. L'insieme non può quindi essere numerabile perché se lo fosse dovrebbe esistere una successione di stringhe contenente tutte le stringhe del tuo insieme, ma abbiamo appena dimostrato che non è possibile.
Sia \(s_1, s_2, \dots\) una qualsiasi successione di stringhe di lunghezza infinita. Vogliamo dimostrare che esiste almeno un elemento nel tuo insieme che non è presente in questa successione. Per farlo creiamo una stringa \(s\) il cui carattere \(i-\)esimo differisce dal carattere \(i-\)esimo di \(s_i\). Possiamo per esempio scegliere una \(b\) se il valore era una \(a,\) una \(c\) se era una \(b\) e una \(a\) se era una \(c\). Questa stringa \(s\) non è nella successione perché differisce per almeno un carattere da ogni stringa nella successione. L'insieme non può quindi essere numerabile perché se lo fosse dovrebbe esistere una successione di stringhe contenente tutte le stringhe del tuo insieme, ma abbiamo appena dimostrato che non è possibile.
Grazie mille per la spiegazione !! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo