Preguntas: Demuestre cuidadosamente el Principio de Inducción de Cauchy: Supongamos $P(n)$ es una propiedad que número natural $n$ puede o no tener. Supongamos que
Entonces $P(n)$ es válido para cualquier número natural $n 2$ .
Supongamos que no es cierto.
El número entero más pequeño $m\geq2$ debe existir con $\neg P(m)$ y es fácil demostrar en base a (a), (b), (c) que $m\geq4$ .
Entonces también $\neg P(m+1)$ y una de $m$ y $m+1$ es par y puede escribirse como $2k$ donde $k$ es un número entero que cumple $2\leq k<m$ .
Entonces también $\neg P(k)$ pero esto contradice la minimalidad de $m$ .
La prueba se haría por inducción estándar con ayuda de a)b)c) entonces creo.
Desde $P(2)$ se cumple según a) ya se ha dado el primer paso del argumento estándar de Inducción.
Por b) podemos deducir entonces de $P(2)$ que $P(4)$ también tiene.
De P(4) concluimos aplicando c) que P(3) se cumple.
El último paso sería derivar el paso de inducción estándar $P(n)\Rightarrow P(n+1)$ .
Supongamos que $n\geq 3\ $ $P(n)$ se mantiene, entonces $P(2n)$ se mantiene según b).
Por lo tanto, aplicando sucesivamente c) ( $P(k)\Rightarrow P(k-1)$ ) empezando por $k=2n$ tras un número finito de $n-1$ pasos a los que llegamos $n+1$ y concluir que $P(n+1)$ tiene
Por inducción estándar se puede demostrar que $P(2^k)$ es válida para cualquier $k$ .
Caso base: Se mantiene para $P(2)$ y caso inductivo: Si $P(2^k)$ también $P(2^k)$ .
Para cada número natural $m\ge 3$ existe una $k$ para que $2^k \le m < 2^{k+1}$ y $k \ge 2$ .
Como ocurre con $2^{k+1}$ y $2^{k+1}> 3$ entonces se cumple para $2^{k+1}-1$ e inductivamente de $2^{k+1} -(2^k - m)$
Si esa última línea le parece floja, considérelo.
Sea $Q_k(m)$ sea la afirmación " $P(2^{k+1}-m)$ si $2^{k+1}-m) \ge 3".
Caso base: Si $m=0$ entonces $P(2^{k+1})$ es verdadera como hemos demostrado anteriormente por lo que $Q_k(0)$ es cierto.
Caso base: Si $Q_k(m)$ es cierto, entonces $P(2^{k+1}-m)$ es verdadera y $P(2^{k+1}-m-1)= Q_k(m+1)$ es cierto.
Y ya está. Es cierto para todos $n=2^k$ y $n=2^{k+1}$ y todos $n: 2^k \le n \le 2^{k+1}$ . Así ocurre con todos los $n \ge 2$ .
Existe este principio general de inducción:
Teorema ( Inducción bien fundada ): Sea $X$ sea un conjunto y $R \subseteq X \times X$ una relación binaria bien fundada. Entonces para un predicado $P\colon X \to \text{bool}$ si tenemos $$\forall x. (\forall y. y\ R\ x \Rightarrow P(y)) \Rightarrow P(x)$$ entonces tenemos $\forall x. P(x)$ .
Definición ( Relación fundada ) Una relación se denomina bien fundada si no existen cadenas descendentes infinitas, es decir, si no existen $x_1, x_2, \ldots$ tal que $x_{n+1}\ R\ x_n$ para todos $n$ .
Ejemplo: Sea $X = \mathbb{N}$ y $R$ sea la relación tal que $\forall n. n\ R\ (n+1)$ . Se puede verificar (informalmente sobre el papel) que esta relación está bien fundada. Entonces la fórmula interna de la hipótesis principal, a saber $$\forall y. y\ R\ x \Rightarrow P(y)$$ es vacío para $x = 0$ (tiene que mostrar $P(0)$ en la fórmula circundante de forma ad hoc) y se convierte en $P(x-1)$ para todos $x \geq 1$ . En total, obtenemos $$P(0) \wedge \forall x \in \mathbb{N}_{\geq 1}. P(x-1) \Rightarrow P(x)$$ Este es el principio de inducción habitual en números naturales.
Si confías en este principio, es fácil demostrar tu teorema: Establece $X = \mathbb{N}_{\geq 2}$ y $R$ como sigue:
El primer punto relaciona cada número con su número duplicado. El segundo relaciona cada número par con el número uno menor. Por ejemplo $2\ R\ 4, 4\ R\ 6, \ldots$ y $2\ R \ 1, 4\ R\ 3, \ldots$ . Esta relación está bien fundamentada porque las cadenas descendentes tienen el siguiente aspecto: podemos saltar hacia abajo números pares por la primera viñeta o podemos saltar de un número impar uno hacia arriba a un número par y luego hacia abajo números pares.
Ahora sí que cumplimos la hipótesis principal del teorema: $$\forall x. (\forall y. y\ R\ x \Rightarrow P(y)) \Rightarrow P(x)$$ Es decir, incluso para $x$ por tu segunda suposición del post original. Y para impar $x$ por tu tercera suposición del post original. Por lo tanto, se cumplen los supuestos del teorema y podemos concluir $\forall x. P(x)$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
