3
$\begingroup$

I am confused about the following: I read yesterday that for a formula $\phi(x_1,\ldots,x_n)$ in a first order language $\mathcal{L}$ and an $\mathcal{L}$-structure $\mathcal{A}$, $\mathcal{A} \models \phi(x_1,\ldots,x_n)$ iff $\mathcal{A} \models \forall x_1 \ldots \forall x_n \phi(x_1,\ldots,x_n)$. This seems perfectly fine to me; if I understand it right, it's like saying something like $x^2 \geq 0$ is true iff $\forall x (x^2 \geq 0)$ is true.

Now consider a predicate $Q(x)$; then according to the above $\models Q(x)$ iff $\models \forall x Q(x)$. Isn't this equivalent to $\models Q(x) \leftrightarrow \forall x Q(x)$? However, $\not \models Q(x) \rightarrow \forall x Q(x)$; take for example $\mathcal{A} = (A, Q^{\mathcal{A}})$, where $A=\{a,b\}$, $Q^{\mathcal{A}}=\{a\}$ and $w: \mathrm{Var} \rightarrow A$, $w(x) = a$. What am I doing wrong?

1 Answers 1

3

I believe you are mixing two different conventions:

  • Some authors include a variable assignment along with each model when defining the satisfaction relation, so that a model consists of a structure $\mathcal{A}$ and a function $w$ assigning some element of $|\mathcal{A}|$ to each variable. It is possible to have two such functions w,w' such that $\mathcal{A},w \models \phi$ but \mathcal{A},w' \not \models \phi. Using only this definition, it is impossible to write $\mathcal{A} \models \phi$ when $\phi$ has free variables, as the definition requires $w$ to be fixed first. Enderton's book uses essentially this approach, writing $\models_\mathcal{A}\, \phi[w]$.

  • Other authors go on to define $\mathcal{A} \models \phi$, when $\phi$ has free variables, to mean $\mathcal{A},w\models \phi$ for every variable assignment function $w$ from $\mathcal{A}$. Letting $\phi^u$ be the universal closure of $\phi$, these authors would indeed say that $\mathcal{A} \models \phi$ if and only if $\mathcal{A} \models \phi^u$, because this is an immediate consequence of their definitions. This approach is used by Kleene's 1967 book and I believe it is also common in universal algebra.

One additional point of confusion is that the authors who take the first approach continue by defining ``$\models \phi$'' to mean that $\mathcal{A},w\models \phi$ for every structure $\mathcal{A}$ in the language and every variable assignment $w$ from $\mathcal{A}$. So authors who take the first approach can still prove that $\models \phi$ if and only if $\models \phi^u$ even if $\phi$ has free variables. This is exercise 6 on page 99 of Enderton's book, for example.

In the example in the second paragraph in the question, the trouble is that under the second convention I described, $\mathcal{A} \not \models Q(x)$, although it is true that $\mathcal{A},w \models Q(x)$. In fact neither $Q(x)$ nor $(\forall x)Q(x)$ is a logically valid formula.

  • 0
    Dear Carl: Thank you very much for having pointed out the stupid mistake contained in my (now deleted) answer to [this question](http://math.stackexchange.com/questions/98605/why-characteristic-zero-and-not-infinite-characteristic). That was very kind of you!2012-01-12