Dos fórmulas con distintas variables libres no son semánticamente equivalentes

Question

Tengo dos fórmulas. La primera con variables libres $\{S\}$ es:

$$\forall x(x \in S \Rightarrow P(x))$$

La segunda con variables libres $\{x,S\}$ es:

$$x \in S \Rightarrow P(x)$$

Supongo que no tenemos en la lógica de primer orden:

$$\vDash \forall x(x \in S \Rightarrow P(x)) \Leftrightarrow (x \in S \Rightarrow P(x))$$

He aquí un intento mío. Utilizo un modelo en el que $P=\{<0>\}$ . Y entonces me encuentro con que para estas tareas obtengo diferentes valores de verdad:

$$\begin{array}{ccc} x & S & \forall x(x \in S \Rightarrow P(x)) \\ \hline 0 & \{1\} & F \\ 0 & \{0,1\} & F \end{array}$$

$$\begin{array}{ccc} x & S & x \in S \Rightarrow P(x) \\ \hline 0 & \{1\} & T \\ 0 & \{0,1\} & T \end{array}$$

¿Es ésta una forma de mostrar la desigualdad semántica?

Answer 1

No son semánticamente equivalentes en el sentido de que, para cualquier interpretación de $S$ y $P$ -- la primera sólo tiene un valor de verdad, mientras que el valor de verdad de la segunda depende del valor que le des a $x$ .

Por ejemplo, en su modelo con $S=\{0,1\}$ y $P$ siendo cierto para $0$ entonces su segunda fórmula es cierta a veces, es decir, cuando $x=0$ (y de hecho siempre que $x\ne 1$ ) -- pero con la misma interpretación la primera fórmula es simplemente falsa, y punto.

Answer 2

Podría decirse que la semántica de estas dos fórmulas ni siquiera es la misma ordenar de la cosa, por no hablar de la misma cosa.

Para la semántica habitual de la teoría de conjuntos, la semántica de la primera fórmula sería una $0$ -es decir, un subconjunto del conjunto $D^0=\{\langle\rangle\}$ donde $D$ es el dominio sobre el que estamos trabajando. (Podemos identificar "verdadero" con $\{\langle\rangle\}$ y "false" con $\{\}$ .) En cambio, la semántica de la segunda fórmula sería una relación unaria, es decir, un subconjunto de $D^1=D$ . Generalmente, una fórmula con potencial $n$ las variables libres tendrán la semántica de un $n$ relación -aria, es decir, subconjunto de $D^n$ . Podría decirse que ni siquiera debería tener sentido pregunte a si dos fórmulas con diferentes variables potencialmente libres tienen la misma semántica, pero la teoría de conjuntos tiene una noción global de igualdad que permite hacer preguntas "sin sentido" como si $\pi=\mathbb Q$ . En semántica categórica o teórica de tipos, es bastante fácil y natural arreglar las cosas de tal manera que preguntar si la semántica de fórmulas con diferentes conjuntos de variables potencialmente libres simplemente no está bien formada.

Ahora he dicho repetidamente " potencialmente variables libres". Consideremos una fórmula $P(x)$ . Es evidente que $x$ es gratuito en $P(x)$ pero también podríamos decir que $y$ es gratuito en $P(x)$ pero resulta que no ocurre. Normalmente restringimos las "variables libres" a las variables que realmente ocurren, de ahí que utilice "variables potencialmente libres". Lo importante aquí es que la semántica de $P(x)$ dependerá de si la consideramos una fórmula en la que sólo $x$ puede aparecer libremente o una fórmula en la que $x$ y $y$ pueden aparecer libremente (o cualquier otra colección de variables que contengan $x$ ). Lo que podemos hacer, entonces, es ver su primera fórmula como potencialmente pero no realmente conteniendo $x$ libre que haría su semántica comparable (incluso en una semántica categórica o teórica de tipos) a la semántica de tu segunda fórmula. Esto es importante incluso para la semántica teórica de conjuntos. Supongamos que se elige una interpretación para $S$ , $P$ y un dominio semántico $D$ tal que su segunda fórmula se cumpliera para cada elemento de $D$ . Su semántica sería entonces $D$ sí mismo. En ese caso, también se daría el caso de que tu primera fórmula se mantuviera y, por tanto, su semántica sería $\{\langle\rangle\}$ . $D\neq\{\langle\rangle\}$ pero si consideramos que la primera fórmula tiene una variable libre no utilizada, entonces, al ser una fórmula constantemente "verdadera" su semántica sería también $D$ .

En la semántica categórica más general, este paso de pasar una fórmula de tener un conjunto de variables potencialmente libres a tener un conjunto mayor no es necesariamente trivial. En la semántica teórica de conjuntos tradicional, a menudo se deja completamente implícito y no se discute mucho. Esto es un error. Por ejemplo, la comprensión categórica de los cuantificadores existencial y universal está íntimamente relacionada con esta operación de ampliar el número de variables potencialmente libres. De hecho, son caracterizado por él. En concreto, son adyacentes a la izquierda y a la derecha respectivamente.