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.^[1]

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.^[2]

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

A proposición a demostrar é P.
Supoñemos que P é falso, é dicir, asumimos ¬P.
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.
Dado que asumir que P é falsa leva a unha contradición, conclúese que P é verdadeira.

Formalización[editar | editar a fonte]

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

{\cfrac {\vdash \lnot \lnot P}{\vdash P}}

que podemos ler como: "Se demostramos $\lnot \lnot P$ , daquela podemos concluír $P$ ".

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

\Gamma ,\lnot \lnot P\vdash P,\Delta

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

Xustificación[editar | editar a fonte]

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	$\negp$	$\neg\negp$	$\neg\negp \Rightarrow p$
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:

se P se cumpre, logo P cúmprese.
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:

{\cfrac {{\cfrac {{\cfrac {\ }{\Gamma ,P\vdash P,\Delta }}\;(I)}{\Gamma ,\vdash \lnot P,P,\Delta }}\;({\lnot }R)}{\Gamma ,\lnot \lnot P\vdash P,\Delta }}\;({\lnot }L)

Relación con outras técnicas de proba[editar | editar a fonte]

Refutación por contradición[editar | editar a fonte]

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

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

Comparamos coa proba por contradición xa comentada enriba:

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

Principio do terceiro excluído[editar | editar a fonte]

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[editar | editar a fonte]

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[editar | editar a fonte]

Elementos de Euclides[editar | editar a fonte]

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

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[editar | editar a fonte]

Se

f_{1},\ldots ,f_{k}

son polinomios con

n

indeterminados con coeficientes complexos, que non teñen ceros comúns, daquela existen polinomios

g_{1},\ldots ,g_{k}

tal que

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

Hilbert demostrou a afirmación supoñendo que non existen tales polinomios $g_{1},\ldots ,g_{k}$ e derivou unha contradición.^[4]

Infinidade de primos[editar | editar a fonte]

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:^[5]

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[editar | editar a fonte]

Irracionalidade da raíz cadrada de 2[editar | editar a fonte]

A proba clásica de que a raíz cadrada de 2 é irracional é unha refutación por contradición.^[6] Debemos probar a negación ¬ ∃ a, b ∈ $\mathbb {N}$ tal que a/b = √2 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[editar | editar a fonte]

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.