¿Qué es la inducción?
En su núcleo, la inducción es esta declaración:
Tomar un conjunto $S$. Si $1 \in S$, e $k \in S$ implica que el $k + 1 \in S$, entonces todos los números naturales son en $S$.
Intuitivamente, esto es bastante obvio. Suponga que ambas hipótesis: que $1 \in S$$k \in S \implies k + 1 \in S$.
- Es $1 \in S$? Sí, por supuesto.
- Es $2 \in S$? Sí, porque $1 \in S$, e $1 \in S$ implica $1 + 1 \in S$.
- Es $3 \in S$? Sí, porque sólo se mostraron $2 \in S$, e $2 \in S$ implica $2 + 1 \in S$.
- $\ldots$
Que claramente no era una prueba formal de que la inducción es válido, pero es un buen lugar para comenzar su intuición. No importa qué número natural que empezamos a " podemos "paso atrás" por uno hasta que llegamos a $1$, que sabemos que es verdadero.
Espera, ¿cómo los conjuntos de llegar allí?
Normalmente, la gente no habla de conjuntos cuando se trata de la inducción. Generalmente, se trata de proposiciones. Pero las dos son equivalentes, considerar el conjunto $S = \{ n \mid P(n) \}$ o de la proposición $P(n) = n \in S$. Si usted está trabajando con las proposiciones, la inducción se expresa como:
Tome una proposición $P$. Si $P(1)$ es cierto, y $P(k)$ implica que el$P(k+1)$, $P(n)$ es cierto para todos los $n \in \mathbb{N}$.
¿Cómo hacemos inductivo pruebas?
Como cualquier instrucción condicional, todo lo que necesitas hacer es probar las dos hipótesis:
- $1 \in S$ (en el caso base)
- Si $k \in S$, $k + 1 \in S$ (en el caso recursivo)
o de proposiciones,
- $P(1)$ (en el caso base)
- Si $P(k)$, $P(k + 1)$ (en el caso recursivo)
La parte confusa
El paso recursivo a veces confunde a la gente. "No estamos suponiendo que lo que quieres demostrar?" No del todo. Aquí, una comprensión exacta de enunciados condicionales que se requiere. Si yo digo, "Si hoy es viernes, mañana es sábado", yo soy no diciendo que hoy es viernes. Sólo estoy diciendo que, si podemos mostrar hoy es viernes, entonces sabemos que mañana es sábado.
Es el mismo con el paso recursivo. Estamos probando: "si $P$ es cierto para $k$, entonces también es cierto para $k + 1$". No hemos dicho nada acerca de si o no $P(k)$ es verdad!
Además, no estamos asumiendo $P$ es cierto para todos los $k$, sólo estamos asumiendo que es cierto para un determinado $k$. En la notación, el paso recursivo es:
$$\forall k \in \mathbb{N} \ (P(k) \implies P(k + 1))$$
Por último, la inducción no es el proceso de la prueba de los dos estados. Aquellos que puede ser probada como cualquier otra instrucción. La inducción es la afirmación "si estas dos declaraciones son verdaderas, $P$ es verdadera para todos los números naturales".
Un ejemplo
Queremos mostrar que $\sum_{i = 1}^n i = \frac{n(n+1)}{2}$. (En términos de conjuntos, esto sería "todos los números naturales en el conjunto de $\{ n \mid \sum_{i = 1}^n i = \frac{n(n+1)}{2} \}$, pero por lo general, la proposición de la sintaxis es más fácil).
"$P$ es cierto para $1$" es bastante fácil de ver, sólo tienes que conectarlo y verificación.
El caso recursivo no es mucho más difícil. Suponga que $\sum_{i = 1}^k i = \frac{k(k + 1)}{2}$ es cierto para algunos $k$. Luego, mediante la adición de $k + 1$ a ambos lados, obtenemos $\sum_{i = 1}^{k+1} i = \frac{(k + 1)(k + 2)}{2}$. Por eso, $P(k) \implies P(k+1)$.
Desde $P(1)$$P(k) \implies P(k + 1)$, luego, por inducción, $P(n)$ es cierto para todos los $n$.
Fuerte de inducción
La inducción descrito anteriormente se llama "débil de la inducción". Fuerte inducción es cuando su recursiva hipótesis es reemplazado con "si $P$ es cierto para todos los $i$ menos de $k$, $P$ es cierto para $k$". La justificación es similar, excepto para demostrar que $P(k)$ es true, se puede ver en cualquier $i$ menos de $k$, no sólo a $k - 1$. Se llama fuerte debido a que su hipótesis es más fuerte, usted puede mirar más $i$.
A veces este formato es más fácil de usar que la debilidad de la inducción. Como un ejemplo, nos muestran que todos los números naturales puede ser escrito como $2^a m$ donde $m$ es impar. El caso base es fácil, $1 = 2^0 \cdot 1$.
Para el caso recursivo: vamos a $k \in \mathbb{N}$ y asumir que $P(i)$ es cierto para todos los $i < k$. Si $k$ es impar, hemos terminado. Si no, hay algunos $i < k$ tal que $2i = k$. Por hipótesis, $i = 2^a m$ algunos $a, m$ donde $m$ es impar. Por lo tanto, $k = 2^{a + 1} m$.
Desde $P(1)$$\forall i < k \ P(i) \implies P(k)$, por la fuerte inducción, $P(n)$ es cierto para todos los $n \in \mathbb{N}$. Esto sería difícil con la debilidad de la inducción.
¿Por qué es válido?
Arriba, una intuitiva argumento para la inducción fue mostrado. Pero en matemáticas nos gusta probar cosas. Para ello, se introduce el "principio de orden": todos los no vacía de subconjuntos de a $\mathbb{N}$ tiene un menor elemento.
Principio de buena ordenación, la debilidad de la inducción, y el fuerte de inducción son todos equivalentes!
Usted puede tomar uno de ellos como un axioma, o usted puede probar uno por lo que la construcción de la $\mathbb{N}$. Entonces, hay bastante simples pruebas para demostrar la equivalencia de los tres.
Bien ordenar implica débil de inducción: Supongamos $S$ ser un conjunto, donde $1 \in S$, e $k \in S \implies k + 1 \in S$. Deje $T = \mathbb{N} \setminus S$, es decir, todos los números naturales no $S$. Suponga $T$ no está vacía. Por el bien de pedido, tiene al menos un elemento, $k$. Claramente no puede ser $1$, debido a $1 \in S$. Así debe ser mayor que $1$, y por lo $k - 1 \in \mathbb{N}$. Desde $k$ es el elemento más pequeño en $T$, $k - 1$ no puede ser en $T$, lo $k - 1 \in S$. Pero por supuesto, que implica la $(k - 1) + 1$$S$, y por lo $k \in S$, lo que se contradice con que $k \in T$. Por lo tanto, $T$ estaba vacía después de todo, y por lo $\mathbb{N} \subseteq S$.
Débil de la inducción implica una fuerte inducción: Supongamos $P(k)$ ser una proposición donde $P(1)$ e si $P(i)$ todos los $i < k$,$P(k)$. Deje $Q(n)$ ser la proposición "$P(k)$ es cierto para todos los $k < n$". Vamos a utilizar débil de inducción en $Q$. En primer lugar, tenga en cuenta que $Q(1)$ es cierto. A continuación, supongamos que $Q(n)$ es cierto. Eso significa que $P(i)$ es cierto para todos los $i < k$, y por tanto, por nuestra descripción inicial de $P$, $P(n + 1)$ es cierto. Pero desde $Q(n)$ $P(n + 1)$ son verdaderas, $Q(n + 1)$ es cierto. Por lo tanto, las condiciones para la debilidad de inducción están satisfechos, y $Q(n)$ es cierto para todos los $n$. Esto claramente significa que $P(n)$ es cierto para todos los $n$.
Fuerte inducción implica bien de pedido: Vamos a $P(n)$ ser la proposición "si $n \in S$, $S$ tiene al menos un elemento". Claramente es cierto para $1$, porque si $1 \in S$, $1$ es el menor elemento de a $S$. Para el paso recursivo, suponga que $P(i)$ es cierto para todos los $i < k$. A continuación, queremos mostrar que $P(k)$ es cierto. Deje $k \in S$. Si $k$ es el elemento más pequeño, entonces hemos terminado. Si no, entonces hay algo de $i < k$ tal que $i \in S$. Por lo tanto, $P(i)$ es cierto, y lo $S$ tiene un menor elemento. Por la fuerte inducción, si hay cualquier $n \in S$, entonces tiene al menos un elemento (esto es, donde el "no vacío" parte de los cultivos).
Que una de estas pruebas que usted necesita depende de lo que su construcción de $\mathbb{N}$ o de los axiomas que usted tiene.
