Prueba por contradicción

Prueba demostrando que la negación es imposible.

En lógica , la prueba por contradicción es una forma de prueba que establece la verdad o la validez de una proposición , al mostrar que asumir que la proposición es falsa conduce a una contradicción . Aunque se utiliza con bastante libertad en demostraciones matemáticas, no todas las escuelas de pensamiento matemático aceptan este tipo de demostración no constructiva como universalmente válida. ^[1]

En términos más generales, la prueba por contradicción es cualquier forma de argumento que establece un enunciado llegando a una contradicción, incluso cuando el supuesto inicial no es la negación del enunciado que se debe probar. En este sentido general, la prueba por contradicción también se conoce como prueba indirecta , prueba suponiendo lo contrario , ^[2] y reducción ad impossibile . ^[3]

Una prueba matemática que emplea prueba por contradicción suele proceder de la siguiente manera:

1. La proposición a demostrar es P .
2. Suponemos que P es falso, es decir, asumimos ¬P .
3. Luego se demuestra que ¬P implica falsedad. Esto generalmente se logra derivando dos afirmaciones mutuamente contradictorias, Q y ¬Q , y apelando a la ley de no contradicción .
4. Dado que asumir que P es falso conduce a una contradicción, se concluye que P es de hecho verdadero.

Un caso especial importante es la prueba de existencia por contradicción: para demostrar que un objeto con una propiedad determinada existe, derivamos una contradicción del supuesto de que todos los objetos satisfacen la negación de la propiedad.

Formalización

El principio puede expresarse formalmente como la fórmula proposicional ¬¬P ⇒ P , equivalentemente (¬P ⇒ ⊥) ⇒ P , que dice: "Si suponer que P es falso implica falsedad, entonces P es verdadero".

En la deducción natural el principio toma la forma de la regla de inferencia.

${\displaystyle {\cfrac {\vdash \lnot \lnot P}{\vdash P}}}$

que dice: "Si se prueba, entonces se podrá concluir". ${\displaystyle \lnot \lnot P}$ ${\displaystyle P}$

En cálculo secuente el principio se expresa por el secuente

${\displaystyle \Gamma ,\lnot \lnot P\vdash P,\Delta }$

que dice: "Las hipótesis y la conclusión conllevan o ". ${\displaystyle \Gamma }$ ${\displaystyle \lnot \lnot P}$ ${\displaystyle P}$ ${\displaystyle \Delta }$

Justificación

En lógica clásica, el principio puede justificarse mediante el examen de la tabla de verdad de la proposición ¬¬P ⇒ P , que demuestra que es una tautología :

Otra forma de justificar el principio es derivarlo de la ley del tercero excluido , de la siguiente manera. Suponemos ¬¬P y buscamos demostrar P . Por la ley del medio excluido P se cumple o no:

1. si P se cumple, entonces, por supuesto, P se cumple.
2. si ¬P se cumple, entonces derivamos la falsedad aplicando la ley de no contradicción a ¬P y ¬¬P , después de lo cual el principio de explosión nos permite concluir P.

En cualquier caso, establecimos P . Resulta que, a la inversa, la prueba por contradicción puede utilizarse para derivar la ley del tercero excluido.

En el cálculo secuencial clásico, la prueba por contradicción de LK se puede derivar de las reglas de inferencia para la negación:

${\displaystyle {\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 otras técnicas de prueba

Refutación por contradicción

La prueba por contradicción es similar a la refutación por contradicción , ^{[4] [5]} también conocida como prueba de negación , que establece que ¬P se demuestra de la siguiente manera:

1. La proposición a demostrar es ¬P .
2. Supongamos que P.
3. Derivar falsedad.
4. Concluye ¬P .

En cambio, la prueba por contradicción procede de la siguiente manera:

1. La proposición a demostrar es P .
2. Supongamos ¬P .
3. Derivar falsedad.
4. Concluye P.​

Formalmente no son lo mismo, ya que la refutación por contradicción se aplica sólo cuando se niega la proposición que se va a probar, mientras que la prueba por contradicción puede aplicarse a cualquier proposición. ^[6] En la lógica clásica, donde y pueden intercambiarse libremente, la distinción queda en gran medida oscurecida. Por tanto, en la práctica matemática, ambos principios se denominan "prueba por contradicción". ${\displaystyle P}$ ${\displaystyle \neg \neg P}$

Ley del medio excluido

La prueba por contradicción equivale a la ley del tercero excluido , formulada por primera vez por Aristóteles , que establece que tanto una afirmación como su negación son verdaderas, P ∨ ¬P .

Ley de no contradicción

La ley de no contradicción fue establecida por primera vez como principio metafísico por Aristóteles . Postula que una proposición y su negación no pueden ser ambas verdaderas o, de manera equivalente, que una proposición no puede ser verdadera y falsa al mismo tiempo. Formalmente, la ley de no contradicción se escribe como ¬(P ∧ ¬P) y se lee como "no se da el caso de que una proposición sea a la vez verdadera y falsa". La ley de no contradicción no sigue ni está implícita en el principio de prueba por contradicción.

Las leyes del tercero excluido y de la no contradicción juntas significan que exactamente una de P y ¬P es verdadera.

Prueba por contradicción en lógica intuicionista

En lógica intuicionista la prueba por contradicción no es generalmente válida, aunque se pueden derivar algunos casos particulares. Por el contrario, la prueba de negación y el principio de no contradicción son ambos intuicionistamente válidos.

La interpretación de Brouwer-Heyting-Kolmogorov de la prueba por contradicción da la siguiente condición de validez intuicionista: si no existe un método para establecer que una proposición es falsa, entonces existe un método para establecer que la proposición es verdadera. ^{[ aclarar ]}

Si entendemos por "método" el algoritmo , entonces la condición no es aceptable, ya que nos permitiría resolver el problema de detención . Para ver cómo, considere la afirmación H(M) que dice " La máquina de Turing M se detiene o no se detiene". Su negación ¬H(M) establece que " M ni se detiene ni no se detiene", lo cual es falso por la ley de no contradicción (que es intuicionistamente válida). Si la prueba por contradicción fuera intuicionistamente válida, obtendríamos un algoritmo para decidir si una máquina de Turing arbitraria M se detiene, violando así la prueba (intuicionistamente válida) de no solubilidad del problema de detención .

Una proposición P que satisface se conoce como proposición ¬¬-estable . Así, en la lógica intuicionista la prueba por contradicción no es universalmente válida, sino que sólo puede aplicarse a las proposiciones ¬¬-estables. Un ejemplo de tal proposición es decidible, es decir, satisfactoria . De hecho, la prueba anterior de que la ley del tercero excluido implica prueba por contradicción puede reutilizarse para mostrar que una proposición decidible es ¬¬-estable. Un ejemplo típico de proposición decidible es una afirmación que puede comprobarse mediante cálculo directo, como " es primo" o " divide ". ${\displaystyle \lnot \lnot P\Rightarrow P}$ ${\displaystyle P\lor \lnot P}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$

Ejemplos de pruebas por contradicción.

Los elementos de Euclides

Una aparición temprana de la prueba por contradicción se puede encontrar en los Elementos de Euclides , Libro 1, Proposición 6: ^[7]

Si en un triángulo dos ángulos son iguales, entonces los lados opuestos a los ángulos iguales también son iguales.

La prueba procede suponiendo que los lados opuestos no son iguales y deriva una contradicción.

Nullstellensatz de Hilbert

David Hilbert dio una influyente prueba por contradicción . Su Nullstellensatz afirma:

Si hay polinomios en n indeterminados con coeficientes complejos , que no tienen ceros complejos comunes , entonces existen polinomios tales que ${\displaystyle f_{1},\ldots ,f_{k}}$ ${\displaystyle g_{1},\ldots ,g_{k}}$ ${\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}=1.}$

Hilbert demostró la afirmación suponiendo que no existen tales polinomios y dedujo una contradicción. ^[8] ${\displaystyle g_{1},\ldots ,g_{k}}$

Infinidad de números primos

El teorema de Euclides establece que hay infinitos números primos. En los Elementos de Euclides, el teorema se establece en el Libro IX, Proposición 20: ^[9]

Los números primos son más que cualquier multitud de números primos asignados.

Dependiendo de cómo escribimos formalmente la afirmación anterior, la prueba habitual toma la forma de prueba por contradicción o de refutación por contradicción. Presentamos aquí lo primero, veamos a continuación cómo se hace la prueba como refutación por contradicción.

Si expresamos formalmente el teorema de Euclides diciendo que para cada número natural hay un primo mayor que él, entonces empleamos la prueba por contradicción, de la siguiente manera. ${\displaystyle n}$

Dado cualquier número , buscamos demostrar que existe un primo mayor que . Supongamos por el contrario que no existe tal p (una aplicación de prueba por contradicción). Entonces todos los números primos son menores o iguales que , y podemos formar la lista de todos ellos. Sea el producto de todos los números primos y . Como es mayor que todos los números primos, no es primo, por lo que debe ser divisible por uno de ellos, digamos . Ahora bien, ambos y son divisibles por , por lo tanto, también lo es su diferencia , pero esto no puede ser porque 1 no es divisible por ningún número primo. Por lo tanto tenemos una contradicción y por lo tanto hay un número primo mayor que ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p_{1},\ldots ,p_{k}}$ ${\displaystyle P=p_{1}\cdot \ldots \cdot p_{k}}$ ${\displaystyle Q=P+1}$ ${\displaystyle Q}$ ${\displaystyle p_{i}}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle p_{i}}$ ${\displaystyle Q-P=1}$ ${\displaystyle n}$

Ejemplos de refutaciones por contradicción

Los siguientes ejemplos se denominan comúnmente pruebas por contradicción, pero emplean formalmente refutación por contradicción (y por lo tanto son intuicionistamente válidos). ^[10]

Infinidad de números primos

Echemos un segundo vistazo al teorema de Euclides – Libro IX, Proposición 20: ^[9]

Los números primos son más que cualquier multitud de números primos asignados.

Podemos leer la afirmación en el sentido de que para cada lista finita de números primos, hay otro número primo que no está en esa lista, lo que podría decirse que está más cerca y en el mismo espíritu que la formulación original de Euclides. En este caso, la prueba de Euclides aplica la refutación por contradicción en un paso, como sigue.

Dada cualquier lista finita de números primos , se demostrará que existe al menos un número primo adicional que no está en esta lista. Sea el producto de todos los números primos enumerados y un factor primo de , posiblemente él mismo. Afirmamos que no está en la lista de números primos dada. Supongamos por el contrario que así fuera (una aplicación de refutación por contradicción). Entonces dividiría ambos y , por tanto, también su diferencia, que es . Esto genera una contradicción, ya que ningún número primo divide a 1. ${\displaystyle p_{1},\ldots ,p_{n}}$ ${\displaystyle P=p_{1}\cdot p_{2}\cdots p_{n}}$ ${\displaystyle p}$ ${\displaystyle P+1}$ ${\displaystyle P+1}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle P}$ ${\displaystyle P+1}$ ${\displaystyle 1}$

Irracionalidad de la raíz cuadrada de 2

La prueba clásica de que la raíz cuadrada de 2 es irracional es una refutación por contradicción. ^[11] De hecho, nos propusimos demostrar la negación ¬ ∃ a, b ∈ . a/b = √ 2 ${\displaystyle \mathbb {N} }$ suponiendo que existen números naturales a y b cuya razón es la raíz cuadrada de dos, y derivar una contradicción.

Prueba por descenso infinito

La prueba por descenso infinito es un método de prueba mediante el cual se demuestra que un objeto más pequeño con la propiedad deseada no existe de la siguiente manera:

• Supongamos que hay un objeto más pequeño con la propiedad deseada.
• Demostrar que existe un objeto aún más pequeño con la propiedad deseada, derivando así una contradicción.

Semejante prueba es también una refutación por contradicción. Un ejemplo típico es la prueba de la proposición "no existe el número racional positivo más pequeño": supongamos que existe un número racional positivo más pequeño q y derive una contradicción observando que ⁠q/2⁠ es incluso menor que q y sigue siendo positivo.

La paradoja de Russell

La paradoja de Russell , planteada teóricamente como "no hay ningún conjunto cuyos elementos sean precisamente aquellos conjuntos que no se contienen a sí mismos", es una afirmación negada cuya prueba habitual es una refutación por contradicción.

Notación

Las pruebas por contradicción a veces terminan con la palabra "¡Contradicción!". Isaac Barrow y Baermann utilizaron la notación QEA, para " quod est absurdum " ("que es absurdo"), similar a QED , pero esta notación rara vez se utiliza en la actualidad. ^[12] Un símbolo gráfico que a veces se utiliza para las contradicciones es un símbolo de "relámpago" con una flecha en zigzag hacia abajo (U+21AF: ↯), por ejemplo en Davey y Priestley. ^[13] Otros que a veces se usan incluyen un par de flechas opuestas (como ^{[ cita necesaria ]} o ), ^{[ cita necesaria ]} flechas tachadas ( ), ^{[ cita necesaria ]} una forma estilizada de hash (como U+2A33: ⨳) , ^{[ cita necesaria ]} o la "marca de referencia" (U+203B: ※), ^{[ cita necesaria ]} o . ^{[14] [15]} ${\displaystyle \rightarrow \!\leftarrow }$ ${\displaystyle \Rightarrow \!\Leftarrow }$ ${\displaystyle \nleftrightarrow }$ ${\displaystyle \times \!\!\!\!\times }$

La opinión de Hardy.

GH Hardy describió la prueba por contradicción como "una de las mejores armas de un matemático", diciendo: "Es una táctica mucho mejor que cualquier táctica de ajedrez : un jugador de ajedrez puede ofrecer el sacrificio de un peón o incluso una pieza, pero un matemático ofrece el juego". ". ^[dieciséis]

Demostración automatizada de teoremas

En la demostración automatizada de teoremas, el método de resolución se basa en la prueba por contradicción. Es decir, para demostrar que una determinada afirmación está implicada por determinadas hipótesis, el probador automático asume las hipótesis y la negación de la afirmación, e intenta derivar una contradicción. ^[17]

Ver también

• Ley del tercero excluido
• Ley de no contradicción
• Prueba por agotamiento
• Prueba por descenso infinito
• Modo de peaje
• Reducción al absurdo

Referencias

1. Bishop, Errett 1967. Fundamentos del análisis constructivo , Nueva York: Academic Press. ISBN  4-87187-714-0
2. "Prueba por contradicción". www2.edc.org . Consultado el 12 de junio de 2023 .
3. "Reductio ad absurdum | lógica". Enciclopedia Británica . Consultado el 25 de octubre de 2019 .
4. "Prueba por contradicción". nLaboratorio . Consultado el 7 de octubre de 2022 .
5. Richard Hammack, Libro de prueba , tercera edición, 2022, ISBN 978-0-9894721-2-8 ; consulte el "Capítulo 9: Refutación". 
6. Bauer, Andrej (29 de marzo de 2010). "Prueba de negación y prueba por contradicción". Matemáticas y Computación . Consultado el 26 de octubre de 2021 .
7. "Elementos de Euclides, Libro 6, Proposición 1" . Consultado el 2 de octubre de 2022 .
8. Hilbert, David (1893). "Ueber die vollen Invariantensysteme" . Annalen Matemáticas . 42 (3): 313–373. doi :10.1007/BF01444162.
9. "Elementos de Euclides, Libro 9, Proposición 20" . Consultado el 2 de octubre de 2022 .
10. Bauer, Andrej (2017). "Cinco etapas para aceptar las matemáticas constructivas". Boletín de la Sociedad Matemática Estadounidense . 54 (3): 481–498. doi : 10.1090/bull/1556 .
11. Alfeld, Peter (16 de agosto de 1996). "¿Por qué la raíz cuadrada de 2 es irracional?". Comprensión de las matemáticas, una guía de estudio . Departamento de Matemáticas, Universidad de Utah . Consultado el 6 de febrero de 2013 .
12. "Discusiones del foro de matemáticas".
13. B. Davey y HA Priestley, Introducción a las celosías y al orden , Cambridge University Press, 2002; consulte "Índice de notación", pág. 286.
14. Gary Hartitle, Introducción a la lógica modal , Capítulo 2, pág. II-2. https://web.archive.org/web/20110607061046/http://people.umass.edu/gmhwww/511/pdf/c02.pdf
15. La lista completa de símbolos de LaTeX, pág. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf
16. GH Hardy , La disculpa de un matemático ; Prensa de la Universidad de Cambridge, 1992. ISBN 9780521427067 .   PDF p.19 Archivado el 16 de febrero de 2021 en Wayback Machine .
17. "Resolución lineal", De la lógica a la programación lógica , The MIT Press, págs. 93-120, 1994, doi :10.7551/mitpress/3133.003.0007, ISBN 978-0-262-28847-7, recuperado el 21 de diciembre de 2023

Lecturas adicionales y enlaces externos

• Franklin, James ; Daoud, Albert (2011). Prueba en matemáticas: una introducción. Capítulo 6: Kew. ISBN 978-0-646-54509-7.{{cite book}}: CS1 maint: location (link)
• Prueba por contradicción de Cómo escribir pruebas de Larry W. Cusick
• Enciclopedia de Filosofía de Internet Reductio ad Absurdum; ISSN 2161-0002