Lo siguiente es de Analysis with an Introduction to Proof de Steven Lay
Demuestra el principio de inducción fuerte: Sea P(n)P(n) sea una afirmación que sea verdadera o falsa para cada n∈N siempre que
(a) P(1) es verdadera, y
(b) para cada k∈N Si P(j) es verdadera para todos los enteros j tal que 1 ≤ j ≤ k entonces P(k+1) es cierto.
Prueba.
Definir Q(n):= " P(j) es cierto para 1 ≤ j ≤ n ."
Desde (a) sabemos que Q(1) se mantiene.
Además, sabemos que Q(n) se mantiene ya que P(j) es cierto para 1 ≤ j ≤ n . Así, por (b) , P(n+1) es cierto. De ello se desprende que P(j) es cierto para 1 ≤ j ≤ (n+1) y así Q(n+1) se mantiene.
Por lo tanto, hemos verificado el paso inductivo. Por lo tanto, Q(n) es válida para todos los n∈N Q.E.D.
Me gustaría saber si la prueba que he proporcionado es suficiente y fluye lógicamente. Además, me gusta probar la inducción fuerte sin incorporar el Principio de Ordenamiento Bueno.
0 votos
No veo dónde se puede utilizar el principio de buen orden.
0 votos
En otras pruebas se utiliza el principio de ordenación para demostrar la inducción fuerte por contradicción. Quiero ver cómo demostrar la inducción fuerte utilizando la inducción débil.
1 votos
Tienes la idea correcta, pero probablemente deberías empezar el paso inductivo diciendo: ASUMIR Q(n) se mantiene, y así P(j) se mantiene para j<=n . Entonces .... (etc. como lo hiciste) ... Q(n+1) es cierto. Por inducción ordinaria (débil), Q(n) es válida para todos los n de lo que se deduce que P(n) es válida para todos los n , según se desee.
0 votos
Aquí está mi prueba formal (formato DC Proof) de que la inducción fuerte se sigue de la inducción débil (99 líneas): dcproof.com/StrongInductionHolds.htm
0 votos
@DanChristensen: para la prueba proporcionada, ¿se utiliza alguna lógica específica?
1 votos
@K.M Sólo lógica de predicados clásica y un poco de teoría de conjuntos, del tipo que se utiliza implícitamente en casi todos los libros de texto de matemáticas.
1 votos
@K.M Hay que acostumbrarse a las pruebas formales. Son muy detalladas. De alguna manera, eso hace que sean más difíciles de leer. Cada línea invoca precisamente una regla de inferencia: no se permiten improvisaciones ni atajos, ni "similarmente" ni "y así sucesivamente" ni "obviamente".
0 votos
El enunciado de su teorema no es una frase completa.