Algebras-de-Lindenbaum--una-introduccion-booleana-a-la-logica

Vista previa del material en texto

UNIVERSIDAD NACIONAL AUTÓNOMA 
DE MÉXICO 
 
 
FACULTAD DE CIENCIAS 
 
 
 
ÁLGEBRAS DE LINDENBAUM. 
 
UNA INTRODUCCIÓN BOOLEANA A LA LÓGICA. 
 
 
 
T E S I S 
 
QUE PARA OBTENER EL TÍTULO DE : 
 
 
 
M A T E M Á T I C O 
 
 
 
 
 
P R E S E N T A : 
 
 
 
CÉSAR HERNÁNDEZ CRUZ 
 
 
 
TUTOR: DR. JOSÉ ALFREDO AMOR MONTAÑO 
 
 
2006 
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
Hoja de Datos del Jurado 
 
 
1. Datos del alumno. 
Hernández 
Cruz 
César 
Teléfono: 55 19 99 16 
Universidad Nacional Autónoma de México 
Facultad de Ciencias 
Matemáticas. 
 
2. Datos del tutor: 
Doctor 
José Alfredo 
Amor 
Montaño 
 
3. Datos del sinodal 1 
Maestro en Ciencias 
Rafael 
Rojas 
Barbachano 
 
4. Datos del sinodal 2 
Doctora 
Yolanda 
Torres 
Falcón 
 
5. Datos del sinodal 3 
Matemático 
David 
Meza 
Alcántara 
 
6. Datos del sinodal 4 
Doctora 
Gabriela 
Campero 
Arena 
 
7. Datos del trabajo escrito. 
Álgebras de Lindenbaum. 
Una Introducción Booleana a la Lógica. 
87 páginas 
2006. 
,.. 
Indice general 
Introducción 
1. Álgebras de Boole 
1.1. Redes ..... 
1.2. Filtros . . . . . . . . . . . . . . . . . . 
1.3. Propiedades de las Álgebras de Boole . 
2. Álgebras de Lindenbaum 
2.1. Sistemas formales .... 
2.2. Álgebras de Lindenbaum . 
3. Lógica Proposicional y de Predicados 
3.1. Lógica Proposicional ................. . 
3.1.1. Dos aplicaciones del Teorema de Compacidad 
3.2. Lógica de Predicados ........... . 
3.2.1. La Álgebra de Lindenbaum de CP 
4. Teoría de Modelos 
4.1. Nociones básicas . . . . . . . . . 
4.2. Teoremas de L6wenheim-Skolem 
4.3. Ultraproductos . . . . . . . . . . 
5. Filtros y Teorías 
5.1. Filtros como Teorías - Teorías como Filtros 
5.2. Equivalentes del Teorema de Compacidad 
A. Apéndice 
A.l. Teorema de Compacidad para SC. 
A.2. Constantes y Letras Funcionales . 
A.2.1. Cerradura bajo chivos expiatorios. 
v 
1 
1 
6 
10 
19 
19 
23 
33 
33 
39 
42 
50 
57 
57 
61 
63 
69 
69 
77 
81 
81 
82 
84 
〈X,≤〉 X
≤ X
x ∈ X x ≤ x
x, y ∈ X x ≤ y y ≤ x x = y
x, y, z ∈ X x ≤ y y ≤ z x ≤ z
X
〈X,≤〉 ≤
x, y ∈ X x ≤ y y ≤ x
〈X,≤〉
< X x < y x ≤ y x �= y <
X ≤ 〈X,≤〉 <
X ≤
≤
X X
≤ x ≤ y
Capítulo 1 
Álgebras de Boole 
1.1. Redes 
Un orden parcial reflexivo es un par ordenado 
conjunto no vacío y 
propiedades: 
es una relación binaria sobre 
(a) Reflexividad: para cada 
(b) A ntisimetría: para cada 
(c) Transitividad: para cada 
, si 
, si 
y 
y 
donde es un 
con las siguientes 
, entonces 
, entonces 
Una relación binaria sobre un conjunto 
(a) y con (c), será un preorden. 
, que cumple únicamente con 
Diremos que un orden parcial 
además: 
(d) Dicotomía: para cada 
es un orden total si cumple 
se cumple o 
Si es un orden parcial reflexivo, podemos definir una nueva relación 
sobre por si y sólo si y es llamado el orden parcial 
irreflexivo de inducido por . Si es un orden total, es el orden 
estricto de inducido por . Es común la utilización de órdenes estrictos, 
que consisten en conjuntos dotados de un orden estricto. 
De ahora en adelante, no mencionaremos la relación de orden explíci-
tamente, a menos que sea necesario para evitar ambigüedad, así, nos referire-
mos al "conjunto parcialmente ordenado "donde la relación de orden en 
será ,a menos que se indique lo contrario. Si a menudo utilizaremos 
Capítulo 1 
Álgebras de Boole 
1.1. Redes 
Un orden parcial reflexivo es un par ordenado 
conjunto no vacío y 
propiedades: 
es una relación binaria sobre 
(a) Reflexividad: para cada 
(b) A ntisimetría: para cada 
(c) Transitividad: para cada 
, si 
, si 
y 
y 
donde es un 
con las siguientes 
, entonces 
, entonces 
Una relación binaria sobre un conjunto 
(a) y con (c), será un preorden. 
, que cumple únicamente con 
Diremos que un orden parcial 
además: 
(d) Dicotomía: para cada 
es un orden total si cumple 
se cumple o 
Si es un orden parcial reflexivo, podemos definir una nueva relación 
sobre por si y sólo si y es llamado el orden parcial 
irreflexivo de inducido por . Si es un orden total, es el orden 
estricto de inducido por . Es común la utilización de órdenes estrictos, 
que consisten en conjuntos dotados de un orden estricto. 
De ahora en adelante, no mencionaremos la relación de orden explíci-
tamente, a menos que sea necesario para evitar ambigüedad, así, nos referire-
mos al "conjunto parcialmente ordenado "donde la relación de orden en 
será ,a menos que se indique lo contrario. Si a menudo utilizaremos 
x y y
x
X X X
X
A X
A X X
A x ∈ X A X
a ≤ x a ∈ A x ∈ X A
X a ∈ A x ≤ a
x ∈ X A x
A X
A X x ∈ X A
a ∈ A a ≤ x y A X x ≤ y
x ∈ X
A A
A X
A X
A A
A A A = {ai|i ∈ I}
X
∨
i∈I ai A
∧
i∈I ai
A A x
y A = {x, y} x∨y A x∧y A
x ∨ y x ∧ y x
y
〈X,≤〉
x, y ∈ X
{x, y}
R
x, y ∈ R x ∨ y x ∧ y
κ κ
≤ κ
< κ− completa
< κ completa κ
κ
Q
{r ∈ Q|r · r < 2} Q
x
x
Demostración. x y R
x ≤ x∨y y ≤ x∨y x y x = x∨y
y = x ∨ y x = y �
x, y, z ∈ R
L1 x ∨ y = y ∨ x x ∧ y = y ∧ x
L2 x ∨ (y ∨ z) = (x ∨ y) ∨ z x ∧ (y ∧ z) = (x ∧ y) ∧ z
L3 (x ∨ y) ∧ y = y (x ∧ y) ∨ y = y
Demostración.
�
R
x ∈ R y ∈ R
L4 x ∨ y = 1 x ∧ y = 0
y x
e.g.
X = {0, a, b, c, 1}
≤
x, y ∈ X x ≤ y x = 0 y = 1 x = y
a ∨ b = b ∨ c = c ∨ a = 1 a ∧ b = b ∧ c =
c ∧ a = 0 a, b, c
R distributiva x, y, z ∈ R
L5 (x ∨ y) ∧ z = (x ∧ z) ∨ (y ∧ z)
(x ∧ y) ∨ z = (x ∨ z) ∧ (y ∨ z)
R x ∈ R x∧ 1 =
x x ∨ 1 = 1 x ∧ 0 = 0 x ∨ 0 = x
〈R,≤〉 x, y, z ∈ R
(x ∧ z) ∨ (y ∧ z) ≤ (x ∨ y) ∧ z
(x ∨ z) ∧ (y ∨ z) ≤ (x ∧ y) ∨ z
Demostración.
(x∧ z) ≤ z (y ∧ z) ≤ z (x∧ z)∨ (y ∧ z) ≤
z (x ∧ z) ≤ x ≤ (x ∨ y) (y ∧ z) ≤ y ≤ (x ∨ y)
(x ∧ z) ∨ (y ∧ z) ≤ (x ∨ y)
(x ∧ z) ∨ (y ∧ z) ≤ (x ∨ y) ∧ z
�
L5 R x, y
z R
L′5 (x ∨ y) ∧ z ≤ (x ∧ z) ∨ (y ∧ z)
(x ∧ y) ∨ z ≤ (x ∨ z) ∧ (y ∨ z)
R
Demostración. R
y z x R x∨y = 1
x ∧ z = 0
y = y ∨ 0 = y ∨ (x ∧ z)
= (y ∨ x) ∧ (y ∨ z)
= 1 ∧ (y ∨ z)
= y ∨ z
z = y ∨ z y = z �
x x∗
(x∗)∗ = x
〈P(X),⊆〉
X
X
〈P(X),⊆〉
B
B = 〈B,∨,∧, ∗, 0, 1〉
L1−L5
≤ B x ≤ y x ∨ y = y
0 �= 1
B = 〈B,∨,∧, ∗, 0, 1〉
L1 − L5 ≤ x ≤ y
x ∨ y = y 〈B,≤〉
Demostración. 〈B,≤〉
x, y ∈ B x ∧ y ∈ B x ∨ y ∈ B
〈B,≤〉
x ∈ B x∗ ∈ B ∗
〈B,≤〉
L5
〈B,≤〉
〈B,≤〉
x ≤ y x ∨ y = y,
y ≤ z y ∨ z = z,
x ∨ z = x ∨ (y ∨ z) = (x ∨ y) ∨ z = y ∨ z = z
x ≤ y ⇒ x ∨ y = y
y ≤ x⇒ y ∨ x = x
}
⇒ x = y
1 = x ∨ 1 = x ∨ (x ∨ x∗) =
(x ∨ x) ∨ x∗ 0 = 0 ∨ 0 = (x ∧ x∗) ∨ (x ∧ x∗) = (x ∨ x) ∧ x∗
x ∨ x = x
x ≤ x �
x, y ∈ F x ∧ y ∈ F
x ∈ F y ∈ R x ≤ y y ∈ F
0 /∈ F
x, y ∈ I x ∨ y ∈ I
x ∈ I y ∈ R y ≤ x y ∈ I
1 /∈ I
R
R R
R
R R {1}
{0} R
x ∈ R
{y|x ≤ y} x
{y|y ≤ x} x
i.e.
L1 − L5 ∧ ∨
L1−L5
L1 − L5
∧,∨, 0
≤ ≥
x, y
x ∧ y∗ = 0 x ≤ y
Demostración. x ∧ y∗ = 0 x = x ∧ 1 =
x ∧ (y ∨ y∗) = (x ∧ y) ∨ (x ∧ y∗) = (x ∧ y) ∨ 0 = x ∧ y ≤ y
x ≤ y x∧y = x x∧y∗ = (x∧y)∧y∗ =
x ∧ (y ∧ y∗) = x ∧ 0 = 0 �
x∨y∗ = 1 y ≤ x
A
pif
A
A B
A0 B
A
A0 = {x ∈ B| (∃a ∈ A)(a ≤ x)}
Ac A
Ac = { (X)|X ∈ [A]<ℵ0}
F A A0 = F sub−base
A Ac F
A F F = (Ac)0 A genera a F
A ⊆ Ac ⊆ (Ac)0
(Ac)0
(Ac)0
Demostración. x ∈ (Ac)0 X ∈
[A]<ℵ0 X) ≤ x
x, y ∈ (Ac)0 X,Y ∈ [A]<ℵ0 (X) ≤
x (Y ) ≤ y X Y X ∪ Y ∈ [A]<ℵ0
(X ∪ Y ) = (X)∧ (Y ) (X)∧ (Y ) ≤ x ∧ y
x ∧ y ∈ (Ac)0 x ∈ (Ac)0 x ≤ y
y ∈ (Ac)0 0 /∈ (Ac)0
A
0 ∈ (Ac)0 X ∈ [A]<ℵ0
(X) ≤ 0 (X) = 0 A
F A ⊆ F x ∈ (Ac)0
X ∈ [A]<ℵ0 (X) ≤ xX ⊆ F F
(X) ∈ F F x ∈ F
(Ac)0 ⊆ F �
A κ [A]<κ = {X ⊆ A |X| < κ}
A
B B
F
x ∈ B x ∈ F x∗ ∈ F
Demostración. x ∈ B x x∗ F
G F x
G − F x /∈ F x∗ ∈ F ⊆ G
x ∧ x∗ = 0 ∈ G
F
F x /∈ F
G = ((F ∪ {x})c)0 F G
F ∪ {x} X ∈ [F ]<ℵ0 (X) ∧ x = 0
(X) ≤ x∗ (X) ∈ F x∗ ∈ F �
Demostración. F B F
B F F ∈ F F
F
F
D = {Di|i ∈ I} F D =
⋃
i∈I Di x, y ∈ D
i, j ∈ I x ∈ Di y ∈ Dj D
Di ⊆ Dj Dj ⊆ Di Di ⊆ Dj
x, y ∈ Dj Dj x ∧ y ∈ Dj z ∈ B x ≤ z
z ∈ Dj ⊆ D i ∈ I 0 /∈ Di
0 /∈ D D F ⊆ D
D ∈ F D D F
F
G G F �
Demostración.
�
Demostración. x �= 0 {x}
�
Demostración. x �= y x ≤ y
y ≤ x x
y x ∧ y∗ �= 0 {x, y∗}
F B y∗ ∈ F y /∈ F �
A
A
0 /∈ A
A
A A A
A A
B B
B
B′ B B′
x ∈ B′ x∗ ∈ B′
x ∧ x∗ = 0 ∈ B′ x ∨ x∗ = 1 ∈ B′ B′
B′ B
{0, 1} B B
{0} {1}
I =
{x∗|x ∈ F} B′ = F ∪ I
�
B1, B2 B1 B2
f B1 B2 i.e.
x, y ∈ B1 :
f(x ∧ y) = f(x) ∧ f(y)
f(x ∨ y) = f(x) ∨ f(y)
f(x∗) = f(x)∗
B1 B2
B1 B2
B1 B2
B1 B2
x ≤ y f(x) ≤ f(y) x, y ∈ B1
f [B1] B2
�
f f
isomorfismo B1 f [B1] f f
B1 B2 B1 B2
B1 B2 isomorfas B1 ∼= B2
F B ∼F
B
x ∼F y d ∈ F, x ∧ d = y ∧ d
∼F
Demostración. �
∼F x ∼F
x′ y ∼F y′
x ∧ y ∼F x′ ∧ y′
x ∨ y ∼F x′ ∨ y′
x∗ ∼F x′∗
Demostración. �
x� y (x ∨ y∗) ∧ (x∗ ∨ y)
x, y ∈ B
x ∼F y x� y ∈ F
x� y = 1 x = y
Demostración. (x ∨
y∗) ∧ (x∗ ∨ y) = (x∗ ∧ y∗) ∨ (x ∧ y)
y ∧ [(x∗ ∧ y∗) ∨ (x ∧ y)] = [y ∧ (x∗ ∧ y∗)] ∨ [y ∧ (x ∧ y)] = y ∧ x
x ∧ [(x∗ ∧ y∗) ∨ (x ∧ y)] = [x ∧ (x∗ ∧ y∗)] ∨ [x ∧ (x ∧ y)] = x ∧ y
y ∧ [(x∗ ∧ y∗) ∨ (x ∧ y)] = x ∧ [(x∗ ∧ y∗) ∨ (x ∧ y)]
y ∧ (x� y) = x ∧ (x� y)
x� y ∈ F x ∼F y
d ∈ F d = 1∧d = (y∨y∗)∧d =
(y ∧ d) ∨ (y∗ ∧ d) = (x ∧ d) ∨ (y∗ ∧ d) = (x ∨ y∗) ∧ d
d ≤ (x ∨ y∗) F x ∨ y∗ ∈ F x∗ ∨ y ∈ F
F (x ∨ y∗) ∧ (x∗ ∨ y) ∈ F
x = y x � y = 1
(x ∨ y∗) ∧ (x∗ ∨ y) = 1 (x ∨ y∗) = 1
(x∗ ∨ y) = 1
�
|x| ∼F
x B B/F = {|x|∣∣x ∈ B}
x, y ∈ B
|x| ∧ |y| = |x ∧ y|
|x| ∨ |y| = |x ∨ y|
|x|∗ = |x∗|
B/F
h : B → B/F h(x) = |x|
B B/F
x ∈ B
|x| = 1 x ∈ F
Demostración. x ∈ F |x| = F
1 ∈ F F �
f : B1 → B2
F = {x ∈ B1|f(x) = 1} f [B1]
B1/F
Demostración. F
�
x, y ∈
B1
|x| = |y| x ∼F y
x� y ∈ F
f(x� y) = 1
f(x)� f(y) = 1 f
f(x) = f(y)
|x| x h : B1 → B1/F
g : B1/F → f [B1] g(|x|) = f(x)
g
B1/F f [B1] B1/F ∼= f [B1] �
F f
kernel
{x|f(x) = 0}
{1}
Demostración. f : B1 → B2
{1} f(x) = f(y) f(x∨y∗) = f(x)∨f(y∗) =
f(x) ∨ f(y)∗ = f(x) ∨ f(x)∗ = 1 f(x∗ ∨ y) = 1
f(x�y) = 1 x�y = 1 x = y
f �
F
x ∨ y ∈ F x ∈ F y ∈ F
B/F ∼= 2
x ∈ B x∗
Demostración. (b)⇔ (d)
(d) ⇒ (a) |x| x B
B/F |x| �= 1 x /∈ F
x∗ ∈ F |x∗| = |x|∗ = 1
|x| = |x|∗∗ = 0
B/F = {0, 1} ∼= 2
(a) ⇒ (d) x /∈ F |x| �= 1 |x| = 0
|x∗| = 1 x∗ ∈ F
(b)⇒ (c) x∨ y ∈ F x /∈ F G = ((F ∪ {x})c)0
F G z ∈ F
z ∧ x = 0 z, x ∨ y ∈ F z ∧ (x ∨ y) = (z ∧ x) ∨ (z ∧ y) = 0 ∨ (z ∧ y) =
z ∧ y ∈ F z ∧ y ≤ y F y ∈ F
(c) ⇒ (d) x ∈ B x ∨ x∗ = 1 ∈ F x ∈ F
x∗ ∈ F �
{An|n < ω}
n ∈ ω an = inf(An) Π
Π
n ∈ ω h(an) = {h(a)|a ∈ An}
h B B/F ∼= 2
{An|n ∈ ω}
n ∈ ω An
x Π
Demostración. an = (An)
{bn|n ∈ ω} n ∈ ω bn ∈ An {x, a0 ∨ b∗0, . . . , an ∨ b∗n}
m = 0 A0
b ∈ A0 x ∧ (a0 ∨ b∗) = 0
x ∧ (a0 ∨ b∗) = (x ∧ a0) ∨ (x ∧ b∗)
x ∧ a0 = 0 x ∧ b∗ = 0 b ∈ A0 x ≤ b
b ∈ A0 x ≤ a0 = (A0) x = x ∧ a0 = 0
b ∈ A0 x ∧ (a0 ∨ b) = 0 b ∈ A0
x ∧ (a0 ∨ b) b0 b
m ∈ ω 0 < m
n ∈ m bn
y = x ∧ (a0 ∨ b∗0) ∧ · · · ∧ (am−1 ∨ b∗m−1)
y �= 0
b ∈ Am y ∧ (am ∨ b∗) = 0
y ∧ (am ∨ b∗) = (y ∧ am) ∨ (y ∧ b∗)
y ∧ am = 0 y ∧ b∗ = 0 b ∈ Am y ≤ b
b ∈ Am y ≤ am = (Am) y = y ∧ am = 0
bm ∈ Am
y ∧ (am ∨ b∗m) �= 0
n ≤ m bn
bn n ∈ ω
{x, a0 ∨ b∗0, . . . , an ∨ b∗n, . . . }
F B
F Π
h B B/F an ∨ b∗n ∈ F
h(an) ∨ h(bn)∗ = h(an ∨ b∗n) = 1 h(an) ≥ h(bn)
{h(b)|b ∈ An} ≤ h(an)
an = (An) an ≤ b b ∈ An h(an) ≤ h(b)
b ∈ An
h(an) ≤ {h(b)|b ∈ An}
h(an) = {h(b)|b ∈ An}
F Π �
Demostración. B A
B B A �= ∅
h : B → P(A)
h(b) = {D ∈ A|b ∈ D}
h b B
b h a b
B D ∈ A a ∈ D b /∈ D D ∈
h(a) − h(b) h(a) �= h(b) h
B A
h(a∗) = A− h(a) a∗ ∈ D a /∈ D
h(a ∨ b) = h(a) ∪ h(b) a ∨ b ∈ D a ∈ D b ∈ D
h(a ∧ b) = h(a) ∩ h(b) a ∧ b ∈ D a ∈ D b ∈ D
h(0) = ∅ h(1) = A 0 /∈ D 1 ∈ D D
h B P(A) B h B
P(A) h B B �
S S
S S
S S ES
Φ ⊆ ES
= 〈S,Φ〉
Φ
Φ ES
Φ
1 2 1
2 1 < 2
1 2
1
2 1
= 〈S,Φ〉 Rn n
n ∈ N 2 ≤ n n Φ
Φn
n − 1 ϕ
n − 1 ϕ Rn
Capítulo 2 
Álgebras de Lindenbaum 
2.1. Sistemas formales 
Sea un conjunto no vacío. A los elementos de les llamaremos símbolos 
de . Diremos que, una sucesión finita de símbolos de ,forma una expresion 
de . Al conjunto de expresiones de lo denotaremos por 
Definición 2.1.1 Sea S un conjunto de símbolos y , no vacío. Por 
un Lenguaje Formal (L. F.), L, entederemos a la pareja ordenada 
L 
A S de le llamará el alfabeto de L, y a el conjunto de fórmulas de L. 
Por lo general para construir a partir de se dan una serie de reglas, 
llamadas reglas de formación de las fórmulas de L, y que proporcionan un 
mecanismo efectivo para decidir si una expresión dada pertenece o no a 
Definición 2.1.2 Si L Y L son dos lenguajes formales, decimos que L es 
un sublenguaje de L , denotado por L L si y sólo si: 
(i) El alfabeto de L está contenido en el de L 
(ii) El conjunto de fórmulas de L está conformado por todas aquellas 
fórmulas de L que sólo tienen símbolos de L . 
Sea L un L. F. Por una regla de inferencia de aridad en L, 
con y , entenderemos una relación -aria sobre ,es decir, un 
subconjunto del producto cartesiano , de tal suerte que para todo conjunto 
de fórmulas y cada fórmula ,se pueda decidir efectivamente si las 
fórmulas junto con están en la relación , y esto debe ocurrir si 
Capítulo 2 
Álgebras de Lindenbaum 
2.1. Sistemas formales 
Sea un conjunto no vacío. A los elementos de les llamaremos símbolos 
de . Diremos que, una sucesión finita de símbolos de ,forma una expresion 
de . Al conjunto de expresiones de lo denotaremos por 
Definición 2.1.1 Sea S un conjunto de símbolos y , no vacío. Por 
un Lenguaje Formal (L. F.), L, entederemos a la pareja ordenada 
L 
A S de le llamará el alfabeto de L, y a el conjunto de fórmulas de L. 
Por lo general para construir a partir de se dan una serie de reglas, 
llamadas reglas de formación de las fórmulas de L, y que proporcionan un 
mecanismo efectivo para decidir si una expresión dada pertenece o no a 
Definición 2.1.2 Si L Y L son dos lenguajes formales, decimos que L es 
un sublenguaje de L , denotado por L L si y sólo si: 
(i) El alfabeto de L está contenido en el de L 
(ii) El conjunto de fórmulas de L está conformado por todas aquellas 
fórmulas de L que sólo tienen símbolos de L . 
Sea L un L. F. Por una regla de inferencia de aridad en L, 
con y , entenderemos una relación -aria sobre ,es decir, un 
subconjunto del producto cartesiano , de tal suerte que para todo conjunto 
de fórmulas y cada fórmula ,se pueda decidir efectivamente si las 
fórmulas junto con están en la relación , y esto debe ocurrir si 
n− 1 ϕ
Rn ϕ n− 1
Rn
= 〈S,Φ〉 {Ri}i∈I I
SF = 〈 , {Ri}i∈I〉.
〈S,Φ〉
SF SF = 〈 , {Ri}i∈I〉
L
SF
Δ ⊆ Φ ϕ ∈ Φ ϕ Δ
Δ SF ϕ1, . . . ϕn
(i) ϕn = ϕ
(ii) j ∈ {1, . . . , n} ϕj Δ ϕj
SF
Δ �SFL ϕ
ϕ1, . . . , ϕn
ϕ Δ SF Δ
SF
Δ Δ �SF ϕ
Γ Δ Γ �SF ϕ
Demostración. ϕ1, . . . , ϕn ϕ Δ Γ
Δ Γ
ϕ1, . . . , ϕn ϕ Γ �
Δ ψ
Δ �SF ϕ ϕ ψ
ψ �SF ϕ
ϕ
ψ Δ Δ Φ Δ ∪ {ψ} � ϕ
Δ;ψ �SF ϕ
SF
Δ;ψ � ϕ
Δ Δ � ϕ
� ϕ
SF Γ ⊆ Φ
Γ Γ�
Γ SF
Γ� = {ϕ ∈ Φ|Γ � ϕ}
SF = 〈 , {Ri}i∈I〉 T ⊆ Φ
T T� = T T
T
T T
T
T T
Γ ⊆ T Γ Γ� = T Γ
T Γ T
T T
ϕ ∈ (T) ϕ /∈ T (T) = T
T
T
ϕ ∈ (T) Γ � ϕ Γ
T
T
T ϕ ∈ (T)
T ϕ ¬ϕ
T T
T
ϕ ∈ (T) ϕ (T)
T T
T
T
ϕ
ϕ
Φ
SF
SF
SF
Φ
SF
Φ
ϕ ψ
Δ Δ Δ;�
Δ;� Φ ϕ,ψ
Δ ⊆ Φ ∼Δ;�
ψ ∼Δ;� ϕ Δ;ψ � ϕ Δ;ϕ � ψ
Φ
ϕ ∈ Φ |ϕ| = {ψ ∈ Φ∣∣ψ ∼Δ;� ϕ}
ϕ,ψ χ Δ;ϕ � ϕ Δ;ϕ � ψ
Δ;ψ � χ Δ;ϕ � χ
Φ/ ∼Δ;�= {|ϕ|
∣∣ϕ ∈ Φ}
|Φ|
≤Δ;�
|ϕ| ≤Δ;� |ψ| Δ;ϕ � ψ
Δ;�
LA1 ϕ ψ χ
Δ;χ � ϕ Δ;χ � ψ
ξ Δ; ξ � ϕ Δ; ξ � ψ Δ; ξ � χ
LA2 ϕ ψ χ
Δ;ϕ � χ Δ;ψ � χ
ξ Δ;ϕ � ξ Δ;ψ � ξ Δ;χ � ξ
Δ;� LA1
ϕ,ψ ∈ Φ {|ϕ|, |ψ|} ≤Δ;�
LA2 Δ;�
LA1 LA2 |Φ|
LA3 1
ϕ ∈ Φ Δ;ϕ � 1
LA4 0
ϕ ∈ Φ Δ; 0 � ϕ
1 0 ∼Δ;�
|Φ|
LA5 ϕ ∈ Φ ψ χ
ϕ ψ LA1 Δ;χ � 0
ξ ϕ ψ
LA2 Δ; 1 � ξ
LA1−LA5
LA6 ϕ ψ Δ;ϕ � ψ Δ;ψ � ϕ
ψ
ϕ
ϕ ψ
ϕ ψ ϕ∧ψ
LA1 ϕ ψ ϕ ∨ ψ
LA2
LA7 ϕ,ψ χ
Δ; (ϕ ∨ ψ) ∧ χ � (ϕ ∧ χ) ∨ (ψ ∧ χ)
Δ; (ϕ ∧ ψ) ∨ χ � (ϕ ∨ χ) ∧ (ψ ∨ χ)
SFL Δ Δ;�
LA1−LA7 〈|Φ|,≤Δ;�〉
Φ ≤Δ;�
LA7 i.e. ϕ∧ ψ ϕ ∨ ψ
v.g.
∧
ϕ ∧ ψ
ϕ ψ LA1
∧
(ϕ ∧ ψ) ∧
∧ ∨ ¬ SFL
LA3, LA4 LA6
LA′1 ∧
ϕ ψ (ϕ∧ψ)
Δ; (ϕ ∧ ψ) � ϕ Δ; (ϕ ∧ ψ) � ψ
ξ Δ; ξ � ϕ Δ; ξ � ψ Δ; ξ � (ϕ ∧ ψ)
LA′2 ∨
ϕ ψ (ϕ∨ψ)
Δ;ϕ � (ϕ ∨ ψ) Δ;ψ � (ϕ ∨ ψ)
ξ Δ;ϕ � ξ Δ;ψ � ξ (ϕ ∨ ψ) � ξ
LA′5 ¬
ϕ ∈ Φ ¬ϕ Δ; (ϕ∧¬ϕ) � 0
Δ; 1 � (ϕ ∨ ¬ϕ)
LA′7 ϕ,ψ χ
Δ; (ϕ ∨ ψ) ∧ χ � (ϕ ∧ χ) ∨ (ψ ∧ χ)
Δ; (ϕ ∧ ψ) ∨ χ � (ϕ ∨ χ) ∧ (ψ ∨ χ)
LAi LA
′
i
Δ Δ;�
→
Δ
→
ϕ ψ
Δ ⊆ Φ
Δ;ϕ � ψ Δ � ϕ→ ψ. �
ϕ → ψ
ψ ϕ Δ [�]
≤Δ;�
|ϕ| ≤Δ;� |ψ| Δ � ϕ→ ψ
Δ
Δ e.g.
LA′1
LA1 ∧
ϕ ψ (ϕ ∧ ψ)
(ϕ ∧ ψ) → ϕ (ϕ ∧ ψ) → ψ Δ
ξ ξ → ϕ ξ → ψ
Δ Δ � ξ → (ϕ ∧ ψ) Δ � (ξ →
ϕ)→
(
(ξ → ψ)→ (ξ → [ϕ ∧ ψ])
)
LA′1 − LA′7
Δ
Δ
SF Δ Φ
|Φ| = Φ/ ∼Δ;�= {|ϕ|
∣∣ϕ ∈ Φ} 〈|Φ|,≤Δ;�〉
→ [�]
ϕ ψ Δ;ϕ � ψ Δ;ψ � ϕ
Δ
AL1a (ϕ ∧ ψ)→ ϕ
AL1b (ϕ ∧ ψ)→ ψ
AL2 (χ→ ϕ)→
(
(χ→ ψ)→ (χ→ [ϕ ∧ ψ])
)
AL3a ϕ→ (ϕ ∨ ψ)
AL3b ψ → (ϕ ∨ ψ)
AL4 (ϕ→ χ)→
(
(ψ → χ)→ ([ϕ ∨ ψ]→ χ)
)
AL5 ϕ ∧ ¬ϕ→ ψ
AL6 ψ → ϕ ∨ ¬ϕ
AL7 (ϕ ∨ ψ) ∧ χ→ (ϕ ∧ χ) ∨ (ψ ∧ χ)
AL8 (ϕ ∧ ψ) ∨ χ→ (ϕ ∨ χ) ∧ (ψ ∨ χ)
AL9 (ϕ→ ψ)→
(
(ψ → χ)→ (ϕ→ χ)
)
AL10 ϕ→ (ψ → ϕ)
〈|Φ|,≤Δ;�〉
AL9 AL10
SF
Δ
→ [�]
Δ;�
AL9 AL10 Δ;�
AL9 AL10
Δ � (ϕ→ ψ)→ ((ψ → χ)→ (ϕ→ χ))
Δ; (ϕ → ψ) � ((ψ → χ) → (ϕ → χ)) Δ ∪ {(ϕ →
ψ), (ψ → χ)} � (ϕ→ χ) → ≤Δ;�
|ϕ| ≤Δ;� |ψ| |ψ| ≤Δ;� |χ| Δ � (ϕ → ψ) Δ � (ψ → χ)
Δ ∪ {(ϕ → ψ), (ψ → χ)} � (ϕ → χ) Δ � (ϕ → χ)
|ϕ| ≤Δ; |χ|
Δ � ϕ → (ϕ → ϕ)
Δ;ϕ � (ϕ→ ϕ) Δ∪{ϕ,ϕ} � ϕ
Δ;ϕ � ϕ |ϕ| ≤Δ;� |ϕ|
AL1 −
AL6
|ϕ| ∧ |ψ| = |ϕ ∧ ψ|
|ϕ| ∨ |ψ| = |ϕ ∨ ψ|
|ϕ|∗ = |¬ϕ|
0 = |ϕ ∧ ¬ϕ|
1 = |ϕ ∨ ¬ϕ|
AL7 AL8
‘∧
‘∨
SF
→ [�]
ϕ ψ Δ;ϕ � ψ Δ;ψ � ϕ Δ Φ
AL1 −AL10 SF Δ 〈|Φ|,≤Δ;�〉
Δ 〈|Φ|,≤Δ;�〉
SF
ϕ ∈ Φ |ϕ|
ϕ
Σ ⊆ Φ |Σ| = {|ϕ|∣∣ϕ ∈
Σ} |Σ| A Σ
ϕ1, . . . , ϕn ∈ Σ {ϕ1, . . . , ϕn} ϕ1 ∧ · · · ∧ϕn
|ϕ1| ∧ · · · ∧ |ϕn| 
= 0
Σ
|Σ| A
Demostración. �
AL10
ϕ ∨ ¬ϕ
SF
→ [�] Δ
Δ � ϕ→ ψ Δ � ϕ Δ � ψ
→ [�]
Δ;ϕ � ψ Δ � ϕ Δ � ψ �
ξ Δ � ξ AL10 Δ � ξ →
(
(ϕ∨¬ϕ)→
ξ
)
Δ � (ϕ∨¬ϕ)→ ξ
AL6 Δ � ξ → (ϕ∨¬ϕ)
∼Δ;� ξ ϕ ∧ ¬ϕ
SF Δ
Δ
AL10
ϕ∧¬ϕ
Δ
AL11 ¬ϕ→ (ϕ→ ψ)
{Pi}i∈I ∪{∧,∨,¬,→}∪{(, )} I
P = {Pi}i∈I
i
ii ϕ ψ (¬ϕ) (ϕ ∧ ψ) (ϕ ∨ ψ) (ϕ→ ψ)
iii
i ii
2
P
2
f f̄ : Φ→ 2
ϕ ψ f̄(ϕ) f̄(ψ)
f̄(ϕ ∧ ψ) = f̄(ϕ) ∧ f̄(ψ)
f̄(ϕ ∨ ψ) = f̄(ϕ) ∨ f̄(ψ)
f̄(¬ϕ) = f̄(ϕ)∗
f̄(ϕ→ ψ) = f̄(ϕ)∗ ∨ f̄(ψ)
ϕ f̄
2 f ϕ
f � ϕ
f � ϕ ⇐⇒ f̄(ϕ) = 1
ϕ |= ϕ
Σ
Σ
LA1 − LA10
A
A
�
Σ
ψ ϕ Σ, ψ � ϕ
Σ � ψ → ϕ
ψ � ϕ
� ψ → ϕ
[�]
→ �
ϕ f : P → 2
|ψ| |χ|
A ˜̄f : A → 2˜̄f(|ψ|) = f̄(ψ) |ψ| = |χ| f̄(ψ) = f̄(χ)
|ϕ| = 1 f̄(ϕ) = 1 f
ϕ
ϕ ϕ ¬ϕ
Demostración. ϕ ¬ϕ
ϕ ¬ϕ
�
2 f(Pn) = h(|Pn|)
ϕ f̄(ϕ) = h(|ϕ|)
Demostración.
ϕ
ϕ ψ
f̄(ϕ ∧ ψ) = f̄(ϕ) ∧ f̄(ψ) = h(|ϕ|) ∧ h(|ψ|) = h(|ϕ| ∧ |ψ|) = h(|ϕ ∧ ψ|)
f̄(ϕ ∨ ψ) = f̄(ϕ) ∨ f̄(ψ) = h(|ϕ|) ∨ h(|ψ|) = h(|ϕ| ∨ |ψ|) = h(|ϕ ∨ ψ|)
f̄(¬ϕ) = f̄(ϕ)∗ = h(|ϕ|)∗ = h(|ϕ|∗) = h(|¬ϕ|)
f̄(ϕ→ ψ) = f̄(ϕ)∗ ∨ f̄(ψ) = h(|ϕ|∗) ∨ h(|ψ|) = h(|ϕ|∗ ∨ |ψ|) = h(|¬ϕ ∨ ψ|)
→
ϕ → ψ
|¬ϕ ∨ ψ|
f h �
A U
A A /U
2 U
fU A A /U
f Uf = {|ϕ|
∣∣f̄(ϕ) =
1} A |ϕ|, |ψ| ∈ Uf
f̄(ϕ ∧ ψ) = f̄(ϕ) ∧ f̄(ψ) = 1 ∧ 1 = 1 |χ| ∈ A |ϕ| ≤ |χ|
A ϕ→ χ
f̄(ϕ → χ) = 1 ⇒ f̄(¬ϕ ∨ χ) = 1 ⇒ f̄(ϕ)∗ ∨ f̄(χ) = 1 ⇒ 0 ∨ f̄(χ) =
1 ⇒ f̄(χ) = 1 |ϕ| /∈ Uf ⇒ f(ϕ) �= 1 ⇒ f̄(ϕ) = 0 ⇒ f̄(ϕ)∗ =
1 ⇒ f̄(¬ϕ) = 1 ⇒ |¬ϕ| ∈ Uf Uf
A
Demostración. ϕ
A |ϕ| �= 1 |¬ϕ| �= 0
U A
|¬ϕ| A /U ∼= 2
f
A A /U |¬ϕ| ∈ U h(|¬ϕ|) = 1 f(¬ϕ) = 1
f(ϕ) = 0 ϕ �
Σ ϕ ϕ
¬ϕ Σ
ϕ {ϕ}
Σ ϕ
Σ ∪ {ϕ} Σ � ¬ϕ
Demostración. Σ � ¬ϕ Σ ∪
{ϕ} � ¬ϕ Σ∪{ϕ} � ϕ Σ∪{ϕ}
Σ∪ {ϕ} Σ∪ {ϕ} � ψ
Σ ∪ {ϕ} � ¬ψ Σ � ϕ → ψ
Σ � ϕ → ¬ψ (ϕ → ψ) →
(
(ϕ → ¬ψ) → ¬ϕ
)
Σ � ¬ϕ �
ϕ ¬ϕ ϕ
ϕ ϕ ϕ
Demostración. (a) ⇒ (b) ¬ϕ ¬ϕ
f f̄(¬ϕ) �= 1
f̄(¬ϕ) = 0 f̄(ϕ) = 1 ϕ ϕ
f f̄(ϕ) = 1
f̄(ϕ)∗ = 0 f̄(¬ϕ) = 0 ¬ϕ ¬ϕ
� ¬¬ϕ↔ ϕ
(b)⇒ (a) ϕ ⇔ ¬ϕ ⇔ ϕ
(b)⇔ (c) ϕ ⇔ ¬ϕ ⇔ ϕ
(d)⇒ (c) ϕ
(c)⇒ (d) {ϕ1, . . . , ϕn} (ϕ1 ∧
· · ·∧ϕn)
ϕ1, . . . , ϕn (ϕ1∧ · · ·∧ϕn) f(ϕ1∧ · · ·∧
ϕn) = f(ϕ1) ∧ · · · ∧ f(ϕn) {ϕ1, . . . , ϕn} ⇔
(ϕ1∧· · ·∧ϕn) ⇔ (ϕ1∧· · ·∧ϕn) ⇔ {ϕ1, . . . , ϕn}
(ϕ1∧· · ·∧ϕn)
{ϕ1, . . . , ϕn} {ϕ1, . . . , ϕn} �
(ϕ1∧· · ·∧ϕn) {ϕ1, . . . , ϕn} � ϕi i ∈ {1, . . . , n}
AL2 AL10
{ϕ1, . . . , ϕn} (ϕ1 ∧ · · · ∧ ϕn)
AL1a {(ϕ1 ∧ · · · ∧
ϕn)} � ϕi i ∈ {1, . . . , n}
{ϕ1, . . . , ϕn}
Σ
Σ
Demostración. Σ
Σ0 Σ0
Σ Σ
Σ
ϕ Σ � ϕ Σ � ¬ϕ
Σ Σ1 Σ2 Σ1 � ϕ Σ2 � ¬ϕ Σ0 = Σ1 ∪ Σ2
Σ ϕ ¬ϕ
Σ0 �
Σ
Σ
Σ
Demostración. Σ
Σ
Σ
Σ
|Σ| = {|σ|∣∣σ ∈ Σ}
A U A |Σ|
A /U ∼= 2 fU
A A /U fU
Σ �
Σ Σ
Σ
Demostración. Σ
Σ
Σ
Σ �
B
k
k k
Demostración.
k ≤ m
k k
Demostración. m
m = 1
m < n n C
n
(i) k k+1
k < n
(ii) k < n S k
k
(i) n
n − 1 (n − 1) + 1 = n
n − 1
(ii)
S
l ≤ n− k l
C − S l
S T
l C−S l
S ∪T k+ l
k + l
C − S �
B = {bi|i ∈ I} G = {gj |j ∈ J}
B
L
{Pij |i ∈ I, j ∈ J} Σ
L
i ∈ I Pij0∨· · ·∨Pijk gj0 , . . . , gjk
bi
i ∈ I j, j′ J
¬(Pij ∧ Pij′)
j ∈ J i, i′ I
¬(Pij ∧ Pi′j)
Σ0 Σ Σ0
C bi j ∈ J
Pij Σ0 C
m
Pij bi gj
Σ0
f Σ bi gj
f(pij) = 1 Σ
Σ
�
Demostración. Q = {qi|i ∈ I} C =
{c0, c1, c2, c3} = {cj |j ∈ 4}
L
{Pij |i ∈ I, j ∈ 4} Σ
L
i ∈ I (Pi0 ∨ · · · ∨ Pi3)
i ∈ I j, j′ 4
¬(Pij ∧ Pij′)
j ∈ 4 ¬(Pij ∧ Pi′j) qi
qi′
Σ0 Σ Σ0
D qi j ∈ 4 Pij
Σ0 D
Pij qi
j Σ0
f Σ qi
cj f(pij) = 1 Σ
Σ �
(a)
{vn|n ∈ ω}
(b)
{Pn|n ∈ ω}
Pn δ(n)
Pn
(c)
(d)
¬ ∧
(e)
∃
(f)
( ) ,
x = y
x y
Pn(x1, . . . , xδ(n))
x1, . . . , xδ(n) δ(n)
ϕ,ψ x (¬ϕ), (ϕ ∧ ψ)
(∃x)ϕ
∨,→ ↔
ϕ ∨ ψ) ¬(¬ϕ ∧ ¬ψ)
ϕ→ ψ ¬(ϕ ∧ ¬ψ)
ϕ↔ ψ ((ϕ→ ψ) ∧ (ψ → ϕ))
∀
(∀x)ϕ ¬(∃x)¬ϕ
ϕ ψ x (ϕ∨ψ), (ϕ→ ψ), (ϕ↔
ψ) (∀x)ϕ
A = 〈A, {Rn|n ∈ ω}〉
A A n ∈ ω Rn
λ(n) A
A
Rn
Pn i.e. n ∈ ω δ(n) = λ(n)
A
A Rn Pn A
x < 22
x ϕ(v)
v
A v
A
x = 〈x0, x1, . . . , xn, . . . 〉
A x
x vn
xn A x a ∈ A x(n/a)
x
a vn
x(n/a) = 〈x0, x1, . . . , xn−1, a, xn+1, . . . 〉
vn x(n/a)
vn x
x
ϕ A A |=x ϕ
(a). A |=x vm = vn xm xn
(b). A |=x Pn(vi1 , . . . , viδ(n)) 〈xi1 , . . . , xiδ(n)〉 ∈ Rn
(c). A |=x ¬ϕ A |=x ϕ
(d). A |=x ϕ ∧ ψ A |=x ϕ A |=x ψ
(e). A |=x (∃vn)ϕ a ∈ A A |=(x/a) ϕ
ϕ A x, y
vn ϕ xn = yn
A |=x ϕ A |=y ϕ
A |= ϕ[x0, . . . , xn] A |=x ϕ
ϕ v0, . . . , vn
A |= ϕ[x0, . . . , xn] vi xi
i ≤ n ϕ A σ
A |=x σ x A |=x σ
x A |= σ σ
A A σ Σ
A Σ A
Σ A |= Σ
σ
ϕ→ (ψ → ϕ)
[ϕ→ (ψ → χ)]→ [(ϕ→ ψ)→ (ϕ→ χ)]
(¬ϕ→ ¬ψ)→ (ψ → ϕ)
(ϕ ∧ ψ)→ ϕ
(ϕ ∧ ψ)→ ψ
[χ→ ϕ]→ [(χ→ ψ)→ (χ→ [ϕ ∧ ψ])]
ϕ→ (ϕ ∨ ψ)
ψ → (ϕ ∨ ψ)
[ϕ→ χ]→ [(ψ → χ)→ ([ϕ ∨ ψ]→ χ)]
ϕ ψ χ
(∀x)ϕ(x)→ ϕ(y)
(∀x)(ϕ→ ψ)→ (ϕ→ (∀x)ψ)
x, y ψ
ϕ y x ϕ
x
(∀x)(x = x)
(∀x)(∀y)(x = y → [ϕ→ ϕ′])
x ϕ y
x ϕ′
x ϕ y
ψ ϕ (ϕ→ ψ)
ϕ ψ
(∀x)ϕ ϕ ϕ
x
→ [�]
ϕ Σ
ϕ1, . . . , ϕn ϕ = ϕn i ≤ n
ϕi Σ j, k < i
y x ϕ x ϕ
∀y ∃y
ϕj ϕk
ϕj j < i
Σ Σ
Σ � ϕ
ϕ deducible
∅ � ϕ
ϕ
� ϕ
Demostración.
B Γ
D1, . . . ,Dn Γ
Di B
Di B Di Γ
Di
B
C B Γ,B � C
Γ � C
Demostración.
D1, . . . ,Dn C Γ B C
B Dn = C )
n C Γ Γ � C
C
C B
B Γ
C �
Γ,B � C
Γ � B → C
Demostración. D1, . . . ,Dn C Γ B
Γ � B → Di i ≤ n Di
Γ Di → (B → Di)
Γ � B → Di Di
j k i Dk Dj → Di
Γ � B → Dj Γ � B → (Dj → Di)
Γ �
(
B → (Dj → Di)
)
→
(
(B → Dj)→ (B → Di)
)
Γ � B → Di j < i
Di (∀xk)Dj Γ � B → Dj
Dj B B
B Γ � Dj
xk D
Γ � (∀xk)Dj Γ � Di Γ � Di → (B → Di)
Γ � B → Di Dj B xk
B Dj ∀xkDj
B
B → Dj Γ � (∀xk)(B → Dj)
Γ � (∀xk)(B → Dj)→ (B → (∀xk)Dj) xk
B Γ � B → (∀xk)Dj
Γ � B → Di i = n �
Γ � B → C Γ � C
E
Γ Γ,B � C
E Dj E Γ
B → Dj E
Γ � D → (B → C ) Γ,D ,B � C
Ded ⊆ V al
Demostración.
�
ϕ
ϕ ¬ϕ
Demostración. ϕ ¬ϕ
ϕ ¬ϕ
�
Φ
� Φ
ϕ � ψ � ϕ→ ψ
�
ϕ,ψ
Φ
ϕ ∧ ψ � ψ ∧ ϕ ψ ∧ ϕ � ϕ ∧ ψ
ϕ∧ψ ψ∧ϕ
≡
Φ
ϕ ≡ ψ � ϕ→ ψ � ψ → ϕ
ϕ→ ϕ ≡
(ϕ → ψ) → [(ψ → χ) →
(ϕ→ χ)]
≡ Φ
ϕ ψ ϕ ≡ ϕ′ ψ ≡ ψ′
� ϕ→ ψ � ϕ′ → ψ′
Demostración. � ϕ′ → ψ′ �
ϕ → ψ
1. � (ψ → ψ′)→ [(ϕ→ ψ)→ (ϕ→ ψ′)]
2. � ψ → ψ′
3. � ϕ→ ψ
4. � (ϕ→ ψ)→ (ϕ→ ψ′)
5. � ϕ→ ψ′
6. � (ϕ→ ψ′)→ [(ϕ′ → ϕ)→ (ϕ′ → ψ′)]
7. � ϕ′ → ϕ
8. � (ϕ′ → ϕ)→ (ϕ′ → ψ′)
9. � ϕ′ → ψ′
�
ϕ Φ ϕ
ϕ
ϕ| = {ψ ∈ Φ∣∣ϕ ≡ ψ}
Φ/ ≡ {|ϕ|∣∣ϕ ∈ Φ}
≤ Φ/ ≡
|ϕ| ≤ |ψ| � ϕ→ ψ
Φ
A = 〈Φ/ ≡,≤〉
|ϕ| = 1 � ϕ |ϕ| = 0 � ¬ϕ
Demostración. ϕ → ϕ ≤
(ϕ → ψ) → [(ψ →
χ)→ (χ→ ψ)]
Φ/ ≡
{|ϕ|, |ψ|} Φ/ ≡
|ϕ ∧ ψ|
� (ϕ ∧ ψ)→ ϕ � (ϕ ∧ ψ)→ ψ
|ϕ∧ψ| ≤ |ϕ| |ϕ∧ψ| ≤ |ψ| |ϕ∧ψ|
{|ϕ|, |ψ|} |χ| {|ϕ|, |ψ|}
� χ → ϕ � χ → ψ � χ →
(ϕ∧ψ) |ϕ∧ψ|
{|ϕ|, |ψ|} |ϕ ∨ ψ|
{|ϕ|, |ψ|} A
[(ϕ∧χ)∨(ψ∧χ)]→ [(ϕ∨ψ)∧χ] [(ϕ∨ψ)∧χ]→ [(ϕ∧χ)∨(ψ∧χ)]
ϕ,ψ, χ
|(ϕ ∨ ψ) ∧ χ| = |(ϕ ∧ χ) ∨ (ψ ∧ χ)|
(|ϕ| ∨ |ψ|) ∧ |χ| = (|ϕ| ∧ |χ|) ∨ (|ψ| ∧ |χ|)
A
� ϕ ψ � ψ →
ϕ |ψ| ≤ |ϕ| |ϕ| = 1 A
¬ϕ → (ϕ → ψ) � ¬ϕ
ψ ϕ → ψ |ϕ| ≤ |ψ| |ϕ| = 0
|ϕ| = 1 ψ |ψ| ≤ |ϕ|
� ψ → ϕ ψ � ψ � ϕ
|ϕ| = 0 � ¬ϕ
ϕ
� ϕ ∨ ¬ϕ � ¬(ϕ ∧ ¬ϕ)
|ϕ| ∨ |¬ϕ| = 1 |ϕ| ∧ |¬ϕ| = 0A i.e.
�
Φ A
A
ϕ Φ ϕ(vk1/vp1 , . . . , vkn/vpn)
ϕ vpi vj+i
j p1, . . . , pn
ϕ
vki vpi 1 ≤ i ≤ n
ϕ
|(∀vk)ϕ| = inf{|ϕ(vk/vp)|
∣∣p ∈ ω}
Demostración.
� (∀vk)ϕ→ ϕ(vk/vp)
p ∈ ω
|(∀vk)ϕ| ≤ |ϕ(vk/vp)|
|(∀vk)ϕ| ≤ {|ϕ(vk/vp)
∣∣p ∈ ω}
ψ |ψ|
{|ϕ(vk/vp)|
∣∣p ∈ ω} q
vq ϕ ψ
� ψ → ϕ(vk/vq)
� ψ → (∀vq)ϕ(vk/vp)
� (∀vq)ϕ(vk/vq)→ ϕ
� (∀vq)ϕ(vk/vq)→ (∀vk)ϕ
� ψ → (∀vk)ϕ
|(∀vk)ϕ i.e. {|ϕ(vk/vp)
∣∣p ∈
ω} �
A
ϕ,ψ
(i) |¬ϕ| ∈ D ⇐⇒ |ϕ| /∈ D
(ii) |ϕ ∧ ψ| ∈ D ⇐⇒ |ϕ| ∈ D |ψ| ∈ D
(iii) |ϕ|, |ϕ→ ψ| ∈ D |ψ| ∈ D
Demostración. (i) |¬ϕ| ∈ D D
|¬ϕ|∗ ∈ D |¬ϕ|∗ = |¬¬ϕ| = |ϕ|
|ϕ| /∈ D |ϕ| /∈ D D
|ϕ|∗ ∈ D |ϕ|∗ = |¬ϕ| |¬ϕ| ∈ D
(ii) |ϕ∧ψ| ∈ D |ϕ∧ψ| ≤ |ϕ|
|ϕ∧ψ| ≤ |ψ| D |ϕ| ∈ D |ψ| ∈ D
|ϕ ∧ ψ| {|ϕ|, |ψ|}
D
(iii) |ϕ|, |ϕ→ ψ| ∈ D |ϕ→ ψ| =
|¬(ϕ ∧ ¬ψ)| (i) |ϕ ∧ ¬ψ| /∈ D
(ii) |ϕ| /∈ D |¬ψ| /∈ D |ϕ| ∈ D
|¬ψ| /∈ D (i) |ψ| ∈ D �
Demostración. σ
σ
σ
� σ |σ| �= 1
A |¬σ| �= 0
ϕ
|∀vkϕ| = {|ϕ(vk/vp)|
∣∣p ∈ ω} Π
A |¬σ|
Π |∀vkϕ| ∈ D
p ∈ ω |ϕ(vk/vp)| ∈ D
h : A → A /U.
A V
∼ V
vi ∼ vj |vi = vj | ∈ D
v ∈ V v∼ = {v′ ∈ V |v′ ∼ v} V ∼ = {v∼|v ∈ V }
V ∼ A V ∼
n ∈ ω Rn V ∼
〈w∼1 , . . . , w∼δ(n)〉 ∈ Rn |Pn(w1, . . . , wδ(n))| ∈ D
i.e. 1 ≤ i ≤ δ(n)
ui ∼ wi |P (u1, . . . , uδ(n))| ∈ D |P (w1, . . . , wδ(n))| ∈ D
A = 〈V ∼, {Rn|n ∈ ω}〉 x ∈ V ω x = 〈x0, . . . , xn, . . . 〉
x∼ ∈ (V ∼)ω 〈x∼0 , . . . , x∼n , . . . 〉 V ∼
ϕ(v0, . . . , vn)
v0, . . . vn x ∈ V ω
A |=x∼ ϕ |ϕ(v0/x0, . . . , vn/xn)| ∈ D. ∗
∗
ϕ
ϕ vi = vj
V ∼ ∗ ϕ
Pn(w1, . . . , wδ(n)) Rn
∗
μ ϕ μ
ϕ ¬ψ (ψ ∧ χ) ∃vnψ
ψ χ μ
∗ ϕ ¬ψ (ψ ∧ χ)
∗ ϕ
ϕ ∃vnψ ψ
v0, . . . , vn
A |=x∼ ϕ⇐⇒ v∼ ∈ V A |=x∼(n/v∼) ψ
⇐⇒ p ∈ ω A |=x∼(n/v∼p ) ψ
⇐⇒ p ∈ ω |ψ(v0/x0, . . . , vn−1/xn−1, vn/vp)| ∈ D
⇐⇒ p ∈ ω |¬ψ(v0/x0, . . . , vn−1/xn−1, vn)| ∈ D
⇐⇒ |∀vn¬ψ(v0/x0, . . . , vn−1/xn−1, vn)| ∈ D
B B/F
⇐⇒ |¬∀vn¬ψ(v0/x0, . . . , vn−1/xn−1, vn)| ∈ D
|∃vnψ(v0/x0, . . . , vn−1/xn−1, vn)| = |¬∀vn¬ψ(v0/x0, . . . ,
vn−1/xn−1, vn)| ∗ ϕ ∗
|¬σ| ∈ D A
¬σ σ
�
σ ¬σ
¬σ α
α
Demostración. σ ¬σ
σ
σ ¬σ |¬σ| �= 1
|σ| �= 0 σ
V V ∼
A σ �
Demostración. Σ = {σ1, . . . , σn}
Σ σ1∧· · ·∧σn
�
A = 〈A, {Rξ|ξ < α}〉 μ ∈ αω
α A μ
ξ < α Rξ μ(ξ) A i.e. Rξ ⊆ Aμ(ξ)
A μ
A
{Pξ|ξ < α} ξ < α δ(ξ)
Pξ μ(ξ)
μ
μ
A = 〈A, {Rξ|ξ < α}〉 B = 〈B, {Sξ|ξ < α}〉
μ A B
B B A A ⊆ B
A B A i.e.
ξ < α Rξ = Sξ ∩Aμ(ξ)
A B A ⊆ B
X B 〈X, {Sξ∩
Xμ(ξ)|ξ < α}〉 B B X
B �X
h : A → B h A B
ξ < α a1, . . . , aμ(ξ) ∈ A
〈a1, . . . , aμ(ξ)〉 ∈ Rξ 〈h(a1), . . . , h(aμ(ξ))〉 ∈ Sξ
Capítulo 4 
Teoría de Modelos 
4.1. N ociones básicas 
Sea 
definida en 
una estructura relacional y 
con valores en los naturales. Decimos que 
una función 
es de tipo si 
para cada es una relación -aria en 
Dada una estructura relacional , de tipo , un lenguaje apropiado para 
hablar de lo que pasa en es el lenguaje de predicados con el conjunto 
de letras predicativas, donde para cada , el grado 
(o aridad) de , es igual a . Este lenguaje nos servirá para hablar de 
cualquier estructura relacional de tipo . Se asume que cuando utilizamos 
el lenguaje para hacer afirmaciones acerca de una estructura relacional, el 
lenguaje es el apropiado para la estructura relacional en cuestión. En adelante 
consideraremos a todas las estructuras relacionales con tipo fijo, a menos 
que se indique lo contrario. 
Sean y dos estructuras 
relacionales de tipo . Decimos que es una subestructura de (o una 
subinterpretación de ) y que es una extensión de si y cada 
relación en es la restricción de la relación correspondiente de a 
para cada 
Si es una subestructura de lo denotaremos , en particular, a 
cada subconjunto no vacío de , le corresponde la subestructura 
de ; llamamos a esta subestructura la restricción de a 
y la denotamos 
Sea . Decimos que es un homomorfismo de en si para 
cada y cualesquiera 
si y sólo si 
Capítulo 4 
Teoría de Modelos 
4.1. N ociones básicas 
Sea 
definida en 
una estructura relacional y 
con valores en los naturales. Decimos que 
una función 
es de tipo si 
para cada es una relación -aria en 
Dada una estructura relacional , de tipo , un lenguaje apropiado para 
hablar de lo que pasa en es el lenguaje de predicados con el conjunto 
de letras predicativas, donde para cada , el grado 
(o aridad) de , es igual a . Este lenguaje nos servirá para hablar de 
cualquier estructura relacional de tipo . Se asume que cuando utilizamos 
el lenguaje para hacer afirmaciones acerca de una estructura relacional, el 
lenguaje es el apropiado para la estructura relacional en cuestión. En adelante 
consideraremos a todas las estructuras relacionales con tipo fijo, a menos 
que se indique lo contrario. 
Sean y dos estructuras 
relacionales de tipo . Decimos que es una subestructura de (o una 
subinterpretación de ) y que es una extensión de si y cada 
relación en es la restricción de la relación correspondiente de a 
para cada 
Si es una subestructura de lo denotaremos , en particular, a 
cada subconjunto no vaCÍo de , le corresponde la subestructura 
de ; llamamos a esta subestructura la restricción de a 
y la denotamos 
Sea . Decimos que es un homomorfismo de en si para 
cada y cualesquiera 
si y sólo si 
A ⊆ B A ⊆ B i : A → B
i(a) = a A B i
A B
h A B
A B �h(A) A B �h(A)
A B h
h A B
A B A B A ∼= B
∼= A ∼= B A
B
A
B A
B A B A ≡ B
≡
A ≡ B σ A |= σ
B |= σ
Demostración.
A � σ A |= ¬σ B |= ¬σ
B � σ
A,B
A ≡ B
Demostración. f : A→ B s ∈ ωA ϕ ∈ FORML
ϕ ∈
FORML A |=s ϕ B |=f◦s ϕ
ϕ vi = vj
A |=s ϕ ⇐⇒ A |=s vi = vj ⇐⇒ s(vi) = s(vj) ⇐⇒ f(s(vi)) = f(s(vj))
⇐⇒ f ◦ s(vi) = f ◦ s(vj)⇐⇒ B |=f◦s vi = vj ⇐⇒ B |=f◦s ϕ
ϕ Pi(v1, . . . , vn)
A |=s ϕ ⇐⇒ A |=s Pi(v1, . . . , vn) ⇐⇒ (s(v1), . . . , s(vn)) ∈ Ri ⇐⇒
(f(s(v1)), . . . , f(s(vn))) ∈ Si ⇐⇒ (f ◦ s(v1), . . . , f ◦
s(vn)) ∈ Si ⇐⇒ B |=f◦s Pi(v1, . . . , vn)⇐⇒ B |=f◦s ϕ
ψ χ A |=s ψ ⇐⇒ B |=f◦s ψ
A |=s χ⇐⇒ B |=f◦s χ
ϕ ψ ∨ χ
A |=s ϕ ⇐⇒ A |=s ψ ∨ χ ⇐⇒ A |=s ψ A |=s χ ⇐⇒ B |=f◦s ψ
B |=f◦s χ⇐⇒ B |=f◦s ψ ∨ χ⇐⇒ B |=f◦s ϕ
ϕ ¬ψ
A |=s ϕ ⇐⇒ A |=s ¬ψ ⇐⇒ A �s ψ ⇐⇒ B �f◦s⇐⇒ B |=f◦s ¬ψ ⇐⇒
B |=f◦s ϕ
ϕ ∃vnψ
A |=s ϕ ⇐⇒ A |=s ∃vnψ ⇐⇒ c ∈ A A |=s(n/c) ψ ⇐⇒
B |=f◦s(n/f(c)) ψ =⇒ B |=f◦s ∃vnψ ⇐⇒ B |=f◦s ϕ
B |=f◦s ϕ ⇐⇒ B |=f◦s ∃vnψ ⇐⇒ b ∈ B B |=f◦s(n/b) ψ
c = f−1(b) A |=s(n/c)
ψ ⇐⇒ A |=s ∃vnψ ⇐⇒ A |=s ϕ
f A |=s ϕ ⇐⇒ B |=f◦s ϕ
ϕ ϕ
A |= ϕ ⇐⇒ B |= ϕ A ≡ B �
A B
B A A � B A ⊆ B
ϕ x ∈ Aω
A |=x ϕ B |=x ϕ
A ⊆ B A � B
ϕ s ∈ ωA
B |=s ∃vnϕ c ∈ A B |=s(n/c) ϕ
Demostración. A � B B |=s ∃vnϕ A |=s
∃vnϕ A |=s(n/c) ϕ c ∈ A s(n/c) ∈ ωA
B |=s(n/c) ϕ
ϕ
s ∈ Aω B |=s ∃vnϕ c ∈ A B |=s(n/c) ϕ
A � B
ϕ s ∈ ωA A |=s ϕ
B |=s ϕ
ϕ
ϕ A ⊆ B
ψ χ
¬ψ ψ ∨ χ
ψ
∃vnψ A |=s ∃vnψ c ∈ A
A |=s(n/c) ψ B |=s(n/c) ψ
B |=s ∃vnψ B |=s ∃vnψ c ∈ A
B |=s(n/c) ψ A |=s(n/c) ψ
A |=s ∃vnψ �
A ⊆ B A � B ϕ(v0,
. . . , vn) v0, . . . , vn a0, . . . , an−1
A b ∈ B B |= ϕ[a0, . . . , an−1, b]
a ∈ A B |= ϕ[a0, . . . , an−1, a].
Demostración. �
A A
ā = 〈ak〉k<β A 〈A, ā〉
A
ā
〈A, ā〉
ā A
A
A
A B
f : A → B
A B
〈A, ā〉 ≡ 〈B, b̄〉 ∪ 〈ck〉k<β
ā = 〈ak〉k<β b̄
ā
�
A α β
ρ ≤ β ≤ α ρ
A B β
Demostración. < A
〈Bn|n ∈ ω〉 A
B0 β Bn+1
a ∈ A ϕ(v0, . . . , vn)
a0, . . . , an−1 ∈ Bn a a ∈ A A |= ϕ[a0, . . . , an−1, a]
a0 ∈ Bn a0 a ∈ A
A |= v0 = v1[a0, a] a0 ∈ Bn+1 Bn ⊆ Bn+1
ρ ρ ≤ β Bn
β B =
⋃
n∈ω Bn β B = A �B
B ⊆ A B � A
ϕ(v0, . . . , vn) a0, . . . an−1 ∈ B a ∈ A
A |= ϕ[a0, . . . , an−1, a] 0 ≤ i < n ai ∈ B
ni ∈ ω ai ∈ Bni m {ni|0 ≤ i < n}
a0, . . . , an−1 ∈ Bm {a ∈ A|A |= ϕ[a0, . . . an−1, a]}
b b ∈ Bm+1 ⊆ B
b ∈ B A |= ϕ[a0, . . . an−1, b]
B � A �
�
Σ α
β ≥ α Σ
γ α ≤ γ ≤ β
Demostración. δ = max{ℵ0, α} δ
Σ Σ
′ δ A Σ β ≥ α
′ A′
β Σ γ α ≤ γ ≤ β
δ ≤ γ, β A′
B′ γ
Σ γ
ℵ0
′
B′
Σ B
γ Σ �
A
α A β ≥ α, ρ ρ
Demostración. β ≥ α, ρ a ∈ Aα A Lα
〈cξ|ξ < α〉
Lα+β Lα 〈dξ|ξ < β〉
Δ Lα
〈A, a〉 Γ = {¬(dξ = dζ)|ξ < ζ < β}
Δ ∪ Γ
Γ0
Γ Δ ∪ Γ0 Γ0
Γ dξ1 , . . . , dξn Γ0
a′1, . . . , a′n n A
A a′′ Aα+β
a′′ξ = aξ ξ < α
a′′ξ = a
′
i ξ = α+ ξi 1 ≤ i ≤ n
a′′ξ
a′i 〈A, a′′〉 Δ ∪ Γ0 dξ
a′′ξ Δ ∪ Γ
Δ ∪ Γ
dξ
Δ∪Γ ≥ β �
Δ∪Γ 〈B, b〉 β Δ
Lα 〈A, a〉 〈A, a〉 ≡
〈B, b′〉 b′ = b �α b′ α
b a A A
B B
A β
�
Σ α Σ
β ≥ ℵ0 Σ ≥ α, β �
Demostración. �
Σ
Σ Σ
Σ α Σ
≥ α
Demostración. � � �
Observación. � �
P0
μ0 = {(0, 2)}
I I
I 〈P(I),⊆〉
i ∈ I Ai = 〈Ai, Ri〉μ0
∏
i∈I Ai = A Ai
i ∈ I i.e.∏
i∈I Ai =
∏
Ai
∏
Ai f, g, f
′, g′
f ∈ A f(i) fi
F ∼F
A
f ∼F g {i ∈ I|fi = gi} ∈ F
∼F
∼F |Ai| ≥ 3 Ai
Demostración. i) F I I ∈ F ∼F
∼F
f ∼F g g ∼F h
X = {i ∈ I|fi = gi} ∈ F
Y = {i ∈ I|gi = hi} ∈ F
X ∩ Y ∈ F X ∩ Y ⊆ Z = {i ∈
I|fi = hi} F Z ∈ F f ∼F h ∼F
ii) ai, bi, ci ∈ Ai ai �= bi bi �= ci ci �= ai
N,M ∈ F N ∩M ∈ F
f, g, h ∈ A
fi =
⎧⎨
⎩
ai i ∈ N
bi i ∈M −N
ci i ∈ I − (M ∪N)
gi =
⎧⎨
⎩
ai i ∈ N
bi i ∈ I − (M ∪N)
ci i ∈M −N
hi =
⎧⎨
⎩
ai i ∈ I − (M �N)
bi i ∈ N −M
ci i ∈M −N
N ∈ F {i ∈ I|fi = gi} = N M ∈ F {i ∈ I|gi = hi} = M
f ∼F g g ∼F h ∼F
f ∼F h {i ∈ I|fi =
hi} ∈ F {i ∈ I|fi = hi} = M ∩N M ∩N ∈ F
M ∈ F M ⊆ D
D ⊆ I D ∈ F
F
f, g, h ∈ A
fi =
{
ai i ∈M
ci i ∈ I −M
gi =
{
ai i ∈M ∪ (I −D)
bi i ∈ D −M
hi =
⎧⎨
⎩
ai i ∈M
bi i ∈ I −D
ci i ∈ D −M
M = {i ∈ I|fi = gi} = {i ∈ I|gi = hi} M ∈ F
f ∼F g g ∼F h
∼F {i ∈ I|fi = hi} = D ∈ F F
�
F I
f ∼F g f g
S
A Ri
〈f, g〉 ∈ S {i ∈ I|〈fi, gi〉 ∈ Ri} ∈ F
∼F Ri
Ai A
∼F S
∼F f ∼F f ′
g ∼F g′ 〈f, g〉 ∈ S 〈f ′, g′〉 ∈ S
Demostración. f, f ′, g, g′ ∈ A f ∼F f ′ g ∼F g′
X = {i ∈ I|fi = f ′i} Y = {i ∈ I|gi = g′i} X,Y ∈ F
〈f, g〉 ∈ S Z = {i ∈ I|〈fi, gi〉 ∈ Ri} ∈ F F
X ∩ Y ∩ Z ∈ F X ∩ Y ∩ Z ⊆ W = {i ∈ I|〈f ′i , g′i〉 ∈ Ri}
W ∈ F 〈f ′, g′〉 ∈ S �
f ∈ A f/F
f ∼F A/F
A i.e. A/F = {f/F |f ∈ A}
S A RF A/F
〈f/F, g/F 〉 ∈ RF 〈f, g〉 ∈ S
∏
Ai/F 〈
∏
Ai/F,RF 〉
= 〈A/F,RF 〉
∏
Ai/F {Ai|i ∈
I} F F ∏ Ai/F
i ∈ I Ai = A AI/F
A F F AI/F
A
{Ai|i ∈ I}
F I∏
Ai/F Ai∏
Ai/F
f = 〈f1, . . . , fn, . . . 〉
∏
Ai i.e f ∈ Aω
f/F f/F = 〈f1/F, . . . , fn/F, . . . 〉 A/F
f/F ∈ (A/F )ω 〈f1(i), . . . , fn(i), . . . 〉 Ai
fi
ϕ f/F ∈ (A/F )ω∏
Ai/F |=f/F ϕ {i ∈ I|Ai |=fi ϕ} ∈ F
Demostración.
ϕ
ϕ vm = vn∏
Ai/F |=f/F vm = vn fm/F = fn/F
fm ∼F fn {i ∈ I|fm(i) = fn(i)} ∈ F {i ∈ I|Ai |=fi
vm = vn} ∈ F
ϕ P0(vm, vn)
r ϕ r
i) ϕ ψ ∧ χ Dψ = {i ∈ I|Ai |=fi ψ} Dχ = {i ∈
I|Ai |=fi χ} Dψ ∩Dχ = {i ∈ I|Ai |=fi ψ ∧ χ}∏
Ai/F |=f/F ψ ∧ χ ⇔
∏
Ai/F |=f/F ψ
∏
Ai/F |=f/F χ ⇔
Dψ, Dχ ∈ F ⇔ Dψ ∩Dχ ∈ F
ψ χ
r F
ψ ∧ χ
ii) ϕ ¬ψ∏
Ai/F |=f/F ¬ψ
∏
Ai/F |=f/F ψ
{i ∈ I|Ai |=fi ψ} /∈ F I − {i ∈ I|Ai |=fi ψ} ∈ F
{i ∈ I|Ai �fi ψ} ∈ F {i ∈ I|Ai |=fi ¬ψ} ∈ F
{i ∈ I|Ai |=fi ψ}
F
iii) ϕ ∃vnψ D = {i ∈ I|Ai |=fi ∃vnψ}∏
Ai/F |=f/F ∃vnψ D ∈ F∏
Ai/F |=f/F ∃vnψ b ∈ A∏
Ai/F |=f(n/b)/F ψ E = {i ∈ I|Ai |=f(n/b)(i) ψ}
E ∈ F f(n/b)(i) =
f(i)(n/bi) E ⊆ D F
D ∈ F
D ∈ F i ∈ D Ai |=fi ∃vnψ
bi Ai Ai |=f(i)(n/bi) ψ
c ∈∏Ai ci = bi
i ∈ D Ai D ⊆ {i ∈ I|Ai |=f(n/c)(i) ψ} = C
C ∈ F ∏ Ai/F |=f(n/c)/F ψ∏
Ai/F |=f/F ∃vnψ
∏
Ai/F |=f/F ϕ
�
σ
∏
Ai/F |= σ ⇐⇒ {i ∈ I|Ai |= σ} ∈ F
�
Σ
Σ
Demostración. Σ
Σ Σ
Σ
Σ
Σ
I = [Σ]<ω Σ
Δ ∈ I AΔ
Δ ∈ I Δ∗ = {Δ′ ∈ I|Δ ⊆ Δ′} Δ ∈ Δ∗
Δ∗
{Δ1, . . . ,Δn} I Δ1 ∪ · · · ∪Δn ∈ Δ∗1 ∩ · · · ∩Δ∗n
{Δ∗|Δ ∈ I}
F I
∏
Δ∈I AΔ/F
Σ
σ ∈ Σ {σ} ∈ I {σ} = Δ0
AΔ0 |= σ AΔ′ |= σ Δ0 ⊆ Δ′
Δ∗0 = {Δ′ ∈ I|Δ0 ⊆ Δ′} ⊆ {Δ′ ∈ I|AΔ′ |= σ} Δ∗0 ∈ F {Δ′ ∈
I|AΔ′ |= σ} ∈ F
∏
AΔ/F |= σ �
Σ
Demostración. Σ
Σ
Σ
Σ �
Taut V al
SF Φ
A SF
Δ
Δ
A A ⊆ A
A ⊆ Φ/ ∼�
(Ac)0
∅ /∈ (Ac)0
|ϕ| ∈ (Ac)0 ψ ϕ → ψ
|ψ| ∈ (Ac)0 (Ac)0
A T
A
F A
T
T = {ϕ∣∣|ϕ| ∈ F}
(Ac)0
(Ac)0 F
F
ϕ ∈ Φ |ϕ|
ϕ Σ ⊆ Φ
|Σ| = {|ϕ|∣∣ϕ ∈ Σ} |Σ|
A Σ ϕ1, . . . , ϕn ∈
Σ {ϕ1, . . . , ϕn} ϕ1 ∧ · · · ∧ ϕn
|ϕ1| ∧ · · · ∧ |ϕn| �= 0
Σ
|Σ| A
T |T|
A
Demostración. T
|T| ϕ,ψ ∈ T
ϕ ∧ ψ ∈ T ϕ,ϕ → ψ ∈ T ψ ∈ T
T �
A
A T = {ϕ∣∣|ϕ| ∈ F} T
|T|
Demostración. F = |T| T
|T| = F
F T 	 ϕ ϕ ∈
T T 	 ϕ Δ ⊆ T Δ = {δ1, . . . δn} Δ 	 ϕ
F |δ1| ∧ · · · ∧ |δn| ∈ F Δ 	 ϕ |δ1| ∧ · · · ∧ |δn| ≤ ϕ
|ϕ| ∈ F ϕ ∈ T T
�
T
|T| ϕ ∈ Φ |ϕ| ∈ |T| |ϕ|∗ =
|¬ϕ| ∈ |T| |T| A |T|
A T
ϕ ∈ Φ ϕ ∈ T ¬ϕ ∈ T i.e. T
T |T|
A
Demostración. �
T
Γ Γ T
B
Demostración. F
X = {x1, . . . , xn} a =
∧n
i=1 xi F = {b ∈ B|a ≤ b} �
T
Γ |T|
|Γ| A
F A A
T = {ϕ∣∣|ϕ| ∈ F}
Γ = f [A] f
A
Demostración. |T| |Γ|
T |ϕ| ∈ |T| ϕ ∈ T
Γ 	 ϕ |∧ψ∈Γ ψ| ≤ |ϕ|
Γ
|T| ϕ ∈ T
(A) = a ≤ |ϕ| a
	 a → ϕ Γ 	 ϕ
Demostración. B SF
{Pb|b ∈ B} = P Δ
Pb ←→ Pc ∧ Pd b, c, d ∈ B b = c ∧ d
Pb ←→ Pc ∨ Pd b, c, d ∈ B b = c ∨ d
Pb ←→ ¬Pc b, c,∈ B b = c∗
P1
¬P0
A (Δ) Δ
D B v D
v(Pb)
{
0 b /∈ D
1 b ∈ D
v Δ
(i) b �= c Δ � Pb ←→ Pc b �= c
Δ ∪ {¬(Pb ←→ Pc)}
(ii) ϕ b ∈ B
Δ 	 (ϕ←→ Pb)
h : B → A (Δ)
h(b) = |Pb|
(i) h (ii)
Σ h e.g. h ∧
b, c, d ∈ B b = c ∧ d h(b) = h(c) ∧ h(d)
|Pb| = |Pc| ∧ |Pd| Σ 	 (Pb ←→ Pc ∧ Pd) Pb ←→ Pc ∧ Pd
Σ
B ∼= A (Δ) �
x ∈ B
x �= 0 y y ≤ x y = 0
y = x
x B x x
B
Demostración. F a a
b ∈ B a � b 0 �= (a∧b∗)
a ≤ b∗ (a ∧ b∗) ≤ a a
a ∧ b∗ = a
F b ∈ B 0 < b < a b /∈
F b F
F b ∈ B
0 < b < a a �
A
A
T
T ϕ T
ψ ψ → ϕ |ψ| = 0 	 ϕ→ ψ
�
T
T |T|
A
T |T|
A
�
�
A SFL
Φ/ ∼� ∼�
SF
A
Φ/ ∼�
A C
〈P(I),⊆〉 C
P(I) I
I U
U C
C A C
A
SF
C c ∈ C c �= ∅ c ∈ U
C
c∗ ∈ C U c∗ ∈ U C
U �
{0, 1}
{0, 1}
Demostración. X = {a ∈ A|h(a) = 1} X A
A B
D B X ⊆ D g
B {0, 1} D b ∈ B
g(b)
{
0 b /∈ D
1 b ∈ D
X ⊆ D (A−X)∩D = ∅ a ∈ A−X, a∗ ∈ X g
h
A {0, 1}
SF
P ′
f ′ SF ′ f ′
SF
A
Demostracion. A B F A = F ∪ I
I F F A h
A {0, 1} F g h
B {0, 1}
D = {b ∈ B|h(b) = 1} B �
Σ
Σ Σ
Demostración. (1) ⇒ (2) F
B B/F
U h B B/F
h−1[U ] B F
a, b ∈ h−1[U ] ⇒ h(a), h(b) ∈ U ⇒ h(a) ∧ h(b) ∈ U U
h h(a ∧ b) ∈ U ∴ a ∧ b ∈ h−1[U ]
a ∈ h−1[U ] c ∈ B a ≤ c ⇒ h(a) ≤ h(c) h
h(c) ∈ U U c ∈ h−1[U ]
a ∈ B a /∈ h−1[U ] h(a) /∈ U h(a)∗ ∈ U
h h(a∗) ∈ U ∴ a∗ ∈ h−1[U ]
a ∈ F h(a) = |1| h(a) ∈ U
a ∈ h−1[U ] ∴ F ⊆ h−1[U ]
(2) ⇒ (3) Σ
∗
F 1
∗ = ∪ {cϕ|ϕ ∈ F 1}
ϕ ∈ F ϕ∗ := (∃x)ϕ(x) → ϕ(cϕ)
Σ∗ = Σ ∪ {ϕ∗|ϕ ∈ F}
Σ
Σ∗ ∗
B ∗ ϕ ∈ L∗ ϕ
ϕ i.e. |ϕ| = {ψ| 	L ϕ ↔ ψ} Σ
Σ∗ Σ∗| = {|ϕ∗| : ϕ∗ ∈ Σ∗}
Σ∗ B
F B
A ∗
A ∗
n−
P [τ1, . . . τn] A |P (τ1, . . . , τn)| ∈ F
A
Σ∗ A Σ∗
Σ Σ A A
Σ
A A′
A′ Σ
(3)⇒ (4) Σ
Σ Σ
(4)⇒ (1) B
B
B Σ1
B B
B Σ2
+ B U
Σ3
U
|Σ∗| |Γ| ⊆ |Σ∗|
(|Γ|) = 0 |ψ|∈|Γ| |ψ| = 0
0 = |ϕ ∧ ¬ϕ| |Σ∗|
P 31 P
2
1 P
1
1
∀x∀y∀z U(x) ∧ U(y) ∧ P 31 (x, y, z) → U(z)
∀x∀y∀z∀w U(x) ∧ P 21 (y, z) ∧ P 11 (w) ∧ P 31 (x, z, w) → U(y)
∀x∀y P 21 (x, y) → U(x) ∨ U(y)
Σ = Σ1 ∪ Σ2 ∪ Σ3 Σ0
Σ A0 B
Σ0 A
B A0 A
A a
A0 (A, F, a) Σ0 Σ B′
UB
′
U B′ Σ1
B ∴ UB′ ∩B B �
∀x P 11 (x) → ¬U(x)
Σ Σ
Σ
Demostración. Σ
Σ
Σ
Σ
n < ω fn : {pi|i < n} → 2 fn (∗)
Σ0 Σ
Σ0 fn {pi|i < n}
n = 0 Σ
n fn
{pi|i ≤ n}
Σ
f0 = ∅
fn+1 =
{
fn ∪ {(pn, 0)} fn ∪ {(pn, 0)} (∗)
fn ∪ {(pn, 1)}
(∗) fn+1(pn) = 0
Σ0 Σ
fn+1 {pi|i < n} pn 0
Σ1 Σ Σ2 = Σ0∪Σ1
Apéndice A 
Apéndice 
A.l. Teorema de Compacidad para SC. 
Sea un conjunto de fórmulas de se. Entonces es satisfacible si y 
solamente si cada subconjunto finito de es satisfacible. 
Si es satisfacible, entonces existe una asignación que 
hace verdaderas a todas las fórmulas que pertenecen a , así, todas las 
fórmulas de cualquier subconjunto finito de serán satisfechas por esa misma 
asignación. 
Supongamos ahora que cada subconjunto finito de es satisfacible. Sea 
y . Diremos que cumple la propiedad 
si para cada subconjunto finito de existe una valuación que satisface 
y es compatible con en el conjunto , observemos que para 
el caso simplemente tenemos que cada subconjunto finito de es 
satisfacible. Mostraremos por recursión sobre que puede extenderse al 
conjunto de tal manera que esta propiedad se siga cumpliendo, 
esto con la finalidad de definir una valuación de se que satisfaga a 
Sea 
si 
si no 
Supongamos que la propiedad 
tonces existir un subconjunto finito 
valuación compatible con en 
cumple la propiedad 
no se cumple si . Debe en-
de que no es satisfecho por ninguna 
para la cual tome el valor . 
Sea un subconjunto finito de , entonces es un subconjunto 
Apéndice A 
Apéndice 
A.l. Teorema de Compacidad para SC. 
Sea un conjunto de fórmulas de se. Entonces es satisfacible si y 
solamente si cada subconjunto finito de es satisfacible. 
Si es satisfacible, entonces existe una asignación que 
hace verdaderas a todas las fórmulas que pertenecen a , así, todas las 
fórmulas de cualquier subconjunto finito de serán satisfechas por esa misma 
asignación. 
Supongamos ahora que cada subconjunto finito de es satisfacible. Sea 
y . Diremos que cumple la propiedad 
si para cada subconjunto finito de existe una valuación que satisface 
y es compatible con en el conjunto , observemos que para 
el caso simplemente tenemos que cadasubconjunto finito de es 
satisfacible. Mostraremos por recursión sobre que puede extenderse al 
conjunto de tal manera que esta propiedad se siga cumpliendo, 
esto con la finalidad de definir una valuación de se que satisfaga a 
Sea 
si 
si no 
Supongamos que la propiedad 
tonces existir un subconjunto finito 
valuación compatible con en 
cumple la propiedad 
no se cumple si . Debe en-
de que no es satisfecho por ninguna 
para la cual tome el valor . 
Sea un subconjunto finito de , entonces es un subconjunto 
Σ fn
{pi|i < n} Σ0
pn Σ1
fn {pi|i < n} pn Σ1
Σ
fn ∪{(pn, 0)} (∗)
fn ∪{(pn, 1)} fn
{pi|i ≤ n} (∗)
F =
⋃ {fn|n ∈ ω} F
Σ ϕ ∈ Σ n
ϕ
{pi|i < n} {ϕ} Σ {ϕ}
F {pi|i < n}
ϕ {pi|i < n} F
ϕ �
∗
〈cξ, ξ < β〉
{fn|n ∈ ω}
fn
γ(n) fn
∗
〈A, {Rn|n ∈
ω}, {Fn|n ∈ ω}, {aξ|ξ ∈ β}〉 〈A, {Rn|n ∈ ω}〉
n ∈ ω Fn γ(n)− a = {aξ|ξ ∈ β}
β A i.e. a ∈ Aβ
n+ 1 n
+
{Cξ|ξ ∈ β}
{Dn|n ∈ ω} Dn
η(n) = γ(n) + 1
〈A, {Rn|n ∈ ω}, {Fn|n ∈ ω}, a〉 ∗
〈A, {Rn|n ∈ ω}, {Sn|n ∈ ω}, {Tξ|ξ ∈ β}〉
+ Sn = {(a1, . . . , aγ(n), Fn(a1, . . . , aγ(n)))|a1, . . . , aγ(n) ∈
A} Tξ = {aξ} ξ < β
∃!xTξ(x) ξ < β
(∀x1) . . . (∀xγ(n))(∃!z)Sn(x1, . . . , xγ(n), z) n ∈ ω
∗ +
ϕ(f(t1, . . . , tn), c, w) ∗ ϕ+
ϕ+ = (∀x)(∀y)
(
Pf (t1, . . . , tn, x) ∧ Pc(y)→ ϕ(x, y, w)
)
Pf Pc f
c t1, . . . , tn
x, y, w
ϕ+ +
f
1)
2) τ1, . . . τn
τ1, . . . , τn
3)
∗ ϕ ∗
+
Σ
∗ = ∪ {cϕ|ϕ ∈ F 1}
ϕ ∈ F ϕ∗ := (∃x)ϕ(x) → ϕ(cϕ)
Σ∗ = Σ ∪ {ϕ∗|ϕ ∈ F}
Σ
Σ∗ = {ϕ∗|ϕ ∈ Σ} ∗
Σ ∪ A
A ⊆ {ϕ∗|ϕ ∈ F} |A|
|A| A = ∅ Σ
Σ′ = Σ ∪ {ϕ∗0, . . . , ϕ∗n−1}
Σ∪{ϕ∗0, . . . , ϕ∗n} Σ′∪{ϕ∗n}
Σ′ � ¬ϕ∗n
ϕ∗n Σ′ � ¬((∃x)ϕn(x)→ ϕn(cϕn)) Σ′ � ((∃x)ϕn(x) ∧
¬ϕn(cϕn)) Σ′ � ¬ϕn(cϕn)
¬ϕn(cϕn)
Σ′ cϕn x
¬ϕn(x) Σ′
ψ0, . . . , ψk ¬ϕn(cϕn) Σ′ i ∈ {0, . . . , k}
ψi(cϕn) ψi(x)
ψi(cϕn) cϕn
Σ′
h, i, j ∈ {0, . . . , k} j, h ≤ i
ψi ψj ψh
ψ′i ψi
cϕn x ψ
′
j ψ
′
h
ψ′i ψ
′
j ψ
′
h
¬ϕn(x) Σ
x
Σ′ ψi(cϕn)
¬ϕn(x)
(∀x)¬ϕn(x)
Σ′ � (∀x)¬ϕn(x) ∧ (∃x)ϕn(x)
Σ′ Σ ∪
{ϕ∗0, . . . , ϕ∗n} �
&
Bibliografía 
[1] Amor, J. A. "Un refinamiento del concepto de sistema axiomático" en 
Signos Filosóficos, vol. VI, núm, 11, enero-junio 2004, pp. 121-140 
[2] Amor, J. A. Compacidad en la lógica de primer orden y su relación con 
el teorema de completud, Las prensas de Ciencias, 1999. 
[3] Bell, J. L. Y Slomson, A. B. Models and Ultraproducts: An Introduction, 
North Holland Publishing Company, 1974. 
[4] Enderton, H. B. A Mathematical Introduction to Logic, Harcourt Aca-
demic Press, Second Edition, 2001. 
[5] Enderton, H. B. Una introducción Matemática a la Lógica, IIF-UNAM, 
2005. 
[6] Jané, 1. Álgebras de Boole y Lógica, Universitat de Barcelona Publica-
cions, 1989. 
[7] Manzano, M. Teoría de modelos, Alianza Universidad Textos, 1989. 
[8] Mendelson, E. Introduction to Mathematical Logic, Fourth Edition, 
Chapman Hall/CRC, 1997. 
Bibliografía 
[1] Amor, J. A. "Un refinamiento del concepto de sistema axiomático" en 
Signos Filosóficos, vol. VI, núm, 11, enero-junio 2004, pp. 121-140 
[2] Amor, J. A. Compacidad en la lógica de primer orden y su relación con 
el teorema de completud, Las prensas de Ciencias, 1999. 
[3] Bell, J. L. Y Slomson, A. B. Models and Ultraproducts: An Introduction, 
North Holland Publishing Company, 1974. 
[4] Enderton, H. B. A Mathematical Introduction to Logic, Harcourt Aca-
demic Press, Second Edition, 2001. 
[5] Enderton, H. B. Una introducción Matemática a la Lógica, IIF-UNAM, 
2005. 
[6] Jané, 1. Álgebras de Boole y Lógica, Universitat de Barcelona Publica-
cions, 1989. 
[7] Manzano, M. Teoría de modelos, Alianza Universidad Textos, 1989. 
[8] Mendelson, E. Introduction to Mathematical Logic, Fourth Edition, 
Chapman Hall/CRC, 1997. 
	Portada 
	Índice General 
	Introducción
	Capítulo 1. Álgebras de Boole 
	Capítulo 2. Álgebras de Lindenbaum
	Capítulo 3. Lógica Proposicional y Lógica de Predicados
	Capítulo 4. Teoría de Modelos
	Capítulo 5. Filtros Teorías
	Apéndice
	Bibliografía