La prueba por contradicción vs Probar el contrapositivo

Question

¿Cuál es la diferencia entre una "prueba por contradicción" y "probar el contrapositivo"? Intuitiva, se siente como haciendo exactamente lo mismo. Y cuando comparo un ejercicio, una persona prueba por contradicción, y el otro, demuestra que el contrapositivo, las pruebas a las que se ven casi exactamente el mismo.

Por ejemplo, supongamos que queremos demostrar: $P \implies Q$ Cuando quiero demostrar por contradicción, yo diría que asumir que esto no es cierto. Suponga $Q$ no es cierto, y $P$ es cierto. Blabla, pero esto implica $P$ no es verdadero, lo cual es una contradicción.

Cuando quiero probar el contrapositivo, digo yo. Suponga $Q$ no es cierto. Blabla, esto implica $P$ no es cierto.

La única diferencia en la prueba de ello es que asumo $P$ que es verdad en el principio, cuando quiero demostrar por contradicción. Pero esto se siente casi redundante, ya que al final siempre me sale que esto no es cierto. La única otra manera de que yo pudiera conseguir una contradicción es demostrando que $Q$ es cierto. Pero esto sería exactamente las mismas cosas como una prueba directa.

Puede alguien aclararme un poco aquí ? Por ejemplo: ¿hay pruebas de que puede ser probado por contradicción, pero no se ha probado en la prueba de los contrapositve?

Answer 1

Para demostrar $P \rightarrow Q$, puede hacer lo siguiente:

1. Probar directamente, que es asumir la $P$ y el espectáculo $Q$;
2. Demostrar por contradicción, que es asumir la $P$ $\lnot Q$ y derivar una contradicción; o
3. Probar el contrapositivo, que se asumen $\lnot Q$ y el espectáculo $\lnot P$.

A veces, la contradicción se llega a en $(2)$ es meramente contradiciendo la supuesta premisa $P$, y por lo tanto, como nota, es esencialmente una prueba por contrapositivo $(3)$. Sin embargo, tenga en cuenta que $(3)$ nos permite asumir sólo $\lnot Q$; si podemos extraer $\lnot P$, tenemos una limpieza a prueba de contrapositivo.

Sin embargo, en $(2)$, el objetivo es derivar una contradicción: la contradicción podría no llegar a $\lnot P$, si uno ha asumido ($P$ e $\lnot Q$). Llegar a una contradicción, que cuenta en una prueba por contradicción: decir que asumimos $P$ e $\lnot Q$ , y derivar de, digamos, $Q$. Desde $Q \land \lnot Q$ es una contradicción (que nunca puede ser cierto), nos vemos obligados entonces a la conclusión de que no puede ser que tanto $(P \land \lnot Q)$.

Pero tenga en cuenta que $\lnot (P \land \lnot Q) \equiv \lnot P \lor Q\equiv P\rightarrow Q.$

Así que una prueba por contradicción generalmente se ve algo como esto ($R$ a menudo $Q$ o $\lnot P$ o de cualquier otra contradicción):

• $P \land \lnot Q$ Premisa
  • $P$
  • $\lnot Q$
  • $\vdots$
  • $R$
  • $\vdots$
  • $\lnot R$
  • $\lnot R \land R$ Contradicción

$\therefore \lnot (\lnot P \land Q) \equiv P \rightarrow Q$

---

Answer 2

Hay un útil regla general, cuando usted tiene una prueba por contradicción, a ver si es "realmente" una prueba por contrapositivo.

En una prueba de por contrapositivo, demuestras $P \to Q$ asumiendo $\lnot Q$ y el razonamiento hasta que se obtenga $\lnot P$.

En una "auténtica" prueba por contradicción, supongamos tanto $P$ $\lnot Q$ , y deducir algunas otras contradicción $R \land \lnot R$.

Así que, después de finalizar la prueba, pregúntate a ti mismo: Es la "contradicción" que se me han sacado $\lnot P$, cuando la implicación $P \to Q$? ¿Nunca utilizo $P$ como una suposición? Si ambas respuestas son "sí", entonces la prueba es una prueba por contraposición, y se puede decir de esa manera.

Por ejemplo, aquí es una prueba por la "contradicción":

La Proposición: Suponga $A \subseteq B$. Si $x \not \in B$$x \not \in A$.

Prueba. Vamos a proceder por la contradicción. Suponga $x \not \in B$$x \in A$. Entonces, desde el $A \subseteq B$,$x \in B$. Esto es una contradicción, por lo que la prueba está completa.

Que la prueba puede ser directamente reformulado en una prueba por contrapositivo:

La Proposición: Suponga $A \subseteq B$. Si $x \not \in B$$x \not \in A$.

Prueba. Procedemos por contraposición. Suponga $x \in A$. Entonces, desde el $A \subseteq B$,$x \in B$. Esto es lo que queríamos probar, por lo que la prueba está completa.

La prueba por contradicción puede ser aplicado a una clase mucho más amplia de las declaraciones de la prueba por contraposición, que sólo funciona para las consecuencias. Pero hay pruebas de implicaciones por la contradicción que no puede ser reformulado en pruebas por contraposición.

Proposición: Si $x$ es un múltiplo de a $6$ $x$ es un múltiplo de a $2$.

Prueba. Vamos a proceder por la contradicción. Deje $x$ ser un número que es múltiplo de $6$ pero no un múltiplo de $2$. A continuación, $x = 6y$ algunos $y$. Podemos reescribir esta ecuación como $1\cdot x = 2\cdot (3y)$. Debido a que el lado derecho es un múltiplo de a $2$, por lo que es el lado izquierdo. Luego, debido a que $2$ es primo, y $1\cdot x $ es un múltiplo de a$2$, $x$ es un múltiplo de a $2$ o $1$ es un múltiplo de a $2$. Ya hemos asumido que $x$ no es un múltiplo de a $2$, podemos ver que $1$ debe ser un múltiplo de $2$. Pero eso es imposible: sabemos $1$ no es un múltiplo de a $2$. Así que tenemos una contradicción: $1$ es un múltiplo de a $2$ $1$ no es un múltiplo de a $2$. La prueba está completa.

Por supuesto que la proposición no pueda ser probado directamente así: el punto es simplemente que la prueba se da es realmente una prueba por contradicción, en vez de una prueba por contraposición. El beneficio clave de la prueba por contradicción es que se puede detener cuando usted encuentra alguna contradicción, no sólo de una contradicción que implican directamente a la hipótesis.

Answer 3

No es lo mismo.

Si $P$ $Q$ son declaraciones acerca de las instancias que (a priori de forma independiente) son verdaderas para algunos casos y falsa para otros, entonces, demostrando $P\Rightarrow Q$ es el mismo como lo demuestra el contrapositivo $\neg Q\ \Rightarrow \neg P$. Ambos significan la misma cosa: El conjunto de instancias para que $P$ es verdad está contenida en el conjunto de instancias donde $Q$ es cierto.

Demostrando una declaración de $A$ por la contradicción es algo más: Se añaden $\neg A$ a tu lista de axiomas, y el uso de las reglas de la lógica llegar a una contradicción, por ejemplo, en $1=0$. Entonces usted dice: Mi sistema de axiomas estaba bien antes de la adición de $\neg A$. Desde esta adición ha estropeado, en realidad $A$ tiene que ser cierto.

Un ejemplo: Usted desea probar la declaración de $$A:\quad {\rm "The\ number}\ \sqrt{2}\ {\rm is\ irrational."}$$ A continuación, añada las $\sqrt{2}={p\over q}$ a tu lista de axiomas sobre los números racionales y llegar a una contradicción.