Download Representaciones

Representaciones
de conjuntos y funciones
Roberto Moriyón
Determinación de conjuntos
• Las fórmulas lógicas de la Aritmética con una
variable libre determinan conjuntos de números
naturales
• Ejemplos:
– La fórmula y,x=y+y determina al conjunto de los
números pares.
– La fórmula
y,z,u,v, ~y=0 ^ ~z=0 ^ ~u=0 ^~v=0  ~x=(y+z).(u+v)
determina al conjunto de los números primos.
Determinación de conjuntos, II
• Para ver que el número 2 es par basta con
demostrar que al sustituir x por SS0 en la
penúltima fórmula se obtiene una fórmula
que es cierta en la interpretación estándar de
la Aritmética: y,SS0=y+y
• La forma habitual de demostrar que una
fórmula es cierta en la interpretación
estándar es mediante una deducción
• Este procedimiento no es válido si la fórmula
es cierta en unas interpretaciones y falsa en
otras.
Determinación de conjuntos, III
• Las fórmulas lógicas de la Semiótica con una
variable libre determinan lenguajes.
– Por ejemplo, la fórmula
y,z, ~x = y + S[z ^ ~x = y + S]z
determina las cadenas de caracteres que no
contienen corchetes.
• Para ver que la cadena “aba” no contiene
corchetes basta con demostrar que
y,z, ~“aba” = y + S[z ^ ~“aba” = y + S]z
es cierta en la interpretación estándar.
Determinación de conjuntos, IV
• La fórmula
y, x=“a”+y+“b”
determina a las cadenas que empiezan
por a y terminan por b.
• Para ver que la cadena “aba” no
pertenece al lenguaje anterior vasta con
demostrar quey, ~x=“a”+y+“b” es cierta
en la interpretación estándar de la
semiótica.
Determinación de conjuntos, V
• Todo lo anterior es válido también para
fórmulas con n variables libres, que definen
conjuntos de n-plas de números o cadenas.
• Por ejemplo, la fórmula x+y=SSSS0
determina al conjunto de pares de números
A = {(0,4), (1,3), (2,2), (3,1), (4,0)}  X.
• Ello se debe a que para cualesquiera
términos T y U cerrados, o bien T+U=SSSS0
es un teorema o lo es su negación.
Determinación de funciones
• Las fórmulas lógicas de la Aritmética con
dos variables libres pueden determinar
funciones numéricas
• Ejemplos:
– La fórmula x+y=SSSS0 determina a la
función f(x)=4-x, con dominio {0,1,2,3,4}.
– La fórmula y=SSSx determina a la función
f(x)=x+3, con dominio .
– La fórmula y=0 v y=S0 no determina ninguna
función.
Determinación de funciones, II
• En general, las fórmulas de la Aritmética
con m+n variables libres pueden
determinar funciones de n en m.
• Ello ocurre cuando determinan el grafo de
una función.
• Por ejemplo, la fórmula u=x+y+z
determina a la función f(x,y,z)=x+y+z.
Determinación de funciones, III
• La determinación de funciones descrita en
las transparencias anteriores se extiende
a la Semiótica, en la que las fórmulas con
m+n variables libres pueden determinar
funciones de *n en *m.
Determinación de funciones, IV
• No es obvio cómo determinar funciones
como h(x,y)=xy, cuyo cálculo requiere la
ejecución de bucles, mediante fórmulas (la
función exponencial no es parte del
lenguaje de la teoría lógica de la
Aritmética).
Ejemplo de determinación de
función exponencial
• La función f:** definida por
f ( x)  a
2|x|
se determina mediante una fórmula de la teoría
lógica de la Semiótica.
Demostración: aunque no disponemos de bucles,
construiremos en primer lugar una fórmula que
caracteriza al conjunto C de cadenas de la forma
“;:a;0:aa;10:aaaa;210:aaaaaaaa;…;”
que son la concatenación de subcadenas de la
forma ;Sj:ak; con Sj+1=jSj y k=2j.
Ejemplo de determinación de
función exponencial, II
;:a;0:aa;10:aaaa;210:aaaaaaaa;…;
• Su descripción es la siguiente: Son las
cadenas que:
– Comienzan por ;:a; y teminan por ;
– Cada subcadena (item) que separa dos ;
consecutivos contiene : (solamente uno).
– Cada dos items consecutivos de la forma
Sj:Aj verifican que Sj+1=jSj y Aj+1=AjAj.
Ejemplo de determinación de
función exponencial, III
;0:a;00:aa;100:aaaa;2100:aaaaaaaa;…;
La descripción en el lenguaje lógico es:
(t,r=”;0:a;”+t+”;”)^
(g,h,k,(r=g+”;”+h+”;”+k^~s,p,(h=p+”;”+s)) 
(m,n,h=m+”:”+n^(~t,c,(m=t+”:”+c))^
~d,e,(n=d+”:”+e)))^
(u,v,y,z,w,h,
((r=u+”;”+v+”:”+y+”;”+z+”:”+w+”;”+h)^
(~q,p, (v=p+”;”+q) v (y=p+”;”+q) v
(z=p+”;”+q) v (w=p+”;”+q)))
 ((z=“a”+v v z=“b”+v)^w=y+y)))
Ejemplo de determinación de
función exponencial, IV
• Si llamamos G a la fórmula anterior, cuya
única variable libre es r, la fórmula F que
buscamos que determina a la función y=f(x)
es
r,u,(r=u+”;”+x+”:”+y+”;”^G)
• Para demostrar rigurosamente que la fórmula
F anterior determina a la función y=f(x) hay
que ver que dados dos términos S y T sin
variables, FS/x,T/y es un teorema si TI=f(SI) y
su negación es un teorema en caso
contrario.
Ejemplo de determinación de
función exponencial, V
• Por ejemplo, hay que demostrar que
F”a”/x,”aa”/y y ~F”a”/x,”a”/y son teoremas.
• Para lo primero basta con demostrar que
G“;:a;a:aa;”/r es un teorema, lo que es tedioso
pero sencillo.
• Para lo segundo basta con demostrar que
F^Fv/yv=y es un teorema, lo cual se
reduce a demostrar que r=sr+r=s+s es
un teorema.
Determinación de funciones
recursivas primitivas
• Se hace análogamente a la función
exponencial anterior.
• Por ejemplo, se puede utilizar el mismo
procedimiento para determinar la función
de Fibonacci sobre cadenas de caracteres
sobre el alfabeto {a}.
Determinación de funciones
recursivas totales
• Una función recursiva total f se puede
calcular mediante una máquina de Turing
determinista que siempre se para.
• La función  que calcula el cambio de
estado operacional de la máquina de
Turing al ejecutarse una transición es una
función básica.
Determinación de funciones
recursivas totales, II
• La función f se puede determinar
utilizando cadenas auxiliares de la forma
“e0w;” + (“e0w”) + ”;” + ((“e0w”)) +
+ ”;” + … + “:” + j-1)(“e0w”) + ”;” + j)(“e0w”)
Fundamentación teórica:
Representación
• Decimos que una fórmula F de la
Aritmética con una variable libre
representa a un conjunto de números
naturales X cuando para cualquier término
cerrado T, FT es un teorema si y solo sí la
interpretación estándar de T pertenece a
X y ~FT es un teorema si y solo sí la
interpretación estándar de T no pertenece
a X.
Fundamentación teórica:
Representación, II
• Todos los ejemplos que hemos visto de
determinación de conjuntos son
representaciones de conjuntos.
• En la práctica para demostrar que una
fórmula determina a un conjunto hay que
ver que lo representa.
• Lo anterior se extiende a la representación
de conjuntos de tuplas de números o de
cadenas de caracteres y de funciones.
Recordatorio: conjuntos
computables
• Recordatorio: Un conjunto es computable
si hay una máquina de Turing que lo
reconoce y otra que reconoce a su
complementario.
• Un conjunto es computable si hay una
máquina de Turing determinista que
siempre se para que lo reconoce.
• Los conjuntos computables son la imagen
inversa de un valor determinado mediante
una función recursiva total.
Teorema de representación
para la Semiótica
• Una fórmula de la Teoría Lógica de la
Semiótica representa a un conjunto C*n,
si y sólo si C es computable.
Demostración del Teorema de
Representación para la Aritmética
• La primera demostración del Teorema de
Representación la dio Gödel para la
Aritmética. Lo hizo para poder demostrar
su Teorema de Incompletitud.
Demostración del Teorema de
Representación de la Aritmética, II
• Se puede demostrar análogamente al
caso de la Semiótica, demostrando para
ello que se pueden representar listas de
números mediante otros números (al igual
que se pueden representar listas de
cadenas mediante cadenas utilizando
separadores).
Numeración de Gödel
• Para representar listas de números
mediante números, Gödel utiliza el
siguiente procedimiento:
La lista {n1, n2, …, nN} se representa
mediante el número
n1
n2
nN
p1  p2  …  pN
donde p1, p2, … son los primeros números
primos sucesivos, 2, 3, 5, 7, …
Teorema de representación de
funciones
• Si una fórmula de la Teoría Lógica de la
Semiótica representa a una función
f:*n*m, entonces f es recursiva.
• Si f:*n*m es una función recursiva total,
entonces hay una fórmula de la Teoría
Lógica de la Semiótica que la representa.
Teorema de representación de
funciones, II
• El teorema también es cierto en su versión
numérica.
• Ambas versiones del teorema se
demuestran reduciéndolas al caso
correspondiente de conjuntos. La
demostración se deja como ejercicio.
Teorema de representación de
funciones, II
• Hay funciones recursivas que no son
totales pero son representables mediante
fórmulas de la Teoría Lógica de la
Semiótica.
• Como ejemplo se puede considerar la
función que a cada codificación de una
máquina de Turing concatenada con una
palabra le hace corresponder el número
de pasos que da la máquina a partir de la
palabra antes de pararse.
Teorema de representación:
Consecuencias
Ejemplo de función que se puede
representar en la Lógica de la Semiótica:
• :*2*
(T, F) = sustitución de T
en las variables libres de F
Lo anterior es consecuencia de que  es
una función recursiva y total. De hecho, es
recursiva primitiva.
Teorema de representación:
Consecuencias, II
Otro ejemplo: Dado un conjunto recursivo
A de axiomas,
• A :**
A(d) = conclusión de la demostración d (o
0 si d no es una demostración).
A depende del conjunto de axiomas A
que se admita.
A también es una función recursiva
primitiva.
Teorema de representación:
Consecuencias, III
• Tercer ejemplo:
• A :**
A(F) = F si F es un teorema en la teoría
definida por el conjunto A de axiomas (o 0
si ~F es un teorema en dicha teoría).
Como consecuencia del Teorema de
Incompletitud de Gödel, si A es el conjunto
de los axiomas de Peano, A no es una
función total.
Teorema de representación:
Consecuencias, IV
• A(F)= F si existe una demostración de F.
• Por lo tanto, si la fórmula lógica F
representa a la función g=A(d), entonces
la fórmula
(d,F^f=g) v (d,F~g/g^f=0)
representa a f=A(g).
Teorema de representación:
Consecuencias, V
• La numeración de Gödel permite construir
representaciones para las funciones
análogas a las anteriores en la Aritmética:
• Hay una fórmula de la Lógica de la
Aritmética, , con dos variables
(numéricas) libres, que representa cuándo
la demostración representada por el
número d demuestra la fórmula lógica
representada por el número f.
Teorema de representación:
Consecuencias, VI
• Hay una fórmula de la Lógica de la
Aritmética, , con tres variables
(numéricas) libres, que representa cuándo
al sustituir en la fórmula lógica
representada por el número f su variable
libre por el término representado por el
número t se obtiene la fórmula lógica
representada por el número h.
Teorema de representación:
Consecuencias, VII
• Hay una fórmula de la Lógica de la
Aritmética, , con una variable (numérica)
libre, que representa cuándo existe una
demostración de la fórmula lógica
representada por el número f.