Prueba por contradicción

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.

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 \lno \lno P}{\vdash P}}}$

que dice: "Si se prueba, entonces se puede concluir".${\displaystyle \lno \lno P}$${\estilo de visualización P}$

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

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

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

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)}$

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".${\estilo de visualización P}$${\displaystyle \neg \neg P}$

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 .

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.

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (May 2024) (Learn how and when to remove this message)

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}$

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.

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}}$

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}$

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]

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}$

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.

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 , 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.

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 }$

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]

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]

• Ley del tercero excluido
• Ley de no contradicción
• Prueba por agotamiento
• Prueba por descendencia infinita
• Modus operandi
• Reducción al absurdo

El Wikilibro Prueba matemática tiene una página sobre el tema: Prueba por contradicción

• 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