4.2 El paradigma de Godel: Funciones \(\Sigma\)-recursivas

En esta sección desarrollaremos el modelo matemático del concepto de función \(\Sigma\)-efectivamente computable, dado por Godel. Dichas funciones serán llamadas \(\Sigma\)-recursivas. La idea es partir de un conjunto inicial de funciones muy simples y obviamente \(\Sigma\)-efectivamente computables y luego obtener nuevas funciones \(\Sigma\)-efectivamente computables usando constructores que preservan la computabilidad efectiva. Las funciones \(\Sigma\)-recursivas serán las que se obtienen iterando el uso de estos constructores, partiendo del conjunto inicial de funciones antes mencionado. Nos referiremos a este paradigma como el paradigma Godeliano o recursivo. A veces también lo llamaremos el paradigma funcional.

La familia de funciones simples y obviamente \(\Sigma\)-efectivamente computables de la que partiremos es la siguiente \[\left\{ Suc,Pred,C_{0}^{0,0},C_{\varepsilon}^{0,0}\right\} \cup\left\{ d_{a}:a\in\Sigma\right\} \cup\left\{ p_{j}^{n,m}:1\leq j\leq n+m\right\}\] Los constructores que usaremos son:

1. adhocprefix-adhocsufix Composición

2. adhocprefix-adhocsufix Recursión primitiva

3. adhocprefix-adhocsufix Minimización de predicados \(\Sigma\)-totales

Estos constructores nos permiten dadas ciertas funciones construir o definir una nueva función y tienen la propiedad de preservar la computabilidad efectiva en el sentido que si las funciones iniciales son \(\Sigma\)-efectivamente computables, entonces la función obtenida también lo es. Un concepto fundamental es el de función \(\Sigma\)-recursiva primitiva. Estas funciones serán aquellas que se obtienen a partir de las del conjunto inicial usando solo los dos primeros constructores: composición y recursión primitiva. Nuestro primer objetivo es definir el concepto de función \(\Sigma\)-recursiva primitiva para lo cual en las próximas dos secciones definiremos y estudiaremos los constructores de composición y recursión primitiva. Luego definiremos el concepto de función \(\Sigma\)-recursiva primitiva y nos abocaremos a desarrollar este concepto fundamental. Recién después estudiaremos el constructor de Minimización y definiremos el concepto de función \(\Sigma\)-recursiva. La última parte de la sección esta destinada a probar un teorema que nos dice que los conceptos de función \(\Sigma\)-recursiva y \(\Sigma\)-recursiva primitiva son independientes del alfabeto \(\Sigma\).

4.2.1 Composición

Dadas funciones \(\Sigma\)-mixtas \(f,f_{1},...,f_{r}\), con \(r\geq1\), diremos que la función \(f\circ[f_{1},...,f_{r}]\) es obtenida por composición a partir de las funciones \(f,f_{1},...,f_{r}\). Para probar que la composición preserva la computabilidad efectiva necesitaremos el siguiente lema.

Proof. Nótese que \(f\neq\emptyset\) y \([f_{1},...,f_{r}]\neq\emptyset\) (por que?). Además \(f_{i}\neq\emptyset\), para cada \(i=1,...,r\) (por que?). Ya que \(f\neq\emptyset\) tenemos que hay únicos \(n,m\in\omega\) y \(s\in\{\#,\ast\}\) tales que \(f\) es de tipo \((n,m,s)\). Ya que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\) y \(I_{[f_{1},...,f_{r}]}\subseteq I_{f_{1}}\times...\times I_{f_{r}}\), tenemos que

1. adhocprefix-adhocsufix \(r=n+m\)

2. adhocprefix-adhocsufix \(I_{f_{i}}\subseteq\omega\), para cada \(i=1,...,n\)

3. adhocprefix-adhocsufix \(I_{f_{i}}\subseteq\Sigma^{\ast}\), para cada \(i=n+1,...,n+m\)

Ya que \([f_{1},...,f_{r}]\neq\emptyset\) tenemos que \(D_{[f_{1},...,f_{r}]}=\bigcap_{i=1}^{r}D_{f_{i}}\neq\emptyset\), por lo cual los conjuntos \(D_{f_{1}},...,D_{f_{n+m}}\) deberán ser todos de un mismo tipo, digamos de tipo \((k,l)\). Es decir que \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\) y \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\).

Las últimas observaciones del lema son directas de las definiciones de \([f_{1},...,f_{n+m}]\) y de composición de funciones  

Ahora sí podemos probar fácilmente que el constructor composición preserva la computabilidad efectiva

Proof. Si \(f\circ[f_{1},...,f_{r}]=\emptyset\), entonces claramente es \(\Sigma\)-efectivamente computable. Supongamos entonces que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\). Por el lema anterior hay \(n,m,k,l\in\omega\) y \(s\in\{\#,\ast\}\) tales que

1. adhocprefix-adhocsufix \(r=n+m\)

2. adhocprefix-adhocsufix \(f\) es de tipo \((n,m,s)\)

3. adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\)

4. adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\)

Sean \(\mathbb{P},\mathbb{P}_{1},...,\mathbb{P}_{n+m}\) procedimientos efectivos los cuales computen computen las funciones \(f,f_{1},...,f_{n+m}\), respectivamente. Usando estos procedimientos es fácil definir un procedimiento efectivo el cual compute a \(f\circ[f_{1},...,f_{n+m}]\).  

4.2.2 Recursión primitiva

La recursión primitiva es un tipo muy particular de recursión. Consideremos por ejemplo las siguientes ecuaciones:

1. adhocprefix(1)adhocsufix \(R(0)=1\)

2. adhocprefix(2)adhocsufix \(R(t+1)=1+R(t)+R(t)^{2}\)

Nótese que hay una única función \(R:\omega\rightarrow\omega\) la cual cumple (1) y (2). Esto es ya que el valor de \(R\) en \(t\) esta determinado por sucesivas aplicaciones de las ecuaciones (1) y (2). Por ejemplo la ecuación (1) nos dice que \(R(0)=1\) pero entonces la ecuación (2) nos dice que \(R(1)=1+1+1^{2}=3\) por lo cual nuevamente la ecuación (2) nos dice que \(R(2)=1+3+3^{2}=13\) y así podemos notar fácilmente que \(R\) esta determinada por dichas ecuaciones.

Se suele decir que las ecuaciones (1) y (2) definen recursivamente a la función \(R\) pero hay que tener cuidado porque esto es una manera de hablar ya que la función \(R\) podría en nuestro discurso ya haber sido definida de otra manera. Mas propio es pensar que dichas ecuaciones determinan a \(R\) en el sentido que \(R\) es la única que las cumple. Por ejemplo las ecuaciones:

1. adhocprefix(a)adhocsufix \(R(0)=50\)

2. adhocprefix(b)adhocsufix \(R(t+1)=R(t)\)

“definen recursivamente” a la función \(C_{50}^{1,0}\) pero esta claro que la definición de \(C_{50}^{1,0}\) en esta materia no fue dada de esta forma.

Hay casos de recursiones en las cuales el valor de \(R(t+1)\) no solo depende de \(R(t)\) sino que también depende de \(t\). Por ejemplo

1. adhocprefix(i)adhocsufix \(R(0)=1\)

2. adhocprefix(ii)adhocsufix \(R(t+1)=t.R(t)+1\)

De todas maneras debería quedar claro que las ecuaciones (i) y (ii) determinan una única función \(R:\omega\rightarrow\omega\) que las satisface.

También podemos generalizar pensando que la función \(R\) depende no solo de un parámetro \(t\) sino que su dominio es \(\omega^{4}\), es decir depende de \(t\) y \(x_{1},x_{2},x_{3}\). Por ejemplo

1. adhocprefix(p)adhocsufix \(R(0,x_{1},x_{2},x_{3})=x_{1}+2x_{3}\)

2. adhocprefix(q)adhocsufix \(R(t+1,x_{1},x_{2},x_{3})=t+x_{1}+x_{2}+x_{3}+R(t,x_{1},x_{2},x_{3})\)

Dejamos al lector convencerse de que (p) y (q) son cumplidas por una única función \(R:\omega^{4}\rightarrow\omega\). También podríamos tener variables alfabéticas. Por ejemplo consideremos

1. adhocprefix(r)adhocsufix \(R(0,x_{1},x_{2},\alpha_{1},\alpha_{2})=x_{1}+\left\vert \alpha_{1}\right\vert ^{x_{2}}\)

2. adhocprefix(s)adhocsufix \(R(t+1,x_{1},x_{2},\alpha_{1},\alpha_{2})=t+x_{1}+x_{2}+\left\vert \alpha_{1}\right\vert +\left\vert \alpha_{2}\right\vert +R(t,x_{1},x_{2},\alpha_{1},\alpha_{2})\)

Es claro aquí que las ecuaciones (r) y (s) determinan una única función \(R:\omega^{3}\times\Sigma^{\ast2}\rightarrow\omega\) que las cumple. Esto se puede explicar de la siguiente manera:

1. adhocprefix-adhocsufix La ecuación (r) determina los valores de \(R\) sobre el conjunto \(\{0\}\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\). Pero una ves determinados estos valores, la ecuación (s) tomada con \(t=0\), determina los valores de \(R\) sobre el conjunto \(\{1\}\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\). Pero una ves determinados estos valores, la ecuación (s) tomada con \(t=1\), determina los valores de \(R\) sobre el conjunto \(\{2\}\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\), etc

El caso anterior podría generalizarse de la siguiente manera: Si tenemos dadas dos funciones \[\begin{aligned} f & :\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\\ g & :\omega^{n+2}\times\Sigma^{\ast m}\rightarrow\omega \end{aligned}\] entonces las ecuaciones:

1. adhocprefix(a)adhocsufix \(R(0,\vec{x},\vec{\alpha})=f(\vec{x},\vec{\alpha})\)

2. adhocprefix(b)adhocsufix \(R(t+1,\vec{x},\vec{\alpha})=g(R(t,\vec{x},\vec{\alpha}),t,\vec{x},\vec{\alpha})\)

determinan una única función \(R:\omega^{n+1}\times\Sigma^{\ast m}\rightarrow\omega\) que las cumple. Nótese que para el caso \[\begin{aligned} n & =m=2\\ f & =\lambda x_{1}x_{2}\alpha_{1}\alpha_{2}[x_{1}+\left\vert \alpha_{1}\right\vert ^{x_{2}}]\\ g & =\lambda xtx_{1}x_{2}\alpha_{1}\alpha_{2}[t+x_{1}+x_{2}+\left\vert \alpha_{1}\right\vert +\left\vert \alpha_{2}\right\vert +x] \end{aligned}\] las ecuaciones (a) y (b) se transforman en las ecuaciones (r) y (s).

El primer caso de recursión primitiva que definiremos a continuación engloba los ejemplos vistos recién dentro de un marco general.

4.2.2.1 Recursión primitiva sobre variable numérica con valores numéricos

Supongamos tenemos dadas funciones \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\\ g & :\omega\times\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega \end{aligned}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacíos. Usando el razonamiento inductivo usado en los ejemplos anteriores, se puede probar que hay una única función \[R:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\] la cual cumple las ecuaciones

1. adhocprefix-adhocsufix \(R(0,\vec{x},\vec{\alpha})=f(\vec{x},\vec{\alpha})\)

2. adhocprefix-adhocsufix \(R(t+1,\vec{x},\vec{\alpha})=g(R(t,\vec{x},\vec{\alpha}),t,\vec{x},\vec{\alpha})\)

Llamaremos \(R(f,g)\) a esta única función que cumple las ecuaciones anteriores. Resumiendo este hecho, diremos que las ecuaciones

1. adhocprefix(1)adhocsufix \(R(f,g)(0,\vec{x},\vec{\alpha})=f(\vec{x},\vec{\alpha})\)

2. adhocprefix(2)adhocsufix \(R(f,g)(t+1,\vec{x},\vec{\alpha})=g(R(f,g)(t,\vec{x},\vec{\alpha}),t,\vec{x},\vec{\alpha})\)

definen recursivamente a la función \(R(f,g)\). También diremos que \(R(f,g)\) es obtenida por recursión primitiva a partir de \(f\) y \(g\).

NOTA IMPORTANTE: No confundirse y pensar que \(R(f,g)\) es el resultado de aplicar una función \(R\) al par \((f,g)\), de hecho hasta el momento no hemos definido ninguna función \(R\) cuyo dominio sea cierto conjunto de pares ordenados de funciones!

Nótese que cuando \(m=n=0\), se tiene que \(D_{f}=\{\lozenge\}\) y (1) y (2) se transforman en

1. adhocprefix(1)adhocsufix \(R(f,g)(0)=f(\lozenge)\)

2. adhocprefix(2)adhocsufix \(R(f,g)(t+1)=g(R(f,g)(t),t)\)

Veamos algunos ejemplos

1. adhocprefix(E1)adhocsufix Tomemos \(f=p_{1}^{1,0}\) y \(g=Suc\circ p_{1}^{3,0}\). De la definición de \(R(f,g)\), obtenemos que su dominio es \(\omega^{2}\) y \[\begin{aligned} R(f,g)(0,x_{1}) & =p_{1}^{1,0}(x_{1})=x_{1}\\ R(f,g)(t+1,x_{1}) & =\left(Suc\circ p_{1}^{3,0}\right)(R(f,g)(t,x_{1}),t,x_{1})=R(f,g)(t,x_{1})+1 \end{aligned}\] Es fácil notar que la única función que cumple estas dos ecuaciones es \(\lambda tx_{1}\left[t+x_{1}\right]\), lo cual implica que \(\lambda tx_{1}\left[t+x_{1}\right]=R\left(p_{1}^{1,0},Suc\circ p_{1}^{3,0}\right)\)

2. adhocprefix(E2)adhocsufix Sean \(f=C_{0}^{0,0}\) y \(g=p_{1}^{2,0}\). De la definición de \(R(f,g)\), obtenemos que su dominio es \(\omega\) y \[\begin{aligned} R(f,g)(0) & =C_{0}^{0,0}(\lozenge)=0\\ R(f,g)(t+1) & =p_{1}^{2,0}(R(f,g)(t),t)=R(f,g)(t) \end{aligned}\] Es fácil notar que la única función que cumple estas dos ecuaciones es \(C_{0}^{1,0}\) lo cual implica que \(C_{0}^{1,0}=R\left(C_{0}^{0,0},p_{1}^{2,0}\right)\)

Como era de esperar, este caso del constructor de recursión primitiva preserva la computabilidad efectiva

Proof. Sean \(\mathbb{P}_{f}\) y \(\mathbb{P}_{g}\) procedimientos efectivos que computan a \(f\) y \(g\), respectivamente. Es fácil construir entonces un procedimiento efectivo que compute a \(R(f,g)\).  

Nota importante: En los ejemplos anteriores y en todos los casos que manejaremos en esta primera etapa, en las aplicaciones del constructor de recursión primitiva (en sus cuatro formas) las funciones iniciales serán \(\Sigma\)-totales (es decir \(S_{1}=...=S_{n}=\omega\) y \(L_{1}=...=L_{m}=\Sigma^{\ast}\)). Mas adelante veremos aplicaciones con funciones no \(\Sigma\)-totales.

4.2.2.2 Recursión primitiva sobre variable numérica con valores alfabéticos

Ahora haremos el caso en el que la función determinada recursivamente tiene imagen contenida en \(\Sigma^{\ast}\). Es claro que entonces \(f\) y \(g\) también deberán tener imagen contenida en \(\Sigma^{\ast}\). El único detalle a tener en cuenta en la definición de este caso es que si solo hiciéramos estos cambios y pusiéramos las mismas ecuaciones la función \(g\) no resultaría \(\Sigma\)-mixta en general. Para que la \(g\) de la recursión siga siendo \(\Sigma\)-mixta deberemos modificar levemente su dominio en relación al caso ya hecho

Supongamos \(\Sigma\) es un alfabeto finito. Sean \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\\ g & :\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast} \end{aligned}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacíos. Definamos \[R(f,g):\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\] de la siguiente manera

1. adhocprefix(1)adhocsufix \(R(f,g)(0,\vec{x},\vec{\alpha})=f(\vec{x},\vec{\alpha})\)

2. adhocprefix(2)adhocsufix \(R(f,g)(t+1,\vec{x},\vec{\alpha})=g(t,\vec{x},\vec{\alpha},R(f,g)(t,\vec{x},\vec{\alpha}))\)

Diremos que \(R(f,g)\) es obtenida por recursión primitiva a partir de \(f\) y \(g\). Nótese que cuando \(m=n=0\), se tiene que \(D_{f}=\{\lozenge\}\) y (1) y (2) se transforman en

1. adhocprefix(1)adhocsufix \(R(f,g)(0)=f(\lozenge)\)

2. adhocprefix(2)adhocsufix \(R(f,g)(t+1)=g(t,R(f,g)(t))\)

Veamos algunos ejemplos

1. adhocprefix(E1)adhocsufix Tomemos \(f=C_{\varepsilon}^{0,1}\) y \(g=\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[p_{3}^{1,2},p_{2}^{1,2}\right]\). De la definición de \(R(f,g)\), obtenemos que \[\begin{aligned} R(f,g)(0,\alpha_{1}) & =C_{\varepsilon}^{0,1}(\alpha_{1})=\varepsilon\\ R(f,g)(t+1,\alpha_{1}) & =\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[p_{3}^{1,2},p_{2}^{1,2}\right](t,\alpha_{1},R(f,g)(t,\alpha_{1}))=R(f,g)(t,\alpha_{1})\alpha_{1} \end{aligned}\] Es fácil notar que la única función que cumple estas dos ecuaciones es \(\lambda t\alpha_{1}\left[\alpha_{1}{}^{t}\right]\), lo cual implica que \(\lambda t\alpha_{1}\left[\alpha_{1}{}^{t}\right]=R\left(C_{\varepsilon}^{0,1},\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[p_{3}^{1,2},p_{2}^{1,2}\right]\right)\)

2. adhocprefix(E2)adhocsufix Sean \(f=C_{\varepsilon}^{0,0}\) y \(g=p_{2}^{2,0}\). De la definición de \(R(f,g)\), obtenemos que \[\begin{aligned} R(f,g)(0) & =C_{\varepsilon}^{0,0}(\lozenge)=\varepsilon\\ R(f,g)(t+1) & =p_{2}^{2,0}(t,R(f,g)(t))=R(f,g)(t) \end{aligned}\] Es fácil notar que la única función que cumple estas dos ecuaciones es \(C_{\varepsilon}^{1,0}\) lo cual implica que \(C_{\varepsilon}^{1,0}=R\left(C_{\varepsilon}^{0,0},p_{2}^{2,0}\right)\)

La prueba del siguiente lema es completamente análoga a la del lema anterior que fue dejada como ejercicio.

4.2.2.3 Recursión primitiva sobre variable alfabética con valores numéricos

Ya vimos dos casos de recursión donde el parámetro que comanda la recursión es numérico. Daremos a continuación un ejemplo de recursión en el cual el parámetro principal es alfabético. Sea \(\Sigma=\{\%,@,?\}\) y consideremos las siguientes ecuaciones:

1. adhocprefix(1)adhocsufix \(R(\varepsilon)=15\)

2. adhocprefix(2)adhocsufix \(R(\alpha\%)=R(\alpha)+1\)

3. adhocprefix(3)adhocsufix \(R(\alpha@)=R(\alpha).5\)

4. adhocprefix(4)adhocsufix \(R(\alpha?)=R(\alpha)^{20}\)

Nótese que las ecuaciones anteriores determinan una función \(R:\Sigma^{\ast}\rightarrow\omega\). Esto es ya que \(R\) en \(\varepsilon\) debe valer \(15\) y sabiendo esto las ecuaciones (2), (3) y (4) (con \(\alpha=\varepsilon\)) nos dicen que \[\begin{aligned} R(\%) & =16\\ R(@) & =75\\ R(?) & =15^{20} \end{aligned}\] por lo cual podemos aplicarlas nuevamente a dichas ecuaciones (con \(\alpha\in\{\%,@,?\}\)) para calcular \(R\) en todas las palabras de longitud \(2\); y así sucesivamente.

Daremos otro ejemplo un poco mas complicado para seguir aproximándonos al caso general. Nuevamente supongamos que \(\Sigma=\{\%,@,?\}\) y supongamos tenemos una función \[f:\omega\times\Sigma^{\ast}\rightarrow\omega\] y tres funciones \[\begin{aligned} \mathcal{G}_{\%} & :\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega\\ \mathcal{G}_{@} & :\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega\\ \mathcal{G}_{?} & :\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega \end{aligned}\] Entonces hay una única función \(R:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega\) la cual cumple las siguientes ecuaciones

1. adhocprefix(1)adhocsufix \(R(x_{1},\alpha_{1},\varepsilon)=f(x_{1},\alpha_{1})\)

2. adhocprefix(2)adhocsufix \(R(x_{1},\alpha_{1},\alpha\%)=\mathcal{G}_{\%}(R(x_{1},\alpha_{1},\alpha),x_{1},\alpha_{1},\alpha)\)

3. adhocprefix(3)adhocsufix \(R(x_{1},\alpha_{1},\alpha@)=\mathcal{G}_{@}(R(x_{1},\alpha_{1},\alpha),x_{1},\alpha_{1},\alpha)\)

4. adhocprefix(4)adhocsufix \(R(x_{1},\alpha_{1},\alpha?)=\mathcal{G}_{?}(R(x_{1},\alpha_{1},\alpha),x_{1},\alpha_{1},\alpha)\)

(Justifique que las ecuaciones anteriores determinan a la función \(R\).)

El ejemplo anterior nos muestra que para hacer recursión sobre parámetro alfabético nos hace falta "una función \(g\) por cada símbolo de \(\Sigma\)". Esto motiva la siguiente definición. Dado un alfabeto \(\Sigma\), una familia \(\Sigma\)-indexada de funciones será una función \(\mathcal{G}\) tal que \(D_{\mathcal{G}}=\Sigma\) y para cada \(a\in D_{\mathcal{G}}\) se tiene que \(\mathcal{G}(a)\) es una función. Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Sea \(\mathcal{G}\) dada por \[\begin{array}{rcl} \mathcal{G}:\{\square,\%,\blacktriangle\} & \rightarrow & \{Suc,Pred\}\\ \square & \rightarrow & Suc\\ \% & \rightarrow & Suc\\ \blacktriangle & \rightarrow & Pred \end{array}\] Claramente \(\mathcal{G}\) es una familia \(\{\square,\%,\blacktriangle\}\)-indexada de funciones. Notar que \[\mathcal{G}=\{(\square,Suc),(\%,Suc),(\blacktriangle,Pred)\}\] Se tiene también por ejemplo que \(\mathcal{G}(\%)=Suc\) por lo cual también es cierto que \(\mathcal{G}(\%)(22)=23\), etc.

2. adhocprefix(E2)adhocsufix Si \(\Sigma\) es un alfabeto no vacío, la función \[\begin{array}{rcl} \mathcal{G}:\Sigma & \rightarrow & \{f:f\text{ es una función de }\Sigma^{\ast}\text{ en }\Sigma^{\ast}\}\\ a & \rightarrow & d_{a} \end{array}\] es una familia \(\Sigma\)-indexada de funciones. Notar que \[\mathcal{G}=\{(a,d_{a}):a\in\Sigma\}\]

3. adhocprefix(E3)adhocsufix \(\emptyset\) es una flia \(\emptyset\)-indexada de funciones

Si \(\mathcal{G}\) es una familia \(\Sigma\)-indexada de funciones, entonces para \(a\in\Sigma\), escribiremos \(\mathcal{G}_{a}\) en lugar de \(\mathcal{G}(a)\). Ahora sí, nuestro caso de recursión primitiva. Sea \[f:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacíos y sea \(\mathcal{G}\) una familia \(\Sigma\)-indexada de funciones tal que \[\mathcal{G}_{a}:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\omega\] para cada \(a\in\Sigma.\) Definamos \[R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\omega\] de la siguiente manera

1. adhocprefix(1)adhocsufix \(R(f,\mathcal{G})(\vec{x},\vec{\alpha},\varepsilon)=f(\vec{x},\vec{\alpha})\)

2. adhocprefix(2)adhocsufix \(R(f,\mathcal{G})(\vec{x},\vec{\alpha},\alpha a)=\mathcal{G}_{a}(R(f,\mathcal{G})(\vec{x},\vec{\alpha},\alpha),\vec{x},\vec{\alpha},\alpha)\)

Diremos que \(R(f,\mathcal{G})\) es obtenida por recursión primitiva a partir de \(f\) y \(\mathcal{G}\). Nótese que cuando \(m=n=0\), se tiene que \(D_{f}=\{\lozenge\}\) y (1) y (2) se transforman en

1. adhocprefix(1)adhocsufix \(R(f,\mathcal{G})(\varepsilon)=f(\lozenge)\)

2. adhocprefix(2)adhocsufix \(R(f,\mathcal{G})(\alpha a)=\mathcal{G}_{a}(R(f,\mathcal{G})(\alpha),\alpha)\)

Proof. Es dejada al lector  

4.2.2.4 Recursión primitiva sobre variable alfabética con valores alfabéticos

Supongamos \(\Sigma\) es un alfabeto finito. Sea \[f:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacíos y sea \(\mathcal{G}\) una familia \(\Sigma\)-indexada de funciones tal que \[\mathcal{G}_{a}:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}\] para cada \(a\in\Sigma\). Definamos \[R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}\] de la siguiente manera

1. adhocprefix(1)adhocsufix \(R(f,\mathcal{G})(\vec{x},\vec{\alpha},\varepsilon)=f(\vec{x},\vec{\alpha})\)

2. adhocprefix(2)adhocsufix \(R(f,\mathcal{G})(\vec{x},\vec{\alpha},\alpha a)=\mathcal{G}_{a}(\vec{x},\vec{\alpha},\alpha,R(f,\mathcal{G})(\vec{x},\vec{\alpha},\alpha)).\)

Diremos que \(R(f,\mathcal{G})\) es obtenida por recursión primitiva a partir de \(f\) y \(\mathcal{G}\). Nótese que cuando \(m=n=0\), se tiene que \(D_{f}=\{\lozenge\}\) y (1) y (2) se transforman en

1. adhocprefix(1)adhocsufix \(R(f,\mathcal{G})(\varepsilon)=f(\lozenge)\)

2. adhocprefix(2)adhocsufix \(R(f,\mathcal{G})(\alpha a)=\mathcal{G}_{a}(\alpha,R(f,\mathcal{G})(\alpha))\)

Tenemos que

4.2.2.5 Cosmética

Como hemos visto muchas veces para poder aplicar mas naturalmente algún lema, nos es útil cambiar las variables que están siendo usadas en la notación lambda que describe alguna función. Por ejemplo si queremos ver que la función \(\lambda xy\alpha[x+y]\) es de la forma \(R(f,g)\), con \(f\) de tipo \((1,1,\#)\) y \(g\) de tipo \((3,1,\#)\), nos conviene escribir a la función \(\lambda xy\alpha[x+y]\) en la forma \(\lambda tx_{1}\alpha_{1}[t+x_{1}]\), donde se ve mejor cual es el parámetro de la recursión primitiva y cual es el bloque fijo. Obviamente esto es posible ya que \(\lambda xy\alpha[x+y]=\lambda tx_{1}\alpha_{1}[t+x_{1}]\). Esto da lugar a nuestra regla de cosmética:

REGLA DE COSMÉTICA: Si Ud tiene una expresión lambda \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) que denota una función \(f\), entonces puede reemplazar en dicha expresión cada ocurrencia de una de las variables de la lista \(x_{1}...x_{n}\alpha_{1}...\alpha_{m}\) por una nueva variable (del mismo tipo, i.e. numérica o alfabética) la cual no figure en la lista y el resultado será una expresión lambda que también denota a \(f.\)

Por supuesto que dicha regla la puede aplicar varias veces para modificar su notación lambda. Por ejemplo en el caso de \(\lambda xy\alpha[x+y]\) aplicamos tres veces la regla y obtenemos \(\lambda tx_{1}\alpha_{1}[t+x_{1}]\).

4.2.3 Funciones \(\Sigma\)-recursivas primitivas

Intuitivamente hablando una función es \(\Sigma\)-recursiva primitiva si se puede obtener de las iniciales usando los constructores de composición y recursión primitiva. Daremos ahora una definición matemática de este concepto. Definamos los conjuntos \(\mathrm{PR}_{0}^{\Sigma}\subseteq\mathrm{PR}_{1}^{\Sigma}\subseteq\mathrm{PR}_{2}^{\Sigma}\subseteq...\subseteq\mathrm{PR}^{\Sigma}\) de la siguiente manera \[\begin{array}{lll} \mathrm{PR}_{0}^{\Sigma} & = & \left\{ Suc,Pred,C_{0}^{0,0},C_{\varepsilon}^{0,0}\right\} \cup\left\{ d_{a}:a\in\Sigma\right\} \cup\left\{ p_{j}^{n,m}:1\leq j\leq n+m\right\} \\ \mathrm{PR}_{k+1}^{\Sigma} & = & \mathrm{PR}_{k}^{\Sigma}\cup\left\{ f\circ[f_{1},...,f_{r}]:f,f_{1},...,f_{r}\in\mathrm{PR}_{k}^{\Sigma}\text{, }r\geq1\right\} \cup\\ & & \;\;\;\;\left\{ R(f,\mathcal{G}):R(f,\mathcal{G})\text{ está definida y }\{f\}\cup\{\mathcal{G}_{a}:a\in\Sigma\}\subseteq\mathrm{PR}_{k}^{\Sigma}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ R(f,g):R(f,g)\text{ está definida y }f,g\in\mathrm{PR}_{k}^{\Sigma}\right\} \\ \mathrm{PR}^{\Sigma} & = & \bigcup_{k\geq0}\mathrm{PR}_{k}^{\Sigma} \end{array}\] Una función es llamada \(\Sigma\)-recursiva primitiva (\(\Sigma\)-p.r.) si pertenece a \(\mathrm{PR}^{\Sigma}\).

Proof. Lo probaremos usando la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Si \(F\in\mathrm{PR}_{k}^{\Sigma}\), entonces \(F\) es \(\Sigma\)-efectivamente computable.

Es claro que si todos los enuciados \(\mathrm{Enu}_{k}\) son verdaderos, entonces la proposición lo es. Claramente \(\mathrm{Enu}_{0}\) es verdadero. Supongamos entonces que \(\mathrm{Enu}_{k}\) es verdadero y probemos que \(\mathrm{Enu}_{k+1}\) lo es. Sea \(F\in\mathrm{PR}_{k+1}^{\Sigma}\). Si \(F\in\mathrm{PR}_{k}^{\Sigma}\), entonces \(\mathrm{Enu}_{k}\) nos garantiza que \(F\) es \(\Sigma\)-efectivamente computable. Supongamos entonces que \(F\in\mathrm{PR}_{k+1}^{\Sigma}-\mathrm{PR}_{k}^{\Sigma}\). Por definición de \(\mathrm{PR}_{k+1}^{\Sigma}\) tenemos que \(F\) se obtiene usando los constructores de composición y recursión primitiva a partir de funciones de \(\mathrm{PR}_{k}^{\Sigma}\). Pero \(\mathrm{Enu}_{k}\) nos garantiza que dichas funciones son \(\Sigma\)-efectivamente computables por lo cual los Lemas 4.3, 4.4, 4.5, 4.6 y 4.2 nos dicen que siempre \(F\) será \(\Sigma\)-efectivamente computable.  

4.2.3.1 Algunas funciones \(\Sigma\)-recursivas primitivas

En los siguientes lemas se prueba que varias funciones bien conocidas son \(\Sigma\)-recursivas primitivas.

Proof. (1) Nótese que \(\emptyset=Pred\circ C_{0}^{0,0}\in\mathrm{PR}_{1}^{\Sigma}\)

(2) Notar que \[\begin{aligned} \lambda xy\left[x+y\right](0,x_{1}) & =x_{1}=p_{1}^{1,0}(x_{1})\\ \lambda xy\left[x+y\right](t+1,x_{1}) & =\lambda xy\left[x+y\right](t,x_{1})+1\\ & =\left(Suc\circ p_{1}^{3,0}\right)\left(\lambda xy\left[x+y\right](t,x_{1}),t,x_{1}\right) \end{aligned}\] lo cual implica que \(\lambda xy\left[x+y\right]=R\left(p_{1}^{1,0},Suc\circ p_{1}^{3,0}\right)\in\mathrm{PR}_{2}^{\Sigma}.\)

(3) Primero note que \[\begin{aligned} C_{0}^{1,0}(0) & =C_{0}^{0,0}(\lozenge)\\ C_{0}^{1,0}(t+1) & =C_{0}^{1,0}(t) \end{aligned}\] lo cual implica que \(C_{0}^{1,0}=R\left(C_{0}^{0,0},p_{1}^{2,0}\right)\in\mathrm{PR}_{1}^{\Sigma}.\) También note que \[\lambda tx\left[t.x\right]=R\left(C_{0}^{1,0},\lambda xy\left[x+y\right]\circ\left[p_{1}^{3,0},p_{3}^{3,0}\right]\right),\] lo cual por (2) implica que \(\lambda tx\left[t.x\right]\in\mathrm{PR}_{4}^{\Sigma}\).

(4) Note que \[\begin{aligned} \lambda x\left[x!\right](0) & =1=C_{1}^{0,0}(\lozenge)\\ \lambda x\left[x!\right](t+1) & =\lambda x\left[x!\right](t).(t+1), \end{aligned}\] lo cual implica que \[\lambda x\left[x!\right]=R\left(C_{1}^{0,0},\lambda xy\left[x.y\right]\circ\left[p_{1}^{2,0},Suc\circ p_{2}^{2,0}\right]\right).\] Ya que \(C_{1}^{0,0}=\) \(Suc\circ C_{0}^{0,0}\), tenemos que \(C_{1}^{0,0}\in\mathrm{PR}_{1}^{\Sigma}\). Por (3), tenemos que \[\lambda xy\left[x.y\right]\circ\left[p_{1}^{2,0},Suc\circ p_{2}^{2,0}\right]\in\mathrm{PR}_{5}^{\Sigma},\] obteniendo que \(\lambda x\left[x!\right]\in\mathrm{PR}_{6}^{\Sigma}\).  

Ahora consideraremos dos funciones las cuales son obtenidas naturalmente por recursión primitiva sobre variable alfabética.

Proof. (a) Ya que \[\begin{aligned} \lambda\alpha\beta\left[\alpha\beta\right](\alpha_{1},\varepsilon) & =\alpha_{1}=p_{1}^{0,1}(\alpha_{1})\\ \lambda\alpha\beta\left[\alpha\beta\right](\alpha_{1},\alpha a) & =d_{a}(\lambda\alpha\beta\left[\alpha\beta\right](\alpha_{1},\alpha)),\ a\in\Sigma \end{aligned}\] tenemos que \(\lambda\alpha\beta\left[\alpha\beta\right]=R\left(p_{1}^{0,1},\mathcal{G}\right)\), donde \(\mathcal{G}_{a}=d_{a}\circ p_{3}^{0,3}\), para cada \(a\in\Sigma\).

(b) Ya que \[\begin{aligned} \lambda\alpha\left[\left\vert \alpha\right\vert \right](\varepsilon) & =0=C_{0}^{0,0}(\lozenge)\\ \lambda\alpha\left[\left\vert \alpha\right\vert \right](\alpha a) & =\lambda\alpha\left[\left\vert \alpha\right\vert \right](\alpha)+1 \end{aligned}\] tenemos que \(\lambda\alpha\left[\left\vert \alpha\right\vert \right]=R\left(C_{0}^{0,0},\mathcal{G}\right)\), donde \(\mathcal{G}_{a}=\) \(Suc\circ p_{1}^{1,1}\), para cada \(a\in\Sigma.\).  

Proof. Note que \(C_{k+1}^{0,0}=\) \(Suc\circ C_{k}^{0,0}\), lo cual implica \(C_{k}^{0,0}\in\mathrm{PR}_{k}^{\Sigma}\), para \(k\geq0\). También note que \(C_{\alpha a}^{0,0}=d_{a}\circ C_{\alpha}^{0,0}\), lo cual dice que \(C_{\alpha}^{0,0}\in\mathrm{PR}^{\Sigma}\), para \(\alpha\in\Sigma^{\ast}\). Para ver que \(C_{k}^{0,1}\in\mathrm{PR}^{\Sigma}\) notar que \[\begin{aligned} C_{k}^{0,1}(\varepsilon) & =k=C_{k}^{0,0}(\lozenge)\\ C_{k}^{0,1}(\alpha a) & =C_{k}^{0,1}(\alpha)=p_{1}^{1,1}\left(C_{k}^{0,1}(\alpha),\alpha\right) \end{aligned}\] lo cual implica que \(C_{k}^{0,1}=R\left(C_{k}^{0,0},\mathcal{G}\right)\), con \(\mathcal{G}_{a}=p_{1}^{1,1}\), \(a\in\Sigma\). En forma similar podemos ver que \(C_{k}^{1,0},C_{\alpha}^{1,0},C_{\alpha}^{0,1}\in\mathrm{PR}^{\Sigma}\). Supongamos ahora que \(m>0\). Entonces \[\begin{aligned} C_{k}^{n,m} & =C_{k}^{0,1}\circ p_{n+1}^{n,m}\\ C_{\alpha}^{n,m} & =C_{\alpha}^{0,1}\circ p_{n+1}^{n,m} \end{aligned}\] de lo cual obtenemos que \(C_{k}^{n,m},C_{\alpha}^{n,m}\in\mathrm{PR}^{\Sigma}\). El caso \(n>0\) es similar.  

Proof. (a) Note que \[\lambda tx\left[x^{t}\right]=R\left(C_{1}^{1,0},\lambda xy\left[x.y\right]\circ\left[p_{1}^{3,0},p_{3}^{3,0}\right]\right)\in\mathrm{PR}^{\Sigma}.\] O sea que \(\lambda xy\left[x^{y}\right]=\lambda tx\left[x^{t}\right]\circ\left[p_{2}^{2,0},p_{1}^{2,0}\right]\in\mathrm{PR}^{\Sigma}\).

(b) Note que \[\lambda t\alpha\left[\alpha^{t}\right]=R\left(C_{\varepsilon}^{0,1},\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[p_{3}^{1,2},p_{2}^{1,2}\right]\right)\in\mathrm{PR}^{\Sigma}.\]  

Ahora probaremos que si \(\Sigma\) es no vacío, entonces las biyecciones naturales entre \(\Sigma^{\ast}\) y \(\omega\), dadas en el Lema 2.3, son \(\Sigma\)-p.r..

Proof. Supongamos \(\Sigma=\{a_{1},...,a_{k}\}\) y \(\leq\) es dado por \(a_{1}<...<a_{k}\). Ya que \[\begin{aligned} s^{\leq}(\varepsilon) & =a_{1}\\ s^{\leq}(\alpha a_{i}) & =\alpha a_{i+1}\text{, para }i<k\\ s^{\leq}(\alpha a_{k}) & =s^{\leq}(\alpha)a_{1} \end{aligned}\] tenemos que \(s^{\leq}=R\left(C_{a_{1}}^{0,0},\mathcal{G}\right)\), donde \(\mathcal{G}_{a_{i}}=d_{a_{i+1}}\circ p_{1}^{0,2}\), para \(i=1,...,k-1\) y \(\mathcal{G}_{a_{k}}=d_{a_{1}}\circ p_{2}^{0,2}.\) O sea que \(s^{\leq}\in\mathrm{PR}^{\Sigma}.\) Ya que \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(t+1) & =s^{\leq}(\ast^{\leq}(t)) \end{aligned}\] podemos ver que \(\ast^{\leq}\in\mathrm{PR}^{\Sigma}\). Ya que \[\begin{aligned} \#^{\leq}(\varepsilon) & =0\\ \#^{\leq}(\alpha a_{i}) & =\#^{\leq}(\alpha).k+i\text{, para }i=1,...,k, \end{aligned}\] tenemos que \(\#^{\leq}=R\left(C_{0}^{0,0},\mathcal{G}\right)\), donde \[\mathcal{G}_{a_{i}}=\lambda xy\left[x+y\right]\circ\left[\lambda xy\left[x.y\right]\circ\left[p_{1}^{1,1},C_{k}^{1,1}\right],C_{i}^{1,1}\right]\text{, para }i=1,...,k\text{.}\] O sea que \(\#^{\leq}\in\mathrm{PR}^{\Sigma}\).  

Recordemos que llamábamos numerales a los siguientes símbolos \[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\] También recordemos que \(Num\) denotaba el conjunto de los numerales. Sea \(Sig:Num^{\ast}\rightarrow Num^{\ast}\) definida de la siguiente manera \[\begin{aligned} Sig(\varepsilon) & =1\\ Sig(\alpha0) & =\alpha1\\ Sig(\alpha1) & =\alpha2\\ Sig(\alpha2) & =\alpha3\\ Sig(\alpha3) & =\alpha4\\ Sig(\alpha4) & =\alpha5\\ Sig(\alpha5) & =\alpha6\\ Sig(\alpha6) & =\alpha7\\ Sig(\alpha7) & =\alpha8\\ Sig(\alpha8) & =\alpha9\\ Sig(\alpha9) & =Sig(\alpha)0 \end{aligned}\] Definamos \(Dec:\omega\rightarrow Num^{\ast}\) de la siguiente manera \[\begin{aligned} Dec(0) & =\varepsilon\\ Dec(n+1) & =Sig(Dec(n)) \end{aligned}\] Nótese que para \(n\in\mathbf{N}\), la palabra \(Dec(n)\) es la notación usual decimal de \(n\). Nótese que \(Sig=R(C_{1}^{0,0},\mathcal{G})\), donde \(\mathcal{G}\) es la familia \(Num\)-indexada de funciones dada por: \[\begin{aligned} \mathcal{G}_{0}=d_{1}\circ p_{2}^{0,2}\\ \mathcal{G}_{1}=d_{2}\circ p_{2}^{0,2}\\ \mathcal{G}_{2}=d_{3}\circ p_{2}^{0,2}\\ \mathcal{G}_{3}=d_{4}\circ p_{2}^{0,2}\\ \mathcal{G}_{4}=d_{5}\circ p_{2}^{0,2}\\ \mathcal{G}_{5}=d_{6}\circ p_{2}^{0,2}\\ \mathcal{G}_{6}=d_{7}\circ p_{2}^{0,2}\\ \mathcal{G}_{7}=d_{8}\circ p_{2}^{0,2}\\ \mathcal{G}_{8}=d_{9}\circ p_{2}^{0,2}\\ \mathcal{G}_{9}=d_{0}\circ p_{1}^{0,2} \end{aligned}\] por lo cual \(Sig\) es \(Num\)-p.r.. También tenemos que \(Dec=R(C_{\varepsilon}^{0,0},Sig\circ p_{2}^{1,1})\) por lo cual \(Dec\) es \(Num\)-p.r.. En la batalla Godel vence a Neumann utilizaremos el siguiente resultado.

Proof. Sea \(\widetilde{Sig}:\Gamma^{*}\rightarrow\Gamma^{*}\) definida de la siguiente manera: \[\begin{aligned} \widetilde{Sig}(\varepsilon) & =1\\ \widetilde{Sig}(\alpha0) & =\alpha1\\ \widetilde{Sig}(\alpha1) & =\alpha2\\ \widetilde{Sig}(\alpha2) & =\alpha3\\ \widetilde{Sig}(\alpha3) & =\alpha4\\ \widetilde{Sig}(\alpha4) & =\alpha5\\ \widetilde{Sig}(\alpha5) & =\alpha6\\ \widetilde{Sig}(\alpha6) & =\alpha7\\ \widetilde{Sig}(\alpha7) & =\alpha8\\ \widetilde{Sig}(\alpha8) & =\alpha9\\ \widetilde{Sig}(\alpha9) & =Sig(\alpha)0\\ \widetilde{Sig}(\alpha a) & =\varepsilon\text{, palabra }a\in\Gamma-Num \end{aligned}\] Nótese que \(\widetilde{Sig}=R(C_{1}^{0,0},\mathcal{\widetilde{G}})\), donde \(\mathcal{\widetilde{G}}\) es la familia \(\Gamma\)-indexada de funciones dada por: \[\begin{aligned} \mathcal{\widetilde{G}}_{0}=d_{1}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{1}=d_{2}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{2}=d_{3}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{3}=d_{4}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{4}=d_{5}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{5}=d_{6}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{6}=d_{7}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{7}=d_{8}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{8}=d_{9}\circ p_{2}^{0,2}\\ \mathcal{\widetilde{G}}_{9}=d_{0}\circ p_{1}^{0,2}\\ \mathcal{\widetilde{G}}_{a}=C_{\varepsilon}^{0,2}\text{, para }a\in\Gamma-Num \end{aligned}\] por lo cual \(\widetilde{Sig}\) es \(\Gamma\)-p.r. (ojo que aquí las funciones \(p_{2}^{0,2}\), \(C_{\varepsilon}^{0,2}\), \(C_{1}^{0,0}\) y \(d_{0},d_{1},d_{2},...,d_{9}\) son relativas al alfabeto \(\Gamma\)). Pero nótese que \[\begin{aligned} Dec(0) & =\varepsilon\\ Dec(n+1) & =\widetilde{Sig}(Dec(n))\text{, para cada }n\in\omega \end{aligned}\] lo cual nos dice que \(Dec=R(C_{\varepsilon}^{0,0},\widetilde{Sig}\circ p_{2}^{1,1})\) por lo cual \(Dec\) es \(\Gamma\)-p.r. (de nuevo, aquí las funciones \(C_{\varepsilon}^{0,0}\) y \(p_{2}^{1,1}\) son relativas al alfabeto \(\Gamma\)).  

Dados \(x,y\in\omega\), definamos \[x\dot{-}y=\max(x-y,0).\]

Proof. (a) Primero notar que \(\lambda x\left[x\dot{-}1\right]=R\left(C_{0}^{0,0},p_{2}^{2,0}\right)\in\mathrm{PR}^{\Sigma}.\) También note que \[\lambda tx\left[x\dot{-}t\right]=R\left(p_{1}^{1,0},\lambda x\left[x\dot{-}1\right]\circ p_{1}^{3,0}\right)\in\mathrm{PR}^{\Sigma}.\] O sea que \(\lambda xy\left[x\dot{-}y\right]=\lambda tx\left[x\dot{-}t\right]\circ\left[p_{2}^{2,0},p_{1}^{2,0}\right]\in\mathrm{PR}^{\Sigma}\).

(b) Note que \(\lambda xy\left[\max(x,y)\right]=\lambda xy\left[x+(y\dot{-}x)\right]\).

(c) Note que \(\lambda xy\left[x=y\right]=\lambda xy\left[1\dot{-}((x\dot{-}y)+(y\dot{-}x))\right]\).

(d) Note que \(\lambda xy\left[x\leq y\right]=\lambda xy\left[1\dot{-}(x\dot{-}y)\right]\).

(e) Sea \(\leq\) un orden total sobre \(\Sigma.\) Ya que \[\alpha=\beta\text{ sii }\#^{\leq}(\alpha)=\#^{\leq}(\beta)\] tenemos que \[\lambda\alpha\beta\left[\alpha=\beta\right]=\lambda xy\left[x=y\right]\circ\left[\#^{\leq}\circ p_{1}^{0,2},\#^{\leq}\circ p_{2}^{0,2}\right]\] lo cual nos dice que \(\lambda\alpha\beta\left[\alpha=\beta\right]\) es \(\Sigma\)-p.r.  

4.2.3.2 Operaciones lógicas entre predicados

Dados predicados \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), predicados con el mismo dominio, definamos nuevos predicados \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) de la siguiente manera \[\begin{aligned} & \begin{array}{rll} (P\vee Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ o }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\\ & \begin{array}{rll} (P\wedge Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ y }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\\ & \begin{array}{rll} \lnot P:S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=0\\ 0 & & \text{si }P(\vec{x},\vec{\alpha})=1 \end{array}\right. \end{array} \end{aligned}\]

Proof. Note que \[\begin{aligned} \lnot P & =\lambda xy\left[x\dot{-}y\right]\circ\left[C_{1}^{n,m},P\right]\\ (P\wedge Q) & =\lambda xy\left[x.y\right]\circ[P,Q]\\ (P\vee Q) & =\lnot(\lnot P\wedge\lnot Q). \end{aligned}\]  

4.2.3.3 Conjuntos \(\Sigma\)-recursivos primitivos

Un conjunto \(\Sigma\)-mixto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es llamado \(\Sigma\)-recursivo primitivo si su función característica \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. (Nótese que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es el predicado \(\lambda\vec{x}\vec{\alpha}\left[(\vec{x},\vec{\alpha})\in S\right]\).)

Proof. Note que \[\begin{aligned} \chi_{S_{1}\cup S_{2}}^{\omega^{n}\times\Sigma^{\ast m}} & =(\chi_{S_{1}}^{\omega^{n}\times\Sigma^{\ast m}}\vee\chi_{S_{2}}^{\omega^{n}\times\Sigma^{\ast m}})\\ \chi_{S_{1}\cap S_{2}}^{\omega^{n}\times\Sigma^{\ast m}} & =(\chi_{S_{1}}^{\omega^{n}\times\Sigma^{\ast m}}\wedge\chi_{S_{2}}^{\omega^{n}\times\Sigma^{\ast m}})\\ \chi_{S_{1}-S_{2}}^{\omega^{n}\times\Sigma^{\ast m}} & =\lambda xy\left[x\dot{-}y\right]\circ\left[\chi_{S_{1}}^{\omega^{n}\times\Sigma^{\ast m}},\chi_{S_{2}}^{\omega^{n}\times\Sigma^{\ast m}}\right] \end{aligned}\]  

Proof. Si \(S=\emptyset\), entonces es claro que \(S\) es \(\Sigma\)-p.r.. Probaremos ahora el lema para el caso en que \(S\) tiene un solo elemento. Supongamos entonces \[S=\{(z_{1},...,z_{n},\gamma_{1},...,\gamma_{m})\}.\] Note que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es el siguiente predicado \[\left(\chi_{\{z_{1}\}}^{\omega}\circ p_{1}^{n,m}\wedge...\wedge\chi_{\{z_{n}\}}^{\omega}\circ p_{n}^{n,m}\wedge\chi_{\{\gamma_{1}\}}^{\Sigma^{\ast}}\circ p_{n+1}^{n,m}\wedge...\wedge\chi_{\{\gamma_{m}\}}^{\Sigma^{\ast}}\circ p_{n+m}^{n,m}\right).\] Ya que los predicados \[\begin{aligned} \chi_{\{z_{i}\}}^{\omega} & =\lambda xy\left[x=y\right]\circ\left[p_{1}^{1,0},C_{z_{i}}^{1,0}\right]\\ \chi_{\{\gamma_{i}\}}^{\Sigma^{\ast}} & =\lambda\alpha\beta\left[\alpha=\beta\right]\circ\left[p_{1}^{0,1},C_{\gamma_{i}}^{0,1}\right] \end{aligned}\] son \(\Sigma\)-p.r., el Lema 4.14 (aplicado \((n+m)-1\) veces), implica que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. Cuando \(S\) tiene mas de un elemento, ya que entonces es la unión de una cantidad finita de conjuntos de un solo elemento, se puede aplicar el Lema 4.15 (\(\left\vert S\right\vert -1\) veces) para obtener que \(S\) es \(\Sigma\)-p.r..  

El siguiente lema caracteriza cuando un conjunto rectangular es \(\Sigma\)-p.r..

Proof. (\(\Rightarrow\)) Veremos por ejemplo que \(L_{1}\) es \(\Sigma\)-p.r.. Sea \((z_{1},...,z_{n},\zeta_{1},...,\zeta_{m})\) un elemento fijo de \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}.\) Note que \[\alpha\in L_{1}\text{ sii }(z_{1},...,z_{n},\alpha,\zeta_{2},...,\zeta_{m})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m},\] lo cual implica que \[\chi_{L_{1}}^{\Sigma^{\ast}}=\chi_{S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}^{\omega^{n}\times\Sigma^{\ast m}}\circ\left[C_{z_{1}}^{0,1},...,C_{z_{n}}^{0,1},p_{1}^{0,1},C_{\zeta_{2}}^{0,1},...,C_{\zeta_{m}}^{0,1}\right]\] (\(\Leftarrow\)) Note que \(\chi_{S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}^{\omega^{n}\times\Sigma^{\ast m}}\) es el predicado \[\left(\chi_{S_{1}}^{\omega}\circ p_{1}^{n,m}\wedge...\wedge\chi_{S_{n}}^{\omega}\circ p_{n}^{n,m}\wedge\chi_{L_{1}}^{\Sigma^{\ast}}\circ p_{n+1}^{n,m}\wedge...\wedge\chi_{L_{m}}^{\Sigma^{\ast}}\circ p_{n+m}^{n,m}\right).\]  

Dada una función \(f\) y un conjunto \(S\subseteq D_{f}\), usaremos \(f|_{S}\) para denotar la restricción de \(f\) al conjunto \(S\), i.e. \(f|_{S}=f\cap(S\times I_{f})\). Nótese que \(f|_{S}\) es la función dada por \[D_{f|_{S}}=S\ \ \ \text{y}\ \ \ f|_{S}(e)=f(e)\text{, para cada }e\in S\]

Proof. Supongamos \(O=\Sigma^{\ast}\). Entonces \[f|_{S}=\lambda x\alpha\left[\alpha^{x}\right]\circ\left[Suc\circ Pred\circ\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}},f\right]\] lo cual nos dice que \(f|_{S}\) es \(\Sigma\)-p.r.. El caso \(O=\omega\) es similar usando \(\lambda xy\left[x^{y}\right]\) en lugar de \(\lambda x\alpha\left[\alpha^{x}\right]\).  

Usando el lema anterior en combinación con el Lema 4.14 podemos ver que muchos predicados usuales son \(\Sigma\)-p.r.. Por ejemplo sea \[P=\lambda x\alpha\beta\gamma\left[x=\left\vert \gamma\right\vert \wedge\alpha=\gamma^{Pred(\left\vert \beta\right\vert )}\right].\] Nótese que \[D_{P}=\omega\times\Sigma^{\ast}\times(\Sigma^{\ast}-\{\varepsilon\})\times\Sigma^{\ast}\] es \(\Sigma\)-p.r. ya que \[\chi_{D_{P}}^{\omega\times\Sigma^{\ast3}}=\lnot\lambda\alpha\beta\left[\alpha=\beta\right]\circ\left[p_{3}^{1,3},C_{\varepsilon}^{1,3}\right]\] También note que los predicados \[\begin{aligned} & \lambda x\alpha\beta\gamma\left[x=\left\vert \gamma\right\vert \right]\\ & \lambda x\alpha\beta\gamma\left[\alpha=\gamma^{Pred(\left\vert \beta\right\vert )}\right] \end{aligned}\] son \(\Sigma\)-p.r. ya que pueden obtenerse componiendo funciones \(\Sigma\)-p.r.. O sea que \(P\) es \(\Sigma\)-p.r. ya que \[P=\left(\lambda x\alpha\beta\gamma\left[x=\left\vert \gamma\right\vert \right]|_{D_{P}}\wedge\lambda x\alpha\beta\gamma\left[\alpha=\gamma^{Pred(\left\vert \beta\right\vert )}\right]\right).\]

Proof. Lo probaremos usando la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Supongamos \(F:D_{F}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), con \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\), es una función perteneciente a \(\mathrm{PR}_{k}^{\Sigma}\). Entonces existe una función \(\Sigma\)-p.r. \(\bar{F}:\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), tal que \(F=\bar{F}|_{D_{F}}\).

Es claro que si todos los enunciados \(\mathrm{Enu}_{k}\) son verdaderos, entonces el lema lo es. Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Ya que \(F\in\mathrm{PR}_{0}^{\Sigma}\), salvo el caso en que \(F=Pred\), podemos tomar siempre \(\bar{F}=F\). Cuando \(F=Pred\) podemos tomar \(\bar{F}=\lambda x\left[x\dot{-}1\right]\) la cual ya hemos visto es \(\Sigma\)-p.r..

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Sea \(F\in\mathrm{PR}_{k+1}^{\Sigma}\). Si \(F\in\mathrm{PR}_{k}^{\Sigma}\), entonces \(\mathrm{Enu}_{k}\) nos garantiza que se cumple \(\mathrm{Enu}_{k+1}\) para \(F\). Supongamos entonces que \(F\in\mathrm{PR}_{k+1}^{\Sigma}-\mathrm{PR}_{k}^{\Sigma}\). Por definición de \(\mathrm{PR}_{k+1}^{\Sigma}\) tenemos varios casos:

Caso \(F=f\circ[f_{1},...,f_{r}]\), con \(f,f_{1},...,f_{r}\in\mathrm{PR}_{k}^{\Sigma}\text{, }r\geq1\) y \(O=\omega\). Si \(F=\emptyset\) es fácil ver que podemos tomar \(\bar{F}=C_{0}^{n,m}\). Supongamos entonces que \(F\neq\emptyset\). Por el Lema de Composición no Vacía tenemos que hay \(n',m'\in\omega\) tales que

1. adhocprefix-adhocsufix \(r=n'+m'\)

2. adhocprefix-adhocsufix \(f\) es de tipo \((n',m',\#)\)

3. adhocprefix-adhocsufix \(f_{i}\) es de tipo \((n,m,\#)\), para cada \(i=1,...,n'\)

4. adhocprefix-adhocsufix \(f_{i}\) es de tipo \((n,m,\ast)\), para cada \(i=n'+1,...,n'+m'\)

Ya que es veradero \(\mathrm{Enu}_{k}\) tenemos que hay funciones \(\Sigma\)-p.r.

1. adhocprefix-adhocsufix \(\bar{f}:\omega^{n'}\times\Sigma^{\ast m'}\rightarrow\omega\)

2. adhocprefix-adhocsufix \(\bar{f_{i}}:\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), para cada \(i=1,...,n'\)

3. adhocprefix-adhocsufix \(\bar{f_{i}}:\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\), para cada \(i=n'+1,...,n'+m'\)

tales que

1. adhocprefix-adhocsufix \(\bar{f}|_{D_{f}}=f\)

2. adhocprefix-adhocsufix \(\bar{f_{i}}|_{D_{f_{i}}}\), para cada \(i=1,...,n'\)

3. adhocprefix-adhocsufix \(\bar{f_{i}}|_{D_{f_{i}}}\), para cada \(i=n'+1,...,n'+m'\)

Definamos \(\bar{F}=\bar{f}\circ[\bar{f_{1}},...,\overline{f_{n'+m'}}]\). Note que \(D_{\bar{F}}=\omega^{n}\times\Sigma^{\ast m}\). Además es claro que \(\bar{F}\) es \(\Sigma\)-p.r. ya que \(\bar{f},\bar{f_{1}},...,\overline{f_{n'+m'}}\) lo son. Dejamos al lector el fácil chequeo de que \(F=\bar{F}|_{D_{F}}\).

Caso \(F=f\circ[f_{1},...,f_{r}]\), con \(f,f_{1},...,f_{r}\in\mathrm{PR}_{k}^{\Sigma}\text{, }r\geq1\) y \(O=\Sigma^{*}\). Completamente análogo al anterior.

Los otros casos son similares y dejados al lector.  

Ahora podemos probar el siguiente importante resultado

Proof. (\(\Rightarrow\)) Supongamos que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Ya que \(S\) es \(\Sigma\)-p.r. por definición tenemos que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. O sea que \(Pred\circ\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. Pero note que \(S=D_{Pred\circ\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}}\).

(\(\Leftarrow\)) Lo probaremos usando la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Si \(F\in\mathrm{PR}_{k}^{\Sigma}\), entonces \(D_{F}\) es \(\Sigma\)-p.r..

Es claro que si todos los enuciados \(\mathrm{Enu}_{k}\) son verdaderos, entonces (\(\Leftarrow\)) de la proposición lo es. Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Es dejada al lector.

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos \(\mathrm{Enu}_{k}\) es verdadero. Sea \(F\in\mathrm{PR}_{k+1}^{\Sigma}\). Por definición de \(\mathrm{PR}_{k+1}^{\Sigma}\) tenemos varios casos.

Caso \(F\in\mathrm{PR}_{k}^{\Sigma}\). Ya que \(\mathrm{Enu}_{k}\) es veradero, tenemos que \(D_{F}\) es \(\Sigma\)-p.r.. por lo cual se cumple \(\mathrm{Enu}_{k+1}\) para \(F\).

Caso \(F=R(f,g)\), donde \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\\ g & :\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}, \end{aligned}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacíos y \(f,g\in\mathrm{PR}_{k}^{\Sigma}\). Nótese que por definición de \(R(f,g)\), tenemos que \[D_{F}=\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}.\] Ya que \(\mathrm{Enu}_{k}\) es verdadero tenemos que \(D_{f}=S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-p.r., lo cual por el Lema 4.16 nos dice que los conjuntos \(S_{1},...,S_{n}\), \(L_{1},...,L_{m}\) son \(\Sigma\)-p.r.. Ya que \(\omega\) es \(\Sigma\)-p.r., el Lema 4.16 nos dice que \(D_{F}\) es \(\Sigma\)-p.r..

Los otros casos de recursión primitiva son similares y dejados al lector.

Caso \(F=f\circ[f_{1},...,f_{r}]\) con \(f,f_{1},...,f_{r}\in\mathrm{PR}_{k}^{\Sigma}\) y \(r\geq1\). Si \(F=\emptyset\), entonces es claro que \(D_{F}=\emptyset\) es \(\Sigma\)-p.r.. Supongamos entonces que \(F\) no es la función \(\emptyset\). Por el Lema de Composición no Vacía tenemos que \(r\) es de la forma \(n+m\) y \[\begin{aligned} f & :D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\\ f_{i} & :D_{f_{i}}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega\text{, }i=1,...,n\\ f_{i} & :D_{f_{i}}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\Sigma^{\ast},i=n+1,...,n+m \end{aligned}\] con \(O\in\{\omega,\Sigma^{\ast}\}\) y \(k,l\in\omega\). Por Lema 4.18, hay funciones \(\Sigma\)-p.r. \(\bar{f}_{1},...,\bar{f}_{n+m}\) las cuales tienen dominio \(\omega^{k}\times\Sigma^{\ast l}\) y cumplen \[f_{i}=\bar{f}_{i}|_{D_{f_{i}}}\text{, para }i=1,...,n+m.\] Ya que \(\mathrm{Enu}_{k}\) es verdadero tenemos que los conjuntos \(D_{f}\), \(D_{f_{i}}\), \(i=1,...,n+m\), son \(\Sigma\)-p.r. y por lo tanto el Lema 4.15 aplicado \((n+m)-1\) veces nos dice que \[S=\bigcap_{i=1}^{n+m}D_{f_{i}}\] es \(\Sigma\)-p.r.. Nótese que \[\chi_{D_{F}}^{\omega^{k}\times\Sigma^{\ast l}}=(\chi_{D_{f}}^{\omega^{n}\times\Sigma^{\ast m}}\circ\left[\bar{f}_{1},...,\bar{f}_{n+m}\right]\wedge\chi_{S}^{\omega^{k}\times\Sigma^{\ast l}})\] lo cual nos dice que \(D_{F}\) es \(\Sigma\)-p.r..  

4.2.3.4 Lema de división por casos para funciones \(\Sigma\)-p.r.

Una observación interesante es que si \(f_{i}:D_{f_{i}}\rightarrow O\), \(i=1,...,k\), son funciones tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\), entonces \(f_{1}\cup...\cup f_{k}\) es la función \[\begin{array}{rll} D_{f_{1}}\cup...\cup D_{f_{k}} & \rightarrow & O\\ e & \rightarrow & \left\{ \begin{array}{clc} f_{1}(e) & & \text{si }e\in D_{f_{1}}\\ \vdots & & \vdots\\ f_{k}(e) & & \text{si }e\in D_{f_{k}} \end{array}\right. \end{array}\]

Proof. El caso \(k=1\) es trivial. Probaremos usando la Regla de Inducción desde 2 que vale para \(k\geq2\). Para cada \(k\geq2\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Supongamos \(f_{i}:D_{f_{i}}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), \(i=1,...,k\), son funciones \(\Sigma\)-p.r., con \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Si \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) cada ves que \(i\neq j\), entonces \(f_{1}\cup...\cup f_{k}\) es \(\Sigma\)-p.r..

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(2\).

Prueba de que \(\mathrm{Enu}_{2}\) es verdadero. Supongamos \(O=\Sigma^{\ast}\). Sean \[\bar{f}_{i}:\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast},i=1,2,\] funciones \(\Sigma\)-p.r. tales que \(\bar{f}_{i}|_{D_{f_{i}}}=f_{i}\), \(i=1,2\) (Lema 4.18)\(.\) Por la Proposición 4.4 los conjuntos \(D_{f_{1}}\) y \(D_{f_{2}}\) son \(\Sigma\)-p.r. y por lo tanto lo es \(D_{f_{1}}\cup D_{f_{2}}\). Ya que \[f_{1}\cup f_{2}=\left(\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[\lambda x\alpha\left[\alpha^{x}\right]\circ\left[\chi_{D_{f_{1}}}^{\omega^{n}\times\Sigma^{\ast m}},\bar{f}_{1}\right],\lambda x\alpha\left[\alpha^{x}\right]\circ\left[\chi_{D_{f_{2}}}^{\omega^{n}\times\Sigma^{\ast m}},\bar{f}_{2}\right]\right]\right)|_{D_{f_{1}}\cup D_{f_{2}}}\] tenemos que \(f_{1}\cup f_{2}\) es \(\Sigma\)-p.r.. El caso \(O=\omega\) es similar usando \(\lambda xy\left[x.y\right]\) y \(\lambda xy\left[y^{x}\right]\) en lugar de \(\lambda\alpha\beta\left[\alpha\beta\right]\) y \(\lambda x\alpha\left[\alpha^{x}\right]\).

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Sean \(f_{i}:D_{f_{i}}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), \(i=1,...,k+1\), funciones \(\Sigma\)-p.r. tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j.\) Aplicando \(\mathrm{Enu}_{k}\) a las funciones \(f_{i}:D_{f_{i}}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), \(i=1,...,k\) obtenemos que \(f_{1}\cup...\cup f_{k}\) es \(\Sigma\)-p.r.. Aplicando \(\mathrm{Enu}_{2}\) (que ya fue probado) tenemos que \((f_{1}\cup...\cup f_{k})\cup f_{k+1}\) es \(\Sigma\)-p.r.. Pero \[f_{1}\cup...\cup f_{k+1}=(f_{1}\cup...\cup f_{k})\cup f_{k+1}\] por lo cual \(f_{1}\cup...\cup f_{k+1}\) es \(\Sigma\)-p.r., obteniendo que \(\mathrm{Enu}_{k+1}\) es verdadero.  

Proof. Supongamos \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), con \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Si \(D_{f}\) es vacío entonces \(f=\emptyset\) y por lo tanto \(f\) es \(\Sigma\)-p.r.. Supongamos entonces que \(D_{f}=\{e_{1},...,e_{k}\}\) con \(k\geq1\). Por el Corolario 4.1, cada \(\{e_{i}\}\) es \(\Sigma\)-p.r. por lo cual el Lema 4.17 nos dice que \(C_{f(e_{i})}^{n,m}|_{\{e_{i}\}}\) es \(\Sigma\)-p.r.. O sea que \[f=C_{f(e_{1})}^{n,m}|_{\{e_{1}\}}\cup...\cup C_{f(e_{k})}^{n,m}|_{\{e_{k}\}}\] es \(\Sigma\)-p.r., por el lema anterior.  

• CONSEJO IMPORTANTE: Si uno quiere usar el lema de división por casos para probar que una función \(f\) es \(\Sigma\)-p.r., entonces lo primero que hay que hacer, antes de ver que algo sea \(\Sigma\)-p.r. o no, es (a lo mariposa) definir correctamente funciones \(f_{1},...,f_{k}\) tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\) y además \(f_{1}\cup...\cup f_{k}=f\). Consejos para encontrar dichas funciones:

  • Determinar el \(k\), es decir, \(k\) es justamente la cantidad de "casos" en la descripción de \(f\)

  • Para cada "caso" de la descripción de \(f\), asociar un subconjunto del dominio de \(f\) el cual sea justamente definido por la propiedad correspondiente a ese caso. Ojo que dijimos subconjunto de \(D_{f}\), no confundir los tipos!! (a veces los casos se describen usando no todas las variables de las cuales depende la función)

  • Notar que los subconjuntos \(S_{1},...,S_{k}\) así definidos deben ser disjuntos de a pares y unidos deben dar el dominio de \(f\)

  • Para cada \(i\) definir \(f_{i}\) de la siguiente manera:

    1. Dominio de \(f_{i}=S_{i}\)

    2. Regla de asignación de \(f_{i}\) dada por la regla que describe \(f\) para el caso \(i\)-ésimo

    A veces se puede describir \(f_{i}\) como la restricción a \(S_{i}\) de una función con dominio mas amplio de la cual ya sabemos que es \(\Sigma\)-p.r..

  • Probar que cada \(f_{i}\) es \(\Sigma\)-p.r.. Cuando \(f_{i}\) es la restricción a \(S_{i}\) de una función \(\Sigma\)-p.r. con dominio mas amplio entonces basta con probar que \(S_{i}\) es \(\Sigma\)-p.r. y aplicar el Lema 4.17.

Recordemos que dados \(i\in\omega\) y \(\alpha\in\Sigma^{\ast}\), definimos \[\left[\alpha\right]_{i}=\left\{ \begin{array}{lll} i\text{-esimo elemento de }\alpha & & \text{si }1\leq i\leq\left\vert \alpha\right\vert \\ \varepsilon & & \text{caso contrario} \end{array}\right.\]

Proof. Note que \[\begin{aligned} _{i} & =\varepsilon\\{} [\alpha a]_{i} & =\left\{ \begin{array}{lll} [\alpha]_{i} & & \text{si }i\neq\left\vert \alpha\right\vert +1\\ a & & \text{si }i=\left\vert \alpha\right\vert +1 \end{array}\right. \end{aligned}\] lo cual dice que \(\lambda i\alpha\left[[\alpha]_{i}\right]=R\left(C_{\varepsilon}^{1,0},\mathcal{G}\right)\), donde \(\mathcal{G}_{a}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}\) es dada por \[\mathcal{G}_{a}(i,\alpha,\zeta)=\left\{ \begin{array}{lll} \zeta & & \text{si }i\neq\left\vert \alpha\right\vert +1\\ a & & \text{si }i=\left\vert \alpha\right\vert +1 \end{array}\right.\] O sea que sólo resta probar que cada \(\mathcal{G}_{a}\) es \(\Sigma\)-p.r.. Tomemos entonces \(a\in\Sigma\) fijo. Definamos \[\begin{aligned} S_{1} & =\left\{ (i,\alpha,\zeta)\in\omega\times\Sigma^{\ast}\times\Sigma^{\ast}:i\neq\left\vert \alpha\right\vert +1\right\} \\ S_{2} & =\left\{ (i,\alpha,\zeta)\in\omega\times\Sigma^{\ast}\times\Sigma^{\ast}:i=\left\vert \alpha\right\vert +1\right\} \end{aligned}\] Nótese que estos conjuntos son disjuntos y \[\mathcal{G}_{a}=p_{3}^{1,2}|_{S_{1}}\cup C_{a}^{1,2}|_{S_{2}}\] O sea que para aplicar el Lema 4.19 debemos probar que \(p_{3}^{1,2}|_{S_{1}}\) y \(C_{a}^{1,2}|_{S_{2}}\) son \(\Sigma\)-p.r.. Ya que \(p_{3}^{1,2}\) y \(C_{a}^{1,2}\) lo son, basta con probar que \(S_{1}\) y \(S_{2}\) son \(\Sigma\)-p.r. y aplicar entonces el Lema 4.17. Pero nótese que \[\begin{aligned} \chi_{S_{1}}^{\omega\times\Sigma^{\ast}\times\Sigma^{\ast}} & =\lambda xy\left[x\neq y\right]\circ\left[p_{1}^{1,2},Suc\circ\lambda\alpha\left[\left\vert \alpha\right\vert \right]\circ p_{2}^{1,2}\right]\\ \chi_{S_{2}}^{\omega\times\Sigma^{\ast}\times\Sigma^{\ast}} & =\lambda xy\left[x=y\right]\circ\left[p_{1}^{1,2},Suc\circ\lambda\alpha\left[\left\vert \alpha\right\vert \right]\circ p_{2}^{1,2}\right] \end{aligned}\] lo cual garantiza que \(S_{1}\) y \(S_{2}\) son \(\Sigma\)-p.r., concluyendo la prueba de que \(\mathcal{G}_{a}\) es \(\Sigma\)-p.r..  

4.2.3.5 Sumatoria, productoria y concatenatoria de funciones \(\Sigma\)-p.r.

Sea \(\Sigma\) un alfabeto finito. Sea \(f:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\), con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacíos. Para \(x,y\in\omega\) y \((\vec{x},\vec{\alpha})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\), definamos \[\begin{aligned} \sum\limits_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 0 & & \text{si }x>y\\ f(x,\vec{x},\vec{\alpha})+f(x+1,\vec{x},\vec{\alpha})+...+f(y,\vec{x},\vec{\alpha}) & & \text{si }x\leq y \end{array}\right.\\ \prod\limits_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 1 & & \text{si }x>y\\ f(x,\vec{x},\vec{\alpha}).f(x+1,\vec{x},\vec{\alpha})....f(y,\vec{x},\vec{\alpha}) & & \text{si }x\leq y \end{array}\right. \end{aligned}\] En forma similar, cuando \(I_{f}\subseteq\Sigma^{\ast}\), definamos \[\overset{t=y}{\underset{t=x}{\subset}}f(t,\vec{x},\vec{\alpha})=\left\{ \begin{array}{lll} \varepsilon & & \text{si }x>y\\ f(x,\vec{x},\vec{\alpha})f(x+1,\vec{x},\vec{\alpha})....f(y,\vec{x},\vec{\alpha}) & & \text{si }x\leq y \end{array}\right.\] Note que, en virtud de la definición anterior, el dominio de las funciones \[\lambda xy\vec{x}\vec{\alpha}\left[\sum_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\ \ \ \ \ \ \ \ \ \ \ \ \lambda xy\vec{x}\vec{\alpha}\left[\prod_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\ \ \ \ \ \ \ \ \ \ \ \ \lambda xy\vec{x}\vec{\alpha}\left[\subset_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\] es \(\omega\times\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\).

Dejamos al lector que analice en las consideraciones de recién el caso \(n=m=0\) (es decir cuando \(D_{f}=\omega\)).

Proof. (a) Sea \(G=\lambda tx\vec{x}\vec{\alpha}\left[\sum_{i=x}^{i=t}f(i,\vec{x},\vec{\alpha})\right]\). Ya que \[\lambda xy\vec{x}\vec{\alpha}\left[\sum_{i=x}^{i=y}f(i,\vec{x},\vec{\alpha})\right]=G\circ\left[p_{2}^{n+2,m},p_{1}^{n+2,m},p_{3}^{n+2,m},...,p_{n+m+2}^{n+2,m}\right]\] solo tenemos que probar que \(G\) es \(\Sigma\)-p.r.. Primero note que \[\begin{aligned} G(0,x,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 0 & & \text{si }x>0\\ f(0,\vec{x},\vec{\alpha}) & & \text{si }x=0 \end{array}\right.\\ G(t+1,x,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 0 & & \text{si }x>t+1\\ G(t,x,\vec{x},\vec{\alpha})+f(t+1,\vec{x},\vec{\alpha}) & & \text{si }x\leq t+1 \end{array}\right. \end{aligned}\] O sea que si definimos \[\begin{array}{rll} h:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m} & \rightarrow & \omega\\ (x,\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 0 & & \text{si }x>0\\ f(0,\vec{x},\vec{\alpha}) & & \text{si }x=0 \end{array}\right. \end{array}\] \[\begin{array}{rll} g:\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m} & \rightarrow & \omega\\ (A,t,x,\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 0 & & \text{si }x>t+1\\ A+f(t+1,\vec{x},\vec{\alpha}) & & \text{si }x\leq t+1 \end{array}\right. \end{array}\] tenemos que \(G=R(h,g)\). Es decir que solo nos falta probar que \(h\) y \(g\) son \(\Sigma\)-p.r.. Nótese que \[\begin{aligned} h & =C_{0}^{n+1,m}|_{D_{1}}\cup\lambda x\vec{x}\vec{\alpha}\left[f(0,\vec{x},\vec{\alpha})\right]|_{D_{2}}\\ g & =C_{0}^{n+3,m}|_{H_{1}}\cup\lambda Atx\vec{x}\vec{\alpha}\left[A+f(t+1,\vec{x},\vec{\alpha})\right])|_{H_{2}} \end{aligned}\] asique para ver que \(h\) y \(g\) son \(\Sigma\)-p.r. podemos aplicar el Lema 4.19 una ves que hayamos visto que las funciones \[\begin{aligned} & C_{0}^{n+1,m}|_{D_{1}}\text{ \ensuremath{} \ensuremath{} }\lambda x\vec{x}\vec{\alpha}\left[f(0,\vec{x},\vec{\alpha})\right]|_{D_{2}}\\ & C_{0}^{n+3,m}|_{H_{1}}\text{ \ensuremath{} \ensuremath{} }\lambda Atx\vec{x}\vec{\alpha}\left[A+f(t+1,\vec{x},\vec{\alpha})\right])|_{H_{2}} \end{aligned}\] son \(\Sigma\)-p.r.. Es claro que \(C_{0}^{n+1,m}\) y \(C_{0}^{n+3,m}\) son \(\Sigma\)-p.r.. También nótese que \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[f(0,\vec{x},\vec{\alpha})\right] & =f\circ\left[C_{0}^{n+1,m},p_{2}^{n+1,m},p_{3}^{n+1,m},...,p_{n+1+m}^{n+1,m}\right]\\ \lambda Atx\vec{x}\vec{\alpha}\left[A+f(t+1,\vec{x},\vec{\alpha})\right]) & =\lambda xy[x+y]\circ\left[p_{1}^{n+3,m},f\circ\left[Suc\circ p_{2}^{n+3,m},p_{4}^{n+3,m},...,p_{n+3+m}^{n+3,m}\right]\right] \end{aligned}\] lo cual, ya que \(f\) es \(\Sigma\)-p.r., nos dice que \(\lambda x\vec{x}\vec{\alpha}\left[f(0,\vec{x},\vec{\alpha})\right]\) y \(\lambda Atx\vec{x}\vec{\alpha}\left[A+f(t+1,\vec{x},\vec{\alpha})\right])\) son \(\Sigma\)-p.r.. O sea que el Lema 4.17 nos dice que solo nos resta probar que \[\begin{aligned} D_{1} & =\left\{ (x,\vec{x},\vec{\alpha})\in\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x>0\right\} \\ D_{2} & =\left\{ (x,\vec{x},\vec{\alpha})\in\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x=0\right\} \\ H_{1} & =\left\{ (z,t,x,\vec{x},\vec{\alpha})\in\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x>t+1\right\} \\ H_{2} & =\left\{ (z,t,x,\vec{x},\vec{\alpha})\in\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x\leq t+1\right\} . \end{aligned}\] son \(\Sigma\)-p.r.. Veamos por ejemplo que \(H_{1}\) lo es. Es decir debemos ver que \(\chi_{H_{1}}^{\omega^{3+n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. Ya que \(f\) es \(\Sigma\)-p.r. tenemos que \(D_{f}=\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-p.r., lo cual por el Lema 4.16 nos dice que los conjuntos \(S_{1},...,S_{n}\), \(L_{1},...,L_{m}\) son \(\Sigma\)-p.r.. Ya que \(\omega\) es \(\Sigma\)-p.r., el Lema 4.16 nos dice que \[R=\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\] es \(\Sigma\)-p.r.. Nótese que \[\chi_{H_{1}}^{\omega^{3+n}\times\Sigma^{\ast m}}=(\chi_{R}^{\omega^{3+n}\times\Sigma^{\ast m}}\wedge\lambda ztx\vec{x}\vec{\alpha}\left[x>t+1\right])\] por lo cual \(\chi_{H_{1}}^{\omega^{3+n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r. ya que es la conjunción de dos predicados \(\Sigma\)-p.r. La prueba de que \(D_{1},D_{2}\text{ y }H_{2}\) son \(\Sigma\)-p.r. es similar.

(b) Se prueba en forma análoga a la prueba de (a).  

Veamos un ejemplo de como se puede aplicar el lema anterior. Sea \(F=\lambda yx_{1}\left[\sum_{t=0}^{t=y}(x_{1})^{t}\right]\). Es claro que \(D_{F}=\omega^{2}\). Para ver que \(F\) es \(\Sigma\)-p.r. aplicaremos el lema anterior por lo cual es importante encontrar la \(f\) adecuada a la cual se le aplicara el lema. Tomemos \(f=\lambda tx_{1}[(x_{1})^{t}]\). Claramente \(f\) es \(\Sigma\)-p.r. por lo cual el lema anterior nos dice que \[G=\lambda xyx_{1}\left[\sum_{t=x}^{t=y}f(t,x_{1})\right]=\lambda xyx_{1}\left[\sum_{t=x}^{t=y}(x_{1})^{t}\right]\] es \(\Sigma\)-p.r.. Claramente \(G\) no es la función \(F\) pero es en algún sentido "mas amplia" que \(F\) ya que tiene una variable mas y se tiene que \(F(y,x_{1})=G(0,y,x_{1})\), para cada \(y,x_{1}\in\omega\). Es fácil ver que \[F=G\circ\left[C_{0}^{2,0},p_{1}^{2,0},p_{2}^{2,0}\right]\] por lo cual \(F\) es \(\Sigma\)-p.r..

4.2.3.6 Cuantificación acotada de predicados \(\Sigma\)-p.r. con dominio rectangular

Sea \(P:S\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\) un predicado, con \(n,m\in\omega\). Supongamos además que \(S,S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) son no vacíos. Sea \(\bar{S}\subseteq S\). Entonces la expresión Booleana \[(\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\] depende de las variables \(x,\vec{x},\vec{\alpha}\) y valdrá \(1\) en una \((1+n+m)\)-upla \((x,\vec{x},\vec{\alpha})\) cuando \(P(t,\vec{x},\vec{\alpha})\) sea igual a \(1\) para cada \(t\in\{u\in\bar{S}:u\leq x\}\); y \(0\) en caso contrario. Nótese que aquí es crucial que \(\bar{S}\subseteq S\) ya que si no sucediera esto no tendría sentido preguntarnos si \(P(t,\vec{x},\vec{\alpha})\) es \(1\) para cada \(t\in\{u\in\bar{S}:u\leq x\}\). Además también para que la expresión \((\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\) este definida es preciso que \((\vec{x},\vec{\alpha})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). Sobre la variable \(x\) no hay ninguna restricción o sea que puede ser cualquier elemento de \(\omega\). Tenemos entonces que el dominio del predicado \[\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\] es \(\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). En forma análoga se define la forma de interpretar la expresión Booleana \[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\] Cabe destacar que \[\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]=\lnot\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;\lnot P(t,\vec{x},\vec{\alpha})\right]\] Analicemos un poco por separado el caso \(\bar{S}=\emptyset\). Nos queda la expresión \[(\forall t\in\emptyset)_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\] la cual para que este definida requiere que \((x,\vec{x},\vec{\alpha})\) este en \(\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) (ver (12) (d) de la notación lambda); y siempre es verdadera. O sea que \[\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\emptyset)_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]=C_{1}^{1+n,m}|_{\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\] Análogamente \[\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\emptyset)_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]=C_{0}^{1+n,m}|_{\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\] También podemos cuantificar sobre variable alfabética. Sea \(P:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times L\rightarrow\omega\) un predicado, con \(S_{1},...,S_{n}\subseteq\omega\) y \(L,L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacíos. Supongamos \(\bar{L}\subseteq L\). Entonces la expresión Booleana \[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\] depende de las variables \(x,\vec{x},\vec{\alpha}\) y esta definida cuando \((x,\vec{x},\vec{\alpha})\) pertenece a \(\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). Dejamos al lector analizar cuando vale 1 el predicado \[\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right]\] También dejamos al lector estudiar el comportamiento de la función \[\lambda x\vec{x}\vec{\alpha}\left[(\exists\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}P(\vec{x},\vec{\alpha},\alpha)\right]\] Cabe destacar que también \[\lambda x\vec{x}\vec{\alpha}\left[(\exists\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}P(\vec{x},\vec{\alpha},\alpha)\right]=\lnot\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\lnot P(\vec{x},\vec{\alpha},\alpha)\right]\] Dejamos al lector que analice el caso \(\bar{L}=\emptyset\) y también el caso \(n=m=0\) para ambos tipos de cuantificación (es decir cuando \(P:S\subseteq\omega\rightarrow\omega\) o \(P:L\subseteq\Sigma^{\ast}\rightarrow\omega\)).

Proof. (a) Sea \[\bar{P}=P|_{\bar{S}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\cup C_{1}^{1+n,m}|_{(\omega-\bar{S})\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\] Nótese que \(\bar{P}\) tiene dominio \(\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). Veamos que \(\bar{P}\) es \(\Sigma\)-p.r.. Ya que \(P\) es \(\Sigma\)-p.r. tenemos que \(D_{P}=S\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-p.r., lo cual por el Lema 4.16 nos dice que los conjuntos \(S_{1},...,S_{n}\), \(L_{1},...,L_{m}\) son \(\Sigma\)-p.r.. Si \(\bar{S}\neq\emptyset\), ya que es \(\Sigma\)-p.r. por hipótesis, el Lema 4.16 nos dice que \[\bar{S}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\] es \(\Sigma\)-p.r.. Si \(\bar{S}=\emptyset\) entonces \[\bar{S}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\] es también \(\Sigma\)-p.r. ya que es igual al conjunto vacío. O sea que el Lema 4.17 nos dice que \[P|_{\bar{S}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\] es \(\Sigma\)-p.r.. En forma similar, ya que \(\omega-\bar{S}\) es \(\Sigma\)-p.r. (Lema 4.15), obtenemos que \[C_{1}^{1+n,m}|_{(\omega-\bar{S})\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\] es \(\Sigma\)-p.r.. Pero entonces el Lema 4.19 nos dice que \(\bar{P}\) es \(\Sigma\)-p.r.. El Lema 4.21 nos dice que \(\lambda xy\vec{x}\vec{\alpha}\left[\prod\limits_{t=x}^{t=y}\bar{P}(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r.. Ya que \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}P(t,\vec{x},\vec{\alpha})\right] & =\lambda x\vec{x}\vec{\alpha}\left[\prod\limits_{t=0}^{t=x}\bar{P}(t,\vec{x},\vec{\alpha})\right]\\ & =\lambda xy\vec{x}\vec{\alpha}\left[\prod\limits_{t=x}^{t=y}\bar{P}(t,\vec{x},\vec{\alpha})\right]\circ\left[C_{0}^{1+n,m},p_{1}^{1+n,m},...,p_{1+n+m}^{1+n,m}\right] \end{aligned}\] tenemos que \(\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r..

Ya que \[\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]=\lnot\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;\lnot P(t,\vec{x},\vec{\alpha})\right]\] tenemos que \(\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r.

(b) Haremos solo el caso del cuantificador \(\forall\). Primero supongamos que \(\Sigma=\emptyset\). Ya que \(L,L_{1},...,L_{m}\) son no vacíos, deberá suceder que \(L=L_{1}=...=L_{m}=\{\varepsilon\}\). Ya que \(\bar{L}\subseteq L\), tenemos que \(\bar{L}=\emptyset\) o \(\bar{L}=\{\varepsilon\}\). Si \(\bar{L}=\emptyset\), entonces \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right] & =\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\emptyset)_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right]\\ & =C_{1}^{1+n,m}|_{\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}} \end{aligned}\] por lo cual es \(\Sigma\)-p.r. (por que?). Si \(\bar{L}=\{\varepsilon\}\), entonces \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right] & =\lambda x\vec{x}\vec{\alpha}\left[(P(\vec{x},\vec{\alpha},\varepsilon)\right]\\ & =P\circ\left[p_{2}^{1+n,m},...,p_{1+n+m}^{1+n,m},C_{\varepsilon}^{1+n,m}\right] \end{aligned}\] por lo cual es \(\Sigma\)-p.r.

Ahora supongamos \(\Sigma\) es no vacío. Sea \(\leq\) un orden total sobre \(\Sigma.\) Sea \(k\) el cardinal de \(\Sigma\). Primero nótese que

1. adhocprefix(*)adhocsufix \(\left\vert \alpha\right\vert \leq x\) sii \(\#^{\leq}(\alpha)\leq\sum_{\iota=1}^{i=x}k^{i}\), cualesquiera sean \(x\in\omega\) y \(\alpha\in\Sigma^{\ast}\)

(queda como ejercicio probar (*). Sean \[\begin{aligned} \#^{\leq}(L) & =\{\#^{\leq}(\alpha):\alpha\in L\}\\ \#^{\leq}(\bar{L}) & =\{\#^{\leq}(\alpha):\alpha\in\bar{L}\} \end{aligned}\] Nótese que \[\begin{aligned} \chi_{\#^{\leq}(L)}^{\omega} & =\chi_{L}^{\Sigma^{\ast}}\circ\ast^{\leq}\\ \chi_{\#^{\leq}(\bar{L})}^{\omega} & =\chi_{\bar{L}}^{\Sigma^{\ast}}\circ\ast^{\leq} \end{aligned}\] por lo cual \(\#^{\leq}(L)\) y \(\#^{\leq}(\bar{L})\) son \(\Sigma\)-p.r.. Sea \(H=\lambda t\vec{x}\vec{\alpha}\left[P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right].\) Nótese que \[D_{H}=\#^{\leq}(L)\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\] y \(H\) es \(\Sigma\)-p.r.. O sea que por (a) tenemos que \[\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq x}H(t,\vec{x},\vec{\alpha})\right]=\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq x}P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right]\] es \(\Sigma\)-p.r.. Llamemos \(Q\) al predicado \(\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq x}P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right]\). Tenemos que \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}P(\vec{x},\vec{\alpha},\alpha)\right] & =\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq\sum_{\iota=1}^{i=x}k^{i}}P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right]\text{ (por (*))}\\ & =Q\circ\left[\lambda x\vec{x}\vec{\alpha}\left[\sum\limits_{\iota=1}^{i=x}k^{i}\right],p_{1}^{1+n,m},...,p_{1+n+m}^{1+n,m}\right] \end{aligned}\] Pero \(\lambda x\vec{x}\vec{\alpha}\left[\sum\limits_{\iota=1}^{i=x}k^{i}\right]\) es \(\Sigma\)-p.r. (ejercicio), lo cual nos dice que \(\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right]\) lo es  

OBSERVACIÓN: La cuantificación no acotada no preserva la propiedad de ser \(\Sigma\)-p.r.. Como veremos mas adelante si elegimos bien al predicado \(\Sigma\)-p.r. \(P\), obtenemos que el predicado \(\lambda\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})\;P(t,\vec{x},\vec{\alpha})\right]\) no solo no es \(\Sigma\)-p.r. sino que tampoco es \(\Sigma\)-efectivamente computable (Teorema 4.15).

Algunos ejemplos en los cuales cuantificación acotada se aplica naturalmente son dados a continuación.

Proof. (a) Sea \(P=\lambda tx_{1}x_{2}\left[x_{2}=t.x_{1}\right]\). Es claro que \(P\) es \(\Sigma\)-p.r.. El lema anterior nos dice que \(\lambda xx_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x}\;P(t,x_{1},x_{2})\right]\) es \(\Sigma\)-p.r.. Nótese que \(x_{1}\) divide \(x_{2}\) si y solo si hay un \(t\leq x_{2}\) tal que \(x_{2}=t.x_{1}\). Esto nos dice que \[\lambda x_{1}x_{2}\left[x_{1}\text{ divide }x_{2}\right]=\lambda x_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x_{2}}\;P(t,x_{1},x_{2})\right]\] Pero \[\lambda x_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x_{2}}\;P(t,x_{1},x_{2})\right]=\lambda xx_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x}\;P(t,x_{1},x_{2})\right]\circ\left[p_{2}^{2,0},p_{1}^{2,0},p_{2}^{2,0}\right]\] por lo cual \(\lambda x_{1}x_{2}\left[x_{1}\text{ divide }x_{2}\right]\) es \(\Sigma\)-p.r.

(b) Ya que \[x\text{ es primo sii }x>1\wedge\left((\forall t\in\omega)_{t\leq x}\;t=1\vee t=x\vee\lnot(t\text{ divide }x)\right)\] podemos usar un argumento similar al de la prueba de (a).

(c) es dejado al lector.  

La idea fundamental subyacente en las aplicaciones anteriores es que en muchos casos de predicados obtenidos por cuantificación a partir de otros predicados, la variable cuantificada tiene una cota natural en términos de las otras variables y entonces componiendo adecuadamente se lo puede presentar como un caso de cuantificación acotada

4.2.4 Minimización y funciones \(\Sigma\)-recursivas

Tal como fue explicado anteriormente, para obtener la clase de las funciones \(\Sigma\)-recursivas debemos agregar un nuevo constructor a los ya definidos de composición y recursión primitiva, a saber el constructor de minimización. Tiene dos casos aunque solo usaremos el primero para la definición de función \(\Sigma\)-recursiva.

4.2.4.1 Minimización de variable numérica

Sea \(\Sigma\) un alfabeto finito y sea \(P:D_{P}\subseteq\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) un predicado. Dado \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\), cuando exista al menos un \(t\in\omega\) tal que \(P(t,\vec{x},\vec{\alpha})=1\), usaremos \(\min_{t}P(t,\vec{x},\vec{\alpha})\) para denotar al menor de tales \(t^{\prime}s\). Nótese que la expresión \(\min_{t}P(t,\vec{x},\vec{\alpha})\) esta definida solo para aquellas \((n+m)\)-uplas \((\vec{x},\vec{\alpha})\) para las cuales hay al menos un \(t\) tal que se da \(P(t,\vec{x},\vec{\alpha})=1\). Dicho de otra forma, la expresión \[\min_{t}P(t,\vec{x},\vec{\alpha})\] no estará definida en un \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) cuando para cada \(t\in\omega\) se dé que \((t,\vec{x},\vec{\alpha})\) no pertenece a \(D_{P}\) o \(P(t,\vec{x},\vec{\alpha})=0\). Otro detalle importante a tener en cuenta es que la expresión \(\min_{t}P(t,\vec{x},\vec{\alpha})\) no depende de la variable \(t\). Por ejemplo, las expresiones \(\min_{t}P(t,\vec{x},\vec{\alpha})\) y \(\min_{i}P(i,\vec{x},\vec{\alpha})\) son equivalentes en el sentido que están definidas en las mismas \((n+m)\)-uplas y cuando están definidas asumen el mismo valor.

Definamos \[M(P)=\lambda\vec{x}\vec{\alpha}\left[\min\nolimits_{t}P(t,\vec{x},\vec{\alpha})\right]\] Nótese que \[\begin{aligned} D_{M(P)} & =\left\{ (\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}:(\exists t\in\omega)\ P(t,\vec{x},\vec{\alpha})\right\} \\ M(P)(\vec{x},\vec{\alpha}) & =\min\nolimits_{t}P(t,\vec{x},\vec{\alpha})\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M(P)} \end{aligned}\] Diremos que \(M(P)\) se obtiene por minimización de variable numérica a partir de \(P\). Nótese que \(M(P)\) esta definido sólo cuando \(P\) es un predicado cuyo dominio sea un conjunto \(\Sigma\)-mixto de tipo \((n,m)\), con \(n\in\mathbf{N}\).

Veamos algunos ejemplos:

1. adhocprefix(E1)adhocsufix Tomemos \(P=\lambda tx_{1}[t^{2}=x_{1}]\). Tenemos que: \[\begin{aligned} D_{M(P)} & =\left\{ x_{1}\in\omega:(\exists t\in\omega)\ P(t,x_{1})\right\} \\ & =\left\{ x_{1}\in\omega:(\exists t\in\omega)\ t^{2}=x_{1}\right\} \end{aligned}\] Es decir el dominio de \(M(P)\) es el conjunto de los cuadrados. Además para cada \(x_{1}\in D_{M(P)}\) tenemos que \[M(P)(x_{1})=\min\nolimits_{t}P(t,x_{1})=\min\nolimits_{t}(t^{2}=x_{1})\] por lo cual \(M(P)(x)=\sqrt{x}\), para cada \(x\in D_{M(P)}\).

2. adhocprefix(E2)adhocsufix Cuando \(n=m=0\), tenemos que \(P:D_{P}\subseteq\omega\rightarrow\omega\). O sea que \[M(P)=\lambda\left[\min\nolimits_{t}P(t)\right]\] Esto nos dice que \(D_{M(P)}\subseteq\{\lozenge\}\). Además \(D_{M(P)}=\{\lozenge\}\) si y solo si \(P(t)=1\), para algún \(t\in D_{P}\), y en tal caso \(M(P)(\lozenge)=\min\nolimits_{t}P(t)\).

3. adhocprefix(E3)adhocsufix Recordemos que dados \(x_{1},x_{2}\in\omega\), con \(x_{2}\) no nulo, el cociente de dividir \(x_{1}\) por \(x_{2}\) se define como el máximo elemento del conjunto \(\{t\in\omega:t.x_{2}\leq x_{1}\}\). Sea \[\begin{array}[t]{rll} Q:\omega\times\mathbf{N} & \rightarrow & \omega\\ (x_{1},x_{2}) & \rightarrow & \text{cociente de dividir }x_{1}\text{ por }x_{2} \end{array}\] Sea \(P=\lambda tx_{1}x_{2}\left[x_{1}<t.x_{2}\right]\). Notar que \[\begin{aligned} D_{M(P)} & =\{(x_{1},x_{2})\in\omega^{2}:(\exists t\in\omega)\;P(t,x_{1},x_{2})=1\}\\ & =\{(x_{1},x_{2}):(\exists t\in\omega)\;x_{1}<t.x_{2}\}\\ & =\omega\times\mathbf{N} \end{aligned}\] Además si \((x_{1},x_{2})\in\omega\times\mathbf{N}\), es fácil de probar que \[\min\nolimits_{t}\ x_{1}<t.x_{2}=Q(x_{1},x_{2})+1\] por lo que \(M(P)=Suc\circ Q\). Si quisiéramos encontrar un predicado \(P^{\prime}\) tal que \(M(P^{\prime})=Q\), entonces podemos tomar \(P^{\prime}=\lambda tx_{1}x_{2}\left[x_{1}<(t+1).x_{2}\right]\) y con un poco de concentración nos daremos cuenta que \(M(P^{\prime})=Q\). Por supuesto esto tiene una cuota de artificialidad ya que no es tan obvio que \[Q(x_{1},x_{2})=\mathrm{\ menor\ }t\in\omega\mathrm{\ tal\ que\ }x_{1}<(t+1).x_{2}\] Hay una forma mas intuitiva de hacerlo y es diseñando \(P^{\prime}\) con la consigna de que para cada \((x_{1},x_{2})\in D_{Q}\) se dé que \[Q(x_{1},x_{2})=\mathrm{\ unico\ }t\in\omega\mathrm{\ tal\ que\ }P^{\prime}(t,x_{1},x_{2})\] Es decir diseñamos \(P^{\prime}\) de manera que \[P^{\prime}(t,x_{1},x_{2})=1\text{ si y solo si }t=Q(x_{1},x_{2})\] Por ejemplo se puede tomar \(P^{\prime}=\lambda tx_{1}x_{2}\left[x_{1}\geq t.x_{2}\text{ y }x_{1}<(t+1).x_{2}\right]\) que dicho sea de paso es justo la definición de cociente dada en la escuela primaria. Dejamos al lector corroborar que \(M(P^{\prime})=Q\), para este último \(P^{\prime}\), pero nótese que lo único que queda por chequear es que \(M(P^{\prime})\text{ y }Q\) tienen el mismo dominio ya que las reglas de asignación obviamente producen lo mismo.

Tal como lo vimos recién muchas veces que queramos diseñar un predicado \(P\) tal que \(M(P)\) sea igual a una función dada \(f\), será mas fácil diseñar \(P\) de manera que cumpla \[f(\vec{x},\vec{\alpha})=\mathrm{\ unico\ }t\in\omega\mathrm{\ tal\ que\ }P(t,\vec{x},\vec{\alpha})\] cada vez que \((\vec{x},\vec{\alpha})\in D_{f}\). Es decir un predicado \(P\) que caracterice al valor que toma \(f\), es decir el cual cumpla \[P(t,\vec{x},\vec{\alpha})=1\text{ si y solo si }t=f(\vec{x},\vec{\alpha})\] Luego por supuesto deberemos prestar atención a que \(D_{M(P)}=D_{f}\), es decir deberemos también lograr que para cada \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) se dé que \[(\vec{x},\vec{\alpha})\in D_{f}\text{ si y solo si }\exists t\in\omega\text{ }P(t,\vec{x},\vec{\alpha})\] Enunciamos esto en forma de regla.

1. adhocprefixREGLA U:adhocsufix Si tiene una función \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y busca un predicado \(P\) tal que \(f=M(P)\), intente diseñar \(P\) de manera que para cada \((\vec{x},\vec{\alpha})\in D_{f}\) se dé que \[f(\vec{x},\vec{\alpha})=\mathrm{\ unico\ }t\in\omega\mathrm{\ tal\ que\ }P(t,\vec{x},\vec{\alpha})\] Luego chequee que además para cada \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) se dé que \[(\vec{x},\vec{\alpha})\in D_{f}\text{ si y solo si }\exists t\in\omega\text{ }P(t,\vec{x},\vec{\alpha})\]

El siguiente lema nos muestra que en algunos casos el constructor de minimización preserva la computabilidad efectiva.

Proof. Sea \(\mathbb{P}_{P}\) un procedimiento efectivo que compute a \(P\) y sea \(\mathbb{P}_{D_{P}}\) un procedimiento efectivo que compute a \(\chi_{D_{P}}^{\omega\times\omega^{n}\times\Sigma^{\ast m}}\). Nótese que el siguiente procedimiento efectivo (con dato de entrada \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\)) computa la función \(M(P)\).

Etapa 1: Hacer \(T=0\) e ir a Etapa 2

Etapa 2: Correr \(\mathbb{P}_{D_{P}}\) con dato de entrada \((T,\vec{x},\vec{\alpha})\) y guardar la salida en \(A\). Ir a Etapa 3.

Etapa 3: Si \(A=1\) ir a Etapa 4, caso contrario ir a etapa 6.

Etapa 4: Correr \(\mathbb{P}_{P}\) con dato de entrada \((T,\vec{x},\vec{\alpha})\) y guardar la salida en \(B\). Ir a Etapa 5.

Etapa 5: Si \(B=1\), dar como salida \(T\) y terminar. Caso contrario ir a Etapa 6.

Etapa 6: Hacer \(T=T+1\) e ir a Etapa 2.  

Como corolario obtenemos que la minimización de predicados \(\Sigma\)-totales preserva la computabilidad efectiva:

Lamentablemente si quitamos la hipótesis en el lema anterior de que \(D_{P}\) sea \(\Sigma\)-efectivamente computable, el lema resulta falso. Mas adelante en la Proposición 4.18 veremos un contraejemplo basado en la Tesis de Church (esta tesis dice básicamente que el modelo Godeliano de la computabilidad efectiva es correcto). Por el momento el lector puede ejercitar su comprensión del tema convenciéndose de que aun teniendo un procedimiento efectivo que compute a un predicado \(P:D_{P}\subseteq\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), no es claro como construir un procedimiento efectivo que compute a \(M(P)\).

4.2.4.2 Definición de función \(\Sigma\)-recursiva

Con este nuevo constructor de funciones estamos en condiciones de definir la clase de las funciones \(\Sigma\)-recursivas. Definamos los conjuntos \(\mathrm{R}_{0}^{\Sigma}\subseteq\mathrm{R}_{1}^{\Sigma}\subseteq\mathrm{R}_{2}^{\Sigma}\subseteq...\subseteq\mathrm{R}^{\Sigma}\) de la siguiente manera

\[\begin{array}{lll} \mathrm{R}_{0}^{\Sigma} & = & \mathrm{PR}_{0}^{\Sigma}\\ \mathrm{R}_{k+1}^{\Sigma} & = & \mathrm{R}_{k}^{\Sigma}\cup\left\{ f\circ[f_{1},...,f_{r}]:f,f_{1},...,f_{r}\in\mathrm{R}_{k}^{\Sigma}\text{, }r\geq1\right\} \cup\\ & & \;\;\;\;\;\;\;\;\left\{ R(f,\mathcal{G}):R(f,\mathcal{G})\text{ está definida y }\{f\}\cup\{\mathcal{G}_{a}:a\in\Sigma\}\subseteq\mathrm{R}_{k}^{\Sigma}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ R(f,g):R(f,g)\text{ está definida y }f,g\in\mathrm{R}_{k}^{\Sigma}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ M(P):M(P)\text{ está definida, }P\text{ es }\Sigma\text{-total y }P\in\mathrm{R}_{k}^{\Sigma}\right\} \\ \mathrm{R}^{\Sigma} & = & \bigcup_{k\geq0}\mathrm{R}_{k}^{\Sigma} \end{array}\] Una función \(f\) es llamada \(\Sigma\)-recursiva si pertenece a \(\mathrm{R}^{\Sigma}\). Cabe destacar que aunque \(M(P)\) fue definido para predicados no necesariamente \(\Sigma\)-totales, en la definición de los conjuntos \(\mathrm{R}_{k}^{\Sigma}\), nos restringimos al caso en que \(P\) es \(\Sigma\)-total. Obviamente esto lo hacemos ya que como se explico antes el constructor de minimización no siempre preserva la computabilidad efectiva.

Nótese que \(\mathrm{PR}_{k}^{\Sigma}\subseteq\mathrm{R}_{k}^{\Sigma}\), para cada \(k\in\omega\), por lo cual \(\mathrm{PR}^{\Sigma}\subseteq\mathrm{R}^{\Sigma}\). Por supuesto el modelo de Godel seria incorrecto si no fuera cierto el siguiente resultado.

Proof. Lo probaremos usando la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Si \(F\in\mathrm{R}_{k}^{\Sigma}\), entonces \(F\) es \(\Sigma\)-efectivamente computable.

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Fácil.

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que \(F\in\mathrm{R}_{k+1}^{\Sigma}\) y que vale \(\mathrm{Enu}_{k}\). Veamos que entonces \(F\) es \(\Sigma\)-efectivamente computable. Ya que vale \(\mathrm{Enu}_{k}\), podemos suponer que \(F\in\mathrm{R}_{k+1}^{\Sigma}-\mathrm{R}_{k}^{\Sigma}\). Hay varios casos:

Caso \(F=f\circ[f_{1},...,f_{r}]\text{, con }f,f_{1},...,f_{r}\in\mathrm{R}_{k}^{\Sigma}\text{, }r\geq1\). Ya que \(\mathrm{Enu}_{k}\) es verdadero, las funciones \(f,f_{1},...,f_{r}\) son \(\Sigma\)-efectivamente computables. Entonces por Lema 4.2 tenemos que \(F\) es \(\Sigma\)-efectivamente computable.

Caso \(F=M(P)\), con \(P:\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) un predicado perteneciente a \(\mathrm{R}_{k}^{\Sigma}\). Ya que \(\mathrm{Enu}_{k}\) es verdadero, el predicado \(P\) es \(\Sigma\)-efectivamente computable. Ahora podemos aplicar el corolario anterior y concluir que \(F\) es \(\Sigma\)-efectivamente computable.

Los distintos casos en los que \(F\) se obtiene por recursión primitiva a partir de funciones de \(\mathrm{R}_{k}^{\Sigma}\) se siguen de \(\mathrm{Enu}_{k}\) y los respectivos Lemas 4.3, 4.4, 4.5 y 4.6.  

Daremos sin prueba el siguiente conceptualmente importante resultado.

Este resultado no es fácil de probar. Mas adelante (Proposición 4.15) veremos ejemplos naturales de funciones \(\Sigma\)-recursivas que no son \(\Sigma\)-p.r.. Otro ejemplo natural es la famosa función de Ackermann.

4.2.4.3 Lema de minimización acotada de variable numérica de predicados \(\Sigma\)-p.r.

Aunque no siempre que \(P\in\mathrm{R}^{\Sigma}\), tendremos que \(M(P)\in\mathrm{R}^{\Sigma}\) (Proposición 4.18), el siguiente lema nos garantiza que este es el caso cuando \(P\in\mathrm{PR}^{\Sigma}\) y además da condiciones para que \(M(P)\) sea \(\Sigma\)-p.r..

Proof. (a) Sea \(\bar{P}=P\cup C_{0}^{n+1,m}|_{(\omega^{n+1}\times\Sigma^{\ast m})-D_{P}}\). Note que \(\bar{P}\) es \(\Sigma\)-p.r. (por que?). Veremos a continuación que \(M(P)=M(\bar{P})\). Nótese que \[\{t\in\omega:P(t,\vec{x},\vec{\alpha})=1\}=\{t\in\omega:\bar{P}(t,\vec{x},\vec{\alpha})=1\}\] Esto claramente dice que \(D_{M(P)}=D_{M(\bar{P})}\) y que \(M(P)(\vec{x},\vec{\alpha})=M(\bar{P})(\vec{x},\vec{\alpha})\), para cada \((\vec{x},\vec{\alpha})\in D_{M(P)}\)., por lo cual \(M(P)=M(\bar{P})\).

Veremos entonces que \(M(\bar{P})\) es \(\Sigma\)-recursiva. Sea \(k\) tal que \(\bar{P}\in\mathrm{PR}_{k}^{\Sigma}\). Ya que \(\bar{P}\) es \(\Sigma\)-total y \(\bar{P}\in\mathrm{PR}_{k}^{\Sigma}\subseteq\mathrm{R}_{k}^{\Sigma}\), tenemos que \(M(\bar{P})\in\mathrm{R}_{k+1}^{\Sigma}\) y por lo tanto \(M(\bar{P})\in\mathrm{R}^{\Sigma}\).

(b) Ya que \(M(P)=M(\bar{P})\), basta con probar que \(M(\bar{P})\) es \(\Sigma\)-p.r. Primero veremos que \(D_{M(\bar{P})}\) es un conjunto \(\Sigma\)-p.r.. Nótese que \[\chi_{D_{M(\bar{P})}}^{\omega^{n}\times\Sigma^{\ast m}}=\lambda\vec{x}\vec{\alpha}\left[(\exists t\in\omega)_{t\leq f(\vec{x},\vec{\alpha})}\;\bar{P}(t,\vec{x},\vec{\alpha})\right]\] lo cual nos dice que \[\chi_{D_{M(\bar{P})}}^{\omega^{n}\times\Sigma^{\ast m}}=\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\omega)_{t\leq x}\;\bar{P}(t,\vec{x},\vec{\alpha})\right]\circ\left[f,p_{1}^{n,m},...,p_{n+m}^{n,m}\right]\] Pero el Lema 4.22 nos dice que \(\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\omega)_{t\leq x}\;\bar{P}(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r. por lo cual tenemos que \(\chi_{D_{M(\bar{P})}}^{\omega^{n}\times\Sigma^{\ast m}}\) lo es. Sea \[P_{1}=\lambda t\vec{x}\vec{\alpha}\left[\bar{P}(t,\vec{x},\vec{\alpha})\wedge(\forall j\in\omega)_{j\leq t}\;(j=t\vee\lnot\bar{P}(j,\vec{x},\vec{\alpha}))\right]\] Note que \(P_{1}\) es \(\Sigma\)-total. Dejamos al lector usando lemas anteriores probar que \(P_{1}\) es \(\Sigma\)-p.r. Además nótese que para \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) se tiene que \[P_{1}(t,\vec{x},\vec{\alpha})=1\text{ si y solo si }(\vec{x},\vec{\alpha})\in D_{M(\bar{P})}\text{ y }t=M(\bar{P})(\vec{x},\vec{\alpha})\] Esto nos dice que \[M(\bar{P})=\left(\lambda\vec{x}\vec{\alpha}\left[\prod_{t=0}^{f(\vec{x},\vec{\alpha})}t^{P_{1}(t,\vec{x},\vec{\alpha})}\right]\right)|_{D_{M(\bar{P})}}\] por lo cual para probar que \(M(\bar{P})\) es \(\Sigma\)-p.r. solo nos resta probar que \[F=\lambda\vec{x}\vec{\alpha}\left[\prod_{t=0}^{f(\vec{x},\vec{\alpha})}t^{P_{1}(t,\vec{x},\vec{\alpha})}\right]\] lo es. Pero \[F=\lambda xy\vec{x}\vec{\alpha}\left[\prod_{t=x}^{y}t^{P_{1}(t,\vec{x},\vec{\alpha})}\right]\circ\left[C_{0}^{n,m},f,p_{1}^{n,m},...,p_{n+m}^{n,m}\right]\] y por lo tanto el Lema 4.21 nos dice que \(F\) es \(\Sigma\)-p.r..  

OBSERVACIÓN: No siempre que \(P\) sea \(\Sigma\)-p.r. tendremos que \(M(P)\) lo será. Nótese que si \(M(P)\) fuera \(\Sigma\)-p.r., cada ves que \(P\) lo sea, entonces tendríamos que \(\mathrm{PR}^{\Sigma}=\mathrm{R}^{\Sigma}\) (justifique) lo cual contradiría la Proposición 4.6. Mas adelante (Corolario 4.5) veremos un ejemplo de un predicado \(P\) el cual es \(\Sigma\)-p.r. pero \(M(P)\) no es \(\Sigma\)-p.r.

El lema de minimización recién probado es muy útil como veremos en los siguientes dos lemas.

Proof. (a) Ya vimos anteriormente que \(Q=M(P^{\prime})\), donde \[P^{\prime}=\lambda tx_{1}x_{2}\left[x_{1}\geq t.x_{2}\text{ y }x_{1}<(t+1).x_{2}\right]\] Ya que \(P^{\prime}\) es \(\Sigma\)-p.r. y \[Q(x_{1},x_{2})\leq p_{1}^{2,0}(x_{1},x_{2}),\text{ para cada }(x_{1},x_{2})\in\omega\times\mathbf{N}\] (b) del Lema 4.25 implica que \(Q\in\mathrm{PR}^{\Sigma}\).

(b) Nótese que \[R=\lambda xy\left[x\dot{-}Q(x,y).y\right]\] y por lo tanto \(R\in\mathrm{PR}^{\Sigma}\).

(c) Para ver que \(pr\) es \(\Sigma\)-p.r., veremos que la extensión \(h:\omega\rightarrow\omega\), dada por \(h(0)=0\) y \(h(n)=pr(n)\), \(n\geq1\), es \(\Sigma\)-p.r.. Luego \(pr=h|_{\mathbf{N}}\) resultara \(\Sigma\)-p.r. por ser la restricción de una función \(\Sigma\)-p.r. a un conjunto \(\Sigma\)-p.r.. Primero note que \[\begin{aligned} h(0) & =0\\ h(t+1) & =\min\nolimits_{i}\left(i\text{ es primo}\wedge i>h(t)\right) \end{aligned}\] O sea que \(h=R\left(C_{0}^{0,0},g\right)\), donde \[\begin{array}[t]{rll} g:\omega\times\omega & \rightarrow & \omega\\ (A,t) & \rightarrow & \min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right) \end{array}\] Es decir que solo nos resta ver que \(g\) es \(\Sigma\)-p.r.. Pero nótese que \(g=M(P)\), donde \(P=\lambda iAt\left[i\text{ es primo}\wedge i>A\right]\). Claramente \(P\) es \(\Sigma\)-p.r. por lo cual para poder aplicar (b) del lema anterior debemos encontrar una función \(f:\omega\times\omega\rightarrow\omega\) tal que \[M(P)(A,t)\leq f(A,t)\text{, para cada }(A,t)\in\omega^{2}\] Es decir \(f\) deberá cumplir \[\min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right)\leq f(A,t)\text{, para cada }(A,t)\in\omega^{2}\] Definamos \(f=\lambda At[A!+1]\). Debemos probar entonces que \[\min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right)\leq A!+1\text{, para cada }A\in\omega\] Sea \(p\) un primo tal que \(p\) divide a \(A!+1\). Es fácil ver que entonces \(p>A\) ya que de lo contrario \(p\) dividiría a \(A!\) lo cual nos diría que \(p\) divide a \(1=A!+1-A!\), lo cual es absurdo. Pero esto claramente nos dice que \[\min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right)\leq p\leq A!+1\] O sea que (b) del Lema 4.25 implica que \(g=M(P)\) es \(\Sigma\)-p.r.  

Proof. Note que \(D_{\lambda xi\left[(x)_{i}\right]}=\mathbf{N}\times\mathbf{N}\). Sea \[P=\lambda txi\left[\lnot(pr(i)^{t+1}\ \text{divide }x)\right]\] Note que \(P\) es \(\Sigma\)-p.r. y que \(D_{P}=\omega\times\omega\times\mathbf{N}\). Dejamos al lector la prueba de que \(\lambda xi\left[(x)_{i}\right]=M(P)\). Ya que \((x)_{i}\leq x\), para todo \((x,i)\in\mathbf{N}\times\mathbf{N}\), (b) del Lema 4.25 implica que \(\lambda xi\left[(x)_{i}\right]\) es \(\Sigma\)-p.r..

Veamos que \(\lambda x\left[Lt(x)\right]\) es \(\Sigma\)-p.r.. Sea \[Q=\lambda tx\left[(\forall i\in\mathbf{N})_{i\leq x}\;(i\leq t\vee(x)_{i}=0)\right]\] Nótese que \(D_{Q}=\omega\times\mathbf{N}\) y que además por el Lema 4.22 tenemos que \(Q\) es \(\Sigma\)-p.r. (dejamos al lector explicar como se aplica tal lema en este caso). Además nótese que \(\lambda x\left[Lt(x)\right]=M(Q)\) y que \[Lt(x)\leq x,\text{para todo }x\in\mathbf{N}\] lo cual por (b) del Lema 4.25 nos dice que \(\lambda x\left[Lt(x)\right]\) es \(\Sigma\)-p.r..  

Para \(x_{1},...,x_{n}\in\omega\), con \(n\geq1\), escribiremos \(\left\langle x_{1},...,x_{n}\right\rangle\) en lugar de \(\left\langle x_{1},...,x_{n},0,...\right\rangle\).

Proof. Sea \(f_{n}=\lambda x_{1}...x_{n}\left[\left\langle x_{1},...,x_{n}\right\rangle \right]\). Claramente \(f_{1}\) es \(\Sigma\)-p.r.. Además note que para cada \(n\geq1\), tenemos \[f_{n+1}=\lambda x_{1}...x_{n+1}\left[\left(f_{n}(x_{1},...,x_{n})pr(n+1)^{x_{n+1}}\right)\right]\text{.}\] O sea que podemos aplicar un argumento inductivo.  

4.2.4.4 Minimización de variable alfabética

Supongamos que \(\Sigma\neq\emptyset\). Sea \(\leq\) un orden total sobre \(\Sigma\). Recordemos que \(\leq\) puede ser naturalmente extendido a un orden total sobre \(\Sigma^{\ast}\). Sea \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\times\Sigma^{\ast}\rightarrow\omega\) un predicado. Cuando \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) es tal que existe al menos un \(\alpha\in\Sigma^{\ast}\) tal que \(P(\vec{x},\vec{\alpha},\alpha)=1\), usaremos \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) para denotar al menor \(\alpha\in\Sigma^{\ast}\) tal que \(P(\vec{x},\vec{\alpha},\alpha)=1\). Nótese que la expresión \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) esta definida solo para aquellas \((n+m)\)-uplas \((\vec{x},\vec{\alpha})\) para las cuales hay al menos un \(\alpha\) tal que se da \(P(\vec{x},\vec{\alpha},\alpha)=1\). Dicho de otra forma, \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) no estará definida cuando para cada \(\alpha\in\Sigma^{\ast}\) se dé que \((\vec{x},\vec{\alpha},\alpha)\) no pertenece a \(D_{P}\) o \(P(\vec{x},\vec{\alpha},\alpha)=0\). Otro detalle importante a tener en cuenta es que la expresión \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) no depende de la variable \(\alpha\). Por ejemplo, las expresiones \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) y \(\min_{\beta}^{\leq}P(\vec{x},\vec{\alpha},\beta)\) son equivalentes en el sentido que están definidas en las mismas \((n+m)\)-uplas y cuando están definidas asumen el mismo valor.

Definamos \[\begin{array}{c} M^{\leq}(P)=\lambda\vec{x}\vec{\alpha}\left[\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\right]\end{array}\] Nótese que \[\begin{aligned} D_{M^{\leq}(P)} & =\left\{ (\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}:(\exists\alpha\in\Sigma^{\ast})\ P(\vec{x},\vec{\alpha},\alpha)\right\} \\ M^{\leq}(P)(\vec{x},\vec{\alpha}) & =\min\nolimits_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M^{\leq}(P)} \end{aligned}\] Diremos que \(M^{\leq}(P)\) es obtenida por minimización de variable alfabética a partir de \(P\).

Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Sea \(\Sigma=\{@,a,b,c,d,e\}\) y sea \(\leq\) un orden total sobre \(\Sigma\). Sea \(Dir=\{\alpha_{1}\in\Sigma^{\ast}:\left\vert \alpha_{1}\right\vert _{@}=1\}\) y definamos \(U:Dir\rightarrow\Sigma^{\ast}\) de la siguiente manera \[U(\alpha_{1})=\text{unico }\alpha\text{ tal que }\alpha@\text{ es tramo inicial de }\alpha_{1}\] Sea \[P=\lambda\alpha_{1}\alpha[\alpha_{1}\in Dir\text{ y }\alpha@\text{ es tramo inicial de }\alpha_{1}]\] Tenemos que \[\begin{aligned} D_{M^{\leq}(P)} & =\left\{ \alpha_{1}\in\Sigma^{\ast}:(\exists\alpha\in\Sigma^{\ast})\ P(\alpha_{1},\alpha)\right\} \\ & =\left\{ \alpha_{1}\in\Sigma^{\ast}:\alpha_{1}\in Dir\text{ y }(\exists\alpha\in\Sigma^{\ast})\ \alpha@\text{ es tramo inicial de }\alpha_{1}\right\} \\ & =Dir \end{aligned}\] y además es claro que \(M^{\leq}(P)(\alpha_{1})=U(\alpha_{1})\), para cada \(\alpha_{1}\in Dir\), por lo cual \(M^{\leq}(P)=U\). Intente explicar por que se utilizaron los nombres \(Dir\) y \(U\).

2. adhocprefix(E2)adhocsufix Cuando \(n=m=0\), tenemos que \(P:D_{P}\subseteq\Sigma^{\ast}\rightarrow\omega\). O sea que \[M^{\leq}(P)=\lambda[\min\nolimits_{\alpha}^{\leq}P(\alpha)]\] Esto nos dice que \(D_{M^{\leq}(P)}\subseteq\{\lozenge\}\). Además \(D_{M^{\leq}(P)}=\{\lozenge\}\) si y solo si \(P(\alpha)=1\), para algún \(\alpha\in D_{P}\), y en tal caso \(M^{\leq}(P)(\lozenge)=\min\nolimits_{\alpha}^{\leq}P(\alpha)\).

Como puede notarse para el caso alfabético también tenemos:

1. adhocprefixREGLA U:adhocsufix Si tiene una función \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) y busca un predicado \(P\) tal que \(f=M^{\leq}(P)\), intente diseñar \(P\) de manera que para cada \((\vec{x},\vec{\alpha})\in D_{f}\) se dé que \[f(\vec{x},\vec{\alpha})=\mathrm{\ unico\ }\alpha\in\Sigma^{\ast}\mathrm{\ tal\ que\ }P(\vec{x},\vec{\alpha},\alpha)\] Luego chequee que además para cada \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) se dé que \[(\vec{x},\vec{\alpha})\in D_{f}\text{ si y solo si }\exists\alpha\in\Sigma^{\ast}\text{ }P(\vec{x},\vec{\alpha},\alpha)\]

4.2.4.5 Lema de minimización acotada de variable alfabética de predicados \(\Sigma\)-p.r.

Proof. Sea \(Q=P\circ\left[p_{2}^{1+n,m},...,p_{1+n+m}^{1+n,m},\ast^{\leq}\circ p_{1}^{1+n,m}\right]\). Note que \[M^{\leq}(P)=\ast^{\leq}\circ M(Q)\] lo cual por (a) del Lema 4.25 implica que \(M^{\leq}(P)\) es \(\Sigma\)-recursiva.

Sea \(k\) el cardinal de \(\Sigma\). Ya que \[\left\vert \ast^{\leq}(M(Q)(\vec{x},\vec{\alpha}))\right\vert =\left\vert M^{\leq}(P)(\vec{x},\vec{\alpha})\right\vert \leq f(\vec{x},\vec{\alpha})\text{,}\] para todo \((\vec{x},\vec{\alpha})\in D_{M^{\leq}(P)}=D_{M(Q)}\), tenemos que \[M(Q)(\vec{x},\vec{\alpha})\leq\sum_{\iota=1}^{i=f(\vec{x},\vec{\alpha})}k^{i}\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M(Q)}\text{.}\] O sea que por (b) del Lema 4.25, \(M(Q)\) es \(\Sigma\)-p.r. y por lo tanto \(M^{\leq}(P)\) lo es.  

En el ejemplo de recién vimos que \(U=M(P)\), con \(P=\lambda\alpha_{1}\alpha[\alpha@\) es tramo inicial de \(\alpha_{1}]\) por lo cual, dado que \(P\) es \(\Sigma\)-p.r. y ademas \[\left\vert U(\alpha_{1})\right\vert \leq\left\vert \alpha_{1}\right\vert \text{, para cada }\alpha_{1}\in Dir\] el lema anterior nos dice que \(U\) es \(\Sigma\)-p.r.

4.2.5 Conjuntos \(\Sigma\)-recursivamente enumerables

Ya que la noción de función \(\Sigma\)-recursiva es el modelo matemático Godeliano del concepto de función \(\Sigma\)-efectivamente computable, nos podríamos preguntar entonces cual es el modelo matemático Godeliano del concepto de conjunto \(\Sigma\)-efectivamente enumerable. Si prestamos atención a la definición de conjunto \(\Sigma\)-efectivamente enumerable, notaremos que depende de la existencia de ciertas funciones \(\Sigma\)-efectivamente computables por lo cual la siguiente definición cae de maduro:

Diremos que un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-recursivamente enumerable cuando sea vacío o haya una función \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que \(I_{F}=S\) y \(F_{(i)}\) sea \(\Sigma\)-recursiva, para cada \(i\in\{1,...,n+m\}\).

Debería entonces quedar claro que si el concepto de función \(\Sigma\)-recursiva modeliza correctamente al concepto de función \(\Sigma\)-efectivamente computable, entonces el concepto de conjunto \(\Sigma\)-recursivamente enumerable recién definido modeliza correctamente al concepto de conjunto \(\Sigma\)-efectivamente enumerable. Sin embargo para probar algunos de los resultados básicos acerca de los conjuntos \(\Sigma\)-recursivamente enumerables, deberemos esperar a tener probada la equivalencia del paradigma Godeliano con el imperativo.

4.2.6 Conjuntos \(\Sigma\)-recursivos

La versión Godeliana del concepto de conjunto \(\Sigma\)-efectivamente computable es fácil de dar: un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-recursivo cuando la función \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) sea \(\Sigma\)-recursiva. Todo conjunto \(\Sigma\)-recursivo es \(\Sigma\)-recursivamente enumerable pero esto lo probaremos mas adelante junto con otros resultados básicos sobre conjuntos \(\Sigma\)-r.e., los cuales se prueban usando el paradigma imperativo. Mas adelante daremos un ejemplo natural de un conjunto que es \(\Sigma\)-r.e. pero el cual no es \(\Sigma\)-recursivo.

4.2.7 Algunos resultados básicos

Muchos resultados ya probados para el caso primitivo recursivo pueden ser probados usando básicamente las mismas pruebas e ideas para el caso recursivo. Por ejemplo las pruebas de los siguientes cuatro lemas son idénticas a las del caso primitivo recursivo

También se puede probar una versión del lema de división por casos para funciones \(\Sigma\)-recursivas con dominio \(\Sigma\)-recursivo, la cual generaliza el caso \(\Sigma\)-p.r.. La prueba es la misma que la del caso primitivo recursivo aunque al lema previo de existencia de extensiones lo probaremos en forma mas directa que para el caso primitivo recursivo. A saber:

Proof. Si \(f=\emptyset\), es fácil de probar y dejado al lector. Supongamos entonces \(f\) es no vacía. Sin perdida de generalidad podemos suponer que \((0,...,0,\varepsilon,...,\varepsilon)\in D_{f}\). Sea \[\begin{array}[t]{rll} F:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega^{n}\times\Sigma^{\ast m}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} (\vec{x},\vec{\alpha}) & & \text{si }(\vec{x},\vec{\alpha})\in D_{f}\\ (0,...,0,\varepsilon,...,\varepsilon) & & \text{caso contrario} \end{array}\right. \end{array}\] Ya que \[\begin{aligned} F_{(i)} & =\lambda\vec{x}\vec{\alpha}\left[x_{i}.\chi_{D_{f}}^{\omega^{n}\times\Sigma^{\ast m}}(\vec{x},\vec{\alpha})\right]\text{, para }i=1,...,n\\ F_{(i)} & =\lambda\vec{x}\vec{\alpha}\left[\alpha_{i}^{\chi_{D_{f}}^{\omega^{n}\times\Sigma^{\ast m}}(\vec{x},\vec{\alpha})}\right]\text{, para }i=n+1,...,n+m \end{aligned}\] tenemos que cada \(F_{(i)}\) es \(\Sigma\)-recursiva. Es claro que \(\bar{f}=f\circ F\) cumple que \(f=\bar{f}|_{D_{f}}\) por lo cual solo falta ver que \(\bar{f}\) es \(\Sigma\)-recursiva. Pero esto es obvio ya que \(F=\left[F_{(1)},...,F_{(n+m)}\right]\)  

Proof. Completamente análoga a la del caso primitivo recursivo.  

Proof. Supongamos \(\emptyset\neq S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Sea \((z_{1},...,z_{n},\gamma_{1},...,\gamma_{m})\in S\) fijo. Sea \(\leq\) un orden total sobre \(\Sigma\). Sea \(G:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) dada por \[G(x)=\left((x+1)_{1},...,(x+1)_{n},\ast^{\leq}((x+1)_{n+1}),...,\ast^{\leq}((x+1)_{n+m})\right)\] Es claro que cada \(G_{(i)}\) es \(\Sigma\)-recursiva y que \(\mathrm{Im}G=\omega^{n}\times\Sigma^{\ast m}\).

Para \(i=1,...,n\), definamos \(F_{i}:\omega\rightarrow\omega\) de la siguiente manera \[F_{i}(x)=\left\{ \begin{array}{ccl} G_{(i)}(x) & & \text{si }G(x)\in S\\ z_{i} & & \text{caso contrario} \end{array}\right.\] Para \(i=n+1,...,n+m\), definamos \(F_{i}:\omega\rightarrow\Sigma^{\ast}\) de la siguiente manera \[F_{i}(x)=\left\{ \begin{array}{ccl} G_{(i)}(x) & & \text{si }G(x)\in S\\ \gamma_{i} & & \text{caso contrario} \end{array}\right.\] Usando que \(S\) es \(\Sigma\)-recursivo podemos aplicar el lema anterior y ver que cada \(F_{i}\) es \(\Sigma\)-recursiva. Sea \(F=[F_{1},...,F_{n+m}]\). Nótese que \(F_{(i)}=F_{i}\) para cada \(i=1,...,n+m\). Esto nos dice que \(S\) es \(\Sigma\)-r.e. ya que \(\mathrm{Im}F=S\).  

Mas adelante (Lema 4.65) daremos un ejemplo natural de un conjunto que es \(\Sigma\)-r.e. pero el cual no es \(\Sigma\)-recursivo.

Debería quedar claro que si el modelo de Godel es correcto, entonces todos los resultados probados dentro del paradigma filosófico de Leibniz son ciertos una ves reenunciados de acuerdo al paradigma Godeliano. Tal como vimos arriba muchos de estos resultados se prueban en forma fácil en su versión recursiva. Sin embargo muchos otros requieren mas trabajo y es necesario utilizar algún paradigma mas constructivo (como el imperativo de Neumann o el de Turing) para poder probarlos en su versión recursiva. Por ejemplo consideremos el teorema siguiente dado en el contexto del paradigma filosófico de Leibniz:

Se tiene que la versión recursiva de (a)\(\Rightarrow\)(b) es probada sin problemas en el lema anterior pero para probar la versión recursiva de (b)\(\Rightarrow\)(a), nos será necesario utilizar el paradigma imperativo (Teorema 4.11). Lo mismo sucede con el lema de división por casos en su forma mas general (Lema 3.12) y con el teorema de caracterización de conjuntos \(\Sigma\)-efectivamente enumerables (Teorema 3.2), ambos cuando son enunciados en su versión recursiva no son fáciles de probar con las herramientas desarrolladas hasta ahora y nos será necesario usar el paradigma imperativo para representar a los objetos recursivos involucrados. Estas pruebas están en la Sección Resultados Básicos Presentados en Paradigma Recursivo donde se compilan todos los resultados básicos (expresados en paradigma recursivo) y se obtienen algunos resultados los cuales en esta instancia todavía no se pueden probar ya que para obtenerlos es necesario hacer uso de la formalización matemática de ambos paradigmas el funcional y el imperativo (por ejemplo la existencia de un conjunto que es \(\Sigma\)-r.e. pero el cual no es \(\Sigma\)-recursivo).

4.2.8 Recursión primitiva sobre valores anteriores

Dada una función \(h:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\), con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\), no vacíos, definamos \(h^{\downarrow}:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\) de la siguiente manera \[\begin{aligned} h^{\downarrow}(x,\vec{x},\vec{\alpha}) & =\left\langle h(0,\vec{x},\vec{\alpha}),h(1,\vec{x},\vec{\alpha}),...,h(x,\vec{x},\vec{\alpha})\right\rangle \\ & =\Pi_{i=0}^{x}pr(i+1)^{h(i,\vec{x},\vec{\alpha})} \end{aligned}\]

Proof. Supongamos \(f,g\) son \(\Sigma\)-p.r.. Primero veremos que \(h^{\downarrow}\) es \(\Sigma\)-r. (resp. \(\Sigma\)-p.r.). Nótese que para cada \((\vec{x},\vec{\alpha})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) tenemos que \[\begin{aligned} h^{\downarrow}(0,\vec{x},\vec{\alpha}) & =\left\langle h(0,\vec{x},\vec{\alpha})\right\rangle \\ & =\left\langle f(\vec{x},\vec{\alpha})\right\rangle \\ & =2^{f(\vec{x},\vec{\alpha})}\\ h^{\downarrow}(x+1,\vec{x},\vec{\alpha}) & =h^{\downarrow}(x,\vec{x},\vec{\alpha})pr(x+2)^{h(x+1,\vec{x},\vec{\alpha})}\\ & =h^{\downarrow}(x,\vec{x},\vec{\alpha})pr(x+2)^{g(h^{\downarrow}(x,\vec{x},\vec{\alpha}),x,\vec{x},\vec{\alpha})} \end{aligned}\] lo cual nos dice que \(h^{\downarrow}=R(f_{1},g_{1})\) donde \[\begin{aligned} f_{1} & =\lambda\vec{x}\vec{\alpha}\left[2^{f(\vec{x},\vec{\alpha})}\right]\\ g_{1} & =\lambda Ax\vec{x}\vec{\alpha}\left[Apr(x+2)^{g(A,x,\vec{x},\vec{\alpha})}\right] \end{aligned}\] O sea que \(h^{\downarrow}\) es \(\Sigma\)-r. (resp. \(\Sigma\)-p.r.) ya que \(f_{1}\) y \(g_{1}\) lo son. Finalmente nótese que \[h=\lambda ix[(x)_{i}]\circ\left[Suc\circ p_{1}^{1+n,m},h^{\downarrow}\right]\] lo cual nos dice que \(h\) es \(\Sigma\)-r. (resp. \(\Sigma\)-p.r.).  

4.2.9 Independencia del alfabeto

Probaremos que los conceptos de \(\Sigma\)-recursividad y \(\Sigma\)-recursividad primitiva son en realidad independientes del alfabeto \(\Sigma\), es decir que si \(f\) es una función la cual es \(\Sigma\)-mixta y \(\Gamma\)-mixta, entonces \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.) sii \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.).

Ya definimos para el caso de un alfabeto \(\Sigma\neq\emptyset\) y \(\leq\) un orden total sobre \(\Sigma\), las funciones \(\#^{\leq}\) y \(\ast^{\leq}\). Sea \(\Sigma=\emptyset\). Nótese que el conjunto \(\emptyset\) es un orden total sobre \(\Sigma\) (de hecho es el único orden total sobre \(\Sigma\)). Definamos \[\begin{array}{rll} \ast^{\emptyset}:\{0\} & \rightarrow & \{\varepsilon\}\\ 0 & \rightarrow & \varepsilon \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} \#^{\emptyset}:\{\varepsilon\} & \rightarrow & \{0\}\\ \varepsilon & \rightarrow & 0 \end{array}\] Ya que \(\Sigma^{\ast}=\{\varepsilon\}\), las funciones \(\#^{\emptyset}\) y \(\ast^{\emptyset}\) son biyecciones mutuamente inversas entre \(\{0\}\) y \(\Sigma^{\ast}\). Además nótese que estas funciones son \(\Sigma\)-p.r..

Proof. (a) Si \(\Sigma=\emptyset\), entonces es fácil ver que \(\ast^{\leq}\) y \(\#^{\leq}\) son \(\Gamma\)-p.r., y es dejado como ejercicio. Supongamos \(\Sigma=\{a_{1},...,a_{k}\}\) con \(k\geq1\) y \(\leq\) es dado por \(a_{1}<...<a_{k}\). Sea \(s_{e}^{\leq}:\Gamma^{\ast}\rightarrow\Gamma^{\ast}\) dada por \[\begin{aligned} s_{e}^{\leq}(\varepsilon) & =a_{1}\\ s_{e}^{\leq}(\alpha a_{i}) & =\alpha a_{i+1}\text{, si }i<k\\ s_{e}^{\leq}(\alpha a_{k}) & =s_{e}^{\leq}(\alpha)a_{1}\\ s_{e}^{\leq}(\alpha a) & =\varepsilon\text{, si }a\in\Gamma-\Sigma. \end{aligned}\] Note que \(s_{e}^{\leq}\) es \(\Gamma\)-p.r. y que \(s_{e}^{\leq}|_{\Sigma^{\ast}}=s^{\leq}\). Ya que \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(x+1) & =s^{\leq}(\ast^{\leq}(x)) \end{aligned}\] para cada \(x\in\omega\), tenemos que \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(x+1) & =s_{e}^{\leq}(\ast^{\leq}(x)) \end{aligned}\] Pero esto nos dice que \(\ast^{\leq}=R(C_{\varepsilon}^{0,0},g)\) donde \[\begin{array}{lll} g:\omega\times\Gamma^{\ast} & \rightarrow & \Gamma^{\ast}\\ \;\;\;\;\;(x,\alpha) & \rightarrow & s_{e}^{\leq}(\alpha) \end{array}\] Pero es claro que \(g\) es \(\Gamma\)-p.r. por lo cual \(\ast^{\leq}\) es \(\Gamma\)-p.r..

Para ver que \(\#^{\leq}:\Sigma^{\ast}\rightarrow\omega\) es \(\Gamma\)-p.r., sea \(\#_{e}^{\leq}:\Gamma^{\ast}\rightarrow\omega\) dada por \[\begin{aligned} \#_{e}^{\leq}(\varepsilon) & =0\\ \#_{e}^{\leq}(\alpha a_{i}) & =\#_{e}^{\leq}(\alpha).k+i\\ \#_{e}^{\leq}(\alpha a) & =0\text{, si }a\in\Gamma-\Sigma. \end{aligned}\] Ya que \(\#_{e}^{\leq}\) es \(\Gamma\)-p.r., eso es \(\#^{\leq}=\#_{e}^{\leq}|_{\Sigma^{\ast}}\).

(b) El caso \(\Sigma=\emptyset\) es fácil y queda como ejercicio. Supongamos entonces \(\Sigma\) es no vacío. Sea \(n\) el cardinal de \(\Gamma.\) Ya que \[\begin{aligned} \#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\varepsilon) & =0\\ \#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\alpha a) & =\#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\alpha).n+\#^{\leq^{\prime}}(a)\text{, para cada }a\in\Sigma \end{aligned}\] la función \(\#^{\leq^{\prime}}|_{\Sigma^{\ast}}\) es \(\Sigma\)-p.r.. O sea que el predicado \(P=\lambda x\alpha\left[\#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\alpha)=x\right]\) es \(\Sigma\)-p.r.. Sea \(\leq\) un orden total sobre \(\Sigma\). Note que \(\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}=M^{\leq}(P)\), lo cual ya que \[\left\vert \ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}(x)\right\vert \leq x\] nos dice que \(\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\) es \(\Sigma\)-p.r. (Lema 4.29).  

Proof. Veamos que \(\mathrm{R}^{\emptyset}\subseteq\mathrm{R}^{\Sigma}\). Lo probaremos usando la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix \(\mathrm{R}_{k}^{\emptyset}\subseteq\mathrm{R}^{\Sigma}\)

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Fácil.

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que \(F\in\mathrm{R}_{k+1}^{\emptyset}\) y que vale \(\mathrm{Enu}_{k}\). Probaremos que \(F\in\mathrm{R}^{\Sigma}\). Hay varios casos:

Caso \(F\in\mathrm{R}_{k}^{\emptyset}\). Sigue directamente de \(\mathrm{Enu}_{k}\) que \(F\in\mathrm{R}^{\Sigma}\).

Caso \(F=R(f,\mathcal{G})\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\emptyset^{\ast}\\ \mathcal{G}_{a} & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast}\times\emptyset^{\ast}\rightarrow\emptyset^{\ast}\text{, para cada }a\in\emptyset \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacío. Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f\in\mathrm{R}^{\Sigma}\). Nótese que \(\mathcal{G}=\emptyset\), lo cual nos dice que por definición \[\begin{array}{rll} R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast} & \rightarrow & \emptyset^{\ast}\\ (\vec{x},\varepsilon,...,\varepsilon,\varepsilon) & \rightarrow & f(\vec{x},\varepsilon,...,\varepsilon) \end{array}\] Es claro que \(\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}\) es un conjunto \(\Sigma\)-p.r. por lo cual las funciones \(p_{i}^{n,m+1}|_{\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}}\) son \(\Sigma\)-p.r. (aquí las \(p_{i}^{n,m+1}\) son respecto de \(\Sigma\)). Ya que \[R(f,\mathcal{G})=f\circ\left[p_{1}^{n,m+1}|_{\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}},...,p_{n+m}^{n,m+1}|_{\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}}\right]\] tenemos que \(F\in\mathrm{R}^{\Sigma}\).

Caso \(F=R(f,g)\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\emptyset^{\ast}\\ g & :\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast}\rightarrow\emptyset^{\ast} \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacío. Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f,g\in\mathrm{R}^{\Sigma}\). Nótese que respecto de \(\Sigma\), la función \(R(f,g)\) no esta definida ya que por la forma de \(f\), el dominio de \(g\) debería ser \(\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\Sigma^{\ast}\). Sea \[\tilde{g}=g\circ\left[p_{1}^{1+n,m+1},...,p_{1+n+m}^{1+n,m+1},C_{\varepsilon}^{1+n,m+1}\right]\] (aquí las \(p_{i}^{1+n,m+1}\) y \(C_{\varepsilon}^{1+n,m+1}\) son respecto de \(\Sigma\)). Nótese que \(D_{\tilde{g}}=\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\Sigma^{\ast}\) y \(\tilde{g}\) es \(\Sigma\)-recursiva. Además es fácil ver que \(F=Rf,\tilde{g})\) (respecto del alfabeto \(\Sigma\)) por lo cual \(F\) es \(\Sigma\)-recursiva.

Caso \(F=M(P)\), con \(P:\omega\times\omega^{n}\times\emptyset^{\ast m}\rightarrow\omega\), un predicado en \(\mathrm{R}_{k}^{\emptyset}\). Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(P\in\mathrm{R}^{\Sigma}\). Sea \[\bar{P}=P\circ\left[p_{1}^{1+n,m},...,p_{1+n}^{1+n,m},C_{\varepsilon}^{1+n,m},...,C_{\varepsilon}^{1+n,m}\right]\] Nótese que \(\bar{P}\) es \(\Sigma\)-total y \(\Sigma\)-recursivo y además extiende a \(P\). Sea \[\tilde{P}=\lambda xy[x.y]\circ\left[\bar{P},\chi_{\omega\times\omega^{n}\times\emptyset^{\ast m}}^{\omega\times\omega^{n}\times\Sigma^{\ast m}}\right]\] También \(\tilde{P}\) es \(\Sigma\)-total y \(\Sigma\)-recursivo y extiende a \(P\) pero además fuera del dominio de \(P\) vale \(0\). Esto nos dice que \(M(\tilde{P})=M(P)\) por lo cual \(F\) es \(\Sigma\)-recursiva ya que \(M(\tilde{P})\) lo es.

Los otros casos de recursión primitiva son parecidos a los hechos y el caso de la composición es trivial.

La prueba de que \(\mathrm{PR}^{\emptyset}\subseteq\mathrm{PR}^{\Sigma}\) es muy similar. Se dejan los detalles como ejercicio para el lector  

Sea \(\Sigma\) un alfabeto finito (puede ser vacío) y sea \(\leq\) un orden total sobre \(\Sigma\). Para \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), definamos \[f^{\#^{\leq}}=f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq}\circ p_{n+1}^{n+m,0},...,\ast^{\leq}\circ p_{n+m}^{n+m,0}\right]\] Similarmente, para \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\), definamos \[f^{\#^{\leq}}=\#^{\leq}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq}\circ p_{n+1}^{n+m,0},...,\ast^{\leq}\circ p_{n+m}^{n+m,0}\right]\]

Proof. (2)\(\Rightarrow\)(1). Supongamos \(h:D_{h}\subseteq\omega^{n}\times\Gamma^{\ast m}\rightarrow\Gamma^{\ast}\) es tal que \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Dejamos al lector chequear que \[h=\ast^{\leq}\circ h^{\#^{\leq}}\circ\left[p_{1}^{n,m},...,p_{n}^{n,m},\#^{\leq}\circ p_{n+1}^{n,m},...,\#^{\leq}\circ p_{n+m}^{n,m}\right]\] (aquí las \(p_{i}^{n,m}\) son respecto de \(\Gamma\)). Por el lema anterior tenemos que \(h^{\#^{\leq}}\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Ya que (aun cuando \(\Gamma=\emptyset\)) tenemos que las funciones \(\ast^{\leq}\) y \(\#^{\leq}\) son \(\Gamma\)-p.r., tenemos que \(h\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.) ya que es composición de funciones \(\Gamma\)-recursivas (resp. \(\Gamma\)-p.r.).

(1)\(\Rightarrow\)(2). El caso \(\Gamma=\emptyset\) es trivial ya que \(h^{\#^{\leq}}\) se define como composición de funciones \(\emptyset\)-recursivas (resp. \(\emptyset\)-p.r.). Supongamos entonces que \(\Gamma=\{a_{1},...,a_{r}\}\), con \(a_{1}<a_{2}<...<a_{r}\) y \(r>0\). Lo probaremos usando la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Si \(h\in\mathrm{R}_{k}^{\Gamma}\) (resp. \(h\in\mathrm{PR}_{k}^{\Gamma}\)), entonces \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.).

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Facil.

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\) y sea \(h\in\mathrm{R}_{k+1}^{\Gamma}\) (resp. \(h\in\mathrm{PR}_{k+1}^{\Gamma}\)). Hay varios casos

Caso 1. Supongamos \(h=f\circ[f_{1},...,f_{n}]\), con \(f,f_{1},...,f_{n}\in\mathrm{R}_{k}^{\Gamma}\) (resp. \(f,f_{1},...,f_{n}\in\mathrm{PR}_{k}^{\Gamma}\)). Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f^{\#^{\leq}},f_{1}^{\#^{\leq}},...,f_{n}^{\#^{\leq}}\) son \(\emptyset\)-recursivas (resp. \(\emptyset\)-p.r.). Ya que \(h^{\#^{\leq}}=f^{\#^{\leq}}\circ\left[f_{1}^{\#^{\leq}},...,f_{n}^{\#^{\leq}}\right]\), tenemos que \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.).

Caso 2. Supongamos \(h=M(P)\), con \(P:\omega\times\omega^{n}\times\Gamma^{\ast m}\rightarrow\omega\), un predicado en \(\mathrm{R}_{k}^{\Gamma}\). Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(P^{\#^{\leq}}\) es \(\emptyset\)-recursiva. Ya que \(h^{\#^{\leq}}=M(P^{\#^{\leq}})\) y \(D_{P^{\#^{\leq}}}=\omega^{1+n+m}\), tenemos que \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva.

Caso 3. Supongamos \(h=R(f,\mathcal{G})\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Gamma^{\ast}\\ \mathcal{G}_{a} & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Gamma^{\ast}\times\Gamma^{\ast}\rightarrow\Gamma^{\ast}\text{, }a\in\Gamma \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\Gamma}\) (resp. \(\mathrm{PR}_{k}^{\Gamma}\)) y \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\), no vacíos. Nótese que \[\begin{aligned} f^{\#^{\leq}} & :S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\rightarrow\omega\\ \mathcal{G}_{a}^{\#^{\leq}} & :S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\times\omega\rightarrow\omega\text{, }a\in\Gamma\\ h^{\#^{\leq}} & :S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\rightarrow\omega \end{aligned}\] Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f^{\#^{\leq}}\) y cada \(\mathcal{G}_{a}^{\#^{\leq}}\) son \(\emptyset\)-recursivas (resp. \(\emptyset\)-p.r.). Sea \[\begin{array}{rll} i_{0}:\omega & \rightarrow & \omega\\ x & \rightarrow & \left\{ \begin{array}{lll} r & & \text{si }r\text{ divide }x\\ R(x,r) & & \text{caso contrario} \end{array}\right. \end{array}\] y sea \[B=\lambda x\left[Q(x\dot{-}i_{0}(x),r)\right]\] (\(R\) y \(Q\) son definidas en el Lema 4.26). Note que \(i_{0}\) y \(B\) son \(\emptyset\)-p.r. y que \[\ast^{\leq}(x)=\ast^{\leq}(B(x))a_{i_{0}(x)}\text{, para }x\geq1\] (ejercicio). También tenemos para cada \((\vec{x},\vec{y},t)\in S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\) se da \[\begin{aligned} h^{\#^{\leq}}(\vec{x},\vec{y},t+1) & =\#^{\leq}(h(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(t+1)))\\ & =\#^{\leq}(h(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1))a_{i_{0}(t+1)}))\\ & =\#^{\leq}\left(\mathcal{G}_{a_{i_{0}(t+1)}}(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1)),h(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1)))\right)\\ & =\#^{\leq}\left(\mathcal{G}_{a_{i_{0}(t+1)}}(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1)),\ast^{\leq}(h^{\#^{\leq}}(\vec{x},\vec{y},B(t+1))))\right)\\ & =\mathcal{G}_{a_{i_{0}(t+1)}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),h^{\#^{\leq}}(\vec{x},\vec{y},B(t+1))) \end{aligned}\] y ya que \(B(t+1)<t+1\), tenemos que

1. adhocprefix(**)adhocsufix \(h^{\#^{\leq}}(\vec{x},\vec{y},t+1)=\mathcal{G}_{a_{i_{0}(t+1)}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),\left(\left\langle h^{\#^{\leq}}(\vec{x},\vec{y},0),...,h^{\#^{\leq}}(\vec{x},\vec{y},t)\right\rangle \right)_{B(t+1)+1})\), para cada \((\vec{x},\vec{y},t)\in S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\)

A continuación aplicaremos la idea del Lema 4.37. Será mas claro así ya que para aplicarlo directamente deberíamos cambiar el orden de los parámetros de las funciones \(h^{\#^{\leq}}\), \(\mathcal{G}_{a_{i}}^{\#^{\leq}}\) componiéndolas adecuadamente y sería muy engorroso notacionalmente.

Definamos \[H=\lambda t\vec{x}\vec{y}\left[\left\langle h^{\#^{\leq}}(\vec{x},\vec{y},0),...,h^{\#^{\leq}}(\vec{x},\vec{y},t)\right\rangle \right]\] Notar que \[D_{H}=\omega\times S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\] Tenemos que \[\begin{aligned} H(0,\vec{x},\vec{y}) & =\left\langle h^{\#^{\leq}}(\vec{x},\vec{y},0)\right\rangle =\left\langle f^{\#^{\leq}}(\vec{x},\vec{y})\right\rangle =2^{f^{\#^{\leq}}(\vec{x},\vec{y})}\\ H(t+1,\vec{x},\vec{y}) & =\left(H(t,\vec{x},\vec{y}).pr(t+2)^{h^{\#^{\leq}}(\vec{x},\vec{y},t+1)}\right)\\ & =\left(H(t,\vec{x},\vec{y}).pr(t+2)^{\mathcal{G}_{a_{i_{0}(t+1)}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(H(t,\vec{x},\vec{y}))_{B(t+1)+1})}\right)\text{ (por (**))} \end{aligned}\] para cada \((t,\vec{x},\vec{y})\in\omega\times S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\). O sea que si definimos \[g:\omega\times\omega\times S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\rightarrow\omega\] por \[g(A,t,\vec{x},\vec{y})=\left\{ \begin{array}{clc} \left(A.pr(t+2)^{\mathcal{G}_{a_{1}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(A)_{B(t+1)+1})}\right) & \text{si} & i_{0}(t+1)=1\\ \vdots & & \vdots\\ \left(A.pr(t+2)^{\mathcal{G}_{a_{r}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(A)_{B(t+1)+1})}\right) & \text{si} & i_{0}(t+1)=r \end{array}\right.\] tenemos que \(H=R(\lambda x\left[2^{x}\right]\circ f^{\#^{\leq}},g)\). Note que \(g\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.), ya que \[g=\lambda At\vec{x}\vec{y}\left[f_{1}(A,t,\vec{x},\vec{y})P_{1}(A,t,\vec{x},\vec{y})+...+f_{r}(A,t,\vec{x},\vec{y})P_{r}(A,t,\vec{x},\vec{y})\right]\text{,}\] con \[\begin{aligned} f_{i} & =\lambda At\vec{x}\vec{y}\left[\left(A.pr(t+2)^{\mathcal{G}_{a_{i}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(A)_{B(t+1)})}\right)\right]\\ P_{i} & =\lambda At\vec{x}\vec{y}\left[i_{0}(t+1)=i\right] \end{aligned}\] O sea que \(H\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.) y por lo tanto lo es \[h^{\#^{\leq}}=\lambda\vec{x}\vec{y}t\left[(H(t,\vec{x},\vec{y}))_{t+1}\right]\] Los otros casos en los cuales \(h\) es obtenida por recursión primitiva son similares.  

Ahora podemos probar el anunciado resultado de independencia.

Proof. (a) Ya que \(f\) es \((\Sigma\cap\Gamma)\)-mixta, podemos suponer sin perdida de generalidad que \(\Sigma\subseteq\Gamma\) (por que?). Sea \(\leq\) un orden total sobre \(\Sigma\) y sea \(\leq^{\prime}\) un orden total sobre \(\Gamma\). Primero supongamos que \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.). Probaremos que \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Ya que \(f\) es \(\Sigma\) mixta, tenemos que \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), con \(O\in\{\omega,\Sigma^{\ast}\}\). Haremos el caso \(O=\Sigma^{\ast}\). Ya que las funciones \(\#^{\leq^{\prime}}|_{\Sigma^{\ast}}\) y \(\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\) son \(\Sigma\)-p.r. (Lema 4.38) y ademas \[\begin{aligned} f^{\#^{\leq^{\prime}}} & =\#^{\leq^{\prime}}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq^{\prime}}\circ p_{n+1}^{n+m,0},...,\ast^{\leq^{\prime}}\circ p_{n+m}^{n+m,0}\right]\\ & =\#^{\leq^{\prime}}|_{\Sigma^{\ast}}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\circ p_{n+1}^{n+m,0},...,\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\circ p_{n+m}^{n+m,0}\right] \end{aligned}\] (justifique) tenemos que \(f^{\#^{\leq^{\prime}}}\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.). Por el lema anterior tenemos que \(\left(f^{\#^{\leq^{\prime}}}\right)^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.), pero nótese que \(\left(f^{\#^{\leq^{\prime}}}\right)^{\#^{\leq}}=f^{\#^{\leq^{\prime}}}\) ya que \(f^{\#^{\leq^{\prime}}}\) es de tipo \((n+m,0,\#)\), por lo cual tenemos que \(f^{\#^{\leq^{\prime}}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Pero esto por el lema anterior nos dice que \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.).

Supongamos ahora que \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Probaremos que \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.). Ya que \(\#^{\leq}\) y \(\ast^{\leq}\) son \(\Gamma\)-p.r. (Lema 4.38), la función \[f^{\#^{\leq}}=\#^{\leq}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq}\circ p_{n+1}^{n+m,0},...,\ast^{\leq}\circ p_{n+m}^{n+m,0}\right]\] es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Por el lema anterior \(\left(f^{\#^{\leq}}\right)^{\#^{\leq^{\prime}}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Pero nótese que \(\left(f^{\#^{\leq}}\right)^{\#^{\leq^{\prime}}}=f^{\#^{\leq}}\) ya que \(f^{\#^{\leq}}\) es de tipo \((n+m,0,\#)\), por lo cual \(f^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Esto por el lema anterior nos dice que \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.).

(b) Supongamos \(S\) es \(\Sigma\)-mixto y \(\Gamma\)-mixto. Ya que \(S\) es \((\Sigma\cap\Gamma)\)-mixto, podemos suponer sin perdida de generalidad que \(\Sigma\subseteq\Gamma\). Que \[S\text{ es }\Sigma\text{-r.e. sii }S\text{ es }\Gamma\text{-r.e.}\] sigue directo de (a). Supongamos ahora que \(S\) es \(\Sigma\)-recursivo. Veremos que \(S\) es \(\Gamma\)-recursivo. Supongamos \(S\) es de tipo \((n,m)\) es decir \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Por definición tenemos que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-recursiva. Pero \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es también \(\Gamma\)-mixta, por lo cual (a) nos dice que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Gamma\)-recursiva. Además es claro que el conjunto \((\omega^{n}\times\Gamma^{\ast m})-(\omega^{n}\times\Sigma^{\ast m})\) es \(\Gamma\)-recursivo. Ya que \[\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}=\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\cup C_{0}^{n,m}|_{(\omega^{n}\times\Gamma^{\ast m})-(\omega^{n}\times\Sigma^{\ast m})}\] los Lemas 4.33 y 4.35 nos dicen que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}\) es \(\Gamma\)-recursiva (aquí \(C_{0}^{n,m}\) es respecto del alfabeto \(\Gamma\)).

Supongamos ahora que \(S\) es \(\Gamma\)-recursivo. Veremos que \(S\) es \(\Sigma\)-recursivo. Por definición tenemos que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}\) es \(\Gamma\)-recursiva. Ya que \(\omega^{n}\times\Sigma^{\ast m}\) es \(\Gamma\)-recursivo, tenemos que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}|_{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Gamma\)-recursiva. Por (a) tenemos que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}|_{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-recursiva. Pero \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}=\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}|_{\omega^{n}\times\Sigma^{\ast m}}\) por lo cual \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-recursiva, obteniendo que \(S\) es \(\Sigma\)-recursivo.

El caso primitivo recursivo es análogo y dejado al lector.  

4.2.10 Funciones recursivas clásicas

Aquí desarrollaremos el concepto clásico numérico de función recursiva y lo relacionaremos con el nuestro de función \(\Sigma\)-recursiva. Esto nos será útil para la prueba del Teorema de Incompletitud.

Una función \(f\) es llamada numérica si hay un \(n\in\omega\) tal que \(f:D_{f}\subseteq\omega^{n}\rightarrow\omega\). Nótese que cuando \(f\) es no vacía, \(n\) esta determinado por \(f\). Una función numérica \(f\) sera llamada total cuando \(D_{f}=\omega^{n}\), para algún \(n\in\omega\). Sea \(C_{0}^{0}:\{\lozenge\}\rightarrow\omega\) dada por \(C_{0}^{0}(\lozenge)=0\). Para \(1\leq j\leq n\) sea \(p_{j}^{n}:\omega^{n}\rightarrow\omega\) dada por \(p_{j}^{n}(x_{1},...,x_{n})=x_{j}\). Nótese que cuando tenemos un alfabeto fijado, \(C_{0}^{0}=C_{0}^{0,0}\) y \(p_{j}^{n}=p_{j}^{n,0}\).

Definamos los conjuntos \(\mathrm{R}_{0}^{\#}\subseteq\mathrm{R}_{1}^{\#}\subseteq\mathrm{R}_{2}^{\#}\subseteq...\subseteq\mathrm{R}^{\#}\) de la siguiente manera \[\begin{array}{lll} \mathrm{R}_{0}^{\#} & = & \left\{ Suc,Pred,C_{0}^{0}\right\} \cup\left\{ p_{j}^{n}:1\leq j\leq n\right\} \\ \mathrm{R}_{k+1}^{\#} & = & \mathrm{R}_{k}^{\#}\cup\left\{ f\circ[f_{1},...,f_{r}]:f,f_{1},...,f_{r}\in\mathrm{R}_{k}^{\#}\text{, }r\geq1\right\} \cup\\ & & \;\;\;\;\;\;\;\;\left\{ R(f,g):R(f,g)\text{ está definida y }f,g\in\mathrm{R}_{k}^{\#}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ M(P):M(P)\text{ está definida, }P\text{ es un predicado total y }P\in\mathrm{R}_{k}^{\#}\right\} \\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ \mathrm{R}^{\#} & = & \bigcup_{k\geq0}\mathrm{R}_{k}^{\#} \end{array}\] Una función será llamada recursiva clásica si y solo si pertenece a \(\mathrm{R}^{\#}\).

Proof. (1) Notar que \(C_{0}^{1}=R(C_{0}^{0},p_{1}^{2})\in\mathrm{R}_{1}^{\#}\).

(2) Notar que \(\lambda x[1\dot{-}x]=R(Suc\circ C_{0}^{0},C_{0}^{1}\circ p_{1}^{2})\in\mathrm{R}_{3}^{\#}\).

(3) Usaremos la Regla de Inducción desde 1. Para cada \(n\in\mathbf{N}\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{n}\):adhocsufix \(\lambda x_{1}...x_{n}[x_{1}+...+x_{n}]\in\mathrm{R}^{\#}\).

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(1\).

Prueba de que \(\mathrm{Enu}_{1}\) es verdadero. Notar que para \(n=1\) la función \(\lambda x_{1}...x_{n}[x_{1}+...+x_{n}]\) es igual a \(\lambda x_{1}[x_{1}]\) que es justamente la función \(p_{1}^{1}\) la cual claramente está en \(\mathrm{R}^{\#}\).

Prueba de que si \(\mathrm{Enu}_{n}\) es verdadero entonces \(\mathrm{Enu}_{n+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{n}\), es decir \(\lambda x_{1}...x_{n}[x_{1}+...+x_{n}]\in\mathrm{R}^{\#}\). O sea que \(\lambda x_{1}...x_{n}[x_{1}+...+x_{n}]\in\mathrm{R}_{K}^{\#}\), para algún \(K\). Notar que \[\lambda x_{1}...x_{n+1}[x_{1}+...+x_{n+1}]=\lambda x_{1}x_{2}\left[x_{1}+x_{2}\right]\circ[F,p_{n+1}^{n+1}]\] donde \[F=\lambda x_{1}...x_{n}[x_{1}+...+x_{n}]\circ[p_{1}^{n+1},...,p_{n}^{n+1}]\] Notar que \(F\in\mathrm{R}_{K+1}^{\#}\). Pero \(\lambda x_{1}x_{2}\left[x_{1}+x_{2}\right]=R\left(p_{1}^{1},Suc\circ p_{1}^{3}\right)\in\mathrm{R}_{2}^{\#}\). O sea que entonces \(\lambda x_{1}...x_{n+1}[x_{1}+...+x_{n+1}]\in\mathrm{R}_{max\{K+1,2\}+1}^{\#}\), lo cual nos dice que vale \(\mathrm{Enu}_{n+1}\).  

Proof. (1)\(\Rightarrow\)(2) Rutina.

(2)\(\Rightarrow\)(1) Primero usaremos la Regla de Inducción desde 0 para probar que

1. adhocprefix(a)adhocsufix Si \(h\) es \(\emptyset\)-recursiva, entonces \(h^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Si \(h\in\mathrm{R}_{k}^{\emptyset}\), entonces \(h^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Recordemos que \[\mathrm{R}_{0}^{\emptyset}=\left\{ Suc,Pred,C_{0}^{0,0},C_{\varepsilon}^{0,0}\right\} \cup\left\{ p_{j}^{n,m}:1\leq j\leq n+m\right\}\] Note que \(Suc^{\#^{\emptyset}}=Suc\), \(Pred^{\#^{\emptyset}}=Pred\), \((C_{\varepsilon}^{0,0})^{\#^{\emptyset}}=C_{0}^{0}\) y \((C_{0}^{0,0})^{\#^{\emptyset}}=C_{0}^{0}\) por lo cual pertenecen a \(\mathrm{R}^{\#}\). Sean \(n,m,j\in\omega\) tales que \(1\leq j\leq n+m\). Sea \(F=Pred\circ\lambda x[1\dot{-}x]\). Por el lema anterior tenemos que \(F\in\mathrm{R}^{\#}\). Pero note que \[(p_{j}^{n,m})^{\#^{\emptyset}}=p_{j}^{n+m}\circ\left[p_{1}^{n+m},...,p_{n}^{n+m},F\circ p_{n+1}^{n+m},...,F\circ p_{n+m}^{n+m}\right]\] lo que nos dice que \((p_{j}^{n,m})^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Sea \(h\in\mathrm{R}_{k+1}^{\#}\). Por la definición de \(\mathrm{R}_{k+1}^{\#}\) hay varios casos.

Caso \(h\in\mathrm{R}_{k}^{\#}\). Trivial ya que vale \(\mathrm{Enu}_{k}\).

Caso \(h=R(f,\mathcal{G})\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\emptyset^{\ast}\\ \mathcal{G}_{a} & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast}\times\emptyset^{\ast}\rightarrow\emptyset^{\ast}\text{, para cada }a\in\emptyset \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacío. Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f^{\#^{\emptyset}}\in\mathrm{R}^{\#}\). Note que \[\begin{array}{rll} f^{\#^{\emptyset}}:S_{1}\times...\times S_{n}\times\{0\}^{m} & \rightarrow & \{0\}\\ (\vec{x},0,...,0) & \rightarrow & \#^{\emptyset}(f(\vec{x},\varepsilon,...,\varepsilon)) \end{array}\] Nótese que \(\mathcal{G}=\emptyset\), lo cual nos dice que, por definición de \(R(f,\mathcal{G})\): \[\begin{array}{rll} R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast} & \rightarrow & \emptyset^{\ast}\\ (\vec{x},\varepsilon,...,\varepsilon,\varepsilon) & \rightarrow & f(\vec{x},\varepsilon,...,\varepsilon) \end{array}\] O sea que \[\begin{array}{rll} R(f,\mathcal{G})^{\#^{\emptyset}}:S_{1}\times...\times S_{n}\times\{0\}^{m+1} & \rightarrow & \{0\}\\ (\vec{x},0,...,0) & \rightarrow & \#^{\emptyset}(f(\vec{x},\varepsilon,...,\varepsilon)) \end{array}\] Es decir que \[R(f,\mathcal{G})^{\#^{\emptyset}}=\lambda xy[x+y]\circ[G,F\circ p_{n+m+1}^{n+m+1}]\] donde \(F=Pred\circ\lambda x[1\dot{-}x]\) y \[G=f^{\#^{\emptyset}}\circ\left[p_{1}^{n+m+1},...,p_{n}^{n+m+1},p_{n+1}^{n+m+1},...,p_{n+m}^{n+m+1}\right]\] Pero el lema anterior nos dice que \(F,\lambda xy\left[x+y\right]\in\mathrm{R}^{\#}\), lo cual nos dice que \(R(f,\mathcal{G})^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Caso \(h=R(f,\mathcal{G})\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\omega\\ \mathcal{G}_{a} & :\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast}\rightarrow\omega\text{, para cada }a\in\emptyset \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacío. Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f^{\#^{\emptyset}}\in\mathrm{R}^{\#}\). Note que \[\begin{array}{rll} f^{\#^{\emptyset}}:S_{1}\times...\times S_{n}\times\{0\}^{m} & \rightarrow & \omega\\ (\vec{x},0,...,0) & \rightarrow & f(\vec{x},\varepsilon,...,\varepsilon) \end{array}\] Nótese que \(\mathcal{G}=\emptyset\), lo cual nos dice que, por definición de \(R(f,\mathcal{G})\): \[\begin{array}{rll} R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast} & \rightarrow & \omega\\ (\vec{x},\varepsilon,...,\varepsilon,\varepsilon) & \rightarrow & f(\vec{x},\varepsilon,...,\varepsilon) \end{array}\] O sea que \[\begin{array}{rll} R(f,\mathcal{G})^{\#^{\emptyset}}:S_{1}\times...\times S_{n}\times\{0\}^{m+1} & \rightarrow & \omega\\ (\vec{x},0,...,0) & \rightarrow & f(\vec{x},\varepsilon,...,\varepsilon) \end{array}\] Es decir que \[R(f,\mathcal{G})^{\#^{\emptyset}}=\lambda xy[x+y]\circ[G,F\circ p_{n+m+1}^{n+m+1}]\] donde \(F=Pred\circ\lambda x[1\dot{-}x]\) y \[G=f^{\#^{\emptyset}}\circ\left[p_{1}^{n+m+1},...,p_{n}^{n+m+1},p_{n+1}^{n+m+1},...,p_{n+m}^{n+m+1}\right]\] lo cual nos dice que \(R(f,\mathcal{G})^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Caso \(h=R(f,g)\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\omega\\ g & :\omega\times\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\omega \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacío. Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f^{\#^{\emptyset}},g^{\#^{\emptyset}}\in\mathrm{R}^{\#}\). Note que \[R(f,g)^{\#^{\emptyset}}=R(f^{\#^{\emptyset}},g^{\#^{\emptyset}})\] lo cual nos dice que \(R(f,g)^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Caso \(h=R(f,g)\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\emptyset^{\ast}\\ g & :\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast}\rightarrow\emptyset^{\ast} \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacío. Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(f^{\#^{\emptyset}},g^{\#^{\emptyset}}\in\mathrm{R}^{\#}\). Note que \[R(f,g)^{\#^{\emptyset}}=R(f^{\#^{\emptyset}},g^{\#^{\emptyset}})\] lo cual nos dice que \(R(f,g)^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Caso \(h=M(P)\), con \(P:\omega\times\omega^{n}\times\emptyset^{\ast m}\rightarrow\omega\), un predicado en \(\mathrm{R}_{k}^{\emptyset}\). Ya que vale \(\mathrm{Enu}_{k}\) tenemos que \(P^{\#^{\emptyset}}\in\mathrm{R}^{\#}\). Sea \[Q=P^{\#^{\emptyset}}\circ\left[p_{1}^{1+n},...,p_{n}^{1+n},C_{0}^{1}\circ p_{1}^{1+n},...,C_{0}^{1}\circ p_{1}^{1+n}\right]\] Note que \(Q\in\mathrm{R}^{\#}\) y \(Q\) es total. Esto nos dice que \(M(Q)\in\mathrm{R}^{\#}\). Pero \[M(P)^{\#^{\emptyset}}=S\circ[M(Q)\circ[p_{1}^{n+m},...,p_{n}^{n+m}],F\circ p_{n+1}^{n+m},...,F\circ p_{n+m}^{n+m}]\] donde \(S=\lambda x_{1}...x_{m+1}[x_{1}+...+x_{m+1}]\) y \(F=Pred\circ\lambda x[1\dot{-}x]\). El lema anterior nos garantiza que \(S,F\in\mathrm{R}^{\#}\), por lo que \(M(P)^{\#^{\emptyset}}\in\mathrm{R}^{\#}\).

Caso \(h=f\circ[f_{1},...,f_{r}]\text{, con }f,f_{1},...,f_{r}\in\mathrm{R}_{k}^{\emptyset}\text{, }r\geq1\). Es facil probar que \[h^{\#^{\emptyset}}=f^{\#^{\emptyset}}\circ[f_{1}^{\#^{\emptyset}},...,f_{r}^{\#^{\emptyset}}]\] por lo cual podemos aplicar \(\mathrm{Enu}_{k}\).

O sea que hemos probado (a). Asumamos ahora que \(h\) es una función \(\Sigma\)-recursiva y numérica. Veremos que entonces \(h\in\mathrm{R}^{\#}\). Ya que \(h\) es numérica tenemos que es \(\emptyset\)-mixta. O sea que por Independencia del Alfabeto tenemos que \(h\) es \(\emptyset\)-recursiva. Pero entonces (a) nos dice que \(h^{\#}\in\mathrm{R}^{\#}\) lo cual nos dice que \(h\in\mathrm{R}^{\#}\) ya que \(h^{\#}=h\).