In logica, la dimostrazione per contraddizione è una forma di dimostrazione che stabilisce la verità o la validità di una proposizione mostrando che assumere che la proposizione sia falsa porta a una contraddizione. Sebbene sia largamente utilizzata nelle dimostrazioni matematiche, non tutte le scuole di pensiero matematico accettano questo tipo di dimostrazione non costruttiva come universalmente valida.
Più in generale, la dimostrazione per contraddizione è qualsiasi forma di argomentazione che dimostri una proposizione giungendo a una contraddizione, anche quando l'assunzione iniziale non è la negazione della proposizione da dimostrare. In questo senso generale, la dimostrazione per contraddizione è anche nota come dimostrazione indiretta, dimostrazione per assunzione del contrario, e reductio ad impossibile.
Una dimostrazione matematica che impieghi la dimostrazione per contraddizione di solito procede come segue:
La proposizione da dimostrare è P . Si suppone che P sia falso, ossia che ¬P sia vero. Si dimostra quindi che ¬P implica una contraddizione. Ciò si ottiene tipicamente derivando due asserzioni reciprocamente contraddittorie, Q e ¬Q, e appellandosi al principio di non contraddizione. Poiché supporre che P sia falso porta a una contraddizione, si conclude che P è in realtà vero.
Un caso speciale importante è la dimostrazione d'esistenza per contraddizione: per dimostrare che un oggetto con una data proprietà esiste, deriviamo una contraddizione dall'assunzione che tutti gli oggetti soddisfino la negazione della proprietà.
Formalizzazione Il principio può essere formalmente espresso attraverso la formula proposizionale ¬¬ P ⇒ P o, equivalentemente, (¬ P ⇒ ⊥) ⇒ P, da leggersi: "Se presumere che P sia falso implica falsità, allora P è vero."
Nella deduzione naturale il principio prende la forma della regola di inferenza:
che recita: "Se è dimostrato, allora si può concludere ."
Nel calcolo dei sequenti il principio è espresso dalla seguente
che recita: "Ipotesi e comportano la conclusione o ."
Giustificazione Nella logica classica il principio può essere giustificato dall'esame della tabella di verità della proposizione ¬¬P ⇒ P, dalla quale si dimostra che si tratta di una tautologia: P ¬P ¬¬P ¬¬P ⇒ P V F V V F V F V Un altro modo per giustificare il principio è derivarlo dalla legge del terzo escluso, come segue. Avendo assunto ¬¬P si cerchi di dimostrare P. Per la legge del terzo escluso, P o è vera o non è vera:
se P è vera, allora ovviamente P è vera. se ¬P è vera, allora deriviamo la falsità applicando la legge di non contraddizione a ¬P e ¬¬P, dopodiché il principio di esplosione ci consente di concludere P.
In entrambi i casi, si è dimostrato P. Risulta che, al contrario, la dimostrazione per contraddizione può essere utilizzata per derivare la legge del terzo escluso.
Nel classico calcolo dei sequenti LK la dimostrazione per contraddizione può essere derivata dalle regole di inferenza per la negazione:
Relazione con altre tecniche di dimostrazione
Confutazione per contraddizione La dimostrazione per contraddizione è simile alla confutazione per contraddizione, nota anche come dimostrazione di negazione, che afferma che ¬P si dimostra come segue:
La proposizione da dimostrare è ¬P . Si suppone P. Si deriva la falsità. Si conclude ¬P .
Al contrario, la dimostrazione per contraddizione procede come segue:
La proposizione da dimostrare è P . Si suppone ¬P . Si deriva falsità. Si conclude P.
Formalmente queste non sono identiche, poiché la confutazione per contraddizione si applica solo quando la proposizione da dimostrare è negata, mentre la dimostrazione per contraddizione può essere applicata a qualsiasi proposizione. Nella logica classica, dove e possono essere liberamente scambiate, la distinzione è in gran parte oscurata. Pertanto, nella pratica matematica, entrambi i principi sono definiti "dimostrazione per contraddizione".
Legge del terzo escluso La dimostrazione per contraddizione è equivalente alla legge del terzo escluso, formulata per la prima volta da Aristotele, che afferma che o una proposizione o la sua negazione è vera, P ∨ ¬P .
Legge di non contraddizione Il principio di non contraddizione fu enunciato per la prima volta da Aristotele come principio metafisico. Esso postula che una proposizione e la sua negazione non possono essere entrambe vere, o, equivalentemente, che una proposizione non può essere sia vera che falsa. Formalmente, il principio di non contraddizione si scrive come ¬(P ∧ ¬P) e si legge come "non è possibile che una proposizione risulti sia vera sia falsa". Il principio di non contraddizione non segue né è implicato dal principio di dimostrazione per contraddizione.
I due principi di non contraddizione e del terzo escluso indicano che solo una tra P e ¬P è vera.
Dimostrazione per contraddizione nella logica intuizionista Nella logica intuizionista la dimostrazione per contraddizione non è generalmente valida, sebbene se ne possano ricavare alcuni casi particolari. Di contro, la dimostrazione di negazione e il principio di non contraddizione sono entrambi intuizionisticamente validi.
L'interpretazione di Brouwer-Heyting-Kolmogorov della dimostrazione per contraddizione fornisce la seguente condizione di validità intuizionistica: se non esiste un metodo per stabilire che una proposizione sia falsa, allora esiste un metodo per stabilire che la proposizione sia vera.[ chiarire ]
Se per "metodo" si intende un algoritmo, allora la condizione non è accettabile, poiché permetterebbe di risolvere il problema della terminazione. Per capire come, si consideri l'enunciato H(M) che afferma "la macchina di Turing M si ferma o non si ferma". La sua negazione ¬H(M) afferma che "M non si ferma né non si ferma", il che è falso per il principio di non contraddizione (che è intuizionisticamente valido). Se la dimostrazione per contraddizione fosse intuizionisticamente valida, otterremmo un algoritmo per decidere se una macchina di Turing arbitraria M si ferma, violando così la dimostrazione (intuizionisticamente valida) di non risolubilità del problema dell'arresto.
Una proposizione P che soddisfa si dice proposizione ¬¬-stabile. Pertanto, nella logica intuizionista, la dimostrazione per contraddizione non è universalmente valida, ma può essere applicata solo alle proposizioni ¬¬-stabili. Un esempio di proposizione siffatta è una proposizione decidibile, ovvero che soddisfa . In effetti, la dimostrazione di cui sopra, secondo cui il principio del terzo escluso implica una dimostrazione per contraddizione, può essere riproposta per dimostrare che una proposizione decidibile è ¬¬-stabile. Un tipico esempio di proposizione decidibile è un enunciato che può essere verificato tramite calcolo diretto, come " è primo" o " divide ".
Esempi di dimostrazioni per contraddizione
Gli Elementi di Euclide Uno dei primi esempi di dimostrazione per contraddizione si ritrova negli Elementi di Euclide, Libro 1, Proposizione 6:
Se in un triangolo due angoli sono uguali tra loro, allora anche i lati opposti agli angoli uguali sono uguali tra loro.
La dimostrazione procede assumendo che i lati opposti non siano uguali, e ne deriva una contraddizione. Analogamente, molte altre dimostrazioni successive negli Elementi di Euclide utilizzano la stessa strategia di dimostrazione, come la Proposizione 33 nel Libro 7:
Se si sommano il lato dell'esagono e quello del decagono inscritti nello stesso cerchio, l'intera retta è stata secata secondo il rapporto estremo e medio, e il suo segmento maggiore è il lato dell'esagono.
Nullstellensatz di Hilbert Una dimostrazione per contraddizione di grande impatto fu fornita da David Hilbert. Il suo Nullstellensatz afferma:
Se sono polinomi in n indeterminati con coefficienti complessi, che non hanno zeri complessi comuni, allora ci sono polinomi tali che
Hilbert dimostrò l'affermazione assumendo che non esistano i polinomi e ne derivò una contraddizione.
Infinità dei numeri primi Il teorema di Euclide afferma che esistono infiniti numeri primi. Questo teorema è enunciato nel Libro IX, Proposizione 20, degli Elementi di Euclide:
I numeri primi sono più di qualsiasi moltitudine di numeri primi assegnata.
A seconda di come si scrive formalmente l'enunciato di cui sopra, la tipica dimostrazione assume la forma di dimostrazione per contraddizione o di confutazione per contraddizione. Qui si presenta la prima, mentre più avanti si vedrà come la dimostrazione possa essere posta come confutazione per contraddizione.
Se si esprime formalmente il teorema di Euclide dicendo che per ogni numero naturale esiste un numero primo più grande di esso, allora si utilizza la dimostrazione per contraddizione, come segue.
Dato un qualunque numero , si cerchi di dimostrare che esiste un numero primo maggiore di . Si supponga al contrario che un tale p non esista (applicando la dimostrazione per contraddizione). Allora tutti i numeri primi sono minori o uguali a , e si potrebbe elencare tutti . Sia il prodotto di tutti i numeri primi e sia . Poiché è più grande di tutti i numeri primi, non è primo, quindi deve essere divisibile per uno di essi, diciamo Ora entrambi e sono divisibili per , quindi anche la loro differenza , ma questo non può essere perché 1 non è divisibile per nessun numero primo. Quindi abbiamo una contraddizione e perciò esiste un numero primo maggiore di .
Esempi di confutazioni per contraddizione Gli esempi seguenti sono comunemente considerati dimostrazioni per contraddizione, ma formalmente impiegano la confutazione per contraddizione (e quindi sono intuizionisticamente validi).
Infinità dei numeri primi Si torni di nuovo al teorema di Euclide – Libro IX, Proposizione 20:
I numeri primi sono più di qualsiasi moltitudine di numeri primi assegnata.
Si potrebbe interpretare la proposizione come se affermasse che per ogni elenco finito di numeri primi, esiste un altro numero primo non presente in quell'elenco, il che è probabilmente più vicino e nello stesso spirito della formulazione originale di Euclide. In tal caso, la dimostrazione di Euclide applica la confutazione per contraddizione a un solo passo, come mostrato di seguito.
Dato un elenco finito di numeri primi , si mostrerà che esiste almeno un numero primo aggiuntivo non presente in questo elenco. Sia il prodotto di tutti i numeri primi elencati e un fattore primo di , possibilmente stesso. Si vuole che non sia nell'elenco dei numeri primi dato. Si supponga al contrario che lo sia (applicando la confutazione per contraddizione). Allora dividerebbe sia sia , quindi anche la loro differenza, che è . Ciò dà luogo a una contraddizione, poiché nessun numero primo divide 1.
Irrazionalità della radice quadrata di 2 La dimostrazione classica del fatto che la radice quadrata di 2 sia irrazionale è una confutazione per contraddizione. In effetti, si poterebbe a dimostrare la negazione ¬ ∃ a, b ∈ . a/b = √ 2 supponendo che esistano i numeri naturali a e b il cui rapporto è la radice quadrata di due, e se ne deriva una contraddizione.
Dimostrazione per discesa infinita La dimostrazione per discesa infinita è un metodo di dimostrazione mediante il quale si dimostra che non esiste un oggetto minimale dotato della proprietà desiderata, come descritto nel seguito:
Supponiamo che esista un oggetto più piccolo con la proprietà desiderata. Dimostrare che esiste un oggetto ancora più piccolo con la proprietà desiderata, derivando così una contraddizione.
Tale dimostrazione è di nuovo una confutazione per contraddizione. Un esempio tipico è la dimostrazione della proposizione "non esiste un numero razionale positivo minimo": si supponga che esista un numero razionale positivo minimo q e si deduca una contraddizione osservando che è ancora più piccolo di q e comunque positivo.
Il paradosso di Russell