En esta seccion desarrollaremos el modelo matematico del concepto de funcion Σ-efectivamente computable, dado por Godel. Dichas funciones seran llamadas Σ-recursivas. La idea es partir de un conjunto inicial de funciones muy simples y obviamente Σ-efectivamente computables y luego obtener nuevas funciones Σ-efectivamente computables usando constructores que preservan la computabilidad efectiva. Las funciones Σ-recursivas seran 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 tambien lo llamaremos el paradigma funcional.
La familia de funciones simples y obviamente Σ-efectivamente computables de la que partiremos es la siguiente {Suc,Pred,C0,00,C0,0ε}∪{da:a∈Σ}∪{pn,mj:1≤j≤n+m} Los constructores que usaremos son:
- Composicion
- Recursion primitiva
- Minimizacion de predicados Σ-totales
Estos constructores nos permiten dadas ciertas funciones construir o definir una nueva funcion y tienen la propiedad de preservar la computabilidad efectiva en el sentido que si las funciones iniciales son Σ-efectivamente computables, entonces la funcion obtenida tambien lo es. Un concepto fundamental es el de funcion Σ-recursiva primitiva. Estas funciones seran aquellas que se obtienen a partir de las del conjunto inicial usando solo los dos primeros constructores: composicion y recursion primitiva. Nuestro primer objetivo es definir el concepto de funcion Σ-recursiva primitiva para lo cual en las proximas dos secciones definiremos y estudiaremos los constructores de composicion y recursion primitiva. Luego definiremos el concepto de funcion Σ-recursiva primitiva y nos abocaremos a desarrollar este concepto fundamental. Recien despues estudiaremos el constructor de minimizacion y definiremos el concepto de funcion Σ-recursiva. La ultima parte de la seccion esta destinada a probar un teorema que nos dice que los conceptos de funcion Σ-recursiva y Σ-recursiva primitiva son independientes del alfabeto Σ.
Dadas funciones Σ-mixtas f,f1,...,fr, con r≥1, diremos que la funcion f∘[f1,...,fr] es obtenida por composicion a partir de las funciones f,f1,...,fr. Para probar que la composicion preserva la computabilidad efectiva necesitaremos el siguiente lema.
4.1. Supongamos que f,f1,...,fr son funciones Σ-mixtas, con r≥1. Supongamos ademas que f∘[f1,...,fr]≠∅. Entonces hay n,m,k,l∈ω y s∈{#,∗} tales que
- r=n+m
- f es de tipo (n,m,s)
- fi es de tipo (k,l,#), para cada i=1,...,n
- fi es de tipo (k,l,∗), para cada i=n+1,...,n+m
Mas aun, en tal caso la funcion f∘[f1,...,fn+m] es de tipo (k,l,s) y: Df∘[f1,...,fn+m]={(→x,→α)∈n+m⋂i=1Dfi:(f1(→x,→α),...,fn+m(→x,→α))∈Df}f∘[f1,...,fn+m](→x,→α)=f(f1(→x,→α),...,fn+m(→x,→α)).
Proof. Notese que f≠∅ y [f1,...,fr]≠∅ (por que?). Ya que f≠∅ tenemos que hay unicos n,m∈ω y s∈{#,∗} tales que f es de tipo (n,m,s). Ya que f∘[f1,...,fr]≠∅ y I[f1,...,fr]⊆If1×...×Ifr, tenemos que
- r=n+m
- Ifi⊆ω, para cada i=1,...,n
- Ifi⊆Σ∗, para cada i=n+1,...,n+m
Ya que [f1,...,fr]≠∅ tenemos que D[f1,...,fr]=⋂ri=1Dfi≠∅, por lo cual los conjuntos Df1,...,Dfn+m deberan ser todos de un mismo tipo, digamos de tipo (k,l). Es decir que fi es de tipo (k,l,#), para cada i=1,...,n y fi es de tipo (k,l,∗), para cada i=n+1,...,n+m.
Las ultimas observaciones del lema son directas de las definiciones de [f1,...,fn+m] y de composicion de funciones
Ahora si podemos probar facilmente que el contructor composicion preserva la computabilidad efectiva
4.2. Si f,f1,...,fr, con r≥1, son Σ-efectivamente computables, entonces f∘[f1,...,fr] lo es.
Proof. Si f∘[f1,...,fr]=∅, entonces claramente es Σ-efectivamente computable. Supongamos entonces que f∘[f1,...,fr]≠∅. Por el lema anterior hay n,m,k,l∈ω y s∈{#,∗} tales que
- r=n+m
- f es de tipo (n,m,s)
- fi es de tipo (k,l,#), para cada i=1,...,n
- fi es de tipo (k,l,∗), para cada i=n+1,...,n+m
Sean P,P1,...,Pn+m procedimientos efectivos los cuales computen computen las funciones f,f1,...,fn+m, respectivamente. Usando estos procedimientos es facil definir un procedimiento efectivo el cual compute a f∘[f1,...,fn+m].
La recursion primitiva es un tipo muy particular de recursion. Consideremos por ejemplo las siguientes ecuaciones:
(1) R(0)=1
(2) R(t+1)=1+R(t)+R(t)2
Notese que hay una unica funcion R:ω→ω 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 ecuacion (1) nos dice que R(0)=1 pero entonces la ecuacion (2) nos dice que R(1)=1+1+12=3 por lo cual nuevamente la ecuacion (2) nos dice que R(2)=1+3+32=13 y asi podemos notar facilmente que R esta determinada por dichas ecuaciones.
Se suele decir que las ecuaciones (1) y (2) definen recursivamente a la funcion R pero hay que tener cuidado porque esto es una manera de hablar ya que la funcion R podria 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 unica que las cumple. Por ejemplo las ecuaciones:
(a) R(0)=50
(b) R(t+1)=R(t)
definen recursivamente a la funcion C1,050 pero esta claro que la definicion de C1,050 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 tambien depende de t. Por ejemplo
(i) R(0)=1
(ii) R(t+1)=t.R(t)+1
De todas maneras deberia quedar claro que las ecuaciones (i) y (ii) determinan una unica funcion R:ω→ω que las satisface.
Tambien podemos generalizar pensando que la funcion R depende no solo de un parametro t sino que su dominio es ω4, es decir depende de t y x1,x2,x3. Por ejemplo
(p) R(0,x1,x2,x3)=x1+2x3
(q) R(t+1,x1,x2,x3)=t+x1+x2+x3+R(t,x1,x2,x3)
Dejamos al lector convencerse de que (p) y (q) son cumplidas por una unica funcion R:ω4→ω. Tambien podriamos tener variables alfabeticas. Por ejemplo consideremos
(r) R(0,x1,x2,α1,α2)=x1+|α1|x2
(s) R(t+1,x1,x2,α1,α2)=t+x1+x2+|α1|+|α2|+R(t,x1,x2,α1,α2)
Es claro aqui que las ecuaciones (r) y (s) determinan una unica funcion R:ω3×Σ∗2→ω que las cumple. Esto se puede explicar de la siguiente manera:
- La ecuacion (r) determina los valores de R sobre el conjunto {0}×ω×ω×Σ∗×Σ∗. Pero una ves determinados estos valores, la ecuacion (s) tomada con t=0, determina los valores de R sobre el conjunto {1}×ω×ω×Σ∗×Σ∗. Pero una ves determinados estos valores, la ecuacion (s) tomada con t=1, determina los valores de R sobre el conjunto {2}×ω×ω×Σ∗×Σ∗, etc
El caso anterior podria generalizarse de la siguiente manera: Si tenemos dadas dos funciones f:ωn×Σ∗m→ωg:ωn+2×Σ∗m→ω entonces las ecuaciones:
(a) R(0,→x,→α)=f(→x,→α)
(b) R(t+1,→x,→α)=g(R(t,→x,→α),t,→x,→α)
determinan una unica funcion R:ωn+1×Σ∗m→ω que las cumple. Notese que para el caso n=m=2f=λx1x2α1α2[x1+|α1|x2]g=λxtx1x2α1α2[t+x1+x2+|α1|+|α2|+x] las ecuaciones (a) y (b) se transforman en las ecuaciones (r) y (s).
El primer caso de recursion primitiva que definiremos a continuacion engloba los ejemplos vistos recien dentro de un marco general.
Supongamos tenemos dadas funciones f:S1×...×Sn×L1×...×Lm→ωg:ω×ω×S1×...×Sn×L1×...×Lm→ω con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ conjuntos no vacios. Usando el razonamiento inductivo usado en los ejemplos anteriores, se puede probar que hay una unica funcion R:ω×S1×...×Sn×L1×...×Lm→ω la cual cumple las ecuaciones
- R(0,→x,→α)=f(→x,→α)
- R(t+1,→x,→α)=g(R(t,→x,→α),t,→x,→α)
LLamaremos R(f,g) a esta unica funcion que cumple las ecuaciones anteriores. Resumiendo, diremos que las ecuaciones
(1) R(f,g)(0,→x,→α)=f(→x,→α)
(2) R(f,g)(t+1,→x,→α)=g(R(f,g)(t,→x,→α),t,→x,→α)
definen recursivamente a la funcion R(f,g). Tambien diremos que R(f,g) es obtenida por recursion primitiva a partir de f y g.
NOTA IMPOTANTE: No confundirse y pensar que R(f,g) es el resultado de aplicar una funcion R al par (f,g), de hecho hasta el momento no hemos definido ninguna funcion R cuyo dominio sea cierto conjunto de pares ordenados de funciones!
Notese que cuando m=n=0, se tiene que Df={◊} y (1) y (2) se transforman en
(1) R(f,g)(0)=f(◊)
(2) R(f,g)(t+1)=g(R(f,g)(t),t)
Veamos algunos ejemplos
(E1) Tomemos f=p1,01 y g=Suc∘p3,01. De la definicion de R(f,g), obtenemos que su dominio es ω2 y R(f,g)(0,x1)=p1,01(x1)=x1R(f,g)(t+1,x1)=(Suc∘p3,01)(R(f,g)(t,x1),t,x1)=R(f,g)(t,x1)+1 Es facil notar que la unica funcion que cumple estas dos ecuaciones es λtx1[t+x1], lo cual implica que λtx1[t+x1]=R(p1,01,Suc∘p3,01)
(E2) Sean f=C0,00 y g=p2,01. De la definicion de R(f,g), obtenemos que su dominio es ω y R(f,g)(0)=C0,00(◊)=0R(f,g)(t+1)=p2,01(R(f,g)(t),t)=R(f,g)(t) Es facil notar que la unica funcion que cumple estas dos ecuaciones es C1,00 lo cual implica que C1,00=R(C0,00,p2,01)
Como era de esperar, este caso del constructor de recursion primitiva preserva la computabilidad efectiva
4.3. Si f y g son Σ-efectivamente computables, entonces R(f,g) lo es.
Proof. Es dejada al lector
Nota importante: En los ejemplos anteriores y en todos los casos que manejaremos en esta primera etapa, en las aplicaciones del constructor de recursion primitiva (en sus cuatro formas) las funciones iniciales seran Σ-totales (es decir S1=...=Sn=ω y L1=...=Lm=Σ∗). Mas adelante veremos aplicaciones con funciones no Σ-totales.
Ahora haremos el caso en el que la funcion definida recursivamente tiene imagen contenida en Σ∗. Es claro que entonces f y g tambien deberan tener imagen contenida en Σ∗. El unico detalle a tener en cuenta en la definicion de este caso es que si solo hicieramos estos cambios y pusieramos las mismas ecuaciones la funcion g no resultaria Σ-mixta en general. Para que la g de la recursion siga siendo Σ-mixta deberemos modificar levemente su dominio en relacion al caso ya hecho
Supongamos Σ es un alfabeto finito. Sean f:S1×...×Sn×L1×...×Lm→Σ∗g:ω×S1×...×Sn×L1×...×Lm×Σ∗→Σ∗ con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ conjuntos no vacios. Definamos R(f,g):ω×S1×...×Sn×L1×...×Lm→Σ∗ de la siguiente manera
(1) R(f,g)(0,→x,→α)=f(→x,→α)
(2) R(f,g)(t+1,→x,→α)=g(t,→x,→α,R(f,g)(t,→x,→α))
Diremos que R(f,g) es obtenida por recursion primitiva a partir de f y g. Notese que cuando m=n=0, se tiene que Df={◊} y (1) y (2) se transforman en
(1) R(f,g)(0)=f(◊)
(2) R(f,g)(t+1)=g(t,R(f,g)(t))
Veamos algunos ejemplos
(E1) Tomemos f=C0,1ε y g=λαβ[αβ]∘[p1,23,p1,22]. De la definicion de R(f,g), obtenemos que R(f,g)(0,α1)=C0,1ε(α1)=εR(f,g)(t+1,α1)=λαβ[αβ]∘[p1,23,p1,22](t,α1,R(f,g)(t,α1))=R(f,g)(t,α1)α1 Es facil notar que la unica funcion que cumple estas dos ecuaciones es λtα1[α1t], lo cual implica que λtα1[α1t]=R(C0,1ε,λαβ[αβ]∘[p1,23,p1,22])
(E2) Sean f=C0,0ε y g=p2,02. De la definicion de R(f,g), obtenemos que R(f,g)(0)=C0,0ε(◊)=εR(f,g)(t+1)=p2,02(t,R(f,g)(t))=R(f,g)(t) Es facil notar que la unica funcion que cumple estas dos ecuaciones es C1,0ε lo cual implica que C1,0ε=R(C0,0ε,p2,02)
La prueba del siguiente lema es completamente analoga a la del lema anterior que fue dejada como ejercicio.
4.4. Si f y g son Σ-efectivamente computables, entonces R(f,g) lo es.
Ya vimos dos casos de recursion donde el parametro que comanda la recursion es numerico. Daremos a continuacion un ejemplo de recursion en el cual el parametro principal es alfabetico. Sea Σ={%,@,?} y consideremos las siguientes ecuaciones:
(1) R(ε)=15
(2) R(α%)=R(α)+1
(3) R(α@)=R(α).5
(4) R(α?)=R(α)20
Notese que las ecuaciones anteriores determinan una funcion R:Σ∗→ω. Esto es ya que R en ε debe valer 15 y sabiendo esto las ecuaciones (2), (3) y (4) (con α=ε) nos dicen que R(%)=16R(@)=75R(?)=1520 por lo cual podemos aplicarlas nuevamente a dichas ecuaciones (con α∈{%,@,?}) para calcular R en todas las palabras de longitud 2; y asi sucesivamente.
Daremos otro ejemplo un poco mas complicado para seguir aproximandonos al caso general. Nuevamente supongamos que Σ={%,@,?} y supongamos tenemos una funcion f:ω×Σ∗→ω y tres funciones G%:ω×ω×Σ∗×Σ∗→ωG@:ω×ω×Σ∗×Σ∗→ωG?:ω×ω×Σ∗×Σ∗→ω Entonces hay una unica funcion R:ω×Σ∗×Σ∗→ω la cual cumple las siguientes ecuaciones
(1) R(x1,α1,ε)=f(x1,α1)
(2) R(x1,α1,α%)=G%(R(x1,α1,α),x1,α1,α)
(3) R(x1,α1,α@)=G@(R(x1,α1,α),x1,α1,α)
(4) R(x1,α1,α?)=G?(R(x1,α1,α),x1,α1,α)
(Justifique que las ecuaciones anteriores determinan a la funcion R.)
El ejemplo anterior nos muestra que para hacer recursion sobre parametro alfabetico nos hace falta "una funcion g por cada simbolo de Σ". Esto motiva la siguiente definicion. Dado un alfabeto Σ, una familia Σ-indexada de funciones sera una funcion G tal que DG=Σ y para cada a∈DG se tiene que G(a) es una funcion. Algunos ejemplos:
(E1) Sea G dada por G:{◻,%,▴}→{Suc,Pred}◻→Suc%→Suc▴→Pred Claramente G es una familia {◻,%,▴}-indexada de funciones. Notar que G={(◻,Suc),(%,Suc),(▴,Pred)} Se tiene tambien por ejemplo que G(%)=Suc por lo cual tambien es cierto que G(%)(22)=23, etc.
(E2) Si Σ es un alfabeto no vacio, la funcion G:Σ→{f:f es una funcion de Σ∗ en Σ∗}a→da es una familia Σ-indexada de funciones. Notar que G={(a,da):a∈Σ}
(E3) ∅ es una flia ∅-indexada de funciones
Si G es una familia Σ-indexada de funciones, entonces para a∈Σ, escribiremos Ga en lugar de G(a). Ahora sí, nuestro caso de recursion primitiva. Sea f:S1×...×Sn×L1×...×Lm→ω con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ conjuntos no vacios y sea G una familia Σ-indexada de funciones tal que Ga:ω×S1×...×Sn×L1×...×Lm×Σ∗→ω para cada a∈Σ. Definamos R(f,G):S1×...×Sn×L1×...×Lm×Σ∗→ω de la siguiente manera
(1) R(f,G)(→x,→α,ε)=f(→x,→α)
(2) R(f,G)(→x,→α,αa)=Ga(R(f,G)(→x,→α,α),→x,→α,α)
Diremos que R(f,G) es obtenida por recursion primitiva a partir de f y G. Notese que cuando m=n=0, se tiene que Df={◊} y (1) y (2) se transforman en
(1) R(f,G)(ε)=f(◊)
(2) R(f,G)(αa)=Ga(R(f,G)(α),α)
4.5. Si f y cada Ga son Σ-efectivamente computables, entonces R(f,G) lo es.
Proof. Es dejada al lector
Supongamos Σ es un alfabeto finito. Sea f:S1×...×Sn×L1×...×Lm→Σ∗ con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ conjuntos no vacios y sea G una familia Σ-indexada de funciones tal que Ga:S1×...×Sn×L1×...×Lm×Σ∗×Σ∗→Σ∗ para cada a∈Σ. Definamos R(f,G):S1×...×Sn×L1×...×Lm×Σ∗→Σ∗ de la siguiente manera
(1) R(f,G)(→x,→α,ε)=f(→x,→α)
(2) R(f,G)(→x,→α,αa)=Ga(→x,→α,α,R(f,G)(→x,→α,α)).
Diremos que R(f,G) es obtenida por recursion primitiva a partir de f y G. Notese que cuando m=n=0, se tiene que Df={◊} y (1) y (2) se transforman en
(1) R(f,G)(ε)=f(◊)
(2) R(f,G)(αa)=Ga(α,R(f,G)(α))
La prueba del siguiente lema es completamente analoga a la del lema anterior que fue dejada como ejercicio.
4.6. Si f y cada Ga son Σ-efectivamente computables, entonces R(f,G) lo es.
Intuitivamente hablando una funcion es Σ-recursiva primitiva si se puede obtener de las iniciales usando los constructores de composicion y recursion primitiva. Daremos ahora una definicion matematica de este concepto. Definamos los conjuntos PRΣ0⊆PRΣ1⊆PRΣ2⊆...⊆PRΣ de la siguiente manera PRΣ0={Suc,Pred,C0,00,C0,0ε}∪{da:a∈Σ}∪{pn,mj:1≤j≤n+m}PRΣk+1=PRΣk∪{f∘[f1,...,fr]:f,f1,...,fr∈PRΣk, r≥1}∪{R(f,G):R(f,G) esta definida y {f}∪{Ga:a∈Σ}⊆PRΣk}∪{R(f,g):R(f,g) esta definida y f,g∈PRΣk}PRΣ=⋃k≥0PRΣk Una funcion es llamada Σ-recursiva primitiva (Σ-p.r.) si pertenece a PRΣ.
4.3. Si f∈PRΣ, entonces f es Σ-efectivamente computable.
Proof. Dejamos al lector la prueba por induccion en k de que si f∈PRΣk, entonces f es Σ-efectivamente computable, la cual sale en forma directa usando los lemas anteriores que garantizan que los constructores de composicion y recursion primitiva preservan la computabilidad efectiva
En los siguientes cuatro lemas se prueba bien formalmente que varias funciones bien conocidas son Σ-recursivas primitivas.
4.7. Sea Σ un alfabeto finito.
(1) ∅∈PRΣ.
(2) λxy[x+y]∈PRΣ.
(3) λxy[x.y]∈PRΣ.
(4) λx[x!]∈PRΣ.
Proof. (1) Notese que ∅=Pred∘C0,00∈PRΣ1
(2) Notar que λxy[x+y](0,x1)=x1=p1,01(x1)λxy[x+y](t+1,x1)=λxy[x+y](t,x1)+1=(Suc∘p3,01)(λxy[x+y](t,x1),t,x1) lo cual implica que λxy[x+y]=R(p1,01,Suc∘p3,01)∈PRΣ2.
(3) Primero note que C1,00(0)=C0,00(◊)C1,00(t+1)=C1,00(t) lo cual implica que C1,00=R(C0,00,p2,01)∈PRΣ1. Tambien note que λtx[t.x]=R(C1,00,λxy[x+y]∘[p3,01,p3,03]), lo cual por (2) implica que λtx[t.x]∈PRΣ4.
(4) Note que λx[x!](0)=1=C0,01(◊)λx[x!](t+1)=λx[x!](t).(t+1), lo cual implica que λx[x!]=R(C0,01,λxy[x.y]∘[p2,01,Suc∘p2,02]). Ya que C0,01= Suc∘C0,00, tenemos que C0,01∈PRΣ1. Por (3), tenemos que λxy[x.y]∘[p2,01,Suc∘p2,02]∈PRΣ5, obteniendo que λx[x!]∈PRΣ6.
Ahora consideraremos dos funciones las cuales son obtenidas naturalmente por recursion primitiva sobre variable alfabetica.
4.8. Supongamos Σ es un alfabeto finito.
(a) λαβ[αβ]∈PRΣ
(b) λα[|α|]∈PRΣ
Proof. (a) Ya que λαβ[αβ](α1,ε)=α1=p0,11(α1)λαβ[αβ](α1,αa)=da(λαβ[αβ](α1,α)), a∈Σ tenemos que λαβ[αβ]=R(p0,11,G), donde Ga=da∘p0,33, para cada a∈Σ.
(b) Ya que λα[|α|](ε)=0=C0,00(◊)λα[|α|](αa)=λα[|α|](α)+1 tenemos que λα[|α|]=R(C0,00,G), donde Ga= Suc∘p1,11, para cada a∈Σ..
4.9. Sea Σ un alfabeto finito. Entonces Cn,mk,Cn,mα∈PRΣ, para cada n,m,k≥0 y α∈Σ∗.
Proof. Note que C0,0k+1= Suc∘C0,0k, lo cual implica C0,0k∈PRΣk, para k≥0. Tambien note que C0,0αa=da∘C0,0α, lo cual dice que C0,0α∈PRΣ, para α∈Σ∗. Para ver que C0,1k∈PRΣ notar que C0,1k(ε)=k=C0,0k(◊)C0,1k(αa)=C0,1k(α)=p1,11(C0,1k(α),α) lo cual implica que C0,1k=R(C0,0k,G), con Ga=p1,11, a∈Σ. En forma similar podemos ver que C1,0k,C1,0α,C0,1α∈PRΣ. Supongamos ahora que m>0. Entonces Cn,mk=C0,1k∘pn,mn+1Cn,mα=C0,1α∘pn,mn+1 de lo cual obtenemos que Cn,mk,Cn,mα∈PRΣ. El caso n>0 es similar.
4.10. Sea Σ un alfabeto finito.
(a) λxy[xy]∈PRΣ.
(b) λtα[αt]∈PRΣ.
Proof. (a) Note que λtx[xt]=R(C1,01,λxy[x.y]∘[p3,01,p3,03])∈PRΣ. O sea que λxy[xy]=λtx[xt]∘[p2,02,p2,01]∈PRΣ.
(b) Note que λtα[αt]=R(C0,1ε,λαβ[αβ]∘[p1,23,p1,22])∈PRΣ.
Ahora probaremos que si Σ es no vacio, entonces las biyeciones naturales entre Σ∗ y ω, dadas en el Lema 2.3, son Σ-p.r..
4.11. Si ≤ es un orden total sobre un alfabeto no vacio Σ, entonces s≤, #≤ y ∗≤ pertenecen a PRΣ
Proof. Supongamos Σ={a1,...,ak} y ≤ es dado por a1<...<ak. Ya que s≤(ε)=a1s≤(αai)=αai+1, para i<ks≤(αak)=s≤(α)a1 tenemos que s≤=R(C0,0a1,G), donde Gai=dai+1∘p0,21, para i=1,...,k−1 y Gak=da1∘p0,22. O sea que s≤∈PRΣ. Ya que ∗≤(0)=ε∗≤(t+1)=s≤(∗≤(t)) podemos ver que ∗≤∈PRΣ. Ya que #≤(ε)=0#≤(αai)=#≤(α).k+i, para i=1,...,k, tenemos que #≤=R(C0,00,G), donde Gai=λxy[x+y]∘[λxy[x.y]∘[p1,11,C1,1k],C1,1i], para i=1,...,k. O sea que #≤∈PRΣ.
Dados x,y∈ω, definamos x˙−y=max(x−y,0).
4.12.
(a) λxy[x˙−y]∈PRΣ.
(b) λxy[max(x,y)]∈PRΣ.
(c) λxy[x=y]∈PRΣ.
(d) λxy[x≤y]∈PRΣ.
(e) λαβ[α=β]∈PRΣ
Proof. (a) Primero notar que λx[x˙−1]=R(C0,00,p2,02)∈PRΣ. Tambien note que λtx[x˙−t]=R(p1,01,λx[x˙−1]∘p3,01)∈PRΣ. O sea que λxy[x˙−y]=λtx[x˙−t]∘[p2,02,p2,01]∈PRΣ.
(b) Note que λxy[max(x,y)]=λxy[x+(y˙−x)].
(c) Note que λxy[x=y]=λxy[1˙−((x˙−y)+(y˙−x))].
(d) Note que λxy[x≤y]=λxy[1˙−(x˙−y)].
(e) Sea ≤ un orden total sobre Σ. Ya que α=β sii #≤(α)=#≤(β) tenemos que λαβ[α=β]=λxy[x=y]∘[#≤∘p0,21,#≤∘p0,22] lo cual nos dice que λαβ[α=β] es Σ-p.r.
Dados predicados P:S⊆ωn×Σ∗m→ω y Q:S⊆ωn×Σ∗m→ω, con el mismo dominio, definamos nuevos predicados (P∨Q), (P∧Q) y ¬P de la siguiente manera (P∨Q):S→ω(→x,→α)→{1si P(→x,→α)=1 o Q(→x,→α)=10caso contrario(P∧Q):S→ω(→x,→α)→{1si P(→x,→α)=1 y Q(→x,→α)=10caso contrario¬P:S→ω(→x,→α)→{1si P(→x,→α)=00si P(→x,→α)=1
4.13. Si P:S⊆ωn×Σ∗m→ω y Q:S⊆ωn×Σ∗m→ω son predicados Σ-p.r., entonces (P∨Q), (P∧Q) y ¬P lo son tambien.
Proof. Note que ¬P=λxy[x˙−y]∘[Cn,m1,P](P∧Q)=λxy[x.y]∘[P,Q](P∨Q)=¬(¬P∧¬Q).
Un conjunto Σ-mixto S⊆ωn×Σ∗m es llamado Σ-recursivo primitivo si su funcion caracteristica χωn×Σ∗mS es Σ-p.r.. (Notese que χωn×Σ∗mS es el predicado λ→x→α[(→x,→α)∈S].)
4.14. Si S1,S2⊆ωn×Σ∗m son Σ-p.r., entonces S1∪S2, S1∩S2 y S1−S2 lo son.
Proof. Note que χωn×Σ∗mS1∪S2=(χωn×Σ∗mS1∨χωn×Σ∗mS2)χωn×Σ∗mS1∩S2=(χωn×Σ∗mS1∧χωn×Σ∗mS2)χωn×Σ∗mS1−S2=λxy[x˙−y]∘[χωn×Σ∗mS1,χωn×Σ∗mS2]
4.1. Si S⊆ωn×Σ∗m es finito, entonces S es Σ-p.r..
Proof. Si S=∅, entonces es claro que S es Σ-p.r.. Probaremos ahora el lema para el caso en que S tiene un solo elemento. Supongamos entonces S={(z1,...,zn,γ1,...,γm)}. Note que χωn×Σ∗mS es el siguiente predicado (χω{z1}∘pn,m1∧...∧χω{zn}∘pn,mn∧χΣ∗{γ1}∘pn,mn+1∧...∧χΣ∗{γm}∘pn,mn+m). Ya que los predicados χω{zi}=λxy[x=y]∘[p1,01,C1,0zi]χΣ∗{γi}=λαβ[α=β]∘[p0,11,C0,1γi] son Σ-p.r., el Lema 4.13 (aplicado (n+m)−1 veces), implica que χωn×Σ∗mS es Σ-p.r.. Cuando S tiene mas de un elemento, ya que entonces es la union de una cantidad finita de conjuntos de un solo elemento, se puede aplicar el Lema 4.14 (|S|−1 veces) para obtener que S es Σ-p.r..
El siguiente lema caracteriza cuando un conjunto rectangular es Σ-p.r..
4.15. Supongamos S1,...,Sn⊆ω, L1,...,Lm⊆Σ∗ son conjuntos no vacios. Entonces S1×...×Sn×L1×...×Lm es Σ-p.r. sii S1,...,Sn,L1,...,Lm son Σ-p.r.
Proof. (⇒) Veremos por ejemplo que L1 es Σ-p.r.. Sea (z1,...,zn,ζ1,...,ζm) un elemento fijo de S1×...×Sn×L1×...×Lm. Note que α∈L1 sii (z1,...,zn,α,ζ2,...,ζm)∈S1×...×Sn×L1×...×Lm, lo cual implica que χΣ∗L1=χωn×Σ∗mS1×...×Sn×L1×...×Lm∘[C0,1z1,...,C0,1zn,p0,11,C0,1ζ2,...,C0,1ζm] (⇐) Note que χωn×Σ∗mS1×...×Sn×L1×...×Lm es el predicado (χωS1∘pn,m1∧...∧χωSn∘pn,mn∧χΣ∗L1∘pn,mn+1∧...∧χΣ∗Lm∘pn,mn+m).
Dada una funcion f y un conjunto S⊆Df, usaremos f|S para denotar la restriccion de f al conjunto S, i.e. f|S=f∩(S×If). Notese que f|S es la funcion dada por Df|S=S \ \ \ y \ \ f|S(e)=f(e), para cada e∈S
4.16. Sean n,m∈ω y O∈{ω,Σ∗}. Supongamos f:Df⊆ωn×Σ∗m→O es Σ-p.r.. Si S⊆Df es Σ-p.r., entonces f|S es Σ-p.r..
Proof. Supongamos O=Σ∗. Entonces f|S=λxα[αx]∘[Suc∘Pred∘χωn×Σ∗mS,f] lo cual nos dice que f|S es Σ-p.r.. El caso O=ω es similar usando λxy[xy] en lugar de λxα[αx].
Usando el lema anterior en combinacion con el Lema 4.13 podemos ver que muchos predicados usuales son Σ-p.r.. Por ejemplo sea P=λxαβγ[x=|γ|∧α=γPred(|β|)]. Notese que DP=ω×Σ∗×(Σ∗−{ε})×Σ∗ es Σ-p.r. ya que χω×Σ∗3DP=¬λαβ[α=β]∘[p1,33,C1,3ε] Tambien note que los predicados λxαβγ[x=|γ|]λxαβγ[α=γPred(|β|)] son Σ-p.r. ya que pueden obtenerse componiendo funciones Σ-p.r.. O sea que P es Σ-p.r. ya que P=(λxαβγ[x=|γ|]|DP∧λxαβγ[α=γPred(|β|)]).
4.17. Sean n,m∈ω y O∈{ω,Σ∗}. Si f:Df⊆ωn×Σ∗m→O es Σ-p.r., entonces existe una funcion Σ-p.r. ˉf:ωn×Σ∗m→O, tal que f=ˉf|Df.
Proof. Es facil ver por induccion en k que el enunciado se cumple para cada f∈PRΣk
Ahora podemos probar el siguiente importante resultado
4.4. Un conjunto S es Σ-p.r. sii S es el dominio de alguna funcion Σ-p.r..
Proof. Supongamos que S⊆ωn×Σ∗m.
(⇒) Note que S=DPred∘χωn×Σ∗mS.
(⇐) Probaremos por induccion en k que DF es Σ-p.r., para cada F∈PRΣk. El caso k=0 es facil. Supongamos el resultado vale para un k fijo y supongamos F∈PRΣk+1. Veremos entonces que DF es Σ-p.r.. Hay varios casos. Consideremos primero el caso en que F=R(f,g), donde f:S1×...×Sn×L1×...×Lm→Σ∗g:ω×S1×...×Sn×L1×...×Lm×Σ∗→Σ∗, con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ conjuntos no vacios y f,g∈PRΣk. Notese que por definicion de R(f,g), tenemos que DF=ω×S1×...×Sn×L1×...×Lm. Por hipotesis inductiva tenemos que Df=S1×...×Sn×L1×...×Lm es Σ-p.r., lo cual por el Lema 4.15 nos dice que los conjuntos S1,...,Sn, L1,...,Lm son Σ-p.r.. Ya que ω es Σ-p.r., el Lema 4.15 nos dice que DF es Σ-p.r..
Los otros casos de recursion primitiva son dejados al lector.
Supongamos ahora que F=g∘[g1,...,gr] con g,g1,...,gr∈PRΣk. Si F=∅, entonces es claro que DF=∅ es Σ-p.r.. Supongamos entonces que F no es la funcion ∅. Tenemos entonces que r es de la forma n+m y g:Dg⊆ωn×Σ∗m→Ogi:Dgi⊆ωk×Σ∗l→ω, i=1,...,ngi:Dgi⊆ωk×Σ∗l→Σ∗,i=n+1,...,n+m con O∈{ω,Σ∗} y k,l∈ω. Por Lema 4.17, hay funciones Σ-p.r. ˉg1,...,ˉgn+m las cuales son Σ-totales y cumplen gi=ˉgi|Dgi, para i=1,...,n+m. Por hipotesis inductiva los conjuntos Dg, Dgi, i=1,...,n+m, son Σ-p.r. y por lo tanto S=n+m⋂i=1Dgi lo es. Notese que χωk×Σ∗lDF=(χωn×Σ∗mDg∘[ˉg1,...,ˉgn+m]∧χωk×Σ∗lS) lo cual nos dice que DF es Σ-p.r..
Una observacion interesante es que si fi:Dfi→O, i=1,...,k, son funciones tales que Dfi∩Dfj=∅ para i≠j, entonces f1∪...∪fk es la funcion Df1∪...∪Dfk→Oe→{f1(e)si e∈Df1⋮⋮fk(e)si e∈Dfk
4.18 (Division por casos para funciones Σ-p.r.). Sean n,m∈ω y O∈{ω,Σ∗}. Supongamos fi:Dfi⊆ωn×Σ∗m→O, i=1,...,k, son funciones Σ-p.r. tales que Dfi∩Dfj=∅ para i≠j. Entonces f1∪...∪fk es Σ-p.r..
Proof. Supongamos O=Σ∗ y k=2. Sean ˉfi:ωn×Σ∗m→Σ∗,i=1,2, funciones Σ-p.r. tales que ˉfi|Dfi=fi, i=1,2 (Lema 4.17). Por Lema 4.4 los conjuntos Df1 y Df2 son Σ-p.r. y por lo tanto lo es Df1∪Df2. Ya que f1∪f2=(λαβ[αβ]∘[λxα[αx]∘[χωn×Σ∗mDf1,ˉf1],λxα[αx]∘[χωn×Σ∗mDf2,ˉf2]])|Df1∪Df2 tenemos que f1∪f2 es Σ-p.r..
El caso k>2 puede probarse por induccion ya que f1∪...∪fk=(f1∪...∪fk−1)∪fk.
4.2. Supongamos f es una funcion Σ-mixta cuyo dominio es finito. Entonces f es Σ-p.r..
Proof. Supongamos f:Df⊆ωn×Σ∗m→O, con Df={e1,...,ek}. Por el Corolario 4.1, cada {ei} es Σ-p.r. por lo cual el Lema 4.16 nos dice que Cn,mf(ei)|{ei} es Σ-p.r.. O sea que f=Cn,mf(e1)|{e1}∪...∪Cn,mf(ek)|{ek} es Σ-p.r..
Recordemos que dados i∈ω y α∈Σ∗, definimos [α]i={i-esimo elemento de αsi 1≤i≤|α|εcaso contrario
4.19. λiα[[α]i] es Σ-p.r..
Proof. Note que i=ε[αa]i={[α]isi i≠|α|+1asi i=|α|+1 lo cual dice que λiα[[α]i]=R(C1,0ε,G), donde Ga:ω×Σ∗×Σ∗→Σ∗ es dada por Ga(i,α,ζ)={ζsi i≠|α|+1asi i=|α|+1 O sea que solo resta probar que cada Ga es Σ-p.r.. Primero note que los conjuntos S1={(i,α,ζ)∈ω×Σ∗×Σ∗:i≠|α|+1}S2={(i,α,ζ)∈ω×Σ∗×Σ∗:i=|α|+1} son Σ-p.r. ya que χω×Σ∗×Σ∗S1=λxy[x≠y]∘[p1,21,Suc∘λα[|α|]∘p1,22]χω×Σ∗×Σ∗S2=λxy[x=y]∘[p1,21,Suc∘λα[|α|]∘p1,22] Ya que Ga=p1,23|S1∪C1,2a|S2 el Lema 4.18 nos dice que Ga es Σ-p.r., para cada a∈Σ.
Sea Σ un alfabeto finito. Sea f:ω×S1×...×Sn×L1×...×Lm→ω, con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ no vacios. Para x,y∈ω y (→x,→α)∈S1×...×Sn×L1×...×Lm, definamos t=y∑t=xf(t,→x,→α)={0si x>yf(x,→x,→α)+f(x+1,→x,→α)+...+f(y,→x,→α)si x≤yt=y∏t=xf(t,→x,→α)={1si x>yf(x,→x,→α).f(x+1,→x,→α)....f(y,→x,→α)si x≤y En forma similar, cuando If⊆Σ∗, definamos t=y⊂t=xf(t,→x,→α)={εsi x>yf(x,→x,→α)f(x+1,→x,→α)....f(y,→x,→α)si x≤y Note que, en virtud de la definicion anterior, el dominio de las funciones λxy→x→α[t=y∑t=xf(t,→x,→α)] λxy→x→α[t=y∏t=xf(t,→x,→α)] λxy→x→α[⊂t=yt=xf(t,→x,→α)] es ω×ω×S1×...×Sn×L1×...×Lm.
4.20. Sea Σ un alfabeto finito.
(a) Si f:ω×S1×...×Sn×L1×...×Lm→ω es Σ-p.r., con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ no vacios, entonces las funciones λxy→x→α[∑t=yt=xf(t,→x,→α)] y λxy→x→α[∏t=yt=xf(t,→x,→α)] son Σ-p.r.
(b) Si f:ω×S1×...×Sn×L1×...×Lm→Σ∗ es Σ-p.r., con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ no vacios, entonces la funcion λxy→x→α[⊂t=yt=xf(t,→x,→α)] es Σ-p.r.
Proof. (a) Sea G=λtx→x→α[∑i=ti=xf(i,→x,→α)]. Ya que λxy→x→α[i=y∑i=xf(i,→x,→α)]=G∘[pn+2,m2,pn+2,m1,pn+2,m3,...,pn+2,mn+m+2] solo tenemos que probar que G es Σ-p.r.. Primero note que G(0,x,→x,→α)={0si x>0f(0,→x,→α)si x=0G(t+1,x,→x,→α)={0si x>t+1G(t,x,→x,→α)+f(t+1,→x,→α)si x≤t+1 O sea que si definimos h:ω×S1×...×Sn×L1×...×Lm→ω(x,→x,→α)→{0si x>0f(0,→x,→α)si x=0 g:ω3×S1×...×Sn×L1×...×Lm→ω(A,t,x,→x,→α)→{0si x>t+1A+f(t+1,→x,→α)si x≤t+1 tenemos que G=R(h,g). Es decir que solo nos falta probar que h y g son Σ-p.r.. Sean D1={(x,→x,→α)∈ω×S1×...×Sn×L1×...×Lm:x>0}D2={(x,→x,→α)∈ω×S1×...×Sn×L1×...×Lm:x=0}H1={(z,t,x,→x,→α)∈ω3×S1×...×Sn×L1×...×Lm:x>t+1}H2={(z,t,x,→x,→α)∈ω3×S1×...×Sn×L1×...×Lm:x≤t+1}. Notese que h=Cn+1,m0|D1∪λx→x→α[f(0,→x,→α)]|D2g=Cn+3,m0|H1∪λAtx→x→α[A+f(t+1,→x,→α)])|H2 Ya que f es Σ-p.r. y λx→x→α[f(0,→x,→α)]=f∘[Cn+1,m0,pn+1,m2,pn+1,m3,...,pn+1,mn+1+m]λAtx→x→α[A+f(t+1,→x,→α)])=λxy[x+y]∘[pn+3,m1,f∘[Suc∘pn+3,m2,pn+3,m4,...,pn+3,mn+3+m]] tenemos que λx→x→α[f(0,→x,→α)] y λAtx→x→α[A+f(t+1,→x,→α)]) son Σ-p.r..O sea que para probar que h y g son Σ-p.r.solo nos falta ver que los conjuntos D1,D2,H1,H2 son Σ-p.r.. y aplicar luego el Lema 4.16. Veamos que por ejemplo H1 lo es. Es decir debemos ver que χω3+n×Σ∗mH1 es Σ-p.r.. Ya que f es Σ-p.r. tenemos que Df=ω×S1×...×Sn×L1×...×Lm es Σ-p.r., lo cual por el Lema 4.15 nos dice que los conjuntos S1,...,Sn, L1,...,Lm son Σ-p.r.. Ya que ω es Σ-p.r., el Lema 4.15 nos dice que R=ω3×S1×...×Sn×L1×...×Lm es Σ-p.r.. Notese que χω3+n×Σ∗mH1=(χω3+n×Σ∗mR∧λztx→x→α[x>t+1]) por lo cual χω3+n×Σ∗mH1 es Σ-p.r. ya que es la conjuncion de dos predicados Σ-p.r.
Veamos un ejemplo de como se puede aplicar el lema anterior. Sea F=λyx1[∑t=yt=0(x1)t]. Es claro que DF=ω2. Para ver que F es Σ-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=λtx1[(x1)t]. Claramente f es Σ-p.r. por lo cual el lema anterior nos dice que G=λxyx1[t=y∑t=xf(t,x1)]=λxyx1[t=y∑t=x(x1)t] es Σ-p.r.. Claramente G no es la funcion F pero es en algun sentido "mas amplia" que F ya que tiene una variable mas y se tiene que F(y,x1)=G(0,y,x1), para cada y,x1∈ω. Es facil ver que F=G∘[C2,00,p2,01,p2,02] por lo cual F es Σ-p.r..
Ses P:S×S1×...×Sn×L1×...×Lm→ω un predicado, con S,S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ no vacios. Supongamos ˉS⊆S. Entonces la expresion Booleana (∀t∈ˉS)t≤xP(t,→x,→α) depende de las variables x,→x,→α y valdra 1 en una (1+n+m)-upla (x,→x,→α) cuando P(t,→x,→α) sea igual a 1 para cada t∈{u∈ˉS:u≤x}; y 0 en caso contrario. Tenemos entonces que el dominio del predicado λx→x→α[(∀t∈ˉS)t≤xP(t,→x,→α)] es ω×S1×...×Sn×L1×...×Lm. En forma analoga se define la forma de interpretar la expresion Booleana (∃t∈ˉS)t≤xP(t,→x,→α) Cabe destacar que λx→x→α[(∃t∈ˉS)t≤xP(t,→x,→α)]=¬λx→x→α[(∀t∈ˉS)t≤x¬P(t,→x,→α)]
Tambien podemos cuantificar sobre variable alfabetica. Sea P:S1×...×Sn×L1×...×Lm×L→ω un predicado, con S1,...,Sn⊆ω y L,L1,...,Lm⊆Σ∗ no vacios. Supongamos ˉL⊆L. Entonces la expresion Booleana (∀α∈ˉL)|α|≤xP(→x,→α,α) depende de las variables x,→x,→α y valdra 1 en una (1+n+m)-upla (x,→x,→α) cuando P(→x,→α,α) sea igual a 1 para cada α∈{β∈ˉL:|β|≤x}; y 0 en caso contrario. Tenemos entonces que el dominio del predicado λx→x→α[(∀α∈ˉL)|α|≤xP(→x,→α,α)] es ω×S1×...×Sn×L1×...×Lm. En forma analoga se define la forma de interpretar la expresion Booleana (∃α∈ˉL)|α|≤xP(→x,→α,α) Cabe destacar que λx→x→α[(∃α∈ˉL)|α|≤xP(→x,→α,α)]=¬λx→x→α[(∀α∈ˉL)|α|≤x¬P(→x,→α,α)]
4.21. Sea Σ un alfabeto finito.
(a) Sea P:S×S1×...×Sn×L1×...×Lm→ω un predicado Σ-p.r., con S,S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗ no vacios. Supongamos ˉS⊆S es Σ-p.r.. Entonces λx→x→α[(∀t∈ˉS)t≤xP(t,→x,→α)] y λx→x→α[(∃t∈ˉS)t≤xP(t,→x,→α)] son predicados Σ-p.r..
(b) Sea P:S1×...×Sn×L1×...×Lm×L→ω un predicado Σ-p.r., con S1,...,Sn⊆ω y L,L1,...,Lm⊆Σ∗ no vacios. Supongamos ˉL⊆L es Σ-p.r.. Entonces λx→x→α[(∀α∈ˉL)|α|≤xP(→x,→α,α)] y λx→x→α[(∃α∈ˉL)|α|≤xP(→x,→α,α)] son predicados Σ-p.r..
Proof. (a) Sea ˉP=P|ˉS×S1×...×Sn×L1×...×Lm∪C1+n,m1|(ω−ˉS)×S1×...×Sn×L1×...×Lm Notese que ˉP tiene dominio ω×S1×...×Sn×L1×...×Lm y es Σ-p.r.. Ya que λx→x→α[(∀t∈ˉS)t≤xP(t,→x,→α)]=λx→x→α[t=x∏t=0ˉP(t,→x,→α)]=λxy→x→α[t=y∏t=xˉP(t,→x,→α)]∘[C1+n,m0,p1+n,m1,...,p1+n,m1+n+m] el Lema 4.20 implica que λx→x→α[(∀t∈ˉS)t≤xP(t,→x,→α)] es Σ-p.r..
Ya que λx→x→α[(∃t∈ˉS)t≤xP(t,→x,→α)]=¬λx→x→α[(∀t∈ˉS)t≤x¬P(t,→x,→α)] tenemos que λx→x→α[(∃t∈ˉS)t≤xP(t,→x,→α)] es Σ-p.r.
(b) Haremos solo el caso del cuantificador ∀. Primero supongamos que Σ=∅. Ya que L,L1,...,Lm son no vacios, debera suceder que L=L1=...=Lm={ε}. Ya que ˉL⊆L, tenemos que ˉL=∅ o ˉL={ε}. Si ˉL=∅, entonces λx→x→α[(∀α∈ˉL)|α|≤xP(→x,→α,α)]=λx→x→α[1]=C1+n,m1 por lo cual es Σ-p.r.
Si ˉL={ε}, entonces λx→x→α[(∀α∈ˉL)|α|≤xP(→x,→α,α)]=λx→x→α[(P(→x,→α,ε)]=P∘[p1+n,m2,...,p1+n,m1+n+m,C1+n,mε,] por lo cual es Σ-p.r.
Ahora supongamos Σ es no vacio. Sea ≤ un orden total sobre Σ. Sea k el cardinal de Σ. Primero notese que
|α|≤x sii #≤(α)≤∑i=xι=1ki, cualesquiera sean x∈ω y α∈Σ∗
(queda como ejercicio probar (*). Sean #≤(L)={#≤(α):α∈L}#≤(ˉL)={#≤(α):α∈ˉL} Notese que χω#≤(L)=χΣ∗L∘∗≤χω#≤(ˉL)=χΣ∗ˉL∘∗≤ por lo cual #≤(L) y #≤(ˉL) son Σ-p.r.. Sea H=λt→x→α[P(→x,→α,∗≤(t))]. Notese que DH=#≤(L)×S1×...×Sn×L1×...×Lm y H es Σ-p.r.. O sea que por (a) tenemos que λx→x→α[(∀t∈#≤(ˉL))t≤xH(t,→x,→α)]=λx→x→α[(∀t∈#≤(ˉL))t≤xP(→x,→α,∗≤(t))] es Σ-p.r.. Llamemos Q al predicado λx→x→α[(∀t∈#≤(ˉL))t≤xP(→x,→α,∗≤(t))]. Tenemos que λx→x→α[(∀α∈ˉL)|α|≤xP(→x,→α,α)]=λx→x→α[(∀t∈#≤(ˉL))t≤∑i=xι=1kiP(→x,→α,∗≤(t))] (por (*))=Q∘[λx→x→α[i=x∑ι=1ki],p1+n,m1,...,p1+n,m1+n+m] Pero λx→x→α[i=x∑ι=1ki] es Σ-p.r. (ejercicio), lo cual nos dice que λx→x→α[(∀α∈ˉL)|α|≤xP(→x,→α,α)] lo es
OBSERVACION: La cuantificacion no acotada no preserva la propiedad de ser Σ-p.r.. Como veremos mas adelante si elejimos bien al predicado Σ-p.r. P, obtenemos que el predicado λ→x→α[(∃t∈ˉS)P(t,→x,→α)] no solo no es Σ-p.r. sino que tampoco es Σ-efectivamente computable (Teorema 4.15).
Algunos ejemplos en los cuales cuantificacion acotada se aplica naturalmente son dados a continuacion.
4.22. Sea Σ un alfabeto finito.
(a) El predicado λxy[x divide y] es Σ-p.r..
(b) El predicado λx[x es primo] es Σ-p.r..
(c) El predicado λαβ[α\ inicial β] es Σ-p.r..
Proof. (a) Sea P=λtx1x2[x2=t.x1]. Es claro que P es Σ-p.r.. El lema anterior nos dice que λxx1x2[(∃t∈ω)t≤xP(t,x1,x2)] es Σ-p.r.. Notese que x1 divide x2 si y solo si hay un t≤x2 tal que x2=t.x1. Esto nos dice que λx1x2[x1 divide x2]=λx1x2[(∃t∈ω)t≤x2P(t,x1,x2)] Pero λx1x2[(∃t∈ω)t≤x2P(t,x1,x2)]=λxx1x2[(∃t∈ω)t≤xP(t,x1,x2)]∘[p2,02,p2,01,p2,02] por lo cual λx1x2[x1 divide x2] es Σ-p.r.
(b) Ya que x es primo sii x>1∧((∀t∈ω)t≤xt=1∨t=x∨¬(t divide x)) 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 cuantificacion a partir de otros predicados, la variable cuantificada tiene una cota natural en terminos de las otras variables y entonces componiendo adecuadamente se lo puede presentar como un caso de cuantificacion acotada
Tal como fue explicado anteriormente, para obtener la clase de las funciones Σ-recursivas debemos agregar un nuevo constructor a los ya definidos de composicion y recursion primitiva, a saber el constructor de minimizacion. Tiene dos casos aunque solo usaremos el primero para la definicion de funcion Σ-recursiva.
Sea Σ un alfabeto finito y sea P:DP⊆ω×ωn×Σ∗m→ω un predicado. Dado (→x,→α)∈ωn×Σ∗m, cuando exista al menos un t∈ω tal que P(t,→x,→α)=1, usaremos mintP(t,→x,→α) para denotar al menor de tales t′s. Notese que la expresion mintP(t,→x,→α) esta definida solo para aquellas (n+m)-uplas (→x,→α) para las cuales hay al menos un t tal que se da P(t,→x,→α)=1. Dicho de otra forma, mintP(t,→x,→α) no estara definida cuando para cada t∈ω se de que (t,→x,→α) no pertenece a DP o P(t,→x,→α)=0. Otro detalle importante a tener en cuenta es que la expresion mintP(t,→x,→α) no depende de la variable t. Por ejemplo, las expresiones mintP(t,→x,→α) y miniP(i,→x,→α) son equivalentes en el sentido que estan definidas en las mismas (n+m)-uplas y cuando estan definidas asumen el mismo valor.
Definamos M(P)=λ→x→α[mintP(t,→x,→α)] Notese que DM(P)={(→x,→α)∈ωn×Σ∗m:(∃t∈ω) P(t,→x,→α)}M(P)(→x,→α)=mintP(t,→x,→α), para cada (→x,→α)∈DM(P) Diremos que M(P) se obtiene por minimizacion de variable numerica a partir de P.
Veamos un par de ejemplos:
(E1) Tomemos P=λtx1[t2=x1]. Tenemos que: DM(P)={x1∈ω:(∃t∈ω) P(t,x1)}={x1∈ω:(∃t∈ω) t2=x1} Es decir el dominio de M(P) es el conjunto de los cuadrados. Ademas para cada x1∈DM(P) tenemos que M(P)(x1)=mintP(t,x1)=mint(t2=x1) por lo cual M(P)(x)=√x, para cada x∈DM(P).
(E2) Recordemos que dados x1,x2∈ω, con x2 no nulo, el cociente de dividir x1 por x2 se define como el maximo elemento del conjunto {t∈ω:t.x2≤x1}. Sea Q:ω×N→ω(x1,x2)→cociente de dividir x1 por x2 Sea P=λtx1x2[x1<t.x2]. Notar que DM(P)={(x1,x2)∈ω2:(∃t∈ω)P(t,x1,x2)=1}={(x1,x2):(∃t∈ω)x1<t.x2}=ω×N Ademas si (x1,x2)∈ω×N, es facil de probar que mint x1<t.x2=Q(x1,x2)+1 por lo que M(P)=Suc∘Q. Si quisieramos encontrar un predicado P′ tal que M(P′)=Q, entonces podemos tomar P′=λtx1x2[x1<(t+1).x2] y con un poco de concentracion nos daremos cuenta que M(P′)=Q. De todas maneras hay una forma mas facil de hacerlo y es tomando P′ de tal forma que para cada (x1,x2)∈DQ se de que Q(x1,x2)= unico t∈ω tal que P′(t,x1,x2) Por ejemplo se puede tomar P′=λtx1x2[x1≥t.x2 y x1<(t+1).x2] que dicho sea de paso es justo la definicion de cociente dada en la escuela primaria. Dejamos al lector corroborar que M(P′)=Q, para este ultimo P′.
Tal como lo vimos recien muchas veces que querramos encontrar un predicado P tal que M(P) sea igual a una funcion dada f, sera mas facil encontrar un P el cual cumpla f(→x,→α)= unico t∈ω tal que P(t,→x,→α) es decir un predicado P que caracterice al valor que toma f. Enunciamos esto en forma de regla.
REGLA U: Si tenemos una funcion f:Df⊆ωn×Σ∗m→ω y buscamos un predicado P tal que f=M(P) muchas veces es util tratar de diseñar P de manera que para cada (→x,→α)∈Df se de que f(→x,→α)= unico t∈ω tal que P(t,→x,→α)
4.23. Si P:DP⊆ω×ωn×Σ∗m→ω es un predicado Σ-efectivamente computable y DP es Σ-efectivamente computable, entonces la funcion M(P) es Σ-efectivamente computable.
Proof. Ejercicio
Lamentablemente si quitamos la hipotesis en el lema anterior de que DP sea Σ-efectivamente computable, el lema resulta falso. Mas adelante veremos un contraejemplo basado en la Tesis de Church (Proposicion 4.16). Por el momento el lector puede ejercitar su comprencion del tema convenciendose de que aun teniendo un procedimiento efectivo que compute a un predicado P:DP⊆ω×ωn×Σ∗m→ω, no es claro como construir un procedimiento efectivo que compute a M(P).
Con este nuevo constructor de funciones estamos en condiciones de definir la clase de las funciones Σ-recursivas. Definamos los conjuntos RΣ0⊆RΣ1⊆RΣ2⊆...⊆RΣ de la siguiente manera RΣ0=PRΣ0RΣk+1=RΣk∪{f∘[f1,...,fn]:f,f1,...,fr∈RΣk, r≥1}∪{R(f,G):R(f,G) esta definida y {f}∪{Ga:a∈Σ}⊆RΣk}∪{R(f,g):R(f,g) esta definida y f,g∈RΣk}∪{M(P):P es un predicado Σ-total y P∈RΣk}RΣ=⋃k≥0RΣk Una funcion f es llamada Σ-recursiva si pertenece a RΣ. Cabe destacar que aunque M(P) fue definido para predicados no necesariamente Σ-totales, en la definicion de los conjuntos RΣk, nos restringimos al caso en que P es Σ-total.
Notese que PRΣk⊆RΣk, para cada k∈ω, por lo cual PRΣ⊆RΣ. Por supuesto el modelo de Godel seria incorrecto si no fuera cierto el siguiente resultado.
4.5 (Leibniz vence a Godel). Si f∈RΣ, entonces f es Σ-efectivamente computable.
Proof. Dejamos al lector la prueba por induccion en k de que si f∈RΣk, entonces f es Σ-efectivamente computable.
Daremos sin prueba el siguiente conceptualmente importante resultado.
4.6. Sea Σ un alfabeto finito. Entonces no toda funcion Σ-recursiva es Σ-p.r.
Este resultado no es facil de probar. Mas adelante (Proposicion 4.13) veremos ejemplos naturales de funciones Σ-recursivas que no son Σ-p.r.. Otro ejemplo natural es la famosa funcion de Ackermann.
Aunque no siempre que P∈RΣ, tendremos que M(P)∈RΣ (Proposicion 4.16), el siguiente lema nos garantiza que este es el caso cuando P∈PRΣ y ademas da condiciones para que M(P) sea Σ-p.r..
4.24. Sean n,m≥0. Sea P:DP⊆ω×ωn×Σ∗m→ω un predicado Σ-p.r.. Entonces
(a) M(P) es Σ-recursiva.
(b) Si hay una funcion Σ-p.r. f:ωn×Σ∗m→ω tal que M(P)(→x,→α)=mintP(t,→x,→α)≤f(→x,→α), para cada (→x,→α)∈DM(P), entonces M(P) es Σ-p.r..
Proof. (a) Sea ˉP=P∪Cn+1,m0|(ωn+1×Σ∗m)−DP. Note que ˉP es Σ-p.r. (por que?). Veremos a continuacion que M(P)=M(ˉP). Notese que {t∈ω:P(t,→x,→α)=1}={t∈ω:ˉP(t,→x,→α)=1} Esto claramente dice que DM(P)=DM(ˉP) y que M(P)(→x,→α)=M(ˉP)(→x,→α), para cada (→x,→α)∈DM(P)., por lo cual M(P)=M(ˉP).
Veremos entonces que M(ˉP) es Σ-recursiva. Sea k tal que ˉP∈PRΣk. Ya que ˉP es Σ-total y ˉP∈PRΣk⊆RΣk, tenemos que M(ˉP)∈RΣk+1 y por lo tanto M(ˉP)∈RΣ.
(b) Ya que M(P)=M(ˉP), basta con probar que M(ˉP) es Σ-p.r. Primero veremos que DM(ˉP) es un conjunto Σ-p.r.. Notese que χωn×Σ∗mDM(ˉP)=λ→x→α[(∃t∈ω)t≤f(→x,→α)ˉP(t,→x,→α)] lo cual nos dice que χωn×Σ∗mDM(ˉP)=λx→x→α[(∃t∈ω)t≤xˉP(t,→x,→α)]∘[f,pn,m1,...,pn,mn+m] Pero el Lema 4.21 nos dice que λx→x→α[(∃t∈ω)t≤xˉP(t,→x,→α)] es Σ-p.r. por lo cual tenemos que χωn×Σ∗mDM(ˉP) lo es.
Sea P1=λt→x→α[ˉP(t,→x,→α)∧(∀j∈ω)j≤tj=t∨¬ˉP(j,→x,→α)] Note que P1 es Σ-total. Dejamos al lector usando lemas anteriores probar que P1 es Σ-p.r. Ademas notese que para (→x,→α)∈ωn×Σ∗m se tiene que P1(t,→x,→α)=1 si y solo si (→x,→α)∈DM(ˉP) y t=M(ˉP)(→x,→α) Esto nos dice que M(ˉP)=(λ→x→α[f(→x,→α)∏t=0tP1(t,→x,→α)])|DM(ˉP) por lo cual para probar que M(ˉP) es Σ-p.r. solo nos resta probar que F=λ→x→α[f(→x,→α)∏t=0tP1(t,→x,→α)] lo es. Pero F=λxy→x→α[y∏t=xtP1(t,→x,→α)]∘[Cn,m0,f,pn,m1,...,pn,mn+m] y por lo tanto el Lema 4.20 nos dice que F es Σ-p.r..
OBSERVACION: No siempre que P sea Σ-p.r. tendremos que M(P) lo sera. Notese que si M(P) fuera Σ-p.r., cada ves que P lo sea, entonces tendriamos que PRΣ=RΣ (justifique) lo cual contradiria la Proposicion 4.6. Mas adelante (Corolario 4.5) veremos un ejemplo de un predicado P el cual es Σ-p.r. pero M(P) no es Σ-p.r.
El lema de minimizacion recien probado es muy util como veremos en los siguientes dos lemas.
4.25. Sea Σ un alfabeto finito. Las siguientes funciones son Σ-p.r.:
(a) Q:ω×N→ω(x,y)→cociente de la division de x por y
(b) R:ω×N→ω(x,y)→resto de la division de x por y
(c) pr:N→ωn→n-esimo numero primo
Proof. (a) Ya vimos anteriormente que Q=M(P′), donde P′=λtx1x2[x1≥t.x2 y x1<(t+1).x2]. Ya que P′ es Σ-p.r. y Q(x1,x2)≤p2,01(x1,x2), para cada (x1,x2)∈ω×N (b) del Lema 4.24 implica que Q∈PRΣ.
(b) Notese que R=λxy[x˙−Q(x,y).y] y por lo tanto R∈PRΣ.
(c) Para ver que pr es Σ-p.r., veremos que la extension h:ω→ω, dada por h(0)=0 y h(n)=pr(n), n≥1, es Σ-p.r.. Luego pr=h|N resultara Σ-p.r. por ser la restriccion de una funcion Σ-p.r. a un conjunto Σ-p.r.. Primero note que h(0)=0h(t+1)=mini(i es primo∧i>h(t)) O sea que h=R(C0,00,g), donde g:ω×ω→ω(A,t)→mini(i es primo∧i>A) Es decir que solo nos resta ver que g es Σ-p.r.. Pero notese que g=M(P), donde P=λiAt[i es primo∧i>A]. Claramente P es Σ-p.r. por lo cual para poder aplicar (b) del lema anterior debemos encontrar una funcion f:ω×ω→ω tal que M(P)(A,t)≤f(A,t), para cada (A,t)∈ω2 Es decir f debera cumplir mini(i es primo∧i>A)≤f(A,t), para cada (A,t)∈ω2 Definamos f=λAt[A!+1]. Debemos probar entonces que mini(i es primo∧i>A)≤A!+1, para cada A∈ω Sea p un primo tal que p divide a A!+1. Es facil ver que entonces p>A ya que de lo contrario p dividiria a A! lo cual nos diria que p divide a 1=A!+1−A!, lo cual es absurdo. Pero esto claramente nos dice que mini(i es primo∧i>A)≤p≤A!+1 O sea que (b) del Lema 4.24 implica que g=M(P) es Σ-p.r.
4.26. Las funciones λxi[(x)i] y λx[Lt(x)] son Σ-p.r.
Proof. Note que Dλxi[(x)i]=N×N. Sea P=λtxi[¬(pr(i)t+1 divide x)] Note que P es Σ-p.r. y que DP=ω×ω×N. Dejamos al lector la prueba de que λxi[(x)i]=M(P). Ya que (x)i≤x, para todo (x,i)∈N×N, (b) del Lema 4.24 implica que λxi[(x)i] es Σ-p.r..
Veamos que λx[Lt(x)] es Σ-p.r.. Sea Q=λtx[(∀i∈N)i≤x(i≤t∨(x)i=0)] Notese que DQ=ω×N y que ademas por el Lema 4.21 tenemos que Q es Σ-p.r. (dejamos al lector explicar como se aplica tal lema en este caso). Ademas notese que λx[Lt(x)]=M(Q) y que Lt(x)≤x,para todo x∈N lo cual por (b) del Lema 4.24 nos dice que λx[Lt(x)] es Σ-p.r..
Para x1,...,xn∈ω, con n≥1, escribiremos ⟨x1,...,xn⟩ en lugar de ⟨x1,...,xn,0,...⟩.
4.27. Sea n≥1. La funcion λx1...xn[⟨x1,...,xn⟩] es Σ-p.r.
Proof. Sea fn=λx1...xn[⟨x1,...,xn⟩]. Claramente f1 es Σ-p.r.. Ademas note que para cada n≥1, tenemos fn+1=λx1...xn+1[(fn(x1,...,xn)pr(n+1)xn+1)]. O sea que podemos aplicar un argumento inductivo.
Supongamos que Σ≠∅. Sea ≤ un orden total sobre Σ. Recordemos que ≤ puede ser naturalmente extendido a un orden total sobre Σ∗. Sea P:DP⊆ωn×Σ∗m×Σ∗→ω un predicado. Cuando (→x,→α)∈ωn×Σ∗m es tal que existe al menos un α∈Σ∗ tal que P(→x,→α,α)=1, usaremos min≤αP(→x,→α,α) para denotar al menor α∈Σ∗ tal que P(→x,→α,α)=1. Notese que la expresion min≤αP(→x,→α,α) esta definida solo para aquellas (n+m)-uplas (→x,→α) para las cuales hay al menos un α tal que se da P(→x,→α,α)=1. Dicho de otra forma, min≤αP(→x,→α,α) no estara definida cuando para cada α∈Σ∗ se de que (→x,→α,α) no pertenece a DP o P(→x,→α,α)=0. Otro detalle importante a tener en cuenta es que la expresion min≤αP(→x,→α,α) no depende de la variable α. Por ejemplo, las expresiones min≤αP(→x,→α,α) y min≤βP(→x,→α,β) son equivalentes en el sentido que estan definidas en las mismas (n+m)-uplas y cuando estan definidas asumen el mismo valor.
Definamos M≤(P)=λ→x→α[min≤αP(→x,→α,α)] Notese que DM≤(P)={(→x,→α)∈ωn×Σ∗m:(∃α∈Σ∗) P(→x,→α,α)}M≤(P)(→x,→α)=min≤αP(→x,→α,α), para cada (→x,→α)∈DM≤(P) Diremos que M≤(P) es obtenida por minimizacion de variable alfabetica a partir de P.
Vemos un ejemplo. Sea Σ={@,a,b,c,d,e} y sea ≤ un orden total sobre Σ. Sea Dir={α1∈Σ∗:|α1|@=1} y definamos U:Dir→Σ∗ de la siguiente manera U(α1)=unico α tal que α@ es tramo inicial de α1 Sea P=λα1α[α1∈Dir y α@ es tramo inicial de α1] Tenemos que DM≤(P)={α1∈Σ∗:(∃α∈Σ∗) P(α1,α)}={α1∈Σ∗:α1∈Dir y (∃α∈Σ∗) α@ es tramo inicial de α1}=Dir y ademas es claro que M≤(P)(α1)=U(α1), para cada α1∈Dir, por lo cual M≤(P)=U. Intente explicar por que se utiizaron los nombres Dir y U.
4.28. Supongamos que Σ≠∅. Sea ≤ un orden total sobre Σ, sean n,m≥0 y sea P:DP⊆ωn×Σ∗m×Σ∗→ω un predicado Σ-p.r.. Entonces
(a) M≤(P) es Σ-recursiva.
(b) Si existe una funcion Σ-p.r. f:ωn×Σ∗m→ω tal que |M≤(P)(→x,→α)|=|min≤αP(→x,→α,α)|≤f(→x,→α), para cada (→x,→α)∈DM≤(P), entonces M≤(P) es Σ-p.r..
Proof. Sea Q=P∘[p1+n,m2,...,p1+n,m1+n+m,∗≤∘p1+n,m1]. Note que M≤(P)=∗≤∘M(Q) lo cual por (a) del Lema 4.24 implica que M≤(P) es Σ-recursiva.
Sea k el cardinal de Σ. Ya que |∗≤(M(Q)(→x,→α))|=|M≤(P)(→x,→α)|≤f(→x,→α), para todo (→x,→α)∈DM≤(P)=DM(Q), tenemos que M(Q)(→x,→α)≤i=f(→x,→α)∑ι=1ki, para cada (→x,→α)∈DM(Q). O sea que por (b) del Lema 4.24, M(Q) es Σ-p.r. y por lo tanto M≤(P) lo es.
En el ejemplo de recien vimos que U=M(P), con P=λα1α[α@ es tramo inicial de α1] por lo cual, dado que P es Σ-p.r. y ademas |U(α1)|≤|α1|, para cada α1∈Dir el lema anterior nos dice que U es Σ-p.r.
Ya que la nocion de funcion Σ-recursiva es el modelo matematico Godeliano del concepto de funcion Σ-efectivamente computable, nos podriamos preguntar entonces cual es el modelo matematico Godeliano del concepto de conjunto Σ-efectivamente enumerable. Si prestamos atencion a la definicion de conjunto Σ-efectivamente enumerable, notaremos que depende de la existencia de ciertas funciones Σ-efectivamente computables por lo cual la siguiente definicion cae de maduro:
Diremos que un conjunto S⊆ωn×Σ∗m sera llamado Σ-recursivamente enumerable cuando sea vacio o haya una funcion F:ω→ωn×Σ∗m tal que IF=S y F(i) sea Σ-recursiva, para cada i∈{1,...,n+m}.
Deberia entonces quedar claro que si el concepto de funcion Σ-recursiva modeliza correctamente al concepto de funcion Σ-efectivamente computable, entonces el concepto de conjunto Σ-recursivamente enumerable recien definido modeliza correctamente al concepto de conjunto Σ-efectivamente enumerable. Sin envargo para probar algunos de los resultados basicos acerca de los conjuntos Σ-recursivamente enumerables, deberemos esperar a tener probada la equivalencia del paradigma Godeliano con el imperativo.
La version Godeliana del concepto de conjunto Σ-efectivamente computable es facil de dar: un conjunto S⊆ωn×Σ∗m sera llamado Σ-recursivo cuando la funcion χωn×Σ∗mS sea Σ-recursiva. Todo conjunto Σ-recursivo es Σ-recursivamente enumerable pero esto lo probaremos mas adelante junto con otros resultados basicos sobre conjuntos Σ-r.e., los cuales se prueban usando el paradigma imperativo. Mas adelante daremos un ejemplo natural de un conjunto que es Σ-r.e. pero el cual no es Σ-recursivo.
Muchos resultados ya probados para el caso primitivo recursivo pueden ser probados usando basicamente las mismas pruebas e ideas para el caso recursivo. Por ejemplo las pruebas de los siguientes cuatro lemas son identicas a las del caso primitivo recursivo
4.29. Si P:S⊆ωn×Σ∗m→ω y Q:S⊆ωn×Σ∗m→ω son predicados Σ-r., entonces (P∨Q), (P∧Q) y ¬P lo son tambien.
4.30. Si S1,S2⊆ωn×Σ∗m son Σ-r., entonces S1∪S2, S1∩S2 y S1−S2 lo son.
4.31. Supongamos S1,...,Sn⊆ω, L1,...,Lm⊆Σ∗ son conjuntos no vacios. Entonces S1×...×Sn×L1×...×Lm es Σ-r. sii S1,...,Sn,L1,...,Lm son Σ-r.
4.32. Si f:Df⊆ωn×Σ∗m→O es Σ-r. y S⊆Df es Σ-r., entonces f|S es Σ-r
Tambien se puede probar una version del lema de division por casos para funciones Σ-recursivas con dominio Σ-recursivo, la cual generaliza el caso Σ-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:
4.33. Si f:Df⊆ωn×Σ∗m→O es Σ-r. y Df es Σ-r., entonces existe una funcion Σ-r. ˉf:ωn×Σ∗m→O, tal que f=ˉf|Df
Proof. Si f=∅, es facil de probar y dejado al lector. Supongamos entonces f es no vacia. Sin perdida de generalidad podemos suponer que (0,...,0,ε,...,ε)∈Df. Sea F:ωn×Σ∗m→ωn×Σ∗m(→x,→α)→{(→x,→α)si (→x,→α)∈Df(0,...,0,ε,...,ε)caso contrario Ya que F(i)=λ→x→α[xi.χωn×Σ∗mDf(→x,→α)], para i=1,...,nF(i)=λ→x→α[αχωn×Σ∗mDf(→x,→α)i], para i=n+1,...,n+m tenemos que cada F(i) es Σ-recursiva. Es claro que ˉf=f∘F cumple que f=ˉf|Df por lo cual solo falta ver que ˉf es Σ-recursiva. Pero esto es obvio ya que F=[F(1),...,F(n+m)]
4.34. Supongamos fi:Dfi⊆ωn×Σ∗m→O, i=1,...,k, son funciones Σ-recursivas tales que cada Dfi es Σ-recursivo y Dfi∩Dfj=∅ para i≠j. Entonces la funcion f1∪...∪fk es Σ-recursiva.
Proof. Completamente analoga a la del caso primitivo recursivo.
4.35. Si S es Σ-recursivo, entonces S es Σ-r.e.
Proof. Supongamos ∅≠S⊆ωn×Σ∗m. Sea (z1,...,zn,γ1,...,γm)∈S fijo. Sea ≤ un orden total sobre Σ. Sea G:ω→ωn×Σ∗m dada por G(x)=((x+1)1,...,(x+1)n,∗≤((x+1)n+1),...,∗≤((x+1)n+m)) Es claro que cada G(i) es Σ-recursiva y que ImG=ωn×Σ∗m.
Para i=1,...,n, definamos Fi:ω→ω de la siguiente manera Fi(x)={G(i)(x)si G(x)∈Szicaso contrario Para i=n+1,...,n+m, definamos Fi:ω→Σ∗ de la siguiente manera Fi(x)={G(i)(x)si G(x)∈Sγicaso contrario Usando que S es Σ-recursivo podemos aplicar el lema anterior y ver que cada Fi es Σ-recursiva. Sea F=[F1,...,Fn+m]. Notese que F(i)=Fi para cada i=1,...,n+m. Esto nos dice que S es Σ-r.e. ya que ImF=S.
Mas adelante (Lema 4.62) daremos un ejemplo natural de un conjunto que es Σ-r.e. pero el cual no es Σ-recursivo.
Deberia quedar claro que si el modelo de Godel es correcto, entonces todos los resultados probados dentro del paradigma filosofico de Leibniz son ciertos una ves reenunciados de acuerdo al paradigma Godeliano. Tal como vimos arriba muchos de estos resultados se prueban en forma facil en su version recursiva. Sin envargo muchos otros requieren mas trabajo y es necesario utilizar algun paradigma mas constructivo (como el imperativo de Neumann o el de Turing) para poder probarlos en su version recursiva. Por ejemplo consideremos el teorema siguiente dado en el contexto del paradigma filosofico de Leibniz:
4.1. Sea S⊆ωn×Σ∗m. Son equivalentes
(a) S es Σ-efectivamente computable
(b) S y (ωn×Σ∗m)−S son Σ-efectivamente enumerable
Se tiene que la version recursiva de (a)⇒(b) es probada sin problemas en el lema anterior pero para probar la version recursiva de (b)⇒(a), nos sera necesario utilizar el paradigma imperativo (Teorema 4.11). Lo mismo sucede con el lema de division por casos en su forma mas general (Lema 3.4) y con el teorema de caracterizacion de conjuntos Σ-efectivamente enumerables (Teorema 3.2), ambos cuando son enunciados en su version recursiva no son faciles de probar con las herramientas desarrolladas hasta ahora y nos sera necesario usar el paradigma imperativo para representar a los objetos recursivos involucrados. Estas pruebas estan en la Seccion [survey recursivo] donde se compilan todos los resultados basicos (expresados en paradigma recursivo) y se obtienen algunos resultados los cuales en esta instancia todavia no se pueden probar ya que para obtenerlos es necesario hacer uso de la formalizacion matematica de ambos paradigmas el funcional y el imperativo (por ejemplo la existencia de un conjunto que es Σ-r.e. pero el cual no es Σ-recursivo).
Dada una funcion h:ω×S1×...×Sn×L1×...×Lm→ω, con S1,...,Sn⊆ω y L1,...,Lm⊆Σ∗, no vacios, definamos h↓:ω×S1×...×Sn×L1×...×Lm→ω de la siguiente manera h↓(x,→x,→α)=⟨h(0,→x,→α),h(1,→x,→α),...,h(x,→x,→α)⟩=Πxi=0pr(i+1)h(i,→x,→α)
4.36. Supongamos f:S1×...×Sn×L1×...×Lm→ωg:ω×ω×S1×...×Sn×L1×...×Lm→ωh:ω×S1×...×Sn×L1×...×Lm→ω son funciones tales que h(0,→x,→α)=f(→x,→α)h(x+1,→x,→α)=g(h↓(x,→x,→α),x,→x,→α), para cada x∈ω y (→x,→α)∈S1×...×Sn×L1×...×Lm. Entonces h es Σ-r. (resp. Σ-p.r.) si f y g lo son.
Proof. Supongamos f,g son Σ-p.r.. Primero veremos que h↓ es Σ-r. (resp. Σ-p.r.). Notese que para cada (→x,→α)∈S1×...×Sn×L1×...×Lm tenemos que h↓(0,→x,→α)=⟨h(0,→x,→α)⟩=⟨f(→x,→α)⟩=2f(→x,→α)h↓(x+1,→x,→α)=h↓(x,→x,→α)pr(x+2)h(x+1,→x,→α)=h↓(x,→x,→α)pr(x+2)g(h↓(x,→x,→α),x,→x,→α) lo cual nos dice que h↓=R(f1,g1) donde f1=λ→x→α[2f(→x,→α)]g1=λAx→x→α[Apr(x+2)g(A,x,→x,→α)] O sea que h↓ es Σ-r. (resp. Σ-p.r.) ya que f1 y g1 lo son. Finalmente notese que h=λix[(x)i]∘[Suc∘p1+n,m1,h↓] lo cual nos dice que h es Σ-r. (resp. Σ-p.r.).
Probaremos que los conceptos de Σ-recursividad y Σ-recursividad primitiva son en realidad independientes del alfabeto Σ, es decir que si f es una funcion la cual es Σ-mixta y Γ-mixta, entonces f es Σ-recursiva (resp. Σ-p.r.) sii f es Γ-recursiva (resp. Γ-p.r.).
Ya definimos para el caso de un alfabeto Σ≠∅ y ≤ un orden total sobre Σ, las funciones #≤ y ∗≤. Sea Σ=∅. Notese que el conjunto ∅ es un orden total sobre Σ (de hecho es el unico orden total sobre Σ). Definamos #∅:{0}→{ε}0→ε ∗∅:{ε}→{0}ε→0 Ya que Σ∗={ε}, las funciones #∅ y ∗∅ son biyecciones mutuamente inversas entre {0} y Σ∗. Ademas notese que estas funciones son Σ-p.r..
4.37. Supongamos Σ⊆Γ.
(a) Si ≤ es un orden total sobre Σ, entonces las funciones Σ-mixtas ∗≤ y #≤ son Γ-p.r..
(b) Si ≤′ es un orden total sobre Γ, entonces las funciones Σ-mixtas #≤′|Σ∗ y ∗≤′|#≤′(Σ∗) son Σ-p.r..
Proof. (a) Si Σ=∅, entonces es facil ver que ∗≤ y #≤ son Γ-p.r., y es dejado como ejercicio. Supongamos Σ={a1,...,ak} con k≥1 y ≤ es dado por a1<...<ak. Sea s≤e:Γ∗→Γ∗ dada por s≤e(ε)=a1s≤e(αai)=αai+1, si i<ks≤e(αak)=s≤e(α)a1s≤e(αa)=ε, si a∈Γ−Σ. Note que s≤e es Γ-p.r. y que s≤e|Σ∗=s≤. Ya que ∗≤(0)=ε∗≤(x+1)=s≤(∗≤(x)) para cada x∈ω, tenemos que ∗≤(0)=ε∗≤(x+1)=s≤e(∗≤(x)) Pero esto nos dice que ∗≤=R(C0,0ε,g) donde g:ω×Γ∗→Γ∗(x,α)→s≤e(α) Pero es claro que g es Γ-p.r. por lo cual ∗≤ es Γ-p.r..
Para ver que #≤:Σ∗→ω es Γ-p.r., sea #≤e:Γ∗→ω dada por #≤e(ε)=0#≤e(αai)=#≤e(α).k+i#≤e(αa)=0, si a∈Γ−Σ. Ya que #≤e es Γ-p.r., eso es #≤=#≤e|Σ∗.
(b) El caso Σ=∅ es facil y queda como ejercicio. Supongamos entonces Σ es no vacio. Sea n el cardinal de Γ. Ya que #≤′|Σ∗(ε)=0#≤′|Σ∗(αa)=#≤′|Σ∗(α).n+#≤′(a), para cada a∈Σ la funcion #≤′|Σ∗ es Σ-p.r.. O sea que el predicado P=λxα[#≤′|Σ∗(α)=x] es Σ-p.r.. Sea ≤ un orden total sobre Σ. Note que ∗≤′|#≤′(Σ∗)=M≤(P), lo cual ya que |∗≤′|#≤′(Σ∗)(x)|≤x nos dice que ∗≤′|#≤′(Σ∗) es Σ-p.r. (Lema 4.28).
4.38. PR∅⊆PRΣ y R∅⊆RΣ
Proof. Veamos que R∅⊆RΣ. Probaremos por induccion en k que R∅k⊆RΣ. El caso k=0 es trivial. Supongamos entonces que vale la hipotesis inductiva R∅k⊆RΣ y veamos que R∅k+1⊆RΣ. Sea F∈R∅k+1−R∅k veremos que F∈RΣ. Hay varios casos:
Caso F=R(f,G), con f:S1×...×Sn×∅∗m→∅∗Ga:S1×...×Sn×∅∗m×∅∗×∅∗→∅∗, para cada a∈∅ funciones en R∅k y cada Si no vacio. Por hipotesis inductiva tenemos que f∈RΣ. Notese que G=∅, lo cual nos dice que por definicion R(f,G):S1×...×Sn×∅∗m×∅∗→∅∗(→x,ε,...,ε,ε)→f(→x,ε,...,ε) Es claro que ωn×Σ∗m×∅∗ es un conjunto Σ-p.r. por lo cual las funciones pn,m+1i|ωn×Σ∗m×∅∗ son Σ-p.r. (aqui las pn,m+1i son respecto de Σ). Ya que R(f,G)=f∘[pn,m+11|ωn×Σ∗m×∅∗,...,pn,m+1n+m|ωn×Σ∗m×∅∗] tenemos que F es Σ-recursiva
Caso F=R(f,g), con f:S1×...×Sn×∅∗m→∅∗g:ω×S1×...×Sn×∅∗m×∅∗→∅∗ funciones en R∅k y cada Si no vacio. Por hipotesis inductiva tenemos que f,g∈RΣ. Notese que respecto de Σ, la funcion R(f,g) no esta definida ya que por la forma de f, el dominio de g deberia ser ω×S1×...×Sn×∅∗m×Σ∗. Sea ˜g=g∘[p1+n,m+11,...,p1+n,m+11+n+m,C1+n,m+1ε] (aqui las p1+n,m+1i y C1+n,m+1ε son respecto de Σ). Notese que D˜g=ω×S1×...×Sn×∅∗m×Σ∗ y ˜g es Σ-recursiva. Ademas es facil ver que F=Rf,˜g) (respecto del alfabeto Σ) por lo cual F es Σ-recursiva
Caso F=M(P), con P:ω×ωn×∅∗m→ω, un predicado en R∅k. Por hipotesis inductiva tenemos que P∈RΣ. Sea ˉP=P∘[p1+n,m1,...,p1+n,m1+n,C1+n,mε,...,C1+n,mε] Notese que ˉP es Σ-total y Σ-recursivo y ademas extiende a P. Sea ˜P=λxy[x.y]∘[ˉP,χω×ωn×Σ∗mω×ωn×∅∗m] Tambien ˜P es Σ-total y Σ-recursivo y extiende a P pero ademas fuera del dominio de P vale 0. Esto nos dice que M(˜P)=M(P) por lo cual F es Σ-recursiva ya que M(˜P) lo es
Los otros casos de recursion primitiva son parecidos a los hechos y el caso de la composicion es trivial.
La prueba de que PR∅⊆PRΣ es muy similar. Se dejan los detalles como ejercicio para el lector
Sea Σ un alfabeto finito (puede ser vacio) y sea ≤ un orden total sobre Σ. Para f:Df⊆ωn×Σ∗m→ω, definamos f#≤=f∘[pn+m,01,...,pn+m,0n,∗≤∘pn+m,0n+1,...,∗≤∘pn+m,0n+m] Similarmente, para f:Df⊆ωn×Σ∗m→Σ∗, definamos f#≤=#≤∘f∘[pn+m,01,...,pn+m,0n,∗≤∘pn+m,0n+1,...,∗≤∘pn+m,0n+m]
4.39. Sea Γ un alfabeto finito y sea ≤ un orden total sobre Γ. Dada h una funcion Γ-mixta, son equivalentes
(1) h es Γ-recursiva (resp. Γ-p.r.)
(2) h#≤ es ∅-recursiva (resp. ∅-p.r.)
Proof. (2)⇒(1). Supongamos h:Dh⊆ωn×Γ∗m→Γ∗ es tal que h#≤ es ∅-recursiva (resp. ∅-p.r.). Dejamos al lector chequear que h=∗≤∘h#≤∘[pn,m1,...,pn,mn,#≤∘pn,mn+1,...,#≤∘pn,mn+m] (aqui las pn,mi son respecto de Γ). Por el lema anterior tenemos que h#≤ es Γ-recursiva (resp. Γ-p.r.). Ya que (aun cuando Γ=∅) tenemos que las funciones ∗≤ y #≤ son Γ-p.r., tenemos que h es Γ-recursiva (resp. Γ-p.r.) ya que es composicion de funciones Γ-recursivas (resp. Γ-p.r.).
(1)⇒(2). El caso Γ=∅ es trivial ya que h#≤ se define como composicion de funciones ∅-recursivas (resp. ∅-p.r.). Supongamos entonces que Γ={a1,...,ar}, con a1<a2<...<ar y r>0. Probaremos por induccion en k que
Si h∈RΓk (resp. h∈PRΓk), entonces h#≤ es ∅-recursiva (resp. ∅-p.r.).
El caso k=0 es facil y dejado al lector. Supongamos (*) vale para un k fijo. Veremos que vale para k+1. Sea h∈RΓk+1 (resp. h∈PRΓk+1). Hay varios casos
Caso 1. Supongamos h=f∘[f1,...,fn], con f,f1,...,fn∈RΓk (resp. f,f1,...,fn∈PRΓk). Por hipotesis inductiva tenemos que f#≤,f#≤1,...,f#≤n son ∅-recursivas (resp. ∅-p.r.). Ya que h#≤=f#≤∘[f#≤1,...,f#≤n], tenemos que h#≤ es ∅-recursiva (resp. ∅-p.r.).
Caso 2. Supongamos h=M(P), con P:ω×ωn×Γ∗m→ω, un predicado en RΓk. Ya que h#≤=M(P#≤), tenemos que h#≤ es ∅-recursiva.
Caso 3. Supongamos h=R(f,G), con f:S1×...×Sn×L1×...×Lm→Γ∗Ga:S1×...×Sn×L1×...×Lm×Γ∗×Γ∗→Γ∗, a∈Γ funciones en RΓk (resp. \mathrm{PR}_{k}^{\Gamma}) y S_{1},...,S_{n}\subseteq\omega y L_{1},...,L_{m}\subseteq\Sigma^{\ast}, no vacios. Notese 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} Por hipotesis inductiva 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.25). 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). Tambien 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
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 continuacion aplicaremos la idea del Lema 4.36. Sera mas claro asi ya que para aplicarlo directamente deberiamos cambiar el orden de los parametros de las funciones h^{\#^{\leq}}, \mathcal{G}_{a_{i}}^{\#^{\leq}} componiendolas adecuadamente y seria 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 recursion primitiva son similares.
Ahora podemos probar el anunciado resultado de independencia.
4.2 (Independencia del Alfabeto). Sean \Sigma y \Gamma alfabetos cualesquiera.
(a) Supongamos una funcion f es \Sigma-mixta y \Gamma-mixta, entonces f es \Sigma-recursiva (resp. \Sigma-p.r.) sii f es \Gamma-recursiva (resp. \Gamma-p.r.).
(b) Supongamos un conjunto S es \Sigma-mixto y \Gamma-mixto, entonces S es \Sigma-recursivo (resp. \Sigma-r.e., \Sigma-p.r.) sii S es \Gamma-recursivo (resp. \Gamma-r.e., \Gamma-p.r.).
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.37) 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 notese 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.37), la funcion 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 notese 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 definicion tenemos que \chi_{S}^{\omega^{n}\times\Sigma^{\ast m}} es \Sigma-recursiva. Pero \chi_{S}^{\omega^{n}\times\Sigma^{\ast m}} es tambien \Gamma-mixta, por lo cual (a) nos dice que \chi_{S}^{\omega^{n}\times\Sigma^{\ast m}} es \Gamma-recursiva. Ademas 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.32 y 4.34 nos dicen que \chi_{S}^{\omega^{n}\times\Gamma^{\ast m}} es \Gamma-recursiva (aqui C_{0}^{n,m} es respecto del alfabeto \Gamma).
Supongamos ahora que S es \Gamma-recursivo. Veremos que S es \Sigma-recursivo. Por definicion 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 analogo y dejado al lector.
@@finpagina@@