cardinalità (o potenza)

Indicata con |I| oppure NI, per gli insiemi finiti si identifica come il numero di elementi nell’insieme, mentre per gli insiemi infiniti vale che due insiemi hanno la stessa cardinalità o potenza quando esiste una corrispondenza biunivoca tra di loro, indipendentemente se uno sia o non sia il sottoinsieme dell’altro.

Esempio di insiemi infiniti con la stessa cardinalità: $\mathbb{N}=\text{numeri naturali}$ $\mathbb{P}=\text{insieme dei numeri pari}$ $F=\{(a,b)\in \mathbb{N}\times \mathbb{P}|b=2a\}$ $F$ è una corrispondenza biunivoca tra $\mathbb{N}$ e $\mathbb{P}$, quindi i due insiemi hanno la stessa quantità (non numero) di elementi, cioè la stessa cardinalità.

insieme numerabile

Un insieme (infinito) si definisce numerabile se si può definire una corrispondenza biunivoca con $\mathbb{N}$ (sta in biiezione con $\mathbb{N}$), cioè se ha la sua stessa cardinalità.

N.B.: Ogni sottoinsieme infinito di $\mathbb{N}$ è numerabile.

• Anche $\mathbb{N}\times \mathbb{N}$ è numerabile, uno dei metodi possibili per dimostrarlo è il metodo della coda di colomba (o dove tail).

concetto di cardinalità nelle codifiche di informazioni

• NI = NC codifica non ambigua e non ridondante: gli insiemi I e C hanno lo stesso numero di “parole” per codificare ogni tipo di informazioni presenti.
• NI > NC codifica ambigua: non ci sono abbastanza “parole” per codificare ogni tipo di informazioni presenti.
• NI < NC codifica ridondante: ci sono più “parole” di quante sono necessarie per codificare le informazioni presenti. Di per se non è negativa, anzi si usa per la correzione degli errori di trasmissione e per altri scopi, ma riduce l’efficienza.

Bisogna tendere a una codifica meno ridondante possibile.