Cardinalità
Mi è venuto in mente il seguente quesito:
Qual è la cardinalità dell'insieme contenente tutte le parole possibili (anche senza senso)?
Nota. Le parole sono formate dalle lettere del nostro alfabeto.
Qual è la cardinalità dell'insieme contenente tutte le parole possibili (anche senza senso)?
Nota. Le parole sono formate dalle lettere del nostro alfabeto.
Risposte
In un alfabeto di $d$ lettere, puoi scrivere $d^n$ parole di lunghezza $n$. Il vocabolario è l'insieme \(\coprod_{n\ge 0} W^n\) ed ha cardinalità \(\sum d^n = 1+d+d^2+...\).
Chiaramente, se non metti un limite superiore alla lunghezza delle parole, tale numero è infinito; se invece lo metti (diciamo $N$), è quella somma troncata a $N$. E quella somma troncata a $N$, notoriamente, fa \(\frac{d^{N+1}-1}{d-1}\).
http://web.mclink.it/MK1027/BIOPARCO/DO ... babele.pdf
Chiaramente, se non metti un limite superiore alla lunghezza delle parole, tale numero è infinito; se invece lo metti (diciamo $N$), è quella somma troncata a $N$. E quella somma troncata a $N$, notoriamente, fa \(\frac{d^{N+1}-1}{d-1}\).
http://web.mclink.it/MK1027/BIOPARCO/DO ... babele.pdf
Possiamo considerare l'insieme $alpha={A,B,...,Z}$ dove non ho considerato $X,Y,W,J,K$ che chiaramente ha ventuno elementi e possiamo metterlo in corrispondenza biunivoca con $I_(21)$ ponendo $f:alpha->I_(21)$ definendo
${(A|-> 1),(B|-> 2),(...),(Z |-> 21):}$ considerando quindi $alpha={a_i | i in I_21}$ e $I_(21)={n inNN:1leqnleq21}$
ora possiamo definire 'parola di $n$' lettere un qualsiasi elemento di
dove poniamo magari $(x_1,...,x_k):=x_1x_2...x_k$ quindi per esempio $(a_1,a_2,a_3)=(A,B,C):=ABC$
è chiaro che se prendiamo $alpha^k$ tutte le parole possibili in questo insieme delle parole di lunghezza $k$ equivale alle disposizioni con ripetizioni di $21$ lettere a gruppi di $k$ nonché $|alpha^k|=D'_k=21^k$
pertanto se consideriamo quante possano essere tutte le parole di massima lunghezza $m$ avremo a che fare con la quantità
ho visto che Killing mi ha preceduto in maniera praticamente equivalente, ma ormai la posto.
${(A|-> 1),(B|-> 2),(...),(Z |-> 21):}$ considerando quindi $alpha={a_i | i in I_21}$ e $I_(21)={n inNN:1leqnleq21}$
ora possiamo definire 'parola di $n$' lettere un qualsiasi elemento di
$alpha^k=prod_(k)alpha:=underbrace(alphatimesalphatimes...timesalpha)_(k)={(x_1,...,x_k)|x_j inalpha}$
dove poniamo magari $(x_1,...,x_k):=x_1x_2...x_k$ quindi per esempio $(a_1,a_2,a_3)=(A,B,C):=ABC$
è chiaro che se prendiamo $alpha^k$ tutte le parole possibili in questo insieme delle parole di lunghezza $k$ equivale alle disposizioni con ripetizioni di $21$ lettere a gruppi di $k$ nonché $|alpha^k|=D'_k=21^k$
pertanto se consideriamo quante possano essere tutte le parole di massima lunghezza $m$ avremo a che fare con la quantità
$sum_(k=1)^(m)21^k=(21^(m+1)-1)/(20)$
ho visto che Killing mi ha preceduto in maniera praticamente equivalente, ma ormai la posto.
Domanda facile: nel caso in cui non ci sia limite di lunghezza per le parole contenute nell'insieme, esso risulta numerabile?
Detto $S$ l'insieme di tutte le parole componibili con alfabeto (anche infinite), considero $f :S-> NN$ che associa ad ogni parola un numero che è comosto dalla somma di cifre associate ad ogni lettera mediante la posizione $A->1$, ..., $Z->21$ intervallati da 0 in questo modo
$f(CANE)=301012050$
Una tale applicazione dovrebbe essere iniettiva e $S$ è numerabile
Può andare?
$f(CANE)=301012050$
Una tale applicazione dovrebbe essere iniettiva e $S$ è numerabile
Può andare?
Sì... andava bene pure se dicevi (se lo sapevi) che unione numerabile di insiemi finiti è numerabile. Infatti l'insieme preso in considerazione è unione disgiunta dei $W^n$ (che denota l'insieme delle parole formate da n lettere)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo