Matematica Discreta I Lezione del giorno 31 ottobre 2007

(1)

Matematica Discreta I

Lezione del giorno 31 ottobre 2007

Vediamo un’applicazione del principio di induzione al calcolo del numero dei sottoinsiemi di un insieme finito:

Teorema. Il numero dei sottoinsiemi di un insieme finito non vuoto di cardinalità n è 2

ⁿ

. Dimostrazione:

Si tratta di applicare il principio di induzione al predicato:

P(n)=”Il numero dei sottoinsiemi di un insieme finito non vuoto di cardinalità n è 2

ⁿ

” per dimostrare che tale predicato é vero per ogni valore naturale di n.

Basta verificare le 2 ipotesi a),b) del principio di induzione:

a) P(1) è vero, perché il numero dei sottoinsiemi di un insieme finito non vuoto A di cardinalità 1 è 2

¹

(i sottoinsiemi sono infatti solo , A)

b) Se per un certo valore di n supponiamo vero P(n)=”Il numero dei sottoinsiemi di un insieme finito non vuoto di cardinalità n è 2

ⁿ

”, dimostriamo che è vero anche P(n+1)=”il numero dei sottoinsiemi di un insieme finito non vuoto di cardinalità (n+1) è 2

ⁿ⁺¹

” .

Dato l’insieme finito non vuoto A di cardinalità (n+1), fissiamo un elemento a A e consideriamo l’insieme B=A-{a} di cardinalità n. Per contare i sottoinsiemi di A, li dividiamo in 2 categorie:

1. I sottoinsiemi di A che non contengono l’elemento a 2. I sottoinsiemi di A che contengono l’elemento a

Quelli della categoria 1 non sono altro che i sottoinsiemi di B, quindi per ipotesi sono in numero di 2

ⁿ

. Quelli della categoria 2 si ottengono ciascuno prendendone uno della categoria 1 e inserendo nel sottoinsieme l’elemento a, quindi sono anch’essi in numero di 2

ⁿ

. In totale i sottoinsiemi di A sono in numero di 2

ⁿ

+2

ⁿ

=2

ⁿ⁺¹

, quindi anche P(n+1) è vero, come si voleva.

Si conclude, applicando il principio di induzione, che P(n) è vero per ogni valore naturale n, e si ottiene la tesi del teorema.

Divisione fra i numeri naturali.

E’ ben noto che, dati 2 numeri interi positivi, si possa “dividere” il primo (dividendo) per il secondo (divisore) trovando un “quoziente” e un “resto”.

Dimostreremo formalmente tale proprietà:

Teorema dell’algoritmo della divisione.

Comunque dati 2 numeri naturali a,b (detti rispettivamente “dividendo” e “divisore”), esistono due numeri interi q,r0 (detti rispettivamente ”quoziente” e “resto”) tali che a=bq+r con r<b.

Inoltre q,r sono unici.

Dimostrazione:

Dimostrazione dell’esistenza di q,r: si consideri l’insieme di tutte le differenze della forma a-bx, con x che varia fra gli interi 0, limitandosi a quelle differenze che danno un risultato 0:

S = { z / z=a-bx, con x intero 0, e con z 0 }

L’insieme S è non vuoto: almeno la differenza a-b0=a è elemento di S.

In S esiste un minimo: infatti se S non contiene 0 , tutti i suoi elementi sono numeri naturali e basta applicare l’Assioma del minimo; se invece S contiene 0, è proprio 0 il minimo in S.

Chiamiamo r il minimo in S. Per costruzione di S si ha che r è un intero 0, inoltre r=a-bx con x

intero 0. Da cui a=bx+r, e basta scegliere q=x per avere l’esistenza di q ed r. Resta però da

verificare che r<b: se per assurdo fosse rb, si avrebbe r-b0, r-b=(a-bq)-b=a-b(q+1), con q+10

(perché q=x0) dunque il numero r-b sarebbe una delle differenze che appartengono ad S; ma si

avrebbe anche r-b<r (perché b>0), contraddizione perché r è il minimo in S.

(2)

Dimostrazione dell’unicità di q,r: se a=bq+r=bq

1

+r

1

(con q,r,q

1

,r

1

interi 0 e con r<b, r

1

<b) le tesi sono che r=r

1

, q=q

1

.

Tesi r=r

1

: se per assurdo fosse rr

1

, e se per esempio fosse r>r

1

(se è al contrario r<r

1

si ragiona in modo simile) si avrebbe r-r

1

>0, r-r

1

=b(q

1

-q), dunque q

1

-q>0, ossia q

1

-q1, r-r

1

=b(q

1

-q)b; ma si ha anche rr-r

1

=b(q

1

-q)b , contraddizione perché r<b.

Tesi q=q

1

: avendo già dimostrato la prima tesi, si ha bq=a-r=a-r

1

=bq

1

, dunque q=q

1