el propósito de la inducción

Question

Después de obtener una respuesta (en un comentario), de pedro para esta pregunta tengo una pregunta de seguimiento.

Si, en todos los caballos son del mismo color del problema, por ejemplo, tenemos que usar la razón, razón por la cual es específica para el caso, con el fin de encontrar ese "agujero" entre la base correcta del caso y el correcto paso inductivo. Ese "agujero" donde n=2, en que se hace la prueba de colapso.

Entonces, ¿cómo podemos comprobar que nuestra hipótesis es correcta, y que no hay "agujeros"?

Me refiero a que si hemos demostrado en el caso base p(0) o p(1) o p((int)lo que sea) es verdadera y el paso inductivo es verdadero, ¿cómo puede estar seguro de que no hay "agujeros" en la hipótesis?

Hacemos uso de la inducción sólo para demostrar lo que sabemos, más allá de cualquier duda, es cierto? Pero eso no contradice el propósito de una prueba?

Sé que esta es una pregunta de Novato.. pero he buscado respuestas para estas preguntas específicas y no pude encontrar..

Muchas gracias a todos!

Answer 1

La inducción requiere de dos ingredientes: en Primer lugar, debemos demostrar que $p(0)$. Entonces, debemos demostrar que $p(n)$ implica $p(n+1)$. Si podemos hacer esto, entonces estamos seguros de que no hay agujeros en nuestro argumento.

El problema con la prueba en cuestión es que, a pesar de que nos demuestran $p(1)$, nuestra prueba de que $p(n)$ implica $p(n+1)$ es malo. Tratamos de probar esta como:

Dado un conjunto de $n+1$ caballos y dos caballos $A$$B$, y el aviso de que, por hipótesis, $A$ es del mismo color que cada caballo en el conjunto excluyendo $B$ y $B$ es del mismo color que cada caballo en el conjunto excluyendo $A$.

Lo que es bueno hasta ahora, pero si se intenta entonces a la conclusión de que esto implica que todas las $n$ caballos son del mismo color, nos silencio invocar la condición de que no debe ser un caballo de $C$ otros de $A$ $B$ a la que se compara cada uno. Esto implica $n+1\geq 3$, por lo que sólo hemos demostrado que $p(2)$ implica $p(n)$ todos los $n$ (lo cual es evidentemente cierto; si todos los pares de caballos son del mismo color, esta prueba inductiva y correctamente demuestra que todos los caballos que sería).

Esta no es la declaración de que nos íbamos a probar. Queríamos $p(n)\rightarrow p(n+1)$ para todo n. Por lo tanto, no puede invocar la inducción - como puede ver, no hay ninguna manera para nosotros para llegar desde nuestra base de casos $p(1)$$p(2)$. Nunca hemos demostrado que: $$p(1)\rightarrow p(2)$$ lo que significa que la inducción no es aplicable.

El problema es que el argumento no sigue las reglas de la inducción y por lo tanto no funciona. No existe un método general para comprobar si una prueba de que no es puramente simbólico funciona y tienes razón que nuestro argumento podría tener agujeros de la que no somos conscientes, pero esto se aplica a una prueba de nada. Si pensamos que nuestra prueba de que $p(n)\rightarrow p(n+1)$ trabajaba, se habría ya se ha equivocado, ya que la $p(1)\rightarrow p(2)$ es falso - y no necesitamos de inducción a ser mal allí. Más bien, el problema de tener agujeros en la prueba es un problema, independientemente de qué técnica utilizar.

Answer 2

Noción clásica de pruebas de matemáticas es esencialmente finitary, es decir, cada prueba matemática es sólo un fragmento finito de palabras (así como los escribimos en un papel). La mayoría de los naturales o modelo estándar de la aritmética (Aritmética de Peano) es la estructura de los números naturales, donde la distancia entre 2 números sólo es finito. Por lo tanto, el principio de la inducción en los números naturales es realmente coherente con la finitary la naturaleza de las pruebas.

Por ejemplo, supongamos que usted tiene pruebas para p(0), y cualquier n p(n) $\rightarrow$ p(n+1), el camino natural para probar que p(10) de por sí es probar que p(1) con p(0) $\rightarrow$ p(1) y p(0) (aplicar el modus ponens), entonces p(2),p(3) etc. Luego concatenar las (finito) de las pruebas para obtener una prueba de p(10). En el proceso, cada paso nos aseguramos de que no hay un "agujero" en ella.

Ahora, si nos fijamos en la no-estándar de los modelos de la Aritmética de Peano: http://en.m.wikipedia.org/wiki/Non-standard_model_of_arithmetic, entonces la inducton principios vuelto más complicado ya que la intuición no siempre ascensor. Por ejemplo, supongamos $M\models PA$ ser no estándar, a continuación, el principio de la inducción básicamente le dice que no es definible de corte, es decir, $I\subsetneq M$ $I$ se cierra a la baja y cerró en virtud de la función sucesor. Por lo tanto, cada corte es bastante complejo, en este caso (estándar de números naturales de la forma de corte y, obviamente, no es de primer orden de la fórmula que define). Para más información sobre modelos de PA y restringido de inducción, Richard Kaye libro es un clásico.

Answer 3

Si el caso base es correcta y la implicación $n\rightarrow n+1$ es correcto PARA TODOS $n$ ($\ge$ un determinado tresh-hold), luego de la inducción es correcta y demuestra que el reclamo.

No siempre es fácil, a ver si la implicación es realmente adecuado para todos los $n$. Así, en algunos casos, el caso base debe ser elegido algo más alto, aunque la "la pereza" de muchos matemáticos conduce al hecho de que el caso base es principalmente $n=0$ o $n=1$.

Para comprobar la implicación de las necesidades de un cuidadoso análisis, como el "caballo de ejemplo".

Answer 4

Puede resultar declaraciones inductivamente de la que usted no sabía antes de ser verdadera o falsa.

Solo debes asegurarte de que no haya un "agujero" en tu prueba. En el caso de su ejemplo, el problema se produjo porque la prueba del paso inductivo era simplemente errónea. Pero si comprueba que tanto p (0) como el paso inductivo pueden demostrarse formalmente correctos , su prueba será válida y no tendrá que buscar "agujeros" después.

Answer 5

En realidad, el principio de inducción es un axioma que se selecciona para cuidar de que el conjunto de todos los números naturales sea el más pequeño posible de todos los candidatos:

$(0\in M\wedge\forall n\in M(n\in M\implies n+1\in M))\implies \mathbb N\subseteq M$.

El axioma se usa para probar que ciertas condiciones$p(n)$ son verdaderas para todos los números que son elementos en el conjunto definido$\mathbb N$, por$M=\{n\in \mathbb N|p(n)\}$.