18 votos

Tener dificultades para entender las pruebas de contradicción.

Estoy leyendo un libro de introducción a la matemática de las pruebas y no me parece para entender la mecánica de la prueba por contradicción. Considere el siguiente ejemplo.

$\textbf{Theorem:}$ Si $P \rightarrow Q$$R \rightarrow \neg Q$,$P \rightarrow \neg R$.

$\textbf{Proof:}$ (por contradicción) Suponga $P$, entonces se sigue que $Q$. Ahora, suponga $R$, entonces se sigue que $\neg Q$. Contradicción, tenemos $Q$ $\neg Q$ al mismo tiempo. Por lo tanto, $\neg R$. Por lo tanto, si $P \rightarrow Q$$R \rightarrow \neg Q$,$P \rightarrow \neg R$, como se desee.

Lo que no entiendo en esta prueba, es esa la razón de haber llegado a la contradicción, decidimos que nuestra suposición de que $R$ es necesariamente falsa? También podría haber sido nuestra primera suposición, a saber, $P$, era falso. O ambos de ellos podría ser falsa.

Así que mi pregunta es: en general, cuando se prueba por contradicción, ¿cómo sabemos qué supuesto, exactamente es falsa? Y ¿cómo sabemos que exactamente una suposición debe estar mal en el fin de proceder con la prueba?

15voto

Mauro ALLEGRANZA Puntos 34146

En una prueba con varios supuestos usted tiene que elegir uno de ellos para ser "culpa" de la contradicción.

Creo que con su ejemplo en términos de hipótesis; se comienza con un par de ellos (pueden ser dos Lemas ya demostrada, o dos hipótesis) :

$P→Q$ $R→¬Q$.

A continuación, vamos a proceder "formalmente" de la siguiente manera (voy a usar la Deducción Natural de prueba del sistema; para una buena explicación de las reglas que deben utilizarse, consulte : Ian Chiswell & Wilfrid Hodges, la Lógica Matemática (2007), Ch.2 : Informal deducción natural, página 5) :

1) $P$ --- asumido

2) $Q$ --- desde el 1) y $P→Q$ $\rightarrow$- elim (modus ponens)

3) $R$ --- asumido

4) $\lnot Q$ --- a partir de 3) y $R→¬Q$ $\rightarrow$- elim (modus ponens)

5) $\bot$ --- de 2) y 4) por $\lnot$-elim [es decir, la utilización de la regla : "de$\varphi$$\lnot \varphi$, inferir $\bot$]

6) $\lnot R$ --- a partir de 3) y 5) por $\lnot$-intro [es decir, la utilización de la regla : "si de $\varphi$ hemos derivado $\bot$, entonces inferir $\lnot \varphi$], "descarga" temporal asunción 3)

7) $P \rightarrow \lnot R$ --- desde el 1) y 6) por $\rightarrow$-intro, "descarga" temporal de la hipótesis 1).

Por lo tanto hemos demostrado que :

$P→Q, R→¬Q \vdash P \rightarrow \lnot R$.


Según la respuesta anterior, podemos aplicar contraposición : $\varphi \rightarrow \lnot \psi \vdash \psi \rightarrow \lnot \varphi$ a concluir también :

$P→Q, R→¬Q \vdash R \rightarrow \lnot P$.

En la prueba anterior, hemos elegido el assumptiom $R$ a ser "culpa" de la contradicción. Podemos elegir también el $P$.

Si volver a escribir la introducción de $\lnot P$ en el paso 6), el resultado final será exactamente con : $R \rightarrow \lnot P$.


Comentario

Con el fin de "tener un sentimiento" con la anterior aplicación de reglas lógicas, modificar el anterior prueba el uso de un único supuesto de $P \land R$.

Debido al hecho de que :

$P \land R \vdash P$ $P \land R \vdash R$ [por : $\land$-elim]

podemos repetir los mismos pasos hasta 5) : $\bot$.

En este caso, sólo tenemos una hipótesis a ser "culpado" : $P \land R$ y se concluye con :

$\lnot (P \land R)$.

Esto significa que, en presencia de los dos Lemas o hipótesis : $P \rightarrow Q$$R \rightarrow \lnot Q$, nosotros no "conjuntamente valer" $P$$R$.

Por lo tanto, uno de ellos debe ser "eliminado". Cual ? nos toca a nosotros ...

13voto

Jean-Claude Arbaut Puntos 9403

Para responder también podría haber sido nuestra primera suposición, a saber, P, era falso. O ambos de ellos podría ser falso: sí, podría, pero si usted asume que P, entonces R debe ser falsa, de lo que se escribe $P\rightarrow\neg R$. Usted podría haber concluido $R\rightarrow \neg P$, de curso (y es la contraposición), asumiendo $R$ en lugar de $P$.

Observe que ambas de estas implicaciones son verdaderas, incluso si $P$ $R$ son falsas. Usted no sabe que es falso, porque ninguna es falsa a priori. Usted asume una es verdadera, y concluir algo acerca de la otra.


Cuando usted hace esto, en la práctica, no suele ser un problema. Ejemplo, vamos a probar a $\sqrt{2}$ es irracional, por la contradicción.

Así, asumimos $\sqrt{2}$ es racional, y le será dado lugar a algo que es ciertamente malo, por lo tanto la suposición es incorrecta.

Desde $\sqrt{2}$ se supone que para ser racional, tenemos $\sqrt{2}=\frac pq$ para algunos enteros $p$, $q$ que no tienen ningún factor común (de lo contrario, el factor).

Por lo tanto $p^2=2q^2$, lo $2$ divide $p$, e $p=2p'$, y que usted vuelva a escribir la igualdad de $4p'\,^2=2q^2$ o $q^2=2p'\,^2$. Pero, a continuación, $2$ divide también a $q$. No es posible, ya que los $p$ $q$ no tienen ningún factor común.

Por tanto, algo tiene que estar mal. Qué? La única cosa que hemos asumido, que $\sqrt{2}$ es un número racional.

12voto

linksideal Puntos 171

Tenga en cuenta que usted no desea probar o contradecir $P$ o $R$ a sí mismos. Lo que quiero demostrar es la implicación $P\rightarrow\neg R$. Así que usted escoja la asunción de esta implicación, en este caso $P$, y su uso para más argumentación.
Ahora usted puede comenzar su argumentación con otra suposición como $R$ o con cualquier otra cosa. Importante diferencia: ahora usted puede buscar contradicciones.

4voto

paw88789 Puntos 19712

En la demostración de $A\rightarrow B$ por contradicción, supongamos $\neg(A\rightarrow B)$. La negación de la $A\rightarrow B$ $A\wedge \neg B$ (el falso caso de una implicación).

En el caso de que esto significa que puedes asumir $P\rightarrow Q$, $R\rightarrow \neg Q$, y $\neg(P\rightarrow \neg R)$. Sin embargo $\neg(P\rightarrow \neg R)$ es equivalente a $P\wedge R$. Así que usted consigue $P$, $R$, $P\rightarrow Q$ y $R\rightarrow\neg Q$.

Desde que usted debería ser capaz de obtener su contradicción. (Hay otras maneras de probar este problemas así.)

3voto

MattClarke Puntos 121

Permítanme darles un breve y menos formal que la explicación de las otras respuestas.

Si usted comienza con un conjunto de suposiciones {A1, A 2, ... n} y derivar una contradicción, prueba que el conjunto de hipótesis que es internamente inconsistente (o como @J-Marcos enunciado, "conjuntamente incompatibles") -- es decir, no pueden todos ser cierto.

Así que usted puede elegir cualquiera de los supuestos, digamos que Unyo, y a la conclusión de que, sobre la base de los otros supuestos, i debe ser falsa.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X