¿Cómo se puede demostrar que la prueba por inducción es una prueba?

Question

Son pruebas por inducción limitada a los casos en que hay un explícito dependencia de un número entero, como sumas? No puedo entender la idea de la inducción de ser una prueba en menos explícito de los casos. Lo que si tiene una función que de repente cambia de comportamiento? Si una función es positiva hasta cierto límite no puedo probar por inducción que siempre es positivo por la partida de mi prueba en la izquierda del límite?

Me siento como que no estoy llegando a una comprensión de algo fundamental y espero que usted me puede ayudar con esto. Gracias.

Answer 1

El título sugiere el desconcierto acerca de la idea misma de una prueba por inducción (tal vez me estoy reconstruyendo mal la pregunta). De todos modos, vamos a tomar el caso más simple, donde queremos demostrar que todos los números naturales tienen alguna propiedad $P.$ lo que, obviamente, no pueden dar por separado pruebas, una para cada una de las $n$,$n$$P$, debido a que sería una tarea sin fin. Entonces, ¿cómo podemos proceder?

Supongamos que podemos demostrar que (i) $0$ tiene algún tipo de propiedad $P$, y también que (ii) si el número tiene la propiedad de $P$ se produce la siguiente: a continuación, podemos inferir que todos los números tienen la propiedad $P$. El uso de $\varphi$ para una expresión de la atribución de alguna de las propiedades de los números, podemos poner el principio, como este:

(I) $\varphi(0)$, y (ii) $\forall n(\varphi(n) \a \varphi(n + 1))$, we can infer $\forall n\varphi(n)$.

Y el título de la pregunta parece ser: ¿por Qué son los argumentos que apelan a este tipo de principio buenos argumentos?

Bueno, supongamos que establecemos tanto en el caso base (i) y la inducción de paso (ii). Por (i) tenemos $\varphi(0)$. Por (ii), $\varphi(0) \to \varphi(1)$. Por lo tanto podemos inferir $\varphi(1)$. Por (ii) de nuevo, $\varphi(1) \to \varphi(2)$. Por lo tanto ahora podemos inferir $\varphi(2)$. Asimismo, podemos usar otra instancia de (ii) para inferir $\varphi(3)$. Y así sucesivamente y así sucesivamente, correr tan lejos como nos gusta a través de los sucesores de $0$ (es decir, a través de los números que puede ser alcanzado por empezar de cero, y en varias ocasiones la adición de uno). Pero los sucesores de $0$ son los únicos números naturales. Así que para cada número natural $n$, $\varphi(n)$.

La aritmética principio de inducción está asegurado, entonces, por la estructura básica de la secuencia numérica, y en particular por la ausencia de 'callejeros' números que usted no puede conseguir a paso-por-paso desde cero mediante la aplicación y volver a aplicar la función sucesor.

Tanto para el caso más simple. Pero los principios subyacentes más llamativos son los argumentos inductivos (de no más números pero el correo.g estructurales inducciones o transfinito inducciones) son lo suficientemente similares como para convertirse en claro si son muy claros acerca de este caso sencillo. Lo crucial, en cada caso, será encontrar una adecuada inducción paso que dice que una cierta propiedad se transmite de 'predecesores' a 'sucesores', y así las ondas a través de la totalidad de la de dominio.

Answer 2

Todas las formas de inducción matemática $-$ ordinario de la inducción, el llamado fuerte de inducción estructural de inducción, inducción transfinita, etc. $-$ puede resultar útil pensar de la siguiente manera, en términos de la no-existencia de un mínimo contraejemplo al teorema está demostrado. Este punto de vista hace que sea más fácil para evitar el error de pensar en la inducción como un proceso secuencial de algún tipo.

Tengo algunos de la colección de $A$ de los objetos y de algún tipo de ordenamiento de los objetos, lo que voy a denotar por $\preceq$, que tiene la siguiente propiedad:

$(*)\quad$ si $C$ es no-vacío es subconjunto de a $A$, hay un $c_0\in C$ que es mínima con respecto a $\preceq$, lo que significa que si $c\in C$$c\preceq c_0$,$c=c_0$. En otras palabras, ningún elemento de $C$ es estrictamente menor que $c_0$ con respecto a la referencia $\preceq$. Equivalentemente, si $a\in A$$a\prec c_0$,$a\notin C$. (Aquí se $a\prec c_0$ es corto para $a\preceq c_0\text{ and }a\ne c_0$.)

Hay alguna propiedad que los objetos en las $A$ podría poseer; llamarlo $P$. Quiero demostrar que todos los $a\in A$ propiedad $P$, por lo que lo dejo $B=\{a\in A:a\text{ does not have }P\}$ y asumir que $B\ne\varnothing$; mi objetivo es el de obtener una contradicción, ya que implicará que $B$ debe ser en realidad vacía y, por tanto, que todos los $a\in A$$P$.

Yo primero aplique $(*)$ $B$a la conclusión de que hay un $b_0\in B$ $\preceq$- mínimo: si $a\in A$$a\prec b_0$,$a\notin B$. Si usted piensa de $B$ como el conjunto de los 'malos' de los objetos, lo que significa que no tienen la propiedad de $P$, $b_0$ es un mínimo de mala objeto: los objetos anteriores en el orden en que son 'buenas', lo que significa que tienen la propiedad de $P$. Luego me muestran que

$(\dagger)\qquad\qquad\quad$ si $a\in A$, y cada una de las $a'\prec a$ propiedad$P$,$a$$P$.

Mis mínimos "malo" elemento $b_0$ satisface la hipótesis de $(\dagger)$: cada $a\prec b_0$ propiedad $P$. Por lo tanto, $(\dagger)$ implica que el $b_0$ propiedad $P$, y tengo mi contradicción.

El argumento puede resumirse de la siguiente manera. La naturaleza de la $A$ $\preceq$ significa que si mi teorema (que cada $a\in A$$P$) es falsa, debe haber un mínimo de contraejemplo, $b_0$. Pero soy capaz de demostrar $(\dagger)$, lo que implica que no puede haber un mínimo de contraejemplo. Por lo tanto, no puede haber ningún contraejemplo a todos, y el teorema por lo tanto debe ser cierto. Muchas pruebas por inducción en la configuración más avanzada son en realidad redactado de esta manera: Supongamos que el resultado es falso, y deje $\text{thing}$ ser de un mínimo de contraejemplo. Entonces ....

Ordinario de inducción $A$ es típicamente $\{n\in\Bbb Z:n\ge m\}$ para algunos fijos entero $m$. A menudo,$m=1$$A=\Bbb Z^+$, pero los ejemplos se presentan generalmente muy temprano para demostrar que la inducción no tiene que comenzar en $1$. El pedido de $\preceq$ es simplemente ordinario $\le$ sobre los enteros: si $C$ es cualquier subconjunto no vacío de a$\{n\in\Bbb Z:n\ge m\}$, $C$ tiene un mínimo elemento, por lo $(*)$ está satisfecho. (De hecho, $C$ incluso tiene un mínimo elemento.) La inducción de paso está demostrando $(\dagger)$ $a\in A$ que en realidad tienen un predecesor en $A$, y la base es el paso de la prueba por el $a\in A$ que no tiene predecesor. (Si $A=\{n\in\Bbb Z:n\ge m\}$, el único elemento de $A$ sin predecesor es $m$.)

Nota técnica: $(*)$ es un poco informal declaración de la exigencia de que el orden parcial $\langle A,\preceq\rangle$ estar bien fundada.

Answer 3

El Principio de Inducción Matemática es equivalente a la Bien-Principio de orden, que dice que todo conjunto no vacío de enteros positivos tiene al menos un elemento. Usted asume (como un axioma de su sistema de número) del PMI y demostrar WOP a partir de esta suposición, o viceversa.

Answer 4

La inducción es normalmente definido para el caso en el que de forma explícita la dependencia de un número entero (o un número ordinal transfinito de inducción, pero no voy a hablar de eso). No estoy seguro de lo que estás hablando con la función, pero ya que la inducción requiere que usted para demostrar que $P(k)\Longrightarrow P(k+1)$ todos los $n$, usted no será capaz de "probar" que la función estaba en todas partes positivas, debido a que la instrucción $P\Longrightarrow P(n+1)$ podría fallar en el punto donde se cruza el límite de punto'.

Se puede demostrar que la prueba por inducción es una prueba de la siguiente manera:

Supongamos que tenemos que $P(1)$ es cierto, y $P(k)\Longrightarrow P(k+1)$ todos los $n\ge 1$. A continuación, supongamos por contradicción que existe cierta $m$ tal que $P(m)$ es falso. Vamos $S=\{n\in \mathbb{N} : P(k) \text{ is false}\}$. $S$ no está vacía (ya que contiene $m$), por lo que tiene al menos un elemento de a $s$ (La declaración de que todo conjunto no vacío de números naturales tiene al menos un elemento es conocido como el Pozo Principio de orden).

Ahora, desde la $P(1)$ es verdadero, $s\neq 1$. Por lo $s-1$ es un número natural. Ahora, si $s-1$ fuera verdadera, entonces el $P(k)\Longrightarrow P(k+1)$ implicaría que $s$ eran verdaderas (ajuste $k=s-1$). Desde $s$ no es cierto, $s-1$ no debe ser cierto. Pero $s-1<s$, y lo había imaginado $s$ a ser el menor número natural $n$ tal que $P(n)$ no era cierto. Así que tenemos una contradicción.

Por lo tanto, $P(n)$ es cierto para todos los $n\ge 1$.

Resulta que en realidad es un análogo de la inducción que puedes utilizar si quieres demostrar que una afirmación es verdadera para todos los números reales. No se puede aplicar el argumento anterior a los números reales, los números reales no satisfacen el Bien de Pedido Teorema. Por ejemplo, el conjunto $\{1,0.1,0.01,0.001,\dots\}$ no tiene un menor elemento. Tampoco se $\{x\in \mathbb{R} : x>3\}$. Sin embargo, los números reales que satisfacen lo que se conoce como el Mayor límite Inferior de la propiedad. Esto significa que cada conjunto de números reales que está delimitada por encima tiene un mayor límite inferior. Por ejemplo, el conjunto de los números reales que son mayores que las de $3$ no tiene menos de elemento: si usted toma algún número mayor que $3$ - $3.001$, decir - puedo decirle a otro número que es mayor que $4$ pero aún menos de su número (como $3.0001$). Pero tiene un mayor límite inferior, que es $3$. El conjunto $\{x\in\mathbb{R} : x^2 > 2\}$ no tiene ningún elemento menos, pero tiene un mayor límite inferior, que es $\sqrt{2}$.

Ejercicio: ¿cuál es la mayor cota inferior para el conjunto $\{1,0.1,0.01,0.001,\dots\}$?

En general, un límite inferior de un conjunto es un número $b$ que es menor que la de cada elemento en el conjunto. El Mayor límite Inferior de la Propiedad es la declaración de que cada vez que tienes un límite inferior, siempre hay una mayor baja obligada. Se denota el mayor límite inferior de un conjunto $S$ por $\inf S$ ($\inf$ es corto para infimum, otra palabra para mayor límite inferior).

¿Cómo podemos utilizar el Mayor límite Inferior de la Propiedad para formar un análogo de la inducción? Te voy a dar la instrucción de continuo inducción primero, y luego probarlo.

Teorema Deje $P(x)$ ser una declaración acerca de un número real arbitrario $x$. Supongamos que conocemos los dos siguientes hechos:

• $P(x)$ siempre es verdadera si $x<y$ donde $y$ fijo es un número real.
• Si $P(x)$ siempre es cierto hasta cierto número de $c$ (siempre que $x<c$), entonces, para algunos $\varepsilon > 0$, $P(x)$ es cierto siempre hasta el $c+\varepsilon$ (siempre que $x<c+\varepsilon$).

A continuación, $P(x)$ es verdadera para todos los números reales $x$.

La prueba es similar a la prueba para que la natural-número de la inducción:

Prueba: Supongamos por contradicción que, para algún número real $z$, $P(z)$ es falso. Deje $A=\{x\in \mathbb{R} : P(x) \text{ is false}\}$. Desde $P(x)$ es cierto para todos $x<y$, $y-1$ es un límite inferior para $A$. Desde $z\in A$, $A$ no está vacía. Por lo $A$ tiene un mayor límite inferior $a=\inf A$. Ahora, si $x<a$, $P(x)$ es cierto (como $a$ es un límite inferior para $A$, el conjunto de los números reales $x$ tal que $P(x)$ es falso). Por lo tanto, para algunos $\varepsilon > 0$, $P(x)$ es cierto para todos los $x<a+\varepsilon$. Por lo tanto, $a+\varepsilon$ es un límite inferior para $A$. Pero $a+\varepsilon>a$, y lo había imaginado $a$ a ser el mayor límite inferior de $A$. Así que tenemos una contradicción.

Por lo $P(x)$ es verdadera para todos los números reales $x$.

Esta es realmente la misma cosa como prueba por inducción para los números enteros, pero con la máxima límite Inferior de Propiedad en lugar del Bien Principio de orden. Vale la pena mencionar que tengo nunca tuve ocasión de uso continuo de inducción sobre los números reales, y no es una norma técnica: los matemáticos tienden a demostrar afirmaciones acerca de los números reales directamente de la Mayor cota Inferior Principio, y a no utilizar cualquiera de lujo trucos (como lo puede hacer cualquier prueba por inducción en una prueba donde se intenta encontrar un "mínimo contraejemplo', como lo hice yo cuando he demostrado que funciona la inducción de arriba). Pero es muy divertido, y es muestra de que se puede generalizar a cosas como el principio de la inducción a la más general, establece, siempre y cuando usted tiene una declaración similar a la Bien Principio de orden.

Answer 5

Esta matemática.SE pregunta que tiene una gran cantidad de respuestas tan lejos como la inducción sobre los reales va. Y como Austin se mencionó, existen muchos casos en la teoría de grafos donde se puede utilizar la inducción en los vértices o aristas de un grafo para demostrar un resultado. un ejemplo:

Si cada dos nodos de $G$ están unidos por un único camino, a continuación, $G$ está conectado y $n = e + 1$ Donde $n$ es el número de nodos y $e$ es el número de aristas.

$G$ se conecta desde cualquiera de los dos nodos están unidos por un camino. Para mostrar $n = e + 1$, hacemos uso de la inducción. Supongamos que es cierto para menos de $n$ puntos (esto significa que estamos usando la fuerte inducción). Quitar cualquier borde de $G$ rompe $G$ en dos componentes, ya que las rutas son únicos. Supongamos que los tamaños son de $n_1$$n_2$, con $n_1 + n_2 = n$. Por la hipótesis de inducción, $n_1 = e_1 + 1$$n_2 = e_2 + 1$; pero, a continuación,$$n = n_1 + n_2 = (e_1 + 1) + (e_2 + 1) = (e_1 + e_2) + 2 = e − 1 + 2 = e + 1$$

Así que nuestra afirmación es verdadera por la fuerte inducción