I riassunti , gli appunti i testi contenuti nel nostro sito sono messi a disposizione gratuitamente con finalità illustrative didattiche, scientifiche, a carattere sociale, civile e culturale a tutti i possibili interessati secondo il concetto del fair use e con l' obiettivo del rispetto della direttiva europea 2001/29/CE e dell' art. 70 della legge 633/1941 sul diritto d'autore
Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).
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 è 2n.
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 è 2n”
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 è 21 (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 è 2n”, dimostriamo che è vero anche P(n+1)=”il numero dei sottoinsiemi di un insieme finito non vuoto di cardinalità (n+1) è 2n+1” .
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:
Quelli della categoria 1 non sono altro che i sottoinsiemi di B, quindi per ipotesi sono in numero di 2n. 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 2n. In totale i sottoinsiemi di A sono in numero di 2n+2n=2n+1, 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.
Dimostrazione dell’unicità di q,r: se a=bq+r=bq1+r1 (con q,r,q1,r1 interi ³0 e con r<b, r1<b) le tesi sono che r=r1, q=q1 .
Tesi r=r1 : se per assurdo fosse r¹r1, e se per esempio fosse r>r1 (se è al contrario r<r1 si ragiona in modo simile) si avrebbe r-r1>0, r-r1=b(q1-q), dunque q1-q>0, ossia q1-q³1, r-r1=b(q1-q)³b; ma si ha anche r³r-r1=b(q1-q)³b , contraddizione perché r<b.
Tesi q=q1 : avendo già dimostrato la prima tesi, si ha bq=a-r=a-r1=bq1, dunque q=q1 .
Fonte: http://math.unipa.it/~difranco/documents/Lezione31.10.07_000.doc
Sito web da visitare: http://math.unipa.it
Autore del testo: non indicato nel documento di origine
Il testo è di proprietà dei rispettivi autori che ringraziamo per l'opportunità che ci danno di far conoscere gratuitamente i loro testi per finalità illustrative e didattiche. Se siete gli autori del testo e siete interessati a richiedere la rimozione del testo o l'inserimento di altre informazioni inviateci un e-mail dopo le opportune verifiche soddisferemo la vostra richiesta nel più breve tempo possibile.
I riassunti , gli appunti i testi contenuti nel nostro sito sono messi a disposizione gratuitamente con finalità illustrative didattiche, scientifiche, a carattere sociale, civile e culturale a tutti i possibili interessati secondo il concetto del fair use e con l' obiettivo del rispetto della direttiva europea 2001/29/CE e dell' art. 70 della legge 633/1941 sul diritto d'autore
Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).
"Ciò che sappiamo è una goccia, ciò che ignoriamo un oceano!" Isaac Newton. Essendo impossibile tenere a mente l'enorme quantità di informazioni, l'importante è sapere dove ritrovare l'informazione quando questa serve. U. Eco
www.riassuntini.com dove ritrovare l'informazione quando questa serve