Definizione

Si dice che due insiemi A e B hanno la stessa potenza (hanno la stessa cardinalità) se

 esiste una funzione biettiva    f : A®B

Indicata con r_card la relazione tra insiemi "avere la stessa cardinalità", è facile vedere che si tratta di una relazione di equivalenza:

A r_card A dato che id_A : A®A è biettiva

se A r_card B      $f : A®B   biettiva        f ^-1: B ®A biettiva   B r_card A

se A r_card B   e   B r_card C        $f : A®B   e   $g : B®C biettive       g_°f: A®C biettiva    A r_card C

La classe di equivalenza modulo r_card di un insieme A è [A]_rcard ={ X / A r_card X }={ X / $f : A®X biettiva}e si indica con Card(A) oppure con | A | e si chiama potenza (cardinalità) di A

[A]_rcard = Card(A) = | A | = { X / $f : A®X biettiva}

Dal teorema del rappresentante,

A e B hanno la stessa potenza | A | = | B |

Definizione

Un insieme A si dice finito se

A = f  oppure $nÎN* /   | A | = |{1, 2, ... , n }|

Un insieme si dice infinito se non è finito

• Contare gli elementi di un insieme finito A significa stabilire una corrispondenza biunivoca tra A e un sottoinsieme di N del tipo {1, 2, ... , n } e quindi posso scrivere A ={a₁, a₂, ... , a_n }

• Invece di | A | = |{1, 2, ... , n }|, si scrive più semplicemente | A | = n

• |f | = 0 ???

• Per indicare che un insieme A è finito si può scrivere | A | < +¥

Proposizione ?

Un insieme A è finito se e solo se ogni funzione f : A®B iniettiva è anche suriettiva

Dim.

Proposizione ?

Un insieme A è finito se e solo non esiste una biiezione tra A e una sua parte propria

Dim.

Corollario

N è infinito

Basta esibire una biiezione y  tra N e una sua parte propria, ad esempio ponendo y(n) = n² . Evidentemente {n², nÎN}è strettamente contenuto in N.

Non è certo questa l'unica biiezione tra N e una sua parte propria. Si poteva anche porre y(n) = kn con kÎN*

Definizione

Un insieme A si dice numerabile se

| A | = | N |

• Se A è numerabile si può dunque scrivere A ={a₀, a₁, ... , a_n, ...}

• Non fa alcuna differenza scrivere A ={a₁, a₂, ... , a_n, ...}, dato che | N | = | N* |. Una possibile biiezione y: N®N* si ottiene ponendo y(n) = n+1

Definizione

Un insieme A ha potenza (cardinalità) minore o uguale a quella di un insieme B, e si scrive | A | £ | B |, se

 esiste una funzione iniettiva f : A®B

• Se | A | £ | B |    e    | A | ¹ | B |   scriveremo   | A | < | B |

Proposizione

Dato un insieme finito A con | A | = n, allora | P(A) | = 2ⁿ

Dim.

Procediamo per induzione su n.

Sia  U = { nÎN / | P(A) | = 2ⁿ "A : | A | = n}

0ÎU , infatti da  A = f  segue | A | = 0, P(A) = { f },  | P(A) | = 1 ed è anche 2⁰ = 1

Supponiamo ora, per ipotesi induttiva, che   | A | = n     | P(A) | = 2ⁿ e sia B un insieme tale che | B | = n+1. Fissiamo un elemento qualsiasi bÎB (esiste certamente un elemento bÎB, perchè n+1>0) e consideriamo l'insieme B \ {b}. Dato che | B \ {b} | = n, per l'ipotesi induttiva, risulta   | P( B \ {b}) | = 2ⁿ .

Ma che insieme è P( B \ {b}) ? Si tratta dei sottoinsiemi di B che non contengono l'elemento b. Per avere P( B ) basta aggiungere i rimanenti sottoinsiemi di B, ossia quelli che contengono b e questi si possono ottenere aggiungendo b ...

Q.E.D.

Proposizione (Regola della somma)

Dati due insiemi finiti A e B tali che | A | = n, | B | = m e AÇB = f ,  allora

| AÈB | = | A | + | B | = n + m

Dim.

Essendo | A | = n e | B | = m, possiamo scrivere A ={a₁, a₂, ... , a_n}e B ={b₁, b₂, ... , b_m}

Essendo AÇB = f, sarà AÈB  ={a₁, a₂, ... , a_n, b₁, b₂, ... , b_m}

Per dimostrare che |{a₁, a₂, ... , a_n, b₁, b₂, ... , b_m}| = n + m, devo esibire una funzione biiettiva f : AÈB ®{1, 2, ... , n+m}

Basta porre f (a_i) = i e f (b_j) = n+j. Nella figura che segue è indicata la numerazione conseguente ad f

Dimostriamo che f  è biiettiva ...

Proposizione (Regola del prodotto)

Dati due insiemi finiti A e B con | A | = n, | B | = m allora

| AÇB | = | A |·| B | = n·m

Dim.

Essendo | A | = n e | B | = m, possiamo scrivere A ={a₁, a₂, ... , a_n}e B ={b₁, b₂, ... , b_m}

Devo ora esibire una funzione biettiva f : AÇB ®{1, 2, ... , n·m}. Possiamo, ad esempio, porre  f (a_i , b_j) = ( j - 1)n + i

Prima di dimostrare che f è biiettiva, cerchiamo di capire da dove nasce l'idea di questa definizione.

Graficamente il prodotto cartesiano AÇB si può rappresentare nel seguente modo mediante un array bidimensionale

Per passare da questo array bidimensionale a un array monodimensionale, l'idea è di prendere gli elementi per righe

e quindi disporre le righe in un array unidimensionale

Dopo questa parentesi, dimostriamo finalmente che la funzione f : AÇB ®{1, 2, ... , n·m} definita da  f (a_i , b_j) = ( j - 1)n + i è biiettiva.

Se  f (a_i , b_j) = f (a_h , b_k ) , allora ( j - 1)n + i =   ( k - 1)n + h  e quindi (  j - k )n + i - h  =  0 . Dovendo valere per ogni n, deve essere i =  h e j =  k, da cui (a_i , b_j) = (a_h , b_k ) e quindi la funzione è iniettiva.

Q.E.D.

Proposizione (Regola della potenza)

Dati due insiemi  A e B con AÇB = f  e un insieme R ¹ f ,  allora

| R^A ´ R^B | = | R^AÈB |

Dim.

Una possibile biiezione y : R^A ´ R^B ® R^AÈB è definita ponendo "( f, g)ÎR^A ´ R^B

y (( f, g)) = h

con hÎR^AÈB definita da

La definizione di h è ben posta perchè AÇB = f.

Sia ora f : R^AÈB ® R^A ´ R^B  definita ponendo"hÎR^AÈB

f (h) = ( f, g)

con fÎR^A   e   gÎR^B definite da

f(x) = h(x)  "xÎA

g(x) = h(x)  "xÎB

Le definizioni di f e h sono ben poste perchè AÇB = f.

Verifichiamo ora che f °y : R^A ´ R^B ® R^A ´ R^B è la funzione identica su R^A ´ R^B e che y _°f : R^AÈB ® R^AÈB è la funzione identica su R^AÈB

"( f, g)ÎR^A ´ R^B   ( f _° y ) (( f, g)) = f (y (( f, g))) = f (h) = ( f, g)

"hÎR^AÈB   ( y _°f ) ( h) = y (f (h)) = y (( f, g) ) = h

Q.E.D.

Proposizione

Dati due insiemi qualunque A e B  e due insiemi R ¹ f , S ¹ f  allora

| R^A ´ S^A | = |(R ´ S)^A|

| (R^A)^B | = |R ^A´B|

Dim.

Una possibile biiezione y : (R ´ S)^A ® R^A ´ S^A è definita ponendo "hÎ(R ´ S)^A

y (h) = ( p_{R °} h, p_{S °} h)

essendo p_R: (R ´ S) ® R  e  p_S: (R ´ S) ®S proiezioni:  p_R(r, s) = r    e     p_S(r, s) = s     rÎR     sÎS

Sia f : R^A ´ S^A ® (R ´ S)^A   definita ponendo "( f, g)ÎR^A ´ S^A

f (( f, g)) = h

con hÎ(R ´ S)^A definita da

h(x) = ( f(x), g(x))  "xÎA

Verifichiamo ora che f °y : (R ´ S)^A ® (R ´ S)^A è la funzione identica su (R ´ S)^A e che y _°f : R^A ´ S^A ® R^A ´ S^A è la funzione identica su R^A ´ S^A

"hÎ(R ´ S)^A   ( f _° y ) ( h) = f (y (h)) = f ((p_{R °} h, p_{S °} h )) = h

"( f, g)ÎR^A ´ R^B  ( y _°f ) (( f, g)) = y (f (( f, g))) = y (h) = (p_{R °} h, p_{S °} h )  = ( f, g)

Ma allora, per la caratterizzazione della funzione inversa ,  y   è biiettiva.

Q.E.D.