B.3: Inducción Fuerte
( \newcommand{\kernel}{\mathrm{null}\,}\)
En el principio de inducción discutido anteriormente, probamosP(0) y también siP(k), entoncesP(k+1). En la segunda parte, asumimos que esoP(k) es cierto y utilizamos esta suposición para probarP(k+1). Equivalentemente, por supuesto, podríamos asumirloP(k−1) y usarlo para probarP(k) —la parte importante es que podamos llevar a cabo la inferencia de cualquier número a su sucesor; que podamos probar la pretensión en cuestión para cualquier número bajo el supuesto que ostente para su predecesor.
Existe una variante del principio de inducción en la que no sólo asumimos que la reclamación se sostiene para el predecesork−1 dek, sino para todos los números menores quek, y utilizamos esta suposición para establecer el reclamo parak. Esto también nos da el reclamoP(n) para todosn∈\Nat. Por una vez que hemos establecidoP(0), con ello hemos establecido queP sostiene para todos los números menores que1. Y si sabemos que siP(l) por todosl<k, entoncesP(k), sabemos esto en particular parak=1. Entonces podemos concluirP(1). Con esto hemos demostradoP(0) yP(1), es decir,P(l) para todosl<2, y como tenemos también el condicional, siP(l) por todosl<2, entoncesP(2), podemos concluir P(2), y así sucesivamente.
De hecho, si podemos establecer el condicional general “para todosk, siP(l) para todosl<k, entonces”P(k), ya no tenemos que establecer,P(0) ya que de ello se desprende. Porque recuerda que un reclamo general como “para todosP(l)”l<k, es cierto si no los hayl<k. Este es un caso de cuantificación vacia: “todos losA s sonB s” es cierto si no hayA s,\lforallx(A(x)\lifB(x)) es cierto si nox satisfaceA(x). En este caso, la versión formalizada sería “\lforalll(l<k\lifP(l))” —y eso es cierto si no la hayl<k. Y sik=0 ese es exactamente el caso: nol<0, de ahí “para todosP(0)”l<0, es cierto, lo queP sea. Una prueba de “siP(l) para todosl<k, entoncesP(k)” así se establece automáticamenteP(0).
Esta variante es útil si establecer el reclamo para no sek puede hacer para simplemente confiar en el reclamo parak−1 sino que puede requerir la suposición de que es cierto para uno o másl<k.