8 votos

¿Es la inducción algo que tomamos por fe?

Entiendo que en las matemáticas y la lógica nos puede seguir para reducir las cosas más simples axiomas, principios, etc, y tenemos que "dejar" en algún punto de lo contrario sólo estamos yendo para siempre. Finalmente nos dicen que un axioma o principio es lo suficientemente bueno, así que aceptamos que sea válida, la verdadera, útil, sensible, y así sucesivamente.

Dicho esto, mi pregunta es si la inducción matemática es uno de estos "fundamentales" a los conceptos que acaba de aceptar, o si se desprende de algunos, incluso, más profunda o más simple concepto.

A veces veo a gente decir que funciona porque de principio de buena ordenación de los números naturales, pero esto no me satisface. En el Tao del Análisis de Vol I, podemos decir $m \leq n$ (para los números naturales $m$ e $n$) iff $m = n + a$ para algún número natural $a$. Pero entonces, si yo quería demostrar que cualquier conjunto arbitrario de números naturales tiene un mínimo elemento" (la definición de la bien-principio de orden), me gustaría recurrir a la inducción, que es lo que estoy tratando de "probar".

¿Significa esto que el concepto de inducción es sólo algo que todos aceptan como uno de esos suficientemente simple, intuitiva cosas que no requieren una prueba más, que viene de no más simple significa?

11voto

Matt Dawdy Puntos5479

Mi punto de vista es el mismo que en los días de Noé primer comentario: para mí, la inducción es parte de la esencia de lo que quiero decir cuando hablo de los números naturales, por lo que la cosa llevo a la fe no es que la inducción es cierto, pero que los números naturales "existe", lo que eso significa. Los axiomas no dicen de qué llevar en la fe: son una manera de que dos personas están de acuerdo que estamos hablando de la misma cosa.

Algunas personas llaman ultrafinitists en algún sentido negar que los números naturales existen.

Aquí es un blog que describe en detalle el sentido en el que los axiomas de Peano son una manera para que dos personas están de acuerdo que significan lo mismo por "los números naturales."

5voto

La pregunta, más bien supone que es una recta elección, "dar una prueba más de axiomas" vs "tomar en la fe". Pero no es así. Podemos ofrecer el razonamiento que muestra por qué la inducción es convincente, por qué se vincula con la concepción misma de la serie natural (lo que estamos haciendo más que hacer un salto de fe en la aceptación del principio de la inducción), pero donde este razonamiento no es una cuestión de deducir el principio de inducción de algunos de los más fundamentales axioma.

Volver a lo básico. Supongamos que queremos demostrar que todos los números naturales tienen alguna propiedad $P.$ Nosotros obviamente no se puede dar por separado pruebas, una para cada una de las $n$que $n$ ha $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? Es sólo una cuestión de fe?

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.

Ahora, la ausencia de 'callejeros' números (no inductiva números, si te gusta) no es una cuestión de conjeturas o de la fe. No es que tengamos una clara concepción de los números naturales que deja abierta la cuestión de si existen números naturales que no son sucesores de cero -- y tenemos que dar un salto en la oscuridad y la esperanza para el mejor en el juicio de que no hay tal! Más bien, en la aclaración de lo que queremos decir por el número natural de la serie (y la distinción de que, por ejemplo, a partir de largas series de números ordinales) se explica, precisamente, que lo que estamos buscando son los números a los que puede llegar a paso-por-paso desde cero mediante la aplicación y volver a aplicar la función sucesor. Y luego, como se ha explicado, el principio de la inducción puede ser visto sólo una elaboración de la comprensión de lo que cuenta como los números naturales.

2voto

user21820 Puntos11547

Peter Smith respuesta es correcta, pero parece que no entienden la lógica de lo suficientemente bien como para entenderlo. Por lo tanto, voy a explicar de una manera diferente:


Supongamos que usted cree que no hay tal cosa como el conteo de número de $1$ (ya sea como una forma concreta de codificación en algún medio físico, tales como un ordenador, o si como una noción abstracta), y que usted puede añadir repetidamente $1$ a sí mismo para obtener más números de contar, que se denota mediante "$+$" para la adición. Así por ejemplo, puedes obtener los números de contar $1$ e $1+1$ e $1+1+1$ y así sucesivamente. Supongamos que usted también considerar como el conteo de los números de las entidades a las que se puede obtener por este proceso. Esto significa que para que a alguien para convencerle de que tiene un conteo de número de $n$, se tiene que, literalmente, te mostrará que es de esa forma. Para su comodidad también se incluyen "$0$" como contar el número tal que $0+1 = 1$.

Suponiendo que esas creencias, se puede analizar lo que la inducción dice (cuando interpretarse como una afirmación acerca de números de contar). Dado cualquier propiedad $P$ de un recuento de la cantidad que se puede describir, la inducción afirma que si usted puede probar que $0$ satisface $P$, y se puede demostrar que ( para cualquier número a contar $n$ satisface $P$, también tiene que $n+1$ satisface $P$ ), a continuación, se puede concluir que cada número a contar satisface $P$.

¿Por qué debemos aceptar esto? Supongamos que no suponga la inducción. Entonces todo lo que usted puede probar es: $ \def\nn{\mathbb{N}} \def\imp{\Rightarrow} $

$P(0)$.

$\forall n \in \nn\ ( P(n) \imp P(n+1) )$.

$P(0) \imp P(0+1)$. [$\forall$-elim]

$P(0+1)$. [$\imp$-elim]

$P(1)$.

$P(1) \imp P(1+1)$. [$\forall$-elim]

$P(1+1)$. [$\imp$-elim]

$P(1+1) \imp P(1+1+1)$. [$\forall$-elim]

$P(1+1+1)$. [$\imp$-elim]

...

Usted, evidentemente, puede ver que para cualquier expresión de $E$ que representa un número a contar, usted puede probar $P(E)$. Por lo que es seguro (según sus creencias) para concluir "$\forall n \in \nn\ ( P(n) )$", pero usted no puede llegar a esta conclusión sin la inducción! Tú mismo puedes comprobar que ninguna de las reglas en cualquier sistema deductivo permiso a "salir fuera", el sistema y observar lo que usted puede probar y luego "volver a entrar" con algunos externo conclusiones.

Que es lo que la inducción da; la capacidad de transferir un determinado tipo de meta-razonamiento lógico en el sistema. Que tipo? Exactamente por encima de la clase. Es por eso que tenemos un axioma de inducción para cada propiedad $P$. También, por las razones arriba mencionadas para que sea significativa, debemos ser capaces de escribir explícitamente abajo $P$. Para más detalles, vea este post.


Ahora que he explicado por qué la inducción realmente tiene sentido y no es un ad-hoc de la asunción, a tu pregunta de si es fundamental sigue siendo. En este nivel, basta decir que la inducción es fundamental y no puede ser no-circularmente justificado. Ver este post en el 'circularities" en matemáticas, el cual menciona la repetición como uno de los principales circularities'. La repetición puede decirse que es el núcleo de la noción de inducción. Si usted no entiende la repetición, no repetida explicación puede ayudar a comprenderlo. =)

Pero si quieres, no hay una concreta justificación de por qué la inducción no puede ser no-circularmente justificado. Los axiomas de la PA$^-$ están satisfechos, no sólo los números de contar, pero también la colección de $P$ que comprende el cero del polinomio plus entero polinomios cuyo mayor grado de un término que tiene coeficiente positivo. Puedes comprobar por ti mismo que $\nn$ satisface "cada elemento es par o impar", sino $P$ ¿ no. Específicamente:

"$\forall n \in \nn\ \exists k \in \nn\ ( n=k·2 \lor n=k·2+1 )$" es verdadera.

"$\forall n \in P\ \exists k \in P\ ( n=k·2 \lor n=k·2+1 )$" es falsa.

Además, y fundamentalmente, la PA puede comprobar esta afirmación (por $\nn$). Así tenemos un ejemplo claro de un hecho básico que no puede ser probado por el PA sin el uso de la inducción.


[Más avanzadas notas.]

Por supuesto, un seguimiento de la cuestión sería si sólo tenemos un número finito de inducción de los axiomas. En el caso de la PA, la respuesta es no, pero este hecho no puede ser explicado simplemente. La esencia de una explicación es para mostrar que la PA se puede demostrar la consistencia de cada fragmento finito de PA, y, por tanto, por el teorema de la incompletitud de Gödel no finito fragmento de PA es tan poderoso como el todo.

Usted puede formular preguntas similares acerca de cuáles son las principales suposiciones filosóficas que sustentan más fuertes y más fundamental de los sistemas. Para un breve esbozo de PA ACA, vea este post y el artículo enlazado por Peter Smith en los comentarios. Algunos lógicos que se sienta incómodo en algún lugar entre ACA y lleno de segundo orden aritmética Z2, debido a la aparente circularidad en impredicative definiciones de subconjuntos de a$\nn$. Pero incluso si uno se siente cómodo con la iteración powersets, hay aún más la suposición de que hay que tomar en fe (sin ningún no-justificación circular como el de hoy) antes de poder llegar a ZFC, tales como la sustitución completa. Alternativa fundacional sistemas tienen su propia cuota de (y potencialmente diferentes) suposiciones filosóficas.

1voto

CallMeLaNN Puntos111

Es la inducción algo que nos tomamos en la fe?

Si usted va a conceder la existencia de un conjunto infinito $M$ (tal vez no es tan grande de un salto de la "fe"), entonces usted puede construir, es decir, demostrar la existencia del conjunto de los números naturales $N$ (como un subconjunto de a$M$) en el que todos los Axiomas de Peano, incluyendo la Inducción se llevará a cabo.

El uso de la Dedekind la definición de un conjunto infinito, con $M$ ser un conjunto infinito, tenemos una función de $S: M \to M$ e $n_0 \in M$ tal forma que:

$$\forall a,b \in M:[S(a)=S(b) \to a=b]$$

$$\forall a\in M: S(a)\neq n_0$$

El uso de los axiomas de la teoría de conjuntos, entonces podemos construir $N\subset M$ tal forma que:

$$N=\{ n_0, \space S(n_0), \space S(S(n_0)), \space S(S(S(n_0))) \cdots \}$$

Más formalmente:

$$\forall a: [a\in N \iff a\in M \land \forall b\subset M: [n_0\in b \land \forall c\in b: [S(c)\in b] \implies a\in b]]$$

(Se puede sustituir por $0$ para $n_0$ si usted se siente cómodo usando las constantes de esa manera. No debería causar ningún problema.)

Utilizando sólo las reglas de FOL, también podemos a continuación se derivan de cada uno de los Axiomas de Peano (ver mi prueba formal, el comentario en la fuente azul):

PA1: $n_0 \in N$

PA2: $S: N\to N$

PA3: $\forall a,b\in N:[S(a)=S(b) \to a=b]$

PA4: $\forall a\in N:S(a)\neq n_0$

PA5: $\forall P\subset N: [n_0\in P \space \land\space \forall a\in P:[S(a)\in P]\space \to \space P=N] $

1voto

MikeMathMan Puntos159

Un par de cosas interesantes que pueden ayudar a la OP a entender cómo la inducción de "adaptarse".

De acuerdo a wikipedia,

Los primeros usos del método de descenso infinito aparecen en Euclid del Elementos. Un ejemplo típico es la Proposición 31 de Libro 7, en el que Euclides demuestra que cada compuesto entero es dividido (en Euclid del la terminología de "medida") por algún número primo.

Pero si usted mira en

Quien introdujo el Principio de la Inducción Matemática para la primera vez?

parece que sólo en los últimos 500 años o así que tiene la técnica de inducción sido reconocido como una forma de 'hacer negocios'.

Sin embargo, los dos conceptos son equivalentes a aquellos que estudian la corriente principal de las matemáticas.

Ahora Euclides no tienen la terminología de hoy, a la vista de los números naturales como un conjunto infinito, pero él sabía cómo definir un número primo.

Hizo Euclides y sus Elementos tienen un axioma para usar el método de descenso infinito? Yo lo dudo. Fue tan "obvio" que la técnica debe de haber sido considerado "lógica".

Yo puede ser parcial, pero una vez que un "riguroso y formal de matemáticas de inicio del sistema, lidiando con el infinito de una manera seria, la técnica de inducción viene como un "ride free".

i-Ciencias.com

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.

Powered by: