¿Cuando es la prueba por pedido bien preferible a prueba por la inducción?

Question

Ejercicio 1: Demostrar que para $n=1,2,3,\ldots$ tenemos $P(n).$

Prueba: $P(1)$ puede ser visto para ser cierto porque bla, bla, bla. Si $n$ es cualquier valor que $P(n)$ es cierto, entonces podemos afirmar que la etc. etc. y ver que $P(n+1)$ también debe ser cierto. Así que por el principio de inducción matemática, el resultado deseado deben tener.

Ejercicio 2: Uso el buen orden de $\mathbb N$ a demostrar que para todos los $n\in\mathbb N$, $P(n).$

Prueba: Supongamos que el resultado deseado es falso. Luego de algunos $n\in\mathbb N$, $P(n)$ debe ser falsa. Deje $n$ ser el más pequeño miembro del $\mathbb N.$ Desde $P(n)$ es falso, el siguiente argumento muestra que $P(n-1)$ también es falso. Pero eso contradice la minimality de $n$.

¿Qué ejemplos muestran que el método es preferible en algunos casos y el otro en algunos otros casos? ¿Hay alguna en la que el segundo método es más sencillo que el primero?

Answer 1

En el caso de declaraciones del formulario $\forall n \in \mathbb{N}. P(n)$, las dos técnicas de prueba son equivalentes. Pero bien ordenada la inducción es una técnica de prueba mucho más general, podemos usarlo para probar los resultados de la forma $\forall n \in S. P(n)$ para cualquier conjunto ordenado $S$. De hecho, la técnica también se aplica a la clase de ordinales (que no es un juego pero puede ser bien ordenado).

Answer 2

Si sólo estamos hablando de $ \mathbb{N} $, la segunda prueba que siempre es la prueba del principio de inducción, así que los dos son equivalentes.

En cuanto a qué estilo se utiliza, yo diría que el primer estilo es preferible, sobre todo porque esconde los detalles técnicos de por qué que sostiene el principio de inducción y permite que concentrarse en la prueba real.