Buenos ejemplos de doble inducción

Question

Estoy buscando buenos ejemplos en los que la doble inducción sea necesaria. Lo que quiero decir con doble inducción es la inducción sobre $\omega^2$ . Están pensados como ejemplos en un curso de "Autómatas y Lenguajes Formales".

Un ejemplo estándar es el siguiente: para cortar un $n\times m$ barra de chocolate en sus componentes, necesitamos $nm-1$ cortes. Sin embargo, hay una prueba mucho mejor sin usar la inducción.

Otro ejemplo: el límite superior $\binom{a+b}{a}$ en los números de Ramsey. El problema de este ejemplo es que se puede refundir como una inducción sobre $a+b$ mientras que yo quiero algo que sea intrínsecamente inductor en $\omega^2$ .

Ejemplo tibio: La función de Ackermann, que parece sacada de la chistera (salvo que conozcamos la jerarquía recursiva primitiva).

Mejores ejemplos: la demostración de otros teoremas de la teoría de Ramsey (por ejemplo, Van der Waerden o Hales-Jewett). Mientras que estos pueden ser posiblemente refundidos como inducción en $\omega$ Pero es menos obvio, por lo que intuitivamente pensamos en estas pruebas como una doble inducción.

Otro ejemplo: la eliminación de cortes en el cálculo secuencial. En este caso la inducción sobre $\omega^2$ podría ser realmente necesario (aunque no estoy seguro de ello).

El problema de mis ejemplos positivos es que todos son bastante técnicos y complicados. Así que estoy buscando un ejemplo sencillo y no artificioso en el que la inducción sobre $\omega^2$ no puede sustituirse fácilmente por una inducción regular (o por un argumento más sencillo). ¿Alguna sugerencia?

Answer 1

Un buen ejemplo surge al relativizar Teorema de Goodstein de $\rm\ \epsilon_0 = \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ hasta $\rm\ \omega^2\:.\ $

$\rm\ \omega^2\ $ Teorema de Goodstein $\ $ Dados naturales $\rm\ a,\:b,\:c\ $ y una función de "salto de base" creciente y arbitraria $\rm\ g(n)\ $ en $\:\mathbb N\:$ la siguiente iteración llega finalmente a $0\ $ (es decir $\rm\ a = c = 0\:$ ).

$\rm\quad\quad\quad\quad\ \ a\ b + c \ \ \to\quad\quad\ \ a\ \ \ \ \ g(b)\ +\ \ \ c\ \ -\ 1\quad if\quad\ c > 0 $

$\rm\quad\quad\quad\quad\ \ \phantom{a\ b + c}\ \ \to\ \ (a-1)\ g(b)\ +\ g(b)-1\quad if\quad \ c = 0 $

Nota: $\ $ La iteración anterior es realmente en triples $\rm\ (a,b,c)\ $ pero elegí la notación anterior para enfatizar la relación con la notación del radix y con la forma normal de Cantor para los ordinales < $\epsilon_0$ . $\ \ $ Para más información sobre el Teorema de Goodstein, ver el enlace en el post de Andrés o ver mi 1995\12\11 post de sci.math.

Answer 2

Permítanme comenzar con un ejemplo de una inducción de longitud $\epsilon_0$ : La prueba de que Secuencias de Goodstein terminar. Menciono esto porque cuando decidí entender este resultado, comencé a calcular la longitud de estas secuencias y finalmente llegué a una conjetura para una fórmula general (¡!) para la longitud de la secuencia. Resultó que demostrar la conjetura era fácil, porque la prueba se organizó como una inducción de la longitud $\epsilon_0$ . Esto me divirtió y me intrigó mucho. El pequeño documento que surgió de esta aventura es aquí .

Ahora, también encontré una vez un ejemplo natural de una inducción de longitud $\omega^2$ al estudiar un problema "tipo Ramsey": el tamaño de los conjuntos minhomogéneos para funciones regresivas sobre pares. Lo que me gustó de este ejemplo es que la función de Ackermann se inyectó a sí misma en el cuadro y acabó proporcionándome las tasas de crecimiento correctas. Los detalles están en un artículo aquí .

Answer 3

Aunque ya lo has descartado por "tibio", la función de Ackermann (probando la totalidad creo que es lo que se busca) es tu opción más accesible (creo que es una gran opción).

No es artificioso/no natural porque está motivado por conceptos muy diferentes. Si quieres construir otro ejemplo (demostrar $f(x,y) = g(x,y)$ ), probablemente querrás que x e y sean muy asimétricos (en el sentido de que deben usarse de formas sintácticas muy diferentes en los cálculos). Y la función de Ackermann hace precisamente eso.

Answer 4

Se podría inventar un ejemplo sencillo, como demostrar que toda secuencia de las siguientes jugadas sobre pares de números naturales termina eventualmente:

$(i,j)\mapsto (i-1,N)$ para cualquier número natural $N$ .

$(i,j)\mapsto (i,j-1)$

(Editado para que sea un $\omega^2$ problema).

Answer 5

¿Qué hay de probar $m+n = n+m$ para $m,n \in \mathbb{N}$ ? En particular, véase este (sitio que habla de la doble inducción).