¿Axioma de la doble inducción?

Question

¿Cuál sería el conjunto teórico axioma de inducción para la inducción doble * cuando se enuncia en el lenguaje matemático de la lógica de primer o segundo orden?

---

* Referencias sobre qué es la doble inducción Es :

A las preguntas de este StackExchange:

• Doble inducción
• Buenos ejemplos de doble inducción
• "¿Un caso de doble inducción?
• 'Prueba de Divisibilidad con Inducción - Atascado en el Paso de Inducción' ( esta respuesta (en particular )

A otras fuentes:

• 'Método de prueba: Inducción multidimensional
• Inducción matemática" (PDF) (Véase §14.2.4, "Apéndice 2 - Los esquemas básicos de inducción": Inducción para los números naturales: Inducción doble (forma débil)' en la página 15 )
• Inducción matemática: variantes y sutilezas" (PDF) (Véase el §3, que comienza al final de la p. 2 )
• Diferentes tipos de inducción matemática" (PDF) (Véase la variante 11 al final de la p. 2 )
• Prueba por inducción matemática" / "Principio de inducción matemática" (PDF) (Véase la sección sobre "Doble Inducción" que comienza al final de la p. 12 )

Answer 1

He aquí una aplicación directa de la inducción simple (no de la inducción fuerte), dos veces:

Queremos demostrar $P(m,n)$ por inducción sobre $n$ . Por lo tanto, tenemos que demostrar $P(m,0)$ y $P(m,n)\to P(m,n+1)$ . Pero para demostrar $P(m,0)$ utilizamos la inducción sobre $m$ , por lo que tenemos que demostrar $P(0,0)$ y $P(m,0)\to P(m+1,0)$ .

En símbolos, esto equivale a la siguiente afirmación:

$$P(0,0)\,\land\,[\forall m,P(m,0)\to P(m+1,0)]\ \land\ [\forall mn,P(m,n)\to P(m,n+1)]\implies\forall xy, P(x,y)$$

En el lenguaje de la inducción bien fundamentada, esto corresponde a la orden $$(m,n)\prec_1(m',n')\iff (m=m'\land n<n')\lor(n=n'=0\land m<m'),$$ que no es un orden total, pero que de todos modos está bien fundado, porque hay un camino (único) desde $(m,n)$ al elemento mínimo $(0,0)$ de longitud $m+n$ por lo que no hay secuencias descendentes infinitas.

---

Otra posibilidad es simplificar el argumento, englobando ambas inducciones en una sola:

Queremos demostrar $P(m,n)$ por inducción sobre $m+n$ . Por lo tanto, tenemos que demostrar $P(0,0)$ y $P(m,n)\to P(m,n+1),P(m+1,n)$ .

Esto se puede expresar como:

$$P(0,0)\ \land\ [\forall mn,P(m,n)\to P(m+1,n)\land P(m,n+1)]\implies\forall xy, P(x,y)$$

Como orden parcial, se trata de la orden del producto en $\Bbb N^2$ Es decir $$(m,n)\preceq_2(m',n')\iff m\le m'\lor n\le n'.$$ Como esta orden es una extensión de la primera, es decir $(m,n)\preceq_1(m',n')$ implica $(m,n)\preceq_2(m',n')$ Esto significa que el primer teorema de inducción es el más fuerte (se aplica a más $P$ '), pero la fundamentación del segundo orden implica la del primero. El argumento es el mismo: cualquier camino desde $(m,n)$ a $(0,0)$ debe tener una longitud máxima de $m+n$ por lo que no hay secuencias descendentes infinitas.

---

Utilizando el mismo orden parcial, podemos incluso utilizar dos valores que son menores bajo el orden en la inducción:

Si $P(m-1,n)$ y $P(m,n-1)$ juntos implican $P(m,n)$ (si uno u otro no están definidos, esto debería ser demostrable con la hipótesis restante), entonces $P(m,n)$ es cierto para todos los $m,n$ .

Este es un caso especial de inducción fuerte sobre $\prec_2$ o la simple inducción sobre $z=m+n$ (donde la hipótesis de inducción es $\forall mn,m+n=z\to P(m,n)$ ).

Si rompemos el caso base y lo reindexamos para que se pueda escribir como $P(m+1,n)\land P(m,n+1)\to P(m+1,n+1)$ Esto deja las obligaciones $P(0,0)$ , $P(m,0)\to P(m+1,0)$ , $P(0,n)\to P(0,n+1)$ y si simplificamos esto a sólo $[\forall m,P(m,0)]\land[\forall n,P(0,n)]$ obtenemos lo mismo que la variante 11 de Diferentes tipos de inducción matemática :

Si $P(0,n)$ y $P(n,0)$ son verdaderos para todos $n$ y $P(m+1,n)\land P(m,n+1)\to P(m+1,n+1)$ para todos $m,n$ entonces $P(m,n)$ es cierto para todos los $m,n$ .

---

Hay otro enfoque alternativo, que está un poco más cerca de algunos de sus enlaces:

Queremos demostrar $P(m,n)$ que se deduce de $\forall n,P(m,n)$ . Esta última propiedad se demuestra por inducción en $m$ , por lo que tenemos que demostrar $\forall n,P(0,n)$ y $[\forall n,P(m,n)]\to[\forall n,P(m+1,n)]$ . En cada caso, tenemos una inducción secundaria sobre $n$ para actuar.

Esto se traduce como:

\begin {align}P(0,0)\N- & \land\ [ \forall n,P(0,n) \to P(0,n+1)]\N-ES \land\\ ( \forall m,[ \forall n,P(m,n)] \to P(m+1,0))\Ny \land \ \forall mn',[ \forall n,P(m,n)] \land P(m+1,n') \to P(m+1,n'+1) \\ & \implies\forall xy, P(x,y) \end {align}

En el lenguaje de las órdenes de los pozos, esto es el orden lexicográfico: $$(m,n)\prec_3(m',n')\iff m<m'\lor(m=m'\land n<n').$$

Esto último es más fácil de plantear como una inducción fuerte:

Queremos demostrar $P(m,n)$ que se deduce de $\forall n,P(m,n)$ . Esto se demuestra por inducción fuerte en $m$ , por lo que tenemos que demostrar $\forall m'<m,\forall n,P(m',n)$ implica $\forall n,P(m,n)$ . Este último para-todo se demuestra mediante una inducción fuerte sobre $n$ Así que asumiendo adicionalmente que $\forall n'<n,P(m,n')$ necesitamos demostrar $P(m,n)$ .

Expresado como una regla de forma cerrada, esto es:

$$\forall m,[\forall m'<m,\forall n,P(m',n)]\to\forall n,[\forall n'<n,P(m,n')]\to P(m,n)\implies\forall xy,P(x,y)$$

que puede simplificarse a

$$\forall mn,[\forall m'n',m'<m\lor (m=m'\land n<n')\to P(m',n')]\to P(m,n)\implies\forall xy,P(x,y).$$

Esta es la forma más generalizable del principio de inducción, utilizando la inducción fuerte en lugar de la simple. En general, parece:

$$\forall x,[\forall x'\prec x,P(x')]\to P(x)\implies\forall y,P(y)$$

donde $\prec$ es una relación bien fundada o un bien ordenado sobre el dominio. En este caso utilizamos $\prec_3$ como una orden de pozo de $\Bbb N^2$ y en los casos anteriores se utilizó $\prec_1$ y $\prec_2$ .