Compacidad en la Lógica de Primer Orden y su Relación con el Teorema de la Completud - José Alfredo Amor Montaño - Manu FI

Vista previa del material en texto

JOSÉ ALFREDO AMOR MONTAÑO 
 
 
 
 
 
 
 
 
 
 
 
 
COMPACIDAD EN LA LÓGICA DE 
PRIMER ORDEN Y SU RELACIÓN 
CON EL TEOREMA DE COMPLETUD 
 
 
 
 
 
 
 
 
 
 
 
 
FACULTAD DE CIENCIAS, UNAM 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Compacidad en la lógica de primer orden 
y su relación con el Teorema de Completud 
2ª edición, 2006 
3ª edición, 2013 
 
Diseño de portada: Laura Uribe 
 
 © D. R. Universidad Nacional Autónoma de México 
Facultad de Ciencias 
Circuito exterior s/n. Ciudad Universitaria 
México 04510, D. F. 
editoriales@ciencias.unam.mx 
 
 
ISBN 10: 968-36-7540-9 
ISBN 13: 978-968-36-7540-8 
 
Impreso y hecho en México 
iii
La formalidad rigurosa de la sintaxis
sólo tiene sentido cuando detrás de ella
se encuentra la riqueza creativa de la semántica.
Prefacio
La lógica matemática es una rama más de la matemática moderna, que en
el siglo veinte se desarrolló de una manera sorprendente y está integrada
por cuatro areas: Teorı́a de Modelos, Teorı́a de Conjuntos, Teorı́a de la Recursión
y Teorı́a de la Demostración.
Inicialmente la lógica matemática puede considerarse como un modelo
matemático del razonamiento correcto que al desarrollarse y nutrirse de
la teorı́a intuitiva de los conjuntos y del álgebra universal, dio origen a la
teorı́a de modelos. El Teorema de Compacidad junto con el Teorema de
Completud son la puerta de entrada a la Teorı́a de los Modelos.
Compacidad, etimológicamente significa “calidad de compacto”. En la
lógica matemática significa “la existencia de un modelo para cualquier con-
junto infinito de enunciados cuyos subconjuntos finitos tengan modelo”.
Este poderoso teorema de enormes aplicaciones en la teorı́a de modelos
y en muy diversas ramas de la matemática, puede considerarse, desde el
punto de vista semántico como el teorema fundamental de la lógica ma-
temática. Desde un punto de vista sintáctico tal consideración serı́a para
el Teorema de Completud de Gödel.
El objetivo central de este libro es el estudio del Teorema de Compaci-
dad, sus aplicaciones y su relación con el Teorema de Completud.
El texto puede considerarse como una monografı́a sobre el Teorema de
Compacidad en la Lógica de Primer Orden y su relación con el Teorema
de Completud de Gödel.
En el primer capı́tulo se presentan algunos antecedentes, los conceptos
necesarios y los resultados preliminares. Después, algunas equivalencias
del teorema, su prueba, sus limitaciones y su relación con compacidad
en topologı́a. En el capı́tulo 2 se presentan algunos corolarios y varias
aplicaciones muy interesantes de compacidad en diversas ramas de la ma-
temática, como son el problema de los cuatro colores para mapas infinitos, el lema
de König para árboles infinitos, un modelo no-estandar para la aritmética
v
vi PREFACIO
de los números naturales y un modelo para los números infinitesimales.
Finalmente, en el tercer capı́tulo se presentan algunos resultados de tipo
semántico sobre formas normales de Skolem, los Teoremas de Skolem y
de Herbrand, que permiten dar una demostración semántica del Teorema
de Completud de Gödel en su forma restringida o débil, el cual afirma la
existencia de un sistema formal correcto y completo para la validez univer-
sal. Aquı́ se hace un análisis de los conceptos esenciales relacionados con
sistemas axiomáticos. Finalmente se presenta una prueba semántica para
el Teorema de Completud Extendido de Gödel, el cual afirma la existencia
de un sistema formal correcto y completo para la consecuencia lógica.
Se presenta al final un apéndice con la demostración sintáctica del
Teorema de Completud Extendido, realizada en forma análoga a la de-
mostración semántica del Teorema de Compacidad del capı́tulo primero,
sustituyendo el concepto “S-consistente” (consistencia relativa al sistema
formal S) en lugar del concepto “finitamente satisfacible” (existencia de
un modelo para cada subconjunto finito). De este modo queda explı́cita la
analogı́a entre los dos teoremas.
Aunque el objetivo central es el estudio de la compacidad en la lógica
de primer orden, hay otros objetivos secundarios, pero muy interesan-
tes, como la relación del concepto algebraico de isomorfismo y el con-
cepto lógico de verdad en estructuras algebraico-relacionales, de la cual se
presentan el Teorema del Homomorfismo y varios corolarios interesantes
como: isomorfismo entre estructuras implica equivalencia elemental entre
ellas, Lowenheim-Skolem para la lógica sin identidad, y el hecho de que
la relación de identidad no es axiomatizable o axiomáticamente definible.
Quiero dedicar este libro a mis maestros de lógica matemática: Dr.
Ignacio Jané y Dra. Susana Berestovoy. Agradezco al maestro Francisco
Zubieta Russi por sus enseñanzas; al maestro Gonzalo Zubieta Russi y al
Dr. Raúl Orayen por escucharme y orientarme siempre en mi investigación.
Quiero agradecer también a mis compañeros, los maestros Carlos
Torres, Rafael Rojas, Yolanda Torres, Asunción Preisser y Lourdes Guerre-
ro, ya que juntos iniciamos de modo autodidacta el camino fascinante de
la lógica matemática y juntos hemos descubierto muchas de sus facetas y
sorpresas.
Agradezco a todos mis alumnos de mis cursos de lógica matemática
en la Facultad de Ciencias y en la UAM Iztapalapa de quienes también
yo he aprendido. Un agradecimiento especial merece el Dr. Diego Rojas
Rebolledo por el trabajo de edición de texto en LATEX, ası́ como por sus
vii
valiosas sugerencias.
Para la presente segunda edición (corregida y aumentada) de este li-
bro, conté con los valiosos comentarios y sugerencias del Dr. David Meza
Alcántara a quien agradezco la cuidadosa revisión de una versión prelimi-
nar, lo que ayudo mucho a mejorar el nuevo texto.
En la elaboración en LATEX agradezco la colaboración de Héctor Miguel
Cejudo Camacho quien corrigió las erratas de la edición anterior y capturó
las muchas modificaciones, siendo las principales el complemento sobre
consecuencia lógica de Capı́tulo 1, ası́ como los importantes cambios rea-
lizados en el Capı́tulo 3 donde presento la prueba semántica del Teorema
de Correctud-Completud Extendido de Gödel.
Espero que este libro sea útil como texto para los cursos de lógica
matemática en las escuelas y facultades de ciencias y logre motivar a los
lectores a seguir avanzando en este tema.
José Alfredo Amor.
Contenido
Prefacio v
Introducción xi
1 El Teorema de Compacidad para la Lógica de Primer Orden 1
1.1 Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Conceptos y resultados preliminares . . . . . . . . . . 1
1.1.2 Consecuencia lógica . . . . . . . . . . . . . . . . . . . 17
1.1.3 Relaciones entre estructuras . . . . . . . . . . . . . . . 20
1.2 Equivalencias del Teorema de Compacidad . . . . . . . . . . 29
1.3 Prueba del Teorema de Compacidad . . . . . . . . . . . . . . 32
1.3.1 El Teorema de Compacidad . . . . . . . . . . . . . . . 32
1.3.2 Limitaciones del Teorema de Compacidad . . . . . . 40
1.4 ¿Por qué el Teorema de Compacidad en la lógica de primer
orden, se llama “de compacidad”? . . . . . . . . . . . . . . . 42
2 Aplicaciones del Teorema de Compacidad 49
2.1 El Teorema de Lowenheim-Skolem . . . . . . . . . . . . . . . 49
2.2 El problema de los cuatro colores para mapas infinitos . . . 51
2.3 Todo conjunto es totalmente ordenable . . . . . . . . . . . . . 54
2.4 El Lema de Infinitud de König . . . . . . . . . . . . . . . . . . 58
2.5 Un modelo no estándar para la teorı́a de los números naturales 62
2.6 Reivindicación de los infinitesimales . . . . . . . . . . . . . . 64
2.6.1 Un modelo para la teorı́a de los números reales, con
números infinitesimales . . . . . . . . . . . . . . . . . 66
2.6.2 Método general para demostrar propiedades de una
relación ∗R u operación ∗ f : principio de transferencia. 71
ix
x CONTENIDO
2.6.3 Finitos, infinitos e infinitesimales.Estándar y no-
estándar . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.6.4 Propiedades algebraicas . . . . . . . . . . . . . . . . . 74
3 El Teorema de Completud de Gödel y su relación con el Teorema de Com-
pacidad 77
3.1 Teoremas de equivalencia y formas normales prenex . . . . . 78
3.2 Skolemización. Teoremas de Skolem y de Herbrand . . . . . 86
3.3 Sistemas axiomáticos . . . . . . . . . . . . . . . . . . . . . . . 104
3.4 Resultados metalógicos . . . . . . . . . . . . . . . . . . . . . . 114
3.5 Una prueba semántica del Teorema de Correctud-Comple-
tud Extendido . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
A Prueba Sintáctica del Teorema de Completud-Correctud Extendido de
Gödel 139
A.1 Teorema de Correctud-Completud para Lρ . . . . . . . . . . 139
A.2 Prerrequisitos sintácticos . . . . . . . . . . . . . . . . . . . . . 147
A.3 Demostración de la versión A del Teorema de Completud-
Correctud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
A.3.1 Sublemas sobre constantes (para el Lema 2) . . . . . . 157
Introducción
La primera noticia que tenemos del Teorema de Compacidad, data de
1930, cuando Kurt Gödel lo presentó junto con el Teorema de Completud
en su tesis doctoral, en la Universidad de Viena, aunque esta presentación
fue para lenguajes contables. Después, en 1936, el teorema, fue presentado
implı́citamente, para lenguajes incontables, en un artı́culo de Anatolii Mal-
cev; su prueba utiliza funciones de Skolem y el Teorema de Compacidad
para la Lógica de Enunciados; más tarde, el mismo Malcev en un artı́culo
de 1941 dió una presentación explı́cita del mismo teorema, para lenguajes
incontables y es al parecer la primera vez que se hacı́a. Como muchos
otros resultados matemáticos, existen diferentes pruebas de este teorema,
como la ya clásica, de León Henkin [Malitz], y otras que utilizan resultados
más fuertes, como la prueba del Teorema de Compacidad, que hace uso de
ultraproductos [Bell & Slomson], debida a Morel, Scott y Tarski (1958).
La prueba del Teorema de Compacidad que aquı́ veremos se hará utili-
zando exclusivamente métodos semánticos y no como usualmente se pre-
senta en muchos libros clásicos de Lógica, en los que se obtiene el Teorema
de Compacidad como corolario del Teorema de Completud Extendido de
Gödel. El procedimiento que seguiremos para la prueba se basa en el
método de Henkin, para expandir universos, que es una técnica usual en
Lógica Matemática. A diferencia de la prueba original de Gödel, la prueba
de Henkin se generaliza fácilmente a lenguajes de cualquier cardinalidad.
Supondré algunos conocimientos y resultados básicos de la Teorı́a de
Conjuntos, que pueden verse en [Amor 2005] y en los capı́tulos introduc-
torios de [Enderton] y de [Mendelson 1987].
xi
Capı́tulo 1
El Teorema de Compacidad para la Lógica de Pri-
mer Orden
1.1 Antecedentes
1.1.1 Conceptos y resultados preliminares
Lenguajes de primer orden y su semántica
Definición 1.1. Un tipo o signatura es un conjunto ρ de sı́mbolos, de la
siguiente forma:
ρ = [
⋃
1≤n
Rn] ∪ [
⋃
1≤m
Fm] ∪ C,
donde Rn es un conjunto de sı́mbolos relacionales de aridad n, Fm es un
conjunto de sı́mbolos funcionales de aridad m y C un conjunto de sı́mbolos
de constante.
La palabra “aridad” denota el número de argumentos de la relación o
función en cuestión, ya que los sı́mbolos relacionales y funcionales sólo
adquieren sentido cuando se asocia alguna semántica o interpretación al
tipo. Ası́, los sı́mbolos relacionales, funcionales y constantes del tipo se
interpretarán respectivamente, como relaciones, funciones y elementos dis-
tinguidos en un universo de interpretación. Supondremos que un sı́mbolo
no es una sucesión de sı́mbolos.
Para expresarnos en la lógica de primer orden, requerimos de un len-
guaje formal de primer orden de algún tipo ρ. Utilizamos el adjetivo de
1
2 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
primer orden, para indicar que los predicados se aplican únicamente a in-
dividuos, y que la cuantificación es únicamente sobre individuos. Esto
permite distinguirlos de aquellos lenguajes en los que hay predicados que
tienen a otros predicados como argumentos o en los cuales, se permite
cuantificación sobre predicados o funciones, a éstos últimos se les deno-
mina lenguajes de orden superior.
Definición 1.2. Sı́mbolos de un lenguaje de primer orden de tipoρ. Los sı́mbolos
para construir expresiones de un lenguaje de tipo ρ y al que denotaremos
con Lρ, son los siguientes:
i) v0, v1, . . . , vn, vn+1, . . . variables individuales.
ii) (, ), ,. sı́mbolos auxiliares.
iii) ¬,∨. conectivos proposicionales.
iv) ≈. sı́mbolo de igualdad.
v) ∃. cuantificador existencial.
vi) Los sı́mbolos de ρ. todos los sı́mbolos de ρ.
A los sı́mbolos de i) a v) les daremos una interpretación canónica y
les llamamos sı́mbolos lógicos; a los sı́mbolos de vi), les daremos una
interpretación variable y les llamamos sı́mbolos no-lógicos; de ahı́ que sea
ρ el que determine el tipo de lenguaje y el nombre del lenguaje de tipo ρ
de primer orden: Lρ. El lenguaje con el que hablamos acerca del lenguaje
formal, en este caso español más algunas expresiones nuevas, recibe el
nombre de metalenguaje. Ası́, nuestras definiciones y afirmaciones acerca
del lenguaje formal, están dadas en el metalenguaje.
Definición 1.3. Sea ρ un tipo. Una expresión de tipo ρ o ρ-expresión, es una
sucesión finita de sı́mbolos de Lρ.
Definición 1.4. El conjunto de los términos de tipo ρ o ρ-términos, es el menor
conjunto X de ρ-expresiones, tal que:
i) {vi : 0 ≤ i} ∪ C ⊆ X, donde C ⊆ ρ, es el conjunto de constantes de ρ.
1.1 ANTECEDENTES 3
ii) Si f ∈ Fm ⊆ ρ, 1 ≤ m y t1, . . . , tm ∈ X, entonces f (t1, . . . , tm) ∈ X.
Un término de tipo ρ es un elemento del conjunto de los términos de tipo ρ.
Definición 1.5. Una ρ-fórmula atómica es una expresión de la forma:
(t1 ≈ t2) o P(t1, . . . , tn), donde t1, . . . , tn son ρ-términos y P ∈ Rn ⊆ ρ.
Definición 1.6. El conjunto de las fórmulas de tipo ρ, es el menor conjunto X
de ρ-expresiones, tal que:
i) {α : α es una ρ − fórmula atómica} ⊆ X
ii) Si α y β están en X, entonces (¬α), (α ∨ β) ∈ X.
iii) Si α ∈ X y vi ∈ Var = {vi : 0 ≤ i}, entonces (∃viα) ∈ X.
Una ρ-fórmula es un elemento del conjunto de las fórmulas de tipo ρ.
Observaciones: 1.- En la definición 1.4, t1, . . . , tm se usan como variables del
metalenguaje o metavariables que varı́an sobre los términos del lenguaje
formal y en la definición 1.6, α y β se utilizan como metavariables, que
representan cualquier ρ- fórmula de un Lρ.
2.- Las definiciones de términos y de fórmulas dadas anteriormente fueron
hechas de modo recursivo, forma válida en Lógica Matemática, justificada
por un teorema general de recursión, véase [5].
Definición 1.7. Adoptaremos las usuales abreviaturas siguientes:
i) (α ∧ β), como abreviatura de ¬((¬α) ∨ (¬β)).
ii) (α→ β), como abreviatura de ((¬α) ∨ β).
iii) (α↔ β), como abreviatura de ((¬α) ∨ β) ∧ (α ∨ (¬β)).
iv) (∀viα), como abreviatura de (¬(∃vi(¬α))).
Definición 1.8. Una ρ-interpretación o ρ-estructura para un lenguaje Lρ, es un
par A = 〈A, I〉, donde:
i) A , ∅ (A conjunto no vacı́o es el universo o dominio de A).
ii) I : ρ→ A ∪ { f : Am → A, 1 ≤ m} ∪ [
⋃
{P(An) : 1 ≤ n}].
(donde P(An) denota el conjunto potencia de An), y tal que para cualquier
x ∈ ρ:
Si x ∈ Rn, I(x) = x
A ⊆ An.
Si x ∈ Fm, I(x) = x
A : Am → A.
4 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Si x ∈ C, I(x) = xA ∈ A.
I es la función interpretación de A sobre el universo A.
Usualmente si ρ = {x1, . . . , xn}, denotaremos a la estructura A = 〈A, I〉
como sigue:
A = 〈A, xA1 , . . . , x
A
n 〉.
Ejemplo:
Si ρ = {P2, f1, f2,1, f2,2, c0}, donde P2 ∈ R2; f1 ∈ F1; f2,1, f2,2 ∈ F2 y c0 ∈ C (una
constante). Entonces una interpretación posible para Lρ es:
B = 〈N,PB2 , f
B
1 , f
B
2,1, f
B
2,2, c
B
o 〉 = 〈N,≤, s,+, ·, 0〉.
Si A = 〈A, I〉 es una ρ-estructura, su tipo (denotado ρ(A)) es precisamenteel dominio de I, la función de interpretación de A, usualmente, cuando no
haya confusión escribiremos simplemente A, para denotar el dominio o
universo de A, B para el universo de B, C para el universo de C, etc.
Verdad en estructuras (Tarski, 1936)
Definición 1.9. Sea A una ρ-estructura. Una asignación S, para A, es una
función S :N→ A, es decir, una sucesión de elementos de A. Notación:
S ∈ NA = { f :N→ A}.
Una asignación S se conoce también como estado de las variables ya que
intuitivamente cada i ∈ N se corresponde con la variable xi y cada Si con
el valor o estado asociado a xi
Observaciones:
1.- Dada la asignación S, S(i/a) denota la nueva asignación tal que
S(i/a)(n) =
{
Sn, si n , i;
a , si n = i.
2.- [S(i/a)]( j/b), se denota S(i/a, j/b).
3.- S(i/a, j/b) = S( j/b, i/a), si i , j.
4.- S(i/a, j/b) = S( j/b) = S(i/b), si i = j.
1.1 ANTECEDENTES 5
Definición 1.10. La interpretación (o denotación) de un término t, bajo una
asignación S, en una estructura A, lo que denotaremos mediante tA [S], será
un elemento de A, tA [S] ∈ A, definido ası́:
i) Si t = vi, t
A [S] = vA
i
[S] = Si.
ii) Si t = c, tA [S] = cA [S] = cA.
iii) Si t = f (t1, . . . , tn),
tA[S] = ( f (t1, . . . , tn))
A [S] = fA(tA
1
[S], . . . , tAn [S]).
Definición 1.11. Dada una ρ-estructura A, una asignación S ∈ NA, y una
ρ-fórmula α, definimos la relación: S satisface a la fórmula α en la estructura
A, lo que denotamos A |= α[S], de la siguiente manera:
i) A |= (t1 ≈ t2) [S] sii t
A
1
[S] = tA2 [S]
ii) A |= P(t1, . . . , tn) [S] sii 〈t
A
1
[S], . . . , tAn [S]〉 ∈ P
A,
iii) A |= (¬α)[S] sii A 6|= α[S],
iv) A |= (α ∨ β)[S] sii A |= α[S] o A |= β[S],
v) A |= (∃viα)[S] sii hay a ∈ A, tal que A |= α[S(i/a)].
Observaciones:
1.- Con “sii”, abreviamos “si y sólo si”.
2.- Para decir que la asignación S no satisface a la fórmula α en la estructura
A, escribiremos:
A 6|= α[S].
Definición 1.12. (Verdad en una estructura)
i) Una fórmula α, es verdadera en una estructuraA, siiA |= α[S], para toda
S ∈ NA. Y denotamos este hecho como sigue:
A |= α.
En el caso anterior también diremos que A es un modelo de α.
ii) Diremos que una fórmula α es falsa en una estructura A sii A |= ¬α.
iii) Una interpretación A es un modelo para un conjunto Σ de fórmulas sii
toda fórmula de Σ es verdadera en A.
Debemos observar que si una fórmula no es verdadera en una estructura
A, no necesariamente es falsa en A, pues puede ser el caso de que unas
sucesiones la satisfagan, mientras otras no, en A.
6 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Definición 1.13. (Validez Universal o Validez Lógica).
Diremos que una ρ-fórmula α, es universalmente válida o lógicamente válida
sii A |= α, para toda ρ-estructura A. Y denotaremos este hecho como sigue:
|= α.
Más adelante presentamos ejemplos variados de fórmulas universalmente
válidas.
Definición 1.14. La noción “una presencia de la variable v aparece libre en
la fórmula α”, se define por recursión como sigue:
i) v aparece libre en α atómica sii v aparece en α,
ii) v aparece libre en (¬α) sii v aparece libre en α,
iii) v aparece libre en (α∨ β) sii v aparece libre en α o v aparece libre en β,
iv) v aparece libre en (∃viα) sii v aparece libre en α y v , vi.
Definición 1.15. Un ρ-enunciado es una ρ-fórmula en la cual no aparecen
variables libres.
Proposición 1.1. Sea t un ρ-término cualquiera, α una ρ-fórmula cualquiera, S
y S′ dos asignaciones en una ρ- estructura cualquiera A.
a) Si Si = S
′
i
para toda i , tal que vi aparece en t, entonces:
tA [S] = tA [S′].
b) Si Si = S
′
i
para toda i , tal que vi aparece libre en α, entonces:
A |= α[S] sii A |= α[S′].
Las demostraciones se hacen por inducción sobre la formación de términos y
fórmulas, respectivamente y se dejan como ejercicio.
⋄
1.1 ANTECEDENTES 7
Corolario 1.1.1. Sea φ un ρ-enunciado cualquiera y A una ρ- estructura cual-
quiera, entonces:
a) Para cualesquiera S, S′ ∈ NA,A |= φ[S] sii A |= φ[S′].
b) A |= φ sii hay S ∈ NA tal que A |= φ[S].
c) A |= φ o A |= (¬φ).
(Es decir, φ es verdadera en A o (¬φ) es verdadera en A).
Es decir, φ es verdadera o falsa en A, en caso de ser enunciado.
Es importante en una fórmula poder sustituir un término por otro, tanto
por comodidad como por conveniencia, sin embargo, tales sustituciones
no se pueden hacer arbitrariamente, pues pueden cambiar el sentido de la
expresión, por ello reglamentaremos las sustituciones.
Definición 1.16. Sean t0, t ρ-términos, sean además v una variable y α una
ρ-fórmula, definiremos por recursión: (t0)
v
t que se lee “la sustitución de t
en lugar de cada presencia libre de la variable v en t0”, y (α)
v
t que se lee
“la sustitución de t en lugar de cada presencia libre de la variable v en α”,
como sigue:
a) Para términos tenemos, (recursivamente)
Si t0 = vi, (vi)
v
t =
{
t, si v = vi;
vi, si v , vi.
Si t0 = c, (c)
v
t = c.
Si t0 = f (t1, . . . , tn), ( f (t1, . . . , tn))
v
t = f ((t1)
v
t , . . . , (tn)
v
t ).
b) Para fórmulas tenemos, (recursivamente)
i) Atómicas
(t1 ≈ t2)
v
t = ((t1)
v
t ≈ (t2)
v
t ),
(P(t1, . . . , tn))
v
t = P((t1)
v
t , . . . , (tn)
v
t ).
ii) Fórmulas compuestas
(¬α)vt = ¬((α)
v
t ),
(α ∨ β)vt = ((α)
v
t ∨ (β)
v
t ),
(∃viα)
v
t =







(∃viα) , si v = vi;
∃vi((α)
v
t ) , si v , vi y vi no aparece en t o v no aparece libre en α;
∃z((α)viz )
v
t ), si v , vi y vi aparece en t y v aparece libre en α.
(Donde z es la primera nueva variable z , v que no aparece en (∃viα), ni en
t). Observar que si v no aparece libre en α, entonces (α)vt = α para cualquier
α y cualquier t; por inducción sobre α.
8 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Ejemplo: Consideremos la siguiente fórmula: (∃w¬(w ≈ v))v
f (c,w)
, donde
w, v son variables y f (c,w) un término. Entonces, como v aparece libre
en la fórmula, v , w y w aparece en el término, por definición la fórmula
anterior es igual a:
∃z(¬(w ≈ v)wz )
v
f (c,w),
considerando que la fórmula¬(w ≈ v)wz es por definición: ¬(z ≈ v), tenemos
que la fórmula resultante es:
∃z¬(z ≈ v)vf (c,w),
ya que v aparece libre en la fórmula y z no aparece en f (c,w), la fórmula
final es:
∃z¬(z ≈ f (c,w)).
Observación:
En otros textos de lógica matemática se define (α)
y
t de modo diferente para
el caso existencial, ya que se pide que vi no aparezca en t. Esta petición
se conoce como: “x es libre para t en α” o como “(α)vt es admisible”. Con
nuestra definición cualquier sustitución es admisible y sin restricciones.
Teorema 1.2. (Teorema de Sustitución)
Sean t, t0 ρ-términos, α una ρ-fórmula, A una ρ-estructura y S una asignación
S ∈ NA, entonces:
1) tA0 [S(i/t
A [S])] = ((t0)
vi
t )
A [S].
2) A |= α[S(i/tA [S])] sii A |= (α)vit [S].
Informalmente, este teorema afirma que la sustitución de objetos en la
interpretación, se corresponde con la sustitución de sı́mbolos en el lenguaje.
Demostración:
1) (Indución sobre la formación de términos.) Con H.I. abreviamos Hipó-
tesis Inductiva.
i) vAn [S(i/t
A [S])] =
{
vAn [S] = ((vn)
vi
t )
A [S], si i , n; ∗
tA [S] = ((vn)
vi
t )
A [S] , si i = n.
[∗ Por Proposición 1 y por definición 1.16 a).]
1.1 ANTECEDENTES 9
ii) cA [S(i/tA [S])] = cA [S] = ((c)vit )
A [S].
iii) ( f (t1, . . . , tn))
A [S(i/tA [S])] =
= fA(tA
1
[S(i/tA [S])], . . . , tAn [S(i/t
A [S])]), . . . def. de interp. de términos.
= fA(((t1)
vi
t )
A [S], . . . , ((tn)
vi
t )
A [S]), . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.I.
= ( f ((t1)
vi
t , . . . , (tn)
vi
t ))
A [S], . . . . . . . . . . . . . . . . . def. de interp. de términos.
= (( f (t1, . . . , tn))
vi
t )
A [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . def. de sustitución.
2) Por inducción sobre el número de sı́mbolos de la fórmula α. Probamos
2) para fórmulas de n sı́mbolos, suponiendo su verdad para fórmulas con
menos de n sı́mbolos.
i) A |= (t1 ≈ t2) [S(i/t
A [S])]
sii tA
1
[S(i/tA [S])] = tA2 [S(i/t
A [S])], . . . . . . .. . . . . . . . def. de satisfacción,
sii ((t1)
vi
t )
A [S] = ((t2)
vi
t )
A [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por 1),
sii A |= ((t1)
vi
t ≈ (t2)
vi
t ) [S], . . . . . . . . . . . . . . . . . . . . . . . . .def. de satisfacción,
sii A |= (t1 ≈ t2)
vi
t [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . def. de sustitución.
ii) A |= P(t1, . . . , tn) [S(i/t
A [S])]
sii 〈tA
1
[S(i/tA [S])], . . . , tAn [S(i/t
A [S])]〉 ∈ PA, . . . . . . def. de satisfacción,
sii 〈((t1)
vi
t )
A [S], . . . , ((tn)
vi
t )
A [S]〉 ∈ PA, . . . . . . . . . . . . . . . . . . . . . . . . . . por 1),
sii A |= P((t1)
vi
t , . . . , (tn)
vi
t )[S], . . . . . . . . . . . . . . . . . . . . . . def. de satisfacción,
sii A |= (P(t1, . . . , tn))
vi
t [S], . . . . . . . . . . . . . . . . . . . . . . . . def. de sustitución.
iii) A |= (¬α) [S(i/tA [S])]
sii A 6|= α [S(i/tA [S])], . . . . . . . . . . . . . . . . . . . . . . . . . . . . def. de satisfacción,
sii A 6|= (α)vit [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.I.,
sii A |= ¬(α)vit [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . def. de satisfacción,
sii A |= (¬α)vit [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . def. de sustitución.
iv) A |= (α ∨ β) [S(i/tA [S])]
sii A |= α [S(i/tA [S])] o A |= β [S(i/tA [S])], . . . . . . . def. de satisfacción,
sii A |= (α)vit [S] o A |= (β)
vi
t [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .H.I,
sii A |= ((α)vit ∨ (β)
vi
t ) [S], . . . . . . . . . . . . . . . . . . . . . . . . . . def. de satisfacción,
sii A |= (α ∨ β)vit [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . def. de sustitución,
v) A |= (∃vnα) [S(i/t
A [S])] sii A |= (∃vnα)
vi
t [S]
Existen tres casos según la definición de sustitución:
Caso 1) vi no está libre en (∃vnα):
A |= (∃vnα) [S(i/t
A [S])]
sii A |= (∃vnα) [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por Proposición 1,
10 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
sii A |= (∃vnα)
vi
t [S], . . . . . . . . . . . . . . . . . . . . . . . . . ya que (∃vnα)
vi
t = (∃vnα).
Caso 2) vi está libre en (∃vnα) (entonces i , n) y vn no aparece en t.
A |= (∃vnα) [S(i/t
A [S])]
sii hay a ∈ A, tal que A |= α [S(i/tA [S],n/a)], . . . . . . . . . def. satisfacción,
sii hay a ∈ A, tal que A |= α [S(n/a, i/tA [S])], . . . . . . . . . . . . . . . . . . . . . . . . . ∗
sii hay a ∈ A, tal que A |= α [S(n/a, i/tA [S(n/a)])], . . . . . . . . . . . . . . . . . . . ∗∗
sii hay a ∈ A, tal que A |= (α)vit [S(n/a)], . . . . . . . . . . . . H.I. con S = S(n/a),
sii A |= (∃vn(α)
vi
t ) [S], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .def. satisfacción,
sii A |= (∃vnα)
vi
t [S], . . . . . . . . . . . . . . . . . . . def. de sustitución, pues i , n.
[∗ Observación 3 de la definición 1.9 con i , n.]
[∗∗ Como vn no aparece en t, t
A [S] = tA [S(n/a)], por la Proposición 1.]
Caso 3) vi está libre en (∃vnα) (entonces i , n) y vn sı́ aparece en t. Sea k el
menor entero positivo tal que vk no aparece en (∃vnα) ni en t; ası́, k , n y
k , i.
A |= (∃vnα) [S(i/t
A [S])]
sii hay a ∈ A, tal que A |= α [S(i/tA [S],n/a)], . . . . . . . . . def. satisfacción,
sii hay a ∈ A, tal que A |= α [S(i/tA [S],n/a, k/a)], . . . . . . . . . . . . . . . . . . . . ∗1,
sii hay a ∈ A, tal que A |= α [S(i/tA [S], k/a,n/a)], . . . . . . . . . . . . . . . . . . . . ∗2,
sii hay a ∈ A, tal que A |= α [S(i/tA [S], k/a,n/vA
k
[S(i/tA [S], k/a)])],
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pues vA
k
[S(i/tA [S], k/a)] = a,
sii hay a ∈ A, tal que A |= (α)vnvk [S(i/t
A [S], k/a)],
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.I. con S = S(i/tA [S], k/a),
sii hay a ∈ A, tal que A |= (α)vnvk [S(k/a, i/t
A [S])], . . . . . . . . . . . . . . . . . . . . . ∗3,
sii hay a ∈ A, tal que A |= (α)vnvk [S(k/a, i/t
A [S(k/a)])], . . . . . . . . . . . . . . . . ∗4,
sii hay a ∈ A, tal que A |= ((α)vnvk )
vi
t [S(k/a)], . . . . . por H.I. con S = S[k/a],
sii A |= (∃vk((α)
vn
vk )
vi
t [S], . . . . . . . . . . . . . . . . . . . . definición de satisfacción,
sii A |= (∃vnα)
vi
t [S], . . . . . . . . . . . . . . . . . . . def. de sustitución en el caso 3.
[∗1 Proposición 1, pues vk no aparece en α.
∗2 Observación 3 de la definición de 1.9, con k , n.
∗3 Observación 3 de la definición de 1.9, con i , k.
∗4 Proposición 1, pues vk no aparece en t, entonces: t
A [S] = tA [S(k/a)].]
Observe que α y (α)vnvk , poseen el mismo número de sı́mbolos, lo cual
justifica el segundo paso inductivo (sólo para este caso, es que nuestra
inducción es sobre el número de sı́mbolos que aparece n en las fórmulas,
en vez de ser sobre la construcción de las fórmulas, pues α y (α)vnvk son
fórmulas distintas, pero con el mismo número de sı́mbolos. ⋄
1.1 ANTECEDENTES 11
Corolario 1.2.1. Si hay un ρ-término t, tal que A |= (α)vit [S], entonces
A |= (∃viα) [S].
Demostración: Sea t tal que A |= (α)vit [S]; por el teorema de sustitución
tenemos que A |= α [S(i/tA [S])]. Sea a = tA [S] ∈ A, luego hay a ∈ A, tal
que A |= α [S(i/a)] y por definición de satisfacción A |= (∃viα) [S]. ⋄
Corolario 1.2.2. Para cualquier ρ-término t,
|= [(∀viα)→ (α)
vi
t ].
Demostración: Sean A, ρ-estructura y S ∈ NA; supongamos que A |=
(∀viα) [S], esto es, A 6|= (∃vi¬α) [S], por abreviatura de ∀; luego por el
Corolario 2.1, para cada ρ-término t, A 6|= (¬α)vit [S], ası́ por definición de
sustitución y de satisfacción, para cualquier ρ-término t, A |= (α)vit [S]. ⋄
En las siguientes páginas presentamos muchos ejemplos de fórmulas
universalmente válidas clasificadas según su forma.
Ejercicios: Sean φ, γ1, . . . , γm, γ fórmulas cualesquiera. En lo que sigue el
sı́mbolo “⇔” denota la relación “si y sólo si” del metalenguaje.
1.- |= φ⇔|= (∀xφ).
2.- |= φ⇔|= (∀φ), donde ∀φ denota la cuantificación universal de todas
las posibles variables que ocurren libres en φ.
3.- |= φ ⇔ ((¬φ) es no satisfacible) (es decir, no hay interpretación ni
asignación que la satisfagan).
4.- φ es satisfacible⇔ (∃xφ) es satisfacible.
5.- φ es satisfacible⇔ (∃φ) es satisfacible, donde ∃φ denota cuantifi-
cación existencial de todas las posibles variables que ocurren libres en φ.
Presentamos enseguida algunos ejemplos clasificados de fórmulas uni-
versalmente válidas cuya verdad depende únicamente de los criterios de
verdad de los conectivos, las que son generalmente conocidas como tau-
tologı́as. También incluimos el nombre con el que se conocen. En lo que
sigue, α, β, γ, son fórmulas cualesquiera de un lenguaje de primer orden.
12 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
A. Leyes Clásicas
1.- α↔ α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Identidad
2.- ¬(α ∧ ¬α) . . . . . . . . . . . . . . . . . . . . . . . . . . . . No Contradicción
3.- α ∨ ¬α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tercero Excluido
B. Asociatividad y Conmutatividad
1.- (α ∧ β) ∧ γ↔ α ∧ (β ∧ γ)
2.- (α ∨ β) ∨ γ↔ α ∨ (β ∨ γ)
3.- ((α↔ β)↔ γ)↔ (α↔ (β↔ γ))
4.- (α ∧ β)↔ (β ∧ α)
5.- (α ∨ β)↔ (β ∨ α)
6.- (α↔ β)↔ (β↔ α)
C. Leyes de Negación
1.- ¬¬α↔ α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Doble Negación
2.- ¬(α ∨ β)↔ (¬α ∧ ¬β) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ∗
3.- ¬(α ∧ β)↔ (¬α ∨ ¬β) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ∗
4.- ¬(α→ β)↔ (α ∧ ¬β)
5.- ¬(α↔ β)↔ (α ∧ ¬β) ∨ (β ∧ ¬α)
∗[De Morgan o Dualidad.]
D. Leyes de Simplificación
1.- α ∨ α↔ α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Idempotencia
2.- α ∧ α↔ α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Idempotencia
3.- α ∧ (α ∨ β)↔ α . . . . . . . . . . . . . . . . . . . . . . . . . . . Eliminación
4.- α ∨ (α ∧ β)↔ α . . . . .. . . . . . . . . . . . . . . . . . . . . . Eliminación
5.- α ∧ (β ∨ ¬β)↔ α . . . . . . . . . . . . . . . . . . . . . . . . . . . . Absorción
6.- α ∧ (β ∧ ¬β)↔ (β ∧ ¬β) . . . . . . . . . . . . . . . . . . . . . Absorción
7.- α ∨ (β ∧ ¬β)↔ α . . . . . . . . . . . . . . . . . . . . . . . . . . . . Absorción
8.- α ∨ (β ∨ ¬β)↔ (β ∨ ¬β) . . . . . . . . . . . . . . . . . . . . . Absorción
9.- (α ∨ β) ∧ (α ∨ ¬β)↔ α . . . . . . . . . . . . . . . . . . Simplificación
10.- (α ∧ β) ∨ (α ∧ ¬β)↔ α . . . . . . . . . . . . . . . . . Simplificación
E. Distributividad-Factorización
1.- α ∨ (β ∧ γ)↔ (α ∨ β) ∧ (α ∨ γ)
2.- α ∧ (β ∨ γ)↔ (α ∧ β) ∨ (α ∧ γ)
3.- [α→ (β ∨ γ)]↔ [(α→ β) ∨ (α→ γ)]
4.- [α→ (β ∧ γ)]↔ [(α→ β) ∧ (α→ γ)]
5.- [α ∨ (β→ γ)]↔ [(α ∨ β)→ (α ∨ γ)]
6.- [α ∧ (β→ γ)]→ [(α ∧ β)→ (α ∧ γ)]
1.1 ANTECEDENTES 13
7.- [(α ∨ β)→ γ]↔ [(α→ γ) ∧ (β→ γ)]
8.- [(α ∧ β)→ γ]↔ [(α→ γ) ∨ (β→ γ)]
F. Exportación-Importación
1.- [(α ∧ β)→ γ]↔ [α→ (β→ γ)]
2.- [α ∧ (β→ γ)]→ [(α ∧ β)→ γ)]
3.- [α ∧ (α ∧ β→ γ)]→ [β→ γ)]
4.- [α ∧ (β→ γ)]→ [β→ (α ∧ γ)]
5.- [α ∨ (β→ γ)]→ [β→ (α ∨ γ)]
G. Leyes de la Implicación
1.- (α→ β)↔ (¬α ∨ β)
2.- (α→ β)↔ ¬(α ∧ ¬β)
3.- (α→ β)↔ (¬β→ ¬α) . . . . . . . . . . . . . . . . . . . .Contrapuesta
4.- [α→ (β→ γ)]↔ [β→ (α→ γ)] . . . . . . . . . . . . . . . . . . . . . . .∗
5.- α→ (β→ α) . . . . . . . . . . . . . . . Afirmación del antecedente
6.- (¬α→ α)→ α . . . . . . . . . . . . . . . . . .Consecuentia Mirabilis
7.- ¬α→ (α→ β) . . . . . . . . . . . . . . . . . . . Ley de Contradicción
8.- (α→ β)↔ (α→ α ∧ β) . . . . . . . . . . . . . . . . . . . . . . Expansión
9.- (α→ β)↔ (α ∨ β→ β) . . . . . . . . . . . . . . . . . . . . . . Expansión
∗[Intercambio de premisas]
H. Leyes del Bicondicional
1.- (α↔ β)↔ [(α→ β) ∧ (β→ α)]
2.- (α↔ β)↔ [(¬α ∨ β) ∧ (α ∨ ¬β)]
3.- (α↔ β)↔ [(α ∧ β) ∨ (¬α ∧ ¬β)]
4.- (α↔ β)↔ (¬α↔ ¬β)
5.- (α↔ β)↔ ¬(α ∧ ¬β) ∧ ¬(β ∧ ¬α)
14 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Presentamos ahora algunas fórmulas universalmente válidas, que son
tautologı́as, de la forma α → γ o [α ∧ β] → γ, o en general de la forma
[α1 ∧ . . . ∧ αn] → γ, y que corresponden a argumentos correctos o válidos
o bien a las llamadas reglas de inferencia usuales (véase Capı́tulo 3). En lo
que sigue, α, β, γ, δ, αi, α j, βi, denotan fórmulas cualesquiera de un lenguaje
de primer orden.
1.- [(α→ β) ∧ α]→ β . . . . . . . . . . . . . . . . . . . . . . Modus Ponens.
2.- [(α→ β) ∧ ¬β]→ ¬α . . . . . . . . . . . . . . . . . . . Modus Tollens.
3.- [(α ∨ β) ∧ ¬α]→ β . . . . . . . . . . . . . . Silogismo Disyuntivo.
[(α ∨ β) ∧ ¬β]→ α . . . . . . . . . . . . . . Silogismo Disyuntivo.
4.- [(α→ β) ∧ (β→ γ)]→ (α→ γ) . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .Silogismo hipotético, o transitividad de la implicación.
5.- α→ α ∨ β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adición.
β→ α ∨ β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adición.
6.- (α ∧ β)→ α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simplificación.
(α ∧ β)→ β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simplificación.
7.- [α ∧ β]→ (α ∧ β) . . . . . . . . . . . . . . . . . . . . . . . . . . . Adjunción.
8.- [(α→ β) ∧ (α→ γ)]→ (α→ β ∧ γ) . . . . . . .Composición.
9.- [(α→ γ) ∧ (β→ δ) ∧ (α ∨ β)]→ (γ ∨ δ) . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dilema Constructivo.
10.- [(α→ γ) ∧ (β→ δ) ∧ (¬γ ∨ ¬δ)]→ (¬α ∨ ¬β) . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dilema Destructivo.
11.- [¬β→ ¬α]→ (α→ β) . . . . Prueba por Contraposición.
12.- [(α→ γ) ∧ (β→ γ) ∧ (α ∨ β)]→ γ . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Prueba por casos.
13.- [(α→ γ) ∧ (¬α→ γ)]→ γ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . Caso especial de Prueba por Casos.
14.- [
∧n
i=1(αi → γ) ∧ (
∨n
i=1 αi)]→ γ . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Prueba General por casos.
15.- [α ∧ ¬α]→ β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . De una contradicción, inferir cualquier proposición.
16.- [(¬α→ β) ∧ (¬α→ ¬β)]→ α . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Reducción al Absurdo.
[¬α→ (β ∧ ¬β)]→ α . . . . . . . . . . Reducción al Absurdo.
17.- [(α→ γ) ∧ (β→ δ) ∧ (α ∨ β) ∧ ¬(α ∧ β) ∧ (γ ∨ δ) . . . . . .
∧¬(γ ∧ δ)]→ (γ→ α) ∧ (δ→ β) . . . . . . . Ley de Hauber.
1.1 ANTECEDENTES 15
Presentamos ahora algunos ejemplos de fórmulas universalmente vá-
lidas no tautologı́as, es decir, tales que su verdad depende de los criterios
de verdad de los cuantificadores además de los de los conectivos. En lo
que sigue, α y β representan fórmulas cualesquiera y σ una fórmula en la
cual la variable x no aparece libre; x, y, representan variables vi, v j, i, j ∈ N
y t representa un término cualquiera.
A. Relación entre ∀x y ∃x
1.- ∀xα↔ ¬∃x¬α
2.- ¬∀xα↔ ∃x¬α
3.- ∃xα↔ ¬∀x¬α
4.- ¬∃xα↔ ∀x¬α
5.- ∀xα→ (α)xt
La prueba de este último ejemplo es el Corolario 2 del Teorema de Susti-
tución.
B. Intercambio de cuantificadores
1.- ∀x(σ)
y
x ↔ ∀yσ
2.- ∃x(σ)
y
x ↔ ∃yσ
3.- ∀x∀yα↔ ∀y∀xα
4.- ∃x∃yα↔ ∃y∃xα
5.- ∀xα→ ∃xα
6.- ∃x∀yα→ ∀y∃xα
C. Relación de cuantificadores y conectivos
1.- ∀x(α ∧ β)↔ ∀xα ∧ ∀xβ
2.- ∃x(α ∧ β)→ ∃xα ∧ ∃xβ
3.- ∀xα ∨ ∀xβ→ ∀x(α ∨ β)
4.- ∃x(α ∨ β)↔ ∃xα ∨ ∃xβ
5.- ∀x(α→ β)→ (∀xα→ ∀xβ)
6.- (∃xα→ ∃xβ)→ ∃x(α→ β)
D. Doble cuantificación
1.- ∀x(∀xα→ α)
2.- ∃x(∃xα→ α)
3.- ∀x(α→ ∃xα)
4.- ∃x(α→ ∀xα)
5.- ∀x∀xα↔ ∀xα
6.- ∃x∃xα↔ ∃xα
16 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
E. Relación de cuantificadores con fórmulas sin presencias de la variable
cuantificada. Aquı́ x no aparece libre en σ.
1.- ∀xσ↔ σ
2.- ∃xσ↔ σ
3.- ∀x(α ∧ σ)↔ ∀xα ∧ σ
4.- ∃x(α ∧ σ)↔ ∃xα ∧ σ
5.- ∀x(α ∨ σ)↔ ∀xα ∨ σ
6.- ∃x(α ∨ σ)↔ ∃xα ∨ σ
7.- ∀x(σ→ α)↔ (σ→ ∀xα)
8.- ∃x(σ→ α)↔ (σ→ ∃xα)
9.- ∀x(α→ σ)↔ (∃xα→ σ)
10.- ∃x(α→ σ)↔ (∀xα→ σ)
F. Con igualdad
1.- ∀x(x ≈ x)
2.- ∀x∀y(x ≈ y→ y ≈ x)
3.- ∀x∀y∀z(x ≈ y ∧ y ≈ z→ x ≈ z)
Si α(x/y) denota el resultado de sustituir y en lugar de x en α, en cero o
más lugares o todos los lugares. Entonces:
4.- ∀x∀y[x ≈ y→ (α→ α(x/y))] (Ley de Leibniz).
G. Paradoja de Russell
1.- ¬∃x∀y[α↔ ¬(α)xy]
2.- ¬∃x∀y[(α)x
g(x)
↔ ¬(α)x
g(y)
]
3.- ¬∃x∀y[(α)
y
g(y)
↔ ¬((α)
y
g(y)
)xy]
H. Otras universalmente válidas
1.- ∃x[α ∧ ∀y(β→ γ)]→ ∀y[β→ ∃x(α ∧ γ)]
2.- ∃x[α(x) ∧ ∀y(β(y)→ γ(x, y))]→ ∀y[β(y)→ ∃x(α(x) ∧ γ(x, y))]
3.- ∃x(P(x) ∨Q(x))↔ ∃yP(y) ∨ ∃zQ(z))
4.- ∀x∃y[P(x)→ Q(y)]↔ [∃xP(x)→ ∃yQ(y)]
Para aclarar más los tres ejemplos de universalmente válidas del tipo G.
Paradoja de Russell, daremos tres instancias particulares con α = P(x, y):
1.- ¬∃x∀y(P(x, y)↔ ¬P(y, y))
2.- ¬∃x∀y(P(g(x), y)↔ ¬P(g(y), y))
3.- ¬∃x∀y(P(x, g(y))↔ ¬P(y, g(y)))
1.1 ANTECEDENTES 17
1.1.2 Consecuencia lógica
Dedicamos esta sección a uno de los conceptos fundamentales de la lógica
matemática, el concepto de consecuencia lógica. Es importante hacerlo
preciso aquı́, pues en su definición intervienen los conceptos vistos an-
teriormente, como interpretación, asignación, satisfacción y en el caso de
enunciados, el concepto de verdad, y por otro lado lo usaremos en una
de las formulaciones del teorema de compacidad y en el resto del libro,
especialmente en el capı́tulo tres. En lo que sigue nos referiremos como
antes únicamente a lenguajes formales de primer orden con igualdad. Con
respecto a la notación, usaremos las letras griegas minúsculas α, β, γ, ϕ,
ψ, para referirnos a fórmulas del lenguaje. Las letras griegas mayúsculas
Σ, ∆, Γ, las usaremos para referirnos a conjuntos, finitos o infinitos, de
fórmulas de dicho lenguaje. Las letras góticas como A,B, C, representarán
estructurascomo interpretaciones del lenguaje o modelos de fórmulas.
La relación semántica básica de ser forzado a ser verdad por otras ver-
dades, es la idea intuitiva de la relación de consecuencia lógica. Decimos
que una fórmula α es una consecuencia lógica de un conjunto de formulas
Σ, si siempre que las fórmulas de Σ son satisfechas por alguna asignación
dada para las variables en una interpretación, la fórmula α también es
satisfecha por esa asignación en esa interpretación.
Definición 1.17. Sea Σ ∪ {ϕ} un conjunto de fórmulas, no necesariamente
enunciados, en un lenguaje de primer orden con igualdad. Decimos que
ϕ es una consecuencia lógica de Σ o que Σ implica lógicamente a ϕ (denotado
Σ |= ϕ) si y sólo si en toda interpretacionA toda asignación para variables s
(de elementos del universo de A) que satisface α para cada α ∈ Σ, también
satisface ϕ1. Ilustramos esto con los siguientes ejemplos: ∀xP(x) |= P(c)
pero P(x) 6|= ∀xP(x). También, para cualquier fórmula dada ϕ, no necesa-
riamente un enunciado, ϕ |= ∀xϕ implica que |= (ϕ→ ∀xϕ).
Nótese que la definición de “ϕ es consecuencia lógica de Σ” significa
que es imposible que haya una interpretación y una asignación donde
todas las fórmulas del conjunto Σ sean satisfechas y la fórmula ϕ no.
Se sigue inmediatamente de las definiciones, que en el caso particular
de los enunciados, un enunciado ϕ es una consecuencia lógica de un con-
junto de enunciados Σ, si y sólo si para cualquier interpretación, siempre
1Cf. [Mendelson 1987] página 52, [Enderton 2001] página 88 y [Enderton 2004] página
132.
18 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
que todos los enunciados de Σ sean verdaderos, entonces el enunciado ϕ
también es verdadero. En otras palabras, si todos los modelos de Σ son
también modelos de ϕ2.
Las fórmulas que son verdaderas en cualquier interpretación se llaman
lógicamente validas. Cuando una fórmula es verdadera en una interpre-
tación de su lenguaje, decimos que la interpretación es un modelo de la
fórmula; ası́, una fórmula es lógicamente válida si todas las interpretacio-
nes para su lenguaje son modelos de la fórmula. En particular tenemos que
si una fórmula es lógicamente válida, será consecuencia lógica de cualquier
conjunto de fórmulas. Por otro lado, si Σ es un conjunto de fórmulas que
no es satisfacible, entonces trivialmente cualquier fórmula es consecuencia
lógica de Σ.
Usaremos algunas propiedades semánticas básicas3 cuya prueba es ele-
mental, pues depende solamente de las definiciones de verdad y de con-
secuencia lógica. Estas son las siguientes:
a) Si Γ ⊆ Σ y Γ |= ϕ entonces Σ |= ϕ (Monotonı́a)
b) Si Σ |= ϕ y para todo α en Σ, Γ |= α, entonces Γ |= ϕ (Corte)
c) Σ, α |= β si y sólo si Σ |= (α→ β)
d) Σ |= ϕ si y sólo si Σ ∪ {¬ϕ} no es satisfacible
e) Γ es satisfacible si y sólo si Γ 6|= ∃x(x , x)
f) Σ, α, (α→ β) |= β
La propiedad c) para el caso Σ vacı́o, establece la equivalencia entre la
noción de consecuencia lógica entre dos fórmulas y la noción de validez
lógica de la fórmula de forma implicativa correspondiente. La propiedad
d) es una reescritura de la definición de consecuencia lógica. Recordemos
que nuestro lenguaje no tiene el sı́mbolo “→” de implicación, pero enten-
deremos que la fórmula implicativa (α → β) es una abreviatura para la
fórmula (¬α ∨ β).
Algunas de estas propiedades semánticas, cuya prueba es elemental,
pueden ser usadas en adelante, apelando a cualquiera de ellas sólo como
“propiedades semánticas”.
En la sección 1.2 presentaremos el teorema de compacidad para len-
2Recordar que un modelo para un conjunto de fórmulas es una interpretación para el
lenguaje respecto al cual todas las fórmulas del conjunto son verdaderas.
3También llamadas propiedades estructurales de la lógica deductiva clásica.
1.1 ANTECEDENTES 19
guajes de primer orden con igualdad, al que consideramos el resultado
semántico fundamental. Consideramos ahora sus dos formas equivalen-
tes:
Teorema 1.3. Teorema de Compacidad (Gödel-Malcev)(Primera forma)
Si Σ es un conjunto infinito de fórmulas de un lenguaje de primer orden con
igualdad, tal que cada subconjunto finito de Σ es satisfacible, entonces Σ es
tambien satisfacible.
Teorema 1.4. Teorema de Compacidad (Segunda forma)
Si Σ∪ {ϕ} es un conjunto infinito de fórmulas de un lenguaje de primer orden con
igualdad y si Σ |= ϕ, entonces hay un subconjunto finito Γ ⊆ Σ, tal que Γ |= ϕ.
Nótese que el teorema de compacidad es una afirmación puramente se-
mántica que involucra únicamente nociones semánticas. Daremos una
demostración puramente semántica para él, con base en propiedades
semánticas. Damos ahora un esbozo de la demostración de la primera
forma:
Partimos de un conjunto infinito de fórmulas Σ tal que cada subconjunto
finito suyo es satisfacible (llamaremos a esta propiedad “finitamente sa-
tisfacible”). Después desarrollamos dos procesos alternativamente, el pri-
mero consiste en obtener un conjunto Γ tal que Σ ⊆ Γ y Γ es un conjunto
maximal finitamente satisfacible de fórmulas. El segundo proceso consiste
en obtener un conjunto Ω tal que Σ ⊆ Ω, y Ω está cerrado bajo testigos
existenciales4 y es un conjunto finitamente satisfacible de fórmulas. Entonces
los dos procesos se iteran uno en seguida del otro en un nuevo proceso
infinito. Finalmente, la unión de todos esos conjuntos de los dos procesos
alternados infinitamente, es un conjunto de fórmulas Σ∗ tal que: Σ ⊆ Σ∗
y Σ∗ es un conjunto maximal cerrado bajo testigos existenciales y finita-
mente satisfacible. Entonces se construye un modelo para Σ∗. Ese modelo
es obviamente un modelo para Σ y ası́ tenemos que Σ es satisfacible. Esta
prueba se desarrollará con todo detalle en la sección 1.3.
Ejercicios:
1. Probar todas las propiedades semánticas básicas.
4Es decir, si ∃xϕ(x) ∈ Ω entonces hay una constante c (el testigo existencial), tal que
ϕ(c) ∈ Ω.
20 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
2. Probar la equivalencia de las dos formas del teorema de compacidad.
3. Probar lo siguiente:
a) γ1, . . . , γn |= γ ⇔ |= [(γ1 ∧ . . . ∧ γn)→ γ].
b) γ1, . . . , γn |= γ ⇔ |= (γ1 → (γ2 → . . .→ (γn → γ)) . . .).
1.1.3 Relaciones entre estructuras
Es natural pensar en las relaciónes de contención entre los conjuntos que
son universos de determinadas estructuras, ası́ como en la “contención” de
una estructura en otra; estas relaciones son interesantes y a continuación
las presentamos.
Definición 1.18. Sean A, B dos ρ-estructuras, decimos que A es una sub-
estructura de B, lo que denotaremos A ⊆ B, sii
i) A ⊆ B
ii) Si P ∈ Rn ⊆ ρ, entonces P
A = PB ∩ An,
iii) Si f ∈ Fm ⊆ ρ, entonces f
A = fB|Am (la función f
B restringida al
conjunto Am),
iv) Si c ∈ C ⊆ ρ, entonces cA = cB.
El que A sea subestructura de B, también se conoce como que B es una
extensión de A.
Definición 1.19. Sea A = 〈A, I〉, una ρ-estructura y sea B = 〈B, J〉 una
ρ′-estructura, donde I y J son funciones de interpretación. Decimos que A
es el reducto de B a ρ o bien que B es una expansión de A a ρ′ sii
i) ρ ⊆ ρ′
ii) A = B
iii) I = J|ρ (la función de interpretación I, es igual a la restricción de J al
tipo ρ).
Ejemplo:
Consideremos la siguiente estructura B = 〈N, <,+, ·, 0〉, donde:
N = Conjunto de los números naturales.
<= (P2)
A, la relación menor,
+ = ( f2,1)
A, la función suma,
1.1 ANTECEDENTES 21
· = ( f2,2)
A, la función producto,
0 = (c0)
A, el cero.
Entonces una subestructura de B, es A = 〈2N, <,+, ·, 0〉, donde
2N = {n ∈N : tal que n es par}, la relación menor y las funciones de suma
y producto son restringidas a 2N. Ası́ A ⊆ B
A su vez la estructura C = 〈2N,+, 0〉 es el reducto de A, al tipo ρ tipo de C,
ρ = { f2,1, c0} ⊆ {P2, f21, f22, c0} tipo de A.
Veamos ahora una de las relaciones más importantes entre estructuras,
la de homomorfismo.
Definición 1.20. Sean A = 〈A, I〉 y B = 〈B, J〉 dos ρ-estructuras, h es un
homomorfismo de A en B sii
i) h es una función de A en B; h : A→ B,
ii) Para cadaPn ∈ ρ y cada a1, . . . , an ∈ A,
〈a1, . . . , an〉 ∈ P
A
n sii 〈h(a1), . . . , h(an)〉 ∈ P
B
n ,
iii) Para cada fn ∈ ρ y cada a1, . . . , an ∈ A,
h( fAn (a1, . . . , an)) = f
B(h(a1), . . . , h(an)),
iv) Para cada c ∈ ρ, h(cA) = cB.
Definición 1.21. Sea h un homomorfismo de A en B, entonces decimos
que:
i) h es un monomorfismo sii h es una función inyectiva,
ii) h es un epimorfismo sii h es una función suprayectiva,
iii) h es un isomorfismo sii h es una función biyectiva.
Cuando haya un isomorfismo de A sobre B, diremos que A y B son
isomorfas y lo denotaremos de la siguiente manera: A � B.
Ejemplos:
1.- Homomorfismo
A = 〈Z,+, ·〉 y B = 〈Z2,⊕.⊙〉 son homomorfas, donde: Z es el conjunto
de los enteros, Z2 el conjunto de los enteros módulo 2, los sı́mbolos +, ·
denotan las operaciones de suma y producto usuales, y ⊕,⊙ se definen de
la siguiente manera:
22 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
⊕ 0 1
0
1
0 1
1 0
⊙ 0 1
0
1
0 0
0 1
definiendo el homomorfismo, h : Z → Z2, como sigue:
h(z) =
{
0, si z es par;
1, si z es impar.
ası́,
h(2 + 3) = h(5) = 1 = 0 ⊕ 1 = h(2) ⊕ h(3),
y
h(2 · 3) = h(6) = 0 = 0 ⊙ 1 = h(2) ⊙ h(3).
2.- Isomorfismo
Sea A el conjunto de las potencias enteras de 3, A = {3 j : j ∈ Z} entonces
〈A, ·〉 � 〈Z,+〉, definiendo el isomorfismo h de la siguiente manera: si
3 j ∈ A con j ∈ Z, entonces h(3 j) = j. Observar que
h(3 j · 3k) = h(3 j+k) = j + k = h(3 j) + h(3k).
Proposición 1.5. A es una subestructura de B = 〈B, J〉, es decir, A ⊆ B sii la
función identidad i : A→ B, es un monomorfismo.
Demostración: Ejercicio ⋄
Pasaremos ahora a la demostración del teorema del homomorfismo,
que bajo ciertas condiciones, nos permite trasladar un enunciado, que se
cumple en una cierta estructura, a otra estructura homomorfa.
Teorema 1.6. (Teorema del Homomorfismo, TH).
Sea h un homomorfismo de A en B y S ∈ NA, h ◦ S ∈ NB denota la composición
de funciones. Entonces para todo término t y toda fórmula α:
i) h(tA [S]) = tB [h ◦ S].
1.1 ANTECEDENTES 23
ii) Si α no tiene cuantificadores ni sı́mbolo ≈, entonces
A |= α [S] sii B |= α [h ◦ S].
iii) Si h es un monomorfismo y α no tiene cuantificadores, entonces
A |= α [S] sii B |= α [h ◦ S].
iv) Si h es un epimorfismo y α no tiene sı́mbolo ≈, entonces
A |= α [S] sii B |= α [h ◦ S].
v) Si h es un isomorfismo, entonces
A |= α [S] sii B |= α [h ◦ S].
Demostración:
Veamos antes la necesidad de la hipótesis:
1.- Supongamos que α sı́ tiene cuantificadores, sea A = 〈1N,PA〉, donde
1N = {n ∈ N : n es impar }, con PA = ∅ y B = 〈N,PB〉, con PB = {n ∈ N :
n es par }. Es fácil ver que A ⊆ B, y por la Proposición (3), i : A→ B es un
monomorfismo, sea α = (∃xP(x)), tendrı́amos que: A 6|= (∃xP(x)) [S], pero
B |= (∃xP(x)) [i ◦ S].
2.- Supongamos ahora que α sı́ tiene sı́mbolo ≈, sea A = 〈Z,+, ·〉 y sea
B = 〈Z2,⊕,⊙〉, donde Z2 = {0, 1}. Ahora bien sea α = ¬(v1 ≈ v2) y
definamos la siguiente función, h : Z→ Z2, tal que:
h(z) =
{
0, si z es par;
1, si z es impar.
Con esto garantizamos que h es un epimorfismo, luego tendrı́amos
A |= ¬(v1 ≈ v2) [2, 4], mientras que B 6|= ¬(v1 ≈ v2) [h ◦ [2, 4]] o sea
B 6|= ¬(v1 ≈ v2) [0, 0].
Ahora demostraremos la suficiencia de la hipótesis; haremos una prueba
por inducción sobre la formación de términos y fórmulas;
i) Para el caso de los términos tenemos:
Si t = vi,
h(tA [S]) = h(vAi [S]) = h(S(i)) = (h ◦ S)(i) = v
B
i [h ◦ S].
24 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Si t = c,
h(tA [S]) = h(cA [S]) = h(cA) = cB = cB [h ◦ S].
Si t = f (t1, . . . , tn) y suponemos que se cumple i) para toda ti,
h(tA [S]) = h( f (t1, . . . , tn)
A [S]) = h( fA(tA
1
[S], . . . tAn [S]))
= fB(h(tA
1
[S]), . . . , h(tAn [S])) = f
B(tB
1
[h ◦ S], . . . , tBn [h ◦ S])
= f (t1, . . . , tn)
B [h ◦ S].
Paso inductivo para negación y disyunción de ii) a v). Para α, β
fórmulas, supongamos: A |= α [S] sii B |= α [h ◦ S],
A |= ¬α [S] sii A 6|= α [S] . . . . . . . . . . . . . . . . . . . . . . . . . def. de satisfacción,
sii B 6|= α [h ◦ S] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por hipótesis inductiva,
sii B |= ¬α [h ◦ S] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . def. de satisfacción.
A |= (α ∨ β) [S]
sii A |= α [S] o A |= β [S] . . . . . . . . . . . . . . . . . . . . por def. de satisfacción,
sii B |= α [h ◦ S] o B |= β [h ◦ S] . . . . . . . . . . . . . por hipótesis inductiva,
sii B |= (α ∨ β) [h ◦ S] . . . . . . . . . . . . . . . . . . . . . . . por def. de satisfacción.
Ası́, para probar ii), solo resta demostrarlo para las atómicas sin igual-
dad:
A |= Pn(t1, . . . , tn) [S]
sii 〈tA
1
[S], . . . , tAn [S]〉 ∈ P
A
n . . . . . . . . . . . . . . por definición de satisfacción,
sii 〈h(tA
1
[S]), . . . , h(tAn [S])〉 ∈ P
B
n . . . . . . . . . . . . . por ser h homomorfismo,
sii 〈tB
1
[h ◦ S], . . . , tBn [h ◦ S]〉 ∈ P
B
n . . . . . . . . . . . . . . . . . . . . . . por la parte i),
sii B |= Pn(t1, . . . , tn) [h ◦ S] . . . . . . . . . . . . . . . . . . por def. de satisfacción.
Para probar iii), sólo resta demostrarlo para las atómicas con igualdad.
Supongamos que h es monomorfismo:
A |= (t1 ≈ t2) [S],
sii tA
1
[S] = tA2 [S] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por def. de satisfacción,
sii h(tA
1
[S]) = h(tA2 [S]) . . . . . . . . . . . . . . . . . . por ser h función e inyectiva,
sii tB
1
[h ◦ S] = tB2 [h ◦ S] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por la parte i),
sii B |= (t1 ≈ t2) [h ◦ S] . . . . . . . . . . . . . . . . . . . . por la def. de satisfacción.
Para probar el caso iv) y el v), sólo resta demostrar el caso de cuantifi-
cación, α = (∃viβ). Para iv) supongamos que β no tiene igualdad (≈), y que
la función h es epimorfismo, para el caso v) β es cualquier fórmula y h es
isomorfismo, entonces:
1.1 ANTECEDENTES 25
A |= (∃viβ) [S]
sii hay a ∈ A, tal que A |= β [S(i/a)], . . . . . . . . . . . . . . . def. de satisfacción,
sii hay a ∈ A, tal que B |= β [h ◦ (S(i/a))] . . . . . . . . . . . .por H.I. con S(i/a),
sii hay a ∈ A, tal que B |= β [(h ◦ S)(i/h(a))]
Obsérvese que h ◦ (S(i/a)) = (h ◦ S)(i/h(a)), pues
h ◦ (S(i/a)) j =
{
h(a), si j = i;
h(S j), si j , i.
y,
(h ◦ S)(i/h(a)) j =
{
h(a), si j = i;
h(S j), si j , i.
sii hay b ∈ B, tal que B |= β [(h ◦ S)(i/b)]. . . . . . . . . . (⇒) con b = h(a) ∈ B,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (⇐) porque h es epimorfismo.
sii B |= (∃viβ) [h ◦ S] . . . . . . . . . . . . . . . . . . . . . . . . . por def. de satisfacción.
⋄
Antes de ver algunos corolarios, requerimos de una definición más.
Definición 1.22. Si para todo ρ-enunciado σ, sucede que A |= σ sii B |= σ,
decimos entonces que A y B son elementamente equivalentes y lo denotare-
mos de la siguiente manera:
A ≡ B.
Ası́ pues, dos ρ-estructuras son elementalmente equivalentes si hacen
verdaderos a los mismos enunciados del lenguaje de su tipo.
Corolario 1.6.1. Si A � B, entonces A ≡ B
Demostración:
Supongamos que A � B y sea σ un enunciado; por la parte v) del TH,
tenemos que A |= σ [S] sii B |= σ [h ◦ S]; ahora como σ es un enunciado
(no tiene variables libres), las sucesiones son irrelevantes (Proposición 1),
por lo que tendremos de hecho que A |= σ sii B |= σ o sea A ≡ B. ⋄
Corolario 1.6.2. Si α no tiene cuantificadores y A ⊆ B, entonces para cualquier
S ∈ NA,
A |= α [S] sii B |= α [S].
26 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Demostración:
Sea i la función identidad (inclusión) de A en B, i : A → B; como A ⊆ B,
tenemos que i es un monomorfismo y por iii) del TH, tenemos que:
A |= α [S] sii B |= α [i ◦ S],
puesto que [i ◦ S] = S, tenemos finalmente que:
A |= α [S] sii B |= α [S].
⋄
Corolario 1.6.3. Si A es ρ-estructura y E un conjunto tal que A ⊆ E, entonces
hay una ρ-estructura C, con universo E y tal que para todo enunciado α que no
tenga el sı́mbolo de igualdad, se tiene que:
A |= α sii C |= α.
Demostración:
Sea a0 ∈ A y sea h : E→ A, definida de la siguientemanera:
h(x) =
{
x, si x ∈ A ⊆ E;
a0, si x ∈ E \ A.
Definiremos ahora la estructura C sobre E:
a) 〈e1, . . . , en〉 ∈ P
C
n sii 〈h(e1), . . . , h(en)〉 ∈ P
A
n .
b) f C(e1, . . . , en) = f
A(h(e1), . . . , h(en)).
c) cC = cA.
Hemos definido la nueva estructura C, usando la estructura dada, es inme-
diato de la definición de C, que h es homomorfismo de C en A. Ası́, siendo
h un epimorfismo y α sin sı́mbolo ≈, por la parte iv) del TH, se obtiene que:
C |= α [S] sii A |= α [h ◦ S];
obsérvese que h ◦ S ∈ NA, aunque S ∈ NE; ya que α es enunciado tenemos
que:
C |= α sii A |= α.
1.1 ANTECEDENTES 27
⋄
Definición 1.23. Si A = 〈A, I〉 es una ρ-estructura, el cardinal de A es el
cardinal de su universo: |A|.
Corolario 1.6.4. (Teorema de Lowenheim Skolem para Lógica sin identi-
dad)
Si Σ es un conjunto de enunciados sin sı́mbolo ≈, que tiene un modelo A de
cardinal κ, entonces Σ tiene un modelo C de cualquier cardinal λ > κ.
Demostración:
Sea λ > κ. Si λ es cardinal finito, sea B un conjunto ajeno con A, de cardinal
λ\κ. Y si λ es infinito, sea B un conjunto de cardinal λ. Entonces E = B∪A
cumple las hipótesis del Corolario 4.3 de donde hay una estructura C con
universo E tal que: A es modelo de Σ sii C es modelo de Σ; por lo que C es
modelo de Σ y el cardinal de C es igual al cardinal de E que es λ. ⋄
Identidad y axiomatización
El siguiente corolario nos muestra un hecho interesante: supongamos que
la “igualdad”, la interpretamos como una relación binaria; ¿Serı́a entonces
posible, dar un conjunto de propiedades expresadas en Lρ (axiomas de
igualdad), de modo que si son verdaderas en esta interpretación, entonces
la interpretación de la igualdad sea necesariamente la identidad?
Esto no se puede hacer, es decir, la igualdad como identidad no es
definible axiomáticamente.
Definición 1.24. Diremos que la identidad es axiomáticamente definible sii hay
una letra predicativa o sı́mbolo de relación binario P, y un conjunto Σ de
ρ-enunciados, con P ∈ ρ, tales que:
i) En todo σ ∈ Σ, no aparece el sı́mbolo ≈.
ii) Para toda ρ-estructura A, donde PA = {(a, a) : a ∈ A}, A es un modelo de
Σ.
iii) Para cualquier ρ-estructura B, si B es modelo de Σ, entonces
PB = {(b, b) : b ∈ B}. Es decir, PB es la identidad.
Corolario 1.6.5. La relación de identidad no es axiomáticamente definible.
28 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Demostración:
Supongamos que la identidad sı́ fuera axiomáticamente definible, y sean
P y Σ, tales que cumplen con la definición anterior. Considérese ahora el
enunciado siguiente:
∃v0,∃v1, . . . ,∃vn−1(
n−1
∧
i, j
¬P(vi, v j) ∧ ∀w(
n−1
∨
i=0
P(w, vi))),
que se abrevia: (∃!n) “hay exactamente n elementos”.
Sea A = {1, . . . , 7} ⊆ E = {1, . . . , 8}, sea A una ρ-estructura con dominio A tal
que PA = {(a, a) : a ∈ A}; por el corolario 4.3 (TH), hay una ρ-estructura C,
tal que E es el dominio de C, y para cualquier ρ-enunciado σ, sin sı́mbolos
de igualdad:
A |= σ sii C |= σ,
en particular A |= ∃!7 sii C |= ∃!7. Pero por hipótesis, A |= σ para todo
σ ∈ Σ; ahora por el corolario 4.3 (TH); C |= σ, para todo σ ∈ Σ, y por la
clausula iii), de la definición de definibilidad axiomatica de la identidad,
PC debe ser la identidad por lo que E, debe tener exactamente 7 elementos,
¡pero tiene 8!.
⋄
1.2. EQUIVALENCIAS DEL TEOREMA DE COMPACIDAD 29
1.2 Equivalencias del Teorema de Compacidad
Recordemos que si Σ es un conjunto de ρ-enunciados, decimos que una
ρ-estructura A es un modelo de Σ sii A |= σ, para todo σ ∈ Σ. (Def.
1.12). Recordemos también que los sı́mbolos no lógicos son los sı́mbolos
relacionales, funcionales y constantes (Def. 1.1 y Def. 1.2).
En esta sección, presentamos formas equivalentes del Teorema de Com-
pacidad.
Definición 1.25. Decimos que un conjunto de ρ-enunciados Σ, es satisfaci-
ble, sii Σ tiene modelo.
Definición 1.26. Un conjunto de enunciados Σ, es finitamente satisfacible, sii
todo subconjunto finito de Σ es satisfacible.
Definición 1.27. Sea L un lenguaje de primer orden y sea Σ un conjunto de
fórmulas. Definimos:
1) El tipo de Σ, τ(Σ) como el conjunto
τ(Σ) = {s : s es sı́mbolo no lógico de L y s
aparece en alguna fórmula de Σ}.
En particular, τ(φ) denota a τ({φ}).
2) Σ es de tipo ρ sii τ(Σ) ⊆ ρ. En particular, φ es de tipo ρ sii τ(φ) ⊆ ρ.
Definición 1.28. Un conjunto de ρ-enunciados Σ, se llama completo sii para
cualquier ρ-enunciado σ, σ ∈ Σ o ¬σ ∈ Σ.
Ejemplo:
Dada A estructura, TeoA = {σ : σ enunciado y A |= σ} es completo. TeoA
se llama la Teorı́a de A.
Definición 1.29. Un conjunto de ρ-enunciados Σ es maximal finitamente
satisfacible, sii Σ es finitamente satisfacible y para todo ∆ conjunto de enun-
ciados finitamente satisfacible si Σ ⊆ ∆, entonces Σ = ∆.
30 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Definición 1.30. Sea Σ un conjunto de fórmulas, decimos que Σ es cerrado
bajo testigos, sii para toda fórmula (∃vα) ∈ Σ hay una constante c ∈ τ(Σ), tal
que: (α)vc ∈ Σ.
Teorema de Compacidad
Sea Σ un conjunto de ρ-enunciados. Σ es finitamente satisfacible sii Σ es
satisfacible.
Recordemos que la idea de la demostración del Teorema de Compaci-
dad es la siguiente:
Partir de un conjunto de enunciados finitamente satisfacible, “completar y
cerrar bajo testigos” dicho conjunto, de modo que siga siendo finitamente
satisfacible; a continuación iterar los dos pasos anteriores hasta un mo-
mento en que obtengamos un conjunto finitamente satisfacible, completo
y cerrado bajo testigos, el cual veramos que es satisfacible construyéndole
un modelo.
Aunque la prueba que presentaremos en la siguiente sección está hecha
para enunciados, al final veremos que se puede generalizar a fórmulas.
Proposición 1.7. Las siguientes afirmaciones son equivalentes:
i) Para todo conjunto de enunciados Σ, Σ es finitamente satisfacible sii Σ es
satisfacible.
ii) Para todo conjunto de enunciados Σ ∪ {φ}, Σ |= φ sii hay Σ0 ⊆ Σ, finito tal
que Σ0 |= φ.
iii) Para todo conjunto de enunciados Σ, Σ es finitamente satisfacible sii hay un
conjunto de enunciados ∆, finitamente satisfacible tal que Σ ⊆ ∆, ∆ es maximal
finitamente satisfacible y cerrado bajo testigos.
Demostración:
i)⇒ ii)
Supongamos i). Sea Σ ∪ {φ} un conjunto de enunciados.
⇒) Σ |= φ. Entonces Σ ∪ {¬φ} no tiene modelo, de donde hay un subcon-
junto finito Σ0 de Σ tal que Σ0 ∪ {¬φ} no tiene modelo, entonces Σ0 |= φ.
⇐) Es inmediato que si hay Σ0 ⊆ Σ, finito tal que Σ0 ⊆ Σ tal que Σ0 |= φ,
entonces Σ |= φ.
ii)⇒ iii)
⇒) Supongamos la contrapositiva de la parte fuerte de ii), es decir, suponga-
mos que: dadoΣ∪{φ}, un conjunto de enunciados, si para todo subconjunto
finito Σ0 de Σ, Σ0 6|= φ, entonces Σ 6|= φ. Sea Σ un conjunto de enunciados
1.2. EQUIVALENCIAS DEL TEOREMA DE COMPACIDAD 31
finitamente satisfacible, entonces para todo Σn ⊆ Σ, finito, Σn 6|= ∃x(x 0 x),
entonces por hipótesis Σ 6|= ∃x(x 0 x), de donde hay un modelo A0 de Σ.
Para cada a ∈ A universo de A0 sea ca una nueva constante distinta y
sea C = {ca|a ∈ A}. Sea A la expansión de A0 al tipo τ(A) = τ(A0) ∪ C donde
cada ca se interpreta como a y el universo de A es A, el mismo de A0. Es
claro que A también es modelo de Σ.
Sea ∆ = Teo(A) = {σ : σ enunciado y A |= σ}, entonces:
1) Σ ⊆ ∆, pues si σ ∈ Σ, entonces A |= σ y σ ∈ ∆.
2) ∆ es finitamente satisfacible, ya que A es modelo de ∆.
3) ∆ es maximal finitamente satisfacible, pues si σ es un enunciado tal que
σ < ∆, entonces ∆ ∪ {σ} no es finitamente satisfacible: Por definición de
∆ = Teo(A),
A 6|= σ ⇒ A |= ¬σ ⇒ ¬σ ∈ ∆ y {¬σ, σ} ⊆ ∆ ∪ {σ}.
Pero entonces {¬σ, σ}, es un subconjunto finito de ∆∪ {σ} que no es satisfa-
cible.
4) ∆ es cerrado bajo testigos, pues si (∃vα) ∈ ∆ entonces A |= (∃vα) de
donde hay a ∈ A universo de A tal que A |= α[a] y entonces A |= (α)vca por lo
que hay una constante ca ∈ τ(∆) = τ(A) tal que (α)
v
ca
∈ ∆.
⇐) Es inmediato que si ∆ es maximal finitamente satisfacible, tal que
Σ ⊆ ∆, entonces Σ es finitamente satisfacible.
iii)⇒ i)
⇒) La prueba de esta parte, requiere de trabajo adicional que es de hecho
la pruebadel teorema de compacidad, que se hará en la sección 3 de este
capı́tulo, ya que iii) será un resultado previo que ahı́ se demostrará.
⇐) Si Σ es satisfacible entonces es finitamente satisfacible, pues un modelo
de Σ, lo es para todo subconjunto finito de Σ.
⋄
32 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
1.3 Prueba del Teorema de Compacidad
1.3.1 El Teorema de Compacidad
Lema 1.0. SiΣ es un conjunto de ρ-enunciados finitamente satisfacible, y φ es un
ρ-enunciado, entoncesΣ∪{φ} es finitamente satisfacible oΣ∪{¬φ} es finitamente
satisfacible.
Demostración:
Supongamos que no fuera ası́, es decir, que Σ fuera finitamente satisfacible
y que no obstante, ni Σ ∪ {φ} ni Σ ∪ {¬φ}, fueran finitamente satisfacibles,
esto significarı́a que tendrı́amos: Γ1, Γ2 ⊆ Σ, ambos finitos, tales que
Γ1 ∪ {φ} y Γ2 ∪ {¬φ} no serı́an satisfacibles, pero entonces Γ1 ∪ Γ2 ⊆ Σ, es
finito y serı́a satisfacible, de aquı́ que habrı́a un modelo de (Γ1 ∪ Γ2) ∪ {φ}
o de (Γ1 ∪ Γ2) ∪ {¬φ}, lo cual contradice que Γ1 ∪ {φ} y Γ2 ∪ {¬φ} no son
satisfacibles. ⋄
Corolario . Sea Σ conjunto de enunciados, entonces las siguientes afirmaciones
son equivalentes:
a) Σ es completo y finitamente satisfacible.
b) Σ es maximal finitamente satisfacible.
Demostración:
a)⇒ b). Supongamos que Σ es completo y finitamente satisfacible. Sea ∆
un conjunto de enunciados tal que Σ ⊆ ∆. Si Σ , ∆, sea φ ∈ ∆ \Σ, entonces
¬φ ∈ Σ por lo que {φ,¬φ} ⊆ ∆ y ∆ no pueden ser finitamente satisfacible.
b) ⇒ a). Supongamos que Σ es maximal finitamente satisfacible. Sea φ
tal que φ < Σ; entonces Σ , Σ ∪ {φ} y Σ ⊂ Σ ∪ {φ} de donde Σ ∪ {φ}
no es finitamente satisfacible. Como Σ es finitamente satisfacible, por el
Lema 0, Σ∪ {¬φ} es finitamente satisfacible y como contiene a Σ, entonces
Σ = Σ ∪ {¬φ}, de donde ¬φ ∈ Σ y ası́ Σ es completo. ⋄
Lema 1.1. Si Σ es un conjunto de enunciados finitamente satisfacible, entonces
hay un conjunto Γ, con las siguientes propiedades:
i) Σ ⊆ Γ.
ii) τ(Γ) = τ(Σ).
1.3. PRUEBA DEL TEOREMA DE COMPACIDAD 33
iii) Γ es completo.
iv) Γ es finitamente satisfacible.
Demostración: Usaremos el Lema de Zorn. Sea
A = {∆ : ∆ es un conjunto de enunciados de tipo τ(Σ),Σ ⊆ ∆ y
∆ es finitamente satisfacible }
Entonces 〈A,⊆〉 es un conjunto parcialmente ordenado , ∅. La cadena
vacı́a tiene como cota a Σ ∈ A. Sea C una cadena , ∅ en 〈A,⊆〉; es decir
C ⊆ A tal que 〈C,⊆〉 es un conjunto totalmente ordenado. Es claro que
∀∆ ∈ C, ∆ ⊆
⋃
C, por lo que
⋃
C es una cota superior de C. Veamos que
⋃
C ∈ A.
Debe ser claro que
⋃
C es un conjunto de enunciados de tipo τ(Σ) y
que Σ ⊆
⋃
C (pues Σ ⊆ ∆, ∀∆ ∈ C).
⋃
C es finitamente satisfacible pues si
no, habrı́a un B ⊆
⋃
C, B finito y no satisfacible y si B = {α1, . . . , αn} ⊆
⋃
C,
entonces ∀i = 1, . . . , n, αi ∈ ∆i ∈ C (para algún ∆i) y como los ∆i están
totalmente ordenados por ⊆, hay un máximo ∆i0 tal que B ⊆ ∆i0 y entonces
∆i0 no es finitamente satisfacible!. Ası́ pues
⋃
C ∈ A.
Ahora, por el Lema de Zorn, A tiene un elemento maximal respecto a la
relación ⊆, digamos Γ ∈ A. Entonces τ(Γ) = τ(Σ), Σ ⊆ Γ y Γ es finitamente
satisfacible maximal, de donde por el Corolario del Lema 0, Γ es completo
y finitamente satisfacible. ⋄
Obsérvese que por el Corolario del Lema 0, el Γ maximal finitamente
satisfacible obtenido es completo y finitamente satisfacible. Obsérvese
también que esto prueba el inciso iii) de la Proposición 1.5.
Notación:
1.- ℵ0 denota el cardinal de los conjuntos numerables que es el menor con-
junto infinito, ası́ |A| ≥ ℵ0 significa que el conjunto A tiene cardinal infinito
y |A| < ℵ0 que tiene cardinal finito.
2.-Algunas veces para abreviar la escritura de finitamente satisfacible, uti-
lizaremos “fin.sat.”
Lema 1.2. Si Σ es un conjunto de enunciados finitamente satisfacible, entonces
hay un conjunto Ω, con las siguientes propiedades:
i) Σ ⊆ Ω.
ii) Ω es cerrado bajo testigos.
iii) Si |Σ| ≥ ℵ0, entonces |Σ| = |Ω|.
iv) Ω es finitamente satisfacible.
34 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Demostración:
Demos primero el conjuntoΩ; para ello definamos por recursión, sobre los
números naturales, los conjuntos Ωn, para n ∈ N, como sigue:
Ω0 = Σ.
Supongamos definido Ωn, para n ≥ 0.
Para cada σ ∈ [Ωn \
⋃
m<nΩm], sea cσ una constante tal que:
cσ < τ(Ωn), y si σ , σ
′, entonces cσ , cσ′ .
Para cada enunciado σ ∈ [Ωn \
⋃
m<nΩm], sea:
σ∗ =
{
(α)vcσ , cuando σ = (∃vα);
σ , en otro caso.
Definimos
Ωn+1 = Ωn
⋃
{σ∗ : σ∗ , σ, y σ ∈ [Ωn \
⋃
m<n
Ωm]}.
Sea Ω =
⋃
n∈NΩn. Es claro que si n < m, Ωn ⊆ Ωm y τ(Ωn) ⊆ τ(Ωm).
Veamos ahora que en efecto, Ω cumple con las propiedades del lema:
i) Σ ⊆ Ω, pues Σ = Ω0 ⊆
⋃
n∈NΩn.
ii) Ω es cerrado bajo testigos.
Supongamos que (∃vα) ∈ Ω =
⋃
n∈NΩn, luego hay un n ∈ N, tal que
(∃vα) ∈ Ωn. Entonces hay un mı́nimo con esta propiedad, sea k tal mı́nimo.
Por lo tanto (∃vα) ∈ [Ωk \
⋃
m<kΩm], luego:
(∃vα)∗ = (α)vc(∃vα) , (∃vα),
y entonces
(∃vα)∗ = (α)vc(∃vα) ∈ Ωk+1 ⊆ Ω y c(∃vα) ∈ τ(Ωk+1) ⊆ τ(Ω).
Ası́ pues, hay una constante c(∃vα), tal que:
(α)vc(∃vα) ∈ Ω y c(∃vα) ∈ τ(Ω).
iii) Supongamos Σ infinito. Es fácil ver que |Ωn| = |Σ|, ∀n ∈ N, por
inducción sobre N.
|Ω| = |
⋃
n∈N
Ωn| = ℵ0|Ωn| = |Σ|.
1.3. PRUEBA DEL TEOREMA DE COMPACIDAD 35
iv) Ω es finitamente satisfacible. Sea Γ0 ⊆ Ω, Γ0 finito; hay que demos-
trar que Γ0 es satisfacible. Como Γ0 es finito,
Γ0 = {σ1, . . . , σn} ⊆
⋃
n∈N
Ωn,
por lo tanto, para cada k = 1, . . . , n, hay un nk ∈ N, tal que σk ∈ Ωnk , sea
m = max{nk : k = 1, . . . , n} entonces, Γ0 ⊆ Ωm.
Bastará probar queΩm es fin.sat. para todo m ∈N, para tener que Γ0 es
satisfacible:
Para m = 0, Ω0 = Σ es fin.sat. por hipótesis.
Supongamos que Ωn es fin.sat. para n ≥ 0. Sea ∆ ⊆ Ωn+1, ∆ finito
veamos que ∆ es satisfacible. Como
Ωn+1 = Ωn ∪ {σ
∗ : σ∗ , σ y σ ∈ [Ωn \
⋃
m<n
Ωm]},
entonces ∆ = Γ ∪ {σ∗
1
, . . . , σ∗r}, con Γ finito y Γ ⊆ Ωn, además es claro que
σi ∈ [Ωn \
⋃
m<nΩm], y σi = (∃viαi). Luego por hipótesis inductiva Γ ∪
{σ1, . . . , σr} ⊆ Ωn es satisfacible, digamos por una estructura A de tipo
τ(Γ ∪ {σ1, . . . , σr}). Por lo tanto: A |= (∃viαi), entonces para cada S ∈
N A y
cada i = 1, . . . , r, escogemos ai ∈ A, universo de A, tal que A |= αi [S(i/ai)],
las cuales necesariamente existen en A, ya que A es modelo de (∃viαi) para
cada i = 1, . . . , r. Ahora consideremos la siguiente expansiónB deA al tipo
τ(Γ ∪ {σ1, . . . , σr}) ∪ {cσi : i = 1, . . . , r},
B = 〈A, a1, . . . , ar〉, donde ai = c
B
σi
, claramente para cada i y para cada
S ∈ NA,
B |= αi [s(i/ai)] sii B |= (αi)
vi
cσi
[s]
por el teorema de sustitución; por lo tanto, B |= (αi)
vi
cσi
y además B |= Γ, de
donde B |= ∆. Con esto hemos probado que ∆ es satisfacible, con lo que
Ωn+1 es finitamente satisfacible, para toda n, obteniendo iv). ⋄
Lema 1.3. Si Σ es un conjunto de enunciados finitamente satisfacible, completo
y cerrado bajo testigos, entonces Σ tiene un modelo A, de cardinal menor o igual
que el cardinal de Σ, es decir, |A| ≤ |Σ|.
Demostración:
Obsérvese que si Σ es fin.sat., completo y cerrado bajo testigos, entonces Σ
36 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
es infinito y τ(Σ) tiene una infinidad de constantes; esto se ve facilmente
si se consideran todos los enunciados de la forma ∃x(x ≈ x), para cada
variable x. Sea
A′ = {t : t es un término de tipo τ(Σ) y t no tiene variables}.
Definimos una relación r sobre A′ como sigue: Para t, t′ ∈ A′, (t, t′) ∈ r sii
(t ≈ t′) ∈ Σ. Es fácil verificar que r es una relación de equivalencia.
Sea t = {u ∈ A′ : (t,u) ∈ r} y definamos A = {t : t ∈ A′} = A′/r (el cociente
de A′ módulo r).
Ahora definamos para cada Pn, fn, c ∈ τ(Σ); P
A
n , f
A
n , c
A sobre A:
a) Para cada t1, . . . , tn ∈ A y Pn ∈ τ(Σ),
〈t1, . . . , tn〉 ∈ P
A
n sii Pn(t1, . . . , tn) ∈ Σ.
b) Para cada fn ∈ τ(Σ), f
A
n (t1, . . . , tn) = ( fn(t1, . . . , tn)).
c) Para cada constante c ∈ τ(Σ), cA = c.
Sea A = 〈A,PAn , f
A
n , c
A〉, con Pn, fn, c ∈ τ(Σ). Se deja como ejercicio
verificar que estas definiciones no dependen de representantes.
Sublema 1.3.1. tA = t, paratoda t ∈ A′.
Demostración: (Por inducción sobre los términos sin variables)
i) Si t = c, tA = cA = c, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por definición de A.
ii) Si t = fn(t1, . . . , tn) y suponemos por hipótesis inductiva que para todo
i = 1, . . . , n: tA
i
= ti. Tenemos que:
tA = [ fn(t1, . . . , tn)]
A = fAn (t
A
1
, . . . , tAn ), . . . . . . . . . . . . def. de interpretación,
= fAn (t1, . . . , tn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.I.
= ( fn(t1, . . . , tn)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . definición de A.
Sublema 1.3.2. Para todo t ∈ A, hay c ∈ τ(Σ), tal que t = c, es decir, c ∈ t.
Demostración: Para todo t ∈ A′, sucede que (t ≈ t) ∈ Σ, por ser completo
y finitamente satisfacible, y de aquı́ que (∃v0(v0 ≈ t)) ∈ Σ (pues de lo
contrario, por la completud de Σ tendrı́amos que ¬(∃v0(v0 ≈ t)) ∈ Σ, y
este enunciado junto con (t ≈ t) es no satisfacible, contradiciendo que Σ es
1.3. PRUEBA DEL TEOREMA DE COMPACIDAD 37
finitamente satisfacible). Ahora bien, como Σ es cerrado bajo testigos, hay
una c ∈ τ(Σ), tal que (v0 ≈ t)
v0
c ∈ Σ, ed. (c ≈ t) ∈ Σ. Luego (c, t) ∈ r y por lo
tanto c ∈ t o c = t.
Veamos ahora que para todo enunciado α, de tipo τ(Σ):
α ∈ Σ sii A |= α.
Demostración: (Se hará por inducción sobre la longitud de enunciados, es
decir, sobre el número de sı́mbolos que ocurren en cada enunciado).
Supóngase que la proposición se cumple, para α con menos de n sı́mbolos.
Sea α con n sı́mbolos (long[α] = n), tenemos cuatro casos:
1) α es atómica:
i) α = (t1 ≈ t2)
A |= α sii A |= (t1 ≈ t2)
sii tA
1
= tA2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .definición de satisfacción,
sii t1 = t2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por el sublema 1.3.1,
sii (t1, t2) ∈ r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por la definición de t,
sii (t1 ≈ t2) ∈ Σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por la definición de r.
ii) α = P(t1, . . . , tn)
A |= α sii A |= P(t1, . . . , tn)
sii 〈tA
1
, . . . , tAn 〉 ∈ P
A . . . . . . . . . . . . . . . . . . . . . . . . . definición de satisfacción,
sii 〈t1, . . . , tn〉 ∈ P
A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .por el sublema 1.3.1,
sii P(t1, . . . , tn) ∈ Σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . por la definición de A.
2) α = ¬β
A |= α sii A |= ¬β
sii A 6|= β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . definición de satisfacción,
sii β < Σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por hipótesis inductiva,
sii ¬β ∈ Σ . . . . . . . . . . . . . . . . . . . . . . . . . .⇒) por hipótesis, Σ es completo,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⇐) por hipótesis, Σ es fin.sat.
3) α = (β ∨ γ)
A |= α sii A |= (β ∨ γ)
sii A |= β o A |= γ . . . . . . . . . . . . . . . . . . . . . . . . . definición de satisfacción,
sii β ∈ Σ o γ ∈ Σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . por hipótesis inductiva,
sii (β ∨ γ) ∈ Σ . . . . . . . . . . . . . .⇒) por hipótesis Σ es completo fin.sat. y
{β, γ, ¬(β ∨ γ)} no es satisfacible,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⇐) Σ es completo y fin.sat. y
38 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
{(β ∨ γ), ¬β, ¬γ} no es satisfacible.
4) α = (∃viβ)
A |= α sii A |= (∃viβ)
sii hay t ∈ A, tal que A |= β[S(i/t)], ∀S ∈ NA . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . por definición de satisfacción,
sii hay c ∈ A, tal que A |= β[S(i/c)], ∀S ∈ NA . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⇒) por sublema 1.3.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⇐) toda constante es término,
sii hay c ∈ τ(Σ), tal que A |= (β)vic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . por teorema sustitución con c = cA y def. de satisfacción.
sii hay c ∈ τ(Σ), tal que (β)vic ∈ Σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . HI, pues long[(β)vic ] = long[β] < long[(∃viβ)]
sii (∃viβ) ∈ Σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.⇒) porque Σ es completo, fin.sat. y {(β)vic , ¬(∃viβ)} no es satisfacible,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⇐) porque Σ es cerrado bajo testigos.
Con lo cual hemos probado que A es modelo de Σ. Finalmente, es claro
que |A| ≤ |A′| por ser A el cociente de A′ modulo r y como Σ es finitamente
satisafacible y completo, para cada t ∈ A′, t término sin variables de tipo
τ(Σ), el enunciado (t ≈ t) ∈ Σ de donde |A′| ≤ |Σ|. Ası́ pues |A| ≤ |Σ|. ⋄
Teorema 1.6. (Teorema de Compacidad)
Si Σ es un conjunto de enunciados finitamente satisfacible, entonces Σ tiene un
modelo de cardinal menor o igual que |Σ| + ℵ0.
Demostración:
Si ∆ es cualquier conjunto de enunciados fin.sat., denotamos:
ECOM(∆) = Γ del Lema 1.1 (TC) (Extensión completa).
ECBT(∆) = Ω del Lema 1.2 (TC) (Extensión cerrada bajo testigos).
SeaΣun conjunto de enunciados finitamente satisfacible. Ahora definimos
por recursión, para n ∈ N:
Σ0 = Σ,
Σ2n+1 = ECOM(Σ2n),
Σ2n+2 = ECBT(Σ2n+1).
Como dijimos anteriormente, extendemos completando y cerrando bajo
testigos, para ello definimos los Σn, que cumplen las propiedades que a
continuación veremos:
i) Σn ⊆ Σn+1. Esto es inmediato por la propiedad i) de los Lemas 1.1. y 1.2.
1.3. PRUEBA DEL TEOREMA DE COMPACIDAD 39
De aquı́ también se tiene que τ(Σn) ⊆ τ(Σn+1).
ii) Σn es finitamente satisfacible, para todo n ∈ N. Esto es inmediato por
la propiedad iv) de los Lemas 1.1 y 1.2.
iii) Σ2n+1 es completo. Es evidente por el Lema 1.1. (TC).
iv) Σ2n+2 es cerrado bajo testigos. Es evidente por el Lema 1.2. (TC).
Sea Σ∗ =
⋃
n∈N Σn, entonces Σ
∗ es finitamente satisfacible, completo y cerra-
do bajo testigos, es deir, Σ∗ cumple las hipótesis del Lema 1.3.
Demostración:
1) Σ∗ es finitamente satisfacible.
Esta propiedad se cumple por lo siguiente:
Σ∗ =
⋃
n∈N Σn y ya hemos probado en ii), que todo Σn es finitamente satis-
facible, y aunque en general, no es cierto que la unión de finitamente
satisfacibles es finitamente satisfacible, en este caso sı́ es cierto en virtud
de la propiedad anterior de que Σn ⊆ Σn+1, para todo n ∈ N.
2) Σ∗ es completo.
Sea σ del tipo τ(Σ∗). Por tanto σ es del tipo τ(Σn), para algún n ∈ N, y
de aquı́ se sigue por i) que σ es del tipo τ(Σ2m+1), para algún m ∈ N, tal que
2m ≥ n, y Σ2m+1 es completo por iii) por lo que σ ∈ Σ2m+1 o (¬σ) ∈ Σ2m+1 y
como Σ2m+1 ⊆ Σ
∗, entonces σ ∈ Σ∗ o (¬σ) ∈ Σ∗.
3) Σ∗ es cerrado bajo testigos.
Sea (∃v1α) ∈ Σ
∗. Por definición de Σ∗, (∃viα) ∈ Σn, para algún
n ∈ N, luego, por i): (∃viα) ∈ Σ2n+2, para algún n ∈ N, y por iv) hay una
c ∈ τ(Σ2n+2), tal que: (α)
vi
c ∈ Σ2n+2, es decir, hay una c ∈ τ(Σ
∗), tal que
(α)vic ∈ Σ
∗.
Ası́, Σ∗ cumple con las condiciones del Lema 1.3, y por lo tanto tiene un
modelo A, de tipo τ(Σ∗), tal que:
A |= α sii α ∈ Σ∗
y como Σ = Σ0 ⊆ Σ
∗, entonces A es un modelo de Σ, es decir, Σ es satisfa-
cible. Sea B = A|τ(Σ) el reducto de A al tipo τ(Σ), entonces B es un modelo
de Σ de su tipo. Recuérdese además que por el Lema 1.3, el cardinal de B
es menor o igual que el cardinal de Σ∗.
Ahora, hay que observar que |Σ∗| = |Σ| + ℵ0, por lo que el modelo B
obtenido para Σ tiene cardinal menor o igual que |Σ| + ℵ0.
Para entender lo anterior hay que observar que:
Si τ(Σ) es infinito, entonces |τ(Σ)| = |Σ|.
40 [Cap. 1.] EL TEOREMA DE COMPACIDAD PARA...
Si Σ es finito, entonces |Σ∗| = ℵ0.
Si Σ es infinito,