En la inducción matemática, ¿cómo ¿cómo asumiendo $P(n)$ diferir asumiendo $\forall n : P(n)$?

Question

En la inducción matemática,* una primera prueba en el caso base, $P(0)$, es cierto. En el siguiente paso, se asume la $n$^th el caso de que** es cierto, pero ¿no es esto suponiendo que lo que estamos tratando de probar? No estamos tratando de probar cualquier $n$^th el caso de que** es cierto? Entonces, ¿cómo podemos asumir que este sin el empleo de razonamiento circular?

No estoy preguntando cómo probar la inducción matemática es cierto, pero, ¿cómo la inducción matemática es en conformidad con las reglas de la lógica que no admite razonamiento circular como válida.*** En concreto, me estoy preguntando cómo, en el segundo paso de la inducción, no se asume lo que uno está tratando de probar.

En otras palabras, como @DanielV poner a continuación,

¿cómo asumiendo $P(n)$ diferir asumiendo $\forall n : P(n)$?

---

^{*C. S. Peirce preferido el término "Fermatian inferencia."
**=$(P(n))$ o $(\forall n : P(n))$ en este paso?
***Hay algunas lógicas que admitir razonamiento circular, que Aristóteles refuta en su aristotélicos libro 1, 72b-73un20, "mostrando que la circular de la demostración no es aceptable".}

Answer 1

Hay dos equivalentes formulaciones comunes de la segunda etapa: uno es de suponer que la afirmación es verdadera para $n$ y tratando de demostrar que es cierto para $n+1$. La otra es la de asumir que es cierto para $n-1$ e intente probarlo para $n$. De cualquier manera, no estamos asumiendo que lo que estamos tratando de demostrar, estamos suponiendo que el caso antes de lo que estamos tratando de probar.

Quizás una manera más intuitiva para explicar la técnica de inducción es que estamos demostrando que no hay contraejemplos. Hacemos esto al mostrar que en ningún caso puede ser el de menor contraejemplo; ni en el caso base, ni cualquier caso, después de que. El axioma de inducción que los demás tienen de referencia dice que esta ausencia de un menor contraejemplo es suficiente para concluir que la afirmación es verdadera en todos los casos.

Answer 2

Creo que hay dos, pero, como veremos, distintas de las preocupaciones expresadas por el OP:

A. La hipótesis inductiva que se utiliza en la prueba (débil) de la inducción parece decir exactamente lo que usted está tratando de demostrar con la inducción.

B. Como tal, las pruebas por inducción parecen ser circular.

Permítanme abordar tanto de estas preocupaciones:

Preocupes

No, la hipótesis inductiva es no es la misma que la de la inducción está tratando de probar.

Para ver esto, observe que para el paso inductivo estamos tratando de demostrar que $\forall n (P(n) \rightarrow P(n+1))$.

Hacemos esta dejando $n$ ser arbitraria en el número y, a continuación, suponemos $P(n)$ nuestra hipótesis inductiva (por débil de la inducción, que es). Una vez que a continuación muestran que la $P(n+1)$, llegamos a la conclusión (por condicional de la prueba) que $P(n) \rightarrow P(n+1)$. Y por último, utilizamos universal de prueba para decir que desde $n$ fue arbitraria, $\forall n (P(n) \rightarrow P(n+1))$. Aquí es lo que se ve formalmente:

Observe que la hipótesis inductiva $P(a)$ (lo siento, el software requiere el uso de $a$ en lugar de $n$) que asumimos en la línea 4 es en realidad muy diferente de la afirmación de que $\forall x P(x)$ (de nuevo, lo siento, el software requiere el uso de $\forall x P(x)$ en lugar de $\forall n P(n)$) que en el final de su inductivo de la prueba en la línea 10.

En efecto, si el inductivo hipótesis era que la $\forall n P(n)$, entonces podríamos inmediatamente a la conclusión de que $P(n+1)$! Pero que no pasa de curso. Todos asumimos es que $P(n)$, por lo que tomará un poco de trabajo para ir desde allí a $P(n+1)$.

Preocuparse B

De nuevo, usted no tiene que preocuparse. Por favor, tenga en cuenta la siguiente distinción importante entre dos tipos de supuestos:

1. Suponiendo que algo como una premisa original en el inicio de la prueba

2. Haciendo adicional de la asunción durante la prueba (como parte de, digamos, un condicional prueba o prueba por contradicción).

Si adoptamos $\forall n P(n)$ como una premisa original, entonces sí, estamos haciendo razonamiento circular por el uso que demostrar $\forall n P(n)$.

Pero si asumimos $\forall n P(n)$ adicional de asunción para configurar, por ejemplo, una prueba condicional, entonces todo lo que va a conseguir de que es un condicional de la forma $\forall n P(n) \rightarrow \phi$ $\phi$ de lo que sería capaz de inferir con el uso de esta suposición $\forall n P(n)$. Usted no consigue $\forall n P(n)$, de por sí, fuera de eso, y lo que no, haciendo que no es razonamiento circular ...

Como el esqueleto de arriba muestra, el paso inductivo de la siguiente manera el último modelo, como se supone $P(n)$ como una suposición, no como una hipótesis original.

De hecho, como un caso especial, se podría, por supuesto, a la conclusión de $\forall n P(n)$ sobre la base de la $\forall n P(n)$ dentro de un condicional prueba... pero todo lo que nos daría está en la final es $\forall n P(n) \rightarrow \forall n P(n)$, que es una información menos tautología, y no es en absoluto la misma como $\forall n P(n)$. Asimismo, en la prueba de skeleton arriba, yo podría, por supuesto, inferir $P(a)$ (en lugar de $P(a+1)$) sobre la base de la suposición de $P(a)$, pero todos los que me dan en la final es $\forall x (P(x) \rightarrow P(x))$, que es una vez más una tautología sin sentido.

En suma, entonces, el inductivo suposición no es la misma reivindicación, como la afirmación de que estamos tratando de probar, e incluso si lo fuera, todavía no sería razonamiento circular. Por lo tanto las preocupaciones no son nada de qué preocuparse!

Por último, aunque no hay nada de que preocuparse, sin duda, puedo entender sus preocupaciones acerca de inducción débil, porque se siente como que estamos demostrando que "cualquier arbitrario $n$ propiedad $P$ por en algún punto en el supuesto que algunos arbitraria $n$ propiedad $P$"! Hay tal vez una manera de deshacerse de, o al menos aliviar, esta sensación de circularidad?

En pensar en lo que hay, y para ello, en primer lugar quisiera señalar que la fuerte inducción no tiene esta misma sensación de circularidad, como su inductivo suposición es 'supongamos $P(m)$ es cierto para todos los $m$ menor que $n$'. Es decir, haciendo referencia a los números de otros de $n$, uno no da la sensación de que estamos de alguna manera demostrar que $n$ propiedad $P$ asumiendo $n$ tiene la propiedad P.

Pero aviso que el paso inductivo en la debilidad de la inducción puede ser entendido de esta manera: nos muestran que un número $n$ propiedad $P$ sobre la base de su anterior número de tener la propiedad $P$. Por lo tanto, creo que puede ayudar a aliviar la sensación de circularidad, mediante la caracterización de los débiles inducción paso como ir de $n-1$ $n$($n>0$del curso), en lugar de como ir de$n$$n+1$. Misma idea, por supuesto, pero tal vez un poco más fácil aceptar conceptualmente.

Answer 3

Aquí hay otro ejemplo. Supongamos que se pide establecer "si n es mayor que 10, entonces n es mayor que 5". Parece bastante sencillo.

¿Cuál es la primera cosa que usted hace? Asumir "n > 10". Pero espera, no es que suponiendo que cada número es mayor que 10? No. Lo mismo con la inducción: suponiendo que P(n) no es el mismo que suponiendo que P es válido para cada n, es simplemente restringir su atención a los n para el cual P se mantiene.

La única vez que se puede generalizar a partir de $P(n)$ $\forall n : P(n)$es cuando no hay supuestos que contiene la variable $n$. Que es exactamente lo contrario de lo que usted hace con la inducción: el primer paso es crear una suposición que contengan $n$.

Answer 4

En el paso inductivo, que no demuestran $P(n)$ es cierto para todos los $n$ suponiendo que esto es cierto, puedes probar sólo $$\forall n,\;P(n)\implies P(n+1)$$ que no es la misma cosa.

En realidad, para demostrar la implicación es verdadera, usted como para cualquier implicación $\;A\implies B$ prueba: agregar (temporalmente) $A$ a los axiomas de las matemáticas, y usted deduce $B$ a partir de este terminado el conjunto de axiomas. A partir de las reglas de la lógica matemática, $A \implies B$ está probado.

Answer 5

La no circularidad puede quedar más claro si se mira con más detalle en lo que se demostró, a saber: primero "$P(1)$", y la segunda "para todos los $n$ si $P(n)$$P(n+1)$". Permítanme escribir cuidadosamente algunos de lo que está incluido en la segunda parte:

Si $P(1)$$P(2)$. (Ese es el caso especial donde los $n$ es 1).

Si $P(2)$$P(3)$. (Ese es el caso especial donde los $n$ es de 2.)

Si $P(3)$$P(4)$. (Ese es el caso especial donde los $n$ 3.)

Por supuesto, la declaración general de que fue demostrado, "para todos los $n$ si $P(n)$ $P(n+1)$" incluye infinitamente muchas más implicaciones como las tres que acabo de escribir, pero permítanme, por un tiempo, el trabajo con sólo esos tres implicaciones.

La base de paso, demostró como parte de la inducción de la prueba, se asegura de que $P(1)$ es cierto. Una vez que sabemos que, la primera implicación que escribí, se asegura que, como consecuencia, $P(2)$ también es cierto. Una vez que conocemos $P(2)$, la segunda implicación que escribí, se asegura que $P(3)$ también es cierto. Una vez que conocemos $P(3)$, la tercera implicación asegura que $P(4)$ también es cierto.

Entonces, la base de la inducción y de los tres casos especiales de la inducción paso que yo escribí asegurarse de que todos los cuatro de $P(1),P(2),P(3),P(4)$ son verdaderas, puesto que se puede deducir una después de la otra.

Si yo hubiera sido más paciente y que había escrito diez implicaciones en vez de sólo 3, mediante la inducción de paso para $n$ que va desde 1 hasta 10, luego la misma idea, el uso de las implicaciones uno tras otro, mostraría que $P(n)$ es cierto no sólo para $n$ hasta 4 (como he mostrado anteriormente), pero por $n$ 11.

El uso de más y más casos especiales de la inducción de paso, obtendrá suficiente implicaciones para demostrar $P(n)$ para cualquier número natural $n$ que desee. Por ejemplo, si desea $P(1,000,000)$, entonces usted necesitará utilizar 999,999 de tales implicaciones, una después de la otra.

Este sería conseguir terriblemente aburrido, pero, una vez que vea el patrón general (que espero que mis tres implicaciones han hecho lo suficientemente claro), se puede entender que $P(n)$ debe ser verdadera para todos los números naturales $n$.

El principio de inducción dice que, en lugar de utilizar las implicaciones de una en una para obtener $P(n)$ más grande y más grande $n$ (y la necesidad de una infinidad de pasos para tomar el cuidado de todos los valores de $n$), se puede inferir del patrón general de estas implicaciones que usted podría llegar a cualquier $n$ que desee. En otras palabras, se puede concluir que $P(n)$ es verdadera para todos los números naturales $n$.