1.6: Sentencias

Entre las fórmulas en el idioma\(\mathcal{L}\), hay algunas en las que nos interesará especialmente. Estas son las oraciones de\(\mathcal{L}\) - las fórmulas que pueden ser verdaderas o falsas en un modelo matemático dado.

Usemos un ejemplo para introducir un lenguaje que será de vital importancia para nosotros a medida que trabajemos a través de este libro.

Definición 1.5.1. El lenguaje\(\mathcal{L}_{NT}\) es\(\{0, S, +, \cdot, E, <\}\), donde 0 es un símbolo constante,\(S\) es un símbolo de función unario,\(+\)\(\cdot\), y\(E\) son símbolos de función binarios, y\(<\) es un símbolo de relación binaria. Esto se denominará el lenguaje de la teoría de números.

Chaf: Aunque todavía no estamos fijando los significados de estos símbolos, probablemente deberíamos decirte que la interpretación estándar de\(\mathcal{L}_{NT}\) usará 0,,\(+\)\(\cdot\), y de la\(<\) manera que esperas. El símbolo\(S\) representará la función sucesora que mapea un número\(x\) al número\(x + 1\), y se\(E\) utilizará para la exponenciación:\(E32\) se supone que es\(3^2\).

Considere las siguientes dos fórmulas de\(\mathcal{L}_{NT}\):

\[\neg \left( \forall x \right) \left[ \left( y < x \right) \lor \left( y = x \right) \right].\]

\[\left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right].\]

(¿Notó que hemos comenzado a utilizar una presentación informal de las fórmulas?)

La segunda fórmula debería parecer familiar. No es más que la conocida ley de tricotomía de\(<\), y estarías de acuerdo en que la segunda fórmula es una verdadera afirmación sobre la colección de números naturales, donde estás interpretando de la\(<\) manera habitual.

La primera fórmula anterior es diferente. “Dice” que no todos\(x\) son mayores o iguales a\(y\). La verdad de esa afirmación es indeterminada: Depende de lo que\(y\) representa el número natural. La fórmula podría ser verdadera, o podría ser falsa, todo depende del valor de\(y\). Entonces nuestro objetivo en esta sección es separar las fórmulas de\(\mathcal{L}\) en una de dos clases: las oraciones (como el segundo ejemplo anterior) y las no oraciones. Para comenzar esta tarea, debemos hablar de variables libres.

Las variables libres son las variables de las que puede depender el valor de verdad de una fórmula. La variable\(y\) es libre en la primera fórmula anterior. Para dibujar una analogía a partir del cálculo, si miramos

\[\int_1^x \frac{1}{t} dt,\]

la variable\(x\) es libre en esta expresión, ya que el valor de la integral depende del valor de\(x\). La variable no\(t\) es libre, y de hecho no tiene ningún sentido decidir sobre un valor para\(t\). La misma distinción se mantiene entre variables libres y no libres en una\(\mathcal{L}\) fórmula. Tratemos de hacer las cosas un poco más precisas.

Definición 1.5.2. Supongamos que\(v\) es una variable y\(\phi\) es una fórmula. Vamos a decir que\(v\) es gratis en\(\phi\) si

1. \(\phi\)es atómico y\(v\) se produce en (es un símbolo en)\(\phi\), o
2. \(\phi : \equiv \left( \neg \alpha \right)\)y\(v\) es libre en\(\alpha\), o
3. \(\phi : \equiv \left( \alpha \lor \beta \right)\)y\(v\) está libre en al menos el de\(\alpha\) o\(\beta\), o
4. \(\phi : \equiv \left( \forall u \right) \left( \alpha \right)\)y no\(v\) es\(u\) y\(v\) es libre en\(\alpha\).

Así, si nos fijamos en la fórmula

\[\forall v_2 \neg \left( \forall v_3 \right) \left( v_1 = S \left( v_2 \right) \lor v_3 = v_2 \right),\]

la variable\(v_1\) es libre mientras que las variables\(v_2\) y no\(v_3\) son libres. Un ejemplo un poco más complicado es

\[\left( \forall v_1 \forall v_2 \left( v_1 + v_2 = 0 \right) \right) \lor v_1 = S \left( 0 \right).\]

En esta fórmula,\(v_1\) es libre mientras que no\(v_2\) es libre. Especialmente cuando una fórmula se presenta de manera informal, se debe tener cuidado con el alcance de los cuantificadores y la colocación de paréntesis.

Tendremos ocasión de utilizar la notación informal\(\forall x \phi \left( x \right)\). Esto significará que\(\phi\) es una fórmula y\(x\) se encuentra entre las variables libres de\(\phi\). Si entonces escribimos\(\phi \left( t \right)\), donde\(t\) es un\(\mathcal{L}\) -term, eso denotará la fórmula obtenida tomando\(\phi\) y reemplazando cada ocurrencia de la variable\(x\) con el término\(t\). Todo esto se definirá de manera más formal y más precisa en la Definición 1.8.2.

Definición 1.5.3. Una oración en un idioma\(\mathcal{L}\) es una fórmula de\(\mathcal{L}\) que no contiene variables libres.

Por ejemplo, si un lenguaje contenía los símbolos constantes 0, 1 y 2 y el símbolo de función binaria\(+\), entonces las siguientes son oraciones:\(1 + 1 = 2\) y\(\left( \forall x \right) \left( x + 1 = x \right)\). Probablemente estés convencido de que el primero de estos es cierto y el segundo de ellos es falso. En las dos secciones siguientes veremos que podrías estar en lo cierto. Pero entonces otra vez, tal vez no lo seas.

Ejercicios

1. Para cada una de las siguientes, encuentre las variables libres, si las hubiera, y decida si la fórmula dada es una oración. El lenguaje incluye un símbolo de función binaria\(+\), un símbolo\(<\) de relación binaria y símbolos constantes 0 y 2.
   (a)\(\left( \forall x \right) \left( \forall y \right) \left( x + y = 2 \right)\)
   (b)\(\left( x + y < x \right) \lor \left( \forall z \right) \left( z < 0 \right)\)
   (c)\(\left( \left( \forall y \right) \left( y < x \right) \right) \lor \left( \left( \forall x \right) \left( x < y \right) \right)\)
2. Explica con precisión, usando la definición de una variable libre, cómo sabes que la variable\(v_2\) es libre en la fórmula
   \[\left( \forall v_1 \right) \left( \neg \left( \forall v_5 \right) \left( v_2 = v_1 + v_5 \right) \right).\]
3. En matemáticas, a menudo vemos declaraciones como\(\sin^2 x + \cos^2 x = 1\). Observe que esto no es una oración, ya que la variable\(x\) es libre. Pero todos coincidimos en que esta afirmación es cierta, dadas las interpretaciones habituales de los símbolos. ¿Cómo podemos cuadrar esto con la afirmación de que las oraciones son las fórmulas que pueden ser verdaderas o falsas?
4. Si miramos la primera de nuestras fórmulas de ejemplo en esta sección,
   \[\neg \left( \forall x \right) \left[ \left( y < x \right) \lor \left( y = x \right) \right],\]
   e interpretamos las variables como que van sobre los números naturales, probablemente estará de acuerdo en que la fórmula es falsa si\(y\) representa el número natural 0 y true si\(y\) representa cualquier otro número. (Si no estás contento con que 0 sea un número natural, entonces usa 1.) Por otro lado, si interpretamos las variables como que van sobre los enteros, ¿qué podemos decir sobre la verdad o falsedad de esta fórmula? ¿Se te ocurre una interpretación para los símbolos que tendría sentido si intentáramos aplicar esta fórmula a la colección de números complejos?
5. Una variable puede ocurrir varias veces en una fórmula dada. Por ejemplo, la variable\(v_1\) ocurre cuatro veces en la fórmula
   \[\left( \forall v_1 \right) \left[ \left( v_1 = v_3 \right) \lor \left( v_1 = S v_2 \right) \lor \left( 0 + v_{17} < v_1 - S0 \right) \right].\]
   ¿Qué debería significar que una ocurrencia de una variable sea libre? Escribe una definición que comience: Se dice que la aparición\(n\) th de una variable\(v\) en una fórmula\(\phi\) es libre si... Se dice\(\phi\) que una ocurrencia de\(v\) en que no es libre está ligada. Dé un ejemplo de una fórmula en un lenguaje adecuado que contenga apariciones libres y enlazadas de una variable\(v\).
6. Mira la fórmula
   \[\left[ \left( \forall y \right) \left( x = y \right) \right] \lor \left[ \left( \forall x \right) \left( x < 0 \right) \right].\]
   Si denotamos esta fórmula por\(\phi \left( x \right)\) y\(t\) es el término\(S0\), encuentra\(\phi \left( t \right)\). [Sugerencia: El truco aquí es ver que hay un poco de mentira en la discusión de\(\phi \left( t \right)\) en el texto. Habiendo completado el Ejercicio 5, ahora podemos decir que solo reemplazamos la ocurrencia libre de la variable\(x\) cuando pasamos de\(\phi \left( x \right)\) a\(\phi \left( t \right)\).]