La "suposición" en la prueba por inducción

Question

El segundo paso en la prueba por inducción es:

Demostrar que si la afirmación es cierta para algún número entero $n=k$ donde $k\ge n_0$ entonces también es cierto para el siguiente entero mayor, $n=k+1$

Mi pregunta se refiere a la declaración "if". ¿Podemos suponer que la afirmación es cierta? Si lo asumimos, entonces la prueba funciona... pero no es similar a la siguiente "prueba":

Sea $N$ sea el mayor número entero positivo.
Desde $1$ es un número entero positivo, debemos tener $N\ge1$ .
Desde $N^2$ es un número entero positivo, no puede ser mayor que el mayor número entero positivo.
Por lo tanto, $N^2\le N$ y así $N^2-N\le0$ .
Así, $N(N-1)\le0$ y debemos tener $N-1\le0$ .
Por lo tanto, $N\le1$ . Puesto que también $N\ge1$ tenemos $N=1$ .
Por lo tanto, $1$ es el mayor número entero positivo.

Lo único que falla en esta "prueba" es que suponemos falsamente que existe un número entero positivo mayor.

Así que tanto en el caso anterior como en la prueba por inducción hacemos una suposición. En el segundo caso, la suposición lleva a una conclusión falsa. ¿Cuál es la diferencia con la prueba por inducción? ¿Por qué es válida aquí la suposición de que la hipótesis es realmente cierta y por qué no conduce a una contradicción similar?

EDIT: la "prueba" anterior no es mía, está tomada de Cálculo - Curso completo 8ª edición como ejemplo de por qué son importantes las pruebas de existencia.

Answer 1

Tu confusión es que crees que has demostrado algo que no es cierto.

Ha demostrado que

"Si existe un número entero positivo mayor, entonces ese número entero positivo mayor es $1$ "

Es cierto.

Tenga en cuenta que la declaración $$ P \implies Q$$ es falso sólo si $P$ es verdadera y $Q$ es falso

En su caso $P$ es falsa , por lo que su afirmación es verdadera.

Answer 2

De hecho, una conclusión falaz mayo llegar por deducción válida a partir de una premisa injustificable.

Esto es por qué el primero paso de la inducción es pruebe que el predicado está justificado para el caso base; para asegurarnos de que lo hacemos no hacerlo.

Si $\mathcal P(0)$ está demostrado y para todos los números naturales $n$ podemos demostrar que $\mathcal P(n)\to\mathcal P(n+1)$ es demostrable, entonces podemos demostrar sucesivamente $\mathcal P(1)$ , $\mathcal P(2)$ , $\mathcal P(3)$ y así sucesivamente, mediante aplicaciones iterativas de modus ponens .

$${\text{We may soundly prove }\mathcal P(1)\text{ from having proven }\mathcal P(0)\textit{ and }\mathcal P(0)\to\mathcal P(1)\\\text{We may soundly prove }\mathcal P(2)\text{ from having proven }\mathcal P(1)\textit{ and }\mathcal P(1)\to\mathcal P(2)\\\text{We may soundly prove }\mathcal P(3)\text{ from having proven }\mathcal P(2)\textit{ and }\mathcal P(2)\to\mathcal P(3)\\\text{And so forth, and so on,}\textit{ et cetera,}\ldots}$$

Answer 3

El supuesto de la hipótesis inductiva es válido porque has demostrado (en la primera parte de la prueba por inducción, el caso base) que el enunciado $P$ es válido para $n = n_0$ . Así que puedes pensarlo de esta manera: inicialmente, sólo sabes que $P(n_0)$ . Pero esto, junto con su prueba de "si $P(n)$ entonces $P(n + 1)$ ", lo que implica "si $P(n_0)$ entonces $P(n_0 + 1)$ ", permite concluir que $P(n_0 + 1)$ por modus ponens. Otra consecuencia de "si $P(n)$ entonces $P(n + 1)$ es "si $P(n_0 + 1)$ entonces $P(n_0 + 2)$ ", lo que permite concluir que $P(n_0 + 2)$ por modus ponens. Continuando de esta manera, se puede concluir $P(n_0 + k)$ para cualquier número natural $k$ ya que cualquier número natural $\ge n_0$ puede alcanzarse de esta manera utilizando un número finito de aplicaciones del modus ponens.

Answer 4

La prueba por inducción se basa en la siguiente afirmación \begin{aligned} & \left [\mathcal {P}(0) \land \left( \mathcal {P}(n) \implies \mathcal {P}(n+1)\; \forall n\geq 0\right)\right] \\ & \implies \mathcal {P}(n)\; \forall n\geq 0 \, , \end{aligned} donde $\mathcal {P}$ es un predicado sobre los números enteros naturales $\Bbb N$ . Tan pronto como uno ha demostrado la propiedad de la herencia $\mathcal {P}(n) \implies \mathcal {P}(n+1)$ (con el si ) y la inicialización $\mathcal {P}(0)$ entonces $\mathcal {P}(n)\; \forall n$ . Si sólo se demuestra la propiedad de herencia, se pueden obtener resultados tan estúpidos como todos los números enteros naturales son mayores que $\pi$ (predicado correspondiente $\mathcal {P}(n) : n \geq \pi$ ).

Answer 5

Has realizado una prueba por contradicción, no una prueba por inducción, y la hipótesis que has probado, no es la que pensabas.

Lo que realmente argumentaste en tu "prueba":

1. Supongamos que existe un número entero mayor >= 1.
2. Sea N el mayor número entero.
3. Entonces N no puede ser mayor que N^2 (propiedad del "cuadrado" para todos los enteros positivos) y N no puede ser menor que N^2 (contradice los pasos 1+2)
4. Así que N debe ser 1

El paso 1 es como suele empezar una "prueba por contradicción", y el paso 4 es incorrecto. En realidad, los pasos 1 a 3 están bien, sólo que no los has utilizado correctamente.

Esto es lo que debería ocurrir después del paso 3....

Conclusión correcta:

4. Como 1 no es el mayor número entero (2 >= 1, por ejemplo), existe una contradicción, por lo que una de nuestras suposiciones o pasos en 1 - 3 es incorrecto.
5. A primera vista, el paso 2 es una definición simple válida que se deriva del paso 1, y el paso 3 también parece correcto.
6. Por lo tanto, nuestro error es o la propia lógica, o nuestra suposición en el paso 1.
7. Si el paso 1 nos hace llegar a una deducción incorrecta en nuestra lógica, entonces parece que nuestra conclusión debe ser una de 3 cosas: o (A) la propia lógica está rota / es inconsistente, (B) tenemos una muy sutil error lógico, o (C) no hay "mayor entero mayor que 1".

Llegados a este punto, la mayoría de los matemáticos y lógicos dudarán mucho de (A). Comprobarán si (B) es posible. Entonces, al menos en este caso, concluirán rápidamente (C).

Comentario:

Obsérvese que en algunos casos famosos, la conclusión correcta era, en efecto, que la lógica estaba sutilmente equivocada. Esos casos han cambiado la lógica y las matemáticas en el pasado. Pero éste no es uno de esos ejemplos famosos :)