Demasiado simple para probar?

Question

Puede ser un problema demasiado simple para probar completamente de una manera o de la otra?

Es una pregunta que me he estado preguntando a mí mismo por un poco de tiempo ahora.

He estado jugando con algunos problemas de matemáticas que (a primera vista) parece ser simple, pero, por desgracia,las respuestas a estos problemas se les han escapado todos.

También, soy nuevo aquí, así que estoy tratando de comprometerse con la comunidad,y por lo que me gustaría plantear una pregunta.

A lo largo de las líneas de:

Puede un entero no ser par o impar?

Primera vez que lo lees es obvio, "no se puede no tiene que ser un o el otro", estoy de acuerdo con esa declaración, pero ¿cuál es la prueba?

Mirando hacia adelante a conversar a continuación.

Answer 1

Como ya hay una prueba interesante por Hagen von Eitzen para su impar/integer problema, no voy a dar otro. En lugar de ello quiero hablar de la cuestión general de tu post:

Hay un montón de declaraciones de uno de los encuentros que está "claro" y "no requieren de prueba". Por ejemplo supongamos $A,B$ ser conjuntos. Entonces es claro a partir de la definición de los dos conjuntos, que $A\cap B\subset A$$A\cap B\subset B$. Algo Similar puede decirse acerca de $A\subset A\cup B$, $A\setminus B\subset A$ etc.

En mi opinión, las sentencias y las pruebas en un libro como "es clara/de esta manera se sigue directamente de la definición/Obviamente tenemos..." se puede leer como un reto para demostrar estas declaraciones a ti mismo. Sólo entonces se puede estar seguro de que usted entiende los fundamentos de lo que se trata.

Mientras que usted sólo tiene un tiempo limitado durante una conferencia y puede parecer más importante no cubrir esas pruebas simples, cada una de las declaraciones que aún necesita ser demostrada. Esto es donde usted comienza a hacer matemáticas, sentado y con rigor, demostrando incluso la más simple de las declaraciones que parecía tan obvio de vuelta en la escuela (¿por Qué es $0\times a =0$ en un campo? Que debe ser verdad porque lo multiplicamos con el cero, pero no es una prueba para la que es bastante difícil para un estudiante principiante).

Esto se aplica no solamente a simples declaraciones, pero también pasó por ejemplo a los de la curva de Jordan teorema. La declaración en sí es muy simple y puede ser entendido sin saber nada acerca de la matemática: basta con dibujar un plano, una simple curva cerrada y puede explicar el significado del teorema. Demostrar este resultado evidente parecía innecesario hasta (creo que fue Bolzano) observó, que la declaración no es auto-evidente. Y la prueba en sí es bastante difícil y requiere de matemáticas avanzadas (normalmente se llega a ver la prueba después de tomar un curso en análisis complejo).

Answer 2

Definición 1. Deje $n$ ser un número entero. Decimos que $n$ es incluso si existe un entero $k$ tal que $n=2k$.

Definición 2. Deje $n$ ser un número entero. Decimos que $n$ es impar si es que no aún.

Teorema. No hay ningún número entero que no es par o impar.

Prueba. Suponga $n$ es un número entero que no es par o impar. En particular, $n$ es un número entero que no es uniforme. Por definición, 2, $n$ es impar, la contradicción! $\square$

---

Comentario: Esto demuestra que no soy un intuitionist, cf. por ejemplo, https://en.wikipedia.org/wiki/Brouwer%E2%80%93Hilbert_controversy#Validity_of_the_law_of_excluded_middle

Answer 3

Un entero $\,n\,$ es par o impar, ya que, por el algoritmo de la división, $\,n\,$ tiene un único resto $0$ o $1$ cuando se divide por $2$. Por definición, $\,n\,$ es incluso si tiene resto $0$ e impar si tiene resto $1$.

Del mismo modo muchos otros simplemente declaró los problemas tienen muy corta, pruebas simples. Pero esto no implica que todos simplemente-afirmó problemas necesariamente tienen pruebas simples. De hecho, como usted menciona no son simples problemas abiertos, tales como la Collatze conjetura que han eludido la prueba.

Es una falsa suposición simple (corto) declaraciones cortas pruebas. Esto se puede refutar fácilmente utilizando sólo una lógica rudimentaria. Para cualquier sistema formal que ha trivial de energía (por ejemplo, la aritmética de Peano) no hay ningún algoritmo recursivo que decide theoremhood. Esto implica que no es recursiva límite en la longitud de las pruebas (si $\,L(n)\,$ límites de la longitud de las pruebas de una declaración de longitud $\,n,\,$ entonces podríamos prueba para theoremhood simplemente enumerando y probar todas las posibles pruebas de longitud de $\,\le L(n)).\,$ por lo Tanto existen corto-dijo teoremas con pruebas tan inmensamente largo que probablemente no son susceptibles de comprensión humana (estos resultados se remontan a Goedel 1936 papel en la aceleración del ritmo de teoremas).

Queda por ver si existen matemáticamente interesante teoremas como este. Puede haber ejemplos en Collatz-como congruential iteraciones (similar a la difícil abrir $3 x+1$ problema) que fueron descubiertos en la naturaleza, mientras que el análisis de Busy Beaver exclusión de las máquinas (al intentar encontrar el más pequeño universal máquinas de Turing). John Conway, ha demostrado que existe similares simple congruential iteraciones con indecidible detener problema. Que tal indecidible problemas pueden ser codificados de manera sucinta en los programas para pequeñas máquinas de Turing no debe venir como una sorpresa para cualquiera que esté familiarizado con la por encima de la simple los resultados de la lógica. Ellos son un testimonio del poder de ingenio - ya sea humano (en matemáticas poderosas teorías) o la naturaleza (el basado en el ADN de los programas diseñados por la evolución).