Por el Bien del Argumento

Question

Por lo tanto, alguien me envió este xkcd como una respuesta a algo que me dijo en línea:

https://xkcd.com/1432/

Yo francamente sintió asaltado por la cultura pop monstruo. Tal vez como un matemático no es infrecuente.

Mi pregunta es, en matemáticas que a menudo son las cosas por la contradicción. Por ejemplo, tal vez la mejor manera conocida para demostrar que $\sqrt{2} \notin \Bbb{Q}$. Esta prueba es, lo que me parece, bien conocidos. En que muchas personas la han visto en la escuela secundaria.

Mi pregunta es: ¿hay otros ejemplos bien conocidos de pruebas a través de la contradicción (hasta el momento) que son comúnmente conocidos? Supongo que, en una especie de refutación a la idea de que sólo los mentirosos asumir las cosas para el bien de discutir sobre ellos.

Si usted considera que esta pregunta demasiado amplia, podría utilizar una referencia de tales resultados o un buen libro acerca de ellos, etc.

Answer 1

La primera pregunta es, ¿qué quiere usted decir que usted DEBE probar las cosas por la contradicción? La única cosa que usted posiblemente puede decir, es que hay cosas que se puede demostrar sin prueba por contradicción, es decir, sin algunas de las reglas de la lógica que normalmente tomamos por sentado. ¿Qué es exactamente lo que queremos decir con esto?

En la lógica clásica, es un teorema que prueba por contradicción se tiene: para cualquier declaración de $P$ si $\lnot P$ implica $Q$$\lnot Q$,$P$. De este teorema se basa en tres hechos:

1. La ley del medio excluido (LEM): para cualquier $P$, $P$ o $\lnot P$.

2. La ley de la no contradicción (LNC): para cualquier $P$ si $P$$\lnot P$$\bot$. (Este símbolo significa la declaración de que siempre es falsa, leer simplemente como "falsos".)

3. El principio de explosión (PE): para cualquier $P$ si $\bot$$P$.

La prueba del teorema, entonces, va como esto: Suponga que el $\lnot P$ implica $Q$ e no $Q$. Por LEM, $P$ o $\lnot P$. En el primer caso, $P$ y hemos terminado. En el último caso, debido a que $\lnot P$, por nuestra suposición, $Q$$\lnot Q$. Por lo tanto, por LNC, $\bot$, y por el PE, $P$. Así que se hace en este caso es así.

---

Así que, ¿qué se puede hacer sin la prueba por contradicción? Bueno, como el teorema anterior muestra, usted puede conseguir cualquier cosa hecha, siempre y cuando se acepten LEM, LNC, y PE. Pero lo que si usted rechaza estas? Un prominente alternativa a la lógica clásica es intuitionist lógica, que rechaza LEM. En intuitionistic pensamiento, no está permitido demostrar algo por mostrar lo opuesto puede ser cierto. En particular, si usted demuestra que $P$ resultados en una contradicción, lo que significa que $\lnot P$, porque eso es lo $\lnot P$ medios. Pero si usted demuestra que $\lnot P$ resultados en una contradicción, que sólo han demostrado que $\lnot \lnot P$--no ha proporcionado una prueba directa de $P$.

Así, este ha sido un poco rotonda, pero para responder a tu pregunta, ¿cuáles son algunas de las cosas que "necesita" la prueba por contradicción para demostrar? Aquí están algunos ejemplos (me gustaría tener más), en el sentido de que intuitionist la lógica no es suficiente para demostrar que:

• Existe una función que no es continua.

• Existe una incomputable función.

De hecho, (!), demostrando $\sqrt{2}$ es irracional NO requiere prueba por contradicción, como han reclamado; usted puede hacer esto mediante la búsqueda de la continuación de la fracción de $\sqrt{2}$.

---

Vea también:

• Cómo pueden unas declaraciones que ser coherente con intuitionistic lógica, pero no la lógica clásica, cuando intuitionistic lógica demuestra no no LEM?

Answer 2

Si por una prueba, nos referimos a una deducción formal en una de Hilbert del Sistema que obedece clásica de la lógica proposicional, entonces nosotros nunca prueba nada por la contradicción. La razón de esto es que en un sistema de

1. $\phi \rightarrow \psi$
2. $\neg \psi \rightarrow \neg \phi$

seguramente son equivalentes y por lo tanto, cualquier prueba para $\neg \psi \rightarrow \neg \phi$ puede ser extendida a una prueba para $\phi \rightarrow \psi$ y viceversa.

La mayoría de los matemáticos rara vez (nunca) a reflexionar sobre las pruebas de una manera formal, pero están de acuerdo (intuitivamente) en común una lógica de cálculo que permite que la anterior equivalencia. Sin embargo, esto no es cierto de todos los matemáticos y hay otros sistemas lógicos (por ejemplo, intuitionistic lógica) donde 1. y 2. no puede ser demostrablemente equivalente. Por lo tanto, si su definición de una prueba difiere de la mía de una manera sustancial, tendría que proporcionar nosotros con su lógica del sistema y la noción de la prueba, antes de que pudiéramos tratar de responder a su pregunta.

Answer 3

Creo que el principal problema con la contradicción de las pruebas es que pertenecen a un mundo binario donde la cosa es radicalmente cierto o radicalmente falso. Esto funciona muy bien para nuestro formulario de matemáticas, pero en un mundo real, donde las cosas son casi siempre mezclado no funciona bien.

Yo creo que por eso en realidad no alcanzar a otras líneas de pensamiento, desde el sentido común. Supongo que cualquier ejemplo que presentará en la etapa en la que aparecerá como otro "por el bien del argumento".