Numerabilità di insiemi

Insiemi finiti e numerabili[modifica | modifica wikitesto]

Definizione 3.10

Supponiamo di avere un qualsiasi insieme . si dice finito se esiste un intero positivo e una funzione iniettiva e suriettiva. Altrimenti E si dice infinito.

 

Ad esempio, l'insieme è infinito.

Un insieme finito non può essere posto in corrispondenza biunivoca con un suo sottoinsieme proprio, perchè il sottoinsieme proprio ha un numero minore di elementi rispetto all'insieme. Al contrario un insieme infinito può essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio.

Ad esempio, l'insieme può essere messo in corrispondenza biunivoca con l'insieme dei numeri pari .
Definizione 3.11

Un insieme che può essere posto in corrispondenza biunivoca con gli interi positivi si chiama numerabile.

 

L'unione di infiniti insiemi numerabili è un insieme numerabile.

Gli insiemi numerabili sono infiniti, ma sono i piu' piccoli tra gli insiemi infiniti.
Teorema 3.1

Ogni insieme infinito contiene un insieme numerabile.

 
Dimostrazione

Dato un insieme infinito , prendo un elemento . Allora non può essere vuoto, altrimenti sarebbe formato da un solo elemento e non sarebbe infinito. Si prende un altro elemento dall'insieme , che chiamo con . L'insieme non è vuoto, altrimenti avrebbe solo due elementi e non sarebbe infinito. Posso prendere un altro elemento dall'insieme che chiamo ed è diverso dai precedenti. Si procede in questo modo scegliendo altri elementi .

Gli infiniti elementi scelti dell'insieme sono in corrispondenza biunivoca con gli interi. L'insieme contiene un'infinità numerabile, perchè il sottoinsieme degli elementi scelti è in corrispondenza biunivoca con i numeri interi.

 

Caratterizzazione degli insiemi infiniti[modifica | modifica wikitesto]

Teorema 3.2

Un insieme è infinito se e solo se può essere posto in corrispondenza biunivoca con un suo sottoinsieme proprio.

 
Dimostrazione

Sia infinito. Allora contiene un suo sottoinsieme numerabile e posso scrivere

Considero quindi la seguente corrispondenza: ad ogni elemento dell'insieme associo se stesso tramite l'identità. Nel secondo insieme invece considero la corrispondenza che a associa , a associa , a associa , , a associa , , in questo modo ho messo in corrispondenza biunivoca con il suo sottoinsieme

 

Insiemi equipotenti[modifica | modifica wikitesto]

Definizione 3.12

e si dicono avere la stessa cardinalità (o anche potenza) se e possono essere posti in corrispondenza biunivoca.

 

Se gli insiemi sono finiti e hanno la stessa cardinalità, allora hanno lo stesso numero di elementi.

L'"avere la stessa cardinalità" è una relazione di equivalenza: se ha la stessa cardinalità di e ha la stessa cardinalità di , allora ha la stessa cardinalità di .
Definizione 3.13

Si dice che la cardinalità di è maggiore della cardinalità di ( ha una potenza maggiore di ) se ha la stessa cardinalità di un sottoinsieme di ma e non hanno la stessa cardinalità.

 

Se i due insiemi sono finiti, avere cardinalità maggiore significa avere piu' elementi.

Potenza del numerabile[modifica | modifica wikitesto]

Definizione 3.14

Un insieme si dice numerabile se ha la stessa cardinalità degli interi.

 
Ad esempio, i razionali sono numerabili, mentre i reali non lo sono.
Teorema 3.3

Siano degli insiemi numerabili. Allora anche l'unione è numerabile. In altre parole, l'unione di un'infinità numerabile di insiemi è numerabile.

 
Dimostrazione

Denotiamo gli elementi dei vari insiemi con due indici: il primo indice indica l'insieme di appartenenza, il secondo indica il numero dell'elemento. Ad esempio,

Procedo in diagonale. Su ogni diagonale la somma degli indici degli elementi è uguale. Ad ogni numero naturale associo la diagonale dove la somma degli indici è uguale a .
Con l'ordinamento in diagonale riesco a porre in corrispondenza biunivoca tutti gli elementi dell'insieme con gli interi positivi o nulli. L'insieme costituito è numerabile.

 


Teorema 3.4

I razionali sono numerabili.

 
Dimostrazione

Consideriamo i razionali positivi , con , primi tra loro e . Ordiniamo i razionali positivi secondo la somma . Mettiamo in ordine crescente i numeri in cui è costante.

A parità di altezza ho ordinato i numeri in maniera crescente. In questo modo ho messo i razionali in corrispondenza biunivoca con gli interi positivi.

 

Se considero il prodotto cartesiano di insiemi numerabili, ho un insieme numerabile.

Teorema 3.5

Dati e numerabili, allora è numerabile.

 
Dimostrazione

Considero gli insiemi
Ognuno di questi insiemi è costituito da coppie dove la prima coordinata è fissa, mentre la seconda varia. Ognuno di questi insiemi è numerabile, quindi anche la loro unione è numerabile.

 

La costruzione si generalizza al prodotto cartesiano di insiemi numerabili, .

Ad esempio prendiamo tutti i punti del piano a coordinate razionali, l'insieme è numerabile.

Gli insiemi numerabili sono gli insiemi finiti di minor potenza, perchè un insieme infinito contiene sempre un sottoinsieme numerabile (come abbiamo già visto).

Potenza del continuo[modifica | modifica wikitesto]

Mostreremo che l'insieme ha potenza maggiore di quella dei numerabili e la sua cardinalità si chiama potenza del continuo.

Infatti si può dimostrare che i punti dell'intervallo non possono essere messi in corrispondenza biunivoca con gli interi.
Teorema 3.6

Ogni intervallo aperto contenuto in ha la stessa potenza di (può essere messo in corrispondenza biunivoca con ).

 


Esercizio 3.1

Considero la funzione che ad ogni associa . Verificare che per ogni il punto sta nell'intervallo . Dimostrare anche che la corrispondenza è suriettiva e iniettiva e quindi biunivoca.

 
Dimostrazione

Cerco una funzione della forma che mandi il punto in e in .

La funzione costruita è . Bisogna dimostrare che la funzione è contemporaneamente iniettiva e suriettiva.

Dimostro l'iniettività. Prendo due punti del dominio della funzione che chiamo nel dominio della funzione , con la proprietà che .

Divido per :
L'unica possibilità per cui è che , allora è iniettiva.
Dimostro la suriettività.

Una funzione è suriettiva se ogni elemento dell'insieme di arrivo ha una preimmagine, cioè se per ogni esiste un nel dominio tale che . Si deve avere

E' sempre possibile trovare un numero tale che questa condizione sia verificata.
Dimostriamo che appartiene a : infatti siccome , . Inoltre, verifico se , cioè
Moltiplico per
e quest'uguaglianza è evidente, allora,

 


Esercizio 3.2

Dimostrare che manda l'intervallo su tutto ed è iniettiva e suriettiva.

 
Dimostrazione

Dimostro l'iniettività:

Tesi:

Moltiplico ambo i membri per e .

  1. se , anche è necessariamente uguale a 0;
  2. se , allora il primo membro è . Affinchè anche il secondo membro sia maggiore o uguale a 0, anche dev'essere ; Si ottiene
  3. se , il primo membro è minore uguale a 0. Affinchè anche il secondo sia , allora . Si ottiene:

Dimostro la suriettività

Tesi:

Moltiplico per e porto al primo membro

  1. Se , allora
    Verifico che : ovviamente , inoltre, se vale
    si ha
    e quest'ultima disuguaglianza è vera.
  2. Se ,
    Verifico che :
    Inoltre, se vale
    si ha
    Quindi per ogni .

Allora è suriettiva e iniettiva, e quindi biunivoca.

 

I punti di possono essere messi in corrispondenza biunivoca con l'intervallo . I punti dell'intervallo non possono essere messi in corrispondenza biunivoca con gli interi, e quindi l'intervallo non è numerabile.

 PrecedenteSuccessivo