Definir el "lenguaje de primer orden" sin utilizarlo

Question

Me cuesta definir el "lenguaje de primer orden". En principio, un lenguaje de primer orden es cualquier lenguaje producido por una "gramática de primer orden", pero no parece haber ninguna manera de afirmar lo que es una "gramática de primer orden" sin emplear el uso de la lógica de primer orden en algún momento. En particular, no puedo reducir...

si $F$ es un $n$ -símbolo de función primaria y $t_1,\ldots,t_n$ es una lista de $n$ términos, entonces $F(t_1,\ldots,t_n)$ es un término

...y...

si $R$ es un $n$ símbolo de la relación de tipo -ario y $t_1,\ldots,t_n$ es una lista de $n$ términos, entonces $R(t_1,\ldots,t_n)$ es una fórmula

...a las reglas de producción. Esto es un problema porque "es $n$ -ary" es una proposición que debe ser probada, lo que conduce rápidamente a la circularidad. No me siento cómodo pretendiendo que una lista infinitamente larga de gramáticas esté contenida dentro de cualquier medio actualmente disponible (si resulta que se ha desarrollado algún medio para codificar una cantidad infinita de información, Por favor, hágamelo saber). Entonces, ¿qué es un lenguaje de primer orden, y cómo sé que $\mathcal{L}$ es de primer orden sin saber qué es un "número"?

---

Aclaración

Entiendo bastante bien el significado que se pretende dar a "lenguaje de primer orden". Mi problema es que no veo ninguna manera de transmitir este significado de una manera puramente mecánica y finitista. No es posible escribir "lenguajes de primer orden", porque la totalidad de los "lenguajes de primer orden" es infinita; lo mejor que podemos esperar es un conjunto finito de instrucciones para generando subconjuntos finitos arbitrarios de lenguajes de primer orden arbitrarios. En realidad, esto es todo lo que ha hecho cualquier autor.

La razón por la que asumo que estas instrucciones toman la forma de una gramática formal es que así es como se introduce la lógica de primer orden. Al identificar la clase de teorías de primer orden, los autores suelen introducir una gramática formal (a veces en forma de "definiciones inductivas", que no son más que reglas de producción enunciadas en inglés) para describir qué es un lenguaje de primer orden.

Todo el problema se resuelve fácilmente utilizando reglas de reescritura condicional en lugar de una gramática - pero nunca he visto a nadie hacer esto.

---

Como referencia:

Bell y Slomson Modelos y Ultraproductos: Una introducción

Ben-Ari Lógica matemática para la informática

Pudlák Fundamentos lógicos de las matemáticas y la complejidad computacional

Weiss Fundamentos de la teoría de modelos

Wikipedia Lógica de primer orden

Otros libros que hace tiempo que no leo también pasan por el proceso "del lenguaje a la lógica", y los añadiré en cuanto los encuentre.

Answer 1

No sólo se puede definir la sintaxis completa de las lenguas de primer orden en términos de una sola gramática, sino que esta gramática es libre de contexto . En consecuencia, si una cadena dada es o no una fórmula en un lenguaje de primer orden es decidible. La gramática es la siguiente...

$$\begin{align} &\langle formula\rangle&\to&\qquad\neg\langle formula\rangle\\ &&&\qquad\mid(\langle formula\rangle\langle connective\rangle\langle formula\rangle)\\ &&&\qquad\mid\langle quantifier\rangle\langle variable\rangle(\langle formula\rangle)\\ &&&\qquad\mid\langle relation\rangle\langle args\rangle\\ &\langle relation\rangle&\to&\qquad\langle relation\rangle_\text{I}\mid R\\ &\langle args\rangle&\to&\qquad ^\text{I}\langle args\rangle\langle term\rangle\mid\varepsilon\\ &\langle term\rangle&\to&\qquad\langle variable\rangle\mid\langle function\rangle\langle args\rangle\\ &\langle function\rangle&\to&\qquad\langle function\rangle_\text{I}\mid F\\ &\langle variable\rangle&\to&\qquad\langle variable\rangle_\text{I}\mid v\\ &\langle quantifier\rangle&\to&\qquad\exists\mid\forall \end{align}$$

...utilizando $\langle formula\rangle$ como símbolo de inicio, y $^\text{I},_\text{I},(,),\varepsilon,F,R,v,\exists,\forall$ como terminales. Es aceptable excluir las conectivas aquí únicamente porque el conjunto de conectivas lógicas funcionalmente completas es finito . Es es Es posible crear una lista de gramáticas para cada conjunto de conectivas lógicas dentro de un espacio finito, y lo haré si me lo piden.

El lenguaje generado por esta gramática incluye todas las fórmulas de primer orden sintácticamente válidas, por lo que basta para definir la noción de "lenguajes de primer orden". Obsérvese que los símbolos constantes -y, por cierto, las variables proposicionales (algo que no esperaba)- se contabilizan mediante $0$ -arios de funciones y relaciones, respectivamente. La aridad de un símbolo de función o de relación se indica explícitamente mediante los valores del índice superior, mientras que los valores del índice inferior sirven para distinguir los símbolos de función/relación de la misma aridad, por ejemplo $F_\text{II}^\text{III}$ es $\text{II}^\text{th}$ ( $2^\text{nd}$ ) $\text{III}$ Símbolo de función -aria (3-aria).

Las fórmulas resultantes coinciden necesariamente con la aridad de cada símbolo de función/relación con un argumento de la longitud adecuada. Por ejemplo, la fórmula...

$$\exists v(\forall v_\text{I}((R_\text{II}^\text{II}vF^\text{II}v_\text{II}v_\text{IIII}\land\neg R_\text{I}^\text{II}v_\text{I}F_\text{III})))$$

...(" $\exists x.\forall y.R_2(x,F(u,v))\land R_1(y,c)$ , donde $R_1,R_2$ son relaciones binarias, $F$ es una función binaria, y $c$ es una constante" en el lenguaje común) está bien formado, mientras que...

$$(\neg R_\text{I}^\text{III}F_\text{II}v\lor\exists v_\text{II}(R\land R^\text{II}v_\text{II}v))$$

...(" $R_1(c,x)\implies\exists y.\varphi\land R(y,x)$ , donde $R_1$ es un símbolo de relación ternaria, $R$ es un símbolo de relación binaria, $c$ es una constante, y $\varphi$ es una variable proposicional" en lenguaje común) no lo es.

Cabe destacar que la aridad de un símbolo de función/relación se define en términos de la lista de argumentos, en lugar de estar "ligada" a un símbolo de función/relación específico. En realidad, esto es bastante profundo: no podemos definir una gramática en la que la aridad de un símbolo de función/relación aparezca en el lado derecho de una regla de producción independientemente de los argumentos; las producciones de la forma...

$$\begin{align} &\langle formula\rangle&\to&\qquad\langle relation\rangle\langle args\rangle\\ &\langle term\rangle&\to&\qquad\langle function\rangle\langle args\rangle\\ &\langle relation\rangle&\to&\qquad\langle relation\rangle_\text{I}\mid\langle relation\rangle^\text{I}\mid R\\ &\langle function\rangle&\to&\qquad\langle function\rangle_\text{I}\mid\langle function\rangle^\text{I}\mid F\\ &\langle args\rangle&\to&\qquad\langle args\rangle\langle term\rangle\mid\varepsilon \end{align}$$

...donde los no-terminales $\langle function\rangle$ y $\langle relation\rangle$ se sustituyen por símbolos de función/relación de una aridad determinada, dan lugar a fórmulas no válidas. En otras palabras, la "aridad", si debe considerarse parte de la sintaxis, no puede considerarse una propiedad de los símbolos de función/relación en sí mismos.