Prueba por contradicción

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 las pruebas matemáticas, no todas las escuelas de pensamiento matemático aceptan este tipo de prueba 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 la suposición inicial no es la negación del enunciado que se pretende probar. En este sentido general, la prueba por contradicción también se conoce como prueba indirecta , prueba por suposición de lo contrario [ ^2] y reductio ad impossibile ^[3] .

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

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

Un caso especial importante es la prueba de existencia por contradicción: para demostrar que existe un objeto con una propiedad dada, 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 se lee: "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 puede concluir". ${\displaystyle \lnot \lnot P}$ ${\displaystyle P}$

En el cálculo secuencial el principio se expresa mediante la ecuación secuencial

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

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

Justificación

En la 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 medio excluido , de la siguiente manera. Suponemos ¬¬P y buscamos demostrar que P . Por la ley del medio excluido P se cumple o no se cumple:

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 tercio excluido.

En el cálculo secuencial clásico, la prueba por contradicción de LK se deriva 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 P .
3. Derivar falsedad.
4. Concluya ¬P .

Por el contrario, la prueba por contradicción se realiza de la siguiente manera:

1. La proposición a demostrar es P .
2. Supongamos ¬P .
3. Derivar falsedad.
4. Concluir 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 quiere demostrar, mientras que la prueba por contradicción se puede aplicar 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 ello, en la práctica matemática, ambos principios se denominan "prueba por contradicción". ${\displaystyle P}$ ${\displaystyle \neg \neg P}$

Ley del tercero excluido

La prueba por contradicción es equivalente a la ley del tercio excluido , formulada por primera vez por Aristóteles , que establece que una afirmación o su negación es verdadera, P ∨ ¬P .

Ley de no contradicción

La ley de no contradicción fue enunciada 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 equivalentemente, que una proposición no puede ser verdadera y falsa a la vez. Formalmente, la ley de no contradicción se escribe como ¬(P ∧ ¬P) y se lee como "no es el caso que una proposición sea verdadera y falsa a la vez". La ley de no contradicción no se sigue ni está implícita en el principio de prueba por contradicción.

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

Prueba por contradicción en lógica intuicionista

En la lógica intuicionista, la prueba por contradicción no suele ser 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 tomamos "método" como algoritmo , entonces la condición no es aceptable, ya que nos permitiría resolver el problema de la parada . 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) dice que " M ni se detiene ni no se detiene", lo cual es falso según la ley de no contradicción (que es válida desde el punto de vista intuicionista). Si la prueba por contradicción fuera válida desde el punto de vista intuicionista, obtendríamos un algoritmo para decidir si una máquina de Turing arbitraria M se detiene, violando así la prueba (válida desde el punto de vista intuicionista) de no resolubilidad del problema de la parada .

Una proposición P que satisface se conoce como proposición ¬¬-estable . Por lo tanto, en la lógica intuicionista, la prueba por contradicción no es universalmente válida, sino que solo se puede aplicar a las proposiciones ¬¬-estables. Una instancia de tal proposición es una proposición decidible, es decir, que satisface . De hecho, la prueba anterior de que la ley del tercio excluido implica prueba por contradicción se puede reutilizar para mostrar que una proposición decidible es ¬¬-estable. Un ejemplo típico de una proposición decidible es una afirmación que se puede verificar 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

Elementos de Euclides

Un ejemplo temprano de 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 asumiendo que los lados opuestos no son iguales y deriva una contradicción.

El cálculo de ceros de Hilbert

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

Si hay polinomios en n indeterminados con coeficientes complejos , que no tienen ceros complejos comunes , entonces hay 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 asumiendo que no existen tales polinomios y derivó una contradicción. ^[8] ${\displaystyle g_{1},\ldots ,g_{k}}$

Infinitud de primos

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

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

Dependiendo de cómo escribimos formalmente la afirmación anterior, la prueba habitual toma la forma de una prueba por contradicción o una refutación por contradicción. Aquí presentamos la primera, 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 existe 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 la prueba por contradicción). Entonces, todos los primos son menores o iguales que , y podemos formar la lista de todos ellos. Sea el producto de todos los primos y . Como es mayor que todos los números primos, no es primo, por lo tanto, debe ser divisible por uno de ellos, digamos . Ahora bien, tanto 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 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 formalmente emplean la refutación por contradicción (y, por lo tanto, son intuicionistamente válidos). ^[10]

Infinitud de 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 asignada de números primos.

Podemos interpretar la afirmación como si dijera que por cada lista finita de primos existe otro primo que no está en esa lista, lo que posiblemente se acerque más a la formulación original de Euclides y esté en el mismo espíritu que ella. En este caso, la prueba de Euclides aplica la refutación por contradicción en un paso, de la siguiente manera.

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 primos enumerados y un factor primo de , posiblemente él mismo. Afirmamos que no está en la lista dada de primos. Supongamos, por el contrario, que lo estuviera (una aplicación de la refutación por contradicción). Entonces dividiría a ambos y , por lo tanto también su diferencia, que es . Esto da 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 derivamos una contradicción.

Prueba por descendencia infinita

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

• Supongamos que existe 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.

Una prueba de este tipo es, a su vez, una refutación por contradicción. Un ejemplo típico es la prueba de la proposición "no existe el menor número racional positivo": supongamos que existe un menor número racional positivo q y deduzcamos una contradicción observando queq/2⁠ es incluso más pequeño que q y sigue siendo positivo.

La paradoja de Russell

La paradoja de Russell , enunciada en teoría de conjuntos como "no existe 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 demostraciones por contradicción a veces terminan con la palabra "¡Contradicción!". Isaac Barrow y Baermann usaron la notación QEA, por " quod est absurdum " ("que es absurdo"), en la línea de QED , pero esta notación rara vez se usa hoy en día. ^[12] Un símbolo gráfico que a veces se usa para las contradicciones es un símbolo de "rayo" con una flecha en zigzag hacia abajo (U+21AF: ↯), por ejemplo en Davey y Priestley. ^[13] Otros símbolos que a veces se usan incluyen un par de flechas opuestas (como ^{[ cita requerida ]} o ), ^{[ cita requerida ]} flechas tachadas ( ), ^{[ cita requerida ]} una forma estilizada de almohadilla (como U+2A33: ⨳), ^{[ cita requerida ]} o la "marca de referencia" (U+203B: ※), ^{[ cita requerida ]} o . ^{[14] [15]} ${\displaystyle \rightarrow \!\leftarrow }$ ${\displaystyle \Rightarrow \!\Leftarrow }$ ${\displaystyle \nleftrightarrow }$ ${\displaystyle \times \!\!\!\!\times }$

La visió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 más fina que cualquier táctica de ajedrez : un jugador de ajedrez puede ofrecer el sacrificio de un peón o incluso de una pieza, pero un matemático ofrece el juego". ^[16]

Demostración automática de teoremas

En la demostración automática 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 se deduce de unas hipótesis dadas, el demostrador automático supone las hipótesis y la negación de la afirmación, e intenta derivar una contradicción. ^[17]

Véase también

• Ley del tercero excluido
• Ley de no contradicción
• Prueba por agotamiento
• Prueba por descendencia infinita
• Modus operandi
• 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. "Reducción al absurdo | lógica". Enciclopedia Británica . Consultado el 25 de octubre de 2019 .
4. "Prueba por contradicción". nLab . Consultado el 7 de octubre de 2022 .
5. Richard Hammack, Book of Proof , 3.ª edición, 2022, ISBN 978-0-9894721-2-8 ; consulte "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 de la aceptación de las matemáticas constructivas». Boletín de la Sociedad Americana de Matemáticas . 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?". Understanding Mathematics, a study guide . 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 redes y el orden , Cambridge University Press, 2002; véase "Índice de notación", pág. 286.
14. Gary Hardegree, 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. Lista completa de símbolos LaTeX, pág. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf
16. GH Hardy , Disculpa de un matemático ; Cambridge University Press, 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, consultado el 21 de diciembre de 2023

Lectura adicional y enlaces externos

• Franklin, James ; Daoud, Albert (2011). Demostración 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