Dado que básicamente lo que hacemos es demostrar que p(k) => p(k+2) o p(k+1) => p(k+2) y así sucesivamente simplemente agregando un par de pasos base. ¿Estoy en lo correcto aquí? Eso es lo que me parece a mí. Por favor, corríjame si estoy equivocado
Respuestas
¿Demasiados anuncios?
Sí, si pruebas algo mostrando que un contraejemplo mínimo necesariamente llevaría a un contraejemplo aún más pequeño (y por lo tanto, contradicción), eso es lo mismo que el principio de inducción.
A menudo la misma prueba se puede formular fácilmente como una prueba por inducción o como una prueba de contraejemplo mínimo. Sin embargo, también sucede que uno de los dos se adapta de forma más natural, y el otro sería mucho más incómodo de escribir. Por ejemplo, piensa en la conocida prueba de que $\sqrt{2}$ es irracional, donde asumes que $\sqrt{2} = \frac{p}{q}$ sin factores comunes (por lo tanto, un par mínimo entre todos los posibles $p,q$), y luego deduces que en realidad tanto $p$ como $q$ tienen que ser pares, por lo que puedes dividir ambos por $2$ y el contraejemplo no es mínimo después de todo. Podrías reescribir esta prueba como una prueba por inducción, pero se vería incómoda y más difícil de entender.
jmans
Puntos
3018
Sí, tu intuición es correcta. La forma precisa de formular (y demostrar) tu afirmación es que el principio de inducción es equivalente al principio de buena ordenación de $\mathbb N$, es decir, que todo subconjunto no vacío de los números naturales tiene un elemento más pequeño. La demostración no es en absoluto difícil.
