Proba por contradición

En lóxica,a proba por contradición é unha forma de proba que establece a verdade ou a validez dunha proposición, demostrando que asumir a proposición como falsa leva a unha contradición. Aínda que se usa con bastante liberdade nas demostracións matemáticas, non todas as escolas de pensamento matemático aceptan este tipo de probas non construtivas como universalmente válidas.

De forma máis ampla, a proba por contradición é calquera forma de argumento que establece un enunciado chegando a unha contradición, aínda que o suposto inicial non sexa a negación do enunciado que se quere demostrar. Neste sentido xeral, a proba por contradición tamén se coñece como proba indirecta ou redución ao absurdo.

Unha demostración matemática que emprega a proba por contradición normalmente procede do seguinte xeito:

1. A proposición a demostrar é P.
2. Supoñemos que P é falso, é dicir, asumimos ¬P.
3. Demostramos logo que ¬P implica falsidade. Isto normalmente conséguese derivando dúas afirmacións mutuamente contraditorias, Q e ¬Q, e apelando ao principio da non contradición.
4. Dado que asumir que P é falsa leva a unha contradición, conclúese que P é verdadeira.

Formalización

O principio pódese expresar formalmente como a fórmula proposicional ¬¬P ⇒ P, equivalentemente (¬P ⇒ ⊥) ⇒ P, que se pode ler como: "Se asumir que P é falsa implica falsidade, entón P é verdadeira".

Na dedución natural o principio toma a forma da regra de inferencia seguinte

$\frac{⊢\mathrm{\neg }\mathrm{\neg }P}{⊢P}$

que podemos ler como: "Se demostramos $\mathrm{\neg }\mathrm{\neg }P$, daquela podemos concluír $P$".

No cálculo de secuentes o principio exprésase pola secuencia

$\mathrm{\Gamma },\mathrm{\neg }\mathrm{\neg }P⊢P,\mathrm{\Delta }$

que podemos ler como: “As hipóteses $\mathrm{\Gamma }$ e $\mathrm{\neg }\mathrm{\neg }P$ implican a conclusión $P$ ou $\mathrm{\Delta }$."

Xustificación

Na lóxica proposicional o principio pódese xustificar escribindo a táboa de verdade da proposición ¬¬P ⇒ P, que demostra que é unha tautoloxía:

p	Modelo:Math	Modelo:Math	Modelo:Math
T	F	T	T
F	T	F	T

Outra forma de xustificar o principio é derivalo ao principio do terceiro excluído, isto é, asumimos ¬¬P e procuramos demostrar P. Pola lei do terceiro excluído P cúmprese ou non se cumpre:

1. se P se cumpre, logo P cúmprese.
2. se ¬P se cumpre, daquela demostramos falsidade aplicando ao principio da non contradición a ¬P e ¬¬P, o que nos permite concluír P.

En calquera caso, establecemos P . Resulta que, pola contra, a proba por contradición pódese utilizar para derivar a lei do medio excluído.

No cálculo de secuentes a proba por contradición derívase das regras de inferencia para a negación:

$\frac{\frac{\frac{}{\mathrm{\Gamma },P⊢P,\mathrm{\Delta }}(I)}{\mathrm{\Gamma },⊢\mathrm{\neg }P,P,\mathrm{\Delta }}(\mathrm{\neg }R)}{\mathrm{\Gamma },\mathrm{\neg }\mathrm{\neg }P⊢P,\mathrm{\Delta }}(\mathrm{\neg }L)$

Relación con outras técnicas de proba

Refutación por contradición

Sería similar mais usada para probar unha negación en vez dunha afirmación

1. A proposición a demostrar é ¬P.
2. Supoñemos P.
3. Demostramos a falsidade de P.
4. Por tanto temos ¬P .

Comparamos coa proba por contradición xa comentada enriba:

1. A proposición a demostrar é P.
2. Supoñemos ¬P.
3. Demostramos a falsidade de ¬P.
4. Por tanto temos P.

Principio do terceiro excluído

A proba por contradición equivale ao principio do terceiro excluído formulada por primeira vez por Aristóteles.

A é verdadeiro ou é falso, non hai unha terceira posibilidade: A v ¬A

Principìo da non contradición

O principio da non contradición foi declarado por primeira vez como un principio metafísico por Aristóteles.

A non pode ser A e non-A ao mesmo teempo: ¬(A ∧ ¬A)

Exemplos de probas por contradición

Elementos de Euclides

Unha aparición temperá da proba por contradición pódese atopar nos Elementos de Euclides, Libro 1, Proposición 6:

Se nun triángulo dous ángulos son iguais, entón os lados opostos aos ángulos iguais tamén son iguais.

A demostración procede asumindo que os lados opostos non son iguais, e deriva unha contradición.

Teorema dos ceros de Hilbert

Se $f_1,\dots ,f_k$ son polinomios con Modelo:Mvar indeterminados con coeficientes complexos, que non teñen ceros comúns, daquela existen polinomios $g_1,\dots ,g_k$ tal que $f_1{g}_1+\dots +f_k{g}_k=1.$

Hilbert demostrou a afirmación supoñendo que non existen tales polinomios $g_1,\dots ,g_k$ e derivou unha contradición.

Infinidade de primos

O teorema de Euclides afirma que hai infinitos números primos. No tratado Elementos de Euclides o teorema aparece no Libro IX, Proposición 20:

Os números primos son máis que calquera multitude asignada de números primos.Considere calquera lista finita de números primos p₁ , p₂, ... , p_n. Imos mostrar que existe polo menos un número primo adicional que non figura nesta lista. Sexa P o produto de todos os números primos da lista: P = p₁p₂ ... p_n. Sexa q = P + 1. Entón q pode ser primo ou non:

• Se q é primo, é un primo máis que non está na lista.
• Se q non é primo, entón algún factor primo p divide q. Se este factor p estivese na nosa lista, entón dividiría P (xa que P é o produto de todos os números da lista); pero p tamén divide a P + 1 = q, como acabamos de dicir. Se p divide a P e tamén a q, entón p tamén debe dividir a diferenza  dos dous números, que é (P + 1) − P = 1. Como ningún número primo divide a 1, p non pode estar na lista. Isto significa que hai polo menos un número primo máis que non é dos da lista.

Exemplos de refutacións por contradición

Irracionalidade da raíz cadrada de 2

A proba clásica de que a raíz cadrada de 2 é irracional é unha refutación por contradición. Debemos probar a negación ¬ ∃ a, b ∈ $\mathbb{N}$ tal que a/b = Modelo:Sqrt supoñendo que existen números naturais a e b cuxa razón é a raíz cadrada de dous, e deriva unha contradición.

Proba por descenso infinito

A proba por descenso infinito é un método de demostración polo que se mostra que un obxecto máis pequeno coa propiedade desexada non existe:

• Supoña que hai un obxecto máis pequeno coa propiedade desexada.
• Demostrar que existe un obxecto aínda máis pequeno coa propiedade desexada, derivando así unha contradición.

Véxase tamén

Bibliografía

• Modelo:Cita libro

Outros artigos

• Principio do terceiro excluído
• Principio da non contradiction
• Proba do descenso infinito
• Modus tollens

Ligazóns externas

• Proof by Contradiction from Larry W. Cusick's How To Write Proofs
• Reductio ad Absurdum Internet Encyclopedia of Philosophy; ISSN 2161-0002

Modelo:Control de autoridades