Siguiente: Niveles de la jerarquía Un nivel arriba: Jerarquía de Grzegorczyk Anterior: Una escala de funciones

Propiedades de la escala

Consideremos la sucesión de funciones $\left\{g_n:I\!\!N\rightarrow I\!\!N\right\}_{n\geq 3}$ definida recursivamente como sigue:

 

$$\mapsto$$ g₃:y (2+y)²

$$\forall n\geq 3\ \ \ g_{n+1}:y \mapsto$$ g_n^2y+1(y+1) (6)

(aquí, la notación g^e significa la composición de g consigo misma e veces). Se tiene la

Proposición 3.1   $\forall n\geq 3\;\forall x,y\geq 0:\;f_n(x,y)=g_n^{2^{x}}(y).$

En efecto, demostrémosla por inducción en n. Caso ``base'': Para n=3 se tiene

$$g_3^{2^{x}}(y)=\underbrace{(2+(2+\ldots(2+}_{2^x\mbox{\rm vec... ... \underbrace{)^2\ldots)^2)^2}_{2^x\mbox{\rm veces}}=f_3(x,y)$$ (7)

según se vió anteriormente.

Caso inductivo: Supongamos que para $n\geq 3$ se cumple f_n(x,y)=g_n^2x(y). Ahora, mostremos por inducción en x la igualdad

 

f_n+1(x,y)=g_n+1^2x(y) (8)

De 2.4 se tiene f_n+1(0,y)=g_n^2y+1(y+1). Y de 2.6 se sigue que, en efecto, f_n+1(0,y)=g_n+1(y). Supongamos que para $x\geq 0$ se cumple 2.8. Entonces

$$% latex2html id marker 10420 \begin{array}{rcll} f_{n+1}(x+1... ...1}}(y) &\mbox{\rm : por la ley de las potencias. } \end{array}$$

quod erat demonstratum.

Proposición 3.2   Se cumplen las propiedades siguientes:

1.

Toda sección de f_n está por encima de la identidad, i.e.

$$\forall n>1,\ \forall x,y: y<f_n(x,y).$$

2.

Cada f_n es creciente en su primera componente, i.e.

$$\forall n>0,\ \forall x,y: f_n(x,y)<f_n(x+1,y).$$

3.

Cada f_n es creciente en su segunda componente, i.e.

$$\forall n>0,\ \forall x,y: f_n(x,y)<f_n(x,y+1).$$

4.

La sucesión de funciones $\left\{f_n\right\}_n$ es creciente respecto a su índice n, i.e.

$$\forall n>0,\ \forall x,y: f_n(x,y)<f_{n+1}(x,y).$$

Demostración: Mostraremos cada una de las aseveraciones en la proposición.

1.

Por inducción en n: Casos ``bases'': Como f₀ es la función sucesor de su segundo argumento, tenemos evidentemente, $\forall y:\ y < f_0(x,y)$. f₁ es la función suma, luego $\forall x,y:\ y \leq f_1(x,y)$, y la desigualdad es estricta siempre que x>0. Ahora, $\forall x$ es evidente que se cumple $\forall y:\ y < y+1\leq (x+1)(y+1)=f_2(x,y).$ Caso inductivo: Sea $n\geq 2$. Supongamos que $\forall x,y:\ y < f_n(x,y).$ Para probar $\forall y:\ y < f_{n+1}(x,y),$ procedamos por inducción en x. Basta observar que se cumplen,

$$\begin{eqnarray*}\forall y:&& y < f_n(y+1,y+1)=f_{n+1}(0,y) \\ \forall y:&& y < f_{n+1}(x,y)<f_{n+1}(x,f_{n+1}(x,y))=f_{n+1}(x+1,y) \end{eqnarray*}$$

2.

Comprobemos la aseveración en cada n. f₀ es constante respecto a su primer argumento. Es la única función en la escala que no es estrictamente creciente en su primer argumento. Para f₁ es evidente que se cumple $\forall x$:

$$\forall y:\ f_1(x,y)=x+y < (x+1)+y=f_1(x+1,y).$$

Para f₂ es también evidente que se cumple $\forall x$:

$$\forall y:\ f_2(x,y)=(x+1)(y+1) < ((x+1)+1)(y+1)=f_2(x+1,y).$$

Sea $n\geq 2$. Se tiene,

$$% latex2html id marker 10482 \begin{array}{cll} & f_{n}(x,y... ...+1,y) &\mbox{\rm : por la relaci\'on~\ref{eqfn1}} \end{array}$$

3.

Procedamos aquí también por inducción en n. Casos ``bases'': Para $n\leq 2$ se comprueba inmediatamente que $\forall x:\ \ y\mapsto f_n(x,y)$ es creciente. Caso inductivo: Sea $n\geq 0$. Supongamos que $\forall x:\ \ y\mapsto f_n(x,y)$ es creciente. Veamos que lo mismo pasa para n+1. Probaremos esto último por induccón en x. Se tiene,

$$% latex2html id marker 10498 \begin{array}{rcll} f_{n+1}(0,y... ...y+1) &\mbox{\rm : por la relaci\'on~\ref{eqfn0}.} \end{array}$$

Sea $x\geq 0$. Supongamos $\forall y: f_{n+1}(x,y)<f_{n+1}(x,y+1)$. Tenemos,

$$% latex2html id marker 10504 \begin{array}{rcll} f_{n+1}(x+1... ...y+1) &\mbox{\rm : por la relaci\'on~\ref{eqfn1}.} \end{array}$$

4.

Observemos primeramente que para cualquier n,

$$x\leq y\ \ \ \Rightarrow\ \ \ f_n(x,y)\leq f_{n+1}(x,y).$$

En efecto,

$$% latex2html id marker 10510 \begin{array}{rcll} f_{n}(x,y) ... ... porque $f_n$ es creciente en ambas componentes.} \end{array}$$

Mostremos ahora por inducción en x,

$$x\geq y\ \ \ \Rightarrow\ \ \ f_n(x,y)\leq f_{n+1}(x,y).$$

El caso ``base'' x=y queda subsumido en el caso anterior. Supongamos la desigualdad válida para $x\geq y$, cualquiera que sea y. Mostrémosla para x+1:

$$% latex2html id marker 10524 \begin{array}{rcll} f_{n+1}(x+1... ...1,y) &\mbox{\rm : por la relaci\'on~\ref{eqfn1}.} \end{array}$$

Siguiente: Niveles de la jerarquía Un nivel arriba: Jerarquía de Grzegorczyk Anterior: Una escala de funciones