Caṕıtulo 1

Álgebra Universal

Problema 1 Demuestra que un conjunto G provisto de una operación asociativa (denotada poryuxtaposición) que satisface:

Existe e ∈ G tal que ex = x para todo x ∈ G, ypara cada x ∈ g existe un único x′ ∈ G tal que x′x = e,

es necesariamente un grupo.

Sol. Observemos en primer lugar que (ab)′ = b′a′. Por otra parte xa = xb implica a = b. Por lotanto la ley de simplificación a izquierda se satisface en G. Ahora bien, si tenemos una igualdadax = bx se tiene también x′a′ = x′b′ lo que implica a′ = b′. Por otro lado como e = ee = e′e se tienee′ = e′′. Dado que e = e′′e′, como e′ = e′′ se tiene e = e′e′ = (ee)′ = e′. Hemos demostrado arribaque la igualdad ax = bx implica a′ = b′. Veamos ahora que también implica a = b. En efecto, sia′ = b′, de la igualdad a′aa = ea = a se deduce b′aa = a = ea lo que implica e = (b′a)′ = a′b′′

y como también e = a′a se tiene la igualdad a′b′′ = a′a lo que implica a = b′′. De modo análogob = a′′ y entonces a = b′′ = a′′ = b. Ya tenemos las leyes de simplificación por dos lados. Ahorabien, como x′e = x′ se tiene que a′aa′ = ea′ = a′ = a′e y simplificando aa′ = e. Como consecuenciaa′′ = a para todo a y este hecho junto con x′e = x′ (para todo x), implica que e es elemento neutrocuando multiplica por la derecha.

Problema 2 Demuéstrese que la siguiente definición de operación derivada inducida por untérmino es equivalente a la dada en el caṕıtulo I: si t ∈ FΩ(Xn) y a1, . . . , an son elementosde una Ω-álgebra A, entonces tA(a1, . . . , an) = f̄(t) donde f̄ : FΩ(Xn) → A es el único morfismoque extiende a f : Xn → A dada por f(xi) = ai para i = 1, . . . , n.

Sol. Si t = xi es un elemento de Xn, entonces tA(a1, . . . , an) = ai = f(xi) = f̄(xi) = f̄(t).Supongamos ahora que t = ωt1 · · · tp es un elemento que no es una variable, y ω tiene aridad p.Entonces

tA(a1, . . . , an) = ωA((t1)A, . . . , (tp)A)(a1, . . . , an) = ωA(· · · , (ti)A(a1, . . . , an), · · ·) =

= ωA(· · · , f̄(ti), · · ·) = f̄(ωt1 · · · tp) = f̄(t).

Problema 3 Para algún tipo fijado Ω, sean s, t y u Ω–términos y xi, xj variables distintas. Sedenota por s[t, u/xi, xj ] al término obtenido de s por la sustitución simultánea en s de xi por t yde xj por u. Demuéstrese que s[t, u/xi, xj ] no coincide, en general, con s[t/xi][u/xj ], pero śı con

s[t[xn/xj ]/xi][u/xj ][xj/xn],

donde n es lo suficientemente grande como para que la variable xn no figure ni en s ni en t ni enu.

1

2 CAPÍTULO 1. ÁLGEBRA UNIVERSAL

Sol. Sea s un Ω-término y x1, . . . , xn variables distintas. Sean t1, . . . , tn términos cualesquiera. En-tonces denotaremos por s[t1, . . . , tn/x1, . . . , xn] al término obtenido por la sustitución simultáneaen s de cada xi por ti. Para formalizar esta definición consideremos el conjunto de variables Xconteniendo a {x1, . . . , xn} y la aplicación f : X → FΩ(X) tal que f(xi) = ti para i = 1, . . . , n.Sea entonces f̄ : FΩ(X) → FΩ(X) el único homomorfismo de Ω-álgebras tal que f̄(xi) = ti. En-tonces definimos s[t1, . . . , tn/x1, . . . , xn] := f̄(s). En consecuencia s[t, u/xi, xj ] = f̄1(s) dondef1(xi) = t, f1(xj) = u y f1(xk) = xk para todo k 6= i, j. El hecho de que en general nose tiene s[t, u/xi, xj ] = s[t/xi][u/xj ] se pone de manifiesto tomando el tipo Ω = {b} una op-eración binaria y X un conjunto con al menos dos variables . Tomemos dos variables distintasxi y xj y definamos s = bxixj , t = bxixj y u = xi. Entonces s[t, u/xi, xj ] = bbxixjxi mien-tras que s[t/xi][u/xj ] = (bbxixjxj)[u/xj ] = bbxixixi. Ahora queremos demostrar s[t, u/xi, xj ] =s[t[xn/xj ]/xi][u/xj ][xj/xn]. Sea α : X → FΩ(X) la aplicación tal que α(xi) = t[xn/xj ] y α(xj) =xj para j 6= i. Sea β : X → FΩ(X) tal que β(xj) = u y β(xk) = xk para k 6= j. Seapor último γ : X → FΩ(X) tal que γ(xn) = xj y γ(xp) = xp para todo p 6= j. Entoncess[t[xn/xj ]/xi][u/xj ][xj/xn] = γ̄(β̄(ᾱ(s))) pero γβα = f1 ya que

γβα(xi) = γβ(t[xn/xj ]) = γ(t[xn/xj ]) = t = f1(xi),

por otra parte γβα(xj) = γβ(xj) = γ(u) = u = f1(xj) y para k 6= i, j se tiene γβα(xk) =γβ(xk) = γ(xk) = xk. En consecuencia γ̄β̄ᾱ = f̄1 lo que resuelve el problema.

Problema 4 Sea T una teoŕıa algebraica. Pruébese que el conjunto unitario {0} tiene una únicaT–estructura, aśı como que el conjunto vaćıo posee una T–estructura si y solo si T no contieneoperaciones 0–arias.

Sol. El conjunto {0} tiene una única T -estructura, ya que para cada natural n existe una únicaaplicación {0}n → {0} dada trivialmente por (0, . . . , 0) 7→ 0. Por otra parte si T no tiene opera-ciones 0-arias, para cualquier natural n ≥ 1 existe una (única) aplicación ∅ : ∅n → ∅ ya que paran ≥ 1 se tiene ∅n = ∅. Para n = 0 se tiene ∅0 = {∅} y no existe ninguna aplicación {∅} → ∅.

Problema 5 Sean Ω = {m, i, ē} un tipo operacional con α(m) = 2, α(i) = 1, α(ē) = 1 y E elconjunto constituido por las cuatro identidades:

i) (m x m y z = m m x y z),

ii) (ē x = ē y),

iii) (m ē x x = x) y

iv) (m i x x = ē x).Demuéstrese que cada grupo es, de forma natural, un (Ω, E)–modelo. ¿Es cierto el rećıproco?

Sol. Si G es un grupo con producto (x, y) 7→ xy se demuestra que es un Ω-modelo definiendo mGcomo el producto del grupo, iG como la aplicación que a cada x ∈ G le asocia su inverso parael producto del grupo, y ēG como la aplicación x 7→ e donde e es el elemento neutro del grupo.Veamos el rećıproco: si G es el conjunto vaćıo entonces por el problema anterior se tiene que G esun Ω-modelo ya que el tipo Ω no tiene operaciones 0-árias. Evidentemente el conjunto vaćıo no esun grupo. Pero todos los demás Ω-modelos distintos del conjunto vaćıo son grupos aplicando lodemostrado en el problema 1.

Problema 6 Sea Ω el tipo operacional de un grupo. De un Ω–término t se dirá que es reducidosi consta del único śımbolo e, o bien obedece al patrón mm. . .mw, donde w es una cadena deśımbolos compuesta solo por variables y la operación i, la cual no contiene subcadenas de la formaii, ixx o xix, y esta última posibilidad no aparece excepto como parte de la subcadena ixix.

i) Descŕıbase un algoritmo capaz de tomar un término cualquiera t y, a partir de él, producir untérmino reducido t̄ tal que (t = t̄) sea una identidad derivada de la teoŕıa de grupos.

3

ii) Pruébese que el conjunto R(X) de todos los términos reducidos en las variables X es un grupoque contiene a X como subconjunto. Considerando el morfismo inducido de F(Ω,E)(X) a R(X),cuya existencia queda asegurada por la propiedad universal del teorema 1.4, demuéstrese que si sy t son términos reducidos tales que (s = t) es una identidad derivada, entonces s y t coinciden.

iii) Úsense los apartados anteriores para resolver el problema de las palabras en la teoŕıa de grupos.

Sol. La descripción del algoritmo queda como ejercicio para el lector. Sea f : F(Ω,E)(X) → R(X)el morfismo de álgebras dado por la propiedad universal del álgebra F(Ω,E)(X). Tomemos dostérminos reducidos s, t ∈ R(X) tales que s = t es una identidad derivada. Al ser términos reducidosson puntos fijos de f y como s = t es una identidad derivada, entonces f(s) = f(t). Pero siendo sy t puntos fijos de f concluimos que s = t.

Problema 7 Sea T una teoŕıa algebraica que contiene una operación ternaria p (posiblementederivada) para la cual

(∗) (p x y y = x) y (p x x y = y)

son identidades (bien primitivas, bien derivadas) de T . Supóngase que A es un T–modelo tal quecierto subconjunto R de A × A es un submodelo que contiene a la diagonal {(a, a) : a ∈ A}.(Utiĺıcense las definiciones previsibles de modelo producto y submodelo.) El conjunto R puede servisto como un relación binaria en A que satisface la propiedad reflexiva.

i) Pruébese que R es también simétrica y transitiva.

ii) Rećıprocamente, si T es una teoŕıa algebraica con la propiedad de que cada submodelo re-flexivo del cuadrado de un T–modelo es también simétrico, demuéstrese que T contiene algunaoperación ternaria p, primitiva o inducida, que satisface las identidades (*). Indicación: con Fel T–modelo libre engendrado por {x, y}, considérese el submodelo R de F × F engendrado por{(x, x), (x, y), (y, y)}.iii) Dese un ejemplo de una operación p verificando (*) cuando T es la teoŕıa de grupos, perorazónese por qué no hay tal operación en la teoŕıa de los semigrupos. Se recuerda que la teoŕıa delos semigrupos se obtiene de la de los grupos borrando la operación i y la identidad primitiva enla que está involucrada.

Sol. i) Veamos la propiedad simétrica: si (a, b) ∈ R entonces p(b, b)(a, b)(a, a) ∈ R pero

p(b, b)(a, b)(a, a) = (pbaa, pbba) = (b, a)

luego (b, a) ∈ R. Para demostrar la propiedad transitiva supondremos (a, b), (b, c) ∈ R. Entoncesp(a, b)(b, b)(b, c) ∈ R pero p(a, b)(b, b)(b, c) = (pabb, pbbc) = (a, c), por lo tanto (a, c) ∈ R.

ii) Sea T = (Ω, E) la teoŕıa algebraica en cuestión. Sea R el T -submodelo de F × F generadopor los elementos (x, x), (x, y) y (y, y). Como R es un T -modelo transitivo por hipótesis debeser entonces simétrico. Por lo tanto (y, x) ∈ R lo que quiere decir que existe ω ∈ R tal que(y, x) = ωR(a1, b1) · · · (an, bn) siendo n la aridad de ω, y (ai, bi) siendo algunos de los elementos(x, x), (x, y), o (y, y). Supongamos que (ai, bi) = (x, x) para i = i1, . . . , ip, que (ai, bi) = (x, y) parai = j1, . . . , jq , y (ai, bi) = (y, y) para i = k1, . . . kr. Consideremos entonces la operación derivadapabc = ωx1 · · ·xn donde Se deja al lector demostrar que pxyy = x y pxxy = y.

iii) Para el último apartado basta con exhibir una semigrupo S provisto de una relación binariareflexiva pero no simétrica. Por ejemplo podŕıamos mencionar el conjunto de los naturales con larelación de orden habitual.

Problema 8 Considérense 2 = {0, 1}, con su estructura habitual de álgebra de Boole, y n unnúmero natural. Pruébese que cada función ω : 2n → 2 es (la interpretación) de una operaciónderivada de la teoŕıa de las álgebras de Boole. Indicación: procédase por inducción sobre n.Dedúzcase de lo anterior que el álgebra de Boole libre engendrada por n variables consta de 22

n

elementos.

4 CAPÍTULO 1. ÁLGEBRA UNIVERSAL

Sol. Para n = 1 tenemos una función ω : 2→ 2 y el lector puede ver sin dificultad que cualquierade las cuatro posibilidades es la interpretación de una operación derivada de la teoŕıa de álgebrasde Boole. Supongamos entonces n > 1 y que el resultado es cierto para cualquier aplicación 2k → 2con k < n y sea ω : 2n → 2. Entonces se demuestra que ω es la interpretación de una operaciónderivada teniendo en cuenta la igualdad

ω(x1, . . . , xn) = (1 + x1)ω(0, x2, . . . , xn) + x1ω(1, x2, . . . , xn),

y aplicando la hipótesis inductiva a las funciones 2n−1 → 2 tales que

(a1, . . . , an−1) 7→ ω(0, a1, . . . , an1)(a1, . . . , an−1) 7→ ω(1, a1, . . . , an1).

Para la última parte del problema téngase en cuenta que el cardinal del conjunto de todas lasaplicaciones 2n → 2 es exactamente 22n .

Problema 9 En la teoŕıa B de las álgebras de Boole, sea ↓ la operación binaria derivada de Bdefinida mediante

(x ↓ y) = ¬(x ∧ y).Pruébese que la subteoŕıa B0 de B engendrada por ↓, es decir, el conjunto de todas las operacionesderivadas de ↓, contiene a todas las operaciones de B salvo a las 0–arias > y ⊥. Con mayorgeneralidad, demuéstrese que una única operación no puede generar a todo B.

Sol. Para la primera parte del problema téngase en cuenta que ¬x = x ↓ x, x ∧ y = ¬(x ↓ y),x ∨ y = ¬(¬x ∧ ¬y), x ⇒ y = ¬x ∨ y. Una operación de aridad 0 o 1 no puede generar toda lateoŕıa obviamente. Si consideramos una operación ω de aridad mayor o igual a dos, el conjunto deoperaciones derivadas de ω no incluiŕıa a las operaciones de aridad 0.

Problemas propuestosProblema 1 Sea G un conjunto con una operación binaria (denotada por yuxtaposición), unaaplicación i : G→ G y un elemento e ∈ G tal que:

(1) La operacíıon binaria es asociativa,(2) ex = x para cada x ∈ G,(3) i(x)x = e para cada x ∈ G.Demuéstrese que G es un grupo.

Sugerencia: partiendo de i(x)x = e multipĺıquese por i(x) a la derecha y por i(i(x)) a la izquierda.Se obtendrá tras un poco de cálculo que xi(x) = e. Después xe = xi(x)x = · · ·.

Problema 2 Demuéstrese que dado un tipo operacional Ω, se puede construir una categoŕıa Ccuyos objetos son las Ω-estructuras y cuyos morfismo son los homomorfismos de Ω-estructuras.Fijado un conjunto X definamos ahora la categoŕıa CX cuyos objetos son las parejas (f,A) dondeA es una Ω-estructura y f : X → A una aplicación. Para dos objetos O1 = (f,A) y O2 = (g,B) deCX definimos homCX (O1, O2) como el conjunto de todos los morfismos de Ω-estructuras θ : A→ Btales que θf = g. Sea i : X → FΩ(X) la inclusión canónica, demuéstrese que (i, FΩ(X)) es unobjeto inicial de CX (un objeto U de una categoŕıa es inicial cuando para cualquier otro objeto Vde la misma, solo existe una morfismo de U a V ).

Problema 3 Dada una teoŕıa algebraica T = (Ω, E), constrúyase una categoŕıa D cuyos objetossean los modelos de T (también llamados T -álgebras) definiendo adecuadamente la noción demorfismo de T -álgebras. Para un conjunto fijado X Def́ınase la categoŕıa DX análogamente acomo se hizo en el ejercicio anterior. Probar que F(Ω,E)(X) se puede interpretar como formandoparte de un objeto inicial de la categoŕıa DX .

5

Problema 4 Demuéstrese que dos objetos iniciales de una categoŕıa son necesariamente isomor-fos. Conclúyase que las álgebras universales FΩ(X) y F(Ω,E)(X) son únicas salvo isomorfismo.

Problema 5 1. Sea Ω = {e,m} un tipo en el que e es de aridad 0 y m de aridad 2.Supongamosque E está formado por las ecuaciones mex = x y mxe = x. Consideremos un conjunto Aque es modelo para dos (Ω, E) estructuras {ei,mi} (i = 1, 2) tales que las operaciones de lasegunda estructura son Ω-homomorfismos 1→ A y A×A→ A para la primera. Demuéstreseque A satisface las ecuaciones e1 = e2 y m

1m2xzm2yt = m2m1xym1zt. Deducir que m1 =m2 y que m1 es asociativa y conmutativa.

2. Pı́dale a un topólogo algebraico que le explique qué tiene lo anterior que ver con el hecho deque el grupo fundamental de un grupo topológico sea abeliano.

Sugerencia. El hecho de que las operaciones de la segunda Ω-estructura sean homomorfismos paralas de la primera hay que interpretarlo como la conmutatividad de los siguientes diagramas

(A×A)× (A×A) A×A//

A×A��

A//��

m1A×A

m1A

m2Am2A×m2A

1× 1 1//

A��

A×A��

//

1×1

e2A.

m1A

e2A×e2A

Hay que tener en cuenta que m2A : A2 → A solo puede homomorfismo de la Ω-álgebra A2 a la

Ω-álgebra A y análogamente para e2A. Para la segunda parte del problema es mejor consultar lareferencia [2, p. 33-44].

Problema 6 Sea T = (Ω, E) una teoŕıa algebraica tal que el tipo operacional Ω contiene unaoperación de aridad dos s, otra de orden uno o y otra de orden cero e, tal que E contiene igualdadesque nos dicen que:

s es conmutativa, posee elemento neutro dado por la operación e y sxoy = soyx = e parax, y ∈ X.

toda operación w ∈ Ω es distributiva respecto a s, es decir E contiene las ecuacionesωx1 · · ·xi−1sabxi+1 · · ·xn = sωx1 · · ·xi−1axi+1 · · ·xnωx1 · · ·xi−1bxi+1 · · ·xn, para a, b, xi ∈X y todo i.

Estúdiese entonces la posibilidad de dar una noción de ideal para los modelos de T que permita laconstrucción de cocientes en dichos modelos. Definir núcleos e imágenes para homomorfismos deT -álgebras y estudiar los teoremas de isomorf́ıa clásicos en el contexto de estas estructuras.

Problema 7 Construir el anillo Z[x] mediante un álgebra universal del tipo F(Ω,E)(X).

Problema 8 Sea Ω el tipo operacional de la teoŕıa de anillos, es decir, Ω = {m, s, o, 0, 1} dondem y s son de aridad 2 y representan la multiplicación y suma del anillo respectivamente, o es dearidad uno y representa la operación de tomar opuestos, y 0 y 1 son de aridad cero y representana los elementos neutros de s y m respectivamente. Sea E el conjunto de identidades que se usapara definir el concepto de anillo y consideremos la teoŕıa algebraica R = (Ω, E) de anillos. SeaX = {x, y} un conjunto de cardinal dos y consideremos el ideal I de A := F(Ω,E)(X) generado porsmxx1, smyy1, smxymyx. Sea Q := A/I el anillo cociente. Usando una notación estandar en laque s se representa por + y m por la yuxtaposición, demuéstrese que cada clase de equivalenciade Q tiene un representante de la forma n11 + n2x + n3y + n4z donde cada ni es un entero yz := xy. Si denotamos por 1 la clase de equivalencia de 1, por i la de x, por j la de y, y por k lade z, demuéstrese que i2 = j2 = ijk = −1.

6 CAPÍTULO 1. ÁLGEBRA UNIVERSAL

Caṕıtulo 2

Cálculo proposicional

Problema 10 ¿Cuáles de las siguientes expresiones compuestas son tautoloǵıas?

i) (((p⇒ q)⇒ p)⇒ p)ii) (((p ∨ q) ∧ ¬p)⇒ q)iii) (p⇒ (¬p ∨ q))iv) (((p ∧ ¬q)⇒ r)⇒ q)v) (((p⇒ q) ∧ (r ⇒ s))⇒ ((p ∧ r)⇒ (q ∨ s)))vi) (((p⇒ q) ∨ (r ⇒ s))⇒ ((p ∧ r)⇒ (q ∨ s)))

Sol. Escŕıbanse las tablas de veracidad de las diferentes proposiciones.

Problema 11 Escŕıbase una deducción del teorema (⊥ ⇒ q) y complétese a otra del teorema(¬p⇒ (p⇒ q)).

Sol. Sea a la proposición a = (¬¬q ⇒ q) que como se puede observar es el tercer axioma denuestra axiomática del cálculo de proposiciones. Entonces:

1. (⊥ ⇒ a)⇒„⊥ ⇒ ¬¬q)⇒ (⊥ ⇒ q)

«Axioma

2. a Axioma3. a⇒ (⊥ ⇒ a) Axioma4. ⊥ ⇒ a Modus Ponens 2,35.

„⊥ ⇒ ¬¬q)⇒ (⊥ ⇒ q)

«Modus Ponens 1,4

6. ⊥ ⇒ ¬¬q Axioma 17. ⊥ ⇒ q Modus Ponens 5,6.

Vamos ahora a completar a una demostración formal de que ¬p ⇒ (p ⇒ q)). Para simplificaralgo la escritura definamos la proposición b = [(⊥ ⇒ q) ⇒

(p ⇒ (⊥ ⇒ q)

)] que es una forma del

axioma x⇒ (y ⇒ x).

8. (⊥ ⇒ q)⇒“

(p⇒ ⊥)⇒ (⊥ ⇒ q)”

Axioma

9. ⊥ ⇒ q 7.10.

“(p⇒ ⊥)⇒ (⊥ ⇒ q)

”Modus Ponens 8,9

11. b⇒“

(p⇒ ⊥)⇒ b”

Axioma

12. b Axioma13.

“(p⇒ ⊥)⇒ b

”Modus Ponens 11,12

14.“

(p⇒ ⊥)⇒ b”⇒»[(p⇒ ⊥)⇒ (⊥ ⇒ q)]⇒ [(p⇒ F )⇒ (p⇒ (⊥ ⇒ q))]

–

15. [(p⇒ ⊥)⇒ (⊥ ⇒ q)]⇒ [(p⇒ F )⇒ (p⇒ (⊥ ⇒ q))] M.P. 13,1416. (p⇒ F )⇒ (p⇒ (⊥ ⇒ q)) M.P. 10,15.

7

8 CAPÍTULO 2. CÁLCULO PROPOSICIONAL

Consideremos ahora la proposición c =(p⇒ (⊥ ⇒ q)]⇒ ((p⇒ ⊥)⇒ (p⇒ q))

)que es una forma

del segundo axioma. Si escribimos c1 = (p ⇒ (⊥ ⇒ q)) y c2 = ((p ⇒ ⊥) ⇒ (p ⇒ q)), tenemosc = (c1 ⇒ c2). Entonces Entonces:

17. c Ax.18. c⇒ ((p⇒ ⊥)⇒ c) Ax.19. (p⇒ ⊥)⇒ c M.P. 17,1820. (p⇒ ⊥)⇒ (c1 ⇒ c2) pues c = (c1 ⇒ c2)21.

“(p⇒ ⊥)⇒ c1

”⇒“

(p⇒ ⊥)⇒ c2”

Por 20 y Ax. II

22. (p⇒ ⊥)⇒ c2 M.P. 21,1623. (p⇒ ⊥)⇒ ((p⇒ ⊥)⇒ (p⇒ q)) Sust. c224.

“(p⇒ ⊥)⇒ (p⇒ ⊥)

”⇒“

(p⇒ ⊥)⇒ (p⇒ q)”

Por 23 y Ax.II

25. (p⇒ ⊥)⇒ (p⇒ ⊥) Visto en clase26 (p⇒ ⊥)⇒ (p⇒ q) c.q.d.

En clase se ha demostrado p⇒ p pero por si hay alguna duda lo repetimos aqúı:

1. p⇒“

(p⇒ p)⇒ p”

Ax

2. [p⇒ (p⇒ p)]⇒ (p⇒ p) Por 1 y Ax.II3. p⇒ (p⇒ p) Ax4. p⇒ p M.P. 2,3.

Problema 12 Úsese el teorema de deducción para demostrar que el rećıproco del axioma (c), esdecir, (p⇒ ¬¬p), es un teorema del cálculo de proposiciones.

Sol. Hagamos primero una demostración directa:

1. p⇒ [(p⇒ ⊥)⇒ p]2. (p⇒ ⊥)⇒ (p⇒ ⊥)3. ((p⇒ ⊥)⇒ p)⇒ ((p⇒ ⊥)⇒ ⊥)

si hacemos a = ((p⇒ ⊥)⇒ p)⇒ ((p⇒ ⊥)⇒ ⊥), entonces

4. a⇒ (p⇒ a)5. p⇒ a6. [p⇒ ((p⇒ ⊥)⇒ p)]⇒ [p⇒ ((p⇒ ⊥)⇒ ⊥)]7. p⇒ ((p⇒ ⊥)⇒ ⊥)8. p⇒ ¬¬p

.

Ahora, usando el Teorema de Deducción la cosa es más sencilla. Según el mencionado teorema` p ⇒ ¬¬p es equivalente a {p} ` ¬¬p, o lo que es lo mismo {p} `

((p ⇒ ⊥) ⇒ ⊥

). De nuevo

aplicado el teorema, esto será equivalente a {p, p⇒ ⊥} ` ⊥. Ahora bien, una demostración formalde esto último es:

1. p Premisa2. p⇒ ⊥ Premisa3. ⊥ Modus Ponens 1,2.

Problema 13 Pruébese que (p ∧ q) = ((p⇒ (q ⇒ ⊥)⇒ ⊥) y escŕıbase una deducción de (p ∧ q)a partir de las premisas {p, q}. Indicación: será necesario recurrir repetidas veces al mecanismode la demostración del teorema 2.4.

Sol. Se define p ∨ q := ¬p⇒ q y p ∧ q := ¬(¬p ∨ ¬q). Entonces

p ∧ q = ¬(p⇒ ¬q) = (p⇒ (q ⇒ ⊥))⇒ ⊥.

9

Vemos entonces que {p, q} ` (p⇒ (q ⇒ ⊥))⇒ ⊥.

1. p⇒“x⇒ p

”para todo x

2. p Premisa3. x⇒ p Para todo x4.

“p⇒ (q ⇒ ⊥)

”⇒ p Caso particular

5. [(p⇒ (q ⇒ ⊥))⇒ (p⇒ (q ⇒ ⊥))]⇒[(p⇒ (q ⇒ ⊥))⇒ p]⇒ [(p⇒ (q ⇒ ⊥))⇒ (q ⇒ ⊥)] Ax

6. (p⇒ (q ⇒ ⊥))⇒ (q ⇒ ⊥) M.P.7. (p⇒ (q ⇒ ⊥))⇒ (p⇒ (q ⇒ ⊥)) x⇒ x8. [(p⇒ (q ⇒ ⊥))⇒ p]⇒ [(p⇒ (q ⇒ ⊥))⇒ (q ⇒ ⊥)]9. (p⇒ (q ⇒ ⊥))⇒ (q ⇒ ⊥)10. premisa⇒

“(p⇒ (q ⇒ ⊥))⇒ premisa

”Ax

11. (p⇒ (q ⇒ ⊥))⇒ premisa12. (p⇒ (q ⇒ ⊥))⇒ q Caso particular13. [(p⇒ (q ⇒ ⊥))⇒ (q ⇒ ⊥)]⇒

[(p⇒ (q ⇒ ⊥))⇒ q]⇒ [(p⇒ (q ⇒ ⊥))⇒ ⊥] Ax14. [(p⇒ (q ⇒ ⊥))⇒ q]⇒ [(p⇒ (q ⇒ ⊥))⇒ ⊥] M.P. 9,1315. (p⇒ (q ⇒ ⊥))⇒ ⊥] M.P. 12, 14

Problema 14 Sea T el conjunto de las proposiciones compuestas de un conjunto de proposicionesprimitivas P .

i) Si {Ci}i∈I es una familia de subconjuntos consistentes de T totalmente ordenada por la in-clusión, pruébese que

⋃i∈I Ci es un conjunto consistente.

ii) Recurriendo al lema de Zorn, dedúzcase que cada subconjunto consistente S de T está contenidoen un subconjunto consistente maximal.

iii) Demuéstrese el lema 2.5 sin utilizar el lema de Zorn y cuando el conjunto de primitivas P esnumerable.

Sol. Recordemos que un conjunto de proposiciones S no es consistente cuando S ` ⊥. SeaC = ∪iCi, si C no fuera consistente entonces C ` ⊥ pero aplicando el Teorema de complitud setendŕıa C � ⊥ y por el Teorema de compacidad existe un subconjunto finito C ′ de C tal que C ′ � ⊥.Aplicando de nuevo el Teorema de complitud se tendŕıa C ′ ` ⊥. Pero C ′ ⊂ C = ∪iCi y siendo C ′finito y la familia {Ci}i totalmente ordenada, debe existir un i ∈ I tal que C ′ ⊂ Ci. Ahora bienC ′ ` ⊥ implica que Ci ` ⊥ lo que contradice la suposición de que todos los Ci son consistentes.Veamos ahora que casa subconjunto consistente de T está contenido en uno consistente maximal.Sea F el conjunto formado por todos los conjuntos consistentes que contienen a uno dado S.Aplicando el Lema de Zorn bastará demostrar que F , ordenado por inclusión, es un conjuntoinductivo (lo cual por definición quiere decir que toda cadena de F posee una mayorante en F).Pero esto es precisamente lo que se ha demostrado en el apartado anterior. Por lo tanto F esinductivo y esto fuerza la existencia de un elemento maximal en F . Por últimos demostremosel Lema 2.5 sin para el caso en que el conjunto P de primitivas es numerable. Partimos de unconjunto de proposiciones S tal que S � ⊥ y queremos ver que S ` ⊥. Supongamos que S esconsistente, entonces tenemos que demostrar que existe una valoración v de P tal que v̄(t) = 1para todo t ∈ S. Al igual que en la demostración ya vista del lema, se tiene que para cada to bien S ∪ {t} es consistente o bien lo es S ∪ {¬t}. Por lo tanto enumeramos las proposicionescompuestas que se puedan construir a partir de P (la numerabilidad de P implica la del conjuntode todas las proposiciones compuestas construibles a partir de P ). Supongamos por lo tanto quelas proposiciones compuestas construibles a partir de P son t1, . . . , ti, . . .. Ampliemos entonces elconjunto S de la forma siguiente: si S∪{t1} en consistente entonces S1 := S∪{t1} en caso contrarioS1 := S ∪ {¬t1}. Ahora inductivamente definimos si Si−1 ∪ {ti} es consistente, Si := Si−1 ∪ {ti}y en caso contrario Si := Si−1 ∪ {¬ti}. Finalmente S′ = ∪iSi es consistente (igual que en lademostración del lema). Construimos entonces v̄ : T → {0, 1} tal que v̄ es identicamente 1 sobre

10 CAPÍTULO 2. CÁLCULO PROPOSICIONAL

S′ y 0 fuera de S′. Se demuestra que v̄ es un {⊥,⇒}-homomorfismo de la misma forma que en lademostración del lema.

Problema 15 Sea T un conjunto de proposiciones compuestas en un conjunto de proposicionesprimitivas P . Para cada t ∈ T se define

U(t) = {v ∈ V : v̄(t) = 1},

donde V es el conjunto de todas las valoraciones de P en 2.

i) Demuéstrese que {U(t)}t∈T es base de una topoloǵıa en V , o, con mayor concreción, quepara cualesquiera t1, t2 ∈ T se tiene

U(t1) ∩ U(t2) = U(t1 ∧ t2).

ii) Si S ⊂ T , pruébese que S |= ⊥ si y solo si {U(¬t)}t∈S es un recubrimiento abierto de V .

iii) Dedúzcase la equivalencia entre el teorema de compacidad y la afirmación de que elespacio V es compacto.

Sol. Para el primer apartado téngase en cuenta que para toda valoración v : P → {0, 1} setiene v̄(t1 ∧ t2) = v̄(t1)v̄(t2) para cualesquiera t1, t2 ∈ T . Entonces v ∈ U(t1) ∩ U(t2), si y sólo siv̄(t1) = v̄(t2) = 1 lo cual es equivalente a v̄(t1∧ t2) = 1, o lo que es lo mismo v ∈ U(t1∧ t2). Para elsegundo apartado supongamos primero que S � ⊥. Tenemos que demostrar que V ⊂ ∪t∈SU(¬t).Sea pues v ∈ V , es decir una aplicación v : P → {0, 1}. Como S � ⊥, debe existir algun t ∈ S talque v̄(t) = 0. Entonces v̄(¬t) = 1 y por lo tanto v ∈ U(¬t). Rećıprocamente si V ⊂ ∪t∈SU(¬t)toda aplicación P → {0, 1} está en algún U(¬t) con t ∈ S, pero esto quiere decir que la valoraciónse anula en t. Para el tercer apartado hay que notar primero, que un espacio topológico con unabase B, es compacto si y sólo si para cualquier recubrimiento del espacio por abierto de B, existeun subrecubrimiento finito. Veamos entonces la equivalencia de las siguientes afirmaciones:

1. Si S � t existe un subconjunto finito S ′ ⊂ S tal que S′ � t (T. de compacidad).

2. V es compacto.

1⇒2. Si V ⊂ ∪i∈IU(ti) para un cierto conjunto de ı́ndices I tal que ti ∈ T , entonces definamosS := {¬ti : i ∈ I}. Se comprueba que S � ⊥ ya que toda valoración v pertence a algún U(ti) ypor lo tanto se anula sobre el elemento ti ∈ S . Aplicando 1. se tiene la existencia de S ′ ⊂ S conS′ finito tal que S′ � ⊥. Si S′ = {¬ti1 , . . . ,¬tik}, entonces aplicando lo demostrado en el segundoapartado se tiene que V ⊂ U(ti1) ∪ · · · ∪ U(tik ).2⇒ 1. Si S � t entonces V ⊂ ∪s∈SU(¬s) ∪ U(¬t) y aplicando la hipótesis de compacidad de V setiene V ⊂ U(¬t1) ∪ · · · ∪ U(¬tk) ∪ U(¬t) para cierto subconjunto finito S ′ := {t1, . . . , tk} de S.Por lo tanto S′ ∪ {¬t} � ⊥ y a partir de esto se tiene S ′ � (¬t⇒ ⊥) de donde S′ � t.

Problemas propuestosProblema 9 Compruébese que las proposiciones

p⇒ (q ⇒ p),

[p⇒ (q ⇒ r)]⇒ [(p⇒ q)⇒ (p⇒ r)], y

¬¬p⇒ p,son tautoloǵıas.

Problema 10 En el conjunto 2 = {0, 1} se definen las operaciones ¬a = 1−a, a∧ b := mı́n(a, b),a∨ b = máx(a, b) y a⇒ b := 0 si y sólo si a = 1 y b = 0. Escŕıbanse estas operaciones en términosde la multiplicación que dota a 2 de estructura de cuerpo (isomorfo al de los enteros módulo dos).

11

Problema 11 Demuestrese que {p,¬q ⇒ ¬p} � q para cualesquiera proposiciones p y q.

Problema 12 Sea P (X) el álgebra de las proposiciones construidad sobre el conjunto de variablesX. Para cada subconjunto A ⊂ P (X) definamos

Con(A) := {p ∈ P (X):A � p}.

Demuéstrese que:

1. A ⊂ Con(A) para todo A.

2. A1 ⊂ A2 ⇒ Con(A1) ⊂ Con(A2) para cualesquiera A1 y A2.

3. Con(Con(A)) = Con(A), para todo A.

Problema 13 Encuéntrese una demostración de p⇒ r a partir del conjunto de premisas

{p⇒ q, q ⇒ r}.

Problema 14 Sea P (X) el álgebra de proposiciones sobre el conjunto de variables X. Conside-remos la inclusión canónica iX : X → P (X). Demuéstrese que si φ : X → Y es una aplicación,entonces existe un único homomorfismo de álgebras φ̄:P (X) → P (Y ) que hace conmutativo eldiagrama

X P (X)//

P (Y )""E

EEEE

EEEE

EEEE

E

��

iX

φ̄iY φ

Sea A ⊂ P (X) y ω ∈ P (X). Demuéstrese que

1. A ` ω implica φ(A) ` φ(ω).

2. A � ω implica φ(A) � φ(ω).

Problema 15 Definamos para cada A ⊂ P (X) (notaciones como en el problema anterior). SeaA el conjunto de axiomas del cálculo proposicional, es decir, el conjunto de todas las proposicionesque aparecen en el Problema 9. Definamos Ded(A) := {p ∈ P (X):A ` p}. Demuéstrese que Ded(A)es el menor subconjunto D de P (X) tal que D ⊃ A ∪ A y tal que si p y p ⇒ q son elementos deD, entonces también q ∈ D.

12 CAPÍTULO 2. CÁLCULO PROPOSICIONAL

Caṕıtulo 3

Teoŕıas de primer orden

En este caṕıtulo usaremos eventualmente la notación fn para denotar una operación fn ∈ Ω dearidad n en un tipo operacional Ω de un lenguaje de primer orden L = (Ω,Π). También usaremosla notación Am para denotar un predicado Am ∈ Π de aridad m.

Problema 16 ¿Cuáles de las siguientes son fórmulas de un lenguaje L = (Ω,Π) de primer orden?

1. A2(f1(x), x), A2 ∈ Π, f1 ∈ Ω.

2. f3(x, y, z), f3 ∈ Ω.

3. A1(x2)⇒ A1(x1, x2), A1 ∈ Π.

4. (¬∀x2)A2(x1, x2), A2 ∈ Π.

5. ((∀x2)A1(x1))⇒ ¬A1(x2), A1 ∈ Π.

6. A3(f3(x, y, z)), f3 ∈ Ω, A3 ∈ Π.

7. ¬A1(x1)⇒ A1(x2), A1 ∈ Π.

8. (∀x1)A3(a1, a2, f1(a3)), A3 ∈ Π, f1 ∈ Ω.

Sol. No son fórmulas la tercera ni la sexta por un problema de incompatibilidad de aridades.

Problema 17 Sea L el lenguaje de primer orden con Ω = (f 2, a1) donde f2 es de aridad dos, a1es una constante y Π = {A2} donde el predicado A2 es de aridad dos. Consideremos la fórmula

A = (∀x1)(∀x2)[A2(f2(x1, x2), a1)⇒ A2(x1, x2)].

Sea I la interpretación I = Z con f 2I (n,m) := n −m, (a1)I = 0, A2I (n,m) := (n < m). ¿Es AIverdadera?. Búsquese una interpretación J tal que AJ resulte ser falsa.

Sol. La interpretación de A en I es el subconjunto [A]I(2) formado por las parejas (n,m) ∈ Z×Ztales que n−m < 0 implique n < m. Obviamente [A]I (2) = Z×Z por lo que la A es verdadera enla interpretación I . Una interpretación en la que A resulte ser falsa puede ser por ejemplo J = Zcon (a1)J = 0, A

2J (n,m) := (n < m) y f

2(n,m) = nm.

Problema 18 ¿Existe una interpretación para un lenguaje de primer orden L tal que la siguientefórmula

(∀x1)(A1(x1)⇒ A1(f1(x1))

),

se interprete comno un enunciado falso?

13

14 CAPÍTULO 3. TEORÍAS DE PRIMER ORDEN

Sol. Por ejemplo I = Z con A1I(n) := (n < 0) y f1I (n) := n2 para cada entero n.

Problema 19 Sea p una fórmula con V L(p) = {x}. Calcular el enunciado de [(∀x)p]A(∅) encualquier interpretación A. Calcular también la interpretación de (∃x)p.

Sol. Hay que tener en cuenta que para todo conjunto S se tiene S0 := {∅}. Por otra parte cuandop es una fórmula con V L(p) = {x1, . . . , xn+1} entonces ((∀x)p)A : An → {0, 1} siendo

((∀x)p)A(a1, . . . , an) :={

1 si para todo an+1 ∈ A se tiene pA(a1, . . . , an+1) = 1,0 en caso contrario.

En el caso n = 0 se tiene entonces ((∀x)p)A : {∅} → {0, 1} tal que

((∀x)p)A(∅) :={

1 si para todo a1 ∈ A se tiene pA(a1) = 1,0 en caso contrario.

Por lo tanto [(∀x)p]A(∅) = 1 si para cada a1 ∈ A se tiene pA(a1) = 1 y [(∀x)p]A(∅) = 0 en casocontrario. Siguiendo razonamientos similares se llega a que [(∃x)p]A(∅) = 1 si existe algún a1 ∈ Atal que pA(a1) = 1. En caso contrario [(∃x)p]A(∅) = 1.

Problema 20 Uno de los axiomas del cálculo de predicados establece que (∀x, y)[(x = y)⇒ (p⇒p[y/x])] siempre que x ∈ V L(p) e y no esté ligada en p. Sea p una fórmula de un lenguaje deprimer orden L, con una única variable x que es libre en p. Demostrar que para dos términoscualesquiera t1 y t2 se tiene

` (t1 = t2)⇒[p(t1/x)⇒ p(t2/x)

]

Sol. Sea q = (∀y)((x = y) ⇒ (p ⇒ p(y/x))) de tal modo que (∀x)q es un axioma del cálculode predicados (en las condiciones estipuladas arriba). Otro axioma establece que ((∀x)p ⇒ p(t/x)siempre que x ∈ V L(p) y las variables del término t no aparezcan ligadas en p. Por lo tanto a partirde (∀x)q podemos deducir q(t/x) siempre que las variables de t sean distintas de y. Aśı hemosdemostrado que (∀y)

((t = y) ⇒ (p(t/x) ⇒ p(y/x))

)siempre que y no sea una variable de t. Si

ahora s es otro término se tendrá (t = s)⇒ (p(t/x) ⇒ p(y/x)(s/y) y como p(y/x)(s/y) = p(s/x)tenemos lo que se requeŕıa.

Problema 21 Descŕıbase la teoŕıa de primer orden T de los grupos abelianos totalmente orde-nados(es decir grupos abelianos con una relación de orden total compatible con la operación delgrupo).

Sol. Empezaremos por definir el lenguaje L = (Ω,Π). El tipo operacional Ω deberá ser Ω ={+,−, 0} donde + es de aridad dos, − de aridad uno y 0 de aridad cero. Para la operación binaria+ utilizaremos notación infija. Por otra parte Π = {R} donde R es de aridad dos y usaremostambién notación infija para R. Como axiomas de la teoŕıa tomaremos los siguientes:A1: (∀x, y)(x+ y = y + x)A2: (∀x, y, z)(x+ (y + z) = (x+ y) + z).A3: (∀x)(x + 0 = 0).A4: (∀x)(x + (−x) = 0).Hasta aqúı tenemos descrita la teoŕıa de primer orden de grupos abelianos. Para cubrir nuestroobjetivo debemos seguir axiomatizando:A5: (∀x)(xRx).A6: (∀x, y)

((xRy ∧ yRx)⇒ (x = y)

).

A7: (∀x, y, z)((xRy) ∧ (yRz)⇒ xRz

).

A8: (∀x, y)((xRy) ∨ (yRx)

).

Por último axiomatizamos la compatibilidad de R con la operación +:A9: (∀x, y, z)

(xRy ⇒ (x + z)R(y + z)

).

15

Problema 22 En la teoŕıa de primer orden T descrita en el problema anterior, se consideran lafórmulas P =

(¬(x = 0) ∧ 0Rx

)y N =

(¬(x = 0) ∧ xR0

). Demuéstrese que

(1) T ` (∀x)(x = 0 ∨ P ∨N

),

(2) T ` (∀x)(0Rx⇒ −xR0).

Sol. Para el primer apartado podemos demostrar que T ` (x = 0) ∨ P ∨ N y después aplicargeneralización. Para demostrar esto aplicamos el axioma ((∀x)p ⇒ p[t/x] del cálculo de predicadosa A8 definiendo p = (∀y)(xRy ∨ yRx) y t = x. Observemos que x no aparece ligada en p por loque podemos deducir p[x/x] = (∀y)(xRy∨yRx). Ahora podemos repetir el argument para obtenerxR0∨ 0Rx. Abreviemos S := (xR0∨ 0Rx) y entonces tenemos S ⇒

((x 6= 0)⇒ S

)y como hemos

demostrado S podemos concluir (x 6= 0) ⇒ (xR0 ∨ 0Rx). Ahora podemos utilizar el siguienteresultado de cálculo proposicional

`(p⇒ (a ∨ b)

)⇒[p⇒ (a ∧ p) ∨ (b ∧ p)

]

que dejamos como ejercicio al lector, para concluir que (x 6= 0)⇒[(xR0 ∧x 6= 0)∨(0Rx ∧x 6= 0)

].

Aśı hemos demostrado (x 6= 0) ⇒ P ∨ N o lo que es lo mismo (x = 0) ∨ P ∨ N , y aplicandogeneralización (∀x)(x = 0 ∨ P ∨N) como pretend́ıamos.Para el segundo apartado usaremos de nuevo el axioma (∀x)p ⇒ p(t/x) (cuando las variablesde t no estén ligadas en p). Aplicando dicho axioma a A9 (véase problema anterior) se tiene0Ry ⇒ −yR(y + (−y)) pero por A4 y + (−y) = 0 y aplicando lo establecido en el Problema 20se tendrá 0Ry ⇒ −yR0. Usando ahora generalización tendremos (∀y)(0Ry ⇒ −yR0) y ahorapodemos hacer un cambio de variable para obtener (∀x)(0Rx⇒ −xR0).

Problema 23 Se dirá que dos teoŕıas de primer orden son equivalentes cuando tienen los mismosmodelos. Consideremos el lenguaje L′ = (Ω′,Π′) tal que Ω′ = (+,−, 0) como en el problemaanterior, y Π′ = {P} donde P tiene aridad uno. Consideramos entonces la teoŕıa T ′ de primerorden cuyo conjunto de axiomas es: A1, A2, A3, A4 yA5’: (∀x, y)

(P (x) ∧ P (y)⇒ P (x+ y)

).

A6’: (∀x)((x = 0)⇒ ¬P (x)

).

A7’: (∀x)((x = 0) ∨ P (x) ∨ P (−x)

).

Demuéstrese que para todo modelo A de la teoŕıa T de grupos abelianos totalmente ordenados(véase Problema 21), A es también un T ′-modelo definiendo PA(x) := [(0RAx)∧ x 6= 0] para cadax ∈ A. Rećıprocamente, si A es un T ′-modelo, demuéstrese que A es un T -modelo defininiendopara cualesquiera x, y ∈ A la relación xRAy si y sólo si x = y o PA(y − x).

Sol. Sea A un modelo de la teoŕıa de primer orden de grupos abelianos totalmente ordenados.Si la relación de orden RA la denotamos por ≤, Definamos PA como la relación unaria PA(x) =[(0 ≤ x) ∧ x 6= 0], es decir, PA(x) = 1 si y solo si 0 ≤ x y x 6= 0. Vamos a usar la notación0 < x o equivalentemente x > 0 para denotar que PA(x) = 1. Entonces tenemos que demostrarque la interpretación de A1-A4 y A5’-A7’ en A proporciona enunciados verdaderos. Como A esun grupo abeliano, los axiomas A1-A4 dan automáticamente enunciados verdaderos en A. Ahora,la interpretación de A5’ en el modelo A es: ∀x, y ∈ A, x, y > 0 implica x+ y > 0. Para demostraresto tengamos en cuenta que como 0 ≤ x entonces y ≤ x + y por la propiedad de compatibilidadde la relación con la operación del grupo. Como además 0 ≤ y la transitividad implica 0 ≤ x+ y.Si tuviéramos x+ y = 0 entonces x = −y y como 0 ≤ x entonces 0 ≤ −y lo que implica y ≤ 0 enun grupo abeliano ordenado (véase el Problema 22). Pero entonces 0 ≤ y ≤ 0 implica y = 0 encontra de la hipótesis y > 0. Vayamos ahora con la interpretación de A6’. Tenemos que demostrarque si x ∈ A es nulo, entonces no se tiene x > 0. Esto es evidente dada la interpretación de <en nuestro modelo. En cuanto a A7’, habŕıa que demostrar que para cada x ∈ A se tiene x = 0o x > 0 o 0 < x. Como A es totalmente ordenado se tiene 0 ≤ x o x ≤ 0 pero si x no es nuloentonces o x > 0 o x < 0. La última parte del problema nos pide demostrar que si A es unT ′-modelo, entonces definiendo xRAy por x = y o PA(y − x) = 1, tenemos una relación de ordentotal RA compatible con la operación binaria del grupo. La relación RA es obviamente reflexiva.Para ver que es antisimétrica supongamos xRAy, yRAx. Entonces si x 6= y tenemos PA(x−y) = 1

16 CAPÍTULO 3. TEORÍAS DE PRIMER ORDEN

y PA(y − x) = 1. Por el axioma A5’ se tiene entonces PA(0) = 1 cosa imposible por el A5’. Deforma análoga se demuestra la transitividad de RA. Para acabar, tenemos que demostrar que sixRAy entonces para cada z (x+z)RA(y+z). Ahora bien, esto es trivial si x = y. En caso contrarioPA(y − x) = 1 lo que trivialmente implica PA((y + z) − (x + z)) = 1, es decir (x + z)RA(y + z)como queŕıamos ver.

Problema 24 Sea L un lenguaje de primer orden que contiene un predicado binario φr para cadareal positivo r. En L se define la teoŕıa T por medio de los axiomas:

(∀x, y)(φ0(x, y) ⇔ (x = y)),(∀x, y)(φr(x, y) ⇒ φs(y, x)), para cada par de reales positivos (r, s) con r ≤ s.(∀x, y, z)((φr(x, y) ∧ φs(y, z)) ⇒ φr+s(x, z)), para cada r, s ∈ R+.Demuéstrese que cada espacio métrico (X, d) constituye un T–modelo si se interpreta φr(a, b)

como d(a, b) ≤ r. ¿Cada T–modelo proviene de un espacio métrico en el sentido anterior?Sol. Que cada espacio métrico es un modelo de la teoŕıa es fácil de demostrar. El primer axioma deT se cumple en la interpretación gracias a que en un espacio métrico (E, d) se cumple d(a, b) = 0⇔a = b. El segundo axioma es consecuecia de que d(a, b) = d(b, a) para cualesquiera elementos a, b ∈E. Análogamente la desigualdad triangular de los espacios métricos implica que el tercer axiomaproporcionará un enunciado verdadero en la interpretación. Por último, no cada T -modelo provienede un espacio métrico en el sentido anterior. Sea X un conjunto con al menos dos elementos. Paracada real positivo r interpretemos φr(x, y) como x = y. Obtenemos aśı un T -modelo. Si estemodelo proviniera de un espacio métrico queŕıa decir que existe una métrica en X tal que paratodos x, y ∈ X se tiene d(x, y) ≤ r ⇔ x = y. Ahora bien si existen x, y ∈ X con x 6= y entonces0 < r = d(x, y) por lo que x = y lo cual es un absurdo.

Problema 25 Sea A una interpretación de un lenguaje de primer orden L. Demuéstrese que siA |= p, entonces A |= p̄ donde p̄ denota la clausura universal de la fórmula p.

Sol. Bastará demostrar que si x es una variable libre de p, entonces A |= (∀x)p. Con este fin tenemosque demostrar que la interpretación de (∀x)p en A es un enunciado verdadero. Supongamos queV L(p) ⊂ {x, y1, . . . yn}. Entonces la interpretación de (∀x)p en A viene dada por la función((∀x)p)A : An → {0, 1} tal que ((∀x)p)A(a1, . . . , an) = 1 si y solo si pA(a, a1, . . . , an) = 1 paracada a ∈ A. Pero este es precisamente el caso, dado que A |= p.

Problema 26 Sea L un lenguaje de primer orden. Demuéstrese que si t es un término cuyasvariables no aparecen ligadas en la fórmula p, entonces la fórmula (∀x)p ⇒ p(t/x) es una tau-toloǵıa. Recuérdese que p(t/x) o p[t/x] denotan la fórmula que se obtiene sustituyendo todas lasocurrencias de la variable x por el término t.

Sol. Sea A una interpretación de L y supongamos V L(p) ⊂ {x, y1, . . . , yn} siendo t = ωy1 · · · ykcon k ≤ n. Tenemos que demostrar que en caso de ser ((∀x)p)A(a1, . . . , an) = 1 entonces tambiénp(t/x)A(a1, . . . , an) = 1. Pero el hecho de ser ((∀x)p)A(a1, . . . , an) = 1 quiere decir que para cadaa ∈ A se tiene pA(a, a1, . . . , an) = 1. En consequencia:

p(t/x)A(a1, . . . , an) = p(tA(a1, . . . , ak), a1, . . . , an) = 1.

Problema 27 Sea L = (Ω,Π) un lenguaje de primer orden y A y B dos L-estructuras. Se dirá en-tonces que una aplicación f : A → B es un homomorfismo de L-estructuras cuando para cadaω ∈ Ω de aridad n, y para cada R ∈ Π de aridad m, los siguientes diagramas son conmutativos:

An A//

Bn��

B//��

ωA

ωB

ffn

An {0, 1}//

Bn��

;;wwwwwwwwwwww

RA

RB

fn

17

donde fn:An → Bn es la aplicación tal que fn(a1, . . . , an) = (f(a1), . . . , f(an)) para cada n-upla(a1, . . . , an) ∈ An. Def́ınase el concepto de L-subestructura usando la aplicación de inclusión.Demuéstrese que si B es una L-subestructura de A, entonces para cada término t cuyas variables(libres) están contenidas en el conjunto de variables {x1, . . . , xn} se tiene para cada (b1, . . . , bn) ∈Bn que tB(b1, . . . , bn) = tA(b1, . . . , bn).

Sol. La noción de L-subestructura puede enunciarse aśı: dadas dos L-estructuras A y B conB ⊂ A, diremos que B es una L-subestructura de A cuando la inclusión es un homomorfismode L-estructuras. Respecto a la segunda parte del problema, el asunto es trivial para términosdel tipo t = ωx1 · · ·xn donde las xi son variables. Para términos más generales t = ωt1 · · · tkpodemos suponer que la propiedad es cierta para cada término ti y que las variables de cada tiestán contenidas en {x1, . . . , xn}. Entonces para cada (b1, . . . , bn) ∈ Bn se tiene

tB(b1, . . . , bn) = ωB((t1)B(b1, . . . bn), . . . , (tn)B(b1, . . . , bn))= ωA((t1)A(b1, . . . bn), . . . , (tn)A(b1, . . . , bn))= tA(b1, . . . , bn).

Problemas propuestosProblema 16 Sean s y t términos de un lenguaje de primer orden L tal que las variables deambos están contenidas en el conjunto de variables {x1, . . . , xn}. Supongamos que A es una L-subestructura de B siendo i:A → B la inclusión. Demuéstrese la conmutatividad del diagrama:

An {0, 1}//

Bn��

;;wwwwwwwwwwww

(s=t)A

(s=t)B

in

Problema 17 Sea L = (Ω,Π) un lenguaje de primer orden y sea φ ∈ Π de aridad n y t1, . . . , tntérminos tales que V L(ti) ⊂ {x1, . . . , xm}. Supongamos que A es una L-subestructura de B siendoi:A→ B la inclusión. Demuéstrese la conmutatividad de los diagramas

Am {0, 1}//

Bm��

99sssssssssssss

φ(t1,...,tn)A

φ(t1,...,tn)B

im

A0 {0, 1}//

B0 A

AAAA

AAAA OO

i0 ⊥B

⊥A

Problema 18 Sea L un lenguaje de primer orden y p, q fórmulas del mismo tales que V L(p) ∪V L(q) ⊂ {x1, . . . , xn}. Si A es una L-subestructura de B, demuéstrese la conmutatividad del dia-grama An {0, 1}//

Bn��

;;wwwwwwwwwwww

(p⇒q)A

(p⇒q)Bin

Problema 19 Formúlense conjuntos de axiomas en convenientes lenguajes de primer orden (es-pecif́ıquense estos) para cada una de las siguientes teoŕıas:

i) La teoŕıa de los dominios de integridad.

ii) La teoŕıa de los cuerpos algebraicamente cerrados de caracteŕıstica 0.

iii) La teoŕıa de los conjuntos parcialmente ordenados.

iv) La teoŕıa de los conjuntos parcialmente ordenados con elemento máximo y elemento mı́nimo.

18 CAPÍTULO 3. TEORÍAS DE PRIMER ORDEN

v) La teoŕıa de los cuerpos ordenados.

vi) La teoŕıa de los cuerpos ordenados completos.

vii) La teoŕıa de los grupos de orden 168.

viii) La teoŕıa de los grupos simples de orden 168.

ix) La teoŕıa de los planos afines (rudimentarios).

Problema 20 Sea L un lenguaje de primer orden que contiene un predicado binario φr para cadareal positivo r. El L se define la teoŕıa T por medio de los axiomas:

(∀x, y)(φ0(x, y) ⇔ (x = y)),(∀x, y)(φr(x, y) ⇒ φs(y, x)), para cada par de reales positivos (r, s) con r ≤ s.(∀x, y, z)((φr(x, y) ∧ φs(y, z)) ⇒ φr+s(x, z)), para cada r, s ∈ R+.Demuéstrese que cada espacio métrico (X, d) constituye un T–modelo si se interpreta φr(a, b)

como d(a, b) ≤ r. ¿Cada T–modelo proviene de un espacio métrico en el sentido anterior?Problema 21 a) Def́ınase la noción de subestructura de una L–estructura.

b) Demuéstrese que si B es una subestructura de una L–estructura A y p es una fórmula dellenguaje sin cuantificadores en n variables libres, entonces

[p]B = [p]A ∩ Bn.Indicación: si no se resuelve esto con facilidad, es porque uno se ha complicado la vida en elapartado (a).

c) Considerando el centro de un grupo, o el de un álgebra, o de cualquier otra manera, pruébeseque la conclusión de (b) puede fallar si p tiene cuantificadores.

Problema 22 a) Por teoŕıa de primer orden universal se entiende a aquella cuyos axiomas cobranla forma (∀~x)p, con p una fórmula sin cuantificadores y ~x una cadena finita (tal vez vaćıa) denombres de variables separados por comas. Pruébese que las teoŕıas universales tienen la graciade que cada subestructura de un T–modelo es, aśı mismo, un T–modelo.

b) De una teoŕıa de primer orden T se dice que es inductiva si sus postulados respondenal esquema (∀~x)(∃~y)p, con p una fórmula libre de cuantificadores. Para una teoŕıa inductiva T ,supóngase que una estructura A del lenguaje se obtiene como unión de una cadena {Bi}i∈I desubestructuras. Demuéstrese que A es un T–modelo si cada Bi es un T–modelo.

c) ¿Cuáles de las teoŕıas del ejercicio 3.1 son universales?, ¿Cuáles inductivas?

Problema 23 a) Dado un lenguaje de primer orden L = (Ω,Π), denótese por L∗ = (∅,Π∗) ellenguaje obtenido de L mediante la supresión de los śımbolos de operación de Ω y el añadido deun śımbolo de predicado ω∗ por cada ω ∈ Ω, haciendo α(ω∗) = α(ω) + 1.

Si T es una teoŕıa de primer orden escrita en el lenguaje L, expĺıquese cómo construir unateoŕıa T ∗ en L∗ equivalente a T en el sentido de tener los mismos modelos.

b) Apĺıquese el método anterior a la teoŕıa de primer orden de los grupos y a la de los conjuntosordenados con elemento mı́nimo.

Problema 24 a) Demuéstrese que las sentencias (∀x, y)((x = y) ⇒ (y = x)) y(∀x, y, z)((x = y) ⇒ ((y = z) ⇒ (x = z))) son teoremas del cálculo de predicados con

igualdades.b) Compruébese que s ∼ t si y solo si S |= (s = t) define una relación de equivalencia en el

conjunto A de los términos constantes de una teoŕıa completa, consistente y con certificados S.

Problema 25 Demuéstrese que la teoŕıa de primer orden T cuyo único axioma consiste en

(∀x)¬(x = x)es consistente si y solo si el lenguaje L en que está escrita no tiene constantes. Bajo la suposiciónde que T es consisente y L no contenga predicados primitivos 0–arios, pruébese que T es completay posee certificados.

19

Problema 26 Sea T una teoŕıa de primer orden en un lenguaje numerable que solo tiene modelosinfinitos. Demuéstrese que T es completa si T es categórica en cardinal ℵ0.

Problema 27 De un conjunto se dice que es totalmente ordenado denso si hay definida en él unarelación binaria < tal que se dan las siguientes condiciones:

i) Para todo x, y se verifica una y solo una de las relaciones x < y, x = y o y < x.

ii) Si x < y, y < z, entonces x < z.

iii) Si x < y, existe un z tal que x < z, y z < y.

iv) Para cada x existen y, z con y < x y x < z.a) Descŕıbase la teoŕıa de primer orden T de los conjuntos totalmente ordenados densos.b) Demuéstrese que cualesquiera dos conjuntos totalmente ordenados densos de cardinal ℵ0

son isomorfos. Indicación: numérense los conjuntos y establézcase entre ellos de forma inductivauna aplicación que conserve el orden. La sobreyectividad se probará usando la propiedad de quetoda parte no vaćıa de N tiene un primer elemento.

c) Pruébese que T es consistente. Bastará con encontrar un modelo.d) ¿Es T completa? El ejercicio anterior puede proporcionar la respuesta.

Problema 28 Supóngase que una teoŕıa de primer orden T en un lenguaje (Ω,Π) tiene una teoŕıaalgebraica subyacente (Ω, E), esto es, la clausura universal de cada identidad primitiva (s = t) ∈ Ees un axioma de T .

Pruébese que la clausura universal de las identidades derivadas de Ẽ (teorema 1.4) son de-mostrables en la teoŕıa T .

Problema 29 Demuéstrese que las sentencias (∀x, y, z)(a x a y z = a a x y z) y (∀x, y)(a x y =a y x) son deducibles de la aritmética de Peano. Indicación: la conmutatividad requiere de mástrabajo que la asociatividad. Recúrrase a la conclusión del ejercicio anterior cada vez que hagafalta.

Problema 30 Sea T la teoŕıa de primer orden de los cuerpos ordenados completos (ejercicio3.1.vi)). Demuéstrese que cada T–modelo es un cuerpo cerrado real, esto es, un cuerpo ordenadoen el que cada elemento positivo tiene ráız cuadrada.

20 CAPÍTULO 3. TEORÍAS DE PRIMER ORDEN

Caṕıtulo 4

Funciones recursivas

En esta sección se utilizará reiteradamente el hecho de que si α:Nk → N, β:Nk+2 → N sonfunciones recursivas primitivas, entonces la función h:Nk+1 → N tal que

{h(n1, . . . , nk, 0) = α(n1, . . . , nk) yh(n1, . . . , nk, n+ 1) = β(n1, . . . , nk, n, h(n1, . . . , nk, n)

para cualesquiera n1, . . . , nk, n ∈ N, es primitiva recursiva.

Problema 28 Describir una máquina de registros que inicialize el registro Ri, es decir, que leasigne el valor 0.

Sol. Usaremos como es habitual la notación S1 para el estado inicial (o de comienzo) de la maquinay S0 para el estado de parada. Entonces la maquina se puede describir como en el diagrama deabajo.

S1

Ri−1��

S077

Problema 29 Demuéstrese que la función f :N→ N tal que f(0) = 1 y f(n) = 0 para cada n 6= 0es recursiva primitiva.

Sol. Apliquemos el resultado mencionado en el primer párrafo de este caṕıtulo. Tomemos α:N→ Ndada por α(n) = n + 1. Por otra parte sea β:N3 → N la proyección en la primera componente,es decir, β(n1, n2, n3) = n1. Entonces h:N2 → N satisface h(n, 0) = n + 1 y h(n,m + 1) =β(n,m, h(n,m)) = n y es recursiva primitiva. Definamos ahora la función f :N → N tal quef(n) := h(0, n) para cada n. Esta función es recursiva primitiva al ser composición de recursivasprimitivas. Se tiene además f(0) = h(0, 0) = 1 y f(n+ 1) = h(0, n+ 1) = β(0, n, h(0, n)) = 0.

Problema 30 Prefijemos a ∈ N y denotemos por σ:N → N la aplicación tal que σ(n) = n + 1.Demuéstrese que dada una función recursiva primitiva γ:N → N existe otra función recursivaprimitiva g:N→ N tal que g(0) = a y g(σ(n)) = γ(g(n)) para cada n > 0.

Sol. Apliquemos lo mencionado al principio del caṕıtulo tomando como α la función constante devalor a y β:N3 → N la función dada por β(x, y, z) = γ(z) que es recursiva primitiva. Entoncesla función h:N2 → N tal que h(n, 0) = a y h(n,m+ 1) = β(n,m, h(n,m)) es recursiva primitiva.Definamos g:N → N por g(n) := h(0, n). Claramente g es recursiva primitiva y además g(0) =h(0, 0) = a y

g(σ(n)) = h(0, σ(n)) = β(0, n, h(0, n)) = β(0, n, g(n)) = γ(g(n)).

21

22 CAPÍTULO 4. FUNCIONES RECURSIVAS

Problema 31 Demostrar que la función r:N → N tal que r(n) es el resto de dividir n entre doses recursiva primitiva.

Sol. Sabemos que la función γ:N→ N tal que γ(0) = 1 y γ(n) = 0 para n 6= 0 es recursiva primitiva(véase el problema 29). Entonces dada esta función, el problema 30 asegura la existencia de otrafunción recursiva primitiva g tal que g(0) = 0 y g(n+ 1) = γ(g(n)). Ahora bien g(1) = γ(g(0)) =γ(0) = 1. Veamos ahora inductivamente que si n es par g(n) = 0 mientras que si n es impar entoncesg(n) = 1. Lo hemos demostrado para n = 0 y n = 1. Supongámoslo demostrado para todos losnaturales menores que n. Entonces si n > 1 es par g(n) = g(σ(n − 1)) = γ(g(n− 1)) = γ(1) = 0mientras que si n es impar un razonamiento similar demuestra que g(n) = 1.

Problema 32 Un subconjunto M de un conjunto parcialmente ordenado D se dice que es dirigi-do si cada subconjunto finito de M tiene una cota superior (en M). Un conjunto parcialmenteordenado D se dice que es completo (abreviado cpo) si:

Cada subconjunto dirigido M tiene una mı́nima cota superior ∨M .

Hay un elemento mı́nimo ⊥ en D.

Demuéstrese que cada conjunto parcialemente ordenado finito con un elemento mı́nimo es un cpo.Sea N⊥ = N ∪ {⊥} y consideremos la relación definida por (1) ⊥ ≤ n para cada n ∈ N; y (2)n ≤ m⇔ n = m para n,m ∈ N. Demuéstrese que N⊥ es un cpo.

Sol. Si (D,≤) es un conjunto finito parcialmente ordenado con un elemento mı́nimo ⊥ entoncescada subconjunto dirigido M de D (necesariamente finito) es una cadena finita M = {m1, . . . ,mk}con m1 ≤ · · · ≤ mi ≤ mi+1 ≤ · · · ≤ mk. Por lo tanto mk es una mı́nima cota superior de M . Parala segunda parte el lector debe mostrar que los subconjuntos dirigidos M de N⊥ son de cardinaluno o dos. En el primer caso M = {⊥} o bien M = {n} con n ∈ N. En el segundo caso M = {⊥, n}para cierto n ∈ N.

Problema 33 Dados dos cpos D y E y una aplicación f :D → E, diremos que f es monótonacuando x ≤ y ⇒ f(x) ≤ f(y) para cualesquiera x, y ∈ D. Demuéstrese que la imagen por unafunción monótona de un conjunto dirigido es un conjunto dirigido. Diremos que f es continuacuando f(∨M) = ∨f(M) para cada subconjunto dirigido M de D. Diremos que f es estrictasi f(⊥) = ⊥. Dadas dos funciones f, g:D → E definimos en el conjunto D → E de todaslas funciones continuas de D en E la relación f ≤ g si y solo si f(x) ≤ g(x) para cada x.Demuéstrese que con esta relación el conjunto D → E es un cpo. Compruébese que el subconjuntode aplicaciones estrictas de D a E es también un cpo.

Sol. Si f es monotona y M dirigido, para demostrar que f(M) es un subconjunto dirigido de Etomemos un subconjunto finito X = {f(m1), . . . , f(mk)} de f(M). Entonces S = {m1, . . . ,mk}es un subconjunto finito de M por lo que existe algún m ∈ S tal que mi ≤ m para todo i. Peroentonces f(mi) ≤ f(m) lo que implica que f(m) ∈ f(M) es una cota superior de X . Veamosahora que D → E es un cpo. La relación definida en dicho conjunto se comprueba de inmediatoque es de orden parcial. Podemos definir la aplicación ⊥:D → E como la aplicación constantede valor ⊥. Entonces claramente ⊥ es un elemento mı́nimo de D → E. Veamos ahora que cadaconjunto dirigido M ⊂ D → E tiene un mı́nima cota superior. Fijemos d ∈ D y consideremos elconjunto M(d) := {m(d):m ∈ M}. Este subconjunto de E es dirigido como puede comprobarsede inmediato. Por lo tanto tiene sentido ∨M(d) = ∨m∈Mm(d). Definamos ahora la aplicaciónf :D → E tal que f(d) = ∨M(d). Tenemos entonces que para cualesquiera m ∈M , d ∈ D se da larelación m(d) ≤ f(d). Consecuentemente m ≤ f . Ahora se deja al lector la tarea de demostrar quef es continua con lo que f es un elemento de D → E que acota a M . Veamos que si otro elementog ∈ D → E es tal que m ≤ g para todo m ∈ M , entonces f ≤ g. En efecto: fijado d ∈ D se tieneque m(d) ≤ g(d) para cada m ∈M . Por lo tanto ∨M(d) ≤ g(d) o lo que es lo mismo f(d) ≤ g(d).Como esto ocurre para cualquier d ∈ D se tiene f ≤ g. También se deja como ejercicio al lectorcomprobar que el subconjunto de D → E de aplicaciones estrictas es un subcpo de D → E.

23

Problema 34 Sean D y E cpos. Demuéstrese que si f :D → E es monotona y D finito, entoncesf es continua.

Sol. Cada subconjunto dirigido finito es una cadena. Cualquier aplicación monótona transformael máximo de la cadena en el máximo de la cadena imagen.

Problema 35 Sea D un cpo y f :D → D continua. Demuéstrese que f tiene puntos fijos. Másaún, demuéstrese que existe un punto fijo mı́nimo.

Sol. Partiendo de que ⊥ ≤ f(⊥) y usando inducción se tiene que fn(⊥) ≤ fn+1(⊥). Definamosx0 := ∨nfn(⊥). Entonces f(x0) = f(∨nfn(⊥)) = ∨nfn+1(⊥) = ∨nfn(⊥) = x0 por lo tanto x0 esun punto fijo de f . Sea ahora otro punto fijo x ∈ D de f . Como ⊥ ≤ x se tiene fn(⊥) ≤ x luegox0 ≤ x. Aśı hemos demostrado que f tiene un mı́nimo punto fijo.

Problema 36 Demostrar que existe una única función estricta f : N⊥ → N⊥ que satisface:

f(n) =

{1 si n = 0n f(n-1) si n > 0

Sol. Sea D el cpo de todas las funciones estrictas del cpo N⊥ en si mismo. Por comodidad vamosa extender la multiplicación de N a una operación conmutativa N⊥ ×N⊥ → N⊥ que denotaremostambién por yuxtaposición, definiendo ⊥⊥ = ⊥ y ⊥n = n⊥ = ⊥ para cada natural n. Definamosla función F :D → D tal que para cada f ∈ D se tiene F (f) : N⊥ → N⊥ (estricta) dada porF (f)(0) = 1 y F (f)(n) = nf(n−1) para cada n > 0. Demostremos primero que F es monótona. Sif ≤ g entonces F (f)(0) = 1 = F (g)(0) y por otra parte, para n > 0 se tiene F (f)(n) = nf(n−1) ≤ng(n− 1) = F (g)(n). En consecuencia F (f) ≤ F (g). Sea ahora M ⊂ D un subconjunto dirigido.Entonces para cada m ∈ M se tiene m ≤ ∨M luego F (m) ≤ F (∨M) implicando ∨F (M) ≤F (∨M). La otra relación, F (∨M) ≤ ∨F (M) se deja como ejercicio al lector. Se tiene entonces queF es continua y aplicando lo demostrado en el ejercicio 35 existe un punto fijo para F que será laaplicación factorial. Conviene notar que la aplicación que acabamos de ver que existe f :N⊥ → N⊥se puede restringir a f :N→ N por su propia definición.

Problema 37 Fijada una función r:N→ N, demuéstrese que existe una única aplicación f :N→N tal que f(0) = 0 y f(n) = f(n− 1) + [1− r(n)] para n > 0.

Sol. Definamos D como el cpo de aplicaciones estrictas del cpo N⊥ en si mismo. Fijemos Conside-remos ahora F :D → D dada por F (f)(0) = 0 y F (f)(n) = f(n − 1) + [1 − r(n)] para n > 0.Tenemos que demostrar que F posee un punto fijo. En virtud de lo demostrado en el problema35, bastará demostrar que F es continua. Empezaremos viendo que es monótona. Si f, g ∈ D sontales que f ≤ g entonces F (f) ≤ F (g) ya que F (f)(0) = F (g)(0) = 0 y para n > 0

F (f)(n) = f(n− 1) + [1− r(n)] ≤ g(n− 1) + [1− r(n)] = F (g)(n).

El resto de la demostración de que F es continua es similar a la del problema 36. Se tiene entoncesla existencia de un punto fijo mı́nimo de F . Ahora falta demostrar que f es única pero esto tambiénse deja como ejercicio al lector.

Problema 38 En el problema anterior cuando r(n) = resto de dividor n entre dos, comprobarque la función f dada por las relaciones f(0) = 0 y f(n) = f(n− 1) + [1− r(n)] para n > 0, es lafunción parte entera de n/2, es decir, f(n) = E(n/2) siendo E(·) la función parte entera.

Sol. El lector puede comprobar que para cada natural n se tiene E(n/2) = E( n−12 ) + [1 − r(n)].Aplicando lo demostrado en el problema anterior tendremos que f(n) = E(n/2).

Problema 39 Demostrar que la función f(n) = E(n/2) es recursive primitiva.

24 CAPÍTULO 4. FUNCIONES RECURSIVAS

Sol. Definamos g:N3 → N como g(n,m, k) := k+[1−r(m+1)] que es recursiva primitiva. Fijemosα:N→ N recursiva primitiva cualquiera tal que α(0) = 0. Aplicando el resultado del principio delcaṕıtulo, la función h:N2 → N tal que h(n, 0) = α(n) y h(n,m+ 1) = g(n,m, h(n,m)) es recursivaprimitiva. Pero entonces la aplicación f :N → N tal que f(n) := h(0, n) es recursiva primitiva.Además f(0) = h(0, 0) = α(0) = 0 y para todo n se tiene

f(n+ 1) = h(0, n+ 1) = g(0, n, h(0, n)) = g(0, n, f(n)) = f(n) + [1− r(n+ 1)].

Aplicando entonces el problema 38 se tiene que f coincide con E(n/2).

Problemas propuestosProblema 31 Descŕıbase el funcionamiento del programa:

(1, -, 2, 4), (3, +, 3), (4, +, 1), (2 ,- ,5, 7), (5, +, 6), (6, +, 4),(3, -, 8, 9), (5, -, 7, 16), (5, -, 10, 18), (5, +, 11), (4, -, 12, 14),(7, +, 13), (3, +, 11), (7, -, 15, 17), (4, +, 14), (6, -, 17, 0), (2, +, 16),(4, -, 19, 20), (1, +, 18), (1, +, 16),con datos de entrada (n1, n2, 0, 0, . . .).

Problema 32 Escŕıbanse sendos programas para máquina de registros los cuales, dada la entrada(n, 0, 0, . . .), devuelvan los siguientes resultados:

(a) n2−5n+ 2 si este polinomio toma un valor no negativo. El programa debe no finalizar en otrocaso.

(b) El (n+ 1)–ésimo número primo pn.

Problema 33 Demuéstrese sucesivamente que las siguientes funciones son recursivas primitivas:

(a) f1(n) ={

1 si n = 0,0 en otro caso.

(b) f2(n) = resto de dividir n entre 2.

(c) f3(n) = parte entera de n/2.

(d) f4(n) ={n/2 si n es par0 en otro caso.

(e) f5(n,m) ={n/2m si este valor es un entero0 en otro caso.

(f) f6(n) = exponente de la mayor potencia de 2 que divide a n, si n > 0, y f6(0) = 0.Recuérdese que este ejercicio se dio por válido a fin de apoyar la demostración del teorema 4.2,

por lo que está prohibido recurrir a tal resultado para resolverlo.

Problema 34 Si E ⊂ N es un conjunto no vaćıo recursivamente enumerable, pruébese que existeuna función recursiva globalmente definida con E como rango de valores. Indicación: Es crucialla hipótesis de que E contenga al menos un elemento.

Problema 35 Demuéstrese que un subconjunto infinito E de N es recursivo si y solo si existeuna función recursiva f : N → N globalmente definida y estrictamente creciente que tiene a Ecomo conjunto de valores.

Problema 36 Pruébese que la inversa f−1 de una biyección f : N → N recursiva es tambiénrecursiva.

EJERCICIOS DEL CAPÍTULO V

Problema 37 Pruébese que la suma y el producto de números naturales de von-Neumann sonfunciones ZF–definibles en un modelo V de ZF.

Bibliograf́ıa

[1] P. T. Johnstone. Notes on logic and set theory. Cambridge Mathematical Textbooks. Cam-bridge University Press. 1987.

[2] E. H. Spanier. Algebraic Topology. McGraw Hill. 1966.

25