¿Por qué es la inducción matemática una prueba válida de la técnica?

Question

Contexto: estoy estudiando para mi matemáticas discretas examen y sigo corriendo en esta pregunta, que yo no hemos podido solucionar. La pregunta es la siguiente.

---

Problema: La principal forma normal de inducción sobre los números naturales $n$ tiene la siguiente forma:

1. $P(1)$, es cierto, y
2. por cada $n, P(n-1)\a P(n).\qquad\qquad\qquad\text{[a Veces escrito como $P(n)\P(n+1)$]}$

Si 1 y 2 son verdaderas, entonces $P(n)$ es verdadera para todo $n$.

La pregunta es para probar la exactitud de la forma anterior.

---

Mi trabajo: Mi idea era hacer una expresión booleana y si es una tautología en un verdadero falso de tabla. Eso significa que el enunciado es siempre correcta.

He intentado muchas veces, pero he fallado.

Aquí está la pregunta original en hebreo:

n טענה כלשהי לגבי מםפר טבעי $P(n)$ תהי

אם מתקימיים שני התנאים הבאים:

1 - הטענה $P(0)$ נכונה

2 - לכל n>0, $P(n)$ נכונות הטענה $P(n-1)$ גוררת את נכונות הטענה

אז $P(n)$ נכונה לכל מספר טבעי n

הוכיחו את נכונות משפט זה

Answer 1

Considere la siguiente definición de la inducción matemática (adaptado de David Gunderson libro Manual de Inducción Matemática):

---

Principio de la matemática induciton: Para algunos fijos entero $b$, y para cada entero $n\geq b$, vamos $S(n)$ ser una declaración relacionada con $n$. Si

1. $S(b)$ es cierto, y
2. para cualquier entero $k\geq b, S(k)\S(k+1)$,

entonces para todo $n\geq b$, la declaración $S(n)$ es cierto.

---

La inducción matemática de la validez como prueba válida técnica puede ser establecida como una consecuencia de un axioma fundamental sobre el conjunto de enteros positivos (nota: esta es sólo una de las muchas posibles formas de visualización de la inducción--véase el apéndice al final de esta respuesta). La siguiente declaración de este axioma es una adaptación de Juan Durbin del libro de Álgebra Moderna, en donde es llamado el Mínimo Entero Principio, pero se refiere a menudo como el Bien-Principio de orden o WOP. El principio es el siguiente:

Bien-Principio de orden: Todo conjunto no vacío de enteros positivos contiene al menos un elemento.

La validez de la inducción matemática, en este contexto en el que estamos utilizando el WOP para demostrar la validez de la inducción matemática, se establece mediante una prueba por contradicción. Esta prueba se contienen varios "pasos" o "partes". Antes de dar todos los pasos para la prueba de la inducción matemática, puede ser útil para reformular la definición de la prueba técnica en términos de la notación que se usará a lo largo de la secuencia de pasos en la explicación (por consistencia y facilitó la comprensión):

---

Reformular el principio de inducción matemática: Para algunos fijos entero $1$, y para cada entero $n\geq 1$, vamos $S(n)$ ser una declaración relacionada con $n$. Si

1. $S(1)$, es cierto, y
2. para cualquier entero $k\geq 1, S(k)\S(k+1)$,

entonces para todo $n\geq 1$, la declaración $S(n)$ es cierto.

Dejar 1 y 2 anteriores se denota por $(\daga)$ y $(\daga\daga)$, respectivamente.

---

Los pasos de la prueba de que la inducción matemática es una consecuencia de la WOP:

1. Empezar por suponer que $S(1)$ es verdadera y que la proposición $S(k) \rightarrow S(k+1)$ es verdadera para todos los enteros positivos de $k$, es decir, donde $(\daga)$ y $(\daga\daga)$ celebrar como se ha indicado anteriormente.

2. El objetivo es comprobar si o no $S(n)$ es verdadera para todo $n \geq 1$ si $S(1)$ y $S(k) \rightarrow S(k+1)$ son verdaderas. La declaración de la inducción matemática anterior indica que $S(n)$ se deriva lógicamente si $S(1)$ y $S(k) \rightarrow S(k+1)$ son verdaderas, pero sí $S(n)$ realmente seguir si $(\daga)$ y $(\daga\daga)$ son verdaderas? Si sí, entonces la inducción matemática es una prueba válida de la técnica. Si no, entonces es mera basura.

3. Somos escépticos, y pensamos que la inducción matemática es una farsa (sugerencia: una prueba por contradicción que va a tener lugar). Nuestro escepticismo nos induce a suponer que existe al menos un entero positivo para el cual $S(n)$ es falsa [tenga en cuenta que estamos suponiendo que $(\daga)$ y $(\daga\daga)$ son verdaderas, aunque estamos disputando si o no $S(n)$ realmente sigue de la verdad de sus palabras]. Seguramente existe al menos un entero positivo para el cual $S(n)$ es false, aunque $S(1)$ y $S(k) \rightarrow S(k+1)$ son verdaderas.

4. Deje que $\mathcal{P}$ denota el conjunto de todos los enteros positivos para los cuales $S(n)$ es falso. Es este conjunto vacío? Creemos que no---después de todo, estamos suponiendo que existe al menos un entero positivo, decir $\ell$, de los cuales $S(n)$ es falsa; es decir, la suposición es que $S(\ell)$ es falsa, donde $\ell \in \mathcal{P}$. Hay otros números enteros positivos en $\mathcal{P}$? Tal vez, pero no podemos decir con certeza en el momento. Sin embargo, podemos declarar con certeza que $\mathcal{P}$ tiene al menos un elemento por el principio de orden. Dejamos que el menor elemento de $\mathcal{P}$ $\ell$ sin pérdida de generalidad.

5. Desde $S(1)$ es cierto, sabemos que $\ell \neq 1$, y debido a que $\ell$ es positivo y mayor que $1$, también sabemos que $\ell -1$ debe ser un entero positivo. Por otra parte, debido a que $\ell -1$ es menor que $\ell$, debe quedar claro que $\ell -1$ no puede ser de $\mathcal{P}$ [esto es debido a que $\ell$ es el menor elemento en $\mathcal{P}$, lo que significa que cualquier menor entero positivo no puede estar en $\mathcal{P}$]. Notationally, tenemos que $\ell \in \mathcal{P}$ y $(\ell - 1) \noen \mathcal{P}$. ¿Qué significa esto? Desde $(\ell - 1) \noen \mathcal{P}$ y $\ell -1$ es un número entero positivo, y debido a que $\mathcal{P}$ es el conjunto de todos los enteros positivos para los cuales $S(n)$ es falsa, debe ser que $S(\ell-1)$ es cierto.

6. Por último, recordar que hemos mantenido que $(\daga\daga)$ era cierto; es decir, $S(k) \rightarrow S(k+1)$ es cierto para cualquier entero $k \geq 1$. Desde $\ell$ y $\ell -1$ son ambos enteros positivos, podemos dejar que $k = \ell -1$ y $k+1 = \ell$. Sustituyendo estos valores en la implicación de que asumimos para ser verdad, obtenemos que $S(\ell-1) \rightarrow S(\ell)$. ¿Ve usted el problema ahora (y, por tanto, la conclusión de la prueba por contradicción)?

7. Suponiendo que $(\daga)$ y $(\daga\daga)$ mantenidos mientras que también suponiendo que $S(n)$ era falso, para algún entero positivo de $\ell$, hemos deducido a través de una serie de pasos que $S(\ell-1) \rightarrow S(\ell)$ [$(\daga\daga)$ donde $k = \ell -1$ y $k+1 = \ell$]. ¿Qué hay de malo con esto? Simplemente considere los siguientes tres afirmaciones que se producen dentro de la prueba:

   • $S(\ell-1)\(\ell)\qquad$ [True---por supuesto $(\daga\daga)$]
   • $S(\ell)\qquad$ [False---debido a la suposición de que $S(n)$ era falso por $\ell\in\mathbb{Z^+}$]
   • $S(\ell-1)\qquad$ [True---por el principio de orden]

   La lógica problema ahora debe ser evidente. Sabemos $S(\ell-1) \rightarrow S(\ell)$ es cierto por nuestra suposición original, pero esta implicación no puede ser cierto si $S(\ell)$ es falso. Por qué? Porque una implicación de la forma p $\rightarrow q$ sólo es falsa cuando la hipótesis, $p$, es verdadera y la conclusión, $q$, es falso. En nuestro caso, desde $S(\ell-1)$ es cierto, la implicación $S(\ell-1) \rightarrow S(\ell)$ sólo es cierto cuando $S(\ell)$ también es cierto, lo que contradice la elección de $\ell$. En consecuencia, $S(n)$ debe ser verdadera para todo entero positivo de $n$.

---

Addendum: puede ser de interés para los estudiantes que están tomando cursos de matemáticas discretas que la forma de inducción demostrado anteriormente (a menudo denominado simplemente como "inducción") es en realidad equivalente a ambas fuerte de inducción y la WOP. Esto puede ser sorprendente, pero hay un buen artículo sobre la Equivalencia de las Tres Variaciones sobre Inducton para los lectores que estén interesados.

La idea básica detrás de la equivalencia de las pruebas es el siguiente:

1. Fuerte inducción implica la Inducción.
2. La inducción implica una Fuerte Inducción.
3. Buen orden de $\mathbb{N}$ implica la Inducción [Esta es la prueba descritos en esta respuesta, pero con mucho mayor detalle]
4. Fuerte Inducción implica el buen orden de $\mathbb{N}$.

Equivalencia de Inducción, Fuerte de Inducción, y el buen orden en $\mathbb{N}$ de la siguiente manera después de haber probado los cuatro implicaciones descritas anteriormente (el papel vinculado a contiene los detalles de la prueba(s)).

La respuesta que siempre cuida de (3) anterior, pero usted puede explorar los otros tres para mostrar la equivalencia, si se desea.

Answer 2

Tu pregunta parece un poco confuso para mí, tal y como está, pero yo voy a responder a la una en el título, y si la pregunta es actualizado, voy a tratar de que demasiado.

La inducción matemática se puede tomar como su propio axioma, independiente de la otra (a pesar de que, como comentarios del punto de salida, que puede ser probada como un teorema en común, como los sistemas de ZF). Es decir, es más afín a las declaraciones de: $$x\cdot (y+1)=x\cdot y + x$$ que a menudo se toma para ser parte de la definición de la multiplicación y no puede ser derivable de más básicas de las declaraciones. El punto detrás de esas definiciones es la de captar una idea intuitiva - el de arriba comienza a capturar la propiedad distributiva de la multiplicación, que sabemos a partir de la intuición de una idea razonable. Sin embargo, es posible que no podríamos probar la afirmación anterior sin tomar esto como un axioma.

Inducción básicamente dice que todo número natural puede ser "engañado" a partir de cero. Es decir, si hemos probado las declaraciones:

• $P(1)$ es cierto
• $P(n)\rightarrow P(n+1).$

Entonces, podemos construir una prueba para cada número natural. Por ejemplo, si queremos saber que $P(5)$ era cierto, podríamos inferir que, desde $P(1)$ es verdadera y $P(1)\rightarrow P(2)$ tenemos $P(2)$. Pero $P(2)\rightarrow P(3)$ y $P(3)\rightarrow P(4)$ y $P(4)\rightarrow P(5)$, por lo tanto podemos deducir $P(5)$. Inducción simplemente dice que $P(n)$ debe ser verdadera para todos los números naturales, ya que podemos crear una prueba como la de arriba para cada natural. Sin la inducción, podemos, para cualquier natural $n$, crear una prueba para $P(n)$ - inducción sólo formaliza y dice que nos permite saltar de allí a $\forall n[ P(n)]$.

Answer 3

Si se siente extraño que una prueba contundente de la técnica ha sido colocado, casi como hacer trampa, en la definición de los números naturales, uno debe tener en cuenta que la inducción sólo es válida en el modelo formal. Hay una ambigüedad en nuestra mente, en donde podremos mezclar los números que hemos obtenido a partir de la realidad con los objetos en el slick modelo de Peano.

La inducción es una parte importante de la definición del modelo de los números naturales. Si uno omite el axioma de inducción a partir de los axiomas de Peano, $\Bbb$ N no está bien definido y conjuntos mayores que pueden satisfacer los axiomas.

El axioma de inducción asegura que $\Bbb$ N es el conjunto mínimo que satisface los otros axiomas.

Para ver esto, vamos a $P(n)\ffi n\N$, donde $N$ satisface los otros axiomas de Peano. Entonces el axioma de inducción de estados:

$0\N$ y $(n\N\implica n+1\N)$ implica que para todo $n\in\Bbb N$ se tiene que $n\in$ N. Es decir, $\Bbb N\subseteq$N.

También, el mínimo de $\Bbb N \implica$ principio de inducción.

Si no podemos usar los axiomas para la demostración de teoremas, creo que no se puede demostrar.

Answer 4

Formalmente, la inducción es un axioma o una consecuencia de los otros axiomas.

De manera informal, puede ser visto como similar a una prueba por contradicción, tal vez algo como:

Deja $$ n ser el valor más pequeño para el que $P(n)$ es falso.

A menos que $n$ es el menor valor posible en $\mathbb{N}$ (es decir, $1$, o si prefiere $0$), sabemos que $P(n-1) \implica P(n)$, así que si $P(n)$ es falso también lo es de $P(n-1)$ de contradecir la definición de $n$.

Mientras tanto $$ n no puede ser el menor valor posible en $\mathbb{N}$, como sabemos que $P(1)$ era cierto.

Answer 5

La inducción matemática es, definitivamente, la oveja negra de común métodos de prueba.

Común de los métodos de prueba incluyen:

• La prueba por contradicción
• Prueba directa
• Prueba por el agotamiento de
• Prueba por inducción

No estoy seguro de qué más de una geometría de la escuela secundaria libro de texto podría discutir, pero vamos a ir con eso. Los tres primeros se refieren a todos los de la lógica. El cuarto pertenece a los números naturales.

¿Está usted de acuerdo...

que cada subconjunto de los números naturales $S$ que

• contiene 1, y
• si contiene algún número $a$, entonces $+1$

debe ser que los números naturales?

Entonces usted cree que la prueba por inducción funciona.

Que es la prueba por inducción. Dicen que quieren demostrar que $1+\cdots+n=\frac{(n)(n+1)}{2}$ para todos los números naturales $n$. A continuación, vamos a $S$ el conjunto de todos los números (!!) donde la propiedad es true (!!). Ahora prueba por inducción se ve exactamente igual que bastante agradable propiedad de los números naturales ya he declarado anteriormente.