Función Ackermann-Péter: Prueba por inducción de que A (x, y) <A (x, y +1)

Question

Sea $$ \begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end {eqnarray *} $$

Quiero probar por inducción sobre x que$$A(x,y) < A(x,y+1) \; \forall x,y \in \mathbb{N} $ $

Base:$x = 0$

PS

Hasta ahora, tan fácil, pero estoy completamente estancado con el paso de inducción. ¿Podría por favor ayudarme a seguir?

¡Gracias por adelantado!

Answer 1

Voy a detalle la inducción paso en $x$.

Supongamos que $\ \displaystyle A(x,y) < A(x,y+1)\ \forall y \in \mathbb{N}\ $ y el aviso de que esto implica que $\ \displaystyle A(x,y) < A(x,w)\ \forall y,w \in \mathbb{N} |w>y$.

Entonces :
$A(x+1,0)=A(x,1)\ $ $\ A(x+1,1)=A(x,A(x+1,0))=A(x,A(x,1))$

Observe que el más pequeño posible resultado es $0+1=1$ y desde $\ 1\le A(x,0)<A(x,1)$ deducimos $1 < A(x,1)$, e inferir (considerando $y=1,\ w=A(x,1)$ en la hipótesis de inducción) que $\ A(x+1,0) < A(x+1,1)$

Vamos a hacer una inducción en $y$ demasiado y supongo que $A(x+1,z) < A(x+1,z+1)$$0\le z\le y\ $, entonces :

$A(x+1,y+1)=A(x,A(x+1,y))\ $ $\ A(x+1,y+2)=A(x,A(x+1,y+1))$

pero vamos que $\ A(x+1,y) < A(x+1,y+1)\ $, de modo que podemos usar nuestro inducción en $x$ otra vez a la conclusión de que la $\ A(x+1,y+1) < A(x+1,y+2)\ $ y que : $$\ A(x+1,y) < A(x+1,y+1)\ \ \forall\; y \in \mathbb{N}$$