Two formulas with different free variables not semantically equivalent

Question

I have two formulas. The first one with free variables $\{S\}$ is:

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

The second one with free variables $\{x,S\}$ is:

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

I guess we do not have in first order logic:

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

Here is an attempt of mine. I use a model where $P=\{<0>\}$. And then I find that for these assignments I get different truth values:

$$\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}$$

Is this a way to show semantical inequality?

Answer 1

They are not semantically equivalent in that -- for any given interpretation of $S$ and $P$ -- the first has only one truth value, whereas the truth value of the second depends on which value you give $x$.

For example, in your model with $S=\{0,1\}$ and $P$ being true for $0$ only, then your second formula is true sometimes, namely when $x=0$ (and in fact whenever $x\ne 1$) -- but with the same interpretation the first formula is simply false, period.

Answer 2

The semantics for those two formulas are arguably not even the same sort of thing, let alone the same thing.

For the usual set-theoretic semantics, the semantics of the first formula would be a $0$-ary relation, i.e. a subset of the set $D^0=\{\langle\rangle\}$ where $D$ is the domain we're working over. (We can identify "true" with $\{\langle\rangle\}$ and "false" with $\{\}$.) The semantics of the second formula, on the other hand, would be a unary relation, i.e. a subset of $D^1=D$. Generally, a formula with potentially $n$ free variables will have semantics as an $n$-ary relation, i.e. subset of $D^n$. Arguably, it shouldn't even make sense to ask whether two formulas with different potentially free variables have the same semantics, but set theory has a global notion of equality which lets you ask "nonsense" questions like whether $\pi=\mathbb Q$. In categorical or type theoretic semantics, it's quite easy and natural to arrange things such that asking whether the semantics of formulas with different sets of potentially free variables is simply not well-formed.

Now I've repeatedly said "potentially free variables". Consider a formula $P(x)$. It is clear that $x$ is free in $P(x)$, but we could also say that $y$ is free in $P(x)$ but it just happens not to occur. Usually we restrict "free variables" to the variables that actually occur hence my use of "potentially free variables". The significance here is that the semantics of $P(x)$ depend on whether we consider it a formula where only $x$ may occur freely or a formula where $x$ and $y$ may both occur freely (or any other collection of variables containing $x$). What we can do, then, is view your first formula as potentially but not actually containing $x$ free which would make its semantics comparable (even in a categorical or type theoretic semantics) to the semantics of your second formula. Even for the set-theoretic semantics, this is important. Let's say that you chose an interpretation for $S$, $P$ and a semantic domain $D$ such that your second formula held for every element of $D$. It's semantics would then be $D$ itself. In that case, it would also be the case that your first formula would hold and thus its semantics would be $\{\langle\rangle\}$. $D\neq\{\langle\rangle\}$, but if we viewed the first formula as having one, unused free variables, then, being a constantly "true" formula its semantics would also be $D$.

In the more general categorical semantics, this step of moving a formula from having one set of potentially free variables to having a larger set is not necessarily trivial. In traditional set-theoretic semantics it is often left completely implicit and not much discussed. This is a mistake. For example, the categorical understanding of the existential and universal quantifiers are intimately related to this operation of expanding the number of potential free variables. In fact, they are characterized by it. Specifically, they are left and right adjoint to it respectively.