¿Cómo eliminar los símbolos constantes de una teoría de primer orden?

Question

Esta pregunta se basa en mi anterior pregunta en el que pregunté si los símbolos constantes son necesarios en las teorías de primer orden. En esa pregunta di una idea aproximada sobre cómo deshacerse de estos símbolos, que no estaba completamente pensada. Intentaré arreglar esto ahora y estaría encantado si alguien puede verificar este enfoque.

Digamos que tenemos una teoría de primer orden $T$

• sobre una lengua $L$ con (posiblemente infinitos) símbolos constantes $c_i$ .
• elegimos (posiblemente infinitos) predicados $\varphi_i(x_1,...,x_{n_i})$ para que $\varphi_i(c_{\sigma_i(1)},...,c_{\sigma_i(n_i)})$ constituye un sistema de axiomas de $T$ . El $\sigma(i)$ elegirá los símbolos constantes que están presentes en el $i$ -a axioma y $n_i$ (posiblemente cero) denotará cuántos hay.

Quiero construir una teoría $T'$ sobre una lengua $L'$ que tiene todos los símbolos constantes eliminados. Aún así, $T$ y $T'$ deberían tener exactamente los mismos modelos (en cierto sentido). Lo haré sustituyendo los axiomas $\varphi_i$

Necesitaré algunas anotaciones abreviadas:

• Escribo $\vec x$ para una secuencia de algunas de las variables $x_1,x_2,...$ donde los nombres exactos se derivan del lugar de uso de esta secuencia. Por ejemplo, en $(\forall \vec x)\varphi_i(\vec x)$ la secuencia estará formada por las variables $x_{\sigma_i(1)},...,x_{\sigma_i(n_i)}$ .
• Escribo $\vec x=\vec y$ para la afirmación de que las dos secuencias coinciden elementalmente en las variables que están contenidas en ambas. Si una variable $x_j$ no está en ambas secuencias, entonces $\vec x=\vec y$ no contiene $x_j$ .
• Escribo $\Delta(\vec x)$ para la afirmación de que todas las variables de $\vec x$ son diferentes. Así que $\Delta(\vec x)$ contiene la declaración $x_i\not= x_j$ para cualquier par de variables distintas $x_i,x_j\in\vec x$ conjugados entre sí.

Ahora voy a sustituir el axioma $\varphi_i$ por

$$(A_i)\qquad (\exists \vec x)[\Delta(\vec x)\wedge \varphi_i(\vec x)\quad\wedge\quad(\forall \vec y)\left[\Delta(\vec y)\wedge \varphi_i(\vec y)\rightarrow \vec x=\vec y]\right],$$

y para cualquier par $\varphi_i, \varphi_j$ de los axiomas anteriores introduciré el axioma

$$(A_{ij})\qquad (\forall \vec x \forall \vec y)[\varphi_i(\vec x)\wedge\varphi_j(\vec y)\rightarrow \vec x= \vec y] $$

En el caso especial de que tengamos símbolos constantes en $T$ pero ningún axioma contiene ninguno de ellos, introduciré el axioma $(\exists x)[x=x]$ para asegurar que hay al menos un elemento en el modelo.

En mi opinión, esto refleja todas las propiedades que las constantes aportan inherentemente a la teoría. ¿Es esto correcto? ¿Me da esto una teoría equivalente (en cierto sentido, véase la nota 2)?

---

NOTA:

No creo que debe deshacerse de los símbolos contantes. Mi motivación es puramente académica en el sentido de que quiero conozca si siempre hay una teoría equivalente sin símbolos constantes, como si siempre hay una teoría equivalente sustituyendo los símbolos de función y los símbolos constantes por símbolos de relación.

Como señalaron Giorgio y René en sus respuestas a mi anterior pregunta, hay aplicaciones legítimas y útiles para los símbolos constantes. No lo pongo en duda.

---

NOTA 2:

No estoy seguro de cómo comparar directamente los modelos (todo el "espacio" de) de estas teorías, ya que se definen sobre diferentes lenguajes. Así que el primero es un $L$ -de la estructura, la segunda una $L'$ -estructura. ¿Se hace comparando las categorías de estructuras creadas por estas dos teorías?

Answer 1

No, se necesitan constantes:

Supongamos que $\mathcal{L}=\{R,(c_n)_{n\in\omega}\}$ donde $R$ es una relación binaria y consideremos la siguiente teoría $T=\{(R(c_0,c_n))_{n\in\omega},(c_n\neq c_m)_{n\neq m}\}.$ Afirmo que no hay ninguna teoría $T'$ de $\mathcal{L}^-=\{R\}$ tal que un modelo satisface $T$ si y sólo si su $\mathcal{L}^-$ -reducto satisface $T'$ .

De hecho, suponiendo lo contrario, tal $T'$ existe. Sea $M=(\mathbb{N}, >)$ sean los números naturales con $R$ definido como el orden inverso.

Tenemos que $T\models T'$ es decir, cada modelo de $T$ satisface todas las fórmulas de $T'$ . Para cada fórmula de $\varphi\in T'$ existe un número finito de fórmulas de $T$ Llamémoslo $U_\varphi$ , de tal manera que $U_\varphi\models\varphi$ . Esto es así porque si no fuera así, entonces para cada $U$ un subconjunto finito de $T$ Tendríamos que $U\cup\{\lnot\varphi\}$ tiene un modelo. Esto implica por compacidad que $T\cup\{\lnot\varphi\}$ tiene un modelo, lo que contradice el hecho de que $T\models\varphi$ .

Por último, nótese que cualquier conjunto finito de fórmulas de $T$ se satisface en $M$ . Por lo tanto, para cualquier $\varphi\in T'$ tenemos que $M\models U_\varphi$ . Esto y el hecho de que $U_\varphi\models\varphi$ implica que $M\models\varphi$ . Como esto es cierto para cada $\varphi\in T'$ tenemos que $M\models T'$ .

Por otro lado, $M$ no puede ampliarse a $\mathcal{L}$ para que satisfaga $T$ . Con esto concluye la prueba.

---

En cuanto a su pregunta sobre el tamaño de la lengua. Si el lenguaje sólo contiene un número finito de constantes y un número finito de relaciones, entonces puedes escribir en una sola fórmula exactamente cómo se relacionan las constantes con las relaciones y, por tanto, puedes deshacerte de las constantes.

Por otro lado, si tienes infinitas relaciones entonces puedes hacer algo similar con lo que hice arriba: Toma $\mathcal{L}=\{c_1,c_2,(R_n)_{n\in\omega}\}$ La teoría $T=\{(R_n(c_1,c_2))_{n\in\omega}\}$ y considerar el modelo $M=\{\mathbb{N}, <_n\}$ donde $k<_n\ell$ si y sólo si $n\leq \ell$ y $k<\ell$ . Usando estos puedes mostrar exactamente lo que mostré arriba.

En cuanto a las funciones, esto es algo que en algún momento estuvo presente en la respuesta de Noé, pero parece que ahora se ha eliminado, así que lo añado aquí: Si tienes una constante $c$ y una función $f$ entonces se pueden definir muchos términos cerrados contables en forma de $f(f(c))$ , $f(f(f(c)))$ etc. Entonces puedes escribir la misma teoría que escribí en mi respuesta original utilizando estos términos en lugar de las constantes.

---

Como señala Alex, la idea que subyace a estas pruebas es que se puede hacer que una constante satisfaga infinitas relaciones, pero no hay ninguna frase en la lógica de primer orden que pueda expresar esto: La constante vincula un objeto y puedes describir infinitas propiedades de ese objeto en particular. Esto está estrechamente relacionado con la noción de saturación en la teoría de los modelos.

Finalmente, sí, si tienes una teoría tal que una fórmula $\varphi$ existe tal que $\forall x(\varphi(x)\to(x=c))$ puedes prescindir de $c$ siempre y cuando esta fórmula $\varphi$ no implica $c$ .

Answer 2

Quiero hacer un comentario que creo que aún no se ha articulado claramente en la discusión.

Dejemos que $L$ sea un lenguaje sin símbolos constantes, y sea $L'$ sea $L$ junto con algunos símbolos constantes (finitos o infinitos).

Digamos que tenemos un $L'$ -sentencia $\varphi$ que menciona los símbolos constantes $c_1,\dots,c_n$ y ninguna otra. A continuación, sustituyendo cada símbolo constante $c_i$ con la variable fresca $x_i$ en todos los lugares en los que aparece $\varphi$ , obtenemos un $L$ -fórmula $\widehat{\varphi}(\overline{x})$ . Y el $L'$ -sentencia $\varphi$ equivale a la $L$ -sentencia $\exists \overline{x}\, \widehat{\varphi}(\overline{x})$ en el sentido de que un $L$ -La estructura satisface $\exists \overline{x}\, \widehat{\varphi}(\overline{x})$ si y sólo si es un reducto de un $L'$ -estructura satisfactoria $\varphi$ .

Esto está muy bien para una sola frase, pero hay problemas cuando se intenta hacer esto con varias frases a la vez. Cuando $\varphi$ y $\psi$ tienen algunos símbolos constantes en común, un $L'$ -estructura que satisface tanto $\varphi$ y $\psi$ no es lo mismo que un $L$ -estructura que satisface tanto $\exists\overline{x}\,\widehat{\varphi}(\overline{x})$ y $\exists\overline{x}\,\widehat{\psi}(\overline{x})$ . La razón es que la tupla que atestigua los cuantificadores existenciales en $\exists\overline{x}\,\widehat{\varphi}(\overline{x})$ no es necesario que sea la misma que la tupla que atestigua los cuantificadores existenciales en $\exists\overline{x}\,\widehat{\psi}(\overline{x})$ .

De acuerdo, pero podemos arreglar esto si sólo nos preocupamos por un número finito de sentencias (es decir, una teoría finitamente axiomatizable). Un modelo para la $L'$ -teoría $\{\varphi_1,\dots,\varphi_n\}$ es lo mismo que un modelo para el $L'$ -sentencia $\bigwedge_{i=1}^m \varphi_i$ y esta frase es equivalente (en el sentido anterior) a la $L$ -sentencia $\exists\overline{x}\,\bigwedge_{i=1}^m \widehat{\varphi_i}(\overline{x})$ . Lo que hicimos aquí fue asegurar que cada instancia de una cada constante fuera manejada por el mismo cuantificador existencial.

Pero la mayoría de las teorías que nos interesan son infinitas. Y no se puede utilizar el truco anterior para una teoría infinita (al menos no en la lógica de primer orden), porque no se puede formar la conjunción infinita. La situación es aún peor cuando se tienen infinitos símbolos constantes, porque no se puede formar un bloque infinito de cuantificadores existenciales.

Answer 3

No, no hay manera de sólo deshacerse de las constantes.

Considere el lenguaje $L$ compuesto por un número incontable de símbolos constantes $c_i$ y sin símbolos no constantes. Sea $T$ sea el conjunto de axiomas que afirman $c_i\not=c_j$ siempre que $i\not=j$ . Entonces cada modelo de $T$ es incontable.

Sin embargo, por Lowenheim-Skolem no hay ninguna teoría en el lenguaje vacío tal que todo modelo de esa teoría sea incontable. Así que para obtener una teoría equivalente "libre de constantes", tendríamos que añadir algo al lenguaje, además de eliminar los símbolos constantes.

---

Otra construcción, esta vez en una lengua contable, estrechamente relacionada con la respuesta de Apostolos, pero no exactamente igual:

Toma la lengua $\{c_i: i\in\mathbb{N}\}\cup \{R\}$ donde $R$ es un símbolo de relación binaria. Sea $T$ sea el conjunto de axiomas que afirman que $R$ es libre de ciclos y que el $c_i$ forman un conjunto estrictamente $R$ -secuencia descendente: $c_0Rc_1Rc_2...$

Ahora para cualquier teoría $T'$ en la lengua $\{R\}$ que contiene los axiomas que afirman que no hay ciclos podemos construir un modelo de $T'$ sin infinito $R$ -secuencias descendentes (este es un buen ejercicio). Este modelo no puede ampliarse a un modelo de $T$ .

Este ejemplo es realmente muy parecido al de Apostolos; lo incluyo, sin embargo, porque evitar la infundamentación es una técnica útil en otras partes de la lógica (como lo es evitar la infundamentación, pero eso es mucho más fácil a través de la compacidad).