Una misma frase puede ser verdadera en un universo y falsa en otro. Antes de hablar de teorías vamos a elegir objetos, decidir qué símbolos podemos usar y comprobar fórmulas con valores concretos. Después veremos qué conjuntos puede describir una fórmula y cómo una simetría puede impedir que distinga un punto. Los resultados generales llegarán después de esos casos pequeños.
Si necesitas repasar:
1. Primero elegimos vocabulario; después le damos una interpretación
Un lenguaje es una lista de símbolos permitidos. En el lenguaje puro del orden usamos la relación <; la igualdad y los conectivos son parte de la lógica. En el lenguaje de cuerpos podemos usar constantes 0 y 1 y operaciones +, − y ·. Cada símbolo tiene una aridad: cuántas entradas recibe.
Una estructura da un universo no vacío e interpreta esos símbolos. Una operación binaria devuelve un elemento por cada pareja; una relación binaria dice si una pareja cumple una condición. El signo escrito no determina por sí solo sobre qué objetos estamos trabajando.
Una operación devuelve un objeto; una relación tiene valor de verdad
Trabajamos en los racionales con + y <.
Operación
Con entradas 2 y 3, la suma devuelve el racional 5. El resultado sigue dentro del universo.
Relación
Con las mismas entradas, 2<3 es verdadera.No devuelve otro racional como resultado de una suma.
Vocabulario
En el lenguaje que solo incluye < no podemos escribir x+1 como término. Desde fuera podemos hablar de suma para describir una función, pero eso no añade + al lenguaje.
El universo y el tipo de símbolo se declaran antes de evaluar.
No se interpreta una relación como si fuera una función que entrega un elemento.
El mismo vocabulario puede interpretarse con otra aritmética
Comparamos Q con el cuerpo de cinco elementos F₅.
Racionales
En Q, 3+4=7 y todos esos números representan racionales distintos.
Cinco elementos
En F₅ usamos las clases 0,1,2,3,4 y sumamos módulo cinco.
Allí 3+4=2.Lectura
La expresión 1+1+1+1+1=0 es falsa en Q y verdadera en F₅.No cambió el alfabeto; cambiaron la estructura y la interpretación.
Una oración se evalúa en una estructura concreta.
F₅ es un cuerpo; no se generaliza esa afirmación a cualquier módulo compuesto.
2. Una variable libre es una entrada; un cuantificador busca dentro del universo
Un término designa un elemento cuando damos valores a sus variables. Una fórmula afirma una condición.
La fórmula recibe un valor de x y pregunta si hay un testigo y permitido.
Una oración no tiene variables libres. El alcance de cada cuantificador se fija con paréntesis. No basta contar letras: una misma letra puede tener apariciones libres y ligadas en lugares distintos.
Buscar un elemento mayor en un universo de tres puntos
M={0,1,2} con el orden habitual; φ(x) es ∃y(x<y).
Entrada cero
Con x=0 podemos elegir y=1; también serviría 2.Basta un testigo para afirmar que φ(0) es verdadera.
Entrada uno
Con x=1 sirve y=2.No se exige que el testigo sea el mismo que para cero.
Entrada dos
No hay un elemento de M mayor que dos.
Usar y=3 estaría fuera del universo.Las soluciones son exactamente {0,1}.
La fórmula tiene una variable libre y selecciona un subconjunto de M.
En Q la misma fórmula es verdadera para todo x, porque el racional x+1 es un testigo.
Cambiar el orden de cuantificadores cambia la obligación
En (Q,<), comparar ∀x∃y(x<y) con ∃y∀x(x<y).
Para cada x
La primera permite elegir y después de conocer x. La regla externa y=x+1 proporciona un testigo racional para cada entrada.
Un único y
La segunda exige un racional y mayor que todos los racionales. Ese mismo y también sería un valor permitido de x, y daría y<y, que es falso.
Resultado
La primera oración es verdadera y la segunda falsa. El orden determina si el testigo puede depender de x.
No se intercambian ∀ y ∃ como si fueran dos sumandos.
En el universo finito anterior, la primera ya falla en su elemento máximo.
3. Satisfacer una fórmula significa evaluar cada parte con sus entradas
M ⊨ φ(a) se lee: la fórmula φ es verdadera en M al sustituir sus variables libres por la tupla a. Primero evaluamos términos, después igualdades o relaciones y luego conectivos y cuantificadores. Los testigos de un existencial deben pertenecer a M.
La definición recursiva de satisfacción explica qué significa verdad. No afirma que exista un algoritmo que resuelva toda pregunta de verdad en cualquier estructura infinita.
Evaluar una condición compuesta sin saltarse el testigo
En M={0,1,2}, ψ(x) es ∃y(x<y ∧ y<2). El 2 se ha nombrado como constante.
Con x=0
Probar y=1 da 0<1 y 1<2.Ambas partes son verdaderas, así que ψ(0) es verdadera.
Con x=1
El único candidato mayor es dos, pero 2<2 es falso. La conjunción falla y no hay otro testigo.
Con x=2
Ningún candidato es mayor que dos. La condición ya falla en su primera parte. El conjunto de soluciones es {0}.
Cada conectivo combina condiciones ya evaluadas.
No basta que exista un y para cada desigualdad por separado: la conjunción exige el mismo y.
Una ecuación puede necesitar un testigo que el universo no tiene
Oración ∃x(x·x=1+1), en Q y en R.
Reales
En R existe √2 y su cuadrado es dos; la oración es verdadera.
Racionales
Si un racional m/n reducido tuviera cuadrado dos, m²=2n² haría m par. Al escribir m=2k se obtiene n²=2k², por lo que n también sería par.
Contradicción
m y n no podrían ser coprimos. No hay testigo racional y la oración es falsa en Q. Aproximar √2 con decimales racionales no da una igualdad exacta.
El cuantificador no puede pedir prestado un objeto de una estructura mayor.
La igualdad usa 1+1, una expresión disponible en el lenguaje de cuerpos.
4. Definir un conjunto es dar una fórmula y todos sus parámetros
Un conjunto D⊆Mⁿ es definible con parámetros si existe una fórmula φ(x, b) cuyas soluciones son exactamente D. La tupla x recorre candidatos y b queda fija. Una fórmula es finita y usa finitos parámetros, aunque M sea infinito.
Sin parámetros no añadimos elementos del universo al vocabulario. Las constantes ya incluidas en el lenguaje sí están permitidas. Un cuantificador existencial proyecta un conjunto de parejas; los conectivos permiten intersecciones, uniones y complementos.
Un intervalo racional tiene muchos más elementos que una lista de enteros
En (Q,<), con parámetros 1 y 4, usar 1<x ∧ x<4.
Comprobar
2 y 3 cumplen las dos condiciones. También 3/2 y 7/2, que no son enteros.
Fronteras
1 y 4 quedan fuera por las desigualdades estrictas. 5 falla en la segunda condición.
Conjunto exacto
La fórmula define todos los racionales del intervalo abierto (1,4), no solamente {2,3}. Los parámetros determinan sus extremos.
Una fórmula describe todos los candidatos que cumplen la condición.
Cambiar el universo a Z cambia el conjunto de soluciones, incluso con extremos iguales.
Proyectar una ecuación conserva el universo del testigo
En el lenguaje de cuerpos, φ(y) es ∃x(y=x·x).
En R
Todo cuadrado es no negativo y todo real no negativo tiene una raíz real. Las soluciones son [0,∞).
En Q
Las soluciones son los cuadrados racionales. 9/4 sí pertenece por el testigo 3/2; dos no pertenece, aunque sea positivo.
Parámetros
No se usaron parámetros añadidos: la operación multiplicación pertenece al lenguaje. La descripción por una proyección no obliga a que el resultado sea igual en Q y R.
El mismo patrón sintáctico puede definir conjuntos distintos.
La no negatividad en esta explicación se describe desde fuera; no se ha añadido < al lenguaje de cuerpos.
5. Un automorfismo conserva fórmulas y también debe conservar los parámetros
Un automorfismo es una biyección del universo que respeta constantes, operaciones y relaciones de la estructura. Conserva igualdades y fórmulas atómicas; los conectivos conservan esa equivalencia. Para un existencial, la biyección transporta un testigo y su inversa permite volver.
Por inducción sobre la fórmula, las soluciones definibles sin parámetros son invariantes bajo todos los automorfismos. Con parámetros b solo podemos usar los que fijan b. Si una simetría mueve un punto del conjunto fuera de él, ya tenemos una prueba de no definibilidad en ese alcance.
Trasladar racionales respeta el orden sin que + esté en el lenguaje
En (Q,<), t(x)=x+3.
Biyección
La inversa es x↦x−3 y ambas envían racionales a racionales.
Relación
a<b equivale a a+3<b+3.Por eso t es un automorfismo del orden.
Fórmulas
Una propiedad sin parámetros que valga para cero también vale para tres. Si la fórmula usa el parámetro cero, esta traslación no lo fija y ya no sirve para conservar esa misma propiedad.
Las simetrías dependen del lenguaje elegido.
En el lenguaje de cuerpos, t no preserva la constante cero ni la multiplicación y no es un automorfismo de cuerpo.
Transportar un testigo explica el paso existencial
Supongamos M ⊨ ∃y R(a, y) y un automorfismo h.
Testigo inicial
Existe b de M tal que R(a, b) es verdadera.
Aplicar h
Como h conserva la relación, R(h(a), h(b)) es verdadera; h(b) sigue dentro de M.
Ambos sentidos
Así existe testigo para h(a). Aplicar h⁻¹ demuestra la implicación contraria. Si hay parámetros, también se transportan, salvo que se haya exigido fijarlos.
La conservación de verdad no es solo un parecido del dibujo.
La sobreyectividad es necesaria para recuperar cualquier testigo del segundo lado.
6. Las simetrías prueban límites concretos de lo definible
En (Q,<), para cualesquiera racionales a y b la traslación x↦x+(b−a) lleva a a b y conserva el orden. Por tanto ningún punto puede distinguirse de todos los demás mediante una fórmula sin parámetros con una variable libre.
La invariancia es una condición necesaria; no es una equivalencia general. Hace falta estudiar la estructura y el lenguaje antes de concluir que todo conjunto invariante tiene una definición.
Los únicos conjuntos unarios sin parámetros del orden racional
Sea D⊆Q definible sin parámetros en (Q,<).
Si está vacío
El conjunto vacío sí es definible: x≠x no tiene soluciones.Si tiene a
Para cualquier b∈Q existe la traslación que lleva a a b. La invariancia obliga a que b también pertenezca a D.
Conclusión
Si no es vacío, D=Q.Q se define por x=x.En particular {2} no es definible sin parámetros, pero sí con el parámetro dos mediante x=2.
Solo hay dos posibilidades en este caso concreto: vacío o todo Q.
No se generaliza esta conclusión a conjuntos de parejas; x<y ya define un subconjunto propio de Q².
Invariante no implica siempre definible
En el cuerpo Q con 0,1,+,−,·, todo automorfismo es la identidad.
Fijar racionales
Debe fijar uno, sus sumas enteras y las inversas multiplicativas no nulas. Así fija cada m/n.
Contar definiciones
Hay solo una cantidad numerable de fórmulas finitas en este lenguaje numerable; incluso permitiendo finitos parámetros racionales siguen siendo numerables.
Comparar conjuntos
Q tiene una cantidad no numerable de subconjuntos. Por tanto algunos no son definibles, aunque todos sean invariantes bajo la identidad.
El criterio de simetrías no es suficiente en estructuras arbitrarias.
Este argumento demuestra existencia de conjuntos no definibles; no pretende haber exhibido una fórmula que los defina.
7. Una teoría reúne oraciones; sus modelos pueden ser diferentes
Una teoría T es un conjunto de oraciones. M es modelo de T si satisface cada una. Th(M) contiene todas las oraciones verdaderas en M. Dos estructuras son elementalmente equivalentes cuando tienen la misma teoría completa.
Un isomorfismo sí preserva toda la estructura y por ello toda oración, pero la equivalencia elemental no obliga en general a un isomorfismo. Tampoco una lista de axiomas tiene por qué decidir cada oración de su lenguaje.
Una oración separa el orden entero del orden racional
Comparar ∀x∀y[x<y ⇒ ∃z(x<z ∧ z<y)].
Racionales
Si x<y, el punto medio (x+y)/2 es racional y queda estrictamente entre ambos.
Enteros
Para x=0 e y=1 no existe un entero intermedio.Ese par basta para que falle la oración universal.
Separación
(Z,<) y (Q,<) no son elementalmente equivalentes.No hace falta probar todas las oraciones: una discrepancia es suficiente.
La densidad es una propiedad expresable en primer orden.
Los puntos medios se usan para justificar verdad en Q; + no forma parte de la oración de orden.
Mismas oraciones no significa mismos tamaños
Los órdenes (Q,<) y (R,<) son densos, sin extremos.
Resultado usado
La teoría de los órdenes lineales densos sin extremos es completa. En consecuencia ambas estructuras satisfacen las mismas oraciones del lenguaje puro del orden.
Tamaños
Q es numerable y R no. Una biyección entre ambos no existe, así que tampoco un isomorfismo.
Alcance
Se enuncia aquí la completitud de esa teoría como teorema. No se deduce solo de comprobar unas cuantas fórmulas ni se aplica automáticamente al añadir la multiplicación.
La equivalencia elemental puede coexistir con la ausencia de isomorfismo.
Nombrar otra operación cambia el lenguaje y puede permitir nuevas oraciones separadoras.
8. Compactitud convierte compatibilidad finita en existencia de un modelo
Compactitud afirma que una teoría de primer orden tiene modelo si cada subconjunto finito de sus oraciones tiene modelo. Hay que comprobar todos los subconjuntos finitos, no solo algunos ejemplos. Es un teorema de existencia; no promete una construcción efectiva del modelo.
Una teoría puede contener infinitas oraciones, pero cada oración sigue siendo finita. El modelo que satisface todas puede tener propiedades que ninguno de los modelos pequeños elegidos para las comprobaciones finitas tenía.
Obligar a que haya tantos elementos como cualquier número finito
T contiene, para cada n≥1, la oración que exige al menos n elementos distintos.
Parte finita
Una colección finita de esas oraciones solo exige tamaños hasta un máximo N. Un conjunto con N elementos la satisface.
Aplicar compactitud
Como funciona para cualquier parte finita, existe un modelo de toda T.
Tamaño final
Ese modelo no puede ser finito: si tuviera m elementos, fallaría la oración que exige m+1. La conclusión es un universo infinito.
Modelos finitos para las partes no obligan a que el modelo completo sea finito.
No se ha supuesto un único tamaño N que valga para todas las oraciones.
Un elemento mayor que todos los numerales estándar
Ampliar Th(N) en su lenguaje aritmético con una constante c y las oraciones c>n para cada numeral estándar n.
Comprobar finitos
En una parte finita solo aparecen finitas cotas. N interpreta c como un natural mayor que todas y satisface también las oraciones de Th(N) incluidas.
Existencia
Compactitud da un modelo que satisface Th(N) y todas esas desigualdades.
Interpretación
Su c no coincide con ningún numeral estándar. No es un natural extra de la N habitual: es un elemento de otro modelo de la misma teoría de primer orden.
El universo del nuevo modelo no se identifica sin más con los naturales habituales.
Este argumento no demuestra que exista en N un natural mayor que todos los naturales.
9. Eliminar cuantificadores requiere una teoría y unas hipótesis
Una teoría elimina cuantificadores si toda fórmula equivale, en todos sus modelos, a una fórmula sin cuantificadores con las mismas variables libres. El lenguaje elegido forma parte del enunciado. Simplificar una fórmula aislada no prueba eliminación general.
La ventaja es sustituir una búsqueda de testigos por una condición explícita sobre las entradas. La equivalencia necesita las hipótesis de la teoría; fuera de ella puede fallar.
Densidad permite sustituir una búsqueda por una desigualdad
En órdenes lineales densos, φ(a, b)=∃y(a<y ∧ y<b).
Necesidad
Si existe y entre a y b, la transitividad del orden da a<b.Suficiencia
Si a<b, la densidad garantiza precisamente un elemento intermedio y.Equivalencia
Por tanto φ(a, b) equivale a a<b en esta teoría.En Z, a=0 y b=1 cumplen a<b pero no permiten un testigo, así que allí la equivalencia falla.
Una fórmula con ∃ se reemplaza por una condición sin ∃ bajo hipótesis explícitas.
No se ha probado con este ejemplo que toda teoría elimine cuantificadores.
No tener extremo superior también elimina una búsqueda concreta
En órdenes lineales sin máximo, ψ(x)=∃y(x<y).
Hipótesis
Sin máximo significa que cada elemento tiene alguno mayor, no que exista un mayor común para todos.
Fórmula equivalente
Para cada x la búsqueda tiene éxito. ψ(x) equivale a x=x, una fórmula verdadera sin cuantificador.
Frontera
En {0,1,2} el máximo dos hace falsa ψ(2). Se conserva la hipótesis; no se transporta la simplificación a ese universo finito.
La teoría aporta la existencia que permite borrar el cuantificador.
Los órdenes densos sin extremos satisfacen ambas hipótesis de estos ejemplos.
10. Una lista infinita de condiciones puede ser coherente y no tener solución dentro
Un tipo parcial es una colección de fórmulas en las mismas variables, con parámetros permitidos, coherente con la teoría considerada. No es necesariamente una única fórmula. Realizarlo significa que una misma tupla satisface todas sus condiciones.
La saturación estudia cuándo una estructura realiza tipos de tamaños y parámetros determinados. No basta satisfacer cada condición en algún punto distinto: se pide un punto común. Aquí veremos esa diferencia sin suponer resultados de clasificación.
Cada parte finita tiene solución racional; la lista entera no
En Q, usar parámetros 1,2,3,… y las condiciones x>n para cada natural n.
Finitas cotas
Para cualquier lista finita de ellas basta elegir un racional mayor que la cota máxima.
Todas juntas
Ningún racional supera todos los naturales. Dado un racional, existe un natural mayor, que produce una condición incumplida.
Qué falta
La compatibilidad finita no produce un testigo dentro de Q. Compactitud puede producirlo en una extensión elemental al incorporar las condiciones y el diagrama elemental de Q.
Realizar un tipo dentro de la estructura es una exigencia adicional.
No se confunde este tipo parcial con una fórmula finita que contenga infinitas conjunciones.
Un mismo testigo debe superar simultáneamente todas las pruebas
En M={0,1,2}, comparar las condiciones x≠0, x≠1 y x≠2.
Por separado
Cada una tiene soluciones. Por ejemplo uno cumple la primera, dos la segunda y cero la tercera.
Por pares
Cualquier pareja también tiene solución: se toma el único elemento no excluido por esa pareja.
Las tres
Juntas excluyen todo M. Esta colección ni siquiera es finitamente satisfacible en M, porque ella misma es finita y no tiene solución.
Comprobar condiciones aisladas es más débil que comprobar todas las partes finitas.
En el ejemplo racional sí funciona cualquier parte finita, y esa es la diferencia decisiva.
Ahora lo resolvemos de principio a fin.
EJEMPLO RESUELTO 1
Intervalo con parámetro
En (Q,<), define los racionales mayores que 2.
Universo
La variable recorre racionales en la estructura de orden (Q,<).Parámetro
El dos se permite como parámetro fijo; no se supone una constante nombrada en el lenguaje puro.
Condición
Usar 2<x, o equivalentemente x>2.Conjunto
D={a∈Q:2<a} incluye exactamente los racionales mayores que dos.
Frontera
Dos no pertenece porque 2<2 es falso.5/2 sí, porque 2<5/2.Alcance
Sin permitir ese parámetro, el conjunto no sería definible en el orden racional: una traslación puede mover puntos a través de esa frontera.
D={a∈Q:a>2}.
2 no pertenece; 5/2 sí pertenece.
EJEMPLO RESUELTO 2
Un punto distinguido
En el lenguaje de cuerpos, define {0} sin parámetros.
Lenguaje
El lenguaje de cuerpos ya incluye una constante cero.
Fórmula
Elegir φ(x): x=0; no se añade ningún parámetro externo al lenguaje.
Testigo
El elemento que interpreta cero satisface la igualdad consigo mismo.
Exclusión
Si a es otro elemento, a=0 es falso por ser distintos.
Conjunto
Las soluciones son exactamente {0}.
Contraste
En el lenguaje puro del orden no hay una constante cero nombrada. La definibilidad sin parámetros cambia al cambiar el lenguaje.
La fórmula x=0 define {0}.
En Q solo 0 satisface la fórmula.
Los símbolos que hemos usado
- L
- Lenguaje: colección de símbolos de relación, función y constante con sus aridades.
- M
- Estructura para L; también se usa su letra para el universo, si no hay confusión.
- M ⊨ φ(a)
- La fórmula φ es verdadera en M con la tupla a asignada a sus variables libres.
- b
- Tupla finita de parámetros tomados del universo de M.
- Definible
- Conjunto de soluciones de una fórmula, en un lenguaje y una estructura fijados.
- Aut(M)
- Grupo de biyecciones del universo que conservan todas las interpretaciones del lenguaje.
- Th(M)
- Conjunto de oraciones del lenguaje verdaderas en M.
Ahora te toca a ti.
Tienes cinco ejercicios. Inténtalos; las pistas te ayudan si te atascas.
Practicar este tema →