1.3: Idiomas

Estaremos construyendo un lenguaje formal muy restringido, y nuestro objetivo al construir ese lenguaje será poder formar ciertas declaraciones sobre ciertos tipos de estructuras matemáticas. Para nuestro trabajo será necesario poder hablar de constantes, funciones y relaciones, por lo que necesitaremos símbolos para representarlas.

Chafia: Vamos a enfatizar esto una vez más. En este momento estamos discutiendo la sintaxis de nuestro lenguaje, las marcas en el papel. No nos vamos a preocupar por la semántica, o el significado, de esas marcas hasta más tarde -al menos no formalmente-. Pero es una tontería pretender que los significados pretendidos no impulsan nuestra elección de símbolos y la forma en que los usamos. Si queremos discutir los semi-semide-anillos izquierdos, nuestro lenguaje formal debe incluir los símbolos de función y relación que los matemáticos en este lucrativo y emocionante campo utilizan habitualmente, no los símbolos involucrados en el ajedrez, el puente o los hemi-semi-para-campos derecho-hemi-para-campos. No es nuestro objetivo confundir a nadie más de lo necesario. Entonces probablemente deberías pasar por el ejercicio ahora mismo de adivinar un lenguaje razonable para usar si nuestro campo de discusión pretendido era, digamos, la teoría de los números naturales. Ver Ejercicio 1.

Definición 1.2.1. Un lenguaje de primer orden\(\mathcal{L}\) es una colección infinita de símbolos distintos, ninguno de los cuales está debidamente contenido en otro, separados en las siguientes categorías:

1. Paréntesis: (,).
2. Conectivos:\(\lor\),\(\lnot\).
3. Cuantificador:\(\forall\).
4. Variables, una por cada entero positivo\(n\):\(v_1, v_2, \ldots, v_n, \ldots\). El conjunto de símbolos variables se denotará Vars.
5. Símbolo de igualdad:\(=\).
6. Símbolos constantes: Algún conjunto de cero o más símbolos.
7. Símbolos de función: Para cada entero positivo\(n\), algún conjunto de símbolos de función cero o más\(n\) -arios.
8. Símbolos de relación: Para cada entero positivo\(n\), algún conjunto de símbolos de relación cero o más\(n\) -arios.

Decir que un símbolo de función es\(n\) -ario (o tiene arity\(n\)) significa que se pretende representar una función de\(n\) variables. Por ejemplo,\(+\) tiene arity 2. De igual manera, los símbolos de una relación\(n\) -aria se destinarán a representar una relación sobre\(n\) -tuplas de objetos. Esto se hará formal en la Definición 1.6.1.

Para especificar un idioma, todo lo que tenemos que hacer es determinar cuáles, si los hay, símbolos de constante, función y relación que deseamos usar. Muchos autores, por cierto, dejan que el símbolo de igualdad sea opcional, o tratan el símbolo de igualdad como un símbolo de relación binaria ordinaria (es decir, 2-aria). Supondremos que cada idioma tiene el símbolo de igualdad, a menos que se indique específicamente.

Chafia: Deberíamos agregar una palabra sobre la frase “ninguna de las cuales está debidamente contenida en otra”, que aparece en esta definición. Hemos sido bastante vagos sobre el significado de la palabra símbolo, pero se supone que debes estar pensando en marcas hechas en una hoja de papel. Estaremos construyendo secuencias de símbolos y tratando de averiguar qué significan en las próximas secciones, y al no dejar que un símbolo esté contenido en otro, encontraremos que nuestro trabajo de interpretar secuencias es mucho más fácil.

Por ejemplo, supongamos que nuestro lenguaje contenía tanto el símbolo\(\heartsuit\) constante como el símbolo constante\(\heartsuit \heartsuit\) (observe que el primer símbolo está debidamente contenido en el segundo). Si estuvieras leyendo una secuencia de símbolos y te\(\heartsuit \heartsuit\) encontraras, sería imposible decidir si se trataba de un símbolo o una secuencia de dos símbolos. Al no permitir que los símbolos estén contenidos en otros símbolos, se evita este tipo de confusión, dejando el campo abierto para que otros tipos de confusión ocupen su lugar.

Ejemplo 1.2.2. Supongamos que estábamos tomando un curso de álgebra abstracta y queríamos especificar el lenguaje de los grupos. Un grupo consiste en un conjunto y una operación binaria que tiene ciertas propiedades. Entre esas propiedades se encuentra la existencia de un elemento de identidad para la operación. Así, podríamos decidir que nuestro lenguaje contendrá un símbolo constante para el elemento de identidad, un símbolo de operación binaria y ningún símbolo de relación. Nosotros obtendríamos

\[\mathcal{L}_G \: \text{is} \: \{ 0, + \},\]

donde 0 es el símbolo constante y\(+\) es un símbolo de función binaria. O tal vez nos gustaría escribir nuestros grupos usando la operación como multiplicación. Entonces una elección razonable podría ser

\[\mathcal{L}_G \: \text{is} \: \{ 1, ^{-1}, \cdot \},\]

que incluye no sólo el símbolo constante 1 y el símbolo de función binaria\(\cdot\), sino también un símbolo de función unario (o 1-ario)\(^{-1}\), que está diseñado para seleccionar la inversa de un elemento del grupo. Como puede ver, hay un poco de elección involucrada en el diseño de un lenguaje.

Ejemplo 1.2.3. El lenguaje de la teoría de conjuntos no es muy complicado en absoluto. Incluiremos un símbolo de relación binaria\(\in\), y eso es todo:

\[\mathcal{L}_{ST} \: \text{is} \: \{ \in \}.\]

La idea es que este símbolo sea utilizado para representar la relación elementhood, por lo que la interpretación de la cadena\(x \in y\) será que el conjunto\(x\) sea un elemento del conjunto\(y\). Es posible que se sienta tentado a agregar otros símbolos de relación\(\subset\), como, o símbolos constantes\(\emptyset\), como, pero será más fácil definir dichos símbolos en términos de símbolos más primitivos. No más fácil en términos de legibilidad, sino más fácil en términos de probar cosas sobre el idioma.

En general, para especificar un idioma necesitamos enumerar los símbolos constantes, los símbolos de función y los símbolos de relación. Puede haber infinitamente muchos [de hecho, incontables muchos (cf. el Apéndice)] de cada uno. Entonces, aquí hay una especificación de un lenguaje:

\[\mathcal{L} \: \text{is} \: \{ c_1, c_2, \ldots, f_1^{a \left( f_1 \right)}, f_2^{a \left( f_2 \right)}, \ldots, R_1^{a \left( R_1 \right)}, R_2^{a \left( R_2 \right)}, \ldots \}.\]

Aquí, los\(c_i\) s son los símbolos constantes, los\(f_i^{a \left( f_i \right)}\) s son los símbolos de función, y los\(R_i^{a \left( R_i \right)}\) s son los símbolos de relación. Los superíndices en los símbolos de función y relación indican la aridad de los símbolos asociados, así\(a\) es un mapeo que asigna un número natural a una cadena que comienza con una\(f\) o una\(R\), seguida de un ordinal subíndice. Así, un símbolo de función oficial podría verse así:

\[f_{17}^{223},\]

lo que diría que la función que se asociará con el símbolo de función 17 es una función de 223 variables. Afortunadamente, tan terrible detalle rara vez será necesario. Normalmente veremos solo símbolos de función unarios o binarios y la aridad de cada símbolo se declarará una vez. Entonces los autores confiarán en que el contexto le recordará al lector paciente la aridad de cada símbolo.

Ejercicios

1. Escribe cuidadosamente los símbolos que te gustaría tener en un idioma\(\mathcal{L}\) que pretendas usar para escribir declaraciones de álgebra elemental. Indique cuáles de los símbolos son símbolos constantes, y la aridad de los símbolos de función y relación que elija. Ahora escribe otro idioma,\(\mathcal{M}\) (es decir, otra lista de símbolos) con el mismo número de símbolos constantes, símbolos de función y símbolos de relación que no querrías usar para álgebra elemental. Piense en el valor de la buena notación.
2. ¿Cuáles son buenos ejemplos de funciones unarias (1-arias)? ¿Funciones binarias? ¿Se pueden encontrar ejemplos naturales de relaciones con arity 1, 2, 3 y 4? Al pensar en este problema, manténgase atento a la diferencia entre la función y el símbolo de función, entre la relación y el símbolo de relación.
3. En la localidad de Sneezblatt hay tres establecimientos gastronómicos: McBurgers, Chez Fancy y Sven's Tandoori Palace. Piensa por un minuto en las declaraciones que quizás quieras hacer sobre estos restaurantes, y luego escribe\(\mathcal{L}\), el lenguaje formal para tu teoría de los restaurantes. Diviértete con esto, pero trata de incluir tanto símbolos de función como de relación en\(\mathcal{L}\). ¿Qué interpretaciones planeas para tus símbolos?
4. Te han puesto a cargo de elaborar el horario para una liga de basquetbol. Esta liga involucra a ocho equipos, cada uno de los cuales debe jugar cada uno de los otros siete equipos exactamente en dos ocasiones: una en casa y otra en el camino. Piensa en un lenguaje razonable para esta situación. ¿Qué constantes necesitarías? ¿Necesitas algún símbolo de relación? ¿Símbolos de función? Sería bueno que su agenda terminada no tuviera ningún equipo jugando dos juegos el mismo día. ¿Se te ocurre una manera de afirmar esto usando los símbolos formales que has elegido? ¿Se puede expresar la frase que establece que cada equipo juega a cada otro equipo exactamente dos veces?
5. Vamos a elaborar un lenguaje para la trigonometría elemental. Para comenzar, permítanos sugerirle que comience con muchos símbolos constantes, uno por cada número real. Es tentador usar los símbolos 7 para representar al número siete, pero esto se encuentra con problemas. (¿Ves por qué esto es ilegal? 7, 77, 7/3,...) Ahora bien, ¿qué funciones te gustaría discutir? Piensa en símbolos para ellos. ¿Cuáles son las peculiaridades de tus símbolos de función? ¡No olvides que necesitas símbolos para sumar y multiplicar! ¿Qué símbolos de relación te gustaría usar?
6. Un lenguaje informático es otro ejemplo de lenguaje. Por ejemplo, el símbolo\(:=\) podría ser un símbolo de función binaria, donde la interpretación de la instrucción
   \[x := 7\]
   sería alterar el estado interno de la computadora colocando el valor 7 en la posición en memoria referenciada por la variable\(x\). Piense en la función asociada al símbolo de función binaria
   \[\text{if _______, then _______.}\]
   ¿Cuáles son las entradas en esta función? ¿Qué tipo de cosas hace la función? Mira la declaración
   \[\text{If} \: x + y > 3, \: \text{then} \: z := 7.\]
   Identifica los símbolos de función, símbolos constantes y símbolos de relación. ¿Cuáles son las peculiaridades de cada función y símbolo de relación?
7. ¿Cuál sería un buen lenguaje para la teoría de los espacios vectoriales? Este problema es un poco más difícil, ya que hay dos variedades diferentes de objetos, escalares y vectores, y hay que poder distinguirlos. Escribe los axiomas de los espacios vectoriales en tu idioma. O, mejor aún, ¡usa un lenguaje que incluya un símbolo de función unario para cada número real para que los escalares no existan como objetos en absoluto!
8. En realidad no es necesario incluir símbolos de función en el lenguaje, ya que una función es solo un tipo especial de relación. Sólo para ver un ejemplo, piensa en la función\(f : \mathbb{N} \rightarrow \mathbb{N}\) definida por\(f \left( x \right) = x^2\). Recordando que una relación sobre\(\mathbb{N} \times \mathbb{N}\) es solo un conjunto de pares ordenados de números naturales, encuentra una relación\(R\) sobre\(\mathbb{N} \times \mathbb{N}\) tal que\(\left( x, y \right)\) sea un elemento de\(R\) si y solo si\(y = f \left( x \right)\). Convénzate de que podrías hacer lo mismo para cualquier función definida en cualquier dominio. ¿Qué condición debe ser verdadera si una relación\(R\) on\(A \times B\) va a ser una función mapeada\(A\) a\(B\)?