Logica Matematica

Lgica Matemtica
Pedro Valero Meja y Guillermo Apuntes UAM

Rual Doble Grado Mat.Inf.
UAM - 15/16 C1 Cdigo en Github
11 de febrero de 2016 15:15
Lgica Matemtica - 15/16 C1 - UAM Pedro Valero Meja y Guillermo Rual
ndice general
1 Lgica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 Sintaxis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Axiomas de la lgica proposicional . . . . . . . . . . . . . . . 4
1.3 Semntica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Problemas TAUT y SAT . . . . . . . . . . . . . . . . . . . . . 8
1.5 Completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Lgica de primer orden (o de predicados) . . . . . . . . . . . . . . . . 15
2.1 Exposicin informal y ejemplos . . . . . . . . . . . . . . . . . 15
2.2 Axiomas de ZFC (Zermelo-Fraenkel con Eleccin) . . . . . . . 17
2.3 Axiomas de Peano . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Introduccin a lgicas de segundo orden . . . . . . . . . . . . 22
2.5 Completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Lenguajes y estructuras . . . . . . . . . . . . . . . . . . . . . 26
2.7 Axiomas de la lgica de primer orden y reglas de deduccin . . 29
2.8 Reglas de deduccin . . . . . . . . . . . . . . . . . . . . . . . 30
2.9 Contenidos para examen . . . . . . . . . . . . . . . . . . . . . 33
2.10 Nuestra historia hasta ahora . . . . . . . . . . . . . . . . . . . 35
3 Computacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1 Motivacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Mquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Minimizacin no acotada y funciones recursivas . . . . . . . . . 48
4 Incompletitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
A Problemas resueltos 58
A.1 Hoja 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
A.2 Hoja 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
A.3 Hoja 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
A.4 Hoja 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
A.5 Hoja 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
A.6 Hoja 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
A.7 Hoja 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
A.8 Hoja 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Bibliografa 100
ndice alfabtico 101
0
Documento compilado el 11 de febrero de 2016 a las 15:15
1 de 102
1. Lgica proposicional
Sea A un conjunto no vaco, definimos el lenguaje como
L A {, = , , , , , >, ), (}
donde los smbolos representan
: negacin.
= : implicacin.
: conjuncin.
: disyuncin.
: equivalencia.
: verdadero.
> : falso.
) : parntesis derecho.
(: parntesis izquierdo.
1.1. Sintaxis
Dado A, un conjunto (finito, numerable o no numerable) de variables proposicio-
nales p, q, r, . . ., se definen:
Palabra Definicin 1.1 Palabra. Concatenacin de smbolos.
Proposicin Definicin 1.2 Proposicin o frmula bien formada. Palabra que pertenece a la
o frmu- clase ms pequea cerrada bajo las siguientes propiedades:
la bien
formada
Los elementos de A, y > son frmulas atmicas (no se pueden dividir).
Si F1 y F2 son frmulas, tambin lo son
(F1 )
(F1 = F2 )
(F1 F2 )
(F1 F2 )
(F1 F2 )
2 de 102
En notacin polaca son frmulas bien formadas:
F1
= F1 F2
F1 F2
F1 F2
F1 F2
Las frmulas bien formadas pueden definirse de manera inductiva:
FBF0 = A {>, }
FBFn+1 = F BFn {(F1 ), (F1 = F2 ), (F1 F2 ), (F1 F2 ), (F1 F2 )}
con F1 , F2 FBFn .
Las frmulas bien formadas son F BF =

n=0 F BFn
Aridad Definicin 1.3 Aridad. La aridad de un operador es el nmero de argumentos que

admite:
, > son 0-arias.
es 1-aria.
, , = , son 2-arias (binarias).
Lema 1.1. Legibilidad nica: Las frmulas no son ambiguas, slo pueden leerse o
construirse de forma nica.
Hay que distinguir los siguientes casos:
F es atmica. La legibilidad nica es obvia.
F es es de la forma G, donde G es una FBF. La legibilidad nica es obvia.
F es de la forma (G1 G2 ) donde G1 y G2 son FBF y es una conectiva binaria.

En este caso habra que ver si existen las FBF G3 y G4 y la conectiva binaria 0 ,
tal que (G1 G2 ) = (G3 0 G4 ). La demostracin de que esto slo es posible si
G1 = G2 , G3 = G4 y = 0 ser un ejercicio de las hojas de problemas. La idea
es que G1 no puede ser un segmento inicial de G3 .
Observacin: a b c no es una frmula bien formada, ya que no tiene parntesis

exteriores. S son frmulas bien formadas las siguientes. (a (b c)), ((a b) c). Pero
como frmulas (sintcticamente) son distintas, aunque su significado sea el mismo.
3 de 102
Notacin:
Usamos para denotar equivalencia en el metalenguaje (en el lenguaje se
usa ).
Usamos p, q, r, s, . . . para denotar frmulas bien formadas.
1.2. Axiomas de la lgica proposicional

A continuacin se proporciona una lista de axiomas proposicionales.
1. >
2. p = (p q), p = (q p)
3. p = (q = (p q))
4. (p q) = p, (p q) = q
5. p = (q = (p q))
6. (p = (q = r)) = ((p = q) = (p = r))
7. p = (p = )
8. (p = ) = p
Los axiomas 2-8 son esquemas de axiomas, lo que quiere decir que si p 6= r,
entonces p = (p q) y r = (r q) son axiomas distintos.
Modus ponens
La regla de deduccin que vamos a utilizar es el modus ponens: Si tenemos p y
p = q, deducimos q.
p
p = q
q
Demostracin Definicin 1.4 Demostracin o prueba. Una demostracin o prueba (formal) es

o prueba una sucesin (finita) p1 , p2 , . . . , pn donde cada pi o bien es un axioma o se obtiene de
dos frmulas anteriores mediante modus ponens.
Notacin
Escribimos ` p para denotar que existe una demostracin de p.
Escribimos p para denotar que p es verdad.
Teora Definicin 1.5 Teora. T (o ) es una teora si es un conjunto de FBF(L).
4 de 102
Ejemplo: T nos dice que un grafo G puede colorearse con cuatro colores. (Ver
ejercicio 4 de la hoja 2).
Recordatorio: (G, E) es un grafo si
(
G = {v
}
E = {v , v } v , v G v 6= v
Dado que son pares de elementos distintos, no puede haber una arista que empiece
y acabe en el mismo vrtice, puesto que en dicho caso tendramos un conjunto de un
slo elemento.
Demostracin Definicin 1.6 Demostracin o prueba (II). Una demostracin a partir de los
o prueba axiomas y una teora T es una sucesin finita p1 , . . . , pn , donde cada pi es o un
(II) axioma, o pi T o se obtiene de dos pj , pk anteriores mediante modus ponens.
Notacin: Usamos T ` p para denotar que existe una prueba de p usando los
axiomas y las frmulas de T .
1.3. Semntica
La semntica se refiere a las interpretaciones que se le dan a las FBF. En el lenguaje
formal interpretamos > como verdadero y como falso. Informalmente utilizaremos
0 para falso y 1 para verdadero.
Vamos a considerar el siguiente lenguaje: tomamos

L = A , , , >, , ), (
Interpretacin Definicin 1.7 Interpretacin. Una interpretacin es una valoracin booleana :

: F BF (L) (Z2 , +, )
que satisface
(>) = 1, () = 0
(p) = 1 + (p), siendo p una FBF.

(p q) = (p) (q) = max (p), (q)

(p q) = (p) (q) = mn (p), (q)
Teorema 1.2. Sea : A {0, 1} una funcin arbitraria. Entonces se extiende,

de modo nico, a una valoracin booleana
: F BF (L) Z2
5 de 102
Demostracin. Por el lema de legibilidad nica.
A partir de los valores (p), (q), . . . se define para las F BF (L) tal y como
describen las siguientes tablas de verdad:
p p
>
1 0
1 0
0 1
p q pq pq p = q p q
1 1 1 1 1 1
1 0 1 0 0 0
0 1 1 0 1 0
0 0 0 0 1 1
Observacin:
> (p p)
>
(p = q) (p q)
(p q) (p = q) (q = p)
Sistema Definicin 1.8 Sistema completo. Un sistema de conectivas es completo si las dems
completo conectivas pueden definirse en trminos de ellas.
Ejemplo: Los siguientes conjuntos son completos.
{, }, {, }, {, = }, {, = }
{, } no es completo. Se puede probar por monotona.

{, } est propuesto como ejercicio (3.10) demostrar si es completo o no.
Modelo Definicin 1.9 Modelo. Sea T F BF (L). Un modelo de T es una valoracin

booleana p T, (p) = 1.
Consecuencia Definicin 1.10 Consecuencia tautolgica. Decimos que p es una consecuencia

tautolgi- tautolgica de T , y escribimos T p, si para todo modelo de T , (p) = 1. En este
ca contexto, decimos que p es una tautologa y escribimos p.
Observacin: Si T = , entonces toda es un modelo de T .
6 de 102
Equivalencia Definicin 1.11 Equivalencia lgica. Si p q, es decir, si p q es una

lgica tautologa, decimos que p y q son lgicamente equivalentes.
Observacin: Sea r una F BF (L), sea p una subfrmula de r y sea cualquier

valoracin booleana. Si p q y reemplazamos cada instancia de p en r por q
denotando por r0 la frmula as obtenida, entonces (r0 ) = (r).
Teora Definicin 1.12 Teora consistente. T es consistente si T 0. La consistencia o

consisten- coherencia puede caracterizarse de forma sencilla:
te
T 0 p F BF (L) T 0 p
Equivalentemente, una teora T es inconsistente si T `.
T ` T ` p p F BF (L)
Observacin: Si T es inconsistente, T ` cualquier cosa. Por otra parte, ninguna

valoracin satisface T , es decir, ninguna cumple (r) = 1 r T . Luego cualquier
cosa es una consecuencia lgica de T porque no hay ninguna valoracin que satisfaga
T.
Teorema 1.3 (Teorema de la deduccin). Si T {p} ` q, entonces
T ` p = q
Demostracin.
/ T , q 6= p, q no es un axioma lgico.
Caso 1: q
Consideramos p1 , . . . , pn = q una demostracin de q. Llevaremos a cabo la
demostracin por induccin en la longitud de las pruebas (frmulas).
Si n = 1 entonces q = p o q T o q es un axioma lgico, lo cual

no corresponde a este caso, por tanto suponemos que n > 1 y que el
Teorema de la deduccin es cierto para todas las pruebas de longitud
menor que n.
Si para alguna j < n, pj = p = q, no hay nada que probar.
Si no, i, j < n pi = r, pj = r = q. Por la hiptesis de induccin
tenemos T ` (p = r) y T ` (p = (r = q)). Utilizamos el
axioma
(p = (r = q)) = ((p = r) = (p = q))
y por modus ponens junto con lo anterior obtenemos
(p = r) = (p = q)
Finalmente, por modus ponens aplicado a T ` (p = r) y a lo anterior
obtenemos T ` (p = q).
7 de 102
Caso 2: q es un axioma lgico, q T o q = p.
Si q es un axioma o q T
Tenemos que T ` q y utilizando el segundo axioma de la lista de axiomas:
r = (q r) r = (q = r)
en el que usamos q en lugar de r y p en lugar de q, instanciamos
q = (p = q)
Usando modus ponens y lo anterior T ` (p = q).

Si q no es axioma ni est en T , entonces q = p. Tenemos T {p} ` p.
Y utilizando (del ejercicio 1a de la hoja dos) ` p = p. entonces
T ` p = p p = q
1.4. Problemas TAUT y SAT

Problema de las tautologas (TAUT): dada F F BF (L) determinar si F
es una tautologa. Es decir, determinar si para toda interpretacin , (F ) = 1.
El problema es saber cunto tiempo se tarda en averiguar si F es una tautologa

en funcin del tamao de los datos de los que se dispone.
Ejemplo: Dada la siguiente FBF y la tabla de verdad correspondiente:
p = (q = p)
p q q = p p = (q = p)
1 1 1 1
1 0 1 1
0 1 0 1
0 0 1 1
Tenemos que:
Nmero n de variables: 2
Nmero k de conectivas: 2
Tiempo (tamao de los datos) < O((n + k)2n )
8 de 102
Clases de complejidad
P: clase de problemas para los que existe un algoritmo que los resuelve en
tiempo polinmico en funcin del nmero de datos de entrada, es decir, K 0
(dependiendo el problema pero no del nmero de datos n) tal que si tenemos n
datos de entrada, el algoritmo requiere menos de O(nK ) operaciones.
NP: tiempo polinmico no determinista. La solucin la proporciona un orculo,

que podemos comprobar que es correcta (o no) en tiempo polinmico. Obvia-
mente PNP.
La clase de problemas NP-difcil se define como aquella que contiene a los

problemas que son como mnimo tan difciles como un problema de NP. Alter-
nativamente, se define como la clase de problemas H tal que todo problema en
NP puede ser transformado polinomialmente en H.
La clase de problemas NP-completo se define como la interseccin entre la

clase de problemas NP y la clase de problemas NP-difcil.
No se sabe si P=NP. Clay Mathematics Institute ha ofrecido un premio de un

milln de dlares estadounidenses para quin desarrolle la primera demostracin
correcta (el profesor no tiene tanto dinero, el te ofrece una matrcula).
Se sabe que TAUT es NP-difcil.
Satisfacin Definicin 1.13 Satisfacin. satisface a T si p T , (p) = 1, o equivalentemente,

si es un modelo de T .
Problema de la satisfacin (SAT): Si F F BF (L), determinar si existe una

interpretacin que satisfaga a F . SAT es NP-completo.
Ejemplo: Comprobar si p = (p = q).

El orculo dice que
(p) = 0
(q) = 0
p q p = p = (p = q)
0 0 1 1
Comprobacin: tiempo O(n + k).
1.5. Completitud
Recordatorio: Podemos reemplazar p por cualquier frmula equivalente. Por ejem-
plo, podemos remplazar p = q por p q, (p q) r por p (q r), cualquier
contradiccin por , etc.
9 de 102
Teorema 1.4. Si existe una prueba de p a partir de los axiomas y modus ponens,
entonces, p es una tautologa.
` p = p
Demostracin. Por induccin en la longitud de la demostracin.

Sean p1 , . . . , pn = p.
Caso n = 1: p1 = p es un axioma, luego es una tautologa.
Caso n > 1: p = pn , y para toda j n, pj es una tautologa.
Si p es una axioma, entonces p es una tautologa.

Si p no es un axioma, entonces se obtiene de dos frmulas anteriores
mediante modus ponens, digamos pi = r y pk = r = p con i, k < n.
Sea una valoracin booleana. Hay que probar que (p) = 1. Por la
hiptesis inicial, (r) = 1 = (r = p) = (rp) = (r)(p) =
max(0, (p)). Por tanto (p) = 1.
Teorema 1.5 (Teorema de completitud). Sea T = .
Validez: T ` p = T p
Adecuacin: T p = T ` p
En general
T ` p T p
Demostracin.
Validez: Sea V el conjunto de todas las valoraciones que satisfacen a T . Si
V = , entonces T ` trivialmente. Si V 6= , entonces, argumentamos como en
el teorema anterior pero considerando slo las valoraciones en V en lugar de todas.
Adecuacin: Sea p una tautologa sin demostracin. Como 0 p entonces T
{p} es consistente (ver teorema 1.7) lo que nos dice que, adems, T `6= p. Pero,
puesto que p es una tautologa, p = con lo que nos queda T ` p , que es
una contradiccin pues esta suponiendo que la teora es consistente.
Otra forma: Probamos la formulacin equivalente T 0 p = T 2 p, es decir,
hay un modelo de T tal que (p) = 0. T 0 p = T {p} es consistente.
10 de 102
Por 1.9, T {p} tiene un modelo . Por tanto, q T , (q) = 1, pero (p) = 0
porque (p) = 1.
Criterio:
T es consistente p T 0 p T es inconsistente p, T ` p
Teorema 1.6. Si T es consistente, entonces, para toda p, o T ` p, o T ` p, o

no prueba ninguna, pero no puede probar ambas.
Demostracin.
Probamos la formulacin equivalente: si T ` p y T ` p, entonces T es
inconsistente.
Usando el axioma 7: Por un lado con p = (p = ), T ` p, y modus
ponens, obtenemos T ` p = . Por otro lado, usando T ` p y modus ponens,
obtenemos T `.
Teorema 1.7. Si T 0 p, entonces T {p} es consistente. Por tanto T es

consistente.
Demostracin.
Vamos a reescribir lo que queremos probar como:
Si T {p} es inconsistente, entonces T ` p.
Si T {p} es inconsistente podemos escribir
T {p} `
Por el teorema de la deduccin
T ` p =
Por el axioma 8, que dice:

(p = ) = p
tomando (p = ) = p y aplicando modus ponens, obtenemos T ` p.
Teora Definicin 1.14 Teora completa. T es completa si es consistente y p F BF (L),

completa o T ` p o T ` p.
11 de 102
Teorema 1.8 (Teorema de Lindenbaum). Toda teora consistente puede exten-

derse a una teora completa.
Demostracin. En esta demostracin nos apoyaremos en el Lema de Zorn.

Sea T una teora consistente y sea P el conjunto de todas las teoras consistentes
que extienden a T , definimos un orden parcial en P mediante inclusin:
T1 T2 T1 T2
Sea {T } una cadena en P .

Si T es consistente, entonces es una cota superior de la cadena.
Puesto que todas las T son consistentes, la unin ser consistente.
Demostracin. Queremos probar que:

[ [
T ` = T ` T 0 = T 0

Realizaremos la prueba por reduccin al absurdo.

Sea p1 , . . . , pn = una prueba formal de . Entonces, T1 ` p1 , T2 T1
tal que T2 ` p2 , . . . , Tn Tn1 tal que Tn ` pn .
Observacin: Al final del procedimiento que acabamos de definir llegamos a

una teora Tn que contiene a todos los pi y que, por tanto Tn `. Pero estbamos
considerando que todas las Ti eran consistentes, por lo que acabamos de llegar a
una contradiccin.
Queda claro pues que la unin de teoras consistentes es consistente.
Por el lema de Zorn sabemos que P = T tiene un elemento maximal M ,

S
que contiene a T . Por tanto M P , lo que implica que M es consistente.
Adems, por ser M maximal tenemos que p M ` p M ` p puesto que de
no ser as, tanto M {p} como M {p} seran consistentes y extenderan T por
lo que perteneceran a P . Puesto que M es el elemento maximal de P tenemos que
M {p} M = p M y M {p} M = p M con lo que M no
sera consistente.
Queda claro pues que M es la extensin completa de la teora que estbamos
buscando.
Teorema 1.9 (Teorema de completitud II). T es consistente T tiene un

modelo.
12 de 102
Demostracin.
=: Por validez, T ` p = T p. Si T es inconsistente, T `, luego

T . Como para toda valoracin booleana, () = 0, ninguna satisface
a T.
=: Sea T consistente, queremos probar que tiene un modelo. Por el teorema

de Lindenbaum (1.8), existe una M T M es completa, es decir, M es
consistente y p F BF (L), o M ` p o M ` p.
Definimos (p) = 1 M ` p, y (p) = 0 M 0 p.
est definida sobre el conjunto F BF (L), y (p) = 1 p M , y por tanto
p T .
Como {, } es un sistema completo de conectivas, podemos suponer que
L = A{}. Para ver que es una valoracin booleana, hay que comprobar
1. (p) = 1 + (p) (mod 2).

Si M ` p, entonces M 0 p (por consistencia), luego
1 = (p) = 1 + (p) = 1 + 0
Si M 0 p, entonces M ` p, y
0 = (p) = 1 + (p) (mod 2) = 1 + 1 (mod 2)
2. (p q) = (p) (q). Si M ` p o M ` q, entonces, por p = (p q)

o q = (p q), que es el axioma 2, y modus ponens, obtenemos
M `pq
Por definicin de ,
(p q) = 1 = max{(p), (q)} = (p) (q)
Si M ` p y M ` q, entonces, usando el axioma 3: p = (q =

(p q)) y modus ponens dos veces, obtenemos:
M ` (p q)
En este caso, (p q) = 0 = (p) (q).
Teorema 1.10 (Teorema de compacidad). Si todo subconjunto finito de una

teora T tiene un modelo, entonces T tiene un modelo.
13 de 102
Demostracin. Como todo subconjunto finito de T tiene un modelo, todo subcon-

junto finito es consistente, luego T es consistente.
De otro modo, si T `, existe una demostracin p1 , . . . , pn = usando las
premisas en T . Pero T {p1 , . . . , pn1 } ` y es finito.
Por 1.9, T tiene un modelo.
Hecho por Edu. Se aceptan correcciones.
Supongamos que todo subconjunto finito de una teora T tiene un modelo. Por
el 1.9, dichos subconjuntos son consistentes. (1)
Supongamos que T `. Como las pruebas formales son un conjunto finito de
proposiciones p1 , . . . , pn = que o bien son axiomas, o bien pertenecen a T , o bien
se obtienen por MP de dos anteriores, T {p1 , . . . , pn1 } = S es un subconjunto
finito de T tal que S `, luego S es inconsistente, contradiccin con (1).
Luego T es consistente, y por 1.9, tiene un modelo.
Observacin: Si es un modelo de T , tambin o es de todos sus subconjuntos

finitos, luego la otra direccin en el teorema de compacidad es trivial.
Teorema 1.11. La lgica proposicional es decidible, es decir, existe un algoritmo

que nos permite saber si ` p o 0 p.
Demostracin. Escribimos la tabla de verdad de p.
Si (p) = 1 , entonces ` p
Si (p) = 0 para algn , entonces 0 p.
14 de 102
2. Lgica de primer orden (o de predicados)
2.1. Exposicin informal y ejemplos

Asumimos que todos los conjuntos usados para definir el lenguaje son disjuntos.
Usaremos:
Smbolos lgicos y de puntuacin:

{, , ), (, , }
Tambin usaremos los dems smbolos lgicos como abreviaciones.
Tendremos un conjunto infinito numerable de variables:
V ar = {v1 , v2 , . . .}
Aunque en la prctica usaremos x, y, z.
Un conjunto de constantes, que podra ser vaco:
Con = {C0 , C1 , . . .}
Funciones:
F un = {f0 , f1 , . . .}
Relaciones o predicados:
Rel = {R1 , R2 , . . .}
Cuantificadores:
{, }
Podemos considerar x(P (x)) como abreviacin de (x(P (x))).
No se puede cuantificar sobre constantes, funciones y relaciones en lgica de primer

orden. En segundo orden, se permite cuantificar sobre funciones y predicados.
Ejemplo: Expresiones de primer orden Sabemos que P (x) = P (x), donde x

es libre, es cierto. Por otro lado x(P (x) = P (x)) tiene el mismo significado, pero
x ahora es una variable ligada al cuantificador.
Ejemplo: Expresin de segundo orden La expresin

P x(P (x) = P (x))
es una expresin de segundo orden al estar cuantificando sobre predicados.
Principio de induccin matemtica en N:

P ( P (0) (n(P (n) = P (n + 1))) = n(P (n)))
Es una frmula de segundo orden.
15 de 102
En una lgica de primer orden, en vez de principio, tenemos un esquema de princi-

pios: Un principio de induccin por cada P .
Ejemplo: Axiomas de la teora de grupos: Lenguaje LG
Axiomas:
1 : xyz((x y) z) = (x (y z))
2 : x(x e = e x = x)
3 : xy(x y = e)
Funciones:
F un = {}
Relaciones:
Rel = {=}
Constantes:
Con = {e}
Un grupo es cualquier modelo de TG = {1 , 2 , 3 }.

Veamos ahora si podemos demostrar, a partir de TG la proposicin
: xy(x y = y x)
Es decir, queremos ver si TG ` .

En esta ocasin es algo sencillo ver que si G es no abeliano, entonces G 2 , como
conclusin tenemos TG 0 . Es decir, un G no abeliano sera un modelo de TG , puesto
que satisface 1 , 2 y 3 pero no es conmutativo y por tanto no satisface 4 .
Esto es un ejemplo de que el teorema de validez tambin es cierto en lgica de
primer orden.
TG ` = TG
Equivalentemente
TG 2 = TG 0
Podemos probar entonces que TG ` ? No, porque si tomamos un conjunto G2

abeliano, entonces G2 2 y por tanto, por validez, TG 0 .
Como conclusin, tenemos que TG no es una teora completa.
Clausura Definicin 2.1 Clausura universal. La clausura universal de es x1 , x2 , . . . , xn ,

universal donde x1 , x2 , . . . , xn son todas las variables que aparecen libres en .
Abreviacin: x z ((x)) es abreviacin de x((x z) (x)).
Abreviacin: !x((x)) abrevia x((x) ((y)( = y = x))).
16 de 102
Ejemplo: La clausura universal de x < 5 + y es
xy(x < 5 + y)
que tiene valor de verdad falso.
2.2. Axiomas de ZFC (Zermelo-Fraenkel con Eleccin)

Todos son conjuntos, hereditarios y bien fundados. No hay urelementos 1 o tomos.
1. Axioma del conjunto vaco Existe un conjunto vaco, representado por .

Formalmente:
z(x(x / z))
(En el lenguaje de la teora de conjuntos LS , tenemos las relaciones binarias
{, =}. Por otro lado F un : , Cons : ).
2. Axioma de extensionalidad. Dos conjuntos son iguales nicamente si contie-

nen los mismo elementos. Formalmente:
xy(z(z x z y) x = y)
Corolario 2.1. El conjunto vaco es nico.
3. Esquema axiomtico de especificacin2 . Sea (u) una frmula de un len-

guaje de primer orden que contenga una variable libre v. Entonces, para cualquier
conjunto x existe un conjunto y cuyos elementos son aquellos elementos de a y
x que cumplen (a). Formalmente:
zyx(x y ((x z) ))
Las FBF permiten definir subconjuntos y hablar de subconjuntos permite evitar

La parado- la paradoja de Russel:
ja de Rus-
sel Tenemos un axioma por cada F BF (LS ), que se define formalmente como:
zyx(x y ((x z) (x)))
Si no tuviramos z, el axioma quedara as.
yx(x y (x))
Si tomamos : x
/ x ( (x x))
yx(x y x
/ x)
Sabemos que y, digamos y0 .
x(x y0 x
/ x)
1
Se utiliza el prefijo alemn ur que significa primordial
2
Tambin conocido como esquema de axiomas de compresin
17 de 102
Como tenemos el cuantificador x, podemos sustituir x por y0 , obteniendo

y0 y0 y0
/ y0
Que es una contradiccin.
Para evitar llegar a esta contradiccin aadimos z como se ha hecho.
Observacin:
{z1 , . . . , zn } es un conjunto.
S(n) = {0, . . . , n} es un conjunto.
y = {1, . . . , n} = {x S(n) x > 0} es un conjunto.
La funcin f (i) = zi es una funcin (conjunto de pares ordenados). Por el axioma
de reemplazo, el rango f es un conjunto. Donde f : {1, . . . , n} {z1 , . . . , zn }.
4. Axioma de emparejamiento. Si x e y son conjuntos, el par {x, y} es un
conjunto. Si z es un conjunto, {{x, y}, z} es un conjunto. Si x = y, entonces
obtenemos {x, x} = {x}. Formalmente

xyzu(u z (u = x) (u = y) )
z es {x, y}, si x = y, z es {x, x} = {x}.
Antes de seguir enunciado los axiomas veamos algunas definiciones de trminos ya

conocidos vistos desde otro enfoque:
Los natu- Definicin 2.2 Los naturales.

rales
0 :=
1 := {} (por emparejamiento o partes cuando lo veamos).
2 := {, {}} = {0, 1} (por emparejamiento).
3 := {1, 2, 3} = {, {}, {, {}}} (Por el axioma 4).
Sucesor Definicin 2.3 Sucesor. El sucesor de n, S(n) es

S(n) = {0, 1, 2, . . . , n}
Suma Definicin 2.4 Suma en los naturales. n + 1 := S(n). Si hemos definido n + m,

en los entonces n + m + 1 := S(n + m).
naturales
Observacin: A partir de aqu podemos definir todo n N como un conjunto, pues

n = S(n 1) = {0, 1, ..., n 1}
Producto Definicin 2.5 Producto de los naturales. En cuanto al producto:

de los
naturales
18 de 102
n0=0
n1=n
Si n m est definido, entonces n(m + 1) = n (m + 1) = n m + n.
Menor Definicin 2.6 Menor.

n < m n m
Usando los axiomas vistos, tenemos que cada n es un conjunto, pero nada nos dice
que N := w sea un conjunto, o que exista un conjunto infinito.
Prosigamos viendo axiomas de ZFE
5. Axioma de la unin.SDada cualquier coleccin de conjuntos C, existe un con-

junto representado por C llamado unin de C, que contiene todos los elementos
de cada conjunto C. Esto es:
xyz(z y u((u x) (z u)))
Se usa al definir
S(n) = {0, 1, . . . , n} = n {n}
Nos permite definir cada n como un conjunto, pero nada nos dice que N sea un
conjunto.
Ejemplo: Sea X = {1, {2}, {2, 3}}, entonces
X = {0, 2, 3}
porque 1 = {}.
6. Esquema axiomtico de reemplazo. Si (a, b) es una sentencia tal que

para cualquier elemento a de un conjunto x el conjunto y = {b|(a, b)} existe,
entonces existe una funcin f : x 7 y tal que f (z) = y. Formalmente

a x a((!y((x, y)))) = (zx ay z((x, y)))
Este axioma nos dice que para definir una funcin, Ranf debe pertenecer a un
conjunto preexistente. En particular, Ranf no es cofinal en el universo de los
conjuntos.
7. Axioma de fundacin.3 . Para todo conjunto no vaco x esite un subconjunto

y x tal que x y =

x (x 6= ) = (y x(z x(z
/ y)))
3
Tambin conocido como axioma de regularidad
19 de 102
Este axioma implica que para todo conjunto z, z / z. Supongamos que existe
un z tal que z z. Entonces, aplicamos el axioma de fundacin al conjunto {z},
porque z no es vaco (al contener a z). {z} es un conjunto por pares y extensin,
{z, z} = {z} o por compresin: {y : y z y = z}.
Por el axioma, y {z} tal que z y = . Pero y = z luego z y = z 6= .
Luego para todo conjunto, z
/ z.
Observacin: Si hubiese un z z, entonces z 3 z 3 z 3 z . . .. Obtendramos

una cadena infinita descendiente de . Pude demostrarse que este axioma prohbe
todas las cadenas infinitas descendientes y los bucles tales como z1 3 z2 3 . . . 3
zn 3 z1 .
8. Axioma del conjunto potencia4 . Para cualquier conjunto x existe otro con-
junto, representado por P(x), que contiene a todos los subconjuntos de x. For-
malmente.
xyz(z y a(a z = a x))
Par ordenado: si x e y son conjuntos (x, y) := {x, {x, y}} podemos definir
funciones, relaciones, etc. Hemos construido cada n con n elementos. Sea X un
conjunto ya construido (por tanto, finito)
X, Y N, f : X Y
Ranf N = {0, . . . , N 1} conjunto ya construido. Podemos tomar N =

max{f (x) : x X} + 1.
En general Card(P(X)) = 2Card(X) .
Abreviacin: Usamos z X w((w z) = (w X)) Xyz(z
X x y).
Nota aleatoria:
R1 = R{} = {(, x) : x R}
R2 = R{0,1} = {f : (0, 1) R} = {(x0 , x1 ) : x0 , x1 R}
R0 = R = {f : R} (es elegir 0 elementos de R, que es lo mismo
que rechazarlos todos, lo cual slo hay una forma de hacerlo, que es nuestra
constante).
9. Axioma de infinitud. Existe un conjunto x tal que x y tal que si y x,
entonces y {y} x. En smbolos:
x(( x) (y(y x = y {y} x)))
A partir de este conjunto, definimos N = exigiendo que todo elemento distinto

del 0 sea sucesor de otro elemento. Sea X un conjunto dado por el axioma de
infinitud.

N := {x X : y X(x = y {y}) (w x(w = 0 (z(w = z {z}1)))) }
4
Tambin conocido como axioma de partes
20 de 102
Ejemplo informal:
N0 := {(0, n) : n N} N
N1 := {(1, n) : n N} N
Luego N0 N1 con el orden del diccionario es {(0, 0), (0, 1), (0, 2), . . . , (1, 0), (1, 1), (1, 2), . . .}
Por induccin: Sea S N. Si 0 S (n(n S = n + 1 S)). En
conclusin, N S.(S N = N = S)
10. Axioma de eleccin. Dada una familia de conjuntos no vacos podemos co-
ger un elemento de cada conjunto. Este axioma puede expresarse de manera
equivalente a, dado un conjunto cualquiera x, existe una funcin f que elige un
elemento de cada conjunto no vaco de x. Formalmente

X(
/ X = f : X X(t x(f (t) t)) )
Hay que notar que al cuantificar funciones estamos pasando a lgica de segundo
orden.
Si C = {A : } es una coleccin de conjuntos disjuntos no vacos,
f : C C tal que
A C, f (A ) A
Luego escrito en primer orden:

yu(u P (y)zw (z u w u) = (z 6= (z = w z w = )) =
x P (y)(z uv(x z = {v})))
El axioma de eleccin es equivalente al lema de Zorn, que es equivalente a que
todo conjunto tiene un buen orden.
Algunas consecuencias:
Todo conjunto infinito contiene un conjunto numerable.

Toda relacin contiene a una funcin con el mismo dominio.
Todo espacio vectorial tiene una base.
Existen conjuntos en [0, 1] que no son medibles con respecto a la medida
de Lebesgue.
Si AP (axiomas de Peano) es completa, puede extenderse a una teora
completa.
2.3. Axiomas de Peano

Los 5 Axiomas de Peano son:
1. Existe un nmero natural 1. En otros trminos, 1 est en N, el conjunto de los

nmeros naturales.
2. Todo nmero natural n tiene un sucesor n* (este axioma es usado para definir
posteriormente la suma).
21 de 102
3. 1 no es el sucesor de algn nmero natural.
4. Si hay dos nmeros naturales n y m con el mismo sucesor, entonces n y m son

el mismo nmero natural.
5. Si 1 pertenece a un conjunto K de nmeros naturales, y dado un elemento

cualquiera n, el sucesor n* tambin pertenece al conjunto K, entonces el conjunto
K debe ser el conjunto de todos los nmeros naturales. Este axioma es el principio
de induccin matemtica.
Teorema 2.2. N es nico en el sentido de que si A y B satisfacen los axiomas

de Peano, entonces A = B = N.
Demostracin. Por hiptesis, 0 A B.

Si n A B entonces n + 1 A B. Por lo tanto A = B = A B = N.
Hasta ahora hemos visto que
Los axiomas de la teora de grupos: admiten muchos modelos muy distintos.
Axioma de Peano: intentan caracterizar a N. Hay varios conjuntos que satisfacen

los axiomas de Peano, estos modelos son todos isomorfos.
La gran ventaja que nos aporta la lgica de primer orden es que permite expresar
los axiomas de ZFC que fundamentan la mayor parte de las matemticas (en particular
ZF Axiomas de Peano (1 orden))
2.4. Introduccin a lgicas de segundo orden

En la prctica, usamos constantemente lgicas de segundo orden sin preocuparnos
de si los conjuntos son demasiado grandes
Ejemplo: Teorema: Sea K un espacio topolgico compacto y sea f : K R

continua. Entonces f alcanza sus valores mximo y mnimo.
Traduccin semiformal: Sea C= clase de todos los conjuntos compactos, y sea:
Fk = {f : K R|f es continua}
Entonces nos queda:

K C f Fk a, b, c K x K f (a) f (x) f (b)
OJO: C es el conjunto de todos los conjuntos.
22 de 102
De modo que, una manera de interpretar el teorema anterior en una lgica de

primer orden es considerar que tenemos un esquema de teoremas, es decir, tenemos
un teorema por cada (K, f ) donde K y f pueden describirse en el lenguaje.
No usamos la lgica de 2 orden todo el tiempo porque compacidad, y por tanto
completitud, fallan.
Teorema 2.3. Existe una teora T en un lenguaje de 2 orden, tal que, todo
subconjunto finito de T tiene un modelo, pero T no tiene ningn modelo.
Demostracin. Si consideramos la teora , donde nos dice que existe una

funcin inyectiva que no es sobreyectiva, vemos que todos sus modelos son infinitos
(todas las funciones que satisfacen la teora deben moverse entre conjuntos infinitos.)

: f x y f (x) = f (y) x = y zx z 6= f (x)
Por otro lado, es claro que todo modelo de es finito.

Vamos a considerar el conjunto de teoras n , cada una de las cuales nos dice
que por lo menos hay n objetos distintos:
2 : v1 v2 (v1 6= v2 )

3 : v1 , v2 , v3 (v1 6= v2 ) (v2 6= v3 ) (v1 6= v3 )
..
.

n : v1 , ..., vn 1i<jn vi 6= vj
Consideramos ahora la teora formada por la unin de estas teoras.

T = , n : n N \ {0, 1}
Sea T un subconjunto finito, si = { }, 1 = {0} es un modelo.

Si para algn n, n , llamamos N al natural ms grande tal que n .
Entonces N = {0, 1, ..., N 1} es un modelo de { } y, por tanto, un modelo
de .
Pero T no tiene modelos, porque cualquier modelo debe ser a la vez finito (por
) y contener al menos n elementos distintos n N, con lo que llegamos a
una contradiccin.
23 de 102
2.5. Completitud
Teorema 2.4 (Teorema de completitud). Sea T una teora en el lenguaje de

primer orden, existen dos versiones de este teorema.
1. T ` T
2. T es consistente T tiene un modelo
Demostracin.
1. Ya hemos visto como demostrar ambos sentidos de la implicacin

) Por validez.
) Por Gdel (Henkin)
2. Es trivial y se deja como ejercicio para el lector.
Corolario: Compacidad: Sea T una teora en un lenguaje de primer orden. T tiene

un modelo todo subconjunto finito de T tiene un modelo.
En todos los lenguajes de primer orden siempre tenemos smbolos lgicos, inclu-
yendo, o no, igualdad, signos de puntuacin (parntesis y comas), cuantificador(es) y
variables, de modo que estos signos no se incluyen al describir un lenguaje.
Ejemplo: Lenguaje de la aritmtica
LArit = { 0, 1 , +, , <
|{z} }
|{z} |{z}
constantes funciones binarias relaciones binarias
Teorema 2.5 (Primer Teorema de incompletitud de Gdel). Sea T una teora en

(un lenguaje de primer orden) axiomatizable5 . Si el lenguaje contiene, al menos,
el lenguaje de la aritmtica y la teora contiene a los axiomas de Peano entonces
T consistente = T incompleta
5
Tenemos un procedimiento para comprobar si cada FBF es un axioma o no
24 de 102
Teorema 2.6 (Teorema de Presburger y Skolem). Each sentence in the languaje

of the structure (Z; 0, 1, +, , <) that is true in this structure is provable from the
axioms for ordered abelian groups with least positive element 1, augmented, for
each n = 2, 3, 4, ... by an axiom that says that for every a ther is a b such that
a = nb or a = nb + 1 or ... or a + nb + 1 + ... + 1 (with n disjuncts in total).
Moreover, there is an algorithm that, given any sentence in this languaje as
input, decides whether this sentence is true in (Z; 1, 0, +, , <).
Teorema 2.7 (Segundo Teorema de incompletitud de Gdel). Sea T una teora

en un lenguaje de primer orden axiomatizable y consistente, si T tiene, al menos,
el poder expresivo de la aritmtica de Peano, es posible escribir una sentencia que
llamaremos CON (T ), que puede interpretarse como T es consistente y que no
puede ser probada, es decir, T 0 CON (T )
Observacin: Si T es consistente entonces T 0 CON (T ).

CON (T ) puede interpretarse como T es consistente", luego existe un modelo a
de T con a CON (T ) y, por tanto, a 2 CON (T ).
En consecuencia, si T es consistente, entonces T {CON (T )} y T {CON (T )}
son extensiones consistentes de T , luego ambas teoras tienen modelos.
Observacin: Los axiomas de Peano son teoremas en ZF luego los resultados ante-
riores se aplican a ZF.
Teorema 2.8. Si ZF es consistente, entonces ZF 0 CON (ZF )
Teorema 2.9 (Teorema de Cantor). Cantor prob que
card(N) < card(R)
por diagonalizacin.
Adems, Cantor conjetur que no existe ningn conjunto E tal que
card(N) < card(E) < card(R)
A esta conjetura se la denomina la hiptesis del continuo (CH)
25 de 102
Aunque Cantor invirti mucho tiempo tratando de demostrar su conjetura, no fue

capaz de conseguir nada. Esta falta de xito se debi a que los axiomas ZF no son
suficientemente fuertes como para demostrar la conjetura.
Teorema 2.10. Si ZF es consistente, entonces tambin lo son:
1. ZF + C + CH (Gdel finales aos 30)
2. ZF + C + CH (Paul Cohen finales aos 60)
3. ZF + C + CH (Paul Cohen finales aos 60)
4. ZF C + CH (Paul Cohen finales aos 60)
Donde C representa el axioma de eleccin.
Llegados a este punto es recomendable para el lector la lectura del

apartado 2.3 del libro
2.6. Lenguajes y estructuras
Lenguaje Definicin 2.7 Lenguaje de primer orden. L es un lenguaje de primer orden si

de primer es unin disjunto de los siguiente conjuntos:
orden
1. Smbolos lgicos y de puntuacin
{, , =, ), (, ,00 }
2. Variables, que quedan representadas por el conjunto infinito numerable
V ar = {v0 , v1 , ...}
3. Constantes (podra ser vaco)
4. Funciones (podra ser vaco)
5. Relaciones o predicados (podra ser vaco)
6. Cuantificador {} considerando el cuantificador como negacin del .
Una L-estructura es una interpretacin del lenguaje L, y si T es una teora en

L entonces un modelo de T es una L-estructura donde todas las frmulas en T son
verdad.
Esta afirmacin establece una relacin entre diferentes trminos que an no hemos
definido. Vamos a verlos:
26 de 102
L- Definicin 2.8 L-estructura. Una L-estructura a es una 4-upla a = (A, C a , F a , Ra )

estructura donde
A 6= es el conjunto al que pertenecen las variables y al que se aplican los

cuantificadores
Por cada c Constantes de L existe ca C a asociada a c
Por cada f n-aria Funciones de L existe f a n-aria F a asociada a f
Por cada r n-aria Relaciones de L existe ra n-aria Ra asociada a r
Los trminos denotan objetos en la interpretacin, son equivalentes a nombres. As

las variables seran nombres comunes y las constantes nombres propios
Trmino Definicin 2.9 Trmino. Los trminos son la clase de frmulas ms pequea que se
obtiene mediante aplicacin de la siguiente regla
1. Las variables son trminos

2. Las constantes son trminos
3. Si t1 ...tn son trminos y f es una funcin n-aria entonces f (t1 , ...tn ) es un
trmino.
Frmula Definicin 2.10 Frmula atmica. Las frmulas atmicas son

atmica
1. Por cada relacin n-aria R y trminos t1 ...tn , R(t1 , ..., tn ) es una frmula at-
mica.
2. Si t1 , t2 son trminos entonces t1 = t2 es una frmula atmica.
Frmula Definicin 2.11 Frmula bien formada. Las frmulas (bien formadas) de L son la
bien clase ms pequea cerrada bajo las siguientes operaciones
formada
1. Las frmulas atmicas son frmulas
2. Si , son frmulas tambin lo son y
3. Si es una frmula tambin lo es x
Variable li- Definicin 2.12 variable ligada. Si x aparece en la frmula bajo el rango de un
gada cuantificador (ya sea o ), decimos que x es una variable ligada.
En caso contrario, es decir, si x aparece en pero no est cuantificada, decimos
Variable li- que x es una variable libre
bre
Frmula Definicin 2.13 Frmula cerrada. Decimos que es una frmula cerrada o sen-
cerrada tencia si no tiene variables libres.
27 de 102
Ejemplo: Reemplazo de variables Consideramos al frmula:

Z 1
y
xy dx =
0 2
donde la variable x est ligada por el dx e y est libre.

Vamos a ver qu trminos pueden reemplazar a la variable y.
Por lo que sabemos de matemticas tenemos claro que podemos sustituir la y por
cualquier otra variable distinta de x como z, t, v... y tambin puede sustituirse por
funciones como sin(y).
En general, podr sustituirse una variable por cualquier variable o funcin que no
dependa variables ligadas.
Ejemplo: Consideramos ahora la frmula

: x(x = y)
Podemos ver que el nico modelo de esta frmula ser aquel conjunto que est
formado por un nico elemento.
Dicho de forma ms tcnica, esta frmula es cierta en la L-estructura a si y slo si
card(A) = 1.
Obviamente, si en este mismo ejemplo sustituimos la y por una x, obtenemos la
frmula
: x(x = x)
que es cierta para todas las interpretaciones.
Proposicin 2.11. Si x aparece libre en una frmula , el trmino t puede sustituir

a x si ninguna de las variables de t se vuelve ligada al reemplazar a x por t.
En estos ejemplos hemos estado hablando de veracidad y falsedad de afirmaciones

sin haber definido previamente estos conceptos. Si bien es algo totalmente intuitivo y
casi trivial, es necesario tener una definicin formal de estos trminos.
Queremos por tanto una definicin que nos permite saber cundo es verdad en
a, es decir, cuando a . Para ello buscaremos una definicin inductiva en trminos
de subfrmulas ms cortas.
En particular queremos definir a x en trminos de a .
Una forma de dar sentido a a es extender el lenguaje L a LA = L {a, a A}
considerando la unin disjunta.
Ejemplo: Supongamos que tenemos L = {c, f, R}, a = (N, 0, S, )

Dada = x(cRx), queremos definir a en trminos de sentencias ms cortas.
Por cada n N, aadimos la constante n (a L), cuya interpretacin es n.
Entonces a , puesto que n, n N, c n, que es una sentencia ms corta que
.
28 de 102
Luego LN es la unin disjunta: LN = L {n : n N}
Consecuencia Definicin 2.14 Consecuencia lgica. Vamos a ver cundo a para Lsentencias.
lgica
Sea LA = L {a : a A} (unin disjunta), tenemos diferentes casos:
1. Sentencias atmicas
Sean t1 , . . . , tn , LA trminos sin variables diremos que
a t1 = t2 ta1 = ta2
y, adems, para toda relacin o predicado nario P ,
a P (t1 , . . . , tn ) (ta1 , . . . , tan ) P a
2. LA sentencias
Sean 1 y 2 LA -sentencias, entonces
a a 2 , a 1 2 a 2 1 a 2
3. Cuantificadores
a = x(x) a A, a (a)
Proposicin 2.12. Sea una frmula de LA , = (x1 , . . . , xn )
a a x1 , x2 , . . . , xn
o equivalentemente,
(a1 , . . . , an ) An = a (a1 , . . . , an )
2.7. Axiomas de la lgica de primer orden y reglas de de-

duccin
1. Axiomas proposicionales (los del libro) o a efectos de este curso, todas las
tautologas.
2. Axiomas de igualdad:
x=x
x = y = y = x

(x = y) (y = z) = x = z
Para toda P naria, x1 = y1 . . . xn = yn P (x1 , . . . , xn ) = P (y1 , . . . , yn )

Para toda funcin f naria, (x1 = y1 . . .xn = yn ) = f (x1 , . . . , xn ) =

f (y1 , . . . , yn )
29 de 102
3. Axioma de cuantificacin.
Si el trmino t puede sustituir en x, entonces
x(x) = (t|x)(= (t) abreviacin)
Teorema 2.13. Si es un axioma y a es una Lestructura, entonces a . Es

decir, los axiomas lgicos son verdad en todas las L-estructuras (interpretaciones).
Demostracin. Son verdad para las frmulas atmicas, por induccin. Por ejemplo,
a x = x. Las dems frmulas por induccin en el nmero de smbolos lgicos
(incluyendo cuantificadores).
2.8. Reglas de deduccin

1. Modus Ponens: De y = obtenemos .
2. Si x no aparece libre en , de = deducimos que = x.
Observacin: Estas reglas de deduccin preservan el valor de verdad:
1. Si a y a = , entonces a .
2. Si x no aparece libre en y a = entonces a 2 a .

Si a 2 , entonces a = cualquier otra cosa.
Si a , entonces, a .
Esto significa que a A (extendemos L {a : a A}, unin disjunta).
(a) = (a|x) es verdad en a. Luego es verdad que a x(x).
Muchas definiciones (y resultados) son enteramente anlogos a las de la lgica

proposicional.
Teora Definicin 2.15 Teora. = { : es una setencia de L, }
Prueba Definicin 2.16 Prueba. Como antes, slo que en vez de una regla de deduccin, hay
dos.
Notacin: ` .
Modelo Definicin 2.17 Modelo. a es un modelo de si
, a
30 de 102
Consecuencia Definicin 2.18 Consecuencia lgica. es una consecuencia lgica de la teora

lgica si para todo modelo a de , a .
Ejemplo: Si = {axiomas de la teora de grupos} y 1 es la sentencia que expresa

la conmutatividad, 1 no es consecuencia lgica de (hay grupos no conmutativos).
Si 2 expresa el hecho de que el inverso por la izquierda es igual que el inverso por
la derecha, entonces 2 es consecuencia lgica de .
Notacin: es consecuencia lgica de . es una nocin semntica
y ` es una nocin sintctica. ` significa que existe una demostracin formal lo
cual depende de los axiomas, de las reglas de deduccin y de las premisas.
Ejemplo: Vamos a probar que si x(x), entonces x(x) (cuestin

semntica).
Sea a cualquier modelo de .
x(x) a A, a (a)
Escogemos cualquier b A 6= . Entonces a (b), luego a x(x).
Trabajando con lgica proposicional vimos que era ms sencillo comprobar que
una FBF era consecuencia lgica, pues bastaba con construir su tabla de verdad, que
construir una demostracin o prueba de la frmula a partir de los axiomas.
Algo similar ocurre en lgica de predicados.
Ejemplo: Demostramos que, siendo z una variable que no aparece en se cumple:

x(x) x(z) = z(z|x)
Sea a x(x), es decir
a A (a) = (a|x)
es cierto en a.
Por tanto, z(z) es verdad en a.
Ejemplo: Vamos a probar

x(x) ` z(z)
Realizaremos la demostracin por pasos:
1. Invocamos la premisa de la demostracin:

x(x)
2. Invocamos ahora el axioma de cuantificacin:

x(x) (x)
31 de 102
3. Aplicamos Modus Ponens con lo que obtenemos:

(z)
4. Apoyndonos en el apartado a) del ejercicio 4 de la hoja 6, invocamos:

` x
5. Combinando los dos ltimos resultados llegamos a:

(z) ` z(z)
Proposicin 2.14. Toda teora consistente puede extenderse a una teora M consis-
tente y maximal (con respecto a la inclusin).
La demostracin de esta proposicin se basa en el empleo del Teorema de Linden-

baum usando Zorn.
Proposicin 2.15. La teora M consistente y maximal, mencionada en la proposicin
anterior, es completa
Demostracin. Sabemos que
, M M
puesto que la teora es maximal, si ,

/ M podramos aadir una de ellas a M
con lo que entonces M no sera maximal. Por tanto no es posible esta situacin.
Por tanto, siempre tendremos una de dos:
M ` M `
siendo la demostracin trivial y de una sola lnea pues o deben pertenecer a

M , como hemos visto en el prrafo anterior.
Proposicin 2.16. Si es completa, entonces es consistente y tenemos que

` `
Por tanto
M = { : ` }
es una teora maximal, consistente y contiene a
De forma general, si queremos demostrar la completitud de una teora, los pasos a

seguir son:
Demostrar validez, es decir, ver que:

` =
Razn: es un axioma (verdad en todas las interpretaciones) o se deriva de

frmulas ya probadas mediante las reglas de deduccin, luego es verdad en todas
las interpretaciones.
32 de 102
Demostrar suficiencia, es decir, ver que:
= `
Razn: La idea es muy similar a la vista en el tema de lgica proposicional.

Si {} es inconsistente, entonces los axiomas y las reglas de deduccin son
suficientemente fuertes para demostrar que ` .
Equivalentemente, si 0 entones {} es consistente.
Para cada , siempre que 0 , aadimos a , con lo que mantenemos
siempre la consistencia.
En cualquier modelo de {}, es falsa luego 2 . As llegamos a:
0 = 2
que es justo lo que queramos demostrar

Clave de esta demostracin: Las teoras consistentes tienen modelos (por el
teorema de completitud, versin 2)
2.9. Contenidos para examen

Para el segundo examen de la asignatura ser de vital importancia aprender los
enunciados y demostraciones de los siguientes teoremas:
1. Hay una teora T en un lenguaje de 2 orden tal que T no tiene modelos,

pero todo subconjunto finito de T si tiene un modelo.
Demostracin. Este es el teorema 2.3 y ya vimos su demostracin.
2. Sea una teora en un lenguaje de primer orden, y sea una sentencia.

Si 0 , entonces {} es consistente.
Demostracin.
Para llevar a cabo esta demostracin nos apoyaremos en el teorema de la

deduccin, que nos dice lo siguiente:
Sea una teora y una sentencia. Si {} ` (donde es una
frmula), entonces ` ( ).
Para probar este teorema6 nos basaremos en la formulacin equivalente:
Si {} es inconsistente, entonces ` .
Supongamos que {} `.
Por el teorema de la deduccin, como no tiene variables libres, concluimos
que ` ( ).
33 de 102
Por otro lado, vemos que

( )
es una tautologa. Si es verdadero, entonces el consecuente es verdadero,
mientras que si es falso, el antecedente es falso.
Otra forma de verlo es escribir la tabla de verdad:
( )
1 0 1 1
0 1 0 1
Finalmente, por Modus Ponens, podemos concluir que
que es justo lo que queremos probar.
3. De Completitud II, probar Completitud I (direccin de adecuacin).

Probar que si toda teora consistente tiene un modelo,
= `
Demostracin. Supongamos que . Es decir, si = (x1 , . . . , xn )

(es decir, todas las variables libres de se encuentran entre las x1 , . . . , xn ),
entonces := x1 , . . . , xn .
Por definicin {} no tiene modelos, de modo que es inconsistente
(Completitud 2).
Como {} es inconsistente, entonces ` (por el teorema anterior).
Como x1 puede sustituir a x1 , de ` , el axioma de cuantificacin y Modus
Ponens obtenemos ` (x2 , . . . , xn ).
Repitiendo para x2 , . . . , xn obtenemos que ` .
Isomorfismo Definicin 2.19 Isomorfismo. Sea a = {A, C a , F a , Ra } y b = {B, C b , F b , Rb }. Dadas

2 interpretaciones de L, Lestructuras a y b, h es un isomorfismo de Lestructuras
si
h : A B es biyectiva.
h(C a ) = C b
a1 , . . . , an A, f a : An A, se tiene que
h(f a (a1 , . . . , an )) = f b (h(a1 ), . . . , h(an ))

6
No el de deduccin que acabamos de mencionar sino el teorema al que pertenece esta demostra-
cin.
34 de 102
P a n-aria, a1 , . . . , an A se tiene que
(a1 , . . . , an ) Ra (h(a1 ), . . . , h(an )) Rb
Teorema 2.17. Dos Lestructuras isomorfas satisfacen las mismas frmulas de

L. Se dice que, a y b son elementalmente equivalentes.
En el teorema, elementalmente se refiere a primer orden (si fuera segundo orden se

dira secundariamente, etc.) y equivalentes a que satisfacen las mismas frmulas.
2.10. Nuestra historia hasta ahora

Vamos a ver un pequeo resumen de lo que hemos hecho hasta ahora a fin de
poder obtener una visin global.
1. Hemos empleado la teora elemental de N, que no es ms que la induccin, para

probar validez, es decir:
` =
2. Hemos empleado lenguajes de primer orden para enunciar los axiomas de ZFC.
3. ZFC (Zorn C) = adecuacin, es decir:
|= = `
Observacin: Esto nos llev al teorema de completitud 2: Si es consistente

entonces tiene un modelo.
4. Para comprobar si una teora es consistente nos basta con encontrar un modelo.
No obstante, en lgica proposicional no es tan sencillo encontrar un modelo
puesto que, por definicin, si a es un modelo, tenemos que ver si a |=
a |= .
La pregunta es clara: Cmo construimos a?
Solucin: Extendemos a una teora maximal consistente con lo que pode-
mos ver:
= a |=
= a |=
5. En el caso de la lgica proposicional extendamos la teora a una teora maximal

consistente M y el modelo era 1M , siendo 1M (p) = 1 si p M y 1M (p) = 0
en caso contrario.
En el caso de la lgica de primer orden necesitamos construir
a = (A, C a , F a , Ra )
35 de 102
Para ello lo primero que necesitamos es el universo A 6= .

La extensin maximal consistente de la teora nos dar las constantes C a A,
las funciones n-arias f a : A 7 A y las relaciones n-arias pa An .
Pero, de dnde sacamos A? Bsicamente lo construiremos tomando todos los
trminos constantes del lenguaje.
Trmino Definicin 2.20 Trmino constante. Los trminos constantes t son aquellos
constante que no tienen variables.
Denotamos el conjunto de trminos constantes de L como Tn .
Para construir A simplemente definimos A = Tn y suponemos que el lenguaje
tiene al menos una constante para garantizar que A =
6 .
Sin embargo tenemos dos posibles problemas:
a) Existencia de testigos.
Puesto que una vez tengamos el universo A, vamos a extender a una
teora maximal empleando Zorn, podra ocurrir que en esta extensin nos
fastidie nuestra teora al aadir alguna sentencia no deseada.
Ejemplo: Sea L = {c}, es sencillo ver que TL = {c} = A.

Si tenemos la teora = {x((x = c))} definida sobre el lenguaje L,
podemos ver que A no es modelo de la teora.
La forma de resolver el problema sera tomar c1 6= c y extender L a L{c1 }.

Adems, debemos aadir la sentencia (c1 = c) a y comprobamos que
esta extensin es consistente, cosa trivial en este caso.
Finalmente tenemos que extender (c1 = c) a una teora maximal

consistente.
Observacin: Esta extensin (que haremos empleando el lemma de Zorn)

es parte clave del problema.
Al aplicar Zorn, sabemos que existe una extensin pero no tenemos ni idea
de cmo es la extensin ni de que sentencias aade a la teora inicial. Por
tanto, podra ocurrir que, a partir de extendamos a tal que
c1 = c 0
con lo que se nos fastidiara el invento.

Al aadir la sentencia (c1 = c) a , toda extensin de cumplir que
c1 6= c.
Con los pasos seguidos en el ejemplo seguimos teniendo varios problemas

obvios. Antes de verlos vamos a aadir algunas definiciones a nuestro vo-
cabulario.
36 de 102
Testigo de Definicin 2.21 Testigo de . Si |= = x(x), decimos que c es

un testigo de si |= (c ).
Volviendo al ejemplo anterior:
Ejemplo: Tenemos que L1 = {c, c }, y 1 es una teora maximal y

consistente que extiende

(c1 = c)
Puesto que 1 es consistente, toda sentencia debe poder ser deducible a

partir de 1 (y por tanto pertenecer a 1 puesto que es maximal) o serlo
su negada.
Es decir:
z((x 6= c) z 6= c1 ) 1
o bien
z((x 6= c) z 6= c1 ) 1
En el primer caso tenemos una sentencia 1 sin testigo.
La solucin obvia a este problema es repetir el procedimiento obteniendo
2 , L2 siendo 2 una teora maximal consistente. Finalmente tomamos la
unin numerable.
Aqu volvemos a tener el mismo problema as que debemos repetir el mismo
procedimiento.
Repetimos, definiendo extensiones L L1 L2 . . ., y 1 2 . . ..
Tomamos L = n=1 Ln y = n=1 n . Entonces es completa y

tiene testigos.
b) El problema de la igualdad
Evidentemente este problema no se da en los lenguajes sin igualdad. No
obstante, en los casos que vamos a tratar en clase vamos a considerar
siempre lenguajes con igualdad.
Ejemplo: Consideremos el lenguaje L = {c, S1 , +1 } y la teora de Z3

es decir, tomamos el conjunto de todas las sentencias de L que son ciertas
en Z3 .
Tomamos la interpretacin T = {c, s1 (c), S1 (S1 (c)), ...} considerando c
como el elemento neutro (el 0) y S1 como la funcin sucesor en Z.
Por definicin de la teora tenemos que
` c = S1 (c)3
Por tanto, podemos definir
A = {[c], [S1 (c)], [S1 (S1 (c))]}
Denotamos [c] = ca para todo c L . Si f L es una funcin n-aria

definimos
f a ([t1 ], [t2 ], ..., [tn ]) = [f (t1 , t2 , ..., tn )]
37 de 102
lo que nos permite definir F a como el conjunto de funciones como la que

acabamos de ver.
Por ltimo tenemos que definir las relaciones, cosa que haremos mediante
la siguiente definicin de las mismas:
([t1 ], [t2 ], ..., [tn ]) P a ` P (t1 , t2 , ..., tn )
Ahora slo nos quedara comprobar que, efectivamente a = (A, C a , F a , Ra )

es un modelo de . Vamos a ello.
Supongamos que ` . Si es atmica, es = (t1 = t + 2) o a =
P (t1 , ..., tn ), entonces a por construccin.
Para otras el resultado se obtiene por induccin en el nmero de smbolos
lgicos.
Tras todas estas divagacin que nos acercan a la comprensin del problema y de
su solucin, vamos a formalizarlo.
Teorema 2.18. Si es una teora consistente, entonces tiene un modelo a =

(A, C a , F a , Ra )
Demostracin. La idea de la demostracin consiste en empezar con un lenguaje L,

que contiene al menos una constante, y .
Ahora definimos una serie de lenguajes y de teoras de la forma:
L L1 L2 ...
1 2 ...
La forma de construir estos lenguajes y teoras es la siguiente: Por cada =

x (x) en Ln aadimos una nueva constante c a Ln formando Ln+1 y aadimos
(c ) a la teora n obteniendo n+1 , que sera una teora consistente y maximal.
Tomamos ahora [ [
L = Ln y = n
n1 n1
que nos permite afirmar que es completa y tiene testigos.
Demostracin. Si , existe un n tal que Ln .

Entonces tenemos dos opciones:
luego es completa.
Sea = x(x) , existe un N tal que N , luego existen c LN +1
y (c ) N +1
38 de 102
Nos gustara tomar A = TL que sera el conjunto de trminos sin variables de

L . Entonces c TL luego tiene un testigo.
Una vez hemos solventado el problema de la existencia de testigos, vamos a
por el problema de la igualdad.
Supongamos que t1 , t2 L y ` t1 = t2 . Definimos la relacin como:
t1 t2 ` t1 = t2
Una vez tenemos la relacin definimos el conjunto cociente:
A = TL /
Observacin: Si L tiene cardinal K (infinito), entonces L y tambin tienen

cardinal K. En concreto si L es numerable lo sern L y .
Cardinalidad Definicin 2.22 Cardinalidad. Decimos que a = (A, C a , F a , Ra ) tiene cardinalidad

si card(A) = .
Teorema 2.19 (Teorema de Lowenheinn-Skolem). Si card(L) = (infinito) y

es una Lteora consistente. Entonces tiene un modelo de cardinalidad . En
particular, si L es numerable, entonces tiene un modelo numerable.
Observacin: card(A) puede ser estrictamente menor que card(L).

Corolario 2.20. Si ZFC tiene un modelo entonces tiene un modelo numerable.
Paradoja de Skolem: R no es numerable. Cmo puede tener modelos nume-

rables?. B numerable significa que existe una biyeccin de B en N, o en algn
subconjunto de N.
Solucin: Si a es un modelo numerable de ZFC, externamente todos los conjun-
tos infinitos en A, tienen card(N). Pero internamente, card(Ra ) > card(Na ) porque
no existe en a ninguna biyeccin de Ra en Na .
Teorema 2.21 (Teorema de Lwenheim-Skolem generalizado). Si la Lteora

tiene modelos infinitos, entonces, card(L), tiene modelos de cardinalidad
.
Test de Vaught: Sea una Lteora consistente, con L numerable. Si todos los
modelos numerables de son isomorfos, entonces la es completa.
39 de 102
Demostracin. Si no es completa, 0 , 0 . Luego {} y

{} son teoras consistentes, luego tienen modelos a1 y a2 respectivamente.
a1 y a2 no son elementalmente equivalentes, luego no son isomorfos.
Observacin: Existen generalizaciones del test de Vaught para otras cardinalidades.
40 de 102
3. Computacin
3.1. Motivacin
La ecuacin diofntica: x2 + y 2 = z 2 tiene soluciones no triviales en enteros, por
ejemplo, x = 3, y = 4, z = 5. Si generalizamos esta ecuacin escribiendo xn +y n = z n ,
para n > 2, podemos ver que tiene soluciones triviales (x = y = z = 0). No obstante,
es sabido que en este segundo caso la ecuacin no tiene soluciones no triviales en
enteros (Wiles, 1995).
X problema de Hilbert: Este problema consiste en hallar un algoritmo que, dada

cualquier ecuacin diofntica, nos diga si esta tiene soluciones en enteros o no.
Es decir, dado cualquier polinomio con coeficientes en Z, dependiente de cual-
quier nmero de variables, x1 , . . . , xm , el algoritmo decide si p(x1 , . . . , xm ) = 0 tiene
soluciones en enteros o no.
Observacin: Se pide un slo algoritmo que debe funcionar para todas las ecua-
ciones diofnticas.
En 1970, Yuri Matiyasevich, basndose en trabajos previos de Martin Davies, Hilary
Putnam y Julia Robinson, demostr que no existe tal algoritmo.
Informalmente, el teorema de incompletitud de Gdel nos dice que dada cualquier
axiomatizacin (computable) de la aritmtica, la teora resultante es incompleta. Ms
precisamente, tenemos:
Teorema 3.1. Sea N = (N, 0, s, +, , <) el modelo estndar de los naturales y

sea una teora axiomatizable de sentencias verdaderas en N .
Entonces existe una sentencia tal que pero 0 , con lo que es
incompleta.
Observacin: Como la teora tiene un modelo, no podemos derivar contradicciones,

es decir, es consistente.
Demostracin. Dada cualquier ecuacin diofntica p(x1 , ..., xn ) = 0, si fuese

completa, tras un nmero finito de pasos obtendramos
` x1 , ..., xn p(x1 , ..., xn ) = 0 ` @x1 , ..., xn p(x1 , ..., xn ) = 0
Y resolveramos el X-problema de Hilbert afirmativamente.

Y como el X-problema de Hilbert no tiene solucin, deducimos que no es
completa.
41 de 102
Ejemplo: Sea x3 + y 3 = z 3
Podramos ir intentando probar con
(x, y, z) = (1, 1, 1) (1, 1, 2) (1, 1, 3) ... (1, 1, n)
pero este sistema no es muy bueno ya que hay combinaciones que nunca llegaramos
a probar como (2, 1, 1).
Lo que habra que hacer sera es probar las combinaciones posibles de la forma:
(x, y, z) = (1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 2, 2) (2, 1, 1) (2, 1, 2) ...
Este si sera un procedimiento que nos asegura pasar por todas las posibilidades y que
si existe una solucin la encontramos en un nmero n finito de pasos.
Observacin: Si es suficientemente rica como para contener los resultados bsi-

cos sobre sumas y productos (por ejemplo si contiene los axiomas N 1N 9 del libro), si
p(x1 , ..., xn ) = 0 para alguna n-tupla a1 , ..., an , entonces ` x1 , ..., xn p(x1 , ..., xn ) =
0.
Es decir, siendo lo bastante rica, en caso de existir solucin de una ecuacin
diofntica de n variables, podremos demostrar la existencia de la solucin a partir de
.
3.2. Mquinas de Turing

Es importante, antes de saber lo que son las mquinas de Turing.
Ejemplo: Para comprender el funcionamiento de las mquinas de Turing vamos a

computar la suma 15 + 267, sumando en columna:
1 5
2 6 7
1. Veo un 5. Lo guardo en mi memoria y bajo.

3. Veo un hueco. Sumo lo que tengo en mi memoria y escribo el ltimo dgito (en
este caso 2) y vaco mi memoria. Si hay ms dgitos, los almaceno en mi memoria
(en este caso un 1).
4. Subo arriba del todo y me muevo a la izquierda.
este caso 8) y vaco mi memoria. BO hay ms dgitos.
42 de 102
9. Veo un hueco. Bajo
este caso 2) y vaco mi memoria. BO hay ms dgitos.
13. Veo un hueco. Bajo.
16. Voy arriba del todo y he acabado.
Mquinas Definicin 3.1 Mquinas de Turing. Variantes (que dan lugar al mismo modelo de
de Turing computacin) que cumplen:
El modelo ideal de computacin sin limitaciones de tiempo ni de espacio.
La condicin bidimensional del papel cuadriculado no es esencial. Consideramos

una cinta infinita en ambas direcciones con casillas:
...
En las casillas encontramos smbolos pertenecientes a un alfabeto finito S. (En

la actualidad, ese alfabeto finito slo tiene 2 smbolos: 0 y 1, ya que todos los
dems se pueden traducir en esos smbolos). En lugar de 0, a veces utilizaremos
B denotando espacio en blanco.
La mquina tiene un cabezal que lee los contenidos de la celda. Puede modifi-
carlos o dejarlos igual.
Puede desplazarse a la casilla de la izquierda o a la de la derecha.
La accin de una mquina de Turing depende nicamente de el contenido de la

casilla que est leyendo y de su estado interno.
La computacin se inicia con el cabezal sobre la casilla con el primer 1.
Denotaremos los estados por q0 , q1 , . . ..
Acciones:
Accin B: Si la casilla que est leyendo tiene una B o un 1, la mquina borra y

escribe B.
Accin 1: La mquina borra y escribe un 1.
43 de 102
Accin D: El cabezal puede moverse una casilla a la derecha.
Accin I: El cabezal puede moverse una casilla a la izquierda.
Un paso de la Mquina de Turing viene especificado por una cuaterna

qi , S, A, qj
donde
qi : Estado inicial.
S: Smbolo.
A: Accin que toma.
qj : Siguiente estado.
Una mquina de Turing viene definida por un nmero finito de cuaternas con la
propiedad de que dos cuaternas distintas no pueden tener los dos primeros smbolos
iguales.
Ejemplo: Consideramos la siguiente mquina de Turing:
1. (q0 , 1, B, q1 )
2. (q1 , B, D, q0 )
Si esta mquina recibe el siguiente input
B B 1 1 1 B 1 B B B ...
Se coloca en el estado q0 y coloca el cabezal en la primera casilla con un 1 en ella.

Tras esto comienza a trabajar siguiendo las reglas que tiene definidas.
1. B B B 1 1 B 1 B B B ...

q 1 q0
2. B B B B B B 1 B B B ...

q0
Como no hay ninguna cuaterna (q0 , B, . . .), la mquina se detiene.
44 de 102
Ejemplo: Extendemos el alfabeto a S = {B, 1, +}
B 1 1 1 + 1 1 B ...

q0
La mquina de Turing es
(q0 , 1, B, q0 )
(q0 , B, D, q1 )
(q1 , 1, D, q1 )
(q1 , +, 1, q2 )
El estado final es
B B 1 1 1 1 1 B ...

q2
La mquina ha sumado 3 + 2, increble.
Test de Church-Turing
Sea una funcin f : A Nk N calculable mediante un algoritmo. La clase
(informal) de todas las funciones f coincide exactamente con la clase de las funciones
recursivas, o equivalentemente, con las funciones cuyos valores pueden calcularse por
MT.
Teorema 3.2. Las funciones f : A Nk N (k = 0, 1, 2, . . .), calculables por

MT son exactamente las funciones recursivas.
Ejemplo: Uso de la tesis de Church. Los primos P forman un conjunto recursivo,

o equivalentemente, hay una MT que determina, para cada n 2, si n P o n P c .
Veamos como podemos demostrarlo.

Dado n, calculamos n
m
para todo 2 m n. Si algn resto da 0, entonces
n P c . Si no, n P .
Como acabamos de comprobar que existe un algoritmo, por las tesis de Church-
Turing, hay una MT que decide si n P o n P c n 2.
Lo que hemos hecho no ha sido una demostracin propiamente dicha pues esto
implicara dar una lista de cuaternas que deciden si n P n
/ P.
45 de 102
Invocar la tesis de Church-Turing no prueba nada, pero con frecuencia puede ser
reemplazada de manera rutinaria por una demostracin formal.
Consideramos funciones parciales y funciones de A Nk N con k 0.
Funcin Definicin 3.2 Funcin parcial. F = {f : A Nk N k = 0, 1, 2, . . .}.

parcial Recordatorio: las constantes son las funciones 0arias. Una funcin karia con k 1
tambin puede ser constante. Los elementos de F son las funciones parciales. Si f F
y A = Nk , entonces f es una funcin total.
Funcin Definicin 3.3 Funcin recursiva primitiva. Las funciones recursivas primitivas
recursiva (son totales) forman la subclase E ms pequea de F , cerrada bajo las siguientes
primitiva operaciones:
Las funciones constantes karias f : Nk N (x1 , . . . , xk , f (x1 , . . . , xk ) = c)

pertenecen a E.
Las proyecciones sobre las coordenadas (o funciones coordenadas) estn en E.

Es decir, para k = 1, 2, . . ., k,i (x1 , . . . , xk ) = xi , est en E.
Las funciones sucesor S E (S(n) = n + 1).
La clase E est cerrada por composicin.
La clase E est cerrada bajo definiciones por recurrencia (o por recursin primi-
tiva, o por induccin).
Definicin 3.4 . Definimos la funcin h : A Nk+1 N por recurrencia a partir de

f : B Nk N y g : C Nk+2 N (aqu, si xk+1 tal que (x1 , . . . , xk , xk+1 ) A,
entonces (x1 , . . . , xk ) B, y C = A N) mediante:
1. h(x1 , . . . , xk , 0) = f (x1 , . . . , xk )
2. h(x1 , . . . , xk , n + 1) = g(x1 , . . . , xk , n, h(x1 , . . . , xk , n))
Ejemplo: La funcin suma + : N2 N es recursiva primitiva. Por recurrencia

definimos:
1. +(x, 0) = 1,1 (x) = x
2. +(x, n + 1) = S(3,3 (x, n, +(x, n))) = x + n + 1
O ms simplemente (e informalmente):
1. x + 0 = x
2. x + (n + 1) = (x + n) + 1
46 de 102
Ejemplo: El producto : N2 N es una funcin recursiva primitiva. Definimos

inductivamente:
1. x 0 = 0
2. x (n + 1) = x n + x
Ejemplo: La exponenciacin : N N 7 N es una funcin recursiva primitiva.

Por recurrencia definimos
1. x0 = 1
2. xy+1 = xy x
Ejemplo: La operacin signo es tambin una funcin recursiva. Definimos induc-

tivamente:
1. signo(x) = 1 si x > 0
2. signo(0) = 0
Conjunto Definicin 3.5 Conjunto recursivo primitivo. Un conjunto A Nk es recursivo

recursivo primitivo si y slo si la funcin indicatriz evaluada sobre este conjunto es primitiva.
primitivo
Relacin Definicin 3.6 Relacin k-aria recursiva primitiva. Una relacin k-aria R Nk
k-aria es recursiva si y slo si el conjunto {(x1 , ..., xr ) R} es recursivo primitivo.
recursiva
primitiva Veamos algunos ejemplos conjuntos y relaciones recursivas primitivas.
Ejemplo:
1. k 1 el conjunto Nk es un conjunto recursivo primitivo pues la funcin indica-

triz sobre este conjunto es la constante 1 y sabemos que las funciones constantes
son recursivas primitivas.
2. Si A es recursivo primitivo, tambin lo es Ac .
Para comprobarlo basta con notar que:
1Ac = max{1Nk 1A , 0}
que sabemos es tambin una funcin recursiva primitiva.
3. La relacin R(x, y) x > y es recursiva primitiva.
Para comprobarlo debemos ver que el conjunto A = {(x, y) N2 , x > y} es
recursivo primitivo.
Esto es sencillo puesto que:
1A = signo max{x y, 0}

47 de 102
4. La relacin x y es recursiva primitiva como podemos comprobar definiendo
1A = signo max{x y + 1, 0}

5. Si una funcin f se define por casos (un nmero finito de casos) usando funciones
recursivas primitivas, entonces f es recursiva primitiva.
Las funciones primitivas no incluyen a todas las funciones calculables mediante un

algoritmo. Como ejemplo tenemos la funcin de AcKermann (ver pginas 89-01 del
libro).
3.3. Minimizacin no acotada y funciones recursivas

Vamos a matizar un poco la definicin que hemos visto de funciones recursivas.
Funcin Definicin 3.7 Funcin recursiva. Las funciones recursivas son la clase E 0 F ms
recursiva pequea que contiene a las constantes, a las proyecciones sobre las coordenadas, a S
y est cerrada por composicin, recurrencia y minimizacin no acotada.
Minimizacin Definicin 3.8 Minimizacin no acotada. Sea f F una funcin (k + 1)-aria,

no acotada definimos la funcin
g(x1 , ..., xk ) = mn{z N f (x1 , ..., xk , z) = 0}
Si el valor z N empleado en la definicin no existe entonces g no est definida

en (x1 , ..., xk ).
A esta forma de generar nuevas funciones se le denomina minimizacin no aco-
tada
Conjunto Definicin 3.9 Conjunto recursivo. Un conjunto A Nk es recursivo si y slo si

recursivo 1A es recursiva total
Conjunto Definicin 3.10 Conjunto recursivamente enumerable. Un conjunto A Nk es

recursi- recursivamente enumerable si es el dominio de una funcin recursiva (parcial o total).
vamente
enumera-
ble Observacin: Si A es un conjunto recursivo su complementario tambin lo es. Para
verlo basta con recordar que la funcin 1Nk es recursiva total y, por tanto, max{1Nk
1A , 0} = 1Ac tambin lo es.
Observacin: Si A es recursivo, A es recursivamente enumerable. Para comprobar

esta afirmacin basta con tomar f (a) = 1A (a) para a A que sabemos es primitiva
pues A es un conjunto recursivo. Por tanto A es el dominio de una funcin recursiva.
Puede demostrarse (aunque aqu no lo vamos a hacer) que las siguientes formula-
ciones de A es recursivamente enumerable son equivalentes a la definicin:
48 de 102
1. Existe una funcin recursiva f tal que dom(f )=A y f = 1 en A.
2. A es el rango de una funcin recursiva parcial
3. A = A es el rango de una funcin recursiva total.
4. Existe una Mquina de Turing que se detiene exactamente cuando su input a

es un elemento de A.
Teorema 3.3. Dada una funcin f F , f es recursiva si existe una Mquina de

Turing que calcula sus valores. Si una Mquina de Turing calcula los valores de
una funcin g F , entonces g es recursiva.
Teorema 3.4. Un conjunto A es recursivo si y slo si A y Ac son recursivamente

enumerables.
Demostracin. Como tantas otras veces vamos a ver los dos sentidos de la impli-
cacin.
1. = Esta demostracin es trivial basndose en las dos observaciones ante-

riores.
2. = Tenemos que definir como funcin calculable 1A , con lo que estaramos

demostrando que A es recursivo por definicin.
Tomamos M TA y M TAc , mquinas de Turing que se detienen exactamente
cuando el input pertenece a A y Ac respectivamente. Es decir, si tomamos un
input perteneciente a A, la mquina M TAc se ejecutar infinitamente mientras
que M TA parar su ejecucin.
Una vez tenemos esto podemos definir la funcin 1A como:
(
1 si M TA detiene su ejecucin mientras M TAc se ejecuta infinitamente
1A =
0 si M TAc detiene su ejecucin mientras M TA se ejecuta infinitamente
Teorema 3.5. No existe una enumeracin efectiva (calculable, algortmica) de las

funciones recursivas totales f : N 7 N
49 de 102
Demostracin. Vamos a realizar esta demostracin por reduccin al absurdo.

Supongamos que existe esta enumeracin. En ese caso la funcin
g(n) = fn (n) + 1
donde fn es la n-sima funcin de la enumeracin, es recursiva total pero no est

en la lista.
Para ver que no est en la lista basta con ver que si la comparamos con la funcin
fn obtenemos un valor distinto en n por lo que difiere en (al menos) un punto con
todas las funciones de la lista.
Teorema 3.6. Existe una enumeracin efectiva de las funciones recursivas (par-
ciales o totales)
Teorema 3.7. Existe una enumeracin efectiva de las mquinas de Turing.
Teorema 3.8. Existe una mquina de Turing universal, es decir, existe una m-
quina de Turing M T U tal que M T U (m, n) (donde m es el cdigo de una mquina
de Turing y n es un nmero natural) simula la accin de la mquina de Turing
codificada por m evaluada sobre el input n.
Demostracin. En el mundo de hoy es sencillo creer en la existencia de esta mquina

de Turing universal pues sera algo similar a un ordenador de los que hoy en da todos
conocemos.
Algoritmo para resolver el problema
Dada una enumeracin efectiva M T0 , M T1 , ... usamos el algoritmo que permite
calcular la lista para hallar M Tn y, a continuacin, usamos el algoritmo de esta
mquina para averiguar qu hace sobre el input k.
Puesto que tenemos definido el algoritmo, invocamos la tesis de Church-Turing
que nos garantiza que existe una M T que ejecuta este algoritmo.
Esta M T ser una mquina de Turing universal.
Observacin: Lo que acabamos de hacer es una pseudo-demostracin del teorema.

Una autntica demostracin requerira dar explcitamente una sucesin de cuaternas
que definen la M T U .
50 de 102
Vamos a considerar ahora el conjunto de mquinas de Turing que calculan funciones

recursivas de una variable.
Notacin: MT(input)=output
Estas mquinas de Turing pueden entenderse como anlogos a programas que
reciben una entrada input y tras un tiempo nos devuelve un resultado output.
Siguiendo con esta idea, una mquina de Turing universal sera el equivalente a un
ordenador, pues recibe descripciones de programas (mquinas de Turing) y nos devuelve
su resultado.
Nos gustara tener una Mquina de Turing , llammosla D, que resuelva el pro-
Problema blema de la detencin, es decir, D simula una Mquina de Turing con input m N
de la y nos dice si la Mquina de Turing se detiene o se queda en un bucle infinito.
detencin
Fijamos una codificacin (algoritmo) que asigna a cada Mquina de Turing su
nmero de Gdel siendo g(M T ) N.
Por ejemplo, si M T (m) genera un output (es decir, la mquina se detiene) entonces
D(g(M T ), m) = 1. En caso contrario tendramos D(g(M T ), m) = 0.
Teorema 3.9. El problema de la detencin es insoluble.

Es decir, la Mquina de Turing D descrita anteriormente no existe.
Demostracin. Esta demostracin se realizar por diagonalizacin.

Usando D construimos la Mquina de Turing V definida en los nmeros g(M T )
como sigue:
1. Dado un input m, V genera (m, m).
2. V simula o ejecuta el programa D(m, m)
3. V diagonaliza. Es decir, si D(m, m) = 1 entonces V entra en un bucle

infinito7
Por otro lado, si D(m, m) = 0 entonces V imprime 1 y se detiene.
Con este algoritmo llegamos a una contradiccin:

Si V (g(V )) = 1 entonces D(g(V ), g(V )) = 0 lo que implica que V (g(v)) entra
en un bucle infinito.
Si V (g(V )) entra en un bucle infinito, entonces D(g(V ), g(V )) = 1 luego
V (g(V )) se detiene.
Ilustremos la demostracin con una versin programable de la misma.
Supongamos que el problema de la diagonalizacin es soluble algortmicamente.
Entonces hay un programa, que llamaremos Termina, que cada vez que se le sumi-
nistra el cdigo de un programa p y sus datos de entrada x nos devuelve true si
el programa termina o false si se ejecuta indefinidamente.
51 de 102
def Termina(p,x):
# Supongamos que aqu viene el cdigo comentado
Una vez tenemos este programa, podemos escribir otro, al que llamaremos Dia-
gonal que lo invoca. Este programa recibir como dato de entrada el cdigo de un
programa cualquiera w, y usar el programa Termina para decidir si el programa
termina cuando se recibe a s mismo como entrada.
def Diagonal(w):
if Termina(w,w):
while True: pass # Bucle infinito
En definitiva, el programa Diagonal (w) termina si y slo si w(w) nunca termina.

Ahora basta con llamar al programa diagonal con l mismo como argumento
para llegar a la clara contradiccin, pues tendramos que:
Diagonal (Diagonal ) termina si y slo si Diagonal (Diagonal ) nunca termina.
Es definitiva, bajo la suposicin de que existe el algoritmo Termina hemos llegado

a una contradiccin. Como conclusin, dicho algoritmo no existe.
Esta segunda demostracin ha sido extraida de Wikipedia
7
Estamos construyendo la Mquina de Turing V y forzamos a que entre en un bucle infinito en
caso de que D(m, m) = 1.
52 de 102
4. Incompletitud
Los principales enunciados bsicos correspondientes a esta seccin ya los hemos
visto. Lo que haremos ser aadir ciertas definiciones y varios resultados/teoremas
importantes.
Recordatorio de lgica proposicional
{p, q} ` r ` (p q) r
Para demostrar esto empezbamos apoyndonos en el teorema de la deduccin:
{p, q} ` r = {p} ` q r
Aplicando de nuevo el teorema de la deduccin obtenamos:
{p} ` q r = ` p (q r) (p q) r
Teorema 4.1. Consideramos el lenguaje de la aritmtica formal, definido como:
L = {0, Si , +1 , 1 , <1 }
y la teora N = {N1 , ..., N9 } correspondiente a los axiomas de Peano (sin incluir

induccin) y definida en el libro en la pgina 91.
En este lenguaje, L, y con la teora N , toda funcin recursiva total f : Nk 7 N
es representable para una frmula de primer orden f .
Lo mismo ocurre con los conjuntos recursivos.
Proposicin 4.2 (Codificacin). Las frmulas pueden codificarse usando nmeros

naturales.
Las demostraciones tambin.
Para llevar a cabo estas codificaciones debemos definir smbolos del lenguaje n N
y asociar a cada variable vi el nmero n(vi ) = 2i con lo que empleamos solamente
nmeros pares.
Una vez tenemos esto podemos asignar a las operaciones los nmeros impares como
sigue:
n(>) = 1, n() = 3, n() = 5, n() = 7, n() = 9, n(=) = 11
n() = 13, n() = 15, n(0 (0 ) = 17, n(0 )0 ) = 19, n(0) = 21, n(S1 ) = 23
n(+1 ) = 25, n(1 ) = 27, n(<1 ) = 29
El problema que nos deriva de esta codificacin es que no es claro cmo descifrar el
predicado 230 puesto que puede interpretarse como el smbolo asociado al 23 seguido
53 de 102
de la variable asociada al 0, o como la variable asociada al 2 seguida de la variable

asociada al 15, etc.
Empleamos la factorizacin nica para resolver este problema. Para ello definimos
la funcin primo(K) que nos devuelve el primo que ocupa la posicin K + 1.
As el nmero de Gdel de una palabra se calcula como:
g(u0 , u1 , ..., uk ) = 2n(u0 ) 3n(u1 ) ... primo(k)n(uk )
De esta forma, al leer el nmero asociado a una frmula basta con factorizarlo, lo
que nos permite obtener la frmula original de manera unvoca.
Teora re- Definicin 4.1 Teora recursiva. Una teora es recursiva si el conjunto de nmeros
cursiva de Gdel
# = {g() }
es recursivo.
Esto nos dice que, dada cualquier , podemos decidir algortmicamente si
c .
Teora Definicin 4.2 Teora de (Teor()). Al conjunto de teoremas de se le denomina

de Teora de .
(Teor()) Teor() = { ` }
Definimos tambin
#Teor() = {g() ` }
Teora de- Definicin 4.3 Teora deducible. Decimos que es deducible si #Teor() es recur-
ducible siva, es decir, existe un algoritmo que dado cualquier nos dice es un teorema o no.
Ejemplo: Podemos comprobar que el caso = es recursiva de manera trivial.

Tambin puede verse que N es recursiva.
Observacin: Cualquier teora finita es recursiva.
Teorema 4.3. La lgica proposicional es deducible.

De hecho, puede demostrarse que el conjunto de los nmeros de Gdel de las
tautologas, es decir {g(p) p es tautologa}, es recursivo primitivo.
54 de 102
Teorema 4.4. El conjunto de axiomas de la lgica de primer orden es recursivo

(de hecho es recursivo primitivo).
Teorema 4.5. Sea una teora recursiva, el conjunto:
Dem() = {(m, n) m = g() y n = g(alguna demostracin formal de )}
es recursivo.
Demostracin. Para llevar a cabo esta demostracin nos basta con encontrar un
algoritmo que nos permita determinar si el par de valores (m,n) pertenece, o no, a
Dem(). Para ello tendremos que descodificar m y n.
Si g 1 (m) = y g 1 (n) es una demostracin de , entonces (m, n) Dem().
En caso contrario (m, n) Dem().
Observacin: Como 1Dem() es una funcin recursiva total, existe una frmula en el
lenguaje formal, digamos Dem() , que la representa.
Puede demostrarse que las proyecciones sobre las coordenadas de conjuntos recur-
sivos son recursivamente enumerables.
Corolario 4.6. Si una teora es recursiva entonces el conjunto de sus teoremas es

recursivamente enumerable, es decir, existe un algoritmo que encuentra todos los teo-
remas de .
Demostracin. Sabemos que la proyeccin sobre los ejes de un conjunto recursivo

es recursivamente enumerable por lo que:
1Dem() es recursivamente enumerable

que es justo lo que necesitamos probar.
Corolario 4.7. Si es recursiva y completa entonces es decidible.
Demostracin. Como #Teor() es recursivamente enumerable, basta probar que

su complementario es recursivamente enumerable.
Dada , enunciamos los teoremas de sistematicamente. Como es completa,
tras un nmero finito de pasos aparecer o .
Vamos a ver ahora los teoremas de incompletitud.
55 de 102
Teorema 4.8 (Teorema Primero de incompletitud). Sea una teora consistente

y recursiva que contiene a N = {N1 , ..., N9 } (los 9 axiomas de la aritmtica).
Entonces no es decidible.
Demostracin. Idea: Si fuera decidible, podramos determinar de manera algort-

mica si cualquier es un teorema o no.
Ello nos permitira resolver problemas insolubes que se pueden codificar en L
utilizando N, por ejemplo el X problema de Hilbert (3.1), con alguna salvedad.
Corolario 4.9. La lgica de primer orden no es decidible, es decir, el conjunto de

nmeros de Gdel que pueden deducirse de los axiomas no es recursivo.
Demostracin. En este caso, = . No estamos aadiendo nada a los axiomas

lgicos.
Utilizando el teorema de la deduccin y Modus Ponens,
N ` ` (N1 N 2 ... N 9)
Si la lgica de primer orden fuera decidible, la teora N tambin lo sera y po-

dramos resolver problemas insolubles.
Corolario 4.10. Sea una teora consistente y recursiva que contiene a N. Entonces
no es completa.
Observacin: No es completa ni completable. Si aadiramos una nueva sentencia que

no podemos probar, mantendramos la consistencia, pero apareceran nuevas sentencias
que no podemos probar.
Demostracin. Si fuera completa, sera decidible (por el corolario 4.7)
Vamos a recordar algo visto con anterioridad, sobre la codificacin. Tenamos
n() = 3 y g() = 23
Informalmente, N ` 2 + 2 = 4 es cierto. Formalmente, escribiramos:
N ` S12 (0), +, ` S12 (0) =` S14 (0)
Ahora nos preguntamos, Podemos demostrar N ` 2 + 2 = 5? No. Y podramos

probar N ` (N 6` 2 + 2 = 5)? Tampoco, por el segundo teorema de incompletitud.
La segunda parte del recordatorio es que Dem() es recursivo. Ello implicaba que
Dem() que representaba a Dem(), es decir, si
(m, n) Dem(), ` Dem() (S1m (0, S1n (0))
56 de 102
Por otro lado:

(m, n) 6 Dem(), ` Dem() (S1m (0, S1n (0))
.
Y utilizando esto, se puede formalizar qu es la consistencia.
Consistencia Definicin 4.4 Consistencia (CON).

(CON)
CON () := v0 Dem() (, v0 )
Aunque no puede aparecer ah (porque estamos codificando todo en nmeros), sino

que tiene que aparecer su nmero de Gdel, es decir g() = 23 = 8
CON () := v0 Dem() (S18 (0), v0 )

Teorema 4.11 (Teorema Segundo de incompletitud). Si es recursiva, consis-

tente y contiene a N, entonces 6` CON ()
Este es el teorema que implica que
N ` (N 6` 2 + 2 = 5)
Demostrar esa afirmacin, sera demostrar la consistencia de y eso no es demostrable

como hemos visto en el segundo teorema de incompletitud.
Comentario sobre la hoja 8 . Esta hoja est puesta por la poca confianza que hay
en el teorema de compacidad.
Definimos:
F = {A N : Ac es finito}.
F U ultrafiltro
Entonces, podemos definir NN , con la siguiente inclusin f (n) : NN N construida
de la siguiente manera f (n) = (n, n, ..., n)
Por lo que: (an )
n=1 (bn )n=1 si {an = bn } U
8
Definimos tambin U := NN /
Afirmacin n o
(n)

c= n=1 > (k) n=1 k N
Tenemos tambin una inclusin de N en U.

Siento esta mierda de comentario, he hecho lo que he podido.
8
Es decir, 2 sucesiones son iguales si son iguales en casi todo punto (iguales salvo en conjuntos
de probabilidad 0 y los elementos que tienen probabilidad 0 son los del ultrafiltro (o algo as))
57 de 102
Apndice A
Problemas resueltos
A.1. Hoja 1
Asumimos genrica e informalmente la no trivialidad. Por ejemplo, cuando hablamos
de conjuntos, lenguajes, etc., suponemos que no son vacos (salvo que explcitamente se
diga lo contrario), cuando hablamos de frmulas suponemos que estn bien formadas,
etcetera. En caso de duda, consultar con el intructor.
Ejercicio 1.1: Aprenderse el lema de Zorn de memoria. Comentario: el lema

de Zorn es equivalente al Axioma de Eleccin.
Todo conjunto parcialmente ordenado no vaco en el que toda cadena (subconjunto

totalmente ordenado) tiene una cota superior, contiene al menos un elemento maximal.
Ejercicio 1.2: Sea A un conjunto finito y parcialmente ordenado. Denotamos

por R el correspondiente orden parcial (usamos R porque un orden parcial es una
relacin binaria, o con aridad" 2). Demostrar que A contiene un elemento maximal.
Demostrar que R puede extenderse a un orden total o lineal, es decir, existe un
orden total R0 tal que R R0 (orden lineal o total significa que para todo par
x, y A, o bien (x, y) R0 , (y, x) R0 ).
Vamos a escribir el conjunto A como:

[
A= Bi
i
para ello vamos a construir los conjuntos Bi como sigue:
1. Tomamos un elemento x A, que usaremos para definir B1

2. Recorremos uno a uno de A y los insertamos en B1 forzando que R siempre
constituya un orden total en B1 . Esto es, cada vez que vayamos a insertar un
elemento, comprobamos primero que tenga relacin con todos los elementos que
ya se encuentran en B1
58 de 102
3. Cuando hemos recorrido todos los elementos de A, damos por concluida la cons-
truccin de B1
4. Repetimos el proceso empezando con un elemento distinto de A
Puesto que A es finito, este procedimiento ser tambin finito y nos permitira
escribir A como unin de n conjuntos totalmente ordenados, siendo n el cardinal de
A.
Es sencillo comprobar que no es posible que ningn conjunto quede vaco (como
mnimo tiene el elemento que usamos como base para construirlo) y tampoco puede
constar de slo un elemento, pues no puede haber ningun elemento en A que no guarde
relacin con ningn otro.
Puesto que los conjuntos Bi son finitos y totalmente ordenados, es claro que tienen
un mximo, por lo que podemos aplicar el lema de Zorn, probando as que el conjunto
A tiene un elemento maximal.
Ahora tenemos que ver como extendemos el orden parcial R a un orden total R0 .
Para que sea una extensin debe cumplirse:
xRy = xR0 y
Para definir el orden total R0 podemos apoyarnos en R siempre que sea posible, con
lo que garantizamos que se cumpla la implicacin. Tras esto, nos quedara definir R0
para aquellos elementos que no estn relacionados en R.
Si tenemos un par de elementos tales que (x, y) / R entonces, por
/ R&(y, x)
definicin, tenemos que x, y pertenecen a distintos Bi .
Llegados a este punto podemos dar un orden arbitrario al conjunto finito de Bi
de forma que
bi R0 bi+1
As nos queda:

xRy si
i x, y Bi
0
xR y =
iRj si x Bi &y Bj

Ejercicio 1.3: El lema de legibilidad nica nos dice que las frmulas bien
formadas no son ambiguas, pueden leerse de un nico modo. Reescribir las frmulas
que aparecen a continuacin en notacin polaca, usando la notacin estndar, y
las que aparecen en notacin estndar, en polaca.
a) p q r p, p q q r p r q s.
b) (q (p q)), ((p q) (( q) r)).
Hallar el rbol de descomposicin de las frmulas en b).
59 de 102
a)
(p q) (r p)
(((p q) (q r)) (p r) ((q s))
b)
rbol de descomposicin
(q(pq))
q (pq)
p p q
Notacin polaca:
q pq
rbol de descomposicin
((p q) ((q) r))
(p q) ((q) r)
p q (q) r
Notacin polaca:
pq qr
Ejercicio 1.4: Sea p una frmula (bien formada). Probar que el nmero de
parntesis izquierdos en p es igual al nmero de parntesis derechos. Sugerencia,
usar induccin.
Atendiendo a la notacin dada en clase , tenemos un conjunto de elementos at-

micos , que llamamos A y que le aadios los elementos > y . La familia de todas las
frmulas bien formadas (FBF) se constituye de la siguiente forma:
FBF0 = A {>, }
FBFn+1 = F BFn {(F1 ), (F1 = F2 ), (F1 F2 ), (F1 F2 ), (F1 F2 )}
con F1 , F2 FBFn .
Con esta notacin vamos a demostrar el ejercicio usando induccin:
60 de 102
Caso base: n = 0
FBF0 = {(a) : a A {>, }}

El elemento (a) tiene el mismo nmero de partesis derechos que izquierdos.
Suponemos que esto tambin se cumple para el caso FBFn , vamos a ver que
tambin se cumple para FBFn+1
FBFn+1 = F BFn {(F1 ), (F1 = F2 ), (F1 F2 ), (F1 F2 ), (F1 F2 )}con F1 , F2 FBFn .
Hemos supuesto que todos los elementos de FBFn tienen el mismo nmero de pa-
rntesis derechos e izquierdos, los elementos que tenemos que comprobar que tambin
lo cumplen son:(F1 ), (F1 = F2 ), (F1 F2 ), (F1 F2 ), (F1 F2 ).
Es fcil ver que esto es cierto ya F1 , F2 FBFn y se les aade un parntesis por
la derecha y otro por la izquierda.
A.2. Hoja 2
Asumimos genrica e informalmente la no trivialidad. Por ejemplo, cuando hablamos
de conjuntos, lenguajes, etc., suponemos que no son vacos (salvo que explcitamente
se diga lo contrario), cuando hablamos de frmulas p, q, r, . . . suponemos que estn
bien formadas, etcetera. En caso de duda, consultar con el intructor.
Ejercicio 2.1: Con el lenguaje L = A{, }, A 6= , la regla de deduccin

modus ponens, y los axiomas
1. (p (q p)),
2. ((p (q r)) ((p q) (p r))), y
3. (((p) (q)) (((p) q) p)),
comprobar que
a) ` (p p),
b) ` (((p) p) p),
c) {(p q), (q r)} ` (p r).
Apartado a)
Si sustituimos q por p obtenemos una instancia del primer axioma:
(p (p p))
Sustituyendo ahora q por p p en el primer axioma obtenemos:
(p ((p p) p))
61 de 102
La sustitucin de q por p p y de r por p en el segundo axioma da lugar a la

instancia:
((p ((p p) p)) ((p (p p)) (p p)))
Aplicando Modus Ponens a las dos ltimas frmulas tenemos:
((p (p p)) (p p))
Y finalmente, aplicando Modus Ponens de nuevo con la primera y ltima frmulas

obtenidas en este ejercicio llegamos a:
pp
Apartado b)
Podemos repetir toda la demostracin del apartado anterior instanciando todas las
frmulas sustituyendo todos los smbolos por p con lo que llegaramos a:
(p p)
Ahora sustituimos q por p en el axioma 3, obteniendo:
(((p) (p)) (((p) p) p))
Aplicando Modus Ponens tenemos:
(((p) p) p)
Apartado c)
Sustituyendo p por q r y q por p en el primer axioma tenemos la instanciacin:
((q r) (p (q r)))
Aplicando ahora Modus Ponens a esta formula junto con (q r) tenemos:
(p (q r))
Aplicando ahora Modus Ponens a la frmula anterior junto con el segundo axioma
llegamos a:
((p q) (p r))
Finalmente, aplicando nuevamente Modus Ponens con (p q) llegamos a
(p r)
Solucin del profesor

Sea
T = (p q), (q r) ` (p r)
62 de 102
1. Escribimos el axioma 1 con (q r) en vez de p y p en vez de q:

((q t) (p (q r)))
2. Tenemos la premisa en T : (q r).

3. Modus ponens utilizando 1 y 2:
(p (q r))
4.
(p (q r)) ((p q) (p r))
((p q) (p r))
6. Tenemos la premisa en T : (p q).

(p r)
Ejercicio 2.2: Demostrar la parte no trivial del lema de legibilidad nica: si

(p q) es una fbf, donde es una conectiva binaria, y (p q) = (r 0 s), entonces
p = r, = 0 , y q = s.
Sea (p q) = (r 0 s) donde p, q, r, s son FBF.

Ningn segmento inicial de una FBF puede ser una FBF.
Razn: Dado que toda FBF comienza con (, acaba necesariamente con ) y tiene
el mismo nmero de parntesis izquierdos que derechos (ver ejercicio 4 de la hoja 1),
cualquier segmento inicial de una FBF no es una FBF porque tendra un nmero mayor
de ( que de ).
Por tanto, tenemos que r no puede ser un segmento inicial de p porque r no sera
FBF y tenemos que p lo es.
Por otro lado, p no puede ser un segmento inicial de r porque tenemos que p es
una FBF, por lo tanto r no sera FBF.
Obtenemos que p y r tienen el mismo nmero de smbolos, luego p = r. A partir
de aqu, tenemos = 0 y, utilizando el mismo razonamiento, q = s.
Ejercicio 2.3: Un grafo es coloreable con 4 colores, si es posible asignar a

todo vrtice uno de los 4 colores de modo que vrtices adyacentes tengan colores
distintos. Sea G un grafo con vrtices {v : }, y conjunto de aristas E
(que podra ser vacio; las aristas son subconjuntos de G con cardinalidad 2). Sea
L = A {, , }, A = {v (i) : , i = 1, 2, 3, 4}. Interpretando v (i) como
el vrtice v tiene color i", enunciar los axiomas de la teora T segn la cual el
grafo (G, E) es coloreable con 4 colores.
63 de 102
El grafo ser coloreable siempre que dos vrtices del mismo color no estn conec-
tados. Por tanto los axiomas seran:A
Cada vrtice tiene solamente un color
{(v (1) v (2)) (v (1) v (3))
(v (1) v (4)) (v (2) v (3))

(v (2) v (4)) (v (3) v (4)) | }
Dos vrtices conectados por una arista no tienen el mismo color
{(va (1)vb (1))(va (2)vb (2))(va (3)vb (3))(va (4)vb (4)) | E(a, b)}
A.3. Hoja 3
Ejercicio 3.1: Sea una valoracin Booleana. Expresar (p q) y (p q)

en trminos de (p) y (q), usando la suma y el producto en Z2 .
Consideramos el 1 como verdadero y el 0 como falso.

Apartado a)
(p q) = (p q) = 1 + (1 + (p)) (1 + (q))
Alternativamente:
(p q) = (p) + (q) + (p) (q)
Apartado b)
(p q) = (p) (q)
Ejercicio 3.2: Demostrar que los siguientes conjuntos de conectivas son

completos: {, }, {, }, {, }, {, }.
Para ver que son completos debemos demostrar que podemos expresar el resto de
conectivas a partir de las dadas. Vamos a ello:
64 de 102
{, }
a b (a) b
a b ab a b
0 0 1 1 1 1
0 1 1 1 1 1
1 0 0 1 0 0
1 1 1 1 0 1
a b (a b)
a b ab ( a b)
0 0 0 1 0 1 1 1
0 1 0 1 0 1 1 0
1 0 0 1 0 0 1 1
1 1 1 1 1 0 0 0
> a (a)
a > a (a)
0 1 1 1 1
1 1 1 1 0
(a (a))
a ( a (a))
0 0 1 0 1 1
1 0 1 0 1 0

a b (a b) (b a) (a b) (b a) (a b) (b a)
a b (a b) ( ( a b) ( b a))
0 0 1 1 1 0 1 1 0 0 1 1
0 1 0 1 0 0 1 1 1 1 0 0
1 0 0 1 0 1 0 0 1 0 1 1
1 1 1 1 1 0 0 1 0 0 0 1
{, }
a b ((a) (b))
a b ab ( (a) (b))
0 0 0 1 0 1 1 1
0 1 1 1 1 1 0 0
1 0 1 1 1 0 0 1
1 1 1 1 1 0 0 0
65 de 102
a b a b (a (b))
a b ab (a (b))
0 0 1 1 1 0 1
0 1 1 1 1 0 0
1 0 0 1 0 1 1
1 1 1 1 1 0 0
> (a (a))
a > (a (a))
0 1 1 1 0 1
1 1 1 1 0 0
a (a)
a a (a)
0 0 1 0 1
1 0 1 0 0

a b (a b) (a b) ((a b)) (((a) (b)))
a b ab ( ( (a b)) ( ((a) (b))))

0 0 1 1 1 1 0 0 0 1 1 1
0 1 0 1 0 1 0 1 1 1 0 0
1 0 0 1 0 1 0 1 1 0 0 1
1 1 1 1 1 0 1 0 1 0 0 0
{, }
a b (a) b
a b ab (a) b
0 0 0 1 1 0
0 1 1 1 1 1
1 0 1 1 0 1
1 1 1 1 0 1
a b (a b) (a (b))
a b ab (a (b))
0 0 0 1 0 1 1
0 1 0 1 0 1 0
1 0 0 1 0 1 1
1 1 1 1 1 0 0
66 de 102
>aa
a > aa
0 1 1 1
1 1 1 1
(a a)
a (a a)
0 0 1 0 1
1 0 1 0 1

a b (a b) (b a) (a b) ((b a))
a b ab ((a b) ( (b a)))
0 0 1 1 1 1 0 0 1
0 1 0 1 0 1 1 1 0
1 0 0 1 0 0 1 0 1
1 1 1 1 1 1 0 0 1
{, }
>
>
1 1 0 1 0
a a
a a a
0 1 1 1 0
1 0 1 0 0
a b a b (a ) b
a b ab (a ) b
0 0 0 1 1 0 0
0 1 1 1 1 0 1
1 0 1 1 0 0 1
1 1 1 1 0 0 1
a b (a b) (a b) (a (b ))
67 de 102
a b ab (a (b ))
0 0 0 1 1 1 0 0
0 1 0 1 1 0 0 0
1 0 0 1 1 1 0 0
1 1 1 1 0 0 0 1
a b (a b) (b a) ((a b) ((b a) ))
a b ab ((a b) ((b a) ))
0 0 1 1 1 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0 0 0
1 0 0 1 0 1 1 0 0 0 0
1 1 1 1 1 0 1 0 0 1 0
Las equivalencias expresadas a lo largo del ejercicio se han obtenido forzando el

cumplimiento de las tablas de verdad.
Ejercicio 3.3: Demostrar que el conjunto de conectivas {, } no es com-

pleto. Sugerencia: usar monotona.
Sea C el conjunto de FBFs constituidas a partir del lenguaje {a, , }. Este con-
junto puede describirse como:
1. a C
2. Si , C = ( ) , ( ) C
3. C es el menor conjunto de FBFs que satisface las propiedades 1 y 2.
Cuando tengamos a = > tendremos que las frmulas (a a), (a a) son tambin
verdaderas y, por definicin del conjunto C, cualquier frmula C tendr valor
verdadero cuando a sea verdadera, ya que las conectivas y siempre evalan a
verdadero cuando a ambos lados tienen valores verdaderos.
Por tanto, es imposible que la negacin, a, que toma valor cuando a = >, se
deduzca de ese conjunto y, por tanto, el conjunto no es completo.
Ejercicio 3.4: Leer con cuidado el Lema 2.1.2 p. 16, y demostrar la colum-
na derecha de los apartados 4-7 (distributividad, absorcin, De Morgan, tercero
excludo).
El lema simplemente nos da una serie de 8 equivalencias. Procedemos a demos-

trar las 4 construyendo las tablas de verdad asociadas y comprobando que la doble
implicacin siempre tiene valor verdadero.
68 de 102
(p (q r)) (p q) (p r)
(p (q r)) (p q) (p r)
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 1
0 0 1 1 0 1 0 0 1 0 0 0 0
0 0 1 1 1 1 0 0 1 0 0 0 1
1 0 0 0 0 1 1 0 0 0 1 0 0
1 1 0 1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1
(p (p q)) p
(p (p q)) p
0 0 0 0 0 1 0
0 0 0 1 1 1 0
1 1 1 1 0 1 1
1 1 1 1 1 1 1
((p q)) (p q)
( (p q)) p q)
1 0 0 0 1 1 1 1
1 0 0 1 1 1 1 0
1 1 0 0 1 0 1 1
0 1 1 1 1 0 0 0
(p p)
(p p)
0 0 1 1 0
1 0 0 1 0
Ejercicio 3.5: Demostrar el Lema 2.1.3 p. 17.
El lema que queremos demostrar dice:
Lema A.3.1. Sea P rop(A) y sean p, q P rop(A), entonces

P
1. py
P P P
p q q
2.
P P
p = pq
3.
P P
{p} q pq
69 de 102
4. Si py p q, entonces q (Modus Ponens)

P P P
Vamos a demostrarlo
1. Por definicin decimos que p si para todo modelo de tenemos que

P P
(p) = 1.
Si tenemos que para todo modelo de , (p q) = > y sabemos que
P
(p q) = (p) (q) = >
queda claro que (p) = > y (q) = >.

Evidentemente esto tambin es cierto en sentido contrario, si tenemos (p) = >
y (q) = > es claro que
(p q) = (p) (q) = >
2. Puesto que tenemos

(p q) = (p) (q)
Es claro que si (p) = > para todo modelo de

P , entonces tendremos (p
P
q) = (p) (q) = > para todo modelo de .
3. Tomemos un modelo cualquier de . En caso de que la interpretacin
P sea
P

tambin un modelo en {p}, es decir, adems de ser modelo de tenemos
P
(p) = >, tendremos tambin (q) = >.
Es decir, dado tenemos que si (p) = > entonces (q) = > y que no sabremos
nada de (q) en caso contrario.
Esta situacin coincide exactamente con (p q) = (p) (q).
PorP otro lado, si tenemos (p q) = (p) (q) = > para P
todo modelo
de , entonces tenemos que, siempre que sea un modelo de y adems se
verifique (p) = >, se cumplir
P (q) = > (si (p) = no podemos asegurar
que (q) = >). Por tanto, {p} q.
4. Tenemos que para todo modelo de , (p) = (p q) = >. Es decir,
P
tenemos que
(p) = (p q) = (p) (q)
Sabiendo que (p) = > llegamos a
> = ( (q)) = (q) = >
Ejercicio 3.6: Comprobar que los tres axiomas en el ejercicio 1 de la hoja

2 son tautologas.
Para demostrar que estos axiomas son tautologas debemos comprobar que para
toda valoracin de las proposiciones p y q, la interpretacion de las FBFs dadas es >.
Vamos a verlo:
70 de 102
1. (p (q p))
(p (q p))
1 1 1 1 1
1 1 0 1 1
0 1 1 0 0
0 1 0 1 0
2. ((p (q r)) ((p q) (p r)))
((p (q r)) ((p q) (p r)))

1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 1 1 1 1 0 1 0 0
1 1 0 1 1 1 1 0 0 1 1 1 1
1 1 0 1 0 1 1 0 0 1 1 0 0
0 1 1 1 1 1 0 1 1 1 0 1 1
0 1 1 0 0 1 0 1 1 1 0 1 0
0 1 0 1 1 1 0 1 0 1 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0
3. (((p) (q)) (((p) q) p))
((( p) ( q)) ((( p) q) p))

1 1 1 1 1 0 0 1 0
0 1 1 1 0 1 0 1 1
1 0 0 1 1 1 1 0 0
0 1 0 1 0 1 1 1 1
Ejercicio 3.7: Comprobar que los ocho axiomas en las pginas 20-21 del
libro son tautologas.
Procedemos como en el ejercicio anterior>
1. >
El smbolo atmico > es una tautologa por definicin, pues siempre tiene el
valor verdadero.
2. p (p q)
p q (p ( p q ))
1 1 1 1 1 1 1
1 0 1 1 1 1 0
0 1 0 1 0 1 1
0 0 0 1 0 0 0
71 de 102
3. p (q (p q))
p q ( p ( q ( p q )))
1 1 0 1 1 0 1 1 0 1 1 1
1 0 0 1 1 1 0 0 0 1 1 0
0 1 1 0 1 0 1 1 0 0 1 1
0 0 1 0 1 1 0 1 1 0 0 0
4. (p q) p
p q (( p q) p)
1 1 1 1 1 1 1
1 0 1 0 0 1 1
0 1 0 0 1 1 0
0 0 0 0 0 1 0
5. p (q (p q)
p q (p ( q ( p q )))
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 0
0 1 0 1 1 0 0 0 1
0 0 0 1 0 1 0 0 0
6. (p (q r)) ((p q) (p r))
p q r (( p ( q r )) (( p q ) ( p r )))
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 0
1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1
1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0
0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1
0 1 0 0 1 1 0 0 1 0 1 1 1 0 1 0
0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1
0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0
7. p (p )
p ( p ( p ))
0 1 1 1 0 1 1 0
0 0 0 1 1 0 0 0
8. (p ) p
p (( p ) p )
0 1 0 1 1 0 1 1
0 0 1 0 0 0 1 0
72 de 102
Ejercicio 3.8: Reescribir los ocho axiomas en las pginas 20-21 del libro
usando slo las conectivas en {, }, y comprobar que dichos axiomas se deducen
de los tres axiomas en el ejercicio 1 de la hoja 2.
Tal y como hemos visto en teora, por el teorema de completitud, existe una prueba
de p a partir de los axiomas y modus ponens si y slo si p es una tautologa.
Por tanto, comprobar que las siguientes frmulas se deducien de los axiomas, basta
con probar que son tautologas, es decir, que su tabla de verdad nos da valor verdadero
para todas las interpreaciones posibles.
1. >
>pp
Trivialmente podemos ver que se trata de una tautologa.
2. p (p q)
p (p q) p ((p) q) p ((q) p)
La ltima equivalencia es una instancia del primer axioma. Para verlo basta con
sustituir q por q en ese axioma.
3. p (q (p q))
p (q (p q)) (p) ((q) (((p) q)))
p (q (p q))
1 1 1 1 1 0 0 0
1 1 0 1 0 0 1 1
0 1 1 0 0 1 1 0
0 1 0 1 0 1 1 1
4. (p q) p
(p q) p (((p) (q))) p ((p (q))) p
(p q) p
0 0 0 1 0
0 0 1 1 0
1 0 0 1 1
1 1 1 1 1
5. p (q (p q))
p (q (p q)) p (q ((p (q))))
73 de 102
p (q (p q))
0 1 0 1 0 0 0
0 1 1 0 0 0 1
1 1 0 1 1 0 0
1 1 1 1 1 1 1
6. (p (q r)) ((p q) (p r))

Ya est en el formato deseado y es uno de los axiomas.
7. p (p )
p (p ((p p)))
p (p )
0 1 1 0 0
1 1 0 1 0
8. (p ) p
(p ((p p))) p
(p ) p
0 1 0 1 1
1 0 0 1 0
Ejercicio 3.9: Obtener ` (p p) a partir del Lema de la Deduccin.
El Lema de la Deduccin nos dice:
(T {p} ` q) = (T ` (p q))
Tomando T = y q = p, tenemos {p} ` p cuya prueba es trivial, ya que p esta en

la teora.
Por el Lema de la Deduccin, concluimos ` (p p), es decir ` (p p)
Ejercicio 3.10: Decidir razonadamente si el conjunto de conectivas {,

} es completo.
No es completo debido a que tanto el como el generan siempre un numero

impar de 0s y 1s, mientras que siempre genera un numero par de 0s y un
nmero par de 1s y el solo intercambia el numero de 0s por el nmero de 1s. Por
tanto, no es posible solo con y con generar un nmero impar de 0s 1s, y
en consecuencia, no se puede encontrar una frmula equivalente al o al , es decir,
{, } NO es completo.
74 de 102
A.4. Hoja 4
Asumimos genrica e informalmente la no trivialidad. Al escribir frmulas, se permi-
ten las abreviaciones razonables (por ejemplo, las que he usado en el primer problema).
Ejercicio 4.1: Forma normal disyuntiva: una fbf est en forma normal
disyuntiva si se expresa como p1 pn , donde n 1, cada pi es de la forma
qi,1 qi,ni , con ni 1, y cada qi,j es o bien atmica o la negacin de una
frmula atmica. Por ejemplo, si p, q, y r son tomos, entonces p, p q, p q r,
y p (q r) estn en forma normal disyuntiva, mientras que p (q r) no lo est.
Probar que toda fbf es equivalente a una fbf en forma normal disyuntiva (las
formas normales conjuntivas se definen de modo anlogo, intercambiando conjun-
ciones y disyunciones, y el resultado tambin es cierto para ellas).
Sea A un conjunto de variables proposicionales, una fbf es o bien:
un elemento de A, > o o bien,
cualquier frmula de la forma: (F1 ), (F1 F2 ), (F1 F2 ), (F1 F2 ), (F1 F2 ).
En el primer caso, dichas frmulas atmicas ya estan en FND (basndonos en la

definicin).
En el segundo caso, basta describir el algoritmo empleado para llevar a cabo esta
conversin.
El algoritmo es el siguiente:
1. Eliminacin de la doble implicacin

Siempre que tengamos algo de la forma (A B) lo convertimos en la represen-
tacin equivalente:
((A B) (B A))
2. Eliminacin de la implicacin
Siempre que tengamos una FBF de la forma: (A B) lo transformamos en la
representacin equivalente:
((A) B)
3. Desplazar los hacia el interior

Empleamos las leyes de De Morgan para transformar FBFs de la forma (A B)
y (A B) en:
((A B)) ((A) (B))

((A B)) ((A) (B))
75 de 102
4. Distribuir conjunciones hacia dentro sobre disyunciones

Todas las FBFs de la forma (A(B C)) las convertiremos en su representacin
equivalente:
((A B) (A C))
obteniendo una FBF en FND.
Es decir, cualquier frmula bien formada que no sea atmica puede ser transformada
en FND aplicando sucesivamente 1-4.
Ejercicio 4.2: Sea A = {p, q, r}, sea L = A {, , , ), (}, y sea : A

{0, 1} una funcin arbitraria. Denotando tambin por su extensin nica a una
valoracin Booleana definida en fbf(L), decidir razonadamente si existe una fbf F
tal que (F ) = 1.
Decidir razonadamente qu ocurre si la cardinalidad de A es 2015 en vez de 3.
Por supuesto que existe la FBF definida: (p (p))

Para comprobarlo basta con ver que:
(
max{0, 1} = 1 si (p) = 0
(p (p)) = max{(p), 1 + (p)} =
max{1, 0} = 1 si (p) = 1
El problema no cambia al variar la cardinalidad de A, de modo que, cuando la

cardinalidad de A sea 2015 seguimos teniendo la misma FBF.
Deduzco que est mal mi razonamiento pero no se por qu. Debe haber alguna
definicin que no estoy entendiendo bien pero no se cual.
Yo lo veo bien.
Ejercicio 4.3: Sea una valoracin Booleana, y sea T := {p F BF (L) :

(p) = 1}. Demostrar que T es una teora completa.
Una teora ser completa si dada una FBF cualquiera q se tiene que T ` q o T 0 q
Si tenemos que (q) = 1 entonces q T , por definicin de T , y por tanto, T ` q.
Por otro lado, si (q) = 0 es claro que no puede deducirse q a partir de T . Vamos
a demostrarlo.
Toda FBF que pueda deducirse de T es una tautologa (puesto que en clase hemos
visto que T ` x = T x).
Por la definicin de tautologa vista en clase, sabemos que todo modelo de T tendr
evaluacin verdadera sobre la tautologa. Es decir:
76 de 102
T ` x = (x) = 1 x F BF (L)
con lo que queda claro que si (x) = 0 = T 0 x
Creo que la definicion de teoria completa no esta completa (valga la redundancia).

Yo la tengo copiada como sigue, y me queda otra demostracin:
Usamos la siguiente definicin:
T es completa T es consistente y FBF(L) p : T ` p T 0 p.
1. T es consistente:
T es consistente existe p FBF(L): T 0 p

Basta tomar p / T, entonces (p) = 0 y por esta razn, p no puede ser con-
secuencia tautlogica de T. Por el Teorema de Validez, sabemos que si T 2 p
entonces T 0 p.
Adems, siempre se puede tomar un p / T, con T6= : si q T entonces
p = (q) cumple p / T.
2. FBF(L) p : T ` p bien T 0 p
Sea p FBF(L): T ` p. Queremos ver que, T 0 (p)
T ` p = T p = (p) / T = T 2 (p) = T0 (p)
La segunda implicacin se debe a que, si p es consecuencia tautolgica de T
entonces toda valoracin 0 que satisfaga T, satisface p. En particular, podemos
tomar 0 = tal que (p) = 1. Entonces (p) = 0, es decir, (p) / T.
El otro caso es anlogo:

Sea p FBF(L): T ` (p). Queremos ver que, T 0 p
T ` (p) = T (p) = p / T = T 2 p = T0 p
Ejercicio 4.4: Sea G un grafo infinito, tal que todos sus subgrafos finitos
pueden colorearse con cuatro colores. Decidir razonadamente si G puede colorearse
con cuatro colores.
Sea G = (V, E) un grafo infinito, definimos A = V {1, 2, 3, 4} como un conjunto

de tomos, donde cada tomo (v, i) indica que el nodo v tiene color i.
As, para
P el grafo G = (V, E), poder colorearlo con 4 colores implica que el siguiente
conjunto PropA tiene un modelo:
P
= {(v, 1) (v, 2) (v, 3) (v, 4) : v V } {((v, i) (v, j)) : v V, 1 i < j 4}
{((v, i) (w, i)) : (v, w) E, 1 i 4}
Puesto que todo subgrafo finito

Pde G = (V, E) es coloreable con 4 colores,
P tenemos
que todo subconjunto finito de tiene un modelo y, por compacidad, tiene un
modelo.
77 de 102
Ejercicio 4.5: Sea X un conjunto parcialmente ordenado. Decidir razona-

damente si el orden parcial puede extenderse a un orden lineal, o total.
Sea (P, R) la representacin de un conjunto (P) parcialmente ordenado (dada la

relacin R).
Vamos a denominar como C el conjunto de todos los rdenes parciales (P, ) que
extienden R, es decir, R .
Podemos ver que los elementos de C satisfacen el lema de Zorn respecto a la
relacin puesto que si tenemos una cadena:
1 2 ... n
entonces el orden parcial (P, n ) ser una cota superior.

Por tanto, podemos aplicar el lema de Zorn y sabemos que hay un elemento maximal
en C.
Este elemento maximal, ser tal que dados dos elementos cualesquiera de P , vase
p1 y p2 , si hay un orden parcial i que los relaciona (p1 p2 , por ejemplo), entonces
tambin estn relacionados en el orden maximal.
Puesto que C es el conjunto de todos los ordenes parciales existentes sobre los
elementos de P , dos elementos cualesquiera de P estarn relacionados por algn order
parcial y por tanto estarn relacionados en el orden maximal. Es decir, el orden maximal
es un orden total.
Ejercicio 4.6: Expresar f es una funcin inyectiva" en un lenguaje de

primer orden.
xy(f (x) = f (y)) = (x = y)
Ejercicio 4.7: Expresar f es una funcin sobreyectiva" en un lenguaje de

primer orden.
Siendo la funcin f de la forma f : A 7 B
y B x A f (x) = y
y x (f (x) = y)
Me parece mejor esta definicion.
78 de 102
Ejercicio 4.8: Una forma de decir que un conjunto X es finito consiste en

afirmar que toda funcin inyectiva de X en X es sobreyectiva. Usar cuantificacin
sobre todas las funciones para probar que la nocin X es finito" puede expresarse
en una lgica de segundo orden.
Podemos expresar la nocin X es finito como:
f (f F ((x1 x2 (x1 X x2 X (f (x1 ) = f (x2 ) = x1 = x2 )))
(x2 (x2 X (x1 (x1 X (f (x1 ) = x2 )))))))
siendo F el espacio de funciones f : X 7 X
Ejercicio 4.9: Expresar la definicin habitual de f es continua" en un

lenguaje de primer orden (usando epsilones y deltas; interpretamos que el dominio
y el rango de f son los reales, con todas sus funciones habituales, valor absoluto,
suma, etc.).
Una funcin f ser continua si y slo si:

R R x1 , x2 R kx1 , x2 k < = f (x1 ), f (x2 ) <

x0 ( > 0 ( ( > 0 (x (( kx, x0 k < ) = ( f (x), f (x0 ) < ))))))
Ejercicio 4.10: Expresar la definicin habitual de f es uniformemente

continua" en un lenguaje de primer orden (usando epsilones y deltas).
Siendo la funcin f de la forma f : A 7 B

R R ( > 0)( > 0)x1 , x2 A kx1 , x2 k < = f (x1 ), f (x2 ) <

( > 0 ( ( > 0 (x1 x2 (( kx1 , x2 k < ) = ( f (x1 ), f (x2 ) < ))))))
79 de 102
Ejercicio 4.11: Buscar los axiomas de la Aritmtica de Peano, entender lo

que dicen, y entregarlos escritos.
Los 5 Axiomas de Peano son:
1. Existe un nmero natural 1. En otros trminos,1 est en N, el conjunto de los

nmeros naturales.
2. Todo nmero natural n tiene un sucesor n* (este axioma es usado para definir
posteriormente la suma).
3. 1 no es el sucesor de algn nmero natural.
4. Si hay dos nmeros naturales n y m con el mismo sucesor, entonces n y m son

el mismo nmero natural.
5. Si 1 pertenece a un conjunto K de nmeros naturales, y dado un elemento

cualquiera n, el sucesor n* tambin pertenece al conjunto K, entonces el conjunto
K debe ser el conjunto de todos los nmeros naturales. Este axioma es el principio
de induccin matemtica.
A.5. Hoja 5
Asumimos genrica e informalmente la no trivialidad. Al escribir frmulas, se per-
miten las abreviaciones razonables.
Ejercicio 5.1: Probar que en ZFC no existe una cadena infinita descendente
z1 3 z2 3 z3 3 . . . .
La demostracin de este hecho se basa en el axioma de Fundacin, que dice:

x (x 6= ) = (y x(z x(z / y)))
Supongamos que existe una cadena infinita descendente: z1 3 z2 3 z3 3 . . .

entonces tendremos una serie de funciones f : N 7 zi tal que f (i) = zi .
Estas funciones, por definicin cumplen que f (n + 1) f (n).
Definimos ahora el conjunto S = {f (n) con n N}, que representa el rango de f ,
que sabemos que puede ser visto como un conjunto debido al axioma de reemplazo.
El axioma de fundacin nos garantiza la existencia de B S tal que B S = .
Por definicin de S, tenemos que n0 tal que B = f (n0 ) pero hemos dicho, desde
el principio, que f (n0 ) contiene a f (n0 + 1), que tambin es un elemento de S.
80 de 102
Por tanto, llegamos a una contradiccin, pues empezamos suponiendo que B S =

, por lo que es imposible que exista la cadena infinita descendente que origin este
razonamiento.
Solucin del profesor: N es un conjunto. n zn es una funcin, luego su rango
S = {z1 , z2 , . . .} es un conjunto. zi S, S zi 3 zi+1 contradice fundacin y no
asumimos que dos zi son distintos. Por tanto se excluye z1 3 z2 3 . . . 3 zn 3 z1 .
Ejercicio 5.2: Sea T la teora (en un lenguaje de primer orden) que se obtiene
al anadir a los tres axiomas de la teora de grupos, un cuarto axioma xy(x = y).
Probar que T es completa.
Recordamos que una teora ser completa, por definicin, si es consistente y p, T `

p T ` p, no puede ser que no podamos deducir ninguna.
Juntando los tres axiomas vistos en clase y el que aade el enunciado tenemos:
1. 1 : xyz((x y) z) = (x (y z))
2. 2 : x(x e = e x = x)
3. 3 : xy(x y = e)
4. 4 : xy(x = y)
El ltimo axioma que hemos aadido hace que slo haya un modelo de esta teora,
es decir, slo hay un grupo que satisface todos estos axiomas simultneamente y es
el grupo trivial formado por el elemento neutro: G = {id}. Por tener un modelo, y
aplicando el Teorema de Completitud (versin 2) tenemos que T es consistente.
Puesto que slo tenemos un modelo, es obvio cualquier FBF describir una
propiedad para la que pueden ocurrir dos opciones:
1. G satisface por lo que G() = > = T . Evidentemente si la propiedad

se satisface para el modelo de la teora (el grupo G), su contrario no lo har, es
decir, en este caso tendramos G 2 = G 0
2. G no satisface , por lo que G() = = G() = T , es decir, G satisface

su opuesto. Por tanto tendramos G = G `
La idea clave de esta explicacin es que nuestra teora tiene un nico grupo que
es modelo lo que evita la posibilidad de que ciertos grupos de la teora satisfagan y
otros , como ocurra con esta misma teora antes de aadir el cuarto axioma.
Ejercicio 5.3: Sea T la teora, en un lenguaje de primer orden L, que se

obtiene al anadir a los axiomas de Peano la coleccion {n : n N}, donde n es
81 de 102
la fbf x > n, y por cada nmero natural n, n es una constante en L cuya inter-
pretacin es n. Decidir razonadamente si T es consistente. Decidir razonadamente
si T tiene un modelo.
Observacin: Ntese que cualquier L-estructura debe contener a N.
Como hemos visto en clase, cualquier interpretacin (en este caso la L-estructura)
que satisfaga los axiomas de Peano debe ser N (en este sentido, N es nico).
En efecto vemos que N es un modelo de T pues satisface los axiomas de Peano y
por ser infinito numerable satisface n con n N.
Puesto que tiene un modelo sabemos tambin que es consistente por el teorema
de completitud.
A.6. Hoja 6
Ejercicio 6.1:
a) Tomando como abreviacin de , probar que el axioma de cuantifi-
cacin para implica la siguiente vesin para : si t puede sustituir a x en ,
entonces (t|x) x(x).
b) Del mismo modo, tomando como abreviacin de , probar que el
axioma de cuantificacin para , si t puede sustituir a x en , entonces (t|x)
x(x)", implica el axioma para .
Hecho por Pedro. Se aceptan correcciones.

Apartado a)
Recordemos que el axioma de cuantificacin para nos dice que:
x(x) (t|x)
Por definicin de la implicacin podemos ver que este axioma es equivalente a:
(t|x) x(x)
Si tomamos como abreviacin de podemos escribir:
(t|x) x(x)
Por ltimo, podemos simplemente redefinir la frmula para que incluya la nega-
cin por si misma con lo que obtenemos el resultado buscado.
82 de 102
Apartado b)
El axioma de cuantificacin para es:
(t|x) x(x)
Basndonos de nuevo en la definicin de la implicacin tenemos
x(x) (t|x)
Tomando la abreviacin del enunciado llegamos a:
x(x) (t|x)
Nuevamente podemos redefinir la funcin con lo que obtenemos el resultado

deseado
Ejercicio 6.2: Probar que la regla de generalizacin para es equivalente a

la siguiente regla de generalizacin para : si x no aparece libre en , de
deducimos (x) .
Hecho por Pedro. Se aceptan correcciones.

Recordamos que la regla de generalizacin de nos dice que, siendo x una variable
libre en :
= x
Por definicin de la implciacin tenemos que la regla anterior es equivalente a:
= (x )
Reemplazando por tenemos:
= (x )
Renombrando = a y = b llegamos a:
b a = (xb) a
Ejercicio 6.3: Usamos |= como abreviacin de {} |= . Probar o

refutar:
a) x( ) |= (x) (x).
b) (x) (x) |= x( ).
c) x( ) |= (x) (x).
83 de 102
d) (x) (x) |= x( ).
e) x( ) |= (x) (x).
f) (x) (x) |= x( ).
g) x( ) |= (x) (x).
h) (x) (x) |= x( ).
i) |= x.
j) x( ) |= (x) (x).
k) (x) (x) |= x( ).
l) x( ) |= (x) (x).
m) (x) (x) |= x( ).
n) x( ) |= (x) (x).
Apartado a)
Vamos a demostrar que
x( ) |= (x) (x)
| {z } | {z }

Sea a cualquier modelo de , si tomamos b A tenemos que
a |= ((b) (b)) = a |= (x) (x) = a |=
Puesto que para todo modelo a de tenemos a |= , podemos concluir que
|=
Apartado b)
Vamos a demostrar que:
(x) (x) |= x( )
| {z } | {z }

Sea a cualquier modelo de y sean b, c A tenemos que:
a |= ((b) (c)) = a |= x( ) = a |=
|=
Apartado c)
84 de 102
x( ) |= (x) (x)
| {z } | {z }

Sea a cualquier modelo de , si tomamos b A tenemos que
a |= ((b) (b)) = a |= (x) (x) = a |=
|=
Apartado d)
En esta ocasin vamos a ver que no es cierta la FBF:
(x) (x) |= x( )
| {z } | {z }

Sea a cualquier modelo de y sean b, c A tenemos que:
a |= ((b) (c))
Si no es posible encontrar dos valores como los indicados que satisfagan b = c, no

podremos concluir x( ).
Por ejemplo:
(a) = a es par
= = T =
(a) = a es impar
Con lo que cualquier FBF es modelo de , pues es una tautologa, pero nunca
toma el valor verdadero.
Apartado e)
Vamos a ver que
x( ) |= (x) (x)
| {z } | {z }

es falsa.
Para ello basta con tomar:
(a) = a es par
(a) = a es mltiplo de 3
En estas condiciones el conjunto {3, 5, 9} es un modelo de , pues (5) (5)

tiene valor verdadero, pero es falsa en {3, 5, 9}, puesto que x es verdadero pero
x es falsa.
85 de 102
Apartado f)
(x) (x) |= x( )
| {z } | {z }

Sea a cualquier modelo de , tenemos dos opciones:
x A
En este caso es sencillo comprobar que es cierto, pues existe un x para el que
la parte derecha de la implicacin es verdad.
x A x A
En este caso podemos ver que para cualquier x que tomemos la parte izquierda
de la implicacin que define tendr valor de verdad falso, por lo que ser
verdadero.
Apartado g)
x( ) |= (x) (x)
| {z } | {z }

Sea a cualquier modelo de , existe b A tal que:
a |= (b) (b) = a |= (b) = a |= (x) (x) = a |=
|=
Solucin del profesor: Si a (x( = )), entonces
a A a (a|x) (a|x)
Esto es equivalente a que o bien a (a) o bien a (a).

Si a (a), entonces a (x(x) x(x))
Si a (a), entonces a (x(x))
Por tanto, a (x(x) x(x))
Apartado h)
(x) (x) |= x( )
| {z } | {z }

86 de 102
Sea a calquier modelo de , tomamos b A tal que:
a |= (b) = a |= (b) (b) = a |= x( ) = a |=
|=
Apartado i)
|= x
|{z} |{z}

Sea a cualquier modelo de tenemos que
a |= = a |= x = a |=
|=
Apartado j)
x( ) |= (x) (x)
| {z } | {z }

La nica forma de que no sea cierto es tener una L-estructura en la que
x(x) y (y)
Sea a cualquier modelo de tenemos
a |= x( )
Por tanto
a |= x = a |= x = a 2 y
Por tanto no puede ocurrir que no sea cierta.
Apartado k)
En esta ocasin vamos a ver que la FBF
(x) (x) |= x( )
| {z } | {z }

es falsa.
87 de 102
Por ejemplo:
(a) = a es par
(a) = a es mltiplo de 4
Tomamos un modelo a de que contenga en A los valores: {2, 3, 4}.

Es sencillo ver que una L-estructura como la mencionada es un modelo de pues
x tiene valor falso, lo que hace que sea verdadero.
Sin embargo, en estas condiciones es sencillo ver que es falso puesto que el caso
concreto del 2 cumple que es par pero no es mltiplo de 4, es decir,
(2) = > (2) = = = = a 2
Apartado l)
x( ) |= (x) (x)
| {z } | {z }

Sea a cualquier modelo de y sea b A tenemos dos opciones:
1. (b) = >
a |= (b) (b) = a |= (b) = a |= (b) = a |=
2. (b) = En este caso x = por lo que nos encontramos con que es una
tautologa y de manera trivial
a |=
|=
Apartado m)
(x) (x) |= x( )
| {z } | {z }

Sea a cualquier modelo de y sea b A, tenemos que
a |= (b) x
Aqu tenemos dos opciones:
1. b (b) = >
a |= (b) x = a |= x = a |= x( ) = a |=
88 de 102
2. b (b) = >
En este caso tendremos que siempre evala a falso y por tanto siempre es
verdadero.
Por tanto
a |=
|=
Apartado n)
x( ) |= (x) (x)
| {z } | {z }

Sea a cualquier modelo de tenemos dos opciones
1. b (b) = >
a |= (b) (b) = a |= (x) (x) = a |=
2. b (b) = >
En este caso tendremos que siempre evala a falso y por tanto siempre es
verdadero.
Por tanto
a |=
Ejercicio 6.4: Usamos ` como abreviacin de {} ` . Probar (sin usar

completitud):
a) ` x.
b) xy(x, y) ` yx(x, y).
c) ` xy(x, y) yx(x, y).
d) xy(x, y) ` yx(x, y).
e) xy(x, y) ` y(y, y).
Abreviaturas: Axioma de Cuantificacin (versin 1)(CA1), Axioma de Cuantifica-

cin (versin 2) (CA2) Regla de Generalizacin (versin 1) (G1), Regla de Generaliza-
cin (versin 2) y Clausura Universal (UC).
CA1: Si el trmino t puede sustituir al trmino x en entonces: x(x) (t|x).
89 de 102
CA2: Si el trmino t puede sustituir al trmio x en entonces: (t|x) x(x).

(Demostrado en el Ejercicio 1)
G1: Si x no aparece libre en entonces: de deducimos x
G2: Si x no aparece libre en entonces: de deducimos x (Demos-
trado en el Ejercicio 2)
Apartado a)
Solucin del profesor:
1. premisa
2. Usamos la siguiente tautologa:
(x )
3. Obtenemos x usando los pasos anteriores y modus ponens.
4. Como no tenemos variables libres, podemos usar el axioma de generalizacin:
x x
5. Tenemos la tautologa (x x) x.
6. Por modus ponens

x
Apartado b)
1. Por CA1: xy(x, y) x(x, y)
2. Por UC: x(x, y) yx(x, y)
Apartado c)
Por cuantificacin para , como y puede sustituir a y:
y(x, y) (x, y)
Por cuantificacin para , como x puede sustituir a x:
(x, y) x(x, y)
Dado que { , } ` :
y(x, y) x(x, y)
90 de 102
Por generalizacin para :

xy x
Por generalizacin para :

xy yx
Apartado d)
1. xy(x, y) premisa.
2. Utilizamos el axioma de cuantificacin ya que x puede sustituir a x
xy(x, y) y(x, y)
3. Utilizando modus ponens

y(x, y)
4. Dado que y puede sustituir a y utilizamos el axioma de cuantificacin de nuevo
y(x, y) (x, y)
5. Utilizando modus ponens obtenemos (x, y).
6. Por el apartado a) de este ejercicio: x(x, y).
7. yx(x, y).
Apartado e)
1. Por el apartado d: xy(x, y) yx(x, y)
2. Por CA1: yx(x, y) y((y|x, y)) (esto es, y (y, y))
A.7. Hoja 7
Ejercicio 7.1: Leer los ejemplos 1-6 p.24 y los ejemplos 1-10 pp. 35-36 del
libro. Sea una sentencia en el lenguaje de los anillos (Ejemplo 6 p.24), verdadera
en todos los cuerpos de caracterstica 0. Decidir razonadamente si la siguiente
afirmacin es verdadera o falsa: existe una N tal que para todo primo p > N ,
es verdad en todos los cuerpos de caracterstica p.
91 de 102
Sea verdadera en todos los cuerpos de caracterstica 0, sea Fl la teora de los

cuerpos, y sea Fl(k) la teora de los cuerpos con caracterstica k.
Con esta nomenclatura es evidente que Fl(0) {} es insatisfacible.
Por tanto, podemos encontrar un subconjunto S de Fl(0) que contenga al menos
Fl y a un conjunto finito de sentencias {n 1 6= 0 : n = 2, 3, . . . , N } tal que al aadirle
{}, sea insatisfacible.
As cualquier modelo de S ser un cuerpo de caracterstica N que no satisface
{}, es decir, cualquier modelo de la teora de los cuerpos con caracterstica N sa-
tisfacer {}, luego por el Teorema de Compacidad todos los cuerpos de caracterstica
N satisfacern .
Ejercicio 7.2: Dar un ejemplo no trivial de teora completa. Sugerencia:

buscarlo en el libro.
Segn el libro, la teora de los cuerpos algebraicos de caracterstica 0 es completa

(p 47). Dicha teora se describe en la pgina 36 de la siguiente forma:
ACF (0) := ACF {n 1 6= 0 n = 2, 3, 5, 7, 11, . . . }

Con ACF la teora de los cuerpos algebraicos cuyos modelos son los cuerpos (anillos
conmutativos con inverso multiplicativo) en los que todos los polinomios de grado
mayor o igual que 2 tienen al menos un 0.
Ejercicio 7.3: Sea L el siguiente lenguaje de primer orden con igualdad:

las constantes de L son {n : n N}, la nica funcin unaria, S1 , las funciones
binarias, +1 y 1 , y la relacin binaria <1 (los subrayados y subindices estn para
distinguir los smbolos de sus interpretaciones habituales). A efectos de este pro-
blema consideramos como versin oficial de los axiomas de Peano los N1-N9 p. 95
del libro, junto con el esquema de axiomas de la p. 111 (induccin), expresados en
el lenguaje L de la forma obvia.
a) Sea 1 la teora, en el lenguaje L, que se obtiene al anadir a los axiomas de
Peano la coleccion {n : n N}, donde n es la fbf x(n <1 x). Decidir razona-
damente si 1 es consistente. De modo ms especfico, decidir razonadamente si
1 tiene un modelo. An ms especficamente, decidir si los nmeros naturales de
toda la vida, en cuya existencia todos creemos, son un modelo de 1 . De existir
algn modelo, decidir razonadamente si es nico. Sugerencia: recordar el primer
Teorema de Incompletitud de Gdel, o el segundo.
b) Sea Lc el lenguaje de primer orden que se obtiene al anadir a L una nueva
constante c, y sea 2 la teora, en el lenguaje Lc , que se obtiene al anadir a los
axiomas de Peano la coleccin {n : n N}, donde n es la fbf n <1 c. Decidir
razonadamente si 2 es consistente. De modo ms especfico, decidir razonada-
mente si 2 tiene un modelo. Decidir si los nmeros naturales de toda la vida,
92 de 102
en cuya existencia todos creemos, son un modelo de 2 . De existir algn mode-

lo, decidir razonadamente si es nico. Sugerencia: recordar el primer Teorema de
Incompletitud de Gdel, o el segundo.
Apartado a)
Solucin del profesor: Dados los axiomas de Peano ms {x(n <1 x) : n N},
tenemos que N es un modelo si tomamos x = n + 1. Por incompletitud de Gdel,
1 0 y 1 0 . Por tanto, 1 {} y 1 {} son consistentes, luego
tienen modelos distintos no isomorfos.
Apartado b)
Solucin del profesor: Sea Lc = n : n < c. Para cada subconjunto finito,
{n1 , . . . , nk } y sea N = max{n1 , . . . , nk } + 1 N. Interpretando c como N se
tiene que N es un modelo de Peano+{n1 , . . . , nk }, luego 2 tiene un modelo por
completitud, que no es N porque no podemos interpretar c como un elemento de N
que satisfaga todas las .
Sea N un modelo de 2 . Entonces c N c > 0, c > 1, . . .. c es un nmero
natural infinito.
El esquema de induccin no falla porque no hay una sentencia de primer orden que
exprese la nocin x es finito.
A.8. Hoja 8
Los 7 primeros problemas en esta hoja proporcionan una construccin" mode-
radamente explicita (Zorn) de modelos no estndar de los naturales. Consideramos
probabilidades P finitamente aditivas, que slo toman los valores 0 y 1.
Ejercicio 8.1: Sea P una probabilidad finitamente aditiva, definida en un

lgebra de subconjuntos de N, con valores en {0, 1}. Los conjuntos con probabilidad
1 forman un filtro. Definir filtro sin utilizar probabilidades, y probar que las dos
definiciones coinciden.
Comencemos por especificar las definiciones:
Filtro Definicin A.8.1 Filtro.

Un subconjunto no vaco F de un conjunto parcialmente ordenado (P, ) es un
filtro si se dan las siguientes condiciones:
1. F no est vaco.
2. Para cada x F , x, y P , x y implica que y tambin est en F.
93 de 102
3. Para cada x, y F , existe cierto elemento z F , tal que z x y z y.
Un filtro se dice propio si no es igual a todo el conjunto P.
Filtro de Definicin A.8.2 Filtro de conjuntos.

conjuntos
Un filtro de conjuntos se obtiene tomando el conjunto potencia de un conjunto
dado S, visto como orden parcial y ordenado por la inclusin de subconjuntos. Con
ello tendremos que un filtro F sobre un conjunto S es un conjunto de subconjuntos
de S con las siguientes propiedades:
1. S est en F . (F es no vaco)
2. F no contiene al conjunto vaco. (F es propio)
3. Si A y B estn en F , tambin su interseccin. (F es cerrado bajo intersecciones

finitas)
4. Si A est en F y A es un subconjunto de B, entonces B est en F , para todos

los subconjuntos B de S.
Ahora damos la definicin de filtro utilizando probabilidades, rescatando las siguientes

definiciones:
lgebra de Definicin A.8.3 lgebra de conjuntos.

conjuntos
Dado un conjunto X, no vaco, y dado un subconjunto de sus partes M P (X),
se dice que M es un lgebra de conjuntos si:
1. M es no vaco.
2. M es cerrado
Sn por la unin finita. Esto es, si tenemos A1 , A2 , . . . , An M,
entonces i=1 Ai M.
3. M es cerrado por complementacin. Es decir, si A M entonces Ac = X \A

M.
Funcin Definicin A.8.4 Funcin de Probabilidad. P:M [0, 1] es una funcin definida
de Proba- en (, M). Siendo un conjunto.
bilidad
Si M es un lgebra entonces P es finitamente aditiva y cumple:
1. P () = 1.
2. A, B M y A B = P (A B) = P (A) + P (B) (aditividad finita).
Ya que tenemos que P : M 7 {0, 1}, lo que tenemos es que

F = A : P (A) = 1, A M
94 de 102
A partir de las definiciones de lgebra y funcin de probabilidad anteriores hemos

podido dar una definicin de filtro. Veamos que coincide con la definicin que no usa
probabilidades.
Debido a que P es una probabilidad, lo que tenemos es una cadena de inclusiones
A1 A2 An = con Ai F ; ya que el total debe estar en F y la probabilidad
no puede sumar ms de uno, luego A, B F = A B 6= . Llamamos S al
lgebra de conjuntos de N, con valores en {0, 1}.
Por construccin, tenemos que ambas definiciones son equivalentes, ya que
El filtro no puede estar vaco pues contiene al total (cuya probabilidad sabemos
que es 1),
Si Ai F , Aj S y Ai Aj implica que Aj tambin est en F.
La razn es que si Ai est en F es por que es un conjunto con probabilidad 1.
No existen conjuntos con probabilidad mayor que 1 porque no existen conjuntos
mayores que el total, y la probabilidad es finitamente aditiva. Por tanto, todo
conjunto Aj en S con probabilidad mayor o igual que Ai debe tener probabilidad
igual a 1 y por tanto estar en F .
Si Ai , Aj F , i j , Ai Aj = Ai F .
Esto es anlogo a la tercera propiedad de filtros en la definicin A.8.1 ya que la
interseccin de dos conjuntos de esa forma es siempre menor o igual que cada
uno de ellos, en particular igual al menor de ellos, de modo que est en F .
Ejercicio 8.2: Probar que todo filtro de subconjuntos de un conjunto S,

puede extenderse a un ultrafiltro (a un filtro maximal con respecto a la inclusin)
en S. Sugerencia: Zorn.
Recordemos que el lemma de zorn dice: Todo conjunto parcialmente ordenado

no vaco en el que toda cadena (subconjunto totalmente ordenado) tiene una cota
superior, contiene al menos un elemento maximal.
Dado el conjunto S tomamos un filtro cualquiera F y a partir de l definimos F
como la coleccin de filtros que contienen a F .
Es sencillo ver que F no es vaco, pues contiene a F y, adems, F est ordenador
por inclusin.
Consideramos ahora D = (Di ) una cadena en F y definimos D = Di .
Con esta definicin es sencillo ver que D es un filtro, pues satisface las condiciones
de la definicin:
Demostracin. Si tomamos dos elementos x, y D entonces existen dos subndices
i, j tales que x Di y y Dj . Al ser D una cadena, para algn k {i, j} se ha
de tener que x, y Dk . Como Dk es un filtro, x, y Dk D.
Por otro lado, si x D y tenemos un elemento x y, entonces para algn i
tenemos x Di y al ser este un filtro, y Di D. Ahora bien, como para todo i
/ Di , se tiene que
/ D.
95 de 102
Queda concluido que D es un filtro propio que acota superiormente a la cadena D

con lo que se satisfacen las hiptesis del lema de zorn.
Como conlusin, existe un elemento maximal de F, que ser un ultrafiltro.
Ejercicio 8.3: Probar que si U es un ultrafiltro en S, para todo A S, o

A U o Ac U .
En primer lugar, nos damos cuenta de que no puede ocurrir: A U y Ac U

puesto que por la propiedad de las intersecciones finitas se dara: A Ac U pero
A Ac = y / U , si U es un filtro (en particular un ultrafiltro).
Para todo conjunto A tenemos diferentes posibles casos.
Si A U ya hemos completado el ejercicio.
Si A / U definimos V como el filtro generado por U A. Al ser U un ultrafiltro
contenido propiamente en V tenemos que, necesariamente, V = S, puesto que U es
maximal y no puede haber otro filtro mayor que l (distinto del total). Por tanto U A
no tiene la propiedad de interseccin finita (de lo contrario sera un filtro).
As, existen u1 , ..., un U tales que
u1 u2 ...un A =
Por tanto ui Ac lo que implica que Ac U , por la definicin de filtro.
Ejercicio 8.4: Probar que si U es un ultrafiltro en S, y A1 An = S,

entonces existe una j {1, . . . , n} tal que Aj U .
Si no existiera j {1, ..., n} tal que Aj U tendramos que, para cada j, Acj U .
Pero el filtro es cerrado por la interseccin finita de modo que
\
Acj U
Pero, por definicin tenemos que Acj = que no puede pertenecer a U por
T
definicin de filtro 1 .
Ejercicio 8.5: Sea nN Xn un producto Q cartesiano de conjuntos no vacos,

Q
y sea U un ultrafiltro en N. Para x, y nN Xn , definimos x y si x e y
son iguales casi seguro, es decir si {n N : xn Q
= yn } U . Probar que
es una relacin de equivalencia. Al conjunto U := nN Xn / se le denomina
ultraproducto.
1
En caso de contener el vaco, la primera propiedad de filtro hace que el filtro sea el total.
96 de 102
Si es una relacin de equivalencia, entonces cumple las siguientes propiedades:
x x Reflexiva
x y = y x Simtrica
x y, y z = x z Transitiva
Tenemos que probar que para x, y Xn , U ultrafiltro en N

Q
nN
def
{n N : xn = yn } U
xy
Gracias a que la igualdad es una relacin de equivalencia, tenemos que si x y,

{n N : xn = yn } = {n N : yn = xn } = y x
Debido a que la igualdad es simtrica, ambos conjuntos de ndices contendrn los
mismos elementos n, y si x y, entonces dicho conjunto de ndices pertenece a U .
PorQel mismo motivo, si {n N : xn = xn } U , entonces x x; ya que
x Xn , xn = xn n.
nN
Finalmente, tenemos que si xn = yn , yn = zn = xn = zn , es decir,

x y, y z = x z
Ejercicio 8.6: Tomando Xn = N para todo n en la construccin anterior,

probar que U es un modelo de los axiomas de Peano. Sugerencia: Buscar en la
literatura el Teorema Fundamental de los Ultraproductos, de o, e invocarlo.
Atendiendo a la sugerencia del enunciado, invocamos el teorema fundamental de

los ultraproductos.
Teorema A.8.1 (Teorema Fundamental de los Ultraproductos de o). Consi-

deremos una familia {Mi }iI de modelos de un lenguaje formal L y sea U un
ultrafiltro en I.
Si (x1 , ..., xn ) Form(L) y f1 , ..., fn iI Mi , entonces
Q
U
Y
M |= [[f1 ], . . . , [fn ]] {i I : Mi |= [f1 (i), . . . , fn (i)]} U
iI
En particular, si es una sentencia

U
Y
M |= {i I : Mi |= } U
iI
97 de 102
Imitando la construccin del ejercicio anterior con Xn = N construimos el ultra-

producto Y
U= N/
nN
Ejercicio 8.7: Probar que si el ultrafiltro U contiene a todos los subconjuntos

de N con complemento finito, entonces existe una c U tal que para todo n
N, c > n. Sugerencia: tomar cn = n.
El ultrafiltro U es un caso particular de filtro de Frchet o tambin conocido co-

mo filtro cofinito. El filtro de Frchet F en el conjunto X el conjunto de todos los
subconjuntos A de X tales que el complemento de A en X es finito.
Si un subconjunto de N tiene complemento finito, puesto que N es infinito, es obvio
que el subconjunto en cuestin ser infinito.
Por tanto, queda claro que el ultrafiltro U est formado por todos los subconjuntos
de N infinitos.
Ejercicio 8.8: Dada la MT con alfabeto {B, 1, 2}, definida por

{(q0 1 2 q0 ), (q0 2 D q0 ), (q0 B D q0 )}, determinar su output cuando el input
es 1 1 B B 1 B 2 B (el resto de la cinta son B 0 s). Describir en general que hace
esta MT, y si se detiene el algn momento o no.
Esta MT recorre la cinta buscando 1s, cuando encuentra un 1, lo cambia por un 2,

y sigue avanzando hacia la derecha. Esta MT no para nunca, ya que en la cinta solo
puede haber caracteres en el alfabeto {B, 1, 2}, si encuentra un 1 lo convierte en un
2, y si se encuentra un 2 un B avanza a la derecha, de manera que no parar nunca
de desplazarse a la derecha.
Para el input dado, realizar las siguientes acciones:
1. empezamos en el estado q0 y con el cabezal en el 1 de la izquierda. Reescribimos

ese 1 por un 2 y pasamos al estado q0 . La cinta queda as: 2 | 1 | B | B | 1 | B | 2 | B . . .
2. como estamos en el estado q0 y leemos un 2, avanzamos a la derecha y pasamos

al estado q0 . La cinta no cambia.
3. como estamos en el estado q0 y leemos un 1, lo cambiamos por un 2 y pasamos

al estado q0 . La cinta queda as: 2 | 2 | B | B | 1 | B | 2 | B . . .

5. como estamos en el estado q0 y leemos B, avanzamos a la derecha y pasamos al

estado q0 . La cinta no cambia.
98 de 102

7. como estamos en el estado q0 y leemos 1, lo cambiamos por un 2 y pasamos al

estado q0 . La cinta queda as: 2 | 2 | B | B | 2 | B | 2 | B . . .




A partir de ahora, suponiendo una cadena infinita de smbolos B, la MT no parar

de avanzar a la derecha.
99 de 102
Bibliografa
[Hal74] Paul Halmos. Naive Set Theory. Undergraduate Texts in Mathematics.

Springer-Verlag, 1974.
[vdD07] Lou van den Dries. Mathematical logic. http://www.math.uiuc.edu/

~henson/Math570/Fall2009/Math570notes.pdf, Fall Semester 2007.
100 de 102
ndice alfabtico
lgebra Mquinas de Turing, 43

de conjuntos, 94 Menor, 19
Minimizacin no acotada, 48
Aridad, 3 Modelo, 6, 30
Cardinalidad, 39 Palabra, 2
Clausura universal, 16 Primer Teorema de incompletitud de G-
Codificacin, 53 del, 24
Conjunto problema de la detencin, 51
recursivamente enumerable, 48 Producto de los naturales, 18
recursivo, 48 Proposicin o frmula bien formada, 2
recursivo primitivo, 47 Prueba, 30
Consecuencia
lgica, 29, 31 Relacin k-aria recursiva primitiva, 47
tautolgica, 6
Consistencia (CON), 57 Satisfacin, 9
Segundo Teorema de incompletitud de G-
Demostracin o prueba, 4 del, 25
Demostracin o prueba (II), 5 Sistema completo, 6
Sucesor, 18
Equivalencia lgica, 7 Suma en los naturales, 18
Frmula Trmino, 27
atmica, 27 constante, 36
bien formada, 27 Teora, 4, 30
cerrada, 27 completa, 11
Filtro, 93 consistente, 7
de conjuntos, 94 de (Teor()), 54
Funcin deducible, 54
de Probabilidad, 94 recursiva, 54
parcial, 46 Teorema
recursiva, 48 de Cantor, 25
recursiva primitiva, 46 de compacidad, 13
Interpretacin, 5 de completitud, 10, 24
Isomorfismo, 34 de completitud II, 12
de Lwenheim-Skolem generalizado, 39
L-estructura, 27 de la deduccin, 7
la paradoja de Russel, 17 de Lindenbaum, 11
Lenguaje de primer orden, 26 de Lowenheinn-Skolem, 39
Los naturales, 18 de Presburger y Skolem, 24
101 de 102
Fundamental de los Ultraproductos de

o, 97
Primero de incompletitud, 55
Segundo de incompletitud, 57
Testigo de , 37
variable
libre, 27
ligada, 27
102 de 102

Logica Matematica

Cargado por

Copyright:

Formatos disponibles

Logica Matematica

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Logica Matematica

Cargado por

Copyright:

Formatos disponibles

Lgica Matemtica

Pedro Valero Meja y Guillermo Apuntes UAM

ndice alfabtico 101

donde los smbolos representan

Palabra Definicin 1.1 Palabra. Concatenacin de smbolos.

Si F1 y F2 son frmulas, tambin lo son

En notacin polaca son frmulas bien formadas:

Las frmulas bien formadas pueden definirse de manera inductiva:

Las frmulas bien formadas son F BF =

Aridad Definicin 1.3 Aridad. La aridad de un operador es el nmero de argumentos que

, > son 0-arias.

, , = , son 2-arias (binarias).

Hay que distinguir los siguientes casos:

F es atmica. La legibilidad nica es obvia.

F es es de la forma G, donde G es una FBF. La legibilidad nica es obvia.

F es de la forma (G1 G2 ) donde G1 y G2 son FBF y es una conectiva binaria.

Observacin: a b c no es una frmula bien formada, ya que no tiene parntesis

Usamos p, q, r, s, . . . para denotar frmulas bien formadas.

1.2. Axiomas de la lgica proposicional

Demostracin Definicin 1.4 Demostracin o prueba. Una demostracin o prueba (formal) es

Escribimos  p para denotar que p es verdad.

Teora Definicin 1.5 Teora. T (o ) es una teora si es un conjunto de FBF(L).

Interpretacin Definicin 1.7 Interpretacin. Una interpretacin es una valoracin booleana :

Teorema 1.2. Sea : A {0, 1} una funcin arbitraria. Entonces se extiende,

Demostracin. Por el lema de legibilidad nica.

Ejemplo: Los siguientes conjuntos son completos.

{, } no es completo. Se puede probar por monotona.

Modelo Definicin 1.9 Modelo. Sea T F BF (L). Un modelo de T es una valoracin

Consecuencia Definicin 1.10 Consecuencia tautolgica. Decimos que p es una consecuencia

Observacin: Si T = , entonces toda es un modelo de T .

Equivalencia Definicin 1.11 Equivalencia lgica. Si  p q, es decir, si p q es una

Observacin: Sea r una F BF (L), sea p una subfrmula de r y sea cualquier

Teora Definicin 1.12 Teora consistente. T es consistente si T 0. La consistencia o

Observacin: Si T es inconsistente, T ` cualquier cosa. Por otra parte, ninguna

Teorema 1.3 (Teorema de la deduccin). Si T {p} ` q, entonces

Si n = 1 entonces q = p o q T o q es un axioma lgico, lo cual

Caso 2: q es un axioma lgico, q T o q = p.

en el que usamos q en lugar de r y p en lugar de q, instanciamos

Usando modus ponens y lo anterior T ` (p = q).

1.4. Problemas TAUT y SAT

El problema es saber cunto tiempo se tarda en averiguar si F es una tautologa

Ejemplo: Dada la siguiente FBF y la tabla de verdad correspondiente:

Tiempo (tamao de los datos) < O((n + k)2n )

NP: tiempo polinmico no determinista. La solucin la proporciona un orculo,

La clase de problemas NP-difcil se define como aquella que contiene a los

La clase de problemas NP-completo se define como la interseccin entre la

No se sabe si P=NP. Clay Mathematics Institute ha ofrecido un premio de un

Se sabe que TAUT es NP-difcil.

Satisfacin Definicin 1.13 Satisfacin. satisface a T si p T , (p) = 1, o equivalentemente,

Problema de la satisfacin (SAT): Si F F BF (L), determinar si existe una

Ejemplo: Comprobar si p = (p = q).

Comprobacin: tiempo O(n + k).

Demostracin. Por induccin en la longitud de la demostracin.

Caso n = 1: p1 = p es un axioma, luego es una tautologa.

Caso n > 1: p = pn , y para toda j n, pj es una tautologa.

Si p es una axioma, entonces p es una tautologa.

Teorema 1.5 (Teorema de completitud). Sea T = .

Teorema 1.6. Si T es consistente, entonces, para toda p, o T ` p, o T ` p, o

Teorema 1.7. Si T 0 p, entonces T {p} es consistente. Por tanto T es

Escribimos p para denotar que p es verdad.

Equivalencia Definicin 1.11 Equivalencia lgica. Si p q, es decir, si p q es una

=: Por validez, T ` p = T p. Si T es inconsistente, T `, luego