Proba por contradición

probar que non é certo o contrario do que queremos probar

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:

  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

editar

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

 

que podemos ler como: "Se demostramos  , daquela podemos concluír  ".

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

 

que podemos ler como: “As hipóteses   e   implican a conclusión   ou  ."

Xustificación

editar

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 ¬p ¬¬p ¬¬p ⇒ 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:

  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:

 

Relación con outras técnicas de proba

editar

Refutación por contradición

editar

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

editar

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

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

Elementos de Euclides

editar

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
Se   son polinomios con n indeterminados con coeficientes complexos, que non teñen ceros comúns, daquela existen polinomios   tal que  

Hilbert demostrou a afirmación supoñendo que non existen tales polinomios   e derivou unha contradición.[4]

Infinidade de primos

editar

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 p1 , p2, ... , pn. 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 = p1p2 ... pn. 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

Irracionalidade da raíz cadrada de 2

editar

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 ∈   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

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.
  1. Bishop, Errett 1967. Foundations of Constructive Analysis, New York: Academic Press. ISBN 4-87187-714-0
  2. "Reductio ad absurdum | logic". Encyclopedia Britannica (en inglés). Consultado o 2019-10-25. 
  3. "Euclid's Elements, Book 6, Proposition 1". Consultado o 2 October 2022. 
  4. Hilbert, David (1893). Ueber die vollen Invariantensysteme. Mathematische Annalen 42. pp. 313–373. doi:10.1007/BF01444162. 
  5. "Euclid's Elements, Book 9, Proposition 20". Consultado o 2 October 2022. 
  6. Alfeld, Peter (16 August 1996). "Why is the square root of 2 irrational?". Understanding Mathematics, a study guide. Department of Mathematics, University of Utah. Arquivado dende o orixinal o 31 de decembro de 2023. Consultado o 6 February 2013. 

Véxase tamén

editar

Bibliografía

editar

Outros artigos

editar

Ligazóns externas

editar