4.6 Resultados basicos presentados en paradigma recursivo

En esta seccion presentaremos varios de los resultados basicos de computabilidad, expresados en el paradigma recursivo, ya que es el mas habitual y comodo. Varios de estos resultados ya han sido establecidos dentro del desarrollo de la computabilidad efectiva en el Capitulo 3. A estos resultados los enunciaremos dentro del paradigma de Godel y daremos pruebas rigurosas matematicas de ellos usando la teoria desarrollada hasta ahora. Sin envargo, veremos que hay otros resultados que son dependientes del desarrollo matematico hecho y aportan nueva informacion al paradigma filosofico (la indecidibilidad del halting problem, por ejemplo).

Como veremos muchas de las pruebas seran de naturaleza imperativa basadas en la equivalencia del paradigma de Godel con el imperativo de Neumann.

4.6.1 Lema de division por casos para funciones $\Sigma$-recursivas

Proof. Probaremos el caso $k=2$ y $O={\Sigma }^{\ast }$. Ademas supondremos que $n=m=1$. Sean $P_1$ y $P_2$ programas que computen las funciones $f_1$ y $f_2$, respectivamente. Para $i=1,2$, definamos $$H_i=\lambda t{x}_1{\alpha }_1\left[Hal{t}^{1,1}\right(t,x_1,{\alpha }_1,P_i\left)\right]$$ Notar que $D_{H_i}={\omega }^2\times {\Sigma }^{\ast }$ y que $H_i$ es $\Sigma$-mixta. Ademas sabemos que la funcion $Hal{t}^{1,1}$ es $(\Sigma \cup {\Sigma }_p)$-p.r. por lo cual resulta facilmente que $H_i$ es $(\Sigma \cup {\Sigma }_p)$-p.r.. Por Independencia del Alfabeto tenemos que $H_i$ es $\Sigma$-p.r. y por lo tanto el Segundo Manantial de Macros nos dice que en $S^{\Sigma }$ hay un macro: $$\left[IF{H}_i\right(V1,V2,W1\left)GOTOA1\right]$$ Para hacer mas intuitivo el uso de este macro lo escribiremos de la siguiente manera $$\left[IFHal{t}^{1,1}\right(V1,V2,W1,P_i\left)GOTOA1\right]$$ Ya que cada $f_i$ es $\Sigma$-computable, el Primer Manantial de Macros nos dice que en $S^{\Sigma }$ hay macros $$\begin{array}{cc}& [W2\leftarrow f_1(V1,W1\left)\right]\\ & [W2\leftarrow f_2(V1,W1\left)\right]\end{array}$$ Sea $P$ el siguiente programa: $$\begin{array}{c}L1N20\leftarrow N20+1\\ \left[IFHal{t}^{1,1}\right(N20,N1,P1,P_1\left)GOTOL2\right]\\ \left[IFHal{t}^{1,1}\right(N20,N1,P1,P_2\left)GOTOL3\right]\\ GOTOL1\\ L2[P1\leftarrow f_1(N1,P1\left)\right]\\ GOTOL4\\ L3[P1\leftarrow f_2(N1,P1\left)\right]\\ L4SKIP\end{array}$$ Notese que $P$ computa la funcion $f_1\cup f_2$ por lo cual ya que sabemos que Godel vence a Neumann, la funcion $f_1\cup f_2$ es $\Sigma$-recursiva.  

La prueba del lema anterior es de naturaleza imperativa ya que da explicitamente un programa (de todas maneras usa el paradigma recursivo o Godeliano para justificar la existencia de los macros). A continuacion daremos una prueba la cual es mas recursiva (aunque aun usa el paradigma imperativo en la existencia de los programas $P_i$).

Proof. Sean $P_1$ y $P_2$ programas que computen las funciones $f_1$ y $f_2$, respectivamente. Sean $$\begin{array}{cc}{P}_1& =\lambda t\overrightarrow{x}\overrightarrow{\alpha }\left[Hal{t}^{n,m}\right(t,\overrightarrow{x},\overrightarrow{\alpha },P_1\left)\right]\\ P_2& =\lambda t\overrightarrow{x}\overrightarrow{\alpha }\left[Hal{t}^{n,m}\right(t,\overrightarrow{x},\overrightarrow{\alpha },P_2\left)\right]\end{array}$$ Notese que $D_{P_1}=D_{P_2}=\omega \times {\omega }^n\times {\Sigma }^{\ast m}$ y que $P_1$ y $P_2$ son $(\Sigma \cup {\Sigma }_p)$-p.r.. Ya que son $\Sigma$-mixtos, el Teorema 4.2 nos dice que son $\Sigma$-p.r.. Tambien notese que $D_{M\left(\right(P_1\vee P_2\left)\right)}=D_{f_1}\cup D_{f_2}$. Definamos $$\begin{array}{cc}{g}_1& =\lambda \overrightarrow{x}\overrightarrow{\alpha }\left[E_{\ast 1}^{n,m}\right(M\left(\right(P_1\vee P_2\left)\right)(\overrightarrow{x},\overrightarrow{\alpha }),\overrightarrow{x},\overrightarrow{\alpha },P_1{)}^{P_1\left(M\left(\right(P_1\vee P_2\left)\right)\right(\overrightarrow{x},\overrightarrow{\alpha }),\overrightarrow{x},\overrightarrow{\alpha })}]\\ g_2& =\lambda \overrightarrow{x}\overrightarrow{\alpha }\left[E_{\ast 1}^{n,m}\right(M\left(\right(P_1\vee P_2\left)\right)(\overrightarrow{x},\overrightarrow{\alpha }),\overrightarrow{x},\overrightarrow{\alpha },P_2{)}^{P_2\left(M\left(\right(P_1\vee P_2\left)\right)\right(\overrightarrow{x},\overrightarrow{\alpha }),\overrightarrow{x},\overrightarrow{\alpha })}]\end{array}$$ Notese que $g_1$ y $g_2$ son $\Sigma$-recursivas y que $D_{g_1}=D_{g_2}=D_{f_1}\cup D_{f_2}$, Ademas notese que $$g_1(\overrightarrow{x},\overrightarrow{\alpha })=\{\begin{array}{ccc}{f}_1(\overrightarrow{x},\overrightarrow{\alpha })& & \text{si}(\overrightarrow{x},\overrightarrow{\alpha })\in D_{f_1}\\ \epsilon & & \text{caso contrario}\end{array}$$ $$g_2(\overrightarrow{x},\overrightarrow{\alpha })=\{\begin{array}{ccc}{f}_2(\overrightarrow{x},\overrightarrow{\alpha })& & \text{si}(\overrightarrow{x},\overrightarrow{\alpha })\in D_{f_2}\\ \epsilon & & \text{caso contrario}\end{array}$$ O sea que $f_1\cup f_2=\lambda \alpha \beta \left[\alpha \beta \right]\circ [g_1,g_2]$ es $\Sigma$-recursiva.  

4.6.2 Conjuntos $\Sigma$-recursivos y $\Sigma$-recursivamente enumerables

A continuacion probaremos los resultados basicos sobre conjuntos $\Sigma$-efectivamente computables y $\Sigma$-efectivamente enumerables, dados en las Secciones [definicion=000020de=000020conjunto=000020sigma-efectivamente=000020enumerable] y [definicion=000020de=000020conjunto=000020sigma-efectivamente=000020computable], pero enunciados dentro del paradigma de Godel.

Proof. Note que $$\begin{array}{cc}\neg P& =\lambda xy\left[x\dot{-}y\right]\circ [C_1^{n,m},P]\\ (P\wedge Q)& =\lambda xy[x.y]\circ [P,Q]\\ (P\vee Q)& =\neg (\neg P\wedge \neg Q).\end{array}$$  

Proof. Es directa del lema anterior.  

Proof. Podemos suponer que ni $S_1$ ni $S_2$ son vacios ya que de lo contrario (1) y (2) se cumplen trivialmente. Ademas supondremos que $n=2$ y $m=1$.

(1). La idea de la prueba es la misma que la que usamos para probar que la union de conjuntos $\Sigma$-efectivamente enumerables es $\Sigma$-efectivamente enumerable. Daremos usando macros un programa que enumera a $S_1\cup S_2$ y luego aplicaremos la Caracterizacion de $\Sigma$-enumerabilidad. Por hipotesis hay funciones $F:\omega \to \omega \times \omega \times {\Sigma }^{\ast }$ y $G:\omega \to \omega \times \omega \times {\Sigma }^{\ast }$ tales que $F_{\left(1\right)}$, $F_{\left(2\right)}$, $F_{\left(3\right)}$, $G_{\left(1\right)}$, $G_{\left(2\right)}$ y $G_{\left(3\right)}$ son $\Sigma$-recursivas, $Im\left(F\right)=S_1$ y $Im\left(G\right)=S_2$. Ya que estas funciones tambien son $\Sigma$-computables, hay macros $$\begin{array}{cc}& [V2\leftarrow F_{\left(1\right)}(V1\left)\right]\\ & [V2\leftarrow F_{\left(2\right)}(V1\left)\right]\\ & [W1\leftarrow F_{\left(3\right)}(V1\left)\right]\\ & [V2\leftarrow G_{\left(1\right)}(V1\left)\right]\\ & [V2\leftarrow G_{\left(2\right)}(V1\left)\right]\\ & [W1\leftarrow G_{\left(3\right)}(V1\left)\right]\end{array}$$ Ya que el predicado $Par=\lambda x[x$ es par$]$ es $\Sigma$-p.r., tenemos que hay un macro: $$\left[IFPar\right(V1\left)GOTOA1\right]$$ el cual escribiremos de la siguiente manera mas intuitiva $$\left[IFV1\text{es par}GOTOA1\right]$$ Ya que la funcion $D=\lambda x[\lfloor x/2\rfloor ]$ es $\Sigma$-p.r., tenemos que hay un macro: $$[V2\leftarrow D(V1\left)\right]$$ el cual escribiremos de la siguiente manera mas intuitiva $$[V2\leftarrow \lfloor V1/2\rfloor ]$$ Sea $P$ el siguiente programa: $$\begin{array}{cc}& [IFN1\text{es par}GOTOL1\\ & N1\leftarrow N1\dot{-}1\\ & [N1111\leftarrow \lfloor N1/2\rfloor ]\\ & [N1\leftarrow G_{\left(1\right)}(N1111\left)\right]\\ & [N2\leftarrow G_{\left(2\right)}(N1111\left)\right]\\ & [P1\leftarrow G_{\left(3\right)}(N1111\left)\right]\\ & GOTOL2\\ L1& [N1111\leftarrow \lfloor N1/2\rfloor ]\\ & [N1\leftarrow F_{\left(1\right)}(N1111\left)\right]\\ & [N2\leftarrow F_{\left(2\right)}(N1111\left)\right]\\ & [P1\leftarrow F_{\left(3\right)}(N1111\left)\right]\\ L2& SKIP\end{array}$$ Es facil ver que $P$ cumple (a) y (b) de (3) de la Caracterizacion de $\Sigma$-enumerabilidad por lo cual $S_1\cup S_2$ es $\Sigma$-enumerable. Esto nos dice que $S_1\cup S_2$ es $\Sigma$-r.e. ya que como vimos Godel vence a Neumann.

(2). Es dejada al lector  

Tal como veremos mas adelante hay conjuntos $\Sigma$-recursivamente enumerables los cuales no son $\Sigma$-recursivos. Sin envargo tenemos el siguiente interesante resultado.

Proof. (a)$\Rightarrow$(b). Si $S=\varnothing$, por definicion $S$ es $\Sigma$-recursivamente enumerable. Supongamos entonces $S\ne \varnothing$. Haremos el caso en el que $n=m=1$ y $(0,\epsilon )\in S$. Sea $\le$ un orden total sobre $\Sigma$. Por hipotesis tenemos que ${\chi }_S^{\omega \times {\Sigma }^{\ast }}$ es $\Sigma$-recursiva por lo cual hay un macro $$\left[IF{\chi }_S^{\omega \times {\Sigma }^{\ast }}\right(V1,W1\left)GOTOA1\right]$$ Ya que la funcion $f=\lambda x\left[\right(x{)}_1]$ es $\Sigma$-p.r. hay un macro $$[V2\leftarrow f(V1\left)\right]$$ el cual escribiremos de la siguiente manera: $$[V2\leftarrow (V1{)}_1]$$ Ya que la funcion $g=\lambda x\left[{\ast }^{\le }\right(\left(x{)}_2\right)]$ es $\Sigma$-p.r. hay un macro $$[W1\leftarrow g(V1\left)\right]$$ el cual escribiremos de la siguiente manera: $$[W1\leftarrow {\ast }^{\le }(\left(V1{)}_2\right)]$$ (Dejamos al lector entender bien el funcionamiento de estos macros.) Sea $P$ el siguiente programa: $$\begin{array}{c}N1\leftarrow N1+1\\ [N2\leftarrow (N1{)}_1]\\ [P2\leftarrow {\ast }^{\le }(N1{)}_2]\\ \left[IF{\chi }_S^{\omega \times {\Sigma }^{\ast }}\right(N2,P2)GOTOL1\\ N1\leftarrow 0\\ P1\leftarrow \epsilon \\ GOTOL2\\ L1[N1\leftarrow N2]\\ [P1\leftarrow P2)]\\ L2SKIP\end{array}$$ Notese que $Dom\left([{\Psi }_P^{1,0,\#},{\Psi }_P^{1,0,\ast }]\right)=\omega$ y que $Im\left([{\Psi }_P^{1,0,\#},{\Psi }_P^{1,0,\ast }]\right)=S$ por lo cual $S$ es $\Sigma$-enumerable lo que nos dice que $S$ es $\Sigma$-recursivamente enumerable.

(b)$\Rightarrow$(a). Haremos el caso en que los conjuntos $S$ y $({\omega }^n\times {\Sigma }^{\ast m})-S$ son no vacios. Tambien supondremos $n=m=1$. Por hipotesis hay funciones $F:\omega \to \omega \times {\Sigma }^{\ast }$ y $G:\omega \to \omega \times {\Sigma }^{\ast }$ tales que $F_{\left(1\right)}$, $F_{\left(2\right)}$, $G_{\left(1\right)}$ y $G_{\left(2\right)}$ son $\Sigma$-recursivas, $Im\left(F\right)=S$ y $Im\left(G\right)=(\omega \times {\Sigma }^{\ast })-S$. Hay macros $$\begin{array}{cc}& [V2\leftarrow F_{\left(1\right)}(V1\left)\right]\\ & [W1\leftarrow F_{\left(2\right)}(V1\left)\right]\\ & [V1\leftarrow G_{\left(1\right)}(V1\left)\right]\\ & [W1\leftarrow G_{\left(2\right)}(V1\left)\right]\end{array}$$ Ya que los predicados $D=\lambda xy[x\ne y]$ y $D^{\prime }=\lambda \alpha \beta [\alpha \ne \beta ]$ son $\Sigma$-p.r. hay macros $$\begin{array}{cc}& \left[IFD\right(V1,V2\left)GOTOA1\right]\\ & \left[IF{D}^{\prime }\right(W1,W2\left)GOTOA1\right]\end{array}$$ los cuales para hacer mas amigable la lectura los escribieremos de la siguiente manera $$\begin{array}{cc}& [IFV1\ne V2GOTOA1]\\ & [IFW1\ne W2GOTOA1]\end{array}$$ Tambien usaremos el macro $$[V1\leftarrow C_1^{0,0}(◊\left)\right]$$ (asociado a la funcion $\Sigma$-p.r. $C_1^{0,0}$), el cual escribiremos de la siguiente manera $$[V1\leftarrow 1]$$ Sea $P$ el siguiente programa: $$\begin{array}{c}L1[N2\leftarrow F_{\left(1\right)}(N20\left)\right]\\ [P2\leftarrow F_{\left(2\right)}(N20\left)\right]\\ [IFN2\ne N1GOTOL2]\\ [IFP2\ne P1GOTOL2]\\ [N1\leftarrow 1]\\ GOTOL3\\ L2[N2\leftarrow G_{\left(1\right)}(N20\left)\right]\\ [P2\leftarrow G_{\left(2\right)}(N20\left)\right]\\ [IFN2\ne N1GOTOL4]\\ [IFP2\ne P1GOTOL4]\\ N1\leftarrow 0\\ GOTOL3\\ L4N20\leftarrow N20+1\\ GOTOL1\\ L3SKIP\end{array}$$ Notese que $P$ computa a la funcion ${\chi }_S^{\omega \times {\Sigma }^{\ast }}$ por lo cual ${\chi }_S^{\omega \times {\Sigma }^{\ast }}$ es $\Sigma$-computable lo que nos dice que es $\Sigma$-recursiva. Esto por definicion nos dice que $S$ es $\Sigma$-recursivo  

Proof. Si $S=\varnothing$, entonces $f{|}_S=\varnothing$ y por lo tanto $f{|}_S$ es $\Sigma$-recursiva. Supongamos $S\ne \varnothing$. Haremos el caso $n=m=1$ y $O={\Sigma }^{\ast }$. Tenemos que hay una $F:\omega \to \omega \times {\Sigma }^{\ast }$ tal que $ImF=S$ y $F_{\left(1\right)}$, $F_{\left(2\right)}$ son $\Sigma$-recursivas. Ya que $f$, $F_{\left(1\right)}$ y $F_{\left(2\right)}$ son $\Sigma$-recursivas, hay macros $$\begin{array}{cc}& [W2\leftarrow f(V1,W1\left)\right]\\ & [V2\leftarrow F_{\left(1\right)}(V1\left)\right]\\ & [W1\leftarrow F_{\left(2\right)}(V1\left)\right]\end{array}$$ Usaremos los macros $$\begin{array}{cc}& [IFV1\ne V2GOTOA1]\\ & [IFW1\ne W2GOTOA1]\end{array}$$ Sea $P$ el siguiente programa $$\begin{array}{cc}L2& [N2\leftarrow F_{\left(1\right)}(N20\left)\right]\\ & [P2\leftarrow F_{\left(2\right)}(N20\left)\right]\\ & [IFN1\ne N2GOTOL1]\\ & [IFP1\ne P2GOTOL1]\\ & [P1\leftarrow f(N1,P1\left)\right]\\ & GOTOL3\\ L1& N20\leftarrow N20+1\\ & GOTOL2\\ L3& SKIP\end{array}$$ Es facil ver que $P$ computa a $f{|}_S$  

Ahora probaremos el analogo recursivo del Teorema 3.2.

Proof. El caso $n=m=0$ es facil y es dejado al lector. Supongamos entonces que $n+m\ge 1$.

(2)$\Rightarrow$(3). Haremos el caso $k=l=1$ y $n=m=2$. El caso general es completamente analogo. Notese que entonces tenemos que $S\subseteq {\omega }^2\times {\Sigma }^{\ast 2}$ y $F:D_F\subseteq \omega \times {\Sigma }^{\ast }\to {\omega }^2\times {\Sigma }^{\ast 2}$ es tal que $ImF=S$ y $F_{\left(1\right)}$, $F_{\left(2\right)}$, $F_{\left(3\right)}$, $F_{\left(4\right)}$ son $\Sigma$-recursivas. Para cada $i\in \{1,2,3,4\}$, sea $P_i$ un programa el cual computa a $F_{\left(i\right)}$. Sea $\le$ un orden total sobre $\Sigma$. Definamos $$H_i=\lambda t{x}_1{\alpha }_1\left[\neg Hal{t}^{1,1}\right(t,x_1,{\alpha }_1,P_i\left)\right]$$ Notar que $D_{H_i}={\omega }^2\times {\Sigma }^{\ast }$ y que $H_i$ es $\Sigma$-mixta. Ademas sabemos que la funcion $Hal{t}^{1,1}$ es $(\Sigma \cup {\Sigma }_p)$-p.r. por lo cual resulta facilmente que $H_i$ es $(\Sigma \cup {\Sigma }_p)$-p.r.. Por Independencia del Alfabeto tenemos que $H_i$ es $\Sigma$-p.r., por lo cual el Segundo Manantial de Macros nos dice que hay un macro: $$\left[IF{H}_i\right(V2,V1,W1\left)GOTOA1\right]$$ Para hacer mas intuitivo el uso de este macro lo escribiremos de la siguiente manera $$\left[IF\neg Hal{t}^{1,1}\right(V2,V1,W1,P_i\left)GOTOA1\right]$$ Para $i=1,2$, definamos $$E_i=\lambda xt{x}_1{\alpha }_1[x\ne E_{\#1}^{1,1}(t,x_1,{\alpha }_1,P_i\left)\right]$$ Para $i=3,4$, definamos $$E_i=\lambda t{x}_1{\alpha }_1\alpha [\alpha \ne E_{\ast 1}^{1,1}(t,x_1,{\alpha }_1,P_i\left)\right]$$ Dejamos al lector probar que las funciones $E_i$ son $\Sigma$-p.r.. O sea que para cada $i\in \{1,2\}$ hay un macro $$\left[IF{E}_i\right(V2,V3,V1,W1\left)GOTOA1\right]$$ y para cada $i\in \{3,4\}$ hay un macro $$\left[IF{E}_i\right(V2,V1,W1,W2\left)GOTOA1\right]$$ Haremos mas intuitiva la forma de escribir estos macros, por ejemplo para $i=1$, lo escribiremos de la siguiente manera $$[IFV2\ne E_{\#1}^{1,1}(V3,V1,W1,P_1\left)GOTOA1\right]$$ Ya que la funcion $f=\lambda x\left[\right(x{)}_1]$ es $\Sigma$-p.r., hay un macro $$[V2\leftarrow f(V1\left)\right]$$ el cual escribiremos de la siguiente manera: $$[V2\leftarrow (V1{)}_1]$$ Similarmente hay macros: $$[W1\leftarrow {\ast }^{\le }(V1{)}_3]$$ $$[V2\leftarrow (V1{)}_2]$$ (dejamos al lector entender bien el funcionamiento de estos macros). Sea $P$ el siguiente programa de $S^{\Sigma }$: $$\begin{array}{c}L1N20\leftarrow N20+1\\ [N10\leftarrow (N20{)}_1]\\ [N3\leftarrow (N20{)}_2]\\ [P3\leftarrow {\ast }^{\le }(N20{)}_3]\\ \left[IF\neg Hal{t}^{1,1}\right(N10,N3,P3,P_1\left)GOTOL1\right]\\ \left[IF\neg Hal{t}^{1,1}\right(N10,N3,P3,P_2\left)GOTOL1\right]\\ \left[IF\neg Hal{t}^{1,1}\right(N10,N3,P3,P_3\left)GOTOL1\right]\\ \left[IF\neg Hal{t}^{1,1}\right(N10,N3,P3,P_4\left)GOTOL1\right]\\ [IFN1\ne E_{\#1}^{1,1}(N10,N3,P3,P_1\left)GOTOL1\right]\\ [IFN2\ne E_{\#1}^{1,1}(N10,N3,P3,P_2\left)GOTOL1\right]\\ [IFP1\ne E_{\ast 1}^{1,1}(N10,N3,P3,P_3\left)GOTOL1\right]\\ [IFP2\ne E_{\ast 1}^{1,1}(N10,N3,P3,P_4\left)GOTOL1\right]\end{array}$$ Dejamos al lector la tarea de comprender el funcionamiento de este programa y convenserse de que computa la funcion $p_1^{2,2}{|}_S$. Pero entonces $p_1^{2,2}{|}_S$ es $\Sigma$-computable por lo cual es $\Sigma$-recursiva, lo cual prueba (3) ya que $Dom\left(p_1^{2,2}{|}_S\right)=S$.

(3)$\Rightarrow$(4). Supongamos $S\ne \varnothing$. Sea $(z_1,...,z_n,{\gamma }_1,...,{\gamma }_m)\in S$ fijo. Sea $P$ un programa el cual compute a $f$ y Sea $\le$ un orden total sobre $\Sigma$. Sea $P:N\to \omega$ dado por $P\left(x\right)=1$ sii $$Hal{t}^{n,m}\left(\right(x{)}_{n+m+1},(x{)}_1,...,(x{)}_n,{\ast }^{\le }\left(\right(x{)}_{n+1}),...,{\ast }^{\le }(\left(x{)}_{n+m}\right)),P)=1$$ Es facil ver que $P$ es $(\Sigma \cup {\Sigma }_p)$-p.r. por lo cual es $\Sigma$-p.r.. Sea $\overline{P}=P\cup C_0^{1,0}{|}_{\left\{0\right\}}$. Para $i=1,...,n$, definamos $F_i:\omega \to \omega$ de la siguiente manera $$F_i\left(x\right)=\{\begin{array}{ccc}(x{)}_i& \text{si}& \overline{P}\left(x\right)=1\\ z_i& \text{si}& \overline{P}\left(x\right)\ne 1\end{array}$$ Para $i=n+1,...,n+m$, definamos $F_i:\omega \to {\Sigma }^{\ast }$ de la siguiente manera $$F_i\left(x\right)=\{\begin{array}{ccc}{\ast }^{\le }\left(\right(x{)}_i)& \text{si}& \overline{P}\left(x\right)=1\\ {\gamma }_{i-n}& \text{si}& \overline{P}\left(x\right)\ne 1\end{array}$$ Por el Lema de Division por Casos, cada $F_i$ es $\Sigma$-p.r.. Es facil ver que $F=[F_1,...,F_{n+m}]$ cumple (4).