MLMA_U2_contenido - German Funes

Vista previa del material en texto

Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
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 2. Lógica de primer orden o de predicados 
 
 
Clave: 
05144845 
 
 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 2 
 
Índice 
 
Índice ....................................................................................................................................... 2 
Unidad 2. Lógica de primer orden o de predicados ............................................................. 3 
Presentación de la unidad ..................................................................................................... 3 
Propósitos de la unidad ......................................................................................................... 3 
Competencia específica ......................................................................................................... 4 
2.1. Lenguajes de primer orden ............................................................................................. 4 
2.1.1. Símbolos lógicos y no lógicos ................................................................................... 6 
2.1.2. Términos y fórmulas ................................................................................................. 11 
2.1.3. Variables libres y variables acotadas ...................................................................... 13 
2.1.4. Definición y ejemplos de enunciados ...................................................................... 15 
2.2. Verdad y modelos .......................................................................................................... 17 
2.2.1. Interpretaciones o estructuras ................................................................................. 17 
2.2.2. Definición de satisfacción......................................................................................... 19 
2.2.3. Definición de verdad para enunciados y definición de modelo ............................. 23 
2.2.4. Implicación lógica ..................................................................................................... 26 
2.2.5. Equivalencia lógica ................................................................................................... 27 
2.2.6. Fórmulas universalmente válidas ............................................................................ 27 
2.2.7. Definibilidad de una estructura ................................................................................ 28 
2.2.8. Homomorfismos y teorema del homomorfismo ...................................................... 32 
2.3. Un cálculo deductivo ..................................................................................................... 38 
2.3.1. Deducciones formales .............................................................................................. 38 
2.3.2. Reglas de inferencia .................................................................................................. 39 
2.3.3. Axiomas lógicos ........................................................................................................ 40 
2.3.4. Deducciones y metateoremas .................................................................................. 44 
2.3.5. Teorema de generalización ....................................................................................... 46 
2.3.6. Teorema de la deducción .......................................................................................... 47 
2.3.7. Teorema de la generalización sobre constantes ..................................................... 51 
2.3.8. Teorema de la existencia de variantes alfabéticas.................................................. 53 
Cierre de la unidad ............................................................................................................... 55 
Para saber más ..................................................................................................................... 55 
Referencias bibliográficas ................................................................................................... 55 
 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 3 
Unidad 2. Lógica de primer orden o de predicados 
 
Presentación de la unidad 
 
La presente unidad contiene las herramientas necesarias para poder construir lo que es llamado 
un cálculo deductivo, es decir, una forma de demostrar que ciertos enunciados son 
consecuencia lógica de un conjunto de otros enunciados, formalizando estos conceptos durante 
el desarrollo. 
 
Se presentan algunos resultados importantes de la lógica de primer orden dejando muy en claro 
su relación con la lógica de enunciados, pues se presentan conceptos similares pero más 
complejos en sí mismos. 
 
Debido a que en general lo que se ha estudiado hasta el momento en la carrera de matemáticas 
está escrito en este tipo de lenguaje, se presentan relaciones directas con conceptos del 
álgebra, primordialmente cálculo. Si bien lo que se usará en general es sencillo dentro de las 
áreas, se recomienda tener a la mano algún texto de definiciones para mejor comprensión de 
los contenidos. 
 
La unidad terminará con la presentación de teoremas que permiten determinar si un enunciado 
es, en la lógica de primer orden, consecuencia lógica de otros. 
 
 
Propósitos de la unidad 
 
 
 
Al terminar esta unidad lograrás: 
 Introducir los conceptos necesarios en la lógica de 
primer orden. 
 Comprender el concepto de validez en la lógica de 
primer orden, como la manera de determinar el 
valor de verdad de los enunciados dentro de una 
estructura. 
 Demostrar los teoremas de generalización y de 
deducción para tener las herramientas de las 
demostraciones deductivas. 
 
 
 
 
 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 4 
Competencia específica 
 
 
 
 
 
 
Analiza algunos resultados de un cálculo deductivo mediante el 
empleo de razonamientos matemáticos correctos expresados en el 
lenguaje de la lógica de primer orden, para determinar métodos de 
deducción adecuados con el fin de demostrar que un enunciado 
dado es implicado lógicamente por otros. 
 
 
 
2.1. Lenguajes de primer orden 
 
El modelo matemático de pensamiento deductivo presentado en la unidad anterior puede ser, 
de cierta forma, muy simple. Se pueden pensar algunos ejemplos sencillos de deducciones 
intuitivamente correctas que no pueden ser reflejadas adecuadamente en un modelo de lógica 
de enunciados. 
 
Considérese, por ejemplo, que se empieza con una serie de hipótesis en lenguaje común y una 
posible conclusión, al hacer la traducción al lenguaje de la lógica de enunciados, se tiene un 
conjunto Σ de hipótesis y la conclusión 𝜏. Si se tiene que Σ ⊨ 𝜏, podría pensarse que la 
deducción original era válida, pero en el caso que Σ ⊭ 𝜏, no se tendrá certeza. Esto puede 
deberse a que el modelo de la lógica de enunciados no refleja la sutiliza de la deducción 
original. 
 
El sistema deductivo que se presenta a continuación es en el que frecuentemente están hechas 
las demostraciones presentes en la literatura. 
 
Para empezar, se dará una descripción informal de las características que podrían tener los 
lenguajes de primer orden que se trabajarán en el curso, o al menos las que se podrían simular. 
Se comienza con un caso especial, el lenguaje de primer orden para la teoría de los números. 
Este lenguaje tiene una forma de ser traducidoal lenguaje común y viceversa, como se 
presenta en la siguiente tabla. 
 
Expresión formal Traducción 
𝟎 Cero. 0 es un símbolo de constante que 
representará el número 0. 
𝑺𝒕 El sucesor de t. 𝑆 es un símbolo de función de 
un argumento, 𝑡 se considerará como una 
expresión para representar algún número 𝑎. 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 5 
Entonces, 𝑆𝑡 nombra a 𝑆(𝑎), el sucesor de 𝑎. 
Por ejemplo, se tiene que 𝑆0 representa el 
número 1. 
< 𝒗𝟏𝒗𝟐 𝑣1 es menor que 𝑣2. < es un símbolo de 
predicado de dos argumentos. Posteriormente 
se darán las convenciones para poder 
abreviar esta expresión en un estilo más 
conocido 𝑣1 < 𝑣2. 
∀ Para todo número natural. El símbolo ∀ es el 
símbolo de cuantificador universal. De una 
forma más general, con cada traducción del 
lenguaje formal al lenguaje común habrá 
determinado conjunto asociado 𝐴 (usualmente 
llamado el universo). ∀ será entonces para 
todo elemento del universo 𝐴. 
∀𝒗𝟏 < 𝟎𝒗𝟏 Para todo número natural 𝑣1, cero es menor 
que 𝑣1.” Dicho de otra manera: “Todo número 
natural es mayor que 0.” Este enunciado 
formal es falso con el significado de la 
traducción, ya que cero no es mayor que sí 
mismo. 
Tabla 1.Características de Lenguajes de primer orden 
 
Se tienen, además, algunas expresiones abreviadas y sus traducciones. 
 
 
Expresión formal Traducción 
𝒙 = 𝒚 𝑥 es igual a 𝑦. En la forma no abreviada, esto 
se convertiría en = 𝑥𝑦. 
∃𝒗 Existe un número natural 𝑣 tal que. O, de una 
manera más general, existe un elemento del 
universo tal que. 
∃𝒗𝟏∀𝒗𝟐 𝒗𝟏 = 𝒗𝟐 Existe exactamente un número natural. De 
nuevo, este enunciado formal resulta falso con 
el significado de la traducción. 
∀𝒗𝟏(𝟎 < 𝒗𝟏 ∨ 𝟎 = 𝒗𝟏) Todo número natural es mayor o igual que 
cero. 
Tabla 2. Expresiones abreviadas y traducciones 
 
Se harán algunas medidas de carácter económico para simplificar sin ninguna pérdida esencial 
de la expresividad lingüística: 
 
En primer lugar, se eligen como conectivos de enunciado solamente ¬ y →. De la unidad 
anterior se sabe que éstos forman un conjunto completo de conectivos y, por lo mismo, no hay 
una razón que obligue a usar más. 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 6 
 
En segundo lugar, no se usará un cuantificador existencial ∃𝑥. En lugar su se usará ¬∀𝑥¬. Esto 
se justifica porque una oración en lenguaje común, como: 
 
𝐻𝑎𝑦 𝑎𝑙𝑔𝑜 𝑝𝑜𝑑𝑟𝑖𝑑𝑜 𝑒𝑛 𝐷𝑖𝑛𝑎𝑚𝑎𝑟𝑐𝑎. 
 
es equivalente a: 
 
𝑁𝑜 𝑒𝑠 𝑒𝑙 𝑐𝑎𝑠𝑜 𝑞𝑢𝑒 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑥, 𝑥 𝑛𝑜 𝑒𝑠𝑡á 𝑝𝑜𝑑𝑟𝑖𝑑𝑜 𝑒𝑛 𝐷𝑖𝑛𝑎𝑚𝑎𝑟𝑐𝑎. 
 
Por lo tanto, la fórmula ∃𝑣1∀𝑣2 𝑣1 = 𝑣2 se convierte, en forma no abreviada, en: 
 
(¬∀𝑣1(¬∀𝑣2 = 𝑣1𝑣2)). 
 
Como ejemplo de un lenguaje a propósito para el caso, se puede traducir “Sócrates es un 
hombre” como 𝐻𝑠; donde 𝐻 es un símbolo de predicado de un argumento que se utiliza para 
traducir “es un hombre” y 𝑠 es un símbolo de contante que se utiliza para nombrar a Sócrates. 
De manera similar, para traducir "Sócrates es mortal", se usa 𝑀𝑠; por lo tanto, “Todos los 
hombres son mortales” se traduce como ∀𝑣1(𝐻𝑣1 → 𝑀𝑣1). 
 
 
2.1.1. Símbolos lógicos y no lógicos 
 
Para lo que sigue, se asume que se tiene un número infinito de objetos distintos (que 
denominamos símbolos), ordenados de acuerdo con lo siguiente: 
 
A. Símbolos lógicos: 
1. Paréntesis: (, ). 
2. Símbolos de conectivo para enunciados:→, ¬. 
3. Variables (una para cada entero positivo 𝑛): 𝑣1, 𝑣2, … 
4. Símbolo de igualdad (opcional): =. 
 
B. Parámetros: 
0. Símbolo de cuantificador: ∀. 
1. Símbolos de predicado: para cada entero positivo 𝑛, algún conjunto (posiblemente 
vacío) de símbolos, denominado símbolos de predicado de 𝑛 argumentos. 
2. Símbolos de constante: algún conjunto (posiblemente vacío) de símbolos. 
3. Símbolos de función: para cada entero positivo 𝑛, algún conjunto (posiblemente 
vacío) de símbolos denominados símbolos de función de 𝑛 argumentos. 
 
En A.3 (símbolos lógicos) se permite la posibilidad de existencia del símbolo de igualdad, pero 
no se da por hecho su presencia. Algunos lenguajes contarán con él y otros no. El símbolo de 
igualdad es un símbolo de predicado de dos argumentos, pero se distingue de otros símbolos 
de predicados de dos argumentos por ser uno más que un parámetro (este estado afectará su 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 7 
comportamiento cuando se traduzca al Lenguaje común). Es necesario asumir que se 
encuentra presente algún símbolo de predicado de 𝑛 argumentos para algún 𝑛. 
 
En B.2 (Parámetros), los símbolos de constante también se llaman símbolos de función de 0 
argumentos. Con frecuencia, esto permite dar un tratamiento uniforme a los símbolos que se 
encuentran en B.2 y B.3. 
 
Al igual que antes, se asume que cada símbolo es distinto y ninguno es una sucesión finita de 
otros símbolos. 
 
Con el fin de especificar qué lenguaje se tiene (que difiere de otros lenguajes de primer orden), 
se debe decir: 
 
 si se encuentra presente o no el símbolo de igualdad, y 
 cuáles son los parámetros. 
 
A continuación se presenta una lista de algunos ejemplos de este lenguaje: 
 
1. Lenguaje puro de predicados 
- Igualdad: no. 
- Símbolos de predicado de 𝑛 argumentos: 𝐴1
𝑛 , 𝐴2
𝑛, … 
- Símbolos de constante: 𝑎1, 𝑎2, … 
- Símbolos de función de 𝑛 argumentos (𝑛 > 0): ninguno. 
 
2. Lenguaje de la teoría de conjuntos 
- Igualdad: sí (normalmente). 
- Parámetros de predicado: un símbolo de predicado de dos argumentos ∈. 
- Símbolos de función: ninguno (u ocasionalmente un símbolo de constante ∅). 
 
3. Lenguaje de la teoría elemental de números 
- Igualdad: sí. 
- Parámetros de predicado: un símbolo de predicado de dos argumentos <. 
- Símbolos de constante: 0. 
- Símbolos de función de un argumento: 𝑆 (para el sucesor). 
- Símbolos de función de dos argumentos: + (para la suma), ⋅ (para la multiplicación), 
y 𝐸 (para la exponenciación). 
 
En los casos 2 y 3 hay ciertas traducciones usuales para los parámetros. A continuación se 
presentan varios ejemplos de enunciados que pueden traducirse a estos lenguajes y unos 
cuantos de enunciados que no pueden ser traducidos así. 
 
Es importante notar que la noción de lenguaje incluye el lenguaje de la teoría de conjuntos. Se 
suele aceptar que, en general, las matemáticas se pueden representar en la teoría de 
conjuntos. Esto significa que: 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 8 
 
 Los enunciados en matemáticas (como el teorema fundamental del cálculo) pueden 
expresarse en el lenguaje de la teoría de conjuntos. 
 Los teoremas de matemáticas son consecuencia lógica de los axiomas de la teoría de 
conjuntos. 
 
El modelo de lógica de primer orden presentado hasta el momento es totalmente adecuado 
para reflejar este procedimiento. 
 
Ejemplo 2.1.1.1 
 
En el lenguaje de la teoría de conjuntos. 
Aquí se pretende que ∀ signifique "para todos los conjuntos" y ∈, "es elemento de". 
 
“No existe un conjunto del cual todo conjunto sea elemento”. Se debe traducir esto al lenguaje 
de la teoría de conjuntos con varios pasos. Los enunciados intermedios no están ni en lenguaje 
común ni en lenguaje formal, sino en una mezcla de ambos. 
 
¬[𝐸𝑥𝑖𝑠𝑡𝑒 𝑢𝑛 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒𝑙 𝑐𝑢𝑎𝑙 𝑡𝑜𝑑𝑜 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑒𝑠 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜] 
¬∃𝑣1[𝑇𝑜𝑑𝑜 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑒𝑠 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑒 𝑣1] 
¬∃𝑣1∀𝑣2 𝑣2 ∈ 𝑣1 
 
Aunque se podría pensar en detenerse aquí, se deberemplazar 𝑣2 ∈ 𝑣1 por ∈ 𝑣1𝑣2, debido a 
que los símbolos de predicado siempre van a la izquierda en dichos contextos. Además se 
debe reemplazar ∃𝑣1 y poner en su lugar ¬∀𝑣1¬, tal como se mencionó anteriormente. Se 
debe utilizar el número correcto de paréntesis. El producto terminado es: 
 
(¬(¬∀𝑣1(¬∀𝑣2 ∈ 𝑣2𝑣1))) 
 
Axioma del par 
"Para cualesquiera dos conjuntos, existe un conjunto cuyos elementos son exactamente los 
dos conjuntos dados". De nuevo, la traducción se hará por pasos. 
 
∀𝑣1 ∀2 [𝐸𝑥𝑖𝑠𝑡𝑒 𝑢𝑛 𝑐𝑜𝑛𝑗𝑢𝑡𝑛𝑜 𝑐𝑢𝑦𝑜𝑠 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 𝑠𝑜𝑛 𝑒𝑥𝑎𝑐𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑣1 𝑦 𝑣2] 
∀𝑣1 ∀2 ∃𝑣3 [𝐿𝑜𝑠 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 𝑑𝑒 𝑣3 𝑠𝑜𝑛 𝑒𝑥𝑎𝑐𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑣1 𝑦 𝑣2] 
∀𝑣1 ∀2 ∃𝑣3 ∀𝑣4(𝑣4 ∈ 𝑣3 ↔ 𝑣4 = 𝑣1 ∨ 𝑣4 = 𝑣2) 
 
Nuevamente se tienen que reemplazar los conectivos con las equivalentes en el conjunto 
completo de →, ¬. Además se deben hacer cambios similares a los anteriores. 
 
Considerando que 
𝛼 ∨ 𝛽 es equivalente a ¬𝛼 → 𝛽 
𝛼 ↔ 𝛽 es equivalente a ¬((𝛼 → 𝛽) → ¬(𝛽 → 𝛼)) 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 9 
 
Se tiene que el producto terminado es: 
 
∀𝑣1 ∀𝑣2 (¬∀𝑣3 (¬∀𝑣4 (¬ ((∈ 𝑣4𝑣3 → ((¬= 𝑣4𝑣1) →= 𝑣4𝑣2))
→ (¬ (((¬= 𝑣4𝑣1) →= 𝑣4𝑣2) →∈ 𝑣4𝑣3)))))) 
 
El producto terminado no resulta tan fácil de leer como la versión que le precedió. Ya que no se 
trata de complicarse, con el paso del tiempo se adoptan reglas convencionales que permiten 
evitar ver el producto terminado. Por el momento se considerará lo anterior como una novedad 
interesante aunque poco atractiva. 
 
En el lenguaje de la teoría elemental de los números 
Se pretende que ∀ signifique “para todos los números naturales” y que < ,0, +,⋅, 𝐸 tengan sus 
significados obvios. 
 
1. Como nombre para el número natural 2 se tiene el término 𝑆𝑆0, ya que 2 es el sucesor del 
sucesor del cero. De forma similar, para el 4 se tiene el término 𝑆𝑆𝑆𝑆0. Para la frase “2 + 2” 
resulta tentador utilizar 𝑆𝑆0 + 𝑆𝑆0; pero se adopta la convención de poner siempre a la 
izquierda el símbolo de función (se usará la notación polaca para los símbolos de 
funciones); entonces se tiene que para la frase en lenguaje común “2 + 2” se usa el término 
+𝑆𝑆0 𝑆𝑆0. El enunciado en lenguaje común “dos más dos es cuatro” se traduce como: 
 
= + 𝑆𝑆0 𝑆𝑆0 𝑆𝑆𝑆𝑆0 
 
(Los espacios se insertaron para ayudar a leer la expresión, pero no constituyen una 
característica oficial del lenguaje). 
 
2. “Cualquier número natural distinto de cero es el sucesor de algún número”. Se realiza la 
traducción en tres pasos: 
 
∀𝑣1 [Si 𝑣1 es diferente de cero, entonces 𝑣1 es el sucesor de algún número] 
∀𝑣1 (𝑣1 ≠ 0 → ∃𝑣2 𝑣1 = 𝑆𝑣2) 
∀𝑣1 ((¬= 𝑣10) → (¬∀𝑣2(¬= 𝑣1 𝑆𝑣2))) 
 
En lenguajes ad hoc 
 
1. “Todas las manzanas están malas”. 
∀𝑣1(𝐴𝑣1 → 𝐵𝑣1) 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 10 
2. “Algunas manzanas están malas”. 
 
Paso intermedio: ∃𝑣1(𝐴𝑣1 ∧ 𝐵𝑣1). 
Producto terminado: (¬∀𝑣1 (¬ (¬(𝐴𝑣1 → (¬𝐵𝑣1))))). 
 
Los puntos anteriores ilustran patrones que surgen continuamente. Un enunciado en lenguaje 
común que afirma que, en una determinada categoría, todo tienen alguna propiedad se traduce 
como: 
 
∀𝑣( → ). 
 
Un enunciado que afirma que en la categoría hay algún objeto o algunos objetos que tienen la 
propiedad se traduce como: 
 
∃𝑣( ∧ ) 
 
Al trabajar con estos patrones debes tener cuidado de no confundirlos, pues, por ejemplo, 
 
∀𝑣1(𝐴𝑣1 ∧ 𝐵𝑣1) 
 
se traduce como “Toda cosa es una manzana y está mala”. Esto es mucho más fuerte que el 
enunciado del punto 1. De forma similar, ∃𝑣1(𝐴𝑣1 → 𝐵𝑣1) se traduce como “Existe algo que 
está malo, si es una manzana”. Esta afirmación es mucho más débil que el enunciado del 
punto 1. Es verdadero (por vacuidad), aún si todas las manzanas están buenas, considerando 
solamente que el mundo tenga alguna otra cosa que no sea una manzana. 
 
3. “El papá de Roberto puede ganarle al papá de cualquier otro niño de la cuadra”. Establece 
un lenguaje donde ∀ significa “para toda la gente”; 𝐾𝑥, “𝑥 es un niño de la cuadra”; 𝑏, 
“Roberto”; 𝐵𝑥𝑦, “𝑥 puede ganarle a 𝑦”, y 𝑓𝑥, “el papá de 𝑥”. Entonces una traducción es: 
 
∀𝑣1 (𝐾𝑣1 → ((¬= 𝑣1𝑏 ) → 𝐵 𝑓𝑏 𝑓𝑣1)) 
 
4. En cálculo se aprendió que el significado de “la función 𝑓 converge a 𝐿 cuando 𝑥” 
 se aproxima a 𝑎”: 
 
∀𝜀 (𝜀 > 0 → ∃𝛿(𝛿 > 0 ∧ ∀𝑥(|𝑥 − 𝑎| < 𝛿 → |𝑓𝑥 − 𝐿| < 𝜀))) 
 
Esto es, aparte de los asuntos de notación, una fórmula del tipo que será de interés que utiliza 
un símbolo de predicado para el orden, símbolos de función para 𝑓, resta, valores absolutos y 
símbolos de constante para 0, 𝑎 y 𝐿. 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 11 
2.1.2. Términos y fórmulas 
 
Se empezará a formalizar un poco el lenguaje que se estudia, de manera muy similar a como se 
hizo en la Unidad 1. 
 
Definición 
Una expresión es una sucesión finita de símbolos. La mayoría de las expresiones son 
absurdas, pero existen ciertas expresiones interesantes: los términos y las fórmulas. 
 
Los términos son los sustantivos y los pronombres del lenguaje que se consideran. Pueden 
entenderse como las expresiones que nombran los objetos. Las fórmulas atómicas son las 
que no tienen ni símbolos de conectivo ni símbolos de cuantificador. 
 
Términos 
Fórmulas atómicas 
Otras fórmulas 
Todas las demás expresiones 
 
Los términos se definen como aquellas expresiones que pueden construirse a partir de los 
simbolos de constante y de las variables al prefijarles los símbolos de función. Con el fin de 
enunciar esto en la terminología de la Unidad 1, se define para cada símbolo de función 𝑓 de 𝑛 
argumentos, una operación de construcción de términos ℱ𝑓 de 𝑛 argumentos sobre las 
expresiones: 
 
ℱ𝑓(𝜀1, … , 𝜀𝑛) = 𝑓𝜀1 ⋯ 𝜀𝑛 
 
De lo anterior es posible formular lo siguiente: 
 
Definición 
El conjunto de términos es el conjunto de expresiones que puede construirse a partir de 
símbolos de constante y variables al aplicar (cero o más veces) las operaciones ℱ𝑓. 
 
Si no hay símbolos de función (además de los símbolos de constante), los términos son 
únicamente los símbolos de constante y las variables. En este caso no se necesita una 
definición inductiva. 
 
Obsérvese que se usa notación polaca para los términos, al ubicar el símbolo de función a la 
izquierda. Los términos no contienen paréntesis ni comas. Más adelante se probará un 
resultado de unicidad de la lectura, mostrando que dado un término es posible descomponerlo 
sin ambigüedades. 
 
Los términos son las expresiones que se traducen como los nombres de los objetos (o frases 
nominales); en contraste con las fórmulas, que se traducen como afirmaciones acerca de los 
objetos. 
Fórmulas 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 12 
 
Algunos ejemplos de términos en el lenguaje de la teoría de los números son: 
 
+ 𝑣2 𝑆0, 
𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆0, 
+ 𝐸𝑣1𝑆𝑆𝑆0 𝐸 𝑣2 𝑆𝑆𝑆𝑆𝑆𝑆𝑆0 
 
Las fórmulas atómicas desempeñarán un papel más o menos análogo al que desempeñan los 
símbolos de enunciado en la lógica de enunciados. Una fórmula atómica es una expresión de 
la forma: 
 
𝑃𝑡1 ⋯ 𝑡𝑛 
 
donde 𝑃 es un símbolo de predicado de 𝑛 argumentos y 𝑡1, … , 𝑡𝑛 son los términos. 
 
Por ejemplo, = 𝑣1 𝑣2 es una fórmula atómica, ya que = es un símbolo de predicado de dos 
argumentos y cada variable es un término. En el lenguaje de la teoría de conjuntos se tiene la 
fórmula atómica ∈ 𝑣5 𝑣3.Nota que las fórmulas atómicas no se definen de forma inductiva, se ha limitado a decir 
explícitamente cuáles expresiones son fórmulas atómicas. 
 
Las fórmulas (o fórmulas bien formadas, más común en los textos escritos en inglés) son 
aquellas expresiones que pueden construirse a partir de las fórmulas atómicas mediante el uso 
del cero o más veces de los símbolos de conectivo y del símbolo de cuantificador. es posible 
expresar esto usando la terminología de la unidad 1 definiendo primero algunas operaciones de 
construcción de fórmulas sobre las expresiones: 
 
ℰ¬(𝛾) = (¬𝛾), 
ℰ→(𝛾, 𝛿) = (𝛾 → 𝛿), 
𝒬𝑖(𝛾) = ∀𝑣𝑖𝛾. 
 
Definición 
El conjunto de las fórmulas es el conjutno de expresiones que pueden construirse a partir de 
las fórmulas atómicas al aplicar (cero o más veces) las operaciones ℰ¬, ℰ→ y 𝒬𝑖(𝛾) (𝑖 = 1,2, … ). 
 
Por ejemplo, por una parte se tiene que ¬𝑣3 no es una fórmula aunque puede verse cómo 
aplicar la operación ℰ¬, 𝑣3 no es una fórmula atómica en la que se usen las operaciones, pues 
no tiene términos de predicado. Por otro lado, 
 
∀𝑣1 ((¬∀𝑣3(¬∈ 𝑣3𝑣1)) → (¬∀𝑣2 (∈ 𝑣2𝑣1 → (¬∀𝑣4(∈ 𝑣4𝑣2 → (¬∈ 𝑣4𝑣1)))))) 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 13 
es una fórmula. Esto se puede comprobar haciendo el árbol de construcción. Se requiere un 
poco de estudio para ver que esta fórmula es el axioma de regularidad de la teoría de 
conjuntos. 
 
 
2.1.3. Variables libres y variables acotadas 
 
Obsérvense que entre los siguientes ejemplos de fórmulas dentro del lenguaje de la teoría de 
conjuntos ∀𝑣2 ∈ 𝑣2𝑣1 y (¬∀𝑣1(¬∀𝑣2 ∈ 𝑣2𝑣1)) existe una diferencia muy importante. El segundo 
ejemplo puede traducirse como: 
 
𝐸𝑥𝑖𝑠𝑡𝑒 𝑢𝑛 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑡𝑜𝑑𝑜 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑒𝑠 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑠𝑢𝑦𝑜. 
 
Mientras que el primero puede traducirse sólo como un enunciado incompleto: 
 
𝑇𝑜𝑑𝑜 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑒𝑠 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑒 1. 
 
En este caso no es posible terminar el enunciado sin saber qué hacer con 𝑣1. En este tipo de 
casos, se dice que 𝑣1 ocurre libre en la fórmula ∀𝑣2 ∈ 𝑣2𝑣1. En el caso de 
(¬∀𝑣1(¬∀𝑣2 ∈ 𝑣2𝑣1)), no hay variables que ocurran libremente. Esta idea se formaliza de 
manera que no dependa de la traducción al lenguaje común que se haga de ella. 
 
Hay dos maneras de ver las variables: si ocurren libres (variables libres) o no (variables 
acotadas).Para comprenderlas mejor y para explicar estas diferencias, se representan como 
sigue: 
 
Variable acotada. Es, por así decirlo, una variable de “verdad”. Puede tomar todos los calores 
dentro de un dominio de variablidad, pero ninguno en particular. Si se cambia la variable por 
otra, no cambia el significado de la expresión. 
 
Variable libre. Variable “aparente”. Puede ser cualquier cosa, pero sólo una (esto está implícito 
en lo que se dirá adelante), al cambiarla se cambia el significado. De manera intuitiva, si la 
variable 𝑥 aparece libre en 𝛼, entonces 𝛼 depende de 𝑥. 
 
Las ideas anteriores se formalizan de mejor manera y de acuerdo con el contexto en el que se 
estudia, en la siguiente definición. 
 
 
 
 
Definición (Variable libre) (por recursión) 
 
Considérese cualquier variable 𝑥. Se define para cada fórmula 𝑎, lo que significa que 𝑥 ocurre 
libre en 𝑎. Esto se hará por recursión: 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 14 
 
1. Para 𝛼 atómica, 𝑥 ocurre libre en 𝛼 sii 𝑥 ocurre en (es decir, es símbolo de) 𝛼. 
2. 𝑥 ocurre libre en (¬𝛼) sii 𝑥 ocurre libre en a. 
3. 𝑥 ocurre libre en (𝛼 → 𝛽) sii 𝑥 ocurre libre en 𝛼 o en 𝛽. 
4. 𝑥 ocurre libre en ∀𝑣𝑖𝛼 sii 𝑥 ocurre libre en 𝛼 y 𝑥 ≠ 𝑣𝑖. 
 
Esta definición usa implícitamente el teorema de recursión. Es posible reformular esto en 
términos de funciones. Para empezar se define para todas las fórmulas atómicas la función ℎ, 
como sigue: 
 
ℎ(𝛼) = 𝑒𝑙 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑡𝑜𝑑𝑎𝑠 𝑙𝑎 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠, 𝑠𝑖 𝑒𝑥𝑖𝑠𝑡𝑒 𝑎𝑙𝑔𝑢𝑛𝑎, 𝑒𝑛 𝑙𝑎 𝑓ó𝑟𝑚𝑢𝑙𝑎 𝑎𝑡ó𝑚𝑖𝑐𝑎 𝑎. 
 
Se quiere extender ℎ a una función ℎ̅ definida en todas las fórmulas de tal manera que: 
 
ℎ̅(ℰ¬(𝛼)) = ℎ̅(𝛼), 
ℎ̅(ℰ→(𝛼, 𝛽)) = ℎ̅(𝛼) ∪ ℎ̅(𝛽), 
ℎ̅(𝒬𝑖(𝛼)) = ℎ̅(𝛼) después de quitar 𝑣𝑖, si se encuentra presente. 
 
Entonces se puede decir que 𝑥 ocurre libre en 𝛼 (o que 𝑥 es una variable libre de 𝛼) sii 𝑥 ∈ ℎ̅(𝛼). 
La existencia de una única ℎ̅ (he aquí lo correcto de la definición) se sigue del teorema de 
recursión que se dio en la unidad anterior y del hecho (que se verá más adelante) de que cada 
fórmula tiene una descomposidón única. 
 
Al traducir un enunciado del lenguaje común, resulta irrelevante la elección de variables 
particulares. Anteriormente se tradujo “todas las manzanas están malas” como ∀𝑣1(𝐴𝑣1 → 𝐵𝑣1); 
pero de igual manera puede ser: 
∀𝑣27(𝐴𝑣27 → 𝐵𝑣27) 
 
De hecho, la variable se utiliza como un pronombre, tal como podrías decir en lenguaje común 
“para cualquier objeto dado, si él es una manzana, entonces él está malo” (así se tienen en el 
lenguaje una cantidad adecuada de pronombres: é𝑙1, é𝑙2, …), ya que la elección de variables 
particulares carece de importancia, frecuentemente ni siquiera se especifica la elección. En 
lugar de hacerlo, se escribe, por ejemplo, ∀𝑥(𝐴𝑥 → 𝐵𝑥), donde se entiende que 𝑥 es alguna 
variable. Esta falta de importancia más adelante se tratará como un teorema. Anteriormente se 
mencionó algo al respecto. 
 
En otras áreas de las matemáticas, las variables se usan de manera similar. Así, se tiene que 
en 
 
∑ 𝑎𝑖𝑗
7
𝑖=1
 
 
𝑖 es una variable "simulada" usada como contador, pero 𝑗 ocurre libre. 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 15 
 
 
2.1.4. Definición y ejemplos de enunciados 
 
Entre las fórmulas se tienen algunas que normalmente resultan ser más interesantes en su 
estudio: los enunciados. Éstos son, de manera intuitiva, las fórmulas que pueden traducirse sin 
espacios en blanco al lenguaje común, una vez que se ha dicho cómo interpretar los 
parámetros, según lo estudiado en en el tema anterior se motiva la siguiente definición. 
 
Definición 
Si ninguna variable ocurre libre en la fórmula 𝛼 (es decir, si ℎ̅(𝛼) = ∅), entonces 𝛼 es un 
enunciado. 
 
Por ejemplo, ∀𝑣2(𝐴𝑣2 → 𝐵𝑣2) y ∀𝑣3(𝑃𝑣3 → ∀𝑣3𝒬𝑣3) son enunciados; se debe tener cuidado con 
las variables pues en (∀𝑣1𝐴𝑣1 → 𝐵𝑣1), pese a que es parecida al primer ejemplo 𝑣1, ocurre 
libre; por lo tanto no es un enunciado. Las demás fórmulas que se pueden tener tienen una 
existencia de segunda clase y se usan, principalmente, como bloques de construcción de los 
enunciados. 
 
Dentro de la matemática utilizadas hasta el momento, las “variables” que se usan no ocurren 
libres pues esto dejaría el enunciado incompleto, sin sentido dentro de lo que se está 
trabajando, ya sea teoría de conjuntos, álgebra o geometría. Las proposiones que se le han 
presentado al (a la) alumno(a) dentro de los cursos son enunciados dentro de la lógica. A lo 
largo de esta unidad se presentan distintos ejemplos de proposiciones y axiomas usandos de 
manera frecuente dentro de la matemática para demostrar la importancia de este lenguaje. 
 
Para simplificar la escritura de los enunciados y de las fórmulas en general, se exponen a 
continuacion algunas convenciones y abreviaturas del lenguaje que se está haciendo. 
 
Se especifica cualquier expresión, en particular una fórmula, al escribir una linea que muestre 
explícitamente cada símbolo. Por ejemplo: 
 
∀𝑣1 ((¬= 𝑣10) → (¬∀𝑣2(¬= 𝑣1𝑆𝑣2))) 
 
Esta forma de expresar las cosas no es tan fácil de comprender, al menos aprimera vista, pese 
a que es realmente completa y formal. La falta de comprensión se debe, en un principio, a la 
forma simple que se le dio al lenguaje considerado desde un principio, pues no se le dotó de un 
cuantificador existencial. Las nuevas consideraciones permitirán escribir expresiones como: 
 
∀𝑣1(𝑣1 ≠ 0 → ∃𝑣2𝑣1 = 𝑆𝑣2) 
 
esta forma es más clara que la anterior, tanto por el significado e como porque se puede poner 
un poco de conocimiento previo de cálculo para darle un contexto familiar. 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 16 
Es importante notar que esta nueva consideración no cambia la definición de la fórmula. 
Solamente prepara la manera de fijar ciertas formas de nombrar fórmulas. Si se da el caso en 
que la sucesión de símbolos resulte importante, se debe seguir con la antigua notación. 
 
Las abreviaciones que se hacen son las siguientes: si 𝛼 y 𝛽 son fórmulas, 𝑥 es una variable y 𝑢 
y 𝑡 son términos: 
 
 (𝛼 ∨ 𝛽) es la abreviación de ((¬𝛼) → 𝛽). 
 (𝛼 ∧ 𝛽) es la abreviación de (¬(𝛼 → (¬𝛽))). 
 (𝛼 ↔ 𝛽) es la abreviación de (¬ ((𝛼 → 𝛽) → (¬(𝛽 → 𝛼)))). 
 ∃𝑥 𝛼 es la abreviación de (¬∀𝑥(¬𝛼)). 
 𝑢 = 𝑡 es la abreviación de = 𝑢𝑡. De manera similar, se abrevia a algunos otros símbolos 
de funciones y de predicados de dos argumentos. Por ejemplo, 2 < 3 abrevia < 2 3, y 
2 + 2 abrevia +2 2. 
 𝑢 ≠ 𝑡 abrevia (¬= 𝑢 𝑡); de forma similar, 𝑢 ≮ 𝑡 abrevia (¬< 𝑢 𝑡). 
 
En cuanto a los paréntesis, no sólo se usan ( y ), sino también [ y ], etc. Se omiten la mención 
de tantos como resulte posible. Con ese fin, se adoptan las siguientes convenciones: 
 
1. Los paréntesis externos se pueden omitir. Por ejemplo, ∀𝑥 𝛼 → 𝛽 es (∀𝑥 𝛼 → 𝛽). 
 
2. ¬, ∀ y ∃ se aplican a lo menos posible. Por ejemplo: 
 
¬𝛼 ∧ 𝛽 es ((¬𝛼) ∧ 𝛽), y no ¬(𝛼 ∧ 𝛽). 
∀𝑥 𝛼 → 𝛽 es (∀𝑥 𝛼 → 𝛽), y no ∀𝑥(𝛼 → 𝛽). 
∃𝑥 𝛼 ∧ 𝛽 es (∃𝑥 𝛼 ∧ 𝛽), y no ∃𝑥 (𝛼 ∧ 𝛽). 
 
En estos casos, incluso se pueden agregar paréntesis sin cambiar el significado, como 
en (∃𝑥 𝛼) ∧ 𝛽. 
 
3. ∧ y ∨ se aplican a lo menos posible, según lo establecido en la convención 2. Por 
ejemplo: 
 
¬𝛼 ∧ 𝛽 
 
4. Cuando se use repetidamente un conectivo, la expresión se agrupará a la derecha. Por 
ejemplo: 
𝛼 → 𝛽 → 𝛾 es 𝛼 → (𝛽 → 𝛾) 
 
Para entender un poco más las convenciones, considérese el siguiente ejemplo. 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 17 
Ejemplo 2.1.4.1 
1. ∃𝑥(𝐴𝑥 ∧ 𝐵𝑥) es (¬∀𝑥 (¬ (¬(𝐴𝑥 → (¬𝐵𝑥))))). Al usar las propiedades de la negación, se 
tiene una fórmula equivalente: (¬∀𝑥(𝐴𝑥 → (¬𝐵𝑥))). 
 
2. ∃𝑥 𝐴𝑥 → 𝐵𝑥 es ((¬∀𝑥(¬𝐴𝑥)) → 𝐵𝑥). 
∃𝑥 (𝐴𝑥 → 𝐵𝑥) es (¬∀𝑥(¬(𝐴𝑥 → 𝐵𝑥))). 
 
 
 
Es momento de evaluar lo aprendido hasta este punto resolviendo la siguiente actividad. 
 
 
2.2. Verdad y modelos 
 
Como se hizo en la lógica de enunciados, donde las asignaciones de verdad decían qué 
símbolos se interpretaban como ciertos y cuales como falsos, en la lógica de primer orden las 
estructuras desempeñan determinan si los enunciados son ciertos o falsos. Este tema está 
dedicado al estudio de este tipo especial de funciones. 
 
 
2.2.1. Interpretaciones o estructuras 
 
Las estructuras suministran el diccionario para traducir del lenguaje formal al lenguaje común; 
por ello, en algunas ocasiones se les denominan interpretaciones. Sin embargo, en este curso 
se considera sólo el nombre de estructura, ya que es posible que la palabra interpretación se 
use en un concepto distinto en un curso más adelante. 
 
La estructura para un lenguaje de primer orden expresa: 
 
 A qué colección de objetos se refiere el símbolo de cuantificador universal (∀). 
 Qué denotan los otros parámetros (los símbolos de función y de predicado). 
 
Formalmente, una estructura 𝔄 para el lenguaje dado de primer orden es una función cuyo 
dominio es el conjunto de parámetros, pues: 
 
 𝔄 le asigna al símbolo de cuantificador ∀ un conjunto no vacío |𝔄| llamado el universo 
(o dominio) de 𝔄. 
 𝔄 le asigna a cada símbolo de predicado 𝑃 de 𝑛 argumentos una relación 𝑛-aria 𝑃𝔄 ⊆
|𝔄|𝑛, es decir, 𝑃𝔄 es un conjunto de 𝑛-adas de elementos del universo. 
 𝔄 le asigna a cada símbolo de constante 𝑐 un elemento 𝑐𝔄 del universo |𝔄|. 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 18 
 𝔄 le asigna a cada símbolo de función 𝑓 de 𝑛 argumentos una operación 𝑛-aria 𝑓𝔄 sobre 
|𝔄|, es decir, 𝑓𝔄: |𝔄|𝑛 → |𝔄|. 
 
La idea es que 𝔄 le asigna significado a los parámetros. ∀ significa "para todo objeto de |𝔄|". El 
símbolo 𝑐 es para nombrar al punto 𝑐𝔄. La fórmula atómica 𝑃𝑡1 ⋯ 𝑡𝑛, significa que la 𝑛-ada de 
puntos nombrados por 𝑡1, … , 𝑡𝑛, está en la relación 𝑃
𝔄. 
 
Nótese que se requiere que el universo |𝔄| sea no vacío. Obsérvese también que 𝑓𝔄 deberá 
tener la totalidad de |𝔄|𝑛 como su dominio, pues no se ha hecho ningún comentario sobre las 
funciones parcialmente definidas. 
 
Ejemplo 2.2.1.1. 
1. Considérese el lenguaje de la teoría de conjuntos, cuyo único parámetro, además de ∀, es 
∈. Tómese la estructura 𝔄 con: 
|𝔄| = el conjunto de los números naturales, 
∈𝔄= el conjunto de los pares 〈𝑚, 𝑛〉 tal que 𝑚 < 𝑛. 
 
Nótese que para este caso se traduce ∈ como “es menor que”, esto de acuerdo con la 
construcción de los números naturales como conjuntos. En presencia de una estructura, es 
posible traducir enunciados del lenguaje formal al lenguaje común y tratar de decir si estas 
traducciones son verdaderas o falsas. El enunciado en el lenguaje de primer orden: 
 
∃𝑥∀𝑦¬𝑦 ∈ 𝑥, 
 
más formalmente, (¬∀𝑣1(¬∀𝑣2(¬ ∈ 𝑣2𝑣1))), con la traducción propia de la teoría de conjuntos 
afirma la existencia de un conjunto vacío, pero se traduce con 𝔄 como: 
 
Existe un número natural tal que ningún número natural es menor que él. 
 
Esto es verdad, por lo tanto se dice que ∃𝑥∀𝑦¬𝑦 ∈ 𝑥 es verdadero en 𝔄 o que 𝔄 es un modelo 
del enunciado. Por otro lado, 𝔄 no es modelo del axioma del par 
 
∀𝑥∀𝑦∃𝑧∀𝑡(𝑡 ∈ 𝑧 ↔ 𝑡 = 𝑥 ∨ 𝑡 = 𝑦), 
 
pues la traducción de este enunciado con 𝔄 es falsa, pues no hay número natural 𝑚 tal que 
para cada 𝑛, 
𝑛 < 𝑚 𝑠𝑖𝑖 𝑛 = 1 
 
2. Considérese que el lenguaje tiene únicamente los parámetros ∀ y un símbolo de predicado 
de dos argumentos 𝐸, y una estructura finita 𝔅 con un universo |𝔅| que consiste en un 
conjunto de cuatro objetos distintos {𝑎, 𝑏, 𝑐, 𝑑}. Supóngase que la relación binaria 𝐸𝔅 es el 
siguiente conjunto de pares: 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 19 
𝐸𝔅 = {〈𝑎, 𝑏〉, 〈𝑏, 𝑎〉, 〈𝑏, 𝑐〉, 〈𝑐, 𝑐〉} 
 
Entonces se puede describir 𝔅 como la gráfica dirigida cuyo conjunto de vértices es el universo 
{𝑎, 𝑏, 𝑐, 𝑑}: 
 
En este contexto se interpreta 𝐸𝑥𝑦 como si la gráfica tuviera una arista del vértice 𝑥 al vértice 𝑦. 
Así se considera una gráfica dirigida. 
 
Considérese el enunciado ∃𝑥 ∀𝑦 ¬𝑦𝐸𝑥. Con la estructura 𝔅 se puede traducir como sigue: 
 
Existe un vértice tal que, para todo vértice, ninguna arista va del último al primero. 
 
Leer el enunciado en lenguaje común es un poco más difícil de leer que la versión en símbolos. 
 
Este enunciado se encuentra dentro de la estructura 𝔅 debido a que ninguna arista apunta al 
vértice 𝑑. 
 
 
 
2.2.2. Definición de satisfacción 
 
En los ejemplos anteriores fue intuitivamente claro que ciertos enunciados del lenguaje formal 
eran verdaderos en la estructura y otros eran falsos. Sin embargo, es necesaria una definición 
matemáticaprecisa de “𝜎 es verdadero en 𝔄”. De ahí que se deba expresar en términos 
matemáticos sin emplear traducciones al lenguaje común o a algún idioma ni criterios supuestos 
para afirmar que algunos enunciados son verdaderos mientras y otros son falsos (si se piensa 
que se tiene tal criterio, póngase a prueba con el enunciado "Este enunciado es falso". Este es 
un ejemplo de lenguaje común de un enunciado que no se puede afirmar como verdad o 
mentira, ya que, al otorgarle el valor de verdadero, él mismo asegura su falsedad, lo cual suena 
como una inconsistencia o contradicción). En otras palabras, se requiere tomar el concepto 
informal “𝜎 es verdadero en 𝔄” y hacerlo parte de las matemáticas. 
 
Con el objetivo de definir “𝜎 es verdadero en 𝔄”, 
 
⊨𝔄 𝜎, 
 
para enunciados 𝜎 y estructuras 𝔄, primero se define un concepto más general relativo a las 
fórmulas: 
 
a 
b c d 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 20 
 𝜑 es una fórmula del lenguaje. 
 𝔄 es una estructura para el lenguaje. 
 𝑠: 𝑉 → |𝔄| es una función del conjunto 𝑉 de todas las variables, en el universo |𝔄| de 𝔄. 
 
Ahora se define qué significa que 𝕬 satisfaga 𝝋 con 𝒔: 
 
⊨𝔄 𝜑[𝑠]. 
 
De manera informal se puede dar esta definición como sigue: 
 
Definición (informal) 
⊨𝔄 𝜑[𝑠] si la traducción de 𝜑 determinada por 𝔄, donde la variable 𝑥 se traduce como 𝑠(𝑥) en 
cualquier lugar en que ocurra libre es verdadera. 
 
La definición formal de satisfacción procede de la siguiente forma para cada tipo de elemento 
en el lenguaje: 
 
I. Términos. Se define la extensión 
 
�̅�: 𝑇 → |𝔄|, 
 
una función del conjunto 𝑇 de todos los términos, en el universo de 𝔄. La idea es que �̅�(𝑡) debe 
ser el elemento del universo 𝔄 que se nombra mediante el término 𝑡. Así �̅� se define por 
recursión como sigue: 
 
1. Para cada variable 𝑥, �̅�(𝑥) = 𝑠(𝑥). 
2. Para cada símbolo de constante 𝑐, �̅�(𝑐) = 𝑐𝔄. 
3. Si 𝑡1, … , 𝑡𝑛 son términos y 𝑓 es un símbolo de función de 𝑛 argumentos, entonces 
 
�̅�(𝑓𝑡1 ⋯ 𝑡𝑛) = 𝑓
𝔄(�̅�(𝑡1), … , �̅�(𝑡𝑛)). 
 
Este último puede verse por ejemplo con 𝑛 = 1, con el diagrama conmutativo siguiente: 
 
 
La existencia de una única extensión �̅� de 𝑠 se sigue del teorema de la recursión que se dio en 
la unidad pasada, se considera también algo que se discutirá más adelante, relacionado con 
que los términos tienen descomposiciones únicas. Debe notarse que �̅� depende tanto de 𝑠 
como de 𝔄. 
𝑇 |𝔄| 
𝑇 |𝔄| 
 
�̅� 
�̅� 
ℱ𝑓 
F 
𝑓𝔄 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 21 
 
II. Fórmulas atómicas. Las fórmulas atómicas se definieron explícitamente, no de manera 
inductiva. Por lo tanto, la definición de satisfacción de las fórmulas atómicas es también 
explícita y no recursiva. 
 
1. ⊨𝔄= 𝑡1𝑡2[𝑠] sii �̅�(𝑡1) = �̅�(𝑡2). 
 
Entonces, = significa =. Nótese que = es un símbolo lógico, no un parámetro sujeto a 
interpretación. 
 
2. Para un parámetro de predicado 𝑃 de 𝑛 argumentos, 
 
⊨𝔄 𝑃𝑡1 ⋯ 𝑡𝑛[𝑠] 𝑠𝑖𝑖 〈�̅�(𝑡1), … , �̅�(𝑡𝑛)〉 ∈ 𝑃
𝔄. 
 
III. Otras fórmulas. Las fórmulas que se definen por inducción tienen, en consecuencia, una 
definición de satisfacción por recursión. 
 
1. Para fórmulas atómicas, la definición es la del punto II. 
2. ⊨𝔄 ¬𝜑[𝑠] sii ⊭𝔄 𝜑[𝑠]. 
3. ⊨𝔄 (𝜑 → 𝜓)[𝑠] sii ⊭𝔄 𝜑[𝑠], o ⊨𝔄 𝜓[𝑠], o ambos (esto no es más que la asociación 
usual de verdad para →). En otras palabras, si 𝔄 satisface a 𝜑 con 𝑠, entonces 𝔄 
satisface a 𝜓 con 𝑠. 
4. ⊨𝔄 ∀𝑥 𝜑[𝑠] sii para todo 𝑑 ∈ |𝔄|, se tiene: 
 
⊨𝔄 𝜑[𝑠(𝑥|𝑑)]. 
 
Donde [𝑠(𝑥|𝑑)] es la función exactamente como 𝑠, excepto que en la variable 𝑥 toma el valor 𝑑. 
Dicho de otra forma: 
 
𝑠(𝑥|𝑑)(𝑦) = {
𝑠(𝑦), 𝑠𝑖 𝑦 ≠ 𝑥,
𝑑, 𝑠𝑖 𝑦 = 𝑥
. 
 
Entonces ∀ significa “para todos los objetos de |𝔄|”. 
 
Puede revisarse de nuevo la definición informal que se presentó y su formalización. Con lo que 
se puede apreciar que la definición de satisfacción es una aplicación del teorema de recursión y 
que las fórmulas tienen descomposiciones únicas. Así es posible poner esta definición en 
términos de funciones, como se hizo en la Unidad 1, para que se vea de manera más directa 
cómo se aplica el teorema de recursión. 
 
1. Considerar un 𝔄 fijo. 
2. Definir una función ℎ̅ que extiende a una función ℎ definida en las fórmulas atómicas, 
tal que para cualquier fórmula 𝜑, ℎ̅(𝜑) es un conjunto de funciones de 𝑉 en |𝔄|. 
3. Se define 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 22 
⊨𝔄 𝜑[𝑠] 𝑠𝑖𝑖 𝑠 ∈ ℎ̅(𝜑). 
 
Se puede escribir en detalle la definición explicita de ℎ y las cláusulas que determinan de 
manera única su extensión ℎ̅ para entender esta definición sobre la extensión. Una forma 
alternativa es considerar que ℎ̅(𝜑) es un conjunto de funciones en el conjunto de aquellas 
variables que ocurren libres en 𝜑. 
 
Aunque todo lo anteriormente dicho es lo más cercano a la intuición, resulta un poco difícil de 
entender si se continúa trabajando sólo en el nivel abstracto de un lenguaje, por lo que se 
presentan algunos ejemplos para aterrizar estos conceptos. 
 
Ejemplo 2.2.2.1. 
Supóngase que el lenguaje cuenta con los parámetros ∀, 𝑃 (símbolo de predicado de dos 
argumentos), 𝑓 (símbolo de función de un argumento) y 𝑐 (símbolo de constante). Sea 𝔄 la 
estructura para este lenguaje definida como sigue: 
 
|𝔄| = ℕ, el conjunto de todos los números naturales. 
\𝑃𝔄 = el conjunto de pares 〈𝑚, 𝑛〉 tales que 𝑚 ≤ 𝑛. 
𝑓𝔄 = la función sucesor 𝑆. 
𝑐𝔄 = 0. 
 
De acuerdo con los conocimientos y omitiendo que 𝔄 es en realidad una función, es posible 
describir sus componentes: 
𝔄 = (ℕ; ≤, 𝑆, 0) 
 
Tal notación no tiene ambigüedad cuando el contexto aclara exactamente qué componentes 
van con qué parámetros. Cada una de las siguientes afirmaciones es consecuencia de la 
definición donde se dan las condiciones que se deben cumplir para 𝔄. 
 
Sea 𝑠: 𝑉 → ℕ la función para la cual 𝑠(𝑣𝑖) = 𝑖 − 1, es decir, 𝑠(𝑣1) = 0, 𝑠(𝑣2) = 1, … 
 
1. �̅�(𝑓𝑓𝑣3) = 𝑆(𝑆(2)) = 4 y �̅�(𝑓𝑣1) = 𝑆(0) = 1 
2. �̅�(𝑐) = 0 y �̅�(𝑓𝑓𝑐) = 2; sin usar 𝑠. 
3. ⊨𝔄 𝑃𝑐𝑓𝑣1[𝑠]. Al traducirse al lenguaje común, resulta en un enunciado verdadero “0 ≤
1”. Más formalmente esto es porque : 
 
〈�̅�(𝑐), �̅�(𝑓𝑣1 )〉 = 〈0,1〉 ∈ 𝑃
𝔄 
 
4. ⊨𝔄 ∀𝑣1𝑃𝑐𝑣1. La traducción al lenguaje común es “0 es menor o igual que cualquier 
número natural”. Se debe verificar formalmente que para todo 𝑛 ∈ ℕ, 
 
⊨𝔄 𝑃𝑐𝑣1[𝑠(𝑣1|𝑛)] 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 23 
que se reduce a 〈0, 𝑛〉 ∈ 𝑃𝔄, es decir, 0 ≤ 𝑛. 
 
5. ⊭𝔄 ∀𝑣1 𝑃𝑣2𝑣1[𝑠] porque existe un número natural 𝑚, tal que 
 
⊭𝔄 𝑃𝑣2𝑣1[𝑠(𝑣1|𝑚)]; 
 
es decir, 〈𝑠(𝑣2), 𝑚〉 ∉ 𝑃
𝔄, puesto que 𝑠(𝑣2) = 1. Se puede tomar 𝑚 = 0, para 
comprobarlo. Hay que recordar la definición de 𝑠(𝑣1|𝑛) y de 𝑃
𝔄. 
 
 
Ejemplo 2.2.2.2. 
Como anteriormente se había hecho, considérese la siguiente estructura 𝔅 con 
 
|𝔅| = {𝑎, 𝑏, 𝑐, 𝑑} 𝑦 𝐸𝔅 = {〈𝑎, 𝑏〉, 〈𝑏, 𝑎〉, 〈𝑏, 𝑐〉, 〈𝑐, 𝑐〉} 
 
para el lenguaje con los parámetros ∀ y 𝐸. Se tiene el siguiente diagrama: 
 
 
Entonces, ⊨𝔅 ∀𝑣2¬𝐸𝑣2𝑣1[𝑠] sii 𝑠(𝑣1) = 𝑑. No hay arista que apunte al vértice 𝑑; además, éste 
es el único con esta propiedad. Es posible plantear la negación de esta fórmula como 
⊨𝔅 ∃𝑣2𝐸𝑣2𝑣1[𝑠] sii 𝑠(𝑣1) ∈ {𝑎, 𝑏, 𝑐}. Analícese con cuidado tanto el orden de la fórmula como el 
contexto que le da significado. 
 
De esta forma seplantea, de manera formalizada y apoyada de la concepción informal, lo que 
significa que una estructura satisfaga una fórmula del lenguaje. Teniendo en cuenta que dada 
una fórmula es muy importante la asignación que se hace del conjunto de todas las variables al 
universo, se puede ver que si se cambiara la asignación 𝑠 en el primer ejemplo de estos dos, 
podría cambiarse el significado de los enunciados y el valor de verdad de las fórmulas. 
 
 
2.2.3. Definición de verdad para enunciados y definición de modelo 
 
Cuando se quiere saber si la estructura 𝔄 satisface o no una fórmula 𝜑 con 𝑠, es necesaria toda 
la (cantidad infinita de) información que se tiene con 𝑠. Lo que importa son los valores de la 
función 𝑠 en (la cantidad finita de) variables que ocurren libres en 𝜑. En particular, si 𝜑 es un 
enunciado, entonces 𝑠 no importa en absoluto. Sobre esto el siguiente teorema. 
 
Teorema 
a 
b c d 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 24 
Si 𝑠1 y 𝑠2 son funciones de 𝑉 en |𝔄| que coinciden en todas las variables que ocurren libres (si 
las hay) en la fórmula 𝜑, entonces: 
 
⊨𝔄 𝜑[𝑠1] 𝑠𝑖𝑖 ⊨𝔄 𝜑[𝑠2] 
 
Demostración 
Como la satisfacción se definió por recursión, la demostración se hará con inducción. 
Se considera la estructura 𝔄 fija. Se probará por inducción que cada fórmula 𝜑 tiene la 
propiedad de que siempre que dos funciones 𝑠1, 𝑠2 coinciden en las variables libres de 𝜑, 𝔄 
satisface 𝜑 con 𝑠1 sii 𝔄 satisface 𝜑 con 𝑠2. Para esto se plantean los posibles casos de la 
fórmula. 
 
Caso 1. 𝜑 = 𝑃𝑡1 ⋯ 𝑡𝑛 es atómica. Entonces, en 𝜑 cualquier variable ocurre libre. Por tanto, 𝑠1 y 
𝑠2 coinciden en todas las variables en cada 𝑡𝑖 . De esto sigue que 𝑠1̅(𝑡𝑖) = 𝑠2̅(𝑡𝑖) para cada 𝑖, 
esto es en cierta forma directo por cómo se definen las extensiones, pero se puede dar la 
demostración formal por inducción sobre 𝑡𝑖. Entonces se tiene que 𝔄 satisface 𝑃𝑡1 ⋯ 𝑡𝑛 con 𝑠1 
sii 𝔄 satisface 𝑃𝑡1 ⋯ 𝑡𝑛 con 𝑠2. 
 
Casos 2 y 3. 𝜑 es ¬𝛼 o 𝛼 → 𝛽. Esto se sigue inmediatamente de la hipótesis de inducción. 
 
Caso 4. 𝜑 = ∀𝑥 𝜓. Las variables libres en 𝜑 son aquellas libres en 𝜓 con excepción de 𝑥. Por lo 
tanto, para cualquier 𝑑 en |𝔄|, 𝑠1(𝑥|𝑑) y 𝑠2(𝑥|𝑑) coinciden en todas las variables libres de 𝜓. Por 
hipótesis de inducción, . 𝔄 satisface con 𝑠1(𝑥|𝑑) sii 𝔄 satisface con 𝑠2(𝑥|𝑑). A partir de esto y de 
la definición de satisfacción, se puede ver que 𝔄 satisface ∀𝑥 𝜓 con 𝑠1 sii 𝔄 satisface ∀𝑥 𝜓 con 
𝑠2. 
 
La prueba anterior consiste en revisar la definición de satisfacción y observar qué información 
dada por 𝑠 se utilizó realmente. Hay un hecho análogo referente a las estructuras que se da sin 
demostración: 
 
Proposición 
Si 𝔄. y 𝔅 coinciden en todos los parámetros que ocurren en 𝜑, entonces ⊨𝔄 𝜑[𝑠] sii ⊨𝔅 𝜑[𝑠]. 
 
Justificado con teorema antes expuesto, se presenta la siguiente notación: 
 
Notación 
Si 𝜑 es una fórmula tal que todas las variables que ocurren libres en 𝜑 están incluidas entre 
𝑣1, … , 𝑣𝑘. Entonces, para elementos 𝑎1, … , 𝑎𝑘 de |𝔄|, 
 
⊨𝔄 𝜑[[𝑎1, … , 𝑎𝑘]] 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 25 
significa que 𝔄 satisface 𝜑 con cualquier función 𝑠: 𝑉 → |𝔄| para la cual 𝑠(𝑣𝑖) = 𝑎𝑖 , 1 ≤ 𝑖 ≤ 𝑘. 
Usando el ejemplo 2.2.2.1, en el que 𝔄 = (ℕ; ≤, 𝑆, 0), se tiene que ⊨𝔄 ∀𝑣2 𝑃𝑣1𝑣2[[0]], pero 
⊭𝔄 ∀𝑣2 𝑃𝑣1𝑣2[[3]]. 
 
Corolario (del teorema) 
Para un enunciado 𝜎 se tienen dos opciones: 
 
a) 𝔄 satisface 𝜎 con toda función 𝑠: 𝑉 → |𝔄|. 
b) 𝔄 no satisface 𝜎 con cualquier función 𝑠 de 𝑉 en |𝔄|. 
 
Con base en este corolario se presenta la siguiente definición. 
 
Definición 
Si se cumple la alternativa a) del corolario, se dice que 𝜎 es verdadero en 𝔄, ⊨𝔄 𝜎 o que 𝔄 es 
un modelo de 𝜎. De cumplirse la alternativa b), se tiene que 𝜎 es falso en 𝔄; sólo ocurre una 
de estas dos opciones dado que |𝔄| es no vacío. 𝔄 es un modelo de un conjunto 𝚺 de 
enunciados sii 𝔄 es un modelo de todos los elementos de Σ. 
 
 
Ejemplo 2.2.3.1 
Si ℜ es el campo de los reales, (ℝ; 0,1, +,⋅) y 𝔔 es el campo de los racionales, (ℚ; 0,1, +,⋅), 
existen enunciados válidos en uno y falsos en el otro. Por ejemplo el enunciado ∃𝑥 (𝑥 ⋅ 𝑥) = 1 +
1 es falso en el campo de los racionales, pues √2 es un número irracional y es cierto en el 
campo de los reales. 
 
Ejemplo 2.2.3.2 
 
Un lenguaje dado tiene sólo dos parámetros ∀ y 𝑃, donde 𝑃 es un símbolo de predicado de dos 
argumentos. Entonces una estructura 𝔄 queda determinada por el universo |𝔄| y la relación 
binaria 𝑃𝔄. De manera sólo descriptiva, abusando del lenguaje, puede denotarse 
 
𝔄 = (|𝔄|; 𝑃𝔄). 
 
Considérese el problema de caracterizar la clase de todos los modelos de los siguientes 
enunciados: 
 
1. ∀𝑥∀𝑦 𝑥 = 𝑦. Una estructura (𝐴; 𝑅) es un modelo de este enunciado sii 𝐴 tiene 
exactamente un elemento. 𝑅 puede ser vacío o puede ser el conjunto unitario 𝐴 × 𝐴. 
2. ∀𝑥∀𝑦 𝑃𝑥𝑦. Una estructura (𝐴; 𝑅) es un modelo de este enunciado sii 𝑅 = 𝐴 = 𝐴 × 𝐴, 
donde 𝐴 puede ser cualquier conjunto no vacío. 
3. ∀𝑥∀𝑦 ¬𝑃𝑥𝑦. Una estructura (𝐴; 𝑅) es un modelo de este enunciado sii 𝑅 = ∅. 
4. ∀𝑥∃𝑦 𝑃𝑥𝑦. Para que una estructura (𝐴; 𝑅) sea modelo de este enunciado se debe tener 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 26 
que el dominio de 𝑅 sea 𝐴. 
 
 
En este punto se debe tener dominado el concepto de satisfacción para comprender cómo la 
estructura es la que da el valor de verdad a un enunciado. Si se tiene algún problema en 
comprender esta situación, se necesita revisar una vez más las definiciones de satisfacción 
pensando en un contexto específico. El primer problema es la notación usada. 
 
La notación que se presentó es de cierta forma apropiada para adaptarse a las nociones que ya 
se tienen, por ejemplo se tiene que: 
 
a) ⊨𝔄 (𝛼 ∧ 𝛽)[𝑠] sii ⊨𝔄 𝛼[𝑠] y ⊨𝔄 𝛽[𝑠], de manera similar para ∨ y ↔. 
b) ⊨𝔄 ∃𝑥 𝛼[𝑠] sii hay algún 𝑑 ∈ |𝔄| con la propiedad de que ⊨𝔄 𝛼[𝑠(𝑥|𝑑)]. 
 
La demostración del punto b) puede ser como sigue: 
 
⊨𝔄 ∃𝑥 𝛼[𝑠] 𝑠𝑖𝑖 ⊨𝔄 ¬∀𝑥 ¬𝛼[𝑠],
 𝑠𝑖𝑖 ⊭𝔄 ∀𝑥 ¬𝛼[𝑠],
 𝑠𝑖𝑖 no pasa que para todo 𝑑 en |𝔄|,
 ⊨𝔄 ¬𝛼[𝑠(𝑥|𝑑)], por definición,
 𝑠𝑖𝑖 no pasa que para todo 𝑑 en |𝔄|,
 ⊭𝔄 𝛼[𝑠(𝑥|𝑑)], por definición,
 𝑠𝑖𝑖 para algún 𝑑 en |𝔄|, ⊨𝔄 𝛼[𝑠(𝑥|𝑑)].
 
 
La notación resulta natural y apropiada para trabajar con los enunciados y las estructuras. 
 
 
2.2.4. Implicación lógica 
 
Definición 
Sea Γ un conjunto de fórmulas y 𝜑 una fórmula. Entonces 𝚪 implica lógicamente a 𝜑, y se 
escribe Γ ⊨ 𝜑, sii para cada estructura 𝔄 del lenguaje y cada función 𝑠: 𝑉 → |𝔄| tal que 𝔄 
satisface cada elemento de Γ con 𝑠, 𝔄 también satisface a 𝜑 con 𝑠. 
 
Se utiliza el mismo símbolo, “⊨”, que se utilizó en la primera unidad para la implicación 
tautológica, pero en adelante denota sólo la implicación lógica. De igual manera se denota “𝛾 ⊨
𝜑” en lugar de “{𝛾} ⊨ 𝜑”. 
 
Para enunciados, la implicación lógica se puede presentar usando el teorema referido 
anteriormente con el siguiente corolario. 
 
Corolario 
Para un conjunto Σ; 𝜏 de enunciados, Σ ⊨ 𝜏 sii cada modelo de Σ es también modelo de 𝜏. Un 
enunciado 𝜏 es válido sii es verdadero en todas las estructuras. 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 27 
 
Ejemplo 2.2.4.1 
Considérense las siguientes implicaciones entre enunciados: 
 
1. ∀𝑣1 𝑄𝑣1 ⊨ 𝑄𝑣2.Ésta es sólo una particularización, si para todos es verdadero, lo es 
para uno de ellos. 
2. 𝑄𝑣1 ⊭ ∀𝑣1 𝑄𝑣1. Para demostrar esto basta encontrar una estructura 𝔄 y una sola 
función 𝑠: 𝑉 → |𝔄| tal que, por una parte, ⊨𝔄 𝑄𝑣1[𝑠] y por la otra, 𝔄 no es modelo de 
∀𝑣1 𝑄𝑣1. Para esto se necesita que |𝔄| tenga al menos dos elementos. 
3. ∀𝑣1 𝑄𝑣1 ⊨ ∃𝑣2 𝑄𝑣2. Ver esto es sencillo considerando que el universo de una estructura 
es no vacío. 
4. ∃𝑥 ∀𝑦 𝑃𝑥𝑦 ⊨ ∀𝑦 ∃𝑥 𝑃𝑥𝑦. Esto se verá más adelante, en el Tema 2.3. 
5. ∀𝑦 ∃𝑥 𝑃𝑥𝑦 ⊭ ∃𝑥 ∀𝑦 𝑃𝑥𝑦. 
 
 
La definición de implicación lógica es muy parecida a la de implicación tautológica que apareció 
en la Unidad 1. Sin embargo, hay una diferencia importante en cuanto a su complejidad. 
 
 
2.2.5. Equivalencia lógica 
 
Continuando con lo presentado en el tema anterior y siguiendo con una especie de analogía a 
lo presentado en la Unidad 1, se dice que 𝜑 y 𝜓 son lógicamente equivalentes (𝝋 ⊨⫤ 𝝍) sii 
𝜑 ⊨ 𝜓 y 𝜓 ⊨ 𝜑. 
 
Del ejemplo 2.2.4.1. en las partes 4 y 5 se puede ver que. aunque ∃𝑥 ∀𝑦 𝑃𝑥𝑦 ⊨ ∀𝑦 ∃𝑥 𝑃𝑥𝑦, 
estas fórmulas nos son lógicamente equivalentes, pues ∀𝑦 ∃𝑥 𝑃𝑥𝑦 ⊭ ∃𝑥 ∀𝑦 𝑃𝑥𝑦. 
 
 
2.2.6. Fórmulas universalmente válidas 
 
El análogo en primer orden del concepto de tautología es el concepto de fórmula válida: una 
fórmula 𝜑 es válida sii ∅ ⊨ 𝜑, escrito ⊨ 𝜑. Entonces 𝜑 es válida sii para cada 𝔄 y cada 
𝑠: 𝑉 → |𝔄|, 𝔄 satisface 𝜑 con 𝑠. 
 
Ejemplo 2.2.6.1 
1. ⊨ ¬¬𝜎 → 𝜎. Si 𝔄 es un modelo de ¬¬𝜎, entonces ⊭𝔄 ¬𝜎 de donde ⊨𝔄 𝜎. Prestando un 
poco de atención a lo que se está haciendo en esta secuencia de afirmaciones podría 
notarse que se ha usado la ley de la doble negación, la cual se va a probar. Se está 
probando la ley de la doble negación en el lenguaje formal considerado para esto, 
denominado lenguaje objeto (revisa en internet algunas definiciones de lo que en 
filosofía es el metalenguaje y el lenguaje objeto). Al hacer la demostración se usa 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 28 
cualquier razonamiento correcto, afuera en el metalenguaje, el lenguaje común, como 
se haría al razonar respecto de espacios vectoriales o gráficas. En particular, el 
razonamiento puede implicar principios que cuando se modelaran formalmente, 
implicarían ¬¬𝜎 y 𝜎. No hay circularidad o redundancia; pero los enunciados del 
metalenguaje que se usan, como era de esperarse, relacionados con las fórmulas del 
lenguaje objeto de las que se hablan. 
 
2. ⊨ ∃𝑥 (𝑄𝑥 → ∀𝑥 𝑄𝑥). Éste es un enunciado extraño, pero válido. 
 
 
Para notar un poco más las diferencias entre la lógica de enunciados y la de primer orden, 
supóngase que en lógica de enunciados se quiere saber si una fórmula 𝛼 es una tautología o 
no. La definición requiere considerar un número finito de asignaciones de verdad, cada una de 
las cuales es una función finita. Para cada una de tales asignaciones de verdad 𝑣, se debe 
calcular �̅�(𝛼), que puede realizarse efectivamente en una cantidad de tiempo finita (en 
consecuencia, el conjunto de tautologías es decidible, como se observó anteriormente). 
 
Cuando se requiere saber si una fórmula 𝜑 del lenguaje de primer orden, es o no válida, la 
definición exige que se considere cada estructura 𝔄. Esto requiere todos los conjuntos no 
vacíos, en seguida para cada estructura se requiere considerar cada función 𝑠 del conjunto 𝑉 de 
las variables en |𝔄|. Para cada 𝔄 y 𝑠 dadas, se debe determinar si 𝔄 satisface a 𝜑 con 𝑠 o no, 
cuando esto sucede es complicado que |𝔄| sea infinito. 
 
De acuerdo con lo anterior, no resulta sorprendente que el conjunto de las fórmulas válidas no 
sea decidible. Sin embargo más adelante se verá un concepto que resulta equivalente al de 
validez. Este es el de deducibilidad, que tiene una definición más cercana a la finitaria, por esta 
vía será posible probar que el conjunto de fórmulas válidas es efectivamente enumerable. De 
esta forma se tiene una caracterización concreta de tales fórmulas. 
 
 
2.2.7. Definibilidad de una estructura 
 
Empieza por considerar que se quiere estudiar el campo de los reales (ℝ; 0,1, +,⋅) compuesto 
por el conjunto de los números reales, junto con los elementos distinguidos 0 y 1, y las 
operaciones de suma y producto. Como antes, se considera el campo de los reales como la 
estructura 
ℜ = (ℝ; 0,1, +,⋅) 
 
en la que el lenguaje con igualdad tiene los símbolos de constante 0 y 1 y los símbolos de 
función de dos argumentos + y ⋅. Aunque no se incluye en el lenguaje un símbolo de orden <, 
se tiene manera para decir que “𝑥 ≥ 0”; pues en esta estructura, los elementos no negativos 
son exactamente los elementos con raíces cuadradas. Esto es, la fórmula ∃𝑣2 𝑥 = 𝑣2 ⋅ 𝑣2 se 
satisface en la estructura ℜ siempre que se asigne a 𝑥 un número no negativo, y sólo en ese 
caso, esto es: 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 29 
 
⊨ℜ ∃𝑣2 𝑣1 = 𝑣2 ⋅ 𝑣2[[𝑎]] ⟺ 𝑎 ≥ 0. 
 
Debido a esto, se dice que el intervalo [0, ∞) es definible en ℜ, y que la fórmula ∃𝑣2 𝑣1 = 𝑣2 ⋅ 𝑣2 
lo define. 
 
Además es posible dar la relación de orden en los reales, es decir, la relación binaria 
{〈𝑎, 𝑏〉 ∈ ℝ × ℝ|𝑎 ≤ 𝑏} en la estructura ℜ mediante la fórmula que expresa “𝑣1 ≤ 𝑣2”: 
 
∃𝑣3 𝑣2 = 𝑣1 + 𝑣3 ⋅ 𝑣3. 
 
Como un ejemplo más corto, considera la gráfica dirigida 
 
𝔄 = ({𝑎, 𝑏, 𝑐}; {〈𝑎, 𝑏〉, 〈𝑎, 𝑐〉}) 
 
donde el lenguaje tiene los parámetros ∀ y 𝐸: 
 
 
Entonces en 𝔄, el conjunto {𝑏, 𝑐} (el rango o imagen de la relación 𝐸𝔄) se define mediante la 
fórmula ∃𝑣2 𝐸𝑣2𝑣1. En cambio, el conjunto {𝑏} no es definible en 𝔄. Esto se debe a que no hay 
propiedad definible en la estructura que separaría a 𝑏 y 𝑐. La prueba de este hecho utilizará el 
teorema del homomorfismo, que se demostrará más adelante en el tema 2.2.8. 
 
Ahora se quiere establecer de manera precisa el concepto de definibilidad de un subconjunto 
del universo o de una relación en el universo. Considérese una estructura 𝔄 y una fórmula 𝜑 
cuyas variables libres se encuentren entre 𝑣1, … , 𝑣𝑘. Entonces se construye sobre |𝔄| la relación 
de aridad 𝑘 
 
{(𝑎1, … , 𝑎𝑘)| ⊨𝔄 𝜑[[𝑎1, … , 𝑎𝑘]]} 
 
Se denotará a este conjunto la relación de aridad 𝑘 que 𝜑 define en 𝔄. En general, se dice 
que una relación de aridad 𝑘 sobre |𝔄| es definible en 𝔄 sii existe una fórmula (cuyas variables 
libres se encuentran entre 𝑣1, … , 𝑣𝑘) que la define ahí. 
 
Ejemplo 2.2.7.1. 
Considérese una parte del lenguaje que se tiene para la teoría de números, específicamente 
que el lenguaje tiene los parámetros ∀,0, 𝑆, +,⋅. Sea 𝔑 la estructura compuesta: 
 
|𝔑| = ℕ, el conjunto de los números naturales. 
0𝔑 = 0, el número 0. 
𝑏 𝑐 
𝑎 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 30 
𝑆𝔑, +𝔑, ⋅𝔑 son 𝑆, +,⋅ , las funciones sucesor, suma y producto. 
Esto en una sola expresión podría ser: 
 
𝔑 = (ℕ; 0, 𝑆, +,⋅) 
 
Algunas relaciones sobre ℕ son definibles en 𝔑 y otras no. Lo más complicado podría ser 
demostrar que relaciones no son definibles, pues al no serlo, es complicado decir exactamente 
cómo son para ver que, en efecto, no son definibles. Suele usarse también el hecho de que 
hay una cantidad no numerable de relaciones sobre ℕ, y, unidamente, una cantidad numerable 
de posibles fórmulas para definir. 
 
Se presentan algunas relaciones definibles, (¿podría el (la) alumno(a), con base en éstas, 
definir alguna otra?) 
 
1. La relación de orden {〈𝑚, 𝑛〉|𝑚 < 𝑛} se define en 𝔑 mediante la fórmula 
∃𝑣3 𝑣1 + 𝑆𝑣3 = 𝑣2 
 
2. Para cualquier número natural 𝑛,{𝑛} es definible. Por ejemplo, {2} se define mediante 
la ecuación: 
𝑣1 = 𝑆𝑆0 
 
Por lo anterior, se tiene que 𝑛 es un 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑒𝑓𝑖𝑛𝑖𝑏𝑙𝑒 en 𝔑. 
3. El conjunto de los primos es definible en 𝔑. Esto es sencillo mediante la fórmula 
 
1 < 𝑣1 ∧ ∀𝑣2 ∀𝑣3 (𝑣1 = 𝑣2 ⋅ 𝑣3 → 𝑣2 = 1 ∨ 𝑣3 = 1) 
 
y recordando la definición usual de los números primos. Esta fórmula usa los 
parámetros 1 y <, que no están en 𝔑. Sin embargo {1} y < son definibles en 𝔑, así que 
es posible usar sus definiciones, por lo tanto el conjunto de los primos es definible por 
 
∃𝑣3 𝑆0 + 𝑆𝑣3 = 𝑣1 ∧ ∀𝑣2 ∀𝑣3 (𝑣1 = 𝑣2 ⋅ 𝑣3 → 𝑣2 = 𝑆0 ∨ 𝑣3 = 𝑆0) 
 
 
Se ha dicho hasta el momento qué significa que elementos dentro de una estructura sean 
definibles. Recuérdese un poco lo que se presenta en un curso de matemáticas, que 
usualmente inicia con algo parecido a alguna de las siguientes afirmaciones: 
 
1. “Una gráfica está compuesta, por definición, de un conjunto no vacío 𝑉 junto con un 
conjunto 𝐸, tal que...” 
2. “Un grupo está compuesto, por definición, de un conjunto no vacío 𝐺 junto con una 
operación binaria ∘ que satisface los axiomas..." 
3. “Un espacio vectorial se compone, por definición, de un conjunto no vacío 𝑉 junto con 
una operación binaria + y, para cada número real 𝑟, una operación llamada 
multiplicación escalar tal que...” 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 31 
 
Se quiere hacer una abstracción de esta situación. En cada caso, los objetos de estudio 
(gráficas, grupos, espacios vectoriales, etc.) son estructuras para un lenguaje adecuado, 
donde se les pide que se satisfagan un determinado conjunto Σ de enunciados, en estos casos 
denominados axiomas. En lo siguiente del curso en cuestión se estudian los modelos del 
conjunto Σ de axiomas, o al menos algunos de los modelos (esto puede ser muy conocido para 
el (la) estudiante en el caso de los grupos estudiados en álgebra o en el de los números reales 
como espacio vectorial o ℝ2. Piénsese en ellos como estructuras para sus lenguajes). 
 
Para un conjunto Σ de enunciados, sea 𝑀𝑜𝑑 Σ la clase de todos los modelos de Σ, es decir, la 
clase de todas las estructuras del lenguaje en las cuales todo elemento de Σ es verdadero. Para 
un solo enunciado 𝜏, se escribe 𝑀𝑜𝑑 𝜏. De manera paralela a esto dentro de la teoría de 
conjuntos se puede ver que si 𝑀𝑜𝑑 Σ es no vacío, es una clase propia, es decir, no es un 
conjunto sino algo “más grande”. Revísese la sección Para saber más, donde se presentan 
textos sobre la teoría de conjuntos. Cabe decir que su lenguaje es uno de lo que se estudia en 
esta sección, pero no el único y por eso se da en general. 
 
Una clase 𝒦 de estructuras del lenguaje es una clase elemental (𝐸𝐶) sii 𝒦 = 𝑀𝑜𝑑 𝜏 para algún 
enunciado 𝜏. 𝒦 es una clase elemental en sentido amplio (𝐸𝐶Δ) sii 𝒦 = 𝑀𝑜𝑑 Σ para algún 
conjunto Σ de enunciados (el adjetivo “elemental” se está usando aquí como sinónimo de 
“primer orden”). 
 
Ejemplo 2.2.7.2 
1. Si el lenguaje cuenta con igualdad y dos parámetros ∀ y 𝐸, donde 𝐸 es un símbolo de 
predicado de dos argumentos. Entonces una gráfica es una estructura para este 
lenguaje 𝔄 = (𝑉; 𝐸𝔄) consistente en un conjunto 𝑉 no vacío de objetos llamados 
vértices (o nodos), y una relación arista 𝐸𝔄 que es simétrica (si 𝑢𝐸𝔄𝑣, entonces 𝑣𝐸𝔄𝑢) 
y antirreflexiva (nunca 𝑣𝐸𝔄𝑣). Si el (la) alumno(a) está familiarizado con la teoría de 
gráficas, reconocerá estas condiciones desde el principio. El axioma que manifiesta que 
la relación arista es simétrica y antirreflexiva se puede traducir mediante el enunciado: 
 
∀𝑥(¬𝑥𝐸𝑥 ∧ ∀𝑦 (𝑥𝐸𝑦 → 𝑦𝐸𝑥)) 
 
Así, la clase de todas las gráficas es una clase elemental. Pueden cambiarse algunas 
restricciones, como cuando se estudian las gráficas dirigidas en las que se hace a un 
lado la simetría o se restringe sólo a graficas finitas. 
Vale la pena decir que la clase de todas las gráficas finitas no es una clase elemental, 
ni siquiera en el sentido amplio. 
 
2. Supóngase que el lenguaje tiene igualdad y los parámetros ∀,0,1, +,⋅. Los campos 
pueden ser considerados como estructuras para este lenguaje. La clase de todos los 
campos es una clase elemental. La clase de los campos de característica cero, que 
tienen como subcampo los racionales (para este ejemplo en particular se requiere 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 32 
conocimiento de álgebra moderna, en especial teoría de campos) es 𝐸𝐶Δ; no es 𝐸𝐶. 
Esto se sigue del teorema de compacidad para la lógica de primer orden que se verá 
más adelante. Es un buen ejemplo para introducirlo y ver su utilidad. 
 
 
Con estos ejemplos se tiene la definición de definibilidad de una estructura. 
 
2.2.8. Homomorfismos y teorema del homomorfismo 
 
El presente contenido será de vital importancia para el curso pues se usará para poder 
comprobar el teorema de completud. 
 
Dentro de los cursos que el (la) estudiante ha tomado es común que le hayan presentado el 
concepto de lo que significa que dos estructuras, con las que se esté trabajando, sean 
isomorfas: debe haber una correspondencia uno a uno entre sus universos |𝔄| y |𝔅| que 
“preserve” las operaciones y las relaciones. 
 
A continuación se explica que dos estructuras isomorfas, aunque no sean idénticas, deben 
tener las mismas propiedades matemáticas. Se quiere definir el concepto de isomorfismo en un 
contexto general y mostrar que dos estructuras isomorfas tienen que satisfacer exactamente los 
mismos enunciados. 
 
Definición 
Sean 𝔄, 𝔅 estructuras para el lenguaje. Un homomorfismo ℎ de 𝔄 en 𝔅 es una función 
ℎ: |𝔄| → |𝔅| con las propiedades siguientes: 
 
a) Para cada parámetro de predicado 𝑃 de 𝑛 argumentos y cada 𝑛-ada 〈𝑎1, … , 𝑎𝑛〉 de 
elementos de |𝔄|: 
〈𝑎1, … , 𝑎𝑛〉 ∈ 𝑃
𝔄 𝑠𝑖𝑖 〈ℎ(𝑎1), … , ℎ(𝑎𝑛)〉 ∈ 𝑃
𝔅 
 
b) Para cada símbolo de función 𝑓 de 𝑛 argumentos y para cada 𝑛-ada como antes: 
 
ℎ (𝑓𝔄(𝑎1, … , 𝑎𝑛)) = 𝑓
𝔅(ℎ(𝑎1), … , ℎ(𝑎𝑛)). 
 
En el caso de un símbolo de constante 𝑐, esto se convierte en ℎ(𝑐𝔄) = 𝑐𝔅. 
 
Las condiciones a) y b) se expresan normalmente como: “ℎ preserva las relaciones y las 
funciones”. Se pueden encontrar versiones más débiles de estas condiciones, pero para este 
curso se usarán estos tipos de homomorfismos. 
 
De manera análoga a como se ha hecho siempre en los cursos de matemáticas si además, ℎ es 
uno a uno, entonces se le llama un isomorfismo (o inmersión isomorfa) de 𝔄 en 𝔅. Si hay un 
isomorfismo de 𝔄 sobre 𝔅, es decir, un isomorfismo ℎ para el cual 𝑟𝑎𝑛 ℎ = |𝔅|, se dice que 𝔄 y 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 33 
𝔅 son isomorfas, denotado como 𝔄 ≅ 𝔅. De nuevo, si se está familiarizado con la teoría de 
grupos o de campos se tendrá más presente el concepto. 
 
Ejemplo 2.2.8.1. 
Si se tiene un lenguaje con los parámetros ∀, +,⋅ . Sea 𝔄 la estructura (ℕ; +,⋅). Es posible 
definir la función ℎ: ℕ → {𝑒, 𝑜} mediante: 
 
ℎ(𝑛) = {
𝑒 𝑠𝑖 𝑛 𝑒𝑠 𝑝𝑎𝑟
𝑜 𝑠𝑖 𝑛 𝑒𝑠 𝑖𝑚𝑝𝑎𝑟
 
 
Entonces, ℎ es un homomorfismo de 𝔄 sobre 𝔅 donde |𝔅| = {𝑒, 𝑜} y +𝔅, ⋅𝔅 se obtiene 
mediante las tablas siguientes: 
 
+𝔅 𝑒 𝑜 ⋅𝔅 𝑒 𝑜 
𝑒 𝑒 𝑜 𝑒 𝑒 𝑒 
𝑜 𝑜 𝑒 𝑜 𝑒 𝑜 
 
Se puede verificar que se satisface la condición b) de la definición 2.2.8.1. Por ejemplo, si 𝑛 y 
𝑚 son ambos números impares, entonces ℎ(𝑛 + 𝑚) = 𝑒 y ℎ(𝑛) +𝔅 ℎ(𝑏) = 𝑜 +𝔅 𝑜 = 𝑒. 
 
 
El siguiente ejemplo pretende introducir el concepto de una subestructura. 
 
Ejemplo 2.2.8.2. (Subestructura) 
Sea ℙ el conjunto de los enteros positivos, sea <𝑃 larelación de orden usual en ℙ y sea <ℕ la 
relación de orden usual en ℕ. Para empezar recuérdese que para este curso, pues esto varía 
según los autores, se tiene que ℕ = {0,1,2, … } y ℙ = {1,2,3,4, … }. Entonces existe un 
isomorfismo ℎ de la estructura (ℙ; <𝑝) sobre (ℕ; <𝑁). Considérese que, por ejemplo, ℎ(𝑛) =
𝑛 − 1 y la función identidad 𝐼𝑑: ℙ → ℕ es un isomorfismo de (ℙ; <𝑝) en (ℕ; <𝑁). Debido a esto 
se dice que (ℙ; <𝑝) es una subestructura de (ℕ; <𝑁). 
 
 
De forma más general se dará la definición de subestructura y extensión como sigue. 
 
Definición 
Tómense dos estructuras 𝔄 y 𝔅 para el lenguaje, tales que |𝔄| ⊆ |𝔅|. A partir de la definición de 
homomorfismo, debe ser claro que la función identidad de |𝔄| en |𝔅| es un isomorfismo de 𝔄 en 
𝔅 sii: 
 
a. 𝑃𝔄 es la restricción de 𝑃𝔅 a |𝔄|, para cada parámetro de predicado 𝑃. 
b. 𝑓𝔄 es la restricción de 𝑓𝔅 a |𝔅|, para cada símbolo de función y 𝑐𝔄 = 𝑐𝔅, para cada 
símbolo de constante 𝑐. 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 34 
 
Si se cumplen estas condiciones, se dice que 𝔄 es una subestructura de 𝔅 y que 𝔅 es una 
extensión de 𝔄. 
 
Por ejemplo, en un lenguaje con un símbolo de función de dos argumentos +, la estructura 
(ℚ; +𝑄) es una subestructura de (ℂ; +𝐶), donde se consideran las respectivas sumas en cada 
campo y la suma de los racionales como restricción de la suma de complejos. 
 
En este ejemplo, el conjunto ℚ es cerrado bajo +𝐶: la suma de dos números racionales es un 
racional. De una forma más general, siempre que 𝔄 sea una subestructura de 𝔅, |𝔄| debe ser 
cerrado bajo 𝑓𝔅 para cada símbolo de función 𝑓. Esta propiedad de cerradura se cumple 
incluso en los símbolos de función de 0 argumentos. Así, 𝑐𝔅 debe pertenecer a |𝔄| para cada 
símbolo de constante 𝑐. 
 
Si se tiene una estructura 𝔅 y 𝐴 es un subconjunto no vacío de |𝔅| cerrado bajo todas las 
funciones de 𝔅, como se mencionó antes. Entonces es posible hacer una subestructura de 𝔅 
con universo 𝐴. De hecho, hay una sola manera de hacer esto. El universo es 𝐴, a cada 
parámetro de predicado 𝑃 se le asigna la restricción de 𝑃^𝔅 a 𝐴, y se hace lo mismo para los 
símbolos de función. Si el lenguaje no tiene símbolos de función, ni siquiera símbolos de 
constante, se puede hacer una subestructura a partir de cualquier subconjunto 𝐴 no vacío de 
|𝔅|. 
 
Éstos son básicamente conceptos algebraicos y el teorema siguiente los relaciona con los 
conceptos lógicos de verdad y de satisfacción. 
 
Teorema (el homomorfismo) 
Sea ℎ un homomorfismo de 𝔄 en 𝔅 y sea 𝑠 una función del conjunto de las variables en |𝔄|: 
 
a) Para cualquier término 𝑡 se tiene ℎ(�̅�(𝑡)) = ℎ ∘ 𝑠̅̅ ̅̅ ̅̅ (𝑡), donde �̅�(𝑡) se calcula en 𝔄 y ℎ ∘ 𝑠̅̅ ̅̅ ̅̅ (𝑡) 
se calcula en 𝔅. 
b) Para cualquier fórmula 𝛼 libre de cuantificadores que no contenga símbolo de igualdad, 
⊨𝔄 𝛼[𝑠] 𝑠𝑖𝑖 ⊨𝔅 𝛼[ℎ ∘ 𝑠] 
c) Si ℎ es uno a uno (es decir, es un isomorfismo de 𝔄 en 𝔅), en la parte b) se puede 
eliminar la restricción “no contenga símbolo de igualdad”. 
d) Si ℎ es un homomorfismo de 𝔄 sobre 𝔅, en b) se puede eliminar la restricción “libre de 
cuantificadores”. 
 
Demostración 
La parte a) usa inducción sobre 𝑡 y es muy directo, así que, como práctica del teorema de 
inducción, considérese completar los detalles. Nótese que ℎ ∘ 𝑠 es una función del conjunto de 
las variables en |𝔅| y su extensión al conjunto de todos los términos es ℎ ∘ 𝑠̅̅ ̅̅ ̅̅ . Esta función se 
evalúa. Aquí, en 𝑡. 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 35 
c) Para una fórmula atómica tal como 𝑃𝑡, se tiene: 
d) 
⊨𝔄 𝑃𝑡[𝑠] ⟺ �̅�(𝑡) ∈ 𝑃
𝔄 
⟺ ℎ(�̅�(𝑡)) ∈ 𝑃𝔅, pues se trata de un homomorfismo 
⟺ ℎ ∘ 𝑠̅̅ ̅̅ ̅̅ (𝑡) ∈ 𝑃𝔅, por a) 
⟺⊨𝔅 𝑃𝑡[ℎ ∘ 𝑠]. 
 
Se requiere, entonces, un argumento inductivo para manejar el caso de los símbolos de 
conectivo. También se puede hacer de manera directa. De nuevo, complétense esos detalles 
como ejercicio. 
 
c) En cualquier caso: 
 
⊨𝔄 𝑢 = 𝑡[𝑠] ⟺ �̅�(𝑢) = �̅�(𝑡) 
⟹ ℎ(�̅�(𝑢)) = ℎ(�̅�(𝑡)) 
⟺ ℎ ∘ 𝑠̅̅ ̅̅ ̅̅ (𝑢) = ℎ ∘ 𝑠̅̅ ̅̅ ̅̅ (𝑡), por a) 
⟺⊨𝔅 𝑢 = 𝑡[ℎ ∘ 𝑠]. 
 
Si ℎ es uno a uno, la flecha del segundo paso también se puede invertir. Esto es claro por la 
definición uno a uno. 
 
d) Se extiende el argumento inductivo de rutina de la parte b) para incluir el paso del 
cuantificador. Esto es, se debe mostrar que si 𝜑 tiene la propiedad de que para toda 𝑠: 
 
⊨𝔄 𝜑[𝑠] ⟺⊨𝔅 𝜑[ℎ ∘ 𝑠], 
 
entonces ∀𝑥 𝜑 tiene la misma propiedad. En todo caso (como una consecuencia de la hipótesis 
de inducción para 𝜑) se tiene la implicación: 
 
⊨𝔅 ∀𝑥 𝜑[ℎ ∘ 𝑠] ⟹⊨𝔄 ∀𝑥 𝜑[𝑠]. 
 
De manera intuitiva, esto es muy plausible. Si 𝜑 es verdadero para todos los elementos en el 
conjunto más grande |𝔅|, es verdadero con mayor razón para todos en el conjunto más 
pequeño 𝑟𝑎𝑛 ℎ. Los detalles son, para un elemento 𝑎 de |𝔄|, 
 
⊨𝔅 ∀𝑥 𝜑[ℎ ∘ 𝑠] ⟹⊨𝔅 𝜑[(ℎ ∘ 𝑠)(𝑥|ℎ(𝑎))] 
⟺⊨𝔅 𝜑[ℎ ∘ (𝑠(𝑥|𝑎))], pues las funciones son las mismas 
⟺⊨𝔄 𝜑[𝑠(𝑥|𝑎)], por la hipótesis de inducción. 
 
Ahora para el regreso, supóngase que ⊭𝔅 ∀𝑥 𝜑[ℎ ∘ 𝑠], de modo que ⊨𝔅 ¬𝜑[(ℎ ∘ 𝑠)(𝑥|𝑏)] para 
algún elemento 𝑏 de |𝔅|. En este punto es necesaria la implicación siguiente: 
 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 36 
(*) Si para algún 𝑏 de |𝔅|, ⊨𝔅 ¬𝜑[(ℎ ∘ 𝑠)(𝑥|𝑏)], entonces para algún 𝑎 de |𝔄|, ⊨𝔅 ¬𝜑[(ℎ ∘
𝑠)(𝑥|ℎ(𝑎))]. 
 
Pues teniendo (*) se puede seguir: 
 
⊨𝔅 ¬𝜑[(ℎ ∘ 𝑠)(𝑥|ℎ(𝑎))] ⟺⊨𝔅 ¬𝜑[ℎ ∘ (𝑠(𝑥|𝑎))] 
⟺⊨𝔄 ¬𝜑[𝑠(𝑥|𝑎)], por hipótesis de inducción 
⟹⊭𝔄 ∀𝑥 𝜑[𝑠]. 
 
Si ℎ es función de |𝔄| sobre |𝔅|, entonces (*) es inmediato; tomando 𝑎 tal que 𝑏 = ℎ(𝑎). Sin 
embargo, puede haber otras ocasiones afortunadas en que se pueda afirmar (*) incluso si ℎ no 
tiene rango |𝔅|. 
 
 
 
Definición 
Se dice que dos estructuras 𝔄 y 𝔅 son elementalmente equivalentes (se escribe 𝔄 ≡ 𝔅) sii 
para cualquier enunciado 𝜎: 
 
⊨𝔄 𝜎 ⇔⊨𝔅 𝜎. 
 
Respecto con esta definición y el teorema de isomorfismo, se tiene el siguiente corolario. 
 
Corolario 
Las estructuras isomorfas son elementalmente equivalentes, es decir: 
 
𝔄 ≅ 𝔅 ⟹ 𝔄 ≡ 𝔅 
 
De hecho, se tiene más verdad que ésta: las estructuras isomorfas se parecen de cualquier 
manera “estructural”: no sólo satisfacen los mismos enunciados de primer orden sino que 
también satisfacen los mismos enunciados de segundo orden (y de órdenes superiores), es 
decir, son equivalentes en segundo orden y más. 
 
El regreso del corolario no es cierto, pues existen estructuras elementalmente equivalentes 
que no son isomorfas. Por ejemplo, la estructura (ℝ; <𝑅), formada por el conjunto de los 
números reales con su relación de orden usual, es elementalmente equivalente a la estructura 
(ℚ; <𝑄), compuesta por el conjunto de los números racionales con su orden natural. ℚ es un 
conjunto numerable mientras que ℝ no lo es; así que estas estructuras no pueden ser 
isomorfas. 
 
Ejemplo 2.2.8.3. 
De un ejemplo anterior se sabe que (ℙ; <𝑃) ≅ (ℕ; <𝑁). Así que, en particular, (ℙ; <𝑃) ≡
(ℕ; <𝑁) y estas estructuras no se pueden distinguir mediante enunciados de primer orden. 
Lógica matemática 
Unidad 2. Lógica de primer orden o de predicados 
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 
 37 
 
Incluso se tiene que la función identidad es una inmersión isomorfa de (ℙ; <𝑃) en (ℕ; <𝑁). De 
esto se tiene que para una función 𝑠: 𝑉 → ℙ y para una 𝜑 libre de cuantificadores: 
 
⊨(ℙ;<𝑃) 𝜑[𝑠] ⟺⊨(ℕ;<𝑁) 𝜑[𝑠] 
 
Es fácil ver que esta equivalencia