Todos usamos la inducción matemática para probar resultados, pero ¿existe una prueba de la inducción matemática en sí misma?

Question

Acabo de darme cuenta de algo interesante. En las escuelas y universidades te enseñan inducción matemática. Normalmente lo usas de inmediato para probar algo como

$$1+2+3+\cdots+n = \frac{n(n+1)}{2}$$

Sin embargo.

¡Acabo de darme cuenta de que en ningún momento se prueba la inducción matemática en sí misma! ¿Cuál es la prueba de la inducción matemática? ¿Se prueva la inducción matemática utilizando la propia inducción matemática? (Eso sería sorprendente.)

Answer 1

Supongamos que queremos mostrar que todos los números naturales tienen alguna propiedad $P$. Un camino a seguir, como tú mencionas, es apelar al principio de inducción aritmética.

El principio es el siguiente: Supongamos que podemos mostrar que (i) $0$ tiene alguna propiedad $P$, y también que (ii) si un número dado tiene la propiedad $P$, entonces el siguiente también la tiene; entonces podemos inferir que (iii) todos los números tienen la propiedad $P.

En símbolos, podemos usar $\varphi$ para una expresión que atribuye alguna propiedad a los números, y podemos expresar el principio de inducción de la siguiente manera:

Dado (i) $\varphi(0)$ y (ii) $\forall n(\varphi(n) \to \varphi(n + 1))$, podemos inferir (iii) $\forall n\varphi(n),$

donde los cuantificadores se aplican a números naturales.

La pregunta que se plantea es, de hecho, ¿cómo mostramos que los argumentos que apelan a este principio son buenos argumentos?

Simplemente bendecir al principio con el título de "Axioma" aún no nos dice por qué podría ser un buen axioma para utilizar en el razonamiento sobre los números. Y producir una prueba a partir de un principio equivalente como el Principio del Número Menor podría no ayudar tampoco, ya que la pregunta simplemente se convertiría en por qué los argumentos que apelan a este principio equivalente son buenos argumentos.

¿Entonces no hay nada que decir?

Bueno, quizás aún podamos esperar alguna clarificación conceptual aquí. Con ese fin, considera este argumento informal.

Supongamos que establecemos tanto el caso base (i) como el paso de inducción (ii).

Por (i) tenemos $\varphi(0)$.

Por (ii), $\varphi(0) \to \varphi(1)$. Por lo tanto, podemos inferir $\varphi(1).

Nuevamente por (ii), $\varphi(1) \to \varphi(2)$. Por lo tanto, ahora podemos inferir $\varphi(2).

Del mismo modo, podemos usar otra instancia de (ii) para inferir $\varphi(3).

Y así sucesivamente, avanzando todo lo que queramos a través de los sucesores de $0$ (es decir, a través de los números que se pueden alcanzar comenzando desde cero y agregando uno repetidamente) hasta llegar al enésimo sucesor de cero.

Pero los sucesores de $0$ son los únicos números naturales, por lo que para cada número natural $n$, $\varphi(n)$.

Expuesto de esa manera, vemos que el punto crucial aquí es el último. Y lo que revela este razonamiento es cómo el principio de inducción aritmética es equivalente a una afirmación sobre la estructura básica de la secuencia numérica. Los números naturales se caracterizan como aquellos a los que se puede llegar paso a paso desde cero agregando repetidamente uno, lo que implica la ausencia de números 'perdidos' a los que no se puede llegar paso a paso desde cero aplicando y reaplicando la función sucesor. Si una propiedad se transmite desde cero, y de sucesor a sucesor, se transmite a cada número porque no hay números 'perdidos' fuera de la secuencia de sucesores.

¿Ahora, qué tan iluminador es eso? De alguna manera, ¿no estamos yendo en círculos?

Bueno, ¡en cierto sentido, sí! ¡Pero nota que este no es un círculo vicioso -- más bien es, por ejemplo, cómo Frege y Russell famosamente definieron los números naturales. El punto que está surgiendo de estas reflexiones es que el principio de inducción sencillamente desarrolla la idea intuitiva de que los números naturales son aquellos a los que se puede llegar paso a paso desde cero agregando uno. Definir de qué estamos hablando al hablar de los números naturales es fijar que estamos hablando de cosas sobre las cuales se cumple el principio de inducción aritmética. Por eso es por qué podemos considerar el principio como axiomático.

Nota: Por supuesto, puedes hacer cosas sofisticadas como modelar los números naturales en ZFC, y luego demostrar en ZFC una versión formal de la inducción sobre estos conjuntos que representan los números. Pero es importante ver que esto no ayuda con la pregunta que se plantea aquí. Después de todo, ¿cuál es el criterio para juzgar que una cierta secuencia de conjuntos definida en ZFC es apropiada para ser utilizada como modelo de los números? No cualquier secuencia servirá. ¡Algunas son demasiado largas! Una secuencia apropiada es aquella donde puedes llegar paso a paso desde el 'cero' agregando repetidamente 'uno', y no hay números 'perdidos' en la secuencia a los que no puedas llegar paso a paso desde el 'cero' aplicando y reaplicando la función 'sucesor' en el modelo. En otras palabras, elegimos la implementación de los números naturales en ZFC para garantizar que la secuencia en cuestión tenga la estructura correcta para que funcione la inducción aritmética. Ahora, puedes probar cosas en ZFC sobre esa secuencia de conjuntos, incluyendo un análogo de la inducción aritmética. Pero tomar eso como una razón independiente para pensar que la inducción se cumple sobre los números es colocar las cosas exactamente al revés. Demostrar la inducción en ZFC es, siendo explícitos, ¡sólo sacar el conejo inductivo que ya has metido de contrabando en el sombrero cuando elegiste cómo implementar los números!

Answer 2

El esquema de inducción puede ser demostrado y generalizado para ser utilizado en conjuntos más grandes que los números naturales (La prueba se puede realizar bajo ZFC, que es un sistema axiomático aceptable que es lo suficientemente fuerte para describir la mayoría de las matemáticas que conocemos).

Probemos, por ejemplo, el principio de inducción para conjuntos bien ordenados. Supongamos que tenemos un conjunto bien ordenado (cada subconjunto tiene un elemento mínimo relativo a algún orden <) $\left(A,< \right)$, como los números naturales $\mathbb{N}$ con su orden natural. Sea $\varphi(x)$ alguna propiedad y asumamos que $\left( \forall y

Supongamos que no se cumple para todos $x\in A$, entonces sea $B=\left\{ x\in A | \neg \phi(x) \right\}$, el conjunto de todos los elementos en $A$ para los cuales la propiedad no se cumple. Por nuestra suposición, $B$ no está vacío, por lo tanto tiene un elemento mínimo $b$ ($A$ está bien ordenado por $<$). Por la minimalidad de $b$, tenemos $\forall b'\in B: b'

Por lo tanto, de hecho, demostramos el principio de inducción, y no solo lo aceptamos como algo natural (o lo etiquetamos como un axioma, al menos no en ZFC). Durante la prueba no podemos usar el principio de inducción que estamos intentando probar (de lo contrario no tendría sentido), pero sí usamos nuestro conocimiento de la estructura del conjunto en el que estamos realizando la inducción (en este caso, el buen orden).

Editar: Supongo que esto es una de las cosas elegantes que Peter Smith mencionó. Creo que es bastante elegante y muestra que no tenemos que tomar el principio de inducción como magia negra (o considerarlo un principio subyacente del universo).

Answer 3

No, no hay evidencia de la inducción. La inducción se considera un axioma matemático.

Un axioma es una regla en matemáticas que no requiere una prueba (ya que se piensa que es el punto de partida o premisa de cualquier prueba matemática).

Este es un extracto del artículo de Wikipedia sobre axiomas.

En ambos sentidos, un axioma es cualquier declaración matemática que sirve como punto de partida a partir del cual se derivan lógicamente otras declaraciones. Dentro del sistema que definen, los axiomas (a menos que sean redundantes) no pueden derivarse por principios de deducción, ni son demostrables por pruebas matemáticas, simplemente porque son puntos de partida; no hay nada más de lo que lógicamente se sigan, de lo contrario se clasificarían como teoremas. Sin embargo, un axioma en un sistema puede ser un teorema en otro, y viceversa.

Hay un conjunto de axiomas para los números naturales llamados Axiomas de Peano. Uno de los axiomas de Peano es la inducción matemática.

Answer 4

Una forma de demostrar el principio de inducción matemática es primero asumir la existencia de los números reales $\mathbb{R}$ (como un campo ordenado completo) luego definir los números naturales $\mathbb{N}$ como la intersección de todos los subconjuntos $S$ de $\mathbb{R}$ que satisfacen la propiedad $$ 1 \in S \text{ y } n \in S \rightarrow n+1 \in S.$$ Usando esta definición uno puede fácilmente demostrar el principio de inducción matemática para $\mathbb{N}$. Ver mis notas Álgebra Abstracta Elemental, Capítulo 10 para más detalles. No recuerdo donde vi este tratamiento por primera vez.

Answer 5

Al parecer, no estás entendiendo completamente qué es la inducción. Y eso es completamente comprensible, me tomó un tiempo entenderlo. Para la mayoría de las personas, no tiene sentido - ¿cómo asumir algo que no sabes que es cierto podría probar algo? La analogía de los dominós es bonita, pero no muy útil a menos que ya entiendas la inducción.

Siempre pienso en ello de esta manera en su lugar:

"¿Cómo sabemos que funciona para $n=5$?" "Porque funciona para $n=4$."

"¿Cómo sabemos que funciona para $n=4$?" "Porque funciona para $n=3$."

"¿Cómo sabemos que funciona para $n=3$?" "Porque funciona para $n=2$."

"¿Cómo sabemos que funciona para $n=2$?" "Porque funciona para $n=1$."

"¿Cómo sabemos que funciona para $n=1$?" "Aquí, te lo mostraré sustituyendo $1$ por $n$."

La razón por la que la inducción es tan poderosa es que puedes simplificar los cuatro primeros pasos (o, cuando $n\neq5$, los primeros $n-1$ pasos) en una pequeña declaración que dice "si funciona para $n-1$, tiene que funcionar para $n$". Y la razón por la que eso funciona es porque siempre puedes seguir restando 1 de cualquier número mayor que 1 para llegar a 1. (Eso es cierto debido a uno de los axiomas de los números naturales, al menos en la aritmética de Peano - otras formalizaciones de los números naturales tienen diversas razones por las que la inducción funciona.)