Por qué, lógicamente, es la prueba por contradicción válido?

Question

¿Cómo se prueba por contradicción de trabajo de forma lógica?

Normalmente, en una prueba que podría tener una premisa verdadera, que conduce a una conclusión verdadera, es decir, es cierto que $T \rightarrow T$.

Pero entonces, ¿cómo se prueba por contradicción de trabajo? Asumimos la premisa es falsa y, a continuación, el objetivo es lo que, espectáculo $F \rightarrow F$? O $F \rightarrow T$? (ambos de los cuales son verdaderas?)

Como ¿qué es exactamente la lógica del mecanismo de debajo de todo esto que permite a pruebas de trabajo, así como una prueba por contradicción?

Answer 1

Sí, bueno, una prueba por contradicción implica dos reglas de inferencia.

$$\begin{split}\text{Negation introduction}\quad&\quad (r\implies q) \text{ and } (r\implies \neg q), \text{ infers } \neg r\\\text{Double Negation elimination:}\quad &\quad \neg\neg p\text{ infers } p\end{split}$$

(1) la "Negación introducción" regla de inferencia sostiene que si algo implica una contradicción, entonces debe ser falsa, ya que suelen afirmar que las contradicciones no son verdaderas y por lo tanto no puede ser infered por cierto de las cosas.

Esto es aceptable en tanto intuitionistic y la lógica clásica de los sistemas. Aunque existen otros sistemas (como mínimo de lógica) que no aceptan esto.

($\def\false{\mathsf F}\def\true{\mathsf T}$Semánticamente, esto es debido a que $\false \to \false$ es verdadero mientras que $\true\to\false$ es falso. Esto lleva a algunos sistemas para definir la negación como $\neg \phi ~\equiv~ \phi\to\mathsf F$ .)

(2) la "Doble negación de la eliminación de la regla" es que si la negación de una premisa es falsa, entonces la premisa debe ser verdadera. Esto es no aceptado en intuitionistic lógica, pero es en la lógica clásica.

(3) la Combinación de estas reglas dan el esquema de una prueba por contradicción: se supone una negación de un predicado, demostrar que se deduce una contradicción, por tanto deducir que el predicado es verdadero.

$$\begin{split}\text{Proof by Contradiction}\quad&\quad (\neg p \implies q) \text{ and }(\neg p\implies \neg q) \text{, infers }p\end{split}$$

Answer 2

Muchos de los problemas que he descrito aquí se exhiben en este Q&A.

En primer lugar, vamos a ser claros acerca de lo que estamos hablando. Hay dos reglas que a menudo se llama "la prueba por contradicción". El primero, la negación de la introducción, puede ser escrito como $\cfrac{\varphi\vdash\bot}{\vdash\neg\varphi}$ que puede leerse como "si podemos derivar que $\varphi$ implica la falsedad, entonces podemos derivar $\neg\varphi$". También podemos escribir esto como un axioma: $(\varphi\Rightarrow\bot)\Rightarrow\neg\varphi$. Por alguna razón, esta es la forma en Bram28 ha tomado su declaración, pero no creo que haya un problema con esto. Usted diría, "bueno, claro que si, asumiendo $\varphi$ conduce a una contradicción, a continuación, $\varphi$ debe haber sido falsa y por lo tanto $\neg\varphi$ es verdadero". Hay otra regla, más apropiadamente llamado "la prueba por contradicción", que puede ser escrito $\cfrac{\neg\varphi\vdash\bot}{\vdash\varphi}$ o como un axioma $(\neg\varphi\Rightarrow\bot)\Rightarrow\varphi$. Estos parece ser lo que usted está teniendo problema con. Viendo como esta última norma ha sido rechazada por muchos matemáticos (constructivistas de varios tipos), usted no estaría completamente loco a la pregunta. (En la débil defensa de Bram28, probablemente aceptar "sustituyendo $\neg\psi$ en la de arriba, por el mismo argumento podemos demostrar que $\neg\psi$ es falso lo $\psi$ es verdad", sino la regla, sólo muestra que la $\neg\neg\psi$ es cierto. La regla que permite pasar de $\neg\neg\psi$ $\psi$es, de hecho, equivalente a la prueba por contradicción.)

Para ser más claro acerca de lo que estamos hablando es necesario distinguir la sintaxis de la semántica. Si estamos hablando de "reglas de inferencia" o "pruebas", que se suele pensar sintácticamente. Es decir, estamos pensando acerca de los símbolos en una página y reglas para el manejo de las colecciones de símbolos en otras colecciones de símbolos o reglas sobre lo que es "correcto" de los arreglos de los símbolos, es decir, una prueba. (Más informal entregas serán oraciones en un lenguaje natural que seguir "las reglas de la razón", pero la idea es que la forma del argumento es lo que lo hace válido.) La semántica, por otra parte, interpreta los símbolos de los objetos matemáticos y, entonces decimos que una fórmula (es decir, la disposición de los símbolos) es "verdadero" si se interpreta como un objeto matemático satisfacer algunas de determinada propiedad. Por ejemplo, decimos que una fórmula clásica de la lógica proposicional es "verdadera" si su interpretación como una función Booleana es la constante de $1$ función.

Por lo tanto, tenemos dos posibles lecturas de su pregunta: 1) ¿por Qué es la regla de $\cfrac{\neg\varphi\vdash\bot}{\vdash\varphi}$ derivable? 2) ¿por Qué es la regla de $\cfrac{\neg\varphi\vdash\bot}{\vdash\varphi}$ "verdadero"?

Para (1), uno de ellos muy insatisfactoria respuesta es que a menudo se toma como dado, es decir, no es derivable por la definición de la lógica. Un poco más satisfactoria respuesta es la siguiente. Dada una lógica constructiva, donde la regla no es derivable pero otros más "normales" que son las normas que nos puede mostrar que si para todas las fórmulas $\varphi$, $\vdash\varphi\lor\neg\varphi$ es derivable, entonces podemos derivar la regla de $\cfrac{\neg\varphi\vdash\bot}{\vdash\varphi}$ (y viceversa). Otra forma de decir esto es que el $\varphi\lor\neg\varphi$ es demostrablemente equivalente a $(\neg\varphi\Rightarrow\bot)\Rightarrow\varphi$. También es demostrablemente equivalente a $\neg\neg\varphi\Rightarrow\varphi$. El axioma $\varphi\lor\neg\varphi$ es a menudo descrito como "todo lo que es verdadero o falso". No se trata exactamente de lo que significa, pero esta idea de que todo lo "verdadero o falso" es a menudo considerado intuitivamente obvio. Sin embargo, no es cuestión de si $\varphi$ es "true" o "false" en la anterior. Tenemos reglas para la construcción de pruebas de otras pruebas, y eso es todo lo que hay para esta perspectiva.

Para (2), si el uso de la "tabla de verdad" la semántica de la lógica proposicional clásica, entonces usted simplemente calcular. Usted sólo tendrá que mostrar que $(\neg\varphi\Rightarrow\bot)\Rightarrow\varphi$ cuando se interpreta es la constante de $1$ función cuando ambos $0$ $1$ son sustituidos en la interpretación de la fórmula. Se puede mostrar fácilmente esto. En estos semántica, la "prueba por contradicción" es simplemente "verdadero". A esta pregunta requiere el cuestionamiento de la semántica. Una cosa es la cuestión de si hay sólo dos valores de verdad, $0$$1$. ¿Por qué no tres o un número infinito de ellos? Esto lleva a varios valores de la lógica. Alternativamente, se podría mantener la verdad de los valores de la misma, pero interpretar fórmulas como algo distinto de funciones Booleanas. Por ejemplo, podríamos decir que son funciones Booleanas, pero sólo podemos permitir monótona, o podríamos decir que son total Booleano relaciones. Hacer estos cambios que requiere la adaptación de la noción de "verdad". Para el último ejemplo, podemos decir que una fórmula es "verdadera" si se interpreta como una relación que se relaciona todas Booleano entradas a $1$. Siendo una relación y no sólo una función, sin embargo, esto no impide que se de también relacionadas con algunas o todas las entradas de a $0$, es decir, algo que puede ser "verdadero" y "falso".

Cambiar la semántica afecta el que las normas y los axiomas de sonido. Una regla o axioma es el sonido con respecto a un determinado semántica, si su interpretación es "verdadero" en el que la semántica. $(\neg\varphi\Rightarrow\bot)\Rightarrow\varphi$ es de sonido con respecto a las "tablas de verdad", pero no con respecto a otras muchas posibles semántica.

Para resumir, si usted está trabajando con respecto a la "tabla de verdad" semántica, a continuación, "la prueba por contradicción" es simplemente "verdadero", que es cuando se interpreta es interpretado como una constante "verdadera" función Booleana, y esto puede ser fácilmente calculada. En este caso, todos sus "supuestos lógicos" están integrados en la noción de "tabla de verdad" de la semántica. Con respecto a la semántica, la "prueba" es irrelevante. La prueba es un concepto sintáctico. Su discusión sobre "suponiendo que la premisa es falsa" es (ligeramente alterados) la prueba de la teoría de la conversación. Con un enfoque semántico, no hay ninguna ", asumiendo la premisa es true/false", la fórmula se interpreta como "verdadero" (es decir, una constante $1$ función) o no. (Usted puede tener meta-lógica supuestos que algunos la fórmula es "true", pero esto está sucediendo fuera de la lógica. En última instancia, la moneda de la matemática reino es el más sintáctico de la noción de la prueba y la semántica empuja a prueba al meta-lógica.)

Answer 3

Es porque la proposición $(\neg P \Rightarrow (Q \wedge \neg Q)) \Rightarrow P$ es una tautología, es decir, siempre es cierto, no importa la verdad, los valores de $P$$Q$.

La tautología es decir "Si el frente de $P$ implica algo imposible, entonces $P$."

Answer 4

Funciona de la siguiente manera:

Digamos que usted tiene un conjunto de declaraciones de $\Gamma$, y queremos inferir $\neg \phi$, y esto lo hacemos mediante una prueba por contradicción.

Por lo tanto, asumimos $\phi$, y muestran que la que conduce a una contradicción.

Esto significa que $\Gamma$, junto con $\phi$ lógicamente implica una contradicción, es decir,

$$\Gamma \cup \phi \vDash \bot$$

y eso significa que es imposible poner todas las declaraciones en $\Gamma \cup \phi$ a true. Pero que entonces también significa que si todas las declaraciones en $\Gamma$ son verdaderas, $\phi$ tendrá que ser falsa, es decir, $\neg \phi$ tendrá que ser verdad. Y así tenemos

$$\Gamma \vDash \neg \phi$$

Así, en efecto, se ha demostrado $\neg \phi$