1.4: Términos y fórmulas

Supongamos que ese\(\mathcal{L}\) es el lenguaje\(\{ 0, +, < \}\), y vamos a utilizar\(\mathcal{L}\) para discutir porciones de aritmética. Si tuviéramos que anotar la cadena de símbolos de\(\mathcal{L}\),

\[\left( v_1 + 0 \right) < v_1,\]

y la cadena

\[v_{17} ) ( \forall + + ( ( ( 0,\]

probablemente estarías de acuerdo en que la primera cadena transmitía algún significado, incluso si ese significado fuera incorrecto, mientras que la segunda cadena no tenía sentido. Es nuestro objetivo en esta sección definir cuidadosamente qué cadenas de símbolos\(\mathcal{L}\) usaremos. En otras palabras, seleccionaremos las cadenas que tendrán significado.

Ahora bien, el punto de tener un lenguaje es poder hacer declaraciones sobre ciertos tipos de sistemas matemáticos. Así, vamos a querer que las declaraciones en nuestro lenguaje tengan la capacidad de referirse a objetos en las estructuras matemáticas bajo consideración. Entonces necesitaremos algunas de las cadenas en nuestro idioma para referirnos a esos objetos. Esas cadenas se llaman los términos de\(\mathcal{L}\).

Definición 1.3.1. Si\(\mathcal{L}\) es un lenguaje, un término de\(\mathcal{L}\) es una cadena finita no vacía\(t\) de símbolos de\(\mathcal{L}\) tal manera que:

1. \(t\)es una variable, o
2. \(t\)es un símbolo constante, o
3. \(t : \equiv f t_1 t_2 \ldots t_n\), donde\(f\) es un símbolo de función\(n\) -aria de\(\mathcal{L}\) y cada uno de los\(t_i\) es un término de\(\mathcal{L}\).

Hay que señalar un par de cosas sobre esta definición. Primero, está el símbolo\(: \equiv\) en la cláusula tercera. El símbolo\(: \equiv\) no forma parte de la lengua\(\mathcal{L}\). Más bien es un símbolo metalingüístico que significa que las cadenas de\(\mathcal{L}\) -símbolos en cada lado del\(: \equiv\) son idénticas. Probablemente la mejor manera natural de leer la cláusula 3 sería decir que "\(t\)es\(f t_1 t_2 \ldots t_n\)”.

Lo otro que hay que notar sobre la Definición 1.3.1 es que esta es una definición por recursión, ya que en la tercera cláusula de la definición,\(t\) es un charrán si contiene subcadenas que son términos. Dado que las subcadenas de\(t\) son más cortas (contienen menos símbolos) que\(t\), y como ninguno de los símbolos de\(\mathcal{L}\) están compuestos por otros símbolos de\(\mathcal{L}\), esto no causa problemas.

Ejemplo 1.3.2. \(\mathcal{L}\)Sea el lenguaje\(\{ \bar{0}, \bar{1}, \bar{2}, \ldots, +, \cdot\}\), con un símbolo constante por cada número natural y dos símbolos de función binarios. Estos son algunos de los términos de\(\mathcal{L}\):\(\bar{714}\),\(+ \bar{3} \bar{2}\),\(\cdot + \bar{3} \bar{2} \bar{4}\). Observe que no\(\bar{1} \bar{2} \bar{3}\) es un término de\(\mathcal{L}\), sino más bien es una secuencia de tres términos seguidos.

Chaff:El término\(+ \bar{3} \bar{2}\) parece bastante molesto en este punto, pero usaremos este tipo de notación (llamada notación polaca) para las funciones en lugar de la notación infija a la\(\left( \bar{3} + \bar{2} \right)\) que estás acostumbrado. En realidad no estamos siendo raros aquí: Ciertamente has visto algunas funciones escritas en notación polaca:\(\sin \left( x \right)\) y me\(f \left( x, y, z \right)\) vienen a la mente. Simplemente estamos siendo consistentes en tratar además de la misma manera. Lo que lo hace difícil es que es difícil recordar que la adición realmente es solo otra función de dos variables. Pero estamos seguros de que al final de este libro, estarás muy cómodo con esa idea y con la notación que estamos usando.

Probablemente valga la pena enfatizar un par de puntos, solo esta vez. Observe que en la aplicación de los símbolos de función, no hay paréntesis ni comas. También observe que todas nuestras funciones están escritas con el operador a la izquierda. Entonces en vez de\(\bar{3} + \bar{2}\), escribimos\(+ \bar{3} \bar{2}\). El motivo de esto es por la consistencia y para asegurarnos de que podamos analizar nuestras expresiones.

Demos un ejemplo. Supongamos que, en algún idioma u otro, escribimos la cadena de símbolos\(\heartsuit \yen \uparrow \diamondsuit \# \# \int\). Supongamos que dos de nuestros compañeros, Humphrey e Ingrid, estaban esperando en el pasillo mientras escribíamos la cuerda. Si Humphrey entrara a la sala y anunciara que nuestra cadena era un símbolo de función de 3 arios seguido de tres términos, mientras que Ingrid proclamaba que la cadena era realmente un símbolo de relación 4-aria seguido de dos términos, esto sería bastante confuso. ¡Sería realmente confuso si ambos fueran correctos! Así que tenemos que asegurarnos de que las cadenas que escribimos puedan ser interpretadas de una sola manera. Este inmueble, denominado legibilidad única, se aborda en el Ejercicio 7 de la Sección 1.4.

Chafia: La legibilidad única es una de esas cosas que, en opinión de los autores, es importante conocer, interesante de probar y aburrida de leer. Así la prueba se coloca en (no nos referimos a “relegados a”) los ejercicios.

Supongamos que miramos más cuidadosamente el término\(\cdot + \bar{3} \bar{2} \bar{4}\). Supongamos por ahora que los símbolos en este término se supone que deben interpretarse de la manera habitual, de modo que eso\(\cdot\) significa multiplicar,\(+\) significa sumar, y\(\bar{3}\) significa tres. Entonces si agregamos algunos paréntesis al término para aclarar su significado, obtenemos

\[\cdot \left( + \bar{3} \bar{2} \right) \bar{4},\]

que debería tener el mismo significado que\(\cdot \bar{5} \bar{4}\), que es\(\bar{20}\), tal como sospechabas.

Tenga la seguridad de que continuaremos usando la notación infija, comas y paréntesis como parecen justificados para aumentar la legibilidad (por los humanos) de este texto. Así\(f t_1 t_2 \ldots t_n\) se escribirá\(f \left( t_1, t_2, \ldots, t_n \right)\) y se\(+ \bar{3} \bar{2}\) escribirá\(\bar{3} + \bar{2}\), entendiendo que esta es taquigrafía y que nuestra versión oficial es la que se da en la Definición 1.3.1.

Los términos de\(\mathcal{L}\) jugar el papel de los sustantivos de la lengua. Para hacer declaraciones matemáticas significativas sobre alguna estructura matemática, vamos a querer ser capaces de hacer aseveraciones sobre los objetos de la estructura. Estas aseveraciones serán las fórmulas de\(\mathcal{L}\).

Definición 1.3.3. Si\(\mathcal{L}\) es un lenguaje de primer orden, una fórmula de\(\mathcal{L}\) es una cadena finita no vacía\(\phi\) de símbolos de\(\mathcal{L}\) tal manera que:

1. \(\phi : \equiv = t_1 t_2\), donde\(t_1\) y\(t_2\) son términos de\(\mathcal{L}\), o
2. \(\phi : \equiv R t_1 t_2 \ldots t_n\), donde\(R\) es un símbolo de relación\(n\) -aria de\(\mathcal{L}\) y\(t_1, t_2, \ldots, t_n\) son todos términos de\(\mathcal{L}\), o
3. \(\phi : \equiv \left( \neg \alpha \right)\), donde\(\alpha\) es una fórmula de\(\mathcal{L}\), o
4. \(\phi : \equiv \left( \alpha \lor \beta \right)\), donde\(\alpha\) y\(\beta\) son fórmulas de\(\mathcal{L}\), o
5. \(\phi : \equiv \left( \forall v \right) \left( \alpha \right)\), donde\(v\) es una variable y\(\alpha\) es una fórmula de\(\mathcal{L}\).

Si una fórmula\(\psi\) contiene la subfórmula\(\left( \forall v \right) \left( \alpha \right)\) [es decir, que la cadena de símbolos que constituyen la fórmula\(\left( \forall v \right) \left( \alpha \right)\) es una subcadena de la cadena de símbolos que componen\(\psi\)], diremos que el alcance del cuantificador\(\forall\) es\(\alpha\). Cualquier símbolo en se\(\alpha\) dirá que se encuentra dentro del alcance del cuantificador\(\forall\). Observe que una fórmula\(\psi\) puede tener varias ocurrencias diferentes del símbolo\(\forall\), y cada ocurrencia del cuantificador tendrá su propio alcance. También observe que un cuantificador puede estar dentro del alcance de otro.

Las fórmulas atómicas de\(\mathcal{L}\) son aquellas fórmulas que satisfacen la cláusula (1) o (2) de la Definición 1.3.3.

Sin duda te has dado cuenta de que no hay paréntesis ni comas en las fórmulas atómicas, y probablemente hayas decidido que seguiremos usando tanto comas como notación infija como parece apropiado. Tienes razón en ambos aspectos. Entonces, en lugar de escribir la versión oficial

\[< SSSSS0SS0\]

en un lenguaje que contiene símbolo constante 0, símbolo de función unaria y símbolo\(S\) de relación binaria <, escribiremos

\[SSSSS0 < SS0\]

o (después de algunas definiciones preliminares)

\[\bar{5} < \bar{2}\]

También observe que estamos usando notación de infijo para el conectivo lógico binario\(\lor\). Esperamos que esto te haga la vida algo más fácil.

Se le pedirá en el Ejercicio 8 de la Sección 1.4 que demuestre que la legibilidad única se mantiene tanto para fórmulas como para términos. Nosotros, en nuestra exposición, usaremos paréntesis de diferentes tamaños, diferentes formas de delimitadores, y omitiremos paréntesis para mejorar la legibilidad sin (esperamos) introducir confusión de su parte.

¡Observe que un término no es una fórmula! Si los términos son los sustantivos de la lengua, las fórmulas serán las declaraciones. Las declaraciones pueden ser verdaderas o falsas. Los sustantivos no pueden. Se puede evitar mucha confusión si tienes en mente este simple dictum.

Por ejemplo, supongamos que está mirando una cadena de símbolos y observa que la cadena no contiene ni el símbolo = ni ningún otro símbolo de relación del idioma. Tal cadena no puede ser una fórmula, ya que no hace ninguna afirmación que pueda ser verdadera o falsa. La cadena puede ser un término, puede ser una tontería, pero no puede ser una fórmula.

Chaff:Esperamos que se haya dado cuenta de que aquí estamos tratando sólo con la sintaxis de nuestro lenguaje. No hemos mencionado que el símbolo se\(\neg\) utilizará para la negación, o que\(\lor\) significará “o”, o incluso eso\(\forall\) significa “para cada”. No te preocupes, van a significar lo que crees que deberían significar. De igual manera, no se preocupe por el hecho de que la definición de una fórmula dejó fuera símbolos para conjunciones, implicaciones y bicondicionales. Llegaremos a ellos a tiempo.

Ejercicios

1. Supongamos que el lenguaje\(\mathcal{L}\) consiste en dos símbolos constantes,\(\diamondsuit\) y\(\heartsuit\), un símbolo de relación unaria\(\yen\), un símbolo\(\flat\) de función binaria y un símbolo de función 3-aria\(\sharp\). Anote al menos tres términos distintos del idioma\(\mathcal{L}\). Escribe un par de no términos que parezcan que podrían ser términos y explicar por qué no son términos. Escribe un par de fórmulas y un par de no fórmulas que parezcan que deberían ser fórmulas.
2. El hecho de que escribamos todas nuestras operaciones a la izquierda es importante para una legibilidad única. Supongamos, por ejemplo, que escribimos nuestras operaciones binarias en el medio (y no permitimos el uso de paréntesis). Si nuestro lenguaje incluyera el símbolo de función binaria\(\#\), entonces el término
   \[u \# v \# w\]
   podría interpretarse de dos maneras. Esto puede marcar la diferencia: Supongamos que la operación asociada al símbolo de función\(\#\) es “restar”. Encuentra tres números reales\(u\),\(v\), y\(w\) tal que las dos interpretaciones diferentes de\(u \# v \# w\) conducen a diferentes respuestas. Cualquier función binaria no asociativa dará otro contraejemplo a una legibilidad única. ¿Se te ocurren tres funciones de este tipo?
3. El lenguaje de la teoría de números es
   \[\mathcal{L}_{NT} \: \text{is} \: \{0, S, +, \cdot, E, <\},\]
   donde los significados previstos de los símbolos son los siguientes: 0 significa el número cero,\(S\) es la función sucesora\(S \left( x \right) = x + 1\), los símbolos\(+\)\(\cdot\), y\(<\) significa lo que esperas, y\(E\) significa exponenciación, entonces\(E \left( 3, 2 \right) = 9\). Supongamos que\(\mathcal{L}_{NT}\) las fórmulas -serán interpretadas con respecto a los enteros no negativos y escribir una\(\mathcal{L}_{NT}\) fórmula -para expresar la afirmación de que\(p\) es un número primo. ¿Se puede escribir la declaración del Teorema de Lagrange, que establece que cada número natural es la suma de cuatro cuadrados?
   Escribe una fórmula que indique que no hay un número primo mayor. ¿Cómo expresaríamos la Conjetura de Goldbach, que cada número par mayor a dos puede expresarse como la suma de dos primos?
   ¿Cuál es la declaración formal de la Conjetura de Twin Primes, que dice que hay infinitamente muchos pares\(\left( x, y \right)\) tales que\(x\) y\(y\) son ambos primos y\(y = x + 2\)? El Teorema de Brecha Limitada, probado en 2013, dice que hay infinitamente muchos pares de números primos que difieren en 70,000,000 o menos. Escribir una declaración formal de ese teorema.
   Usa taquigrafía en tus respuestas a este problema. Por ejemplo, después de haber encontrado la fórmula que dice que\(p\) es prime, llama a la fórmula Prime\(\left( p \right)\) y usa Prime\(\left( p \right)\) en tus respuestas posteriores.
4. Supongamos que nuestro lenguaje tiene infinitamente muchos símbolos constantes de la forma\(','', ''', \ldots\) y no hay símbolos de función o relación distintos de =. Explique por qué esta situación genera problemas al mirar la fórmula\(=''''''\). ¿Dónde en nuestras definiciones proscribimos este tipo de problema?