Evitando la prueba por inducción

Question

Las demostraciones que proceden por inducción casi siempre me resultan insatisfactorias. No parecen profundizar la comprensión, yo describiría algo que es verdadero por inducción como "verdadero por una tecnicidad". Por supuesto, el axioma de inducción es necesario para definir los números naturales y ciertamente parece ser indispensable en una forma u otra.

Sin embargo, sigo interesado en lo siguiente: ¿Existen teoremas "naturales" en matemáticas que parecen poco probables de caer en otro método que no sea la inducción por alguna razón? No incluiría ejemplos que proceden descomponiendo una estructura en componentes más pequeños que son más fáciles de manejar, de alguna manera estas demostraciones cumplen con los criterios de belleza que tengo en mente.

Un ejemplo de un teorema que tiene una demostración por inducción y una prueba más "superior" es el pequeño teorema de Fermat. Es perfectamente posible demostrarlo por inducción, pero la prueba a través de la teoría de grupos parece mejor, quizás porque es más fácilmente generalizable. Me gustaría ejemplos donde parece que la prueba "limpia" es poco probable que exista.

Esto es probablemente muy filosófico y realmente no tengo una pregunta concreta, pero estoy seguro de que no soy el único que se siente de esta manera.

Answer 1

Escribe los axiomas de la teoría de números (llamados "aritmética de Peano," o "PA") como $P^-+\mathrm{Ind}$, donde $P^-$ son los axiomas del semianillo ordenado (sin inducción), y $Ind$ es el axioma (esquema) de inducción. Entonces un teorema requiere algo de inducción si no es demostrable solo por $P^-$ - es decir, si podemos encontrar un modelo de $P^-$ en el que el teorema no es verdadero.

• Como comentario: la equivalencia entre no demostrabilidad y existencia de contraejemplo es (el contrapositivo de) el teorema de completitud de Gödel; ver esta respuesta antigua mía para una discusión de lo que está sucediendo aquí.

Así que esto nos permite formular una pregunta precisa "Pregunta 1:"

Pregunta 1: ¿Hay un teorema "natural" sobre números naturales que requiere algo de inducción, en el sentido mencionado arriba?

Podemos refinar esto. Supongamos que queremos trazar una línea entre demostraciones "simples" mediante inducción, y demostraciones "difíciles" mediante inducción; permitimos lo primero pero somos escépticos sobre lo segundo.

En este caso, de la misma manera en que desglosamos los axiomas de la teoria de números en partes ($P^-$ y $Ind$), ahora necesitamos desglosar $Ind$ en piezas más pequeñas. La forma usual de hacer esto es a través de la jerarquía aritmética: cada fórmula en el lenguaje aritmético puede ser asignada un "nivel de complejidad," y estos niveles están indexados por números naturales. $Ind$ ahora puede ser escrito como $\mathrm{Ind}_1+\mathrm{Ind}_2+ \cdots$, donde $Ind_n$ es la inducción para fórmulas de complejidad $n$. Hablando de manera general, una fórmula tiene complejidad $n$ si puede ser escrita con $n$ bloques alternantes de cuantificadores: por ejemplo, la fórmula $$p(a)=\text{“ }\forall x\,\forall y\,\exists z\,\forall w\,(x+y+w tiene complejidad 3, ya que tiene la forma "$\forall\forall, \exists, \forall$." (Estoy siendo un poco vago aquí, y esto es ligeramente incorrecto; pero no causará problemas.)

Entonces tenemos la pregunta 2:

Pregunta 2: ¿Para cada $n$, hay teoremas "naturales" sobre números naturales que requieren $\mathrm{Ind}_n$?

Observa que si un teorema requiere $\mathrm{Ind}_n$, entonces ciertamente requiere algo de inducción; por lo tanto, la pregunta 2 es un fortalecimiento de la pregunta 1. Por cierto, esto no es la única forma de desglosar $\mathrm{Ind}$; hay muchas otras formas de medir la complejidad de un axioma de inducción.

---

Las respuestas a ambas preguntas son, espectacularmente, SÍ; se estudia la pregunta general, "¿Cuánta inducción necesitamos para probar $\varphi$?" - junto con preguntas similares - por el campo de Matemática inversa.

Algunos ejemplos:

• La afirmación "Hay infinitos números primos" no es demostrable solo en $P^-$; es decir, requiere alguna inducción. ¿Cuánta inducción exactamente? No creo que se sepa, pero se sabe que el nivel (muy débil) de inducción llamado inducción abierta tampoco es suficiente.

• El teorema de Ramsey para parejas - la afirmación, "Cada vez que coloreo pares de números naturales de 'Rojo' o 'Azul,' puedo encontrar un conjunto infinito de números naturales, donde cualquier par de este conjunto se colorea igual que cualquier otro par" - requiere algo de inducción. Nuevamente, no se sabe exactamente cuánto, pero es al menos $\mathrm{Ind}_2$ - una pequeña pero sustancial cantidad de inducción. EDIT: Estoy siendo un poco impreciso aquí. Nota que el teorema de Ramsey no es expresable en el lenguaje de la teoría de números, así que necesito mirar una teoría más expresiva que pueda hablar sobre tales cosas; la teoría utilizada para este propósito es usualmente $RCA_0$, que corresponde de una manera particularmente buena al primer nivel de inducción + la capacidad de hablar sobre conjuntos. Consulta el libro de Simpson (mencionado abajo) para detalles sobre esto.

• Un montón de afirmaciones algebraicas, como "Cada anillo que no es un campo, tiene un ideal propio no trivial", de hecho requieren toda la inducción que $PA$ tiene para ofrecer.

---

REFERENCIAS

Dado que hay mucho contenido aquí, no tengo tiempo para dar una explicación completa - pero aquí hay algunas fuentes:

Para lógica básica, incluido el teorema de completitud de Gödel y qué es un "modelo," me gusta el libro de Enderton "A Mathematical Introduction to Logic" - pero hay muchos libros sobre el mismo tema, y cualquiera de ellos servirá.

Para la jerarquía aritmética, esto se cubrirá en cualquier buen libro de lógica, pero también se puede encontrar en muchos libros de ciencias de la computación teórica - estoy bastante seguro de que está en Arora/Barak, por ejemplo.

Para matemática inversa, esto es más complicado; no hay realmente ninguna introducción legible. El texto clásico es "Subsistemas de Aritmética de Segundo Orden" de Simpson, y el capítulo I es muy agradable y legible, pero el resto es muy difícil.

Answer 2

¿Qué te parece lo siguiente: Dadas las colecciones $\{a_i\}$ y $\{b_i\}$ de números reales, entonces para todo $n$: $\sum_{i=1}^n a_i + \sum_{i=1}^n b_i=\sum_{i=1}^n(a_i+b_i)$.

Si eso es lo que estás buscando, entonces estoy seguro de que puedes encontrar millones de ejemplos similares.

Answer 3

El Teorema de la Categoría de Baire es equivalente al Axma de Elección Dependiente, y por lo tanto no esperarías poder encontrar lo que llamas una prueba clara. Puede que no sea exactamente lo que estás buscando, precisamente porque la inducción por sí sola no es suficiente para demostrar el teorema.

Answer 4

No es una respuesta exacta a tu pregunta (no soy tan inteligente), pero si necesitas derivar algo como una expresión en forma cerrada, pero no te gusta usar una prueba inductiva, puedes probar un método llamado método de perturbación introducido por Graham et al en $Matemáticas Concretas$ (1995). Aquí tienes el ejemplo más simple: mostrar la forma cerrada para $S_n=\sum_{k=1}^{n}a_k = \sum_{k=1}^{n} k$. El primer paso, denota $V_n=\sum_{k=1}^{n}k^2$: $$ V_{n+1} = V_n + a_{n+1} = V_n + (n+1)^2 = \sum_{k=1}^{n}k^2 + (n+1)^2 = \sum_{k=1}^{n}(k+1)^2 + 1 = V_n+2S_n + n+1 $$ $V_n$ se cancela, y después de un poco de álgebra obtienes por supuesto $S_n = \binom{n+1}{2}$.