Prueba por contradicción, ¿razonamiento circular?

Question

Supongamos que queremos demostrar $P$ implica $Q$ . Suponemos que $P$ . La prueba por contradicción comienza asumiendo que no $Q$ y de estos dos supuestos se deriva una "contradicción". Ahora bien, a veces esa contradicción es que $Q$ es cierto. No puedo evitar sentir que el argumento es circular, pero no puedo precisar qué es lo que me molesta. Estamos diciendo que no $Q$ implica $Q$ Por lo tanto $Q$ debe ser cierto para empezar. ¿Por qué son rigurosas las pruebas por contradicción de este tipo?

Answer 1

Lo siguiente es una tautología: $$(R\to \neg R) \to \neg R.$$ Es decir, si a partir de una premisa podemos demostrar que la premisa es falsa, entonces la premisa es falsa.

Si desde $P$ y $\neg Q$ podemos demostrar $Q$ , entonces de $P$ podemos demostrar $\neg Q\to Q$ reemplazando $R$ con $\neg Q$ en la tautología anterior, obtenemos $$(\neg Q\to \neg(\neg Q))\to \neg\neg Q.$$

En lógica no intuicionista, lógica clásica, la Ley del Medio Excluido nos dice que $\neg\neg Q\leftrightarrow Q$ es una tautología. Sustituyendo y utilizando el Modus Ponens, tenemos entonces que de $P$ podemos deducir $ Q$ . Desde $P$ podemos deducir $Q$ concluimos que $P\to Q$ se mantiene.

Eso es:

$$\begin{align*} 1.&&P,\neg Q&\vdash Q&\text{(what we are assuming we can prove)}\\ 2.&&P&\vdash \neg Q\to Q &\text{(Deduction Theorem)}\\ 3.&&P&\vdash ((\neg Q\to \neg\neg Q)\to \neg\neg Q) &\text{(Tautology)}\\ 4.&&P&\vdash \neg\neg Q\leftrightarrow Q &\text{(Tautology)}\\ 5.&&P&\vdash (\neg Q\to Q)\to Q &\text{(by substitution of 4 in 3)}\\ 6.&&P&\vdash Q &\text{(Modus ponens, 2,5)}\\ 7.&&&\vdash P\to Q &\text{(Deduction Theorem)} \end{align*}$$

Dicho esto:

Es muy común encontrar lo que yo llamo "falsas pruebas por contradicción". Pruebas en las que queremos demostrar $P\to Q$ ; asumimos que ambos $P$ y $\neg Q$ . Entonces sin utilizar el supuesto $\neg Q$ procedemos a utilizar la suposición $P$ para establecer $Q$ . Entonces el autor dice "Pero esto contradice $\neg Q$ , una contradicción; por lo tanto, $Q$ ."

Eso es una mala forma y una prueba mal escrita. La prueba se puede hacer directamente simplemente eliminando la línea que dice "Asumir $\neg Q$ ", y eliminando la línea que dice "Pero esto contradice $\neg Q$ una contradicción". Es decir, lo que tenemos es una prueba directa que se ha convertido en una prueba por contradicción añadiendo una suposición extra al principio (que nunca se utiliza) y una línea extra al final (que sólo señala que la nueva línea extra al principio contradice nuestra conclusión anterior).

Por ejemplo:

Teorema. Si $V$ es un espacio vectorial, y $W_1$ y $W_2$ son subespacios propios de $V$ entonces $V\neq W_1\cup W_2$ .

Prueba falsa por contradicción. Supongamos por el contrario que $V=W_1\cup W_2$ .

Si $W_1\subseteq W_2$ entonces $W_1\cup W_2=W_2\neq V$ porque estamos asumiendo $W_1$ y $W_2$ son subespacios propios. Por lo tanto, podemos suponer que $W_1\not\subseteq W_2$ . Simétricamente, si $W_2\subseteq W_1$ entonces $W_1\cup W_2=W_1\neq V$ por lo que podemos suponer $W_2\not\subseteq W_1$ .

Dejemos que $w_1\in W_1-W_2$ y $w_2\in W_2-W_1$ . Entonces $w_1+w_2\notin W_1$ (ya que $w_1\in W_1$ pero $w_2\notin W_1$ ); y $w_1+w_2\notin W_2$ (ya que $w_2\in W_2$ pero $w_1\notin W_2$ ). Por lo tanto, $w_1+w_2\notin W_1\cup W_2$ . Así, $w_1+w_2\in V-(W_1\cup W_2)$ Así que $V\neq W_1\cup W_2$ .

Pero esto contradice nuestra suposición de que $V=W_1\cup W_2$ . Por lo tanto, esta suposición es falsa, por lo que concluimos que $V\neq W_1\cup W_2$ . $\Box$

Ahora bien, fíjate en que si suprimimos las primeras líneas ("Supongamos lo contrario...") y las dos últimas ("Pero esto contradice nuestra suposición de que..."), tenemos un directo ¡prueba de lo que estábamos tratando de probar! Las líneas adicionales no hacen más que oscurecer la prueba y posiblemente crear confusión. Así que es mejor quitarlas.

Tal vez sea ese el tipo de cosas que observó, ya que menciona específicamente una "prueba por contradicción" en la que se llega a la contradicción mostrando que $P$ y $\neg Q$ implica $Q$ ?

Estos son pruebas válidas, sólo incluyen cosas que no son necesarias.

Tenga en cuenta que no está suponiendo que $Q$ , usted está asumiendo $\neg Q$ Como no estás asumiendo lo que quieres demostrar, no estás haciendo un razonamiento circular.

Answer 2

Creo que puedo ver su problema. Ignorando $P$ (que no es realmente relevante para la confusión), estamos probando $Q$ mediante la siguiente técnica:

Supongamos que $\neg Q$ . Entonces (bla bla bla) y por lo tanto $Q$ . Pero esto contradice nuestra suposición de que $\neg Q$ por lo que concluimos que $Q$ .

A primera vista, esto parece circular - parece como si se nos permitiera no justificar nunca nuestra suposición de $\neg Q$ simplemente porque resulta que contradice nuestra eventual conclusión, en el sentido de que la conclusión y la suposición no pueden ser ciertas al mismo tiempo.

De hecho, ese no es un principio de razonamiento sólido en general:

Supongamos que $0=1$ . Entonces, multiplicando ambos lados por $2$ obtenemos $0=2$ . Pero esto contradice $0=1$ (porque $1\ne 2$ Así que $0$ no puede ser igual a ambos al mismo tiempo), por lo que no necesitamos justificar nuestra suposición de que $0=1$ . Así, hemos demostrado que $0=2$ .

Por suerte, esto no es lo que ocurre realmente en una prueba por contradicción. Una forma de ver un esquema general es

Supongamos que $\neg Q$ . Entonces (bla bla bla) y por lo tanto $R$ . Pero $\neg Q$ y $R$ se contradicen entre sí (porque bla bla bla ), por lo que concluimos $Q$ .

Lo importante es que es $Q$ en lugar de $R$ que se está concluyendo. El primer argumento anterior es entonces sólo un ejemplo de esto cuando $R=Q$ -- en cuyo caso es tan fácil ver que $\neg Q$ y $R$ no puede ser a la vez cierto que no merece ningún argumento.

Una forma diferente de ver el argumento es considerarlo una forma abreviada de esto:

Sabemos al menos que $Q$ o $\neg Q$ es cierto. Proceder por análisis de casos:

1. Supongamos que $Q$ . Entonces, claramente $Q$ es cierto.

2. Supongamos que $\neg Q$ . Entonces (bla bla bla) y por lo tanto $Q$ .

Dado que ambas ramas del análisis del caso llegaron a la misma conclusión $Q$ (y hay debe siempre es una de las ramas que se mantiene), podemos concluir con seguridad que $Q$ siempre es cierto.

Answer 3

En mi experiencia, ese escenario suele significar que la suposición inicial de $\sim Q$ no se utilizó de forma esencial en la prueba. ¿Tienes un ejemplo de una prueba en la que $(P\wedge \sim Q) \to Q$ ?

Answer 4

No, demostramos que Q implica no Q. Entonces Q es contradictorio, por lo que debemos tener no Q. En símbolos lógicos, mostramos $Q\implies \lnot Q$ . Si haces una tabla de verdad encontrarás que Q debe ser falso.