Algebra lineare e geometria analitica/Dimostrazioni: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 9:
==Tecniche di Dimostrazione==
===Dimostrazione per Assurdo===
La ''dimostrazione per assurdo'' è una tecnica che si basa sull'equivalenza logica delle due forme <math>(p\rightarrow q)\
Un esempio potrebbe essere dimostrare che <math>\sqrt{2}</math> è irrazionale. Supponiamo, ''per assurdo'', che sia razionale, allora esistono <math>m</math> e <math>n</math> interi coprimi, tali che <math>\sqrt{2}={m\over n}</math> (il fatto che siano coprimi deriva dalla possibilità di scrivere ogni frazione "in forma ridotta"); eleviamo al quadrato: otteniamo che <math>2={m^2/over n^2}</math>, ovvero che <math>m^2=2\cdot n^2</math>; ma allora <math>m^2</math> è pari, e anche <math>m</math> sarà pari (se il quadrato di un numero è pari, anche il numero di cui è quadrato è pari: ogni quadrato contiene, nella sua fattorizzazione, ogni esponente pari); quindi possiamo scrivere <math>m=2h</math> e, sostituendo a <math>m^2</math> il termine <math>(2h)^2=4h^2</math> otteniamo che <math>4h^2=2n^2</math> ovvero che <math>n^2=2h^2</math> (siamo nel campo <math>\mathbb{Q}</math>, quindi possiamo dividere entrambi i membri per <math>2</math>). Ma da questo otteniamo che anche <math>n^2</math> è pari, e quindi anche </math>n</math> è pari, ma allora <math>m</math> e <math>n</math> non sono coprimi come avevamo ipotizzato, e quindi <math>\sqrt{2}</math> è irrazionale (non potendosi scrivere come <math>{m\over n}</math> per opportuni <math>m,n\in\mathbb{Z}</math> coprimi).<br>
===Induzione===
Un altro procedimento molto usato per dimostrare una proposizione fa uso del ''principio di induzione'' (completa o trascendete).<br>
Il principio di induzione completa può essere espresso in più forme, ora useremo questa: intanto, consideriamo un predicato (cioè, una proposizione contenente una variabile, la cui verità è legata al valore assunto dalla variabile) <math>\mathcal{P}(m)</math>, con <math>m</math> che varia in <math>\mathbb{N}</math>, allora vale che "''se <math>\mathcal{P}(0)</math> è vera ('''passo base'''), e se, per ogni <math>n\in\mathbb{N}</math>, assunta vera <math>\mathcal{P}(n)</math> (ipotesi induttiva) allora è vera anche <math>\mathcal{P}(n+1)</math> ('''passo induttivo'''), allora <math>\mathcal{P}(m)</math> è vera per ogni intero naturale <math>n</math>''". Praticamente, il fatto che <math>\mathcal{P}(0)</math> sia vera insieme al fatto che <math>\forall n\in\mathbb{N},\mathcal{P}(n)\rightarrow\mathcal{P}(n+1)</math> ci assicura che anche <math>\mathcal{P}(1)</math> sia vera (basta prendere <math>n=0</math>), quindi con lo stesso ragionamente anche <math>\mathcal{P}(2)</math> sarà vera, quindi <math>\mathcal{P}(3)</math>, eccetera, arrivando a dimostrare che il predicato è vero per ogni valore della variabile. Ovviamente, entrambi i passi vanno dimostrati: esistono predicati induttivi (cioè, per cui è verificato il passo induttivo) che non sono però vere, o lo sono solo definitivamente (nel senso, si prova il passo base per un valore <math>m>0</math>: in questo caso, il predicato sarà vero per ogni <math>n\geq m</math>).<br>
Un esempio classico è la dimostrazione che <math>\forall n\in\mathbb{N},\
===Principio dei Cassetti===
Il Principio dei Cassetti è un principio piuttosto intuitivo, che afferma che se abbiamo <math>n+1</math> oggetti da disporre in <math>n</math> posti, ci sarà almeno un posto in cui andranno messi almeno due oggetti (questi oggetti possono essere, per esempio, piccioni da mettere in delle gabbie, da cui il nome inglese di ''pigeonhole'', o calzini da mettere nei cassetti, da cui appunto il nome di ''principio dei cassetti''). Ovviamente, anche in questo caso sono possibili generalizzazioni.<br>
Può essere utile per gestire alcune situazioni: un esempio di dimostrazione semplice con il principio dei cassetti è per esempio la dimostrazione di questo problema: ''ci sono <math>n</math> ragazzi che vanno sedersi ad un tavolo, e una volta accomodatisi si accorgono che erano stati posizionati dei sognaposto: parlando tra di loro, notano che nessuno ha avuto la fortuna di ritrovarsi al posto assegnatoli; dimostrare che è possibile ruotare il tavolo in modo che almeno due ragazzi si ritrovino davanti il cartellino col proprio nome'': usando il principio dei cassetti, dove gli oggetti da posizione sono i cartellini da mettere davanti ai ragazzi col rispettivo nome, si vede che, delle <math>n</math> possibili configurazioni, una non associa nessun nome al rispettivo ragazzo, perciò ce ne sarà almeno una che associa almeno due nomi e due ragazzi.
[[en:Proofs:Algebra]]</math>
| |||