37 votos

En una prueba por la contradicción, ¿qué pasa si la proposición y su negación conducen a contradicciones?

Estoy aprendizaje de las matemáticas.

Recientemente he pensado más en la prueba por contradicción técnica, y tengo una pregunta que me gustaría aclarado. Permítanme conjunto de la etapa.

Supongamos que estoy tratando de demostrar un teorema.

Teorema: Si a y $\neg$B, $\neg$C.

Prueba (contradicción): supongamos que a es verdadero y $\neg$B es verdadero. Supongamos que C es verdadera ($\neg$C es falsa).

[bla bla bla]

A partir de este, se llega a una contradicción, porque vemos que B es true ($\neg$B es falsa), pero sabemos que $\neg$B es verdadera (porque se supone que es verdadera). Por lo tanto, ya que suponiendo que C es verdadera nos lleva a una contradicción, debe ser el caso que C es falsa ($\neg$C es verdadera). QED.

Mi problema con esto: ¿por qué es que C conduce a una contradicción decir que $\neg$C es cierto? Lo que si $\neg$C también conduce a una contradicción? En ese caso, no una prueba por contradicción no demostrar nada? ¿Por qué podemos estar seguros de que C conduce a una contradicción decir que $\neg$C no conduce a una contradicción?

Lo siento si esta pregunta ya ha sido pedido. He buscado un poco antes de preguntar a ver si alguien tiene esta misma pregunta específica, pero la mayoría de los resultados sólo se le preguntó por qué una prueba por contradicción de las obras en general sin ningún tipo de pregunta clara.

60voto

Bram28 Puntos 18

Si tanto $C$ $\neg C$ conducir a una contradicción, entonces usted debe trabajar con un incoherente conjunto de supuestos ... de la cual nada puede inferirse ... incluyendo $\neg C$. Como tal, $\neg C$ todavía puede ser la conclusión dado que la suposición $C$ conduce a una contradicción.

Por lo tanto, independientemente de si $\neg C$ también conduce a una contradicción, o si no, podemos concluir $\neg C$ una vez suposición $C$ conduce a una contradicción.

La cosa a recordar es que cuando en la lógica nos dice que podemos 'concluir' algo, no significa que ese algo se sigue de la hipótesis ... no es que algo sea verdad. Creo que ese es el origen de la confusión. Usted parece estar diciendo: "OK, si $C$ conduce a una contradicción, entonces lo que queremos decir $\neg C$ es cierto ... Pero espera! Lo que si $\neg C$ conduce a una contradicción así .. no se que significa ese $\neg C$ no puede ser verdad? Así que, ¿cómo podemos decir $\neg C$ es cierto?". Pero no es ese $\neg C$ es cierto .. es solo que lógicamente se deduce de las hipótesis. Que es: si los supuestos se cumplen, entonces $\neg C$ va a ser cierto. Así, son ellos? .. y es? Lo curioso es que, como los lógicos, no nos interesa :)

30voto

Graham Kemp Puntos 29085

¿por qué es que $C$ lleva a una contradicción decir que $\neg C$ es cierto?

Más bien: ¿por qué $\def\false{\mathsf{contradiction}} A,\neg B, C\vdash \false$ nos deja inferir que $A,\neg B\vdash \neg C$

Bien, $A,\neg B,C\vdash \false$ significa que $\false$ es cierto suponiendo que $\{A,\neg B, C\}$ todas son verdaderas. Sin embargo, una $\false$ es, por definición, false, por lo que nos informa de que al menos uno de $\{A,\neg B, C\}$ debe ser falsa. Así, cuando asumimos que $\{A,\neg B\}$ son ambas verdaderas, somos lo que implica que las $C$ es falso. Que es $A,\neg B\vdash \neg C$

Aviso: no Estamos incondicional, declarando que $\neg C$ es verdadero; y estamos afirmando que es tan bajo el supuesto de que $A$ $\neg B$ son verdaderas.

Lo que si $\neg C$ también conduce a una contradicción?

Por qué, si podemos probar $A,\neg B,C\vdash \false$ y también que $A,\neg B,\neg C\vdash \false$ a continuación, hemos demostrado que: al menos uno de $\{A,\neg B, C\}$ y al menos uno de $\{A,\neg B,\neg C\}$ son falsas; incluso simultáneamente. Ya que generalmente se acepta que el $C$ no puede tener dos diferentes verdad tareas a la vez (la ley de noncontradiction: $\neg(\neg C\wedge C)$), debemos concluir que al menos uno de $\{A,\neg B\}$ son falsas. Por lo tanto, inferimos a partir de esas dos pruebas que: $A,\neg B\vdash\false$.$$\begin{split}A,\neg B,C &\vdash \false\\ A,\neg B,\neg C&\vdash\false\\\hline A,\neg B&\vdash \false\end{split}\text{ because } \begin{split}A,\neg B &\vdash \neg C\\ A,\neg B&\vdash\neg\neg C\\\hline A,\neg B&\vdash \false\end{split}$$

13voto

Davislor Puntos 379

Buena pregunta! Hay algunos matemáticos que no están de acuerdo en que la Ley del Medio Excluido es válida, y por lo tanto sólo aceptan directo pruebas de sonido, no de las pruebas por la contradicción. Se diría que su intuición es algo importante. Si usted está usando las reglas de la lógica, que no explotan cuando se encuentran con $p∧¬p$, es decir, una lógica que no indique que una incoherencia demuestra que todas las declaraciones son vacuously cierto, estás usando un paraconsistent lógica. Si usted puede demostrar una contradicción, y todavía pienso que la teoría es de interés, estás haciendo lo inconsistente de las matemáticas.

En las matemáticas y la filosofía, sin embargo, tal resultado sería demostrar que el sistema formal que se utiliza es inconsistente. En una lógica tradicional, tales como los axiomas de la lógica definida por David Hilbert, significa que todos (bien formado) declaraciones convertido en vacuously cierto como teoremas dentro de ese sistema. La prueba del sistema generado por la sola premisa de "Falsa" y que contiene todas las otras declaraciones como teoremas con la misma línea de prueba es demasiado trivial para ser interesante, y que le han demostrado la inconsistencia del sistema a ser equivalente a la trivial bajo la lógica tradicional, tan incoherente teoría sería abandonada. Pero, ya que había sido alguna razón, la gente estaba utilizando la teoría de antes, ellos se pregunte, "¿Podemos rescatar las piezas de esta teoría nos importa? Cambio de los axiomas, consistente, y todavía tiene una teoría interesante, tal vez incluso una de las más útiles?"

El ejemplo más conocido es, probablemente, cuando Frege trató de demostrar que todos los de las matemáticas podría ser fundada en la teoría de conjuntos. En su teoría, fue permisible para definir el conjunto de todos los conjuntos con alguna propiedad. Bertrand Russell demostró que esto llevó a la Paradoja de Russell: el conjunto de todos los conjuntos que no se contienen a sí mismos, contienen en sí? Así, la teoría fue probada inconsistente.

Frege retiró su libro, pero la gente seguía trabajando en el problema. El resultado a largo plazo fue el desarrollo de Zermelo-Frankel la teoría de conjuntos, que la mayoría de los matemáticos utilizan como la base fundamental de su trabajo hoy en día. Dispone de diferentes axiomas que permiten demostrar la existencia de conjuntos correspondientes a los números naturales, los números reales, las matrices, las secuencias, y todas las otras estructuras que necesitamos para hacer matemáticas como actualmente lo entiendo. Sin embargo, (y esto no es una rigurosa explicación) son intencionalmente limitado, de manera que usted no puede probar la existencia de un conjunto que contiene a sí mismo, o algo parecido.

También hay que tener en cuenta que, por Gödel del Segundo Teorema de la Incompletitud, es imposible que un sistema formal tanto complejo suficiente para contener la aritmética, y, además, coherente, para demostrar su propia consistencia. Al menos no en un número finito de pasos.

7voto

Wade Mealing Puntos 111

Mientras ya tienes excelentes respuestas, me permito recordar que significa simplemente "implica de $x$ $y$" "$\neg x$ o $y$". Por lo tanto el teorema Estados $\neg(A\text{ and }\neg B)\text{ or }\neg C$, que es equivalente a $\neg(\text{$A$ and $\neg B $ and $C $})$. Y lo que has hecho exactamente es derivar una contradicción del $A$ y $\neg B$ y $C$, por lo que esto demuestra el teorema.

Por supuesto, es posible que $\neg(\text{$A$ and $\neg B$ and $\neg C $})$ también es cierto, que mostraría $\neg(\text{$A$ and $\neg B $})$.

2voto

NicNic8 Puntos 1207

Similar a lo que Wofsey comentó, una declaración debe ser true o false. Te preguntarás qué sucede si tenemos axiomas contradictorios. Es decir, ¿qué pasa si asumimos A y no A? Resulta que luego puede probar cualquier declaración con estos supuestos.

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