Guía 7 - Sistemas deductivos, completitud y compacidad para

lógica de primer orden

Solución de un alumno

Verano 2021

Ejercicio 1
Ejercicio 2
a. Sabemos que ∆ ` ϕ (pertenece al conjunto).
Si ϕ no es universalmente válida, entonces existe un modelo M tq M 6|= ϕ.
Entonces no es correcto con respecto a la clase de todos los modelos.
b. el conjunto de todos los modelos ` SQ1 . Pero ∆ 6` SQ1 . Entonces ∆ no es completo con respecto
al conj de todas las interpretaciones.
c.
• CORRECTO: Sabemos que ∆ ` ϕ (pertenece al conjunto).
Si ϕ es universalmente válida, entonces todo modelo M pasa que M |= ϕ. Entonces es correcto
con respecto a la clase de todos los modelos.
• COMPLETO: el conjunto de todos los modelos ` SQi . También ∆ ` SQi (porque pertenece).
Entonces ∆ es completo con respecto al conj de todas las interpretaciones.

Ejercicio 3
SQ8: ∀xyz(R(x, y) ∧ R(y, z) → R(x, z))
SQT = SQ ∪ {SQ8}
a. Si
C = {A : A es un modelo transitivo}
Sea
C 0 = {A : A |= SQT }
Basta con ver que:
C = C0
Para demostrar que SQT es correcto y completo con respecto a C.
(⊆) Si M es un modelo transitivo entonces M |= SQ8.
(⊇) Si M |= SQ8 implica que la relación binaria que tiene el modelo es transitiva.
Entonces estamos bajo el teorema de Godel, entonces SQT es correcto y completo con respecto a C.

b. Qvq para toda fórmula ϕ:

C = {todos los modelos}

1
 C |= ϕ ⇒ SQT ` ϕ

Vemos que:
C |= ϕ ⇒ SQ ` ϕ ⇒ SQ ∪ {SQ8} ` ϕ
(∗)

⇒ SQT ` ϕ
(*) vale porque SQ ∪ {SQ8} es consistente.

c. Ya visto en (a).

d. Qvq NO es cierto que para toda fórmula ϕ:

C = {todos los modelos}

SQT ` ϕ ⇒ C |= ϕ

Entonces buscamos ϕ tq:

SQT ` ϕ ∧ C 6|= ϕ
Sea el modelo M = (N, =), es decir la funcío binaria es la igualdad con interpretación estandar. Vemos
que si tomamos ϕ como SQ8:
SQT ` ϕ ∧ M 6|= ϕ ⇒ C 6|= ϕ

Ejercicio 4
Ejercicio 5
a. SQ8 es válido porque P ⊆ T .
SQ9 es válido porque P ⊆ T y T es transitiva.
SQ9 es válido porque T es la relación transitiva extendida de P .
b.
ϕ : ∀xy(T (x, y) → ∃z(P (x, z)))
La ϕ nos dice: “Si hay una relación transitiva entre x e y, entonces existe una relación entre x y z”
Tomamos el modelo:
Cumple SQ8, SQ9, SQ10 pero no cumple ϕ.
c. No es completa porque encontramos un modelo que en el que no vale ϕ, entonces no es posible
que SQ+ ` ϕ.

Ejercicio 6
Veamos que nos dicen los tres axiomas nuevos:
• ∀x(0 6= x + 1) Es decir, x aplicada con 1 nunca nos da 0.
• ∀xy(x + 1 = y + 1 → x = y) Es inyectiva (al aplicarle 1).
• ∀xy((x + y) + 1 = x + (y + 1)) Es asociativa (no tan fuerte enrealidad).

2
Figure 1: alt text

3
Tomamos el modelo M = (N, +, 0M , 1M ).
Donde 0M : 1 y 1M : 2. Este modelo cumple con los axiomas.
Sea la siguiente fórmula:
ϕ : ∀x(0 + x = x)

Sucede que:
C |= ϕ
M |= P
Pero
M 6|= ϕ ⇒ P 6` ϕ

Ejercicio 7
a.
ϕ2 : ∃xy(x 6= y)
ϕ3 : ∃xyz(x 6= y ∧ x 6= z ∧ y 6= z)
...
ϕn : ∃z1 ...zn (z1 6= z2 ∧ ... ∧ z1 6= zn ∧ z2 6= z3 ∧ ... ∧ zn−1 6= zn )
Γ = {ϕi : i ∈ N}
M |= Γ entonces M es infinito.
Nota: (×1 6= ×2 ) ≡ ¬(×1 = ×2 )

b. Asumimos que existe tal fórmula y la llamamos α. Sea Γ0 = Γ ∪ {α}.

• Veamos que es insatisfacible: Suponemos que es satisfacible, entonces existe un modelo y una
valuación tal que M, v |= Γ0 . Entonces M, v |= Γ entonces el dominio es infinito. Pero también
M, v |= α que significa que el dominio es finito. Absurdo. Entonces el conjunto Γ0 es insatisfacible.
• Veamos que es satisfacible: para cualquier subconjunto finito ∆ ⊆ Γ0 puede pasar que no contenga
ningún ϕi entonces simplemente tomando el modelo con un elemento en el dominio lo satisface. Si
por el otro lado contiene ϕi , tomamos k como el mayor i tq ϕ ∈ ∆. Entonces tomamos el modelo
que tiene k + 1 elementos en el dominio y este va a satisfacer a ∆. Entonces por compacidad,
como todo subconjunto es satisfacible entonces el conjunto Γ0 es satisfacible.
Absurdo, no puede ser satisfacible y no satisfacible. Entonces no es expresable la fórmula α.

Ejercicio 8
Suponemos que es expresable. Entonces:

ϕs (x, y) : pertenece a la clausura transitiva de la relación binaria RM

Definimos las siguiente fórmulas:

ϕ0 (x, y) : ¬∃z(R(x, z) ∧ R(z, y) → R(x, y))

...
ϕi (x, y) : ¬∃z1 z2 ...zi (R(x, z1 )∧

4
 R(z1 , z2 ) ∧ ... ∧ R(zn−1 , zn ) ∧ R(zn , y) → R(x, y))

Definimos:
Φ = {ϕi : i ∈ N}
Γ = Φ ∪ {ϕs }

Veamos que sea satisfacible:

M |= Φ ⇒ R no es transitiva
M |= ϕs ⇒ R es transitiva
Si M |= Γ, entonces R es transitiva y no es transitiva. Absurdo.
Veamos que es satisfacible:
Sea ∆ un conjunto finito tq ∆ ⊂ Γ, veamos que es satisfacible.
• ∆ = {ϕs } ó ∆ = ∅
• En otro caso: Tomamos k como el máximo i tq ϕi ∈ ∆. Entonces vamos a armar un modelo que
satisfaga ∆.
Tomamos el modelo M tq RM = {(1, 2), (2, 3), ..., (k, k + 1), (1, k + 1)}. Entonces M |= ∆.
Entonces es satisfacible. Absurdo. Entonces no existe una fórmula para para ϕs .

Ejercicio 9
Suponemos que es expresable la propiedad y la llamamos α a tal fórmula.

ϕi : "existen dos nodos que no están conectados por i o menos pasos"

ϕ0 : ¬∀xy(R(x, y))
ϕ1 : ∃xy(∃z(R(x, z) ∧ R(z, y)) ∧ R(x, y) ∧ distintos(x, y, z))
...
ϕn : ¬∀xy(∃z1 , ..., zn (R(z1 , z2 ) ∧ R(z2 , z3 ) ∧ ... ∧ R(zn−1 , zn ))

Φ = {ϕi : i ∈ N}
Γ = Φ ∪ {α}
• Veamos que es insatisfacible: Suponemos que es satisfacible, entonces existe un modelo y una
valuación tal que M, v |= Γ. Entonces M, v |= Φ entonces existe un par de nodos que no tiene
camino finito. Pero también M, v |= α que significa que para todo par de nodos hay un camino
finito. Absurdo. Entonces el conjunto Γ es insatisfacible.
• Veamos que es satisfacible: para cualquier subconjunto finito ∆ ⊆ Γ0 puede pasar que no contenga
ningún ϕi entonces simplemente tomando el modelo con un elemento en el dominio lo satisface. Si
por el otro lado contiene ϕi , tomamos k como el mayor i tq ϕ ∈ ∆. Entonces tomamos el modelo
que tiene k + 1 elementos en el dominio y este va a satisfacer a ∆. Entonces por compacidad,
como todo subconjunto es satisfacible entonces el conjunto Γ0 es satisfacible.
Absurdo, no puede ser satisfacible y no satisfacible. Entonces no es expresable la fórmula α.

5
Ejercicio 10
Suponemos que es expresable. Entonces:

α : f es una función circular

Definimos las siguiente fórmulas:

ϕ0 : ∃x(f (x) 6= x)
ϕ1 : ∃x(f 2 (x) 6= x)
...
ϕi : ∃x(f i (x) 6= x)

Φ : {ϕi : i ∈ N}
Γ : Φ ∪ {α}
I) Suponemos que Γ es satisfacible. Entonces existe M y v valuación tq M, v |= Γ. De aquí
se desprende que M, v |= Φ, lo cual implica que f no es circular porque no existe i ∈ N tq
∀x(f i (x) = x). Pero también M, v |= α. Lo cual implica que f es circular. Absurdo. Entonces Γ
es insatisfacible.
II) Sea ∆ ⊆ Γ, ∆ finito. Entonces es de la forma:
• No tiene ningún ϕi : ∆ = {α} ó ∅
• Tiene algún ϕi : Tomamos k como el mayor natural i tq ϕi ∈ ∆. Entonces tomamos el modelo
M tq tiene una fM que cumple que es circular a partir de k + 1 iteraciones. Entonces el modelo
satisface ∆.
Entonces por compacidad Γ es satisfacible. Absurdo, no puede ser satisfacible y no satisfacible. Entonces
α no es expresable.

Ejercicio 11
Ejercicio 12
a. S1: Sabemos por los naturales que el sucesor de un número natural nunca va a ser 0.
S4n : Sabemos que los naturales tienen la propiedad que siempre existe un sucesor (y es distinto
del anterior). Entonces S4n es siempre verdadera.

b. Γ finito,
Con(Γ) = Con(Σ)

• Σ insatisfacible: por compacidad existe subconjunto de Σ insatisfacible. Listo.

• Σ satisfacible: Sabemos que Γ ⊆ Con(Σ) (por def de Con).
Sea ∆ ⊆ Σ tq ∆ |= Γ y que sea el mínimo que se pueda formar. Entonces vemos que es finito
porque Γ es finito (solo se necesitan finitos elementos para derivar finitos elementos).
Notemos que ∆ |= Γ, entonces ∆ |= Σ. Listo.
c. Sea k el mayor i tq S4i ∈ Γ, entonces podemos formar el modelo M tq:
1. ∃x(suck+1 (x) = x) y que
2. para todo z ≤ k cumpla ∀x(sucz (x) 6= x).

6
Tomamos:
1. M = {0, 1, ...,
( k + 2}
1 x=k+2
2. sucM (x) =
x + 1 cc
Podemos pensarlo como una ronda de nodos, donde sucM va pasando de nodo a nodo. Notamos que
cumple con (1) tomando cualquier x distinto de 0 y cumple con (2).
Nota: no podemos hacer que vuelva al 0 porque sino no cumpliría S1.
d. Usamos el recíproco del item (b). Como no existe ningún subconjunto finito de SQN que fuerse
a SQN , entonces no existe ningún conjunto de fórmulas/axiomas va a forzar a SQN , es decir
ningún conjunto de fórmulas es completa con respecto a N .