MLMA_U3_contenido - Gabriel Solís

Vista previa del material en texto

Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
1 
 
Universidad Abierta y a Distancia de México 
 
 
Licenciatura en Matemáticas 
 
 
8° Semestre 
 
 
Lógica matemática 
 
 
Unidad 3. Validez, completud y modelos en la lógica 
de primer orden 
 
 
Clave: 
05144845 
 
 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
2 
 
 
 
Unidad 3. Validez, completud y modelos en la lógica de primer orden ................................ 3 
Presentación de la unidad ........................................................................................................ 3 
Propósitos de la unidad ........................................................................................................... 3 
Competencia específica ........................................................................................................... 3 
3.1. Teoremas de validez y completud .................................................................................... 4 
3.1.1. Introducción al enunciado de los teoremas .............................................................. 4 
3.1.2. Demostración de los teoremas ................................................................................... 5 
3.1.3. Teorema de compacidad ........................................................................................... 16 
3.2. Modelos de teorías ........................................................................................................... 19 
3.2.1. Modelos finitos .......................................................................................................... 19 
3.2.2. Tamaño de modelos .................................................................................................. 24 
3.2.3. Teoremas de Löwenheim-Skolem ............................................................................ 24 
Cierre de la unidad .................................................................................................................. 28 
Para saber más ....................................................................................................................... 28 
Referencias bibliográficas ..................................................................................................... 29 
 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
3 
 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
 
 
Presentación de la unidad 
 
En esta unidad se establecerán dos teoremas importantes: la correctud del cálculo deductivo 
(Γ ⊢ 𝜑 ⟹ Γ ⊢ 𝜑) y su completud (Γ ⊨ 𝜑 ⟹ Γ ⊢ 𝜑). Luego será posible obtener varias 
conclusiones interesantes (incluyendo los teoremas de compacidad y de numerabilidad); así 
como el Teorema de Löwenheim-Skolem y sus demostraciones. 
 
 
Propósitos de la unidad 
 
Al término de esta unidad lograrás: 
 
 
 
 Presentar los teoremas de correctud y completud. 
 Brindar una demostración explicada de los 
teoremas de completud y correctud. 
 Presentar formas para determinar si una deducción 
es correcta o no 
 
 
Competencia específica 
 
 
 
Analiza propiedades de conjuntos de 
fórmulas de un lenguaje dado mediante el 
uso de los teoremas de validez, completud, 
compacidad y de Löwenheim-Skolem para 
determinar propiedades de modelos o 
estructuras donde son satisfactibles tales 
fórmulas. 
 
 
 
 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
4 
 
3.1. Teoremas de validez y completud 
 
En las unidades anteriores, en especial dentro del subtema 2.3 de la unidad 2, se hace 
referencia a un cálculo deductivo, el que se ha estado usando hasta ahora, en la cual se dieron 
ciertas normas o guías para éste y se han tenido las consecuencias. En tal tema se presentan 
dos resultados importantes respecto de este cálculo deductivo: su correctud y su completud. 
Puedes notar que, a lo largo de este contenido, el cálculo deductivo se escogió de forma 
arbitraria de entre los que cumplían ciertas condiciones que fueron necesarias, a partir de eso 
se tendrá que “algún” cálculo deductivo así es correcto y completo. 
 
 
3.1.1. Introducción al enunciado de los teoremas 
 
Se presentan los enunciados de los teoremas junto con comentarios de lo que se necesita para 
ellos y lo que implican. 
 
 
3.1.1.1. Teorema. [Correctud] 
Si Γ ⊢ 𝜑, entonces Γ ⊨ 𝜑. 
 
El teorema de correctud dice que las deducciones llevan únicamente a conclusiones “correctas”. 
La demostración de este teorema se basa en que los axiomas lógicos son lógicamente 
implicados por cualquier cosa y que el modus ponens preserva las implicaciones. En el 
siguiente tema se dará la demostración de este teorema. 
 
Como consecuencia de este teorema se tienen los siguientes corolarios. 
 
3.1.1.2. Corolario 
Si ⊢ (𝜑 ↔ 𝜓), entonces 𝜑 y 𝜓 son lógicamente equivalentes. 
 
3.1.1.3. Corolario 
Si 𝜑′ es una variante alfabética de 𝜑, entonces 𝜑 y 𝜑′ son lógicamente equivalentes. 
 
Para la siguiente definición recuerda que un conjunto Γ es consistente sii (si y sólo si) no hay 
ninguna fórmula 𝜑 tal que Γ ⊢ 𝜑 y Γ ⊢ ¬𝜑. 
 
3.1.1.1. Definición 
Un conjunto Γ es satisfactible sii hay algunas 𝔄 y 𝑠 tales que 𝔄 satisface a cada elemento de Γ 
con 𝑠. 
 
3.1.1.4. Corolario 
Si Γ es satisfactible, entonces Γ es consistente. 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
5 
Otro resultado importante es el teorema de completud, al que puedes entender como el inverso 
del teorema de completud y es más profundo que éste. El enunciado del teorema es el 
siguiente: 
 
3.1.1.5. Teorema. [Completud] (Gödel, 1930) 
(a) Si Γ ⊨ 𝜑, entonces Γ ⊢ 𝜑. 
(b) Cualquier conjunto de fórmulas consistente es satisfactible. 
 
De hecho se tiene que (a) y (b) son equivalentes, esto lo puedes demostrar usando que Γ ⊨ 𝜑 
sii Γ ∪ {¬𝜑} es insatisfactible y que Δ es satisfactible sii Δ ⊭⊥, donde ⊥ es alguna fórmula 
refutable insatisfactible, tal como ¬∀𝑥 𝑥 = 𝑥. De manera similar, el teorema de correctud es 
equivalente a que cualquier conjunto de fórmulas satisfactible es consistente. 
 
La demostración del teorema se hará (dada la equivalencia) sólo de (b) y se dará con un 
lenguaje numerable para luego presentar las modificaciones para poder hacerse con un 
lenguaje de mayor cardinalidad. Las ideas de la demostración están relacionadas con las de la 
demostración del teorema de compacidad de la lógica de enunciados: Se comienza con un 
conjunto consistente Γ, el cual se extiende en tres pasos a un conjunto Δ de fórmulas que 
cumple: 
 
i. Γ ⊆ Δ. 
ii. Δ es consistente y para cualquier fórmula 𝛼, 𝛼 ∈ Δ o (¬𝛼) ∈ Δ. 
iii. Para cualquier fórmula 𝜑 y variable 𝑥, hay una constante 𝑐 tal que 
 
(¬∀𝑥 𝜑 → ¬𝜑𝑐
𝑥) ∈ Δ 
 
Para el cuarto paso de la demostración se construye una estructura 𝔄 en la cual se satisfacen 
las fórmulas de Γ que no tengan =. |𝔄| es el conjunto de términos, y para un símbolo de 
predicado 𝑃: 
〈𝑡1, … , 𝑡𝑛〉 ∈ 𝑃
𝔄 𝑠𝑖𝑖 𝑃𝑡1 ⋯ 𝑡𝑛 ∈ Δ. 
 
En el quinto y sexto paso se cambia 𝔄 para que satisfaga las fórmulas que contienen el símbolo 
de igualdad. En el siguiente tema se abarca con detalle la demostración, presta más atención 
en un primer acercamiento a la descripción de los pasos para tener clara la estructura de la 
demostración para que en una segunda lectura revises cada punto para su mejorcomprensión. 
 
 
3.1.2. Demostración de los teoremas 
 
Para la demostración del teorema de compacidad se usará el siguiente lema. 
 
3.1.2.1. Lema 
Todo axioma lógico es válido. 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
6 
Demostración 
Para la demostración de este teorema debes recordar que en la actividad 2 de la unidad pasada 
demostraste que la generalización de una fórmula válida es válida. Así que basta considerar 
únicamente los axiomas lógicos que no sean generalizaciones de otros axiomas. 
 
Se examinan los diversos grupos de axiomas: 
Grupo 1 de axiomas. Tautologías. Para esto puedes ver que: 
Si 𝔄 es una estructura y si se tiene 𝑠: 𝑉 → |𝔄|, definiendo una asignación de verdad 𝑣 sobre el 
conjunto de las fórmulas primas mediante 
 
𝑣(𝛼) = 𝑉 𝑠𝑖𝑖 ⊨𝔄 𝛼[𝑠]. 
 
Entonces para cualquier fórmula (prima o no prima): 
 
�̅�(𝛼) = 𝑉 𝑠𝑖𝑖 ⊨𝔄 𝛼[𝑠]. 
 
Debes probar a detalle esto y con ello concluye que si Γ implica tautológicamente 𝜑, entonces Γ 
implica de manera lógica 𝜑. 
 
Por lo dicho antes, si ∅ implica tautológicamente 𝛼, entonces ∅ ⊨ 𝛼. 
 
Grupo 2 de axiomas. ∀𝑥 𝛼 → 𝛼𝑡
𝑥, donde 𝑡 se puede sustituir por 𝑥. Significativamente esto es 
más complejo de probar que el resto de los grupos. Primero considera un caso sencillo: se 
mostrará que ∀𝑥 𝑃𝑥 → 𝑃𝑡 es válida. Suponga que 
 
⊨𝔄 ∀𝑥 𝑃𝑥[𝑠]. 
 
Entonces, para cualquier 𝑑 en |𝔄| se tiene: 
 
⊨𝔄 𝑃𝑥[𝑠(𝑥|𝑑)]. 
 
Así que en particular tomando 𝑑 = �̅�(𝑡): 
 
⊨𝔄 𝑃𝑥[𝑠(𝑥|�̅�(𝑡))], (3.1.2.1) 
 
Esto es equivalente para una fórmula atómica, según la definición de satisfacción a que: 
 
�̅�(𝑡) ∈ 𝑃𝔄 
y esto es equivalente a 
 
⊨𝔄 𝑃𝑡[𝑠] (3.1.2.2) 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
7 
Para el paso de (3.1.2.1) a (3.1.2.2) en fórmulas no atómicas será necesario aplicar el lema de 
sustitución que aparece enseguida con el cual se establece que: 
 
⊨𝔄 𝜑[𝑠(𝑥|�̅�(𝑡))] 𝑠𝑖𝑖 ⊨𝔄 𝜑𝑡
𝑥[𝑠] 
 
siempre que 𝑡 sea sustituible por 𝑥 en 𝜑. 
 
(Si observas, un lema dentro de un lema que ayuda a probar el primero, esta forma es común 
de trabajar y la habrás quizá encontrado ante la idea de ponerla en este punto de la 
demostración, es así como sabes que la razón está bien determinada y la utilidad del lema, 
aparece más justificada y no sólo como un resultado de tantos para probar.) 
 
Previo al lema de sustitución se prueba un caso especial sencillo de éste con el siguiente lema. 
 
Considera una 𝔄 y una 𝑠 fijas. Para cualquier término 𝑢 sea 𝑢𝑡
𝑥 el resultado de reemplazar la 
variable 𝑥 en 𝑢 por el término 𝑡. 
 
 
3.1.2.2. Lema 
 
�̅�(𝑢𝑡
𝑥) = 𝑠(𝑥|�̅�(𝑡))̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅(𝑢) 
 
La expresión del lema afirma que se puede realizar una sustitución tanto en 𝑠 como en el 
término 𝑢, con los resultados equivalentes. El diagrama de esto es el siguiente: 
 
 
Demostración (lema 3.1.2.2) 
Por inducción sobre 𝑢. Si 𝑢 es un símbolo de constante o una variable diferente de 𝑥, entonces 
𝑢𝑡
𝑥 = 𝑢 y la ecuación se reduce a �̅�(𝑢) = �̅�(𝑢). Si 𝑢 = 𝑥, la ecuación toma la forma �̅�(𝑡) = �̅�(𝑡). El 
paso inductivo es directo, intenta expresarlo, es complicado de escribir. 
∎ 
 
Ahora en concreto el lema de sustitución. 
 
3.1.2.3. Lema [de sustitución] 
Si el término 𝑡 es sustituible por la variable 𝑥 en la fórmula 𝜑, entonces: 
 
⊨𝔄 𝜑𝑡
𝑥[𝑠] 𝑠𝑖𝑖 ⊨𝔄 𝜑[𝑠(𝑥|�̅�(𝑡))] 
Términos Términos 
Sustitución 
de 𝑡 por 𝑥 
|𝔄| 
�̅� 𝑠(𝑥|�̅�(𝑡))̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
8 
 
Demostración [lema de sustitución] 
Se usará inducción sobre 𝜑 (recuerda que la definición de las funciones es recursiva por esta 
razón se usa inducción) para probar que esto se cumple para toda 𝑠. 
 
Caso 1. 𝜑 es atómica. Entonces la conclusión se sigue del lema 3.1.2.2. 
 
Caso 2. 𝜑 es ¬𝜓 o 𝜓 → 𝜃. Entonces se sigue inmediatamente la conclusión para 𝜑 usando la 
hipótesis de inducción para 𝜓 y 𝜃. 
 
Caso 3. 𝜑 es ∀𝑦 𝜓, y 𝑥 no ocurre libre en 𝜑. Entonces 𝑠 y 𝑠(𝑥|�̅�(𝑡)) coinciden en todas las 
variables que ocurran libres en 𝜑. Además 𝜑𝑡
𝑥 es simplemente 𝜑, así que se sigue la 
conclusión. 
 
Caso 4. 𝜑 es ∀𝑦 𝜓, y 𝑥 sí ocurre libre en 𝜑. Debido a que 𝑡 es sustituible por 𝑥 en 𝜑 por 
hipótesis, se tiene que 𝑦 no ocurre en 𝑡 y que 𝑡 es sustituible por 𝑥 en 𝜓 (puedes revisar la 
definición de sustituible para constatar esto). Así se tiene que: 
 
�̅�(𝑡) = 𝑠(𝑦|𝑑)̅̅ ̅̅ ̅̅ ̅(𝑡) (3.1.2.3) 
 
para cualquier 𝑑 en |𝔄|. Pues 𝑥 ≠ 𝑦, 𝜑𝑡
𝑥 = ∀𝑦 𝜓𝑡
𝑥. 
 
⊨𝔄 𝜑𝑡
𝑥 𝑠𝑖𝑖 para cada 𝑑, ⊨𝔄 𝜓𝑡
𝑥[𝑠(𝑦|𝑑)] 
𝑠𝑖𝑖 para cada 𝑑, ⊨𝔄 𝜓[𝑠(𝑦|𝑑)(𝑥|�̅�(𝑡))] por hipótesis de inducción y 3.1.2.3. 
 𝑠𝑖𝑖 ⊨𝔄 𝜑[𝑠(𝑥|�̅�(𝑡))] 
 
Por inducción el lema se cumple para toda 𝜑. 
∎ 
 
Así concretamente se verán las condiciones para el grupo 2 de axiomas. 
 
Suponga que 𝑡 es sustituible por 𝑥 en 𝜑. Suponga también que 𝔄 satisface ∀𝑥 𝜑 con 𝑠. Se 
necesita mostrar que ⊨𝔄 𝜑𝑡
𝑥[𝑠]. Se sabe que para cualquier 𝑑 en |𝔄|, 
 
⊨𝔄 𝜑[𝑠(𝑥|𝑑)]. 
 
En particular para 𝑑 = �̅�(𝑡): 
 
⊨𝔄 𝜑[𝑠(𝑥|�̅�(𝑡))]; 
 
y por el teorema de sustitución, 
 
⊨𝔄 𝜑𝑡
𝑥[𝑠]. 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
9 
 
Por lo tanto ∀𝑥 𝜑 → 𝜑𝑡
𝑥 es válida. 
 
Grupo 3 de axiomas. ∀𝑥(𝛼 → 𝛽) → (∀𝑥 𝛼 → ∀𝑥 𝛽). 
En un ejercicio de la actividad 2 de la unidad pasada debías probar que: 
 
{∀𝑥 (𝛼 → 𝛽), ∀𝑥 𝛼} ⊨ ∀𝑥 𝛽 
 
y con esto llegar a la conclusión. 
 
Grupo 4 de axiomas. 𝛼 → ∀𝑥 𝛼, donde 𝑥 no ocurre libre en 𝛼. 
Basta que pruebes que si 𝑥 no ocurre libre en 𝛼, entonces 𝛼 ⊨ ∀𝑥 𝛼, considera los métodos 
usados durante la actividad, pues esto se desprende de ese tema. 
 
Grupo 5 de axiomas. 𝑥 = 𝑥. 𝔄 satisface 𝑥 = 𝑥 con 𝑠 sii 𝑠(𝑥) = 𝑠(𝑥), lo cual siempre es 
verdadero. 
 
Grupo 6 de axiomas. 𝑥 = 𝑦 → (𝛼 → 𝛼′). Para empezar, como ejemplo de esto, puedes mostrar 
que la siguiente fórmula es válida: 
 
𝑥 = 𝑦 → 𝑃𝑧𝑓𝑥 → 𝑃𝑧𝑓𝑦 
 
donde 𝑓 es un símbolo de función y 𝑃 es un símbolo de predicado de dos argumentos. 
 
Ahora supón que 𝛼 es atómica y que 𝛼′ se obtiene al reemplazar 𝑥 por 𝑦 en algunos lugares. 
Así es suficiente probar que 
 
{𝑥 = 𝑦, 𝛼} ⊨ 𝛼′ 
 
Se toman de manera arbitraria 𝔄 y 𝑠 tales que 
 
⊨𝔄 𝑥 = 𝑦[𝑠], es decir, 𝑠(𝑥) = 𝑠(𝑦) 
 
Entonces, cualquier término 𝑡 tiene la propiedad de que si 𝑡′ se obtiene de 𝑡 al reemplazar 𝑥 por 
𝑦 en algunos lugares, entonces �̅�(𝑡) = �̅�(𝑡′), aunque esto es claro, podrías demostrarlo 
completamente usando inducción sobre 𝑡. 
 
Si 𝛼 es 𝑡1 = 𝑡2 entonces 𝛼
′ tiene que ser 𝑡1
′ = 𝑡2
′ , donde 𝑡𝑖
′ se obtiene a partir de 𝑡𝑖 como se 
describió. 
 
⊨𝔄 𝛼[𝑠] 𝑠𝑖𝑖 �̅�(𝑡1) = �̅�(𝑡2) 
 𝑠𝑖𝑖 �̅�(𝑡1
′ ) = �̅�(𝑡2
′ ) 
 𝑠𝑖𝑖 ⊨𝔄 𝛼
′[𝑠]. 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
10 
De manera similar, si 𝛼 es 𝑃𝑡1 ⋯ 𝑡𝑛 entonces 𝛼
′ es 𝑃𝑡1
′ ⋯ 𝑡𝑛
′ , se tiene el resultado con un 
argumento análogo. 
 
De esta manera se tienen todos los grupos de axiomas, así, la conclusión del lema 3.1.2.1. 
∎ 
Demostración del teorema de correctud [3.1.1.1. Teorema] 
Se mostrara por inducción que cualquier fórmula𝜑 deducible a partir de Γ es implicada 
lógicamente por Γ. 
 
Caso 1. 𝜑 es un axioma lógico. Entonces por el lema (3.1.2.1) se tiene que ⊨ 𝜑, por tanto con 
mayor razón se cumple que Γ ⊨ 𝜑. 
 
Caso 2. 𝜑 ∈ Γ, es claro entonces que Γ ⊨ 𝜑. 
 
Caso 3. 𝜑 se obtiene por modus ponens de 𝜓 y 𝜓 → 𝜑, de donde por hipótesis de inducción se 
tiene Γ ⊨ 𝜓 y Γ ⊨ (𝜓 → 𝜑). De esto se sigue que Γ ⊨ 𝜑. 
∎ 
 
Ahora sigue la demostración del teorema de completud, que como se dijo, es el regreso del 
teorema de correctud y la demostración será para un conjunto numerable de fórmulas. 
 
Demostración. [Teorema de completud (3.1.1.5)] 
Sea Γ un conjunto consistente de fórmulas en un lenguaje numerable. 
 
Paso 1 
Se va a expandir el lenguaje añadiendo un conjunto infinito numerable de nuevos símbolos de 
constante. Luego Γ sigue siendo consistente como un conjunto de fórmulas en el nuevo 
lenguaje. Pues de no ser así, entonces para alguna 𝛽 hay una deducción dentro del lenguaje 
expandido de (𝛽 ∧ ¬𝛽) a partir de Γ que contiene únicamente una cantidad finita de nuevos 
símbolos de constante. Por el teorema de generalización a partir de constantes en la unidad 
anterior (teorema 2.3.7.1), cada uno puede ser reemplazado por una variable. Entonces se tiene 
una deducción (en el lenguaje original) de (𝛽 ∧ ¬𝛽) a partir de Γ. Esto contradice la suposición 
de que Γ era consistente. 
 
Paso 2 
Para cada fórmula 𝜑 en el nuevo lenguaje y para cada variable 𝑥, se agrega a Γ la fórmula 
 
¬∀𝑥 𝜑 → ¬𝜑𝑡
𝑥, 
 
donde 𝑐 es uno de los nuevos símbolos de constante. La idea es que 𝑐 nombrará un 
contraejemplo de 𝜑, si hay alguno. Es posible hacer esto de manera tal que Γ, junto con el 
conjunto Θ de todas las fórmulas agregadas, siga siendo un conjunto consistente. 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
11 
Se da una numeración fija de los pares 〈𝜑, 𝑥〉 donde 𝜑 es una fórmula del lenguaje expandido y 
𝑥 es una variable 
 
〈𝜑1, 𝑥1〉, 〈𝜑2, 𝑥2〉, 〈𝜑3, 𝑥3〉, … 
 
Esto es posible ya que el lenguaje es numerable. Sea 𝜃1 
 
¬∀𝑥1𝜑1 → ¬𝜑1𝑐1
𝑥1 , 
 
donde 𝑐1 es el primero de los nuevos símbolos de constante que no ocurren en 𝜑1. De la misma 
forma para 〈𝜑2, 𝑥2〉 se define 𝜃2; en general, 𝜃𝑛 es 
 
¬∀𝑥𝑛 → ¬𝜑𝑛𝑐𝑛
𝑥𝑛 
 
donde 𝑐𝑛 es el primero de los símbolos de constante que no ocurren en 𝜑𝑛 ni en 𝜃𝑘 para 
cualquier 𝑘 < 𝑛. 
 
Si Θ es el conjunto {𝜃1, 𝜃2, … }. Se afirma que Γ ∪ Θ es consistente. Si no, entonces dado que las 
deducciones son finitas para alguna 𝑚 ≥ 0, 
 
Γ ∪ {𝜃1, … , 𝜃𝑚, 𝜃𝑚+1 } 
 
es inconsistente. Considera la mínima 𝑚 que cumple eso, entonces por reducción al absurdo 
 
Γ ∪ {𝜃1, … , 𝜃𝑚} ⊢ ¬𝜃𝑚+1. 
 
Como 𝜃𝑚+1 es 
¬∀𝑥 𝜑 → ¬𝜑𝑐
𝑥 
 
para algunos 𝑥, 𝜑 y 𝑐. Así por la regla T, se obtiene 
 
Γ ∪ {𝜃1, … , 𝜃𝑚} ⊢ ¬∀𝑥 𝜑 
Γ ∪ {𝜃1, … , 𝜃𝑚} ⊢ 𝜑𝑐
𝑥 . 
 
Puesto que 𝑐 no aparece en ninguna fórmula del lado izquierdo, recordando el corolario 2.3.8.1 
de la unidad anterior que afirma que si Γ ⊢ 𝜑𝑐
𝑥, donde el símbolo de constante 𝑐 no ocurre en Γ 
ni en 𝜑. Entonces Γ ⊢ ∀𝑥 𝜑, y hay una deducción de ∀𝑥 𝜑 a partir de Γ, en la que 𝑐 no ocurre. 
Usando este corolario en la segunda ecuación se obtiene: 
 
Γ ∪ {𝜃1, … , 𝜃𝑚} ⊢ ∀𝑥 𝜑. 
 
Esto y las dos ecuaciones previas contradicen la nominalidad de 𝑚 o la consistencia de Γ si 
𝑚 = 0. 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
12 
 
Paso 3 
Ahora se extiende el conjunto consistente Γ ∪ Θ a un conjunto consistente Δ que es maximal en 
el sentido de que para cualquier fórmula 𝜑 o bien 𝜑 ∈ Δ o ¬𝜑 ∈ Δ. 
Se puede argumentar como sigue: 
 
Sea Λ el conjunto de axiomas lógicos para el lenguaje expandido. Como Γ ∪ Θ ∪ Λ es 
consistente, no existe fórmula 𝛽 tal que Γ ∪ Θ ∪ Λ implique 𝛽 y también ¬𝛽. Por lo tanto, hay una 
asignación de verdad 𝑣 para el conjunto de todas las fórmulas primas que satisface a Γ ∪ Θ ∪ Λ. 
Sea 
Δ = {𝜑|�̅�(𝜑) = 𝑉} 
 
Claramente, para cualquier 𝜑 o 𝜑 ∈ Δ o ¬𝜑 ∈ Δ, pero no ambas. Además se tiene que 
 
Δ ⊢ 𝜑 ⟹ Δ implica tautológicamente 𝜑 
⟹ �̅�(𝜑) = 𝑉 
⟹ 𝜑 ∈ Δ. 
 
Por lo tanto Δ es consistente, pues de otro modo tanto 𝜑 como (¬𝜑) pertenecerían a Δ. 
 
En realidad, independientemente de cómo se haya construido Λ, debe ser deductivamente 
cerrado. Esto es 
Δ ⊢ 𝜑 ⟹ Δ ⊬ ¬𝜑, por consistencia, 
⟹ (¬𝜑) ∉ Δ, 
⟹ 𝜑 ∈ Δ, por maximalidad 
 
Paso 4 
Ahora, a partir de Λ se construye una estructura para el nuevo lenguaje, pero con el símbolo de 
igualdad (si lo hay) reemplazado por un nuevo símbolo de predicado 𝐸 de dos argumentos. 𝔄 
no será la estructura en la que Γ se satisfaga; será una preliminar. 
 
(a) |𝔄| = el conjunto de todos los términos del nuevo lenguaje. 
(b) Se define la relación binaria 𝐸𝔄 como 
 
〈𝑢, 𝑡〉 ∈ 𝐸𝔄 𝑠𝑖𝑖 la fórmula 𝑢 = 𝑡 pertenece a Δ. 
 
(c) Para cada parámetro de predicado 𝑃 de 𝑛 argumentos, se define la relación 𝑛-aria 𝑃𝔄 
como 
 
〈𝑡1, … , 𝑡𝑛〉 ∈ 𝑃
𝔄 𝑠𝑖𝑖 𝑃𝑡1 ⋯ 𝑡𝑛 ∈ Δ. 
 
(d) Para cada símbolo de función 𝑓 de 𝑛 argumentos, sea 𝑓𝔄 la función definida por 
 
𝑓𝔄(𝑡1, … , 𝑡𝑛) = 𝑓𝑡1 ⋯ 𝑡𝑛 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
13 
 
Esto incluye el caso 𝑛 = 0; para un símbolo de constante se considera 𝑐𝔄 = 𝑐. Se define una 
función 𝑠: 𝑉 → |𝔄|, por la función identidad 𝑠(𝑥) = 𝑥 sobre V. 
 
Entonces se sigue que para cualquier término 𝑡, �̅�(𝑡) = 𝑡, esto puede probarse por inducción 
sobre 𝑡 y es muy directo. Para cualquier fórmula 𝜑, sea 𝜑∗ el resultado de reemplazar el 
símbolo de igualdad en 𝜑 por 𝐸. Entonces 
 
⊨𝔄 𝜑
∗[𝑠] 𝑠𝑖𝑖 𝜑 ∈ Δ. 
 
Esto se probará por inducción sobre el número de lugares en los que aparecen los símbolos de 
conectivo o símbolos de cuantificador en 𝜑. 
 
Caso 1. Fórmulas atómicas. 
Se ha definido 𝔄 de manera tal que este caso sea inmediato. Por ejemplo, si 𝜑 es 𝑃𝑡, entonces 
 
⊨𝔄 𝑃𝑡[𝑠] 𝑠𝑖𝑖 �̅�(𝑡) ∈ 𝑃
𝔄 
 𝑠𝑖𝑖 𝑡 ∈ 𝑃𝔄 
 𝑠𝑖𝑖 𝑃𝑡 ∈ Δ. 
 
De forma similar 
 
⊨𝔄 𝑢 𝐸𝑡[𝑠] 𝑠𝑖𝑖 〈�̅�(𝑢), �̅�(𝑡)〉 ∈ 𝐸
𝔄, 
 𝑠𝑖𝑖 〈𝑢, 𝑡〉 ∈ 𝐸𝔄, 
 𝑠𝑖𝑖 𝑢 = 𝑡 ∈ Δ. 
 
Caso 2. Negación 
 
⊨𝔄 (¬𝜑)
∗[𝑠] 𝑠𝑖𝑖 ⊭𝔄 𝜑
∗[𝑠], 
 𝑠𝑖𝑖 𝜑 ∉ Δ por hipótesis de inducción, 
 𝑠𝑖𝑖 (¬𝜑) ∈ Δ por las propiedades de Δ. 
 
Caso 3. Condicional 
 
⊨𝔄 (𝜑 → 𝜓)
∗[𝑠] 𝑠𝑖𝑖 ⊭𝔄 𝜑
∗[𝑠] 𝑜 ⊨𝔄 𝜓
∗[𝑠], 
 𝑠𝑖𝑖 𝜑 ∉ Δ 𝑜 𝜓 ∈ Δ por hipótesis de inducción, 
 𝑠𝑖𝑖 (¬𝜑) ∈ Δ 𝑜 𝜓 ∈ Δ, 
 ⟹ Δ ⊢ (𝜑 → 𝜓) 
 ⟹ 𝜑 ∉ Δ 𝑜 [𝜑 ∈ Δ y Δ ⊢ 𝜓], 
 ⟹ (¬𝜑) ∈ Δ 𝑜 𝜓 ∈ Δ, 
 
Así Δ ⊢ (𝜑 → 𝜓) sii (𝜑 → 𝜓) ∈ Δ. 
 
Caso 4. Cuantificador 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
14 
Se quiere mostrar que 
 
⊨𝔄 ∀𝑥 𝜑
∗[𝑠] 𝑠𝑖𝑖 ∀𝑥 𝜑 ∈ Δ. 
 
Nota que en este caso ∀𝑥 (𝜑∗) = (∀𝑥 𝜑)∗. Δ incluye la fórmula 𝜃: 
 
¬∀𝑥 𝜑 → ¬𝜑𝑐
𝑥 
 
Para mostrar que ⊨𝔄 ∀𝑥 𝜑
∗[𝑠] ⟹ ∀𝑥 𝜑 ∈ Δ, se puede argumentar lo siguiente: si 𝜑∗ es 
verdadero para cualquier cosa, entonces es verdadera para 𝑐, donde por hipótesis de inducción 
𝜑𝑐
𝑥 ∈ Δ. Pero entonces ∀𝑥 𝜑 ∈ Δ, porque 𝑐 fue elegida como un contraejemplo para 𝜑, sies que 
había alguno. 
 
Ahora se pasa al inverso. Considera 𝜓 una variante alfabética de 𝜑 en la que 𝑡 sea sustituible 
por 𝑥, entonces: 
 
 
⊭𝔄 ∀𝑥 𝜑
∗[𝑠] ⟹⊭𝔄 𝜑
∗[𝑠(𝑥|𝑡)], para algún 𝑡, fijo en adelante. 
⟹⊭𝔄 𝜓
∗[𝑠(𝑥|𝑡)], por la equivalencia semántica de las variables alfabéticas. 
⟹⊭𝔄 (𝜓𝑡
𝑥)∗[𝑠], por el lema de sustitución. 
⟹ 𝜓𝑡
𝑥 ∉ Δ, por la hipótesis de inducción. 
⟹ ∀𝑥 𝜓 ∉ Δ, ya que Δ es deductivamente cerrado. 
⟹ ∀𝑥 𝜑 ∉ Δ, por la equivalencia sintáctica de las variables alfabéticas. 
 
Esto completa todos los casos posibles; se sigue, por inducción, que para cualquier 𝜑, 
 
⊨𝔄 𝜑
∗[𝑠] 𝑠𝑖𝑖 𝜑 ∈ Δ. 
 
Si el lenguaje original no incluyó el símbolo de igualdad, entonces puedes ver que aquí se 
concluye la demostración, pues sólo se debe restringir 𝔄 al lenguaje original para obtener una 
estructura que satisfaga a cada elemento de Γ con la función identidad. 
 
Si se tiene el símbolo de igualdad 𝔄 no servirá, pues por ejemplo si Γ contiene el enunciado 
𝑐 = 𝑑 (donde 𝑐 y 𝑑 son símbolos constantes distintos), así que se usará entonces una 
estructura distinta 𝔅 en la cual 𝑐𝔅 = 𝑑𝔅. Esta será el cociente 𝔄/𝐸 de 𝔄 módulo 𝐸𝔄. 
 
Paso 5 
𝐸𝔄 es una relación de equivalencia sobre |𝔄|. Para cada 𝑡 en |𝔄| sea [𝑡] su clase de 
equivalencia. 𝐸𝔄 es, de hecho, una relación de congruencia para 𝔄. Esto significa que se 
cumplen las condiciones siguientes: 
(i) 𝐸𝔄 es una relación de equivalencia sobre |𝔄|. 
(ii) 𝑃𝔄 es compatible con 𝐸𝔄 para cada símbolo de predicado P: 
 
〈𝑡1, … , 𝑡𝑛〉 ∈ 𝑃
𝔄 y 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
15 
𝑡𝑖𝐸
𝔄𝑡𝑖
′, 1 ≤ 𝑖 ≤ 𝑛 ⟹ 〈𝑡1
′ , … , 𝑡𝑛
′ 〉 ∈ 𝑃𝔄. 
 
(iii) 𝑓^𝔄 es compatible con 𝐸𝔄 para cada símbolo de función 𝑓: 
 
𝑡𝑖𝐸
𝔄𝑡𝑖
′, 1 ≤ 𝑖 ≤ 𝑛 ⟹ 𝑓𝔄(𝑡1, … , 𝑡𝑛)𝐸
𝔄𝑓𝔄(𝑡1, … , 𝑡𝑛). 
 
En estas circunstancias, es posible construir la estructura cociente 𝔄 𝐸⁄ , definida como sigue: 
 
(a) |𝔄 𝐸⁄ | es el conjunto de todas las clases de equivalencia de elementos de |𝔄|. 
(b) Para cada símbolo de predicado 𝑃 de 𝑛 argumentos, 
 
〈[𝑡1], … , [𝑡𝑛]〉 ∈ 𝑃
𝔄 𝐸⁄ 𝑠𝑖𝑖 〈𝑡1, … , 𝑡𝑛〉 ∈ 𝑃
𝔄 
 
(c) Para cada símbolo de función 𝑓 de 𝑛 argumentos, 
 
𝑓𝔄 𝐸⁄ ([𝑡1], … , [𝑡𝑛]) = [𝑓
𝔄(𝑡1, … , 𝑡𝑛)] 
 
Esto incluye los casos 𝑛 = 0 𝑐𝔄 𝐸⁄ = [𝑐𝔄]. 
 
Sea ℎ: |𝔄| → |𝔄 𝐸⁄ | la función natural: 
 
ℎ(𝑡) = [𝑡] 
 
Entonces ℎ es un homomorfismo de 𝔄 sobre 𝔄 𝐸⁄ . Además, 𝐸𝔄 𝐸⁄ es la relación de igualdad 
sobre |𝔄 𝐸⁄ |. Por lo tanto, para cualquier 𝜑: 
 
𝜑 ∈ Δ ⟺⊨𝔄 𝜑
∗[𝑠] 
⟺⊨𝔄 𝐸⁄ 𝜑
∗[ℎ ∘ 𝑠] 
⟺⊨𝔄 𝐸⁄ 𝜑[ℎ ∘ 𝑠] 
 
Así 𝔄 𝐸⁄ satisface todos los elementos de Δ (y, por lo tanto, todos los elementos de Γ) con ℎ ∘ 𝑠. 
 
Paso 6 
Al restringir la estructura 𝔄 𝐸⁄ al lenguaje original se satisface a todo elemento de Γ con ℎ ∘ 𝑠. 
∎ 
 
Para un lenguaje no numerable, es necesario hacer unas cuantas modificaciones a la 
demostración anterior del teorema de completud, (Si el lenguaje tiene cardinalidad 𝜆, es decir, 
que tiene 𝜆 símbolos o, equivalentemente, 𝜆 fórmulas.) Se describen las modificaciones 
necesarias, para esto debes tener un conocimiento importante de la teoría de conjuntos, de no 
ser así puedes quedarte esencialmente con el resultado del teorema y tratar de entender sus 
implicaciones. 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
16 
En el paso 1 se agregan 𝜆 nuevos símbolos de constante; los detalles no cambian. En el paso 
2, únicamente cambian los detalles. El cardinal 𝜆 es un ordinal inicial. (Implícitamente se ha bien 
ordenado el lenguaje.) “Numerando” los pares 
 
〈𝜑𝛼 , 𝑥𝛼〉𝛼<𝜆 
 
indexados por los ordinales menores que 𝜆. Para 𝛼 < 𝜆, 𝜃𝛼 es 
 
¬∀𝑥𝛼 𝜑𝛼 → (¬𝜑)𝑐𝛼
𝑥𝛼 
 
donde 𝑐, es el primero de los nuevos símbolos de constante que no está en 𝜑𝛼, ni en 𝜃𝛽 para 
toda 𝛽 < 𝛼. (Esto excluye a lo más ℵ0 ⋅ 𝑐𝑎𝑟𝑑(𝛼) símbolos de constante, así que quedan 
algunos.) Finalmente, en el paso 3, es posible obtener el conjunto maximal Δ usando el lema de 
Zorn. El resto de la demostración es igual. 
 
 
3.1.3. Teorema de compacidad 
 
El siguiente teorema, estudiado de forma separada de los dos previos ya que ésos están 
completamente relacionados, es un resultado importante dentro de la lógica de primer orden. 
Podrás notar la relación con la lógica de enunciados. 
 
3.1.3.1. Teorema 
 
a) Si Γ ⊨ 𝜑, entonces existe un subconjunto finito Γ0 ⊆ Γ, tal que Γ0 ⊨ 𝜑. 
b) Si cada subconjunto finito Γ0 de Γ es satisfactible, entonces Γ es satisfactible. 
 
En particular, un conjunto Σ de enunciados tiene un modelo sii cada subconjunto finito tiene un 
modelo. 
 
Demostración 
Para probar la parte a) del teorema de compacidad, simplemente observa que 
 
Γ ⊨ 𝜑 ⟹ Γ ⊢ 𝜑 
⟹ Γ0 ⊢ 𝜑 para algun Γ0 ⊆ Γ finito, ya que las deducciones son finitas 
⟹ Γ0 ⊨ 𝜑 
 
La parte b) tiene una demostración similar. Si cada subconjunto finito de Γ es satisfactible, 
entonces por correctud, cada subconjunto finito de Γ es consistente. Por lo tanto, Γ es 
consistente, ya que las deducciones son finitas. Así que, por completud, Γ es satisfactible. 
Además, se cumple que a) y b) son equivalentes. 
∎ 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
17 
Nota que en el teorema de compacidad intervienen únicamente nociones semánticas de lo 
estudiado en la unidad 2, no involucra para nada las deducciones; de hecho hay 
demostraciones que evitan las deducciones, así como el siguiente teorema. 
 
3.1.3.2. Teorema [de numerabilidad] 
 
En un lenguaje razonable, el conjunto de fórmulas válidas es efectivamente numerable. 
 
Por lenguaje razonable se entiende un lenguaje cuyo conjunto de parámetros se puede 
numerar efectivamente y en el que las dos relaciones 
 
{〈𝑃, 𝑛〉|𝑃 es un símbolo de predicado de 𝑛 argumentos} 
y 
{〈𝑓, 𝑛〉|𝑓 es un símbolo de función de 𝑛 argumentos} 
 
son decidibles. Por ejemplo, cualquier lenguaje que tenga sólo una cantidad finita de 
parámetros (a esto se le llama lenguaje finito) es ciertamente razonable, ya que los conjuntos 
finitos siempre son decidibles. Por otra parte, un lenguaje razonable deberá ser a lo más 
numerable, ya que no es posible numerar efectivamente un conjunto no numerable. 
 
Demostración 
El hecho esencial es que Λ es decidible, y por lo tanto el conjunto de deducciones es decidible. 
 
Si se nos da cierta expresión 𝜀. (La suposición de que el lenguaje es razonable ya está aquí. 
Sólo existe una cantidad numerable de cosas elegibles que una persona puede dar a otra.) Se 
quiere decidir si 𝜀 está en Λ o no. Primero se verifica que 𝜀 tenga la forma sintáctica necesaria 
para ser una fórmula. Al comparar con la unidad 1, es posible hacer esto para la lógica de 
primer orden pues se te dieron las herramientas para ello. 
 
Si 𝜀 pasa esa prueba, entonces se verifica (construyendo una tabla de verdad) si es una 
generalización de una tautología. Si no, se procede a ver si 𝜀 tiene la forma sintáctica necesaria 
para estar en el grupo 2 de axiomas. 
 
Y así sucesivamente. Si 𝜀 no ha sido aceptada cuando se termine el grupo 6 de axiomas, 
entonces 𝜀 no está en Λ. Con esto puedes ver que en verdad se puede distinguir entre los que 
son elementos de Λ y los que no lo son. 
 
Ya que Λ es decidible, el conjunto de consecuencias tautológicas de Λ es efectivamente 
numerable, eso por unos de los últimos teoremas en la unidad 1. Pero 
 
{𝛼|𝛼 es una consecuencia tautológica de Λ} 
= {𝛼| ⊢ 𝛼} 
= {𝛼|𝛼 es válida} 
∎ 
Lógica matemática 
Unidad3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
18 
 
En el siguiente argumento se presenta una alternativa al párrafo anterior de esta prueba, que 
posiblemente sea más claro: primero se afirma que el conjunto de las deducciones (a partir de 
∅) es decidible. Para una sucesión finita dada 𝛼0, … , 𝛼𝑛 se puede examinar cada 𝛼𝑖 para ver si 
se encuentra en Λ o se puede obtener de elementos anteriores de la sucesión mediante modus 
ponens. Después, para numerar las fórmulas válidas, se comienza por numerar todas las 
sucesiones finitas de fórmulas. Examinando cada sucesión cuando aparece y se decide si es o 
no una deducción. Si no lo es, se descarta; pero si lo es, entonces se pone su último elemento 
en la lista de fórmulas válidas. Continuando de esta manera, se genera de una forma poco 
eficiente una lista en la que a la larga aparecerá cualquier fórmula válida. 
 
3.1.3.3. Corolario 
Sea Γ un conjunto decidible de fórmulas en un lenguaje razonable. 
a) El conjunto de teoremas de Γ es efectivamente numerable. 
b) El conjunto {𝜑|Γ ⊢ φ} de fórmulas implicadas lógicamente por Γ es efectivamente 
numerable. 
Puedes notar que el conjunto en a) y b) es el mismo, y que este corolario incluye el teorema de 
enumerabilidad cuando Γ = ∅. 
 
Demostración 
Γ ∪ Λ es decidible, así que su conjunto de consecuencias tautológicas es efectivamente 
numerable. Y éste es justamente el conjunto que se quiere. 
∎ 
 
Por ejemplo, sea Γ el conjunto (decidible) de axiomas para cualquiera de los sistemas de teoría 
de conjuntos usuales. Entonces este corolario dice que el conjunto de teoremas de la teoría de 
conjuntos es efectivamente numerable. 
 
De una manera más general, es natural insistir en que el conjunto de axiomas sea decidible al 
establecer alguna teoría axiomática. Después de todo, se quiere que las demostraciones a 
partir de estos axiomas sean argumentos “convincentes” que puedan ser “verificados”. Parte del 
proceso de verificación supone revisar que los enunciados que se dice que son axiomas, sean 
de hecho axiomas. Para que esto sea posible, es necesario que el conjunto de axiomas sea 
decidible. 
 
Esto tiene como consecuencia que el conjunto de los teoremas que se siguen de los axiomas 
sea efectivamente numerable. 
 
3.1.3.4. Corolario 
Si Γ es un conjunto decidible de fórmulas en un lenguaje razonable, y que para cualquier 
enunciado 𝜎, o bien Γ ⊨ 𝜎 o Γ ⊨ ¬𝜎. Entonces el conjunto de enunciados que implica Γ es 
decidible. 
 
Demostración 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
19 
Si Γ es inconsistente, entonces se tiene simplemente el conjunto (decidible) de todos los 
enunciados. Así que suponga que Γ es consistente. Suponga también que se da un enunciado 
𝜎 y se pide que se decida si Γ ⊨ 𝜎 o no. Es posible numerar los teoremas de Γ y buscar 𝜎 o ¬𝜎. 
Finalmente aparecerá alguno y así se sabrá la respuesta. 
∎ 
 
Nota que esta demostración realmente describe dos procedimientos de decisión. Uno es 
correcto cuando Γ es inconsistente, y el otro es correcto cuando Γ es consistente. Así que existe 
un procedimiento de decisión para cada caso. Pero no necesariamente éste es efectivo, dada 
una descripción finita de Γ, cuál deberá usarse. Un conjunto es decidible si existe un 
procedimiento de decisión para él, y esto no es lo mismo que tener en nuestras manos uno 
conocido de decisión. 
 
Debes observar que, en general, las demostraciones de numerabilidad no pueden convertirse 
en demostraciones de decidibilidad. Casi para todos los lenguajes, el conjunto de fórmulas 
válidas no es decidible. 
 
Los siguientes temas presentan conceptos con los que probablemente estás familiarizado, pero 
de manera formal. 
 
 
 
3.2. Modelos de teorías 
 
Con base en los teoremas de la sección 3.1, ahora será posible responder más preguntas de 
las que se podían responder anteriormente. 
 
Algunos enunciados tienen únicamente modelos infinitos; por ejemplo, el que dice que < es un 
orden sin elemento máximo. La negación de dicho enunciado es finitamente válida, esto es, es 
verdadera en toda estructura finita. 
 
 
3.2.1. Modelos finitos 
 
Es posible tener enunciados que tengan únicamente modelos finitos. Por ejemplo, cualquier 
modelo de ∀𝑥 ∀𝑦 𝑥 = 𝑦 tiene cardinalidad 1. Pero si todos los modelos de Σ son finitos, 
entonces el tamaño de sus modelos tiene una cota finita, como lo establece el siguiente 
teorema: 
 
3.2.1.1. Teorema. Si un conjunto Σ tiene modelos finitos arbitrariamente grandes, entonces 
tiene un modelo infinito. 
 
Demostración 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
20 
Para cada entero positivo 𝑘 ≥ 2, se puede encontrar un enunciado 𝜆𝑘 que se traduce “Hay al 
menos 𝑘 objetos”. Por ejemplo: 
 
𝜆2 = ∃𝑣1∃𝑣2 𝑣1 ≠ 𝑣2, 
𝜆3 = ∃𝑣1∃𝑣2∃𝑣3(𝑣1 ≠ 𝑣2 ∧ 𝑣1 ≠ 𝑣3 ∧ 𝑣2 ≠ 𝑣3) 
 
Considerar el conjunto 
 
Σ ∪ {𝜆2, 𝜆3, … }. 
 
Por hipótesis, cualquier subconjunto finito tiene un modelo; así que, por compacidad, todo el 
conjunto tiene un modelo, que tiende a ser infinito. 
 
Ejemplo 
 
A priori, es posible pensar que existe una ecuación sofisticada de la teoría de grupos que sea 
verdadera en todo grupo finito, pero falsa en todo grupo infinito. Sin embargo, de acuerdo con 
el teorema anterior, dicha ecuación no existe. 
 
La demostración de este teorema ilustra un método útil para obtener una estructura con 
propiedades dadas. Se escriben enunciados (posiblemente en un lenguaje expandido) que 
establecen las propiedades que se quieren. Después se argumenta que cualquier subconjunto 
finito de estos enunciados tiene un modelo. El teorema de compacidad hace el resto. En las 
páginas que siguen verás más ejemplos de este método. 
 
3.2.1.1 Corolario 
La clase de todas las estructuras finitas (para un lenguaje fijo) no es EC. La clase de todas las 
estructuras infinitas no es Clase elemental (EC). 
 
Demostración 
El primer enunciado se sigue inmediatamente del teorema. Si la clase de todas las estructuras 
infinitas es 𝑀𝑜𝑑 𝜏, entonces la clase de todas las estructuras finitas es 𝑀𝑜𝑑 ¬𝜏. Pero esta clases 
ni siquiera se encuentra en 𝐸𝐶∆, mucho menos en 𝐸𝐶. 
 
A continuación se quiere considerar problemas de decisión relacionados con estructuras finitas. 
Para cualquier estructura 𝔄, definimos la teoría de 𝔄, denotada por Th 𝔄, como el conjunto de 
todos los enunciados verdaderos en 𝔄. Dada una estructura finita 𝔄, se puede preguntar si el 
conjunto Th 𝔄 es decidible, y lo mismo para el conjunto de enunciados que tienen modelos 
finitos. 
 
Las siguientes observaciones ayudarán a dar una respuesta: 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
21 
1. Toda estructura finita 𝔄 es isomorfa a una estructura con universo {1,2, … , 𝑛}, donde 𝑛 es el 
tamaño de 𝔄 (es decir 𝑛 = card|𝔄 |). La idea es que si |𝔄| = {𝑎1, … , 𝑎𝑛}, entonces se 
reemplace 𝑎𝑖 por 𝑖. 
 
 
Ejemplo 
 
Supóngase que el lenguaje tiene únicamente el parámetro ∀ y un símbolo de predicado 𝐸 de 
dos argumentos. Considere la estructura finita 𝔅 con universo |𝔅|, compuesta por un conjunto 
de cuatro objetos distintos {𝑎, 𝑏, 𝑐, 𝑑}, y con 
 
𝐸𝔅 = {⟨𝑎, 𝑏⟩, ⟨𝑏, 𝑎⟩, ⟨𝑏, 𝑐⟩, ⟨𝑐, 𝑐⟩}. 
 
Entonces 𝔅 es isomorfa a la estructura 
 
({1, 2, 3, 4}; {(1, 2), (2, 1), (2, 3), (3, 3)}). 
 
 
Sin embargo, para este caso existen otras posibilidades; si nos hubiéramos centrado en los 
elementos de |𝔅| ordenados como 𝑏, 𝑎, 𝑑, 𝑐, tendríamos unaestructura isomorfa, aunque 
diferente 
 
({1, 2, 3, 4}; { ⟨1, 2⟩, ⟨2, 1⟩, ⟨1, 4⟩, ⟨4, 4⟩}). 
 
2. Una estructura finita del tipo que acabarnos de describir puede describirse, para un lenguaje 
finito, mediante una cadena finita de símbolos. 
 
 
Ejemplo 
 
({1, 2, 3, 4}; {⟨1, 2⟩, ⟨2, 1⟩, ⟨2, 3⟩, ⟨3, 3⟩}) 
 
Esta línea describe completamente la estructura y se puede escribir con numerales en base 
10, junto con puntuación y delimitadores (por ejemplo, paréntesis). Por lo tanto, dicha 
estructura puede ser comunicada a otra persona o a una máquina. La cadena finita de 
símbolos puede escribirse en un formato adecuado de entrada. 
 
3. Dada una estructura finita 𝔄 para un lenguaje finito, con universo {1, … , 𝑛} y por la 
observación anterior, se sabe que dicho objeto puede ser dado, una fórmula 𝜑 y una 
asignación 𝑠𝜑 de números de este universo a las variables libres de 𝜑 (por supuesto que 
sólo hay una cantidad finita), se puede determinar efectivamente si ⊨𝔄 𝜑[𝑠𝜑] o no. 
 
 
 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
22 
Ejemplo 
 
𝐵 = ({1,2,3,4}; {⟨1, 2⟩, ⟨2, 1⟩, ⟨2, 3⟩, ⟨3, 3⟩}) 
𝜑 = ∀𝑣1((¬∀𝑣2¬𝐸𝑣2𝑣1) → 𝐸𝑣1𝑣1). 
 
Se puede organizar la revisión en la forma del árbol que aparece en la figura 3.2.1.1. Se ve 
que el enunciado 𝜑, que dice “Cualquier cosa en el rango de 𝐸 está relacionada consigo 
misma”, es falso en 𝔅. 
 
 
Representación mediante Árbol 
 
En cada hoja del árbol (es decir, en cada vértice mínima) se tiene una fórmula atómica, así que 
se observa para ver si esto se satisface. Nótese que todo cuantificador genera una búsqueda a 
través del universo de n elementos. Dada una fórmula 𝜑 con 𝑘 cuantificadores, el número de 
hojas del árbol está acotado por un polinomio de grado 𝑘 en términos de 𝑛. Si el lenguaje 
contiene símbolos de función, entonces es necesario evaluar cada término utilizando la función 
(finita) que ofrece la estructura. 
 
3.2.1.1. Teorema. Si 𝔄 es una estructura finita en un lenguaje finito, entonces 𝑇ℎ 𝔄 es decidible. 
 
Demostración 1 
Por observación 1, se puede reemplazar 𝔄 por una estructura isomorfa con un universo de la 
forma {1, … 𝑛}, sin que cambie cuáles son los enunciados verdaderos. Después, aplicamos la 
observación 3. ∎ 
 
Demostración 2 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
23 
Si un lenguaje con igualdad cuyo único parámetro (además de ∀) es un símbolo de predicados 
𝑃 de dos argumentos y como 𝔄 es finito y 𝔄 ≡ 𝛿𝔄 . Entonces 𝔄 es isomorfo a 𝛿𝔄. Entonces hay 
un enunciado 𝛿𝔄 que caracteriza 𝔄, salvo isomorfismos. De donde se sigue que: 
 
𝑇ℎ 𝔄 = {𝜎| 𝛿𝔄 ⊨ 𝜎} 
 
Para demostrar la contención ⊆ hay que notar que si 𝜎 es verdadero en 𝔄, entonces es 
verdadero en todas las copias isomorfas y, por tanto, en todos los modelos de 𝛿𝔄 . De modo que 
𝛿𝔄 ⊨ 𝜎, entonces 𝜎 es verdadero en todos los modelos de 𝛿𝔄 , uno de los cuales es 𝔄 aplicando 
el corolario. Con 3.1.3.4 se nota que para todo 𝜎, o bien ⊨𝔄 𝜎 ⊨𝔄 ¬ 𝜎. 
 
4. Dado un enunciado 𝜎 y un entero positivo 𝑛, se puede decidir efectivamente si 𝜎 tiene o no 
un modelo con 𝑛 elementos. Es decir, que la relación binaria 
 
{⟨𝜎, 𝑛⟩|𝜎 tiene un modelo de tamaño 𝑛} 
es decidible. 
 
La idea clave es que solamente hay que revisar una cantidad finita de estructuras, cosa que 
ciertamente se puede hacer. Por la observación 1, el enunciado 𝜎 tiene un modelo de tamaño 𝑛 
si y sólo si tiene un modelo con universo {1, . . . , 𝑛}. Si se restringe el lenguaje a los parámetros 
que ocurren en 𝜎, solamente hay una cantidad finita de ese tipo de estructuras y se pueden 
generar todas sistemáticamente. Al usar la observación 3, se verifica si alguna de éstas es 
modelo de 𝜎. 
 
5. El espectro de un enunciado a se define como {𝑛 | a tiene un modelo de tamaño n}. De la 
observación 4 se sigue que el espectro de cualquier enunciado es un conjunto decidible de 
enteros positivos. 
 
3.2.1.2. Teorema 
Para un lenguaje finito, {𝜎|𝜎 tiene un modelo finito} es efectivamente numerable. 
 
Demostración 
 A continuación se da un procedimiento de semidecisión: dado 𝜎, usando la observación 4, 
revisa primero si éste tiene un modelo de tamaño 1; si es así, inténtalo con 2, y así 
sucesivamente. ∎ 
 
3.2.1.2 Corolario 
Supóngase que el lenguaje es finito y sea Φ el conjunto de enunciados verdaderos en una 
estructura finita. Entonces su complemento Φ es efectivamente numerable. 
 
Demostración sado un enunciado 𝜎, 
𝜎 ∈ Φ ⟺ (¬𝜎) tiene un modelo finito 
 
Se puede aplicar el procedimiento anterior de semidecisión a (¬ 𝜎). 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
24 
 
Se sigue (por el teorema 1.5.3.4) que Φ es decidible si y sólo si es efectivamente numerable. 
Pero esto no sucede. Entonces se afirma el siguiente: 
 
*3.2.1.2. Teorema de Trakhtenbrot (1950) 
El conjunto de enunciados 
 
Φ = {𝜎|𝜎 es verdadero en toda estructura finita } 
 
No es en general decidible ni efectivamente numerable. 
 
Así que el análogo del teorema de numerabilidad restringido a estructuras finitas es falso. 
 
 
3.2.2. Tamaño de modelos 
 
En la prueba del teorema de completud, se empieza con un conjunto consistente Γ y construir 
una estructura 𝔄/𝐸 en la que se satisfacía el conjunto. ¿Qué tan grande era esa estructura? Se 
afirma que si el lenguaje inicial es numerable, entonces |𝔄/𝐸| es un conjunto numerable. De 
modo que un conjunto consistente de enunciados en un lenguaje numerable tiene un modelo 
numerable. 
 
𝔄/𝐸 se construyó a partir de una estructura preliminar 𝔄. El universo de 𝔄 era el conjunto de 
todos los términos del lenguaje obtenido al agregar un conjunto numerable de nuevos símbolos 
de constante. Sin embargo, el lenguaje aumentado seguía siendo numerable, así que el 
conjunto de todas las expresiones era numerable. Es decir, |𝔄| era numerable. 
 
El universo de 𝔄/𝐸 estaba compuesto por las clases de equivalencia de elementos de 𝔄, así 
que éste también era un conjunto numerable. La conclusión es que, tal como se afirmaba, 
𝔄/𝐸 es una estructura numerable. 
 
 
 
3.2.3. Teoremas de Löwenheim-Skolem 
 
El teorema de Löwenheim-Skolem fue publicado por Leopold Löwenheim en 1915 para el caso 
en el que Γ es un conjunto unitario; en 1920, Thoralf Skolem lo generalizó a un Γ posiblemente 
infinito. El teorema marcó una nueva fase en la lógica matemática. El trabajo anterior se había 
encaminado a formalizar las matemáticas por medio de lenguajes formales y cálculos 
deductivos; el inicio de este trabajo, en 1879, se debe en gran parte a Gottlob Frege. Por 
ejemplo, en los Principia Mathematica (1910-1913) de Whitehead y Russell se realizó dicha 
formalización con sumo detalle. Sin embargo, el periodo moderno empezó cuando los lógicos 
dieron un paso atrás y comenzaron a probar resultados acerca de los sistemas formales que se 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
25 
habían estado construyendo. David Hilbert, Emil Post, Kurt Gödel (ya mencionado) y Alfred 
Tarski, entre otros, realizaron trabajos en esa dirección. 
 
 
3.2.3.1. Teorema de Löwenheim-Skolem (1915) 
(a) Sea Γ un conjunto satisfactible de fórmulas en un lenguaje numerable. Entonces hay una 
estructura numerable que satisface Γ. 
(b) Sea Σ un conjunto de enunciados en un lenguaje numerable. Si Σ tiene un modelo, entonces 
tiene un modelo numerable. 
 
Demostración 
Primero, obsérvese que Γ esconsistente, por el teorema de correctud. Entonces, por el teorema 
de completud (junto con las observaciones que hemos hecho hasta ahora), hay una estructura 
numerable que lo satisface.∎ 
 
 
Ejemplo 
 
Sea 𝐴𝑠𝑡 el conjunto de axiomas que el lector prefiera de la teoría de conjuntos. Se presupone 
que esos axiomas son consistentes y, por lo tanto, que tienen un modelo. Por el teorema de 
Löwenheim-Skolem, esos axiomas tienen un modelo numerable 𝔖. Por supuesto, 𝔖 también 
es modelo de todos los enunciados implicados lógicamente por 𝐴𝑠𝑡. Uno de estos enunciados 
afirma (cuando se traduce al español, mediante la traducción propuesta) que hay una 
cantidad no numerable de conjuntos. Aquí no hay contradicción, pero la situación es lo 
suficientemente desconcertante como para que se la llame “la paradoja de Skolem”. Lo que 
es cierto en la estructura 𝔖 es que no hay ningún elemento que satisfaga la definición formal 
de ser una función biyectiva de los números naturales en el universo. Pero esto de ninguna 
manera excluye la posibilidad de que haya (fuera de 𝔖) una auténtica función que da esa 
correspondencia uno a uno. 
 
Recuerda que la teoría de 𝔄, denotada por 𝑇ℎ 𝔄, es el conjunto de todos los enunciados 
verdaderos en 21. Se puede aplicar el teorema de Löwenheim-Skolem (conΣ = 𝑇ℎ 𝔄) para 
probar que para cualquier estructura 𝔄 de un lenguaje numerable, existe una estructura 
numerable 𝔅 elementalmente equivalente a ella. Si 𝔅 es un modelo de 𝑇ℎ 𝔄, entonces 𝔄 = 𝔅, 
pues 
 
⊨𝔄 𝜎 ⇒ 𝜎 ∈ 𝑇ℎ 𝔄 ⟹ ⊨𝔅 𝜎 
 
y 
 
⊭ 𝜎 ⟹⊨𝔄 ¬ 𝜎 ⟹ (¬𝜎) ∈ 𝑇ℎ 𝔄 ⟹⊨𝔅 ¬ 𝜎 ⟹⊭𝔅 𝜎. 
 
 
Ejemplo 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
26 
 
Considerar la estructura 
 
𝔑 = (ℕ; 0, 𝑆, <, +,· ). 
 
Se afirma que existen una estructura numerable 𝔐0, elementalmente equivalente a 𝔑 (es 
decir, 𝔐0 y 𝔑 satisfacen exactamente los mismos enunciados), pero que no es isomorfa a 𝔑. 
 
Demostración 
Se construye 𝔐0 usando teoremas compacidad. Se extiende el lenguaje agregando un nuevo 
símbolo de constante 𝑐. Sea 
 
Σ = {0 < 𝑐, 𝑺𝟎 < 𝑐, 𝑺𝑺𝟎 < 𝑐, … } 
 
Se afirma que Σ ∪ 𝑇ℎ 𝔑 tiene un modelo. Para demostrarlo, tomar cualquier subconjunto finito 
de Σ ∪ 𝑇ℎ 𝔑 tiene un modelo. 
Al usar el teorema de Löwenheim-Skolem, Σ ∪ 𝑇ℎ 𝔑 tiene un modelo numerable 
 
𝔐 = (|𝔐|; 𝟎𝕸, 𝑺𝕸, <𝕸, +𝕸,·𝕸). 
 
Sea 𝔐 la restricción de 𝔐 al lenguaje original: 
 
𝔐0 = (|𝔐|; 𝟎
𝕸, 𝑺𝕸, <𝕸, +𝕸,·𝕸). 
 
Como 𝔐0 es modelo de 𝑇ℎ 𝔑, se tiene que 𝔐0 ≡ 𝔑: 
 
⊨𝔑 𝜎 ⟹ 𝜎 ∈ 𝑇ℎ 𝔑 ⟹ ⊨𝔐0 𝜎 
⊭ 𝔑 𝜎 ⟹ ¬𝜎 ∈ 𝑇ℎ 𝔑 ⟹ ⊨𝔐0 ¬ 𝜎 ⟹⊨ 𝔐0¬ 𝜎 ⊭𝔐0 𝜎. 
 
Se observa que 𝔐0 no es isomorfo a 𝔑 . (|𝔐0| contiene el número infinito 𝑐
𝔐).∎ 
 
 
𝔄/𝐸 se construyó a partir de las estructuras preliminares 𝔄. El universo de 𝔄 era el conjunto de 
todos los términos en un lenguaje que se obtuvo al agregar 𝜆 nuevos símbolos de constante. 
Así que el lenguaje aumentado aún tenía cardinalidad 𝜆. Así, el conjunto de todas las 
expresiones (y por lo tanto, el conjunto de todos los términos) tenía cardinalidad ≤ 𝜆. (De 
hecho, puesto que al menos se tenían los 𝜆 nuevos símbolos de constante, el conjunto de 
términos tenía exactamente cardinalidad 𝜆.) 
 
El universo de 𝔄/𝐸 estaba compuesto por clases de equivalencia de elementos de 𝔄, así que 
𝑐𝑎𝑟𝑑 |𝔄/𝐸| ≤ 𝑐𝑎𝑟𝑑|𝔄|. (Se puede dar una función inyectiva de |𝔄/𝐸| en |𝔄|, al asignar a cada 
clase de equivalencia alguno de sus elementos, pero es posible que para eso se necesite el 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
27 
axioma de elección.) Así, una vez aclarada la cuestión, se ve que Γ se satisface en una 
estructura 𝔄/𝐸 de cardinalidad ≤ 𝜆. 
 
3.2.3.2. Teorema de Löwenheim-Skolem (a) Sea F un conjunto satisfactible de fórmulas en un 
lenguaje de cardinalidad 𝜆. Entonces Γ es satisfactible en alguna estructura de tamaño ≤ 𝜆. (b) 
Sea Σ un conjunto de enunciados de un lenguaje de cardinalidad𝜆. Si Σ tiene un modelo, 
entonces tiene un modelo de cardinalidad ≤ 𝜆. 
 
La primera versión del teorema de Löwenheim-Skolem que se presentó es un caso particular de 
esta versión, en la que 𝜆 = ℵ0. 
 
Supóngase que se tiene una estructura no numerable 𝔄 para un lenguaje numerable. Por el 
teorema de Löwenheim-Skolem (aplicado a 𝑇ℎ 𝔄) hay una estructura 𝔅 numerable que es 
modelo de 𝑇ℎ 𝔄, por lo que 𝔄 = 𝔅, como ya se hizo notar antes. 
 
De manera inversa, supóngase que se empieza con una estructura finita o numerable 𝔅. 
¿Existe una estructura𝔄 no numerable tal que 𝔄 = 𝔅? Si 𝔅 es finita (y el lenguaje incluye la 
igualdad), entonces esto es imposible. Pero si 𝔅 es infinita, entonces sí habrá tal 𝔄, gracias al 
siguiente teorema ascendente y descendente de Löwenheim-Skolem. La parte ascendente se 
debe a Tarski, y de ahí la "T" de LST. 
 
3.2.3.3. Teorema [LST] 
Sea 1' un conjunto de fórmulas en un lenguaje de cardinalidad 𝜆, y supóngase que Γ es 
satisfactible en alguna estructura infinita. Entonces, para todo cardinal 𝑘 ≥ 𝜆, hay una estructura 
de cardinalidad 𝑘 en la que Γ es satisfactible. 
 
Demostración 
Sea 𝔄 la estructura infinita en la que Γ es satisfactible. Se extiende el lenguaje al agregar un 
conjunto C de 𝑘 nuevos símbolos de constante. Sea 
 
Σ = {𝑐1 ≠ 𝑐2|𝑐1, 𝑐2 elementos distintos de C}. 
 
Entonces, cada subconjunto finito de Σ ∪ Γ es satisfactible en la estructura 𝔄, extendida para 
asignar objetos distintos a la cantidad finita de nuevos símbolos de constante del subconjunto. 
(Como 𝔄 es infinito, hay elementos suficientes para dar cabida a cualquier número finito de 
ellos.) Así que, por compacidad, Σ ∪ Γ es satisfactible, y por el teorema de Löwenheim-Skolem 
puede ser satisfecho en una estructura 𝔅 de cardinalidad < 𝑘. (El lenguaje expandido tiene 
cardinalidad 𝜆 + 𝑘 = 𝑘.) Pero cualquier modelo de Σ tiene cardinalidad ≥. De tal manera que 
𝔅 tiene cardinalidad 𝑘; finalmente se restringe 𝔅 al lenguaje original. ∎ 
 
3.2.3.1. Corolario (a) Sea Σ un conjunto de enunciados en un lenguaje numerable. Si Σ cuenta 
con algún modelo infinito, entonces Σ tiene modelos de cualquier cardinalidad infinita. (b) Sea 𝔄 
una estructura infinita para un lenguaje numerable. Entonces, para cualquier cardinal infinito 𝜆, 
hay una estructura 𝔅 de cardinalidad 𝜆 tal que 𝔅 ≡ 𝔄. 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
28 
 
Demostración 
(a) Tómese Γ = Σ, 𝜆 = ℵ0 en el teorema. (b) Tómese Σ = 𝑇ℎ 𝔄 en la parte (a).∎ 
 
 
Ejemplo 
 
Considérese un conjunto Σ de enunciados, de los que se pensará que son axiomas no 
lógicos. Sea Σ un conjunto de axiomas de la teoría de conjuntos o un conjunto de axiomas de 
la teoría de los números. Se dice que Σ es categórica si y sólo si cualesquiera dos modelos 
de Σ son isomorfos. El corolario anterior implica que si Σ tiene algún modelo infinito, 
entonces Σ no es categórica. Por ejemplo, no existe un conjunto de enunciados tal que sus 
modelos sean exactamente las estructuras isomorfas de (ℕ; 0, 𝑆, +,·). 
 
 
Esto concluye los temas de la unidad 3 de Lógica matemática, con los principales teoremas de 
la lógica de primer orden. Cabe decir que no es todo lo que se puede decir de esto y que 
puedes conocer formas distintas de concebir la lógica en este nivel, a manera de un 
planteamiento distinto, para ello revisa la sección Para saber más. 
 
 
Cierre de la unidad 
 
La matemática necesita de un lenguaje apropiado para ser lo mas precisa posible, éste es dado 
por la lógica, como se mencionó, está en lenguaje de la lógica deprimer orden. A la luz de esto, 
mirar las propociones que se tienen a diario en el quehacer matemático puede brindarte una 
perspectiva distinta de los teoremas y, asimismo, posibles herramientas para probarlo. 
Seguramente ya has usado métodos de demostración de los aquí presentados, pero ésta es 
una formalización de eso. Analízalo con cuidado. 
 
 
Para saber más 
 
Se puede revisar el capítulo IV de Enderton, H., A Mathematical Introduction to Logic, Academic 
Press, 2001, para ver que hay enunciados categóricos de segundo orden; sin embargo, los 
enunciados de segundo orden son objetos peculiares que se obtuvieron a costa de mantener 
fija la noción de subconjunto, inmune a la interpretación mediante estructuras. 
 
Considera revisar textos con alternativas a esta visión de la lógica en textos como los 
siguientes: 
 
Suppes, P. y S. Hill (1981). Introducción a la lógica matemática, México: Reverte. 
 
Hurley, P. (2012). A concise introduction to logic (11ª ed.).Bostón EUA. Cengage Learning 
Lógica matemática 
Unidad 3. Validez, completud y modelos en la lógica de primer orden 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 
 
29 
 
 
Referencias bibliográficas 
 
Amor, J. A. y R. Rojas (1991). Sistemas formales. México: Vínculos matemáticos núm. 149, 
Facultad de Ciencias UNAM. 
 
Amor, J. A. (1993). Lógica proposicional dentro de la lógica de primer orden. México: 
Vínculos matemáticos núm. 113, Facultad de Ciencias UNAM. 
 
Enderton, H. (2001). A Mathematical Introduction to Logic.(2a Edición) Los Angeles California 
EUA. Academic Press.