Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you for your answer. I am following the second convention. So, under this convention, is it wrong to use $\models\phi$ (meaning that $\mathcal{A} \models \phi$ for any structure $\mathcal{A}$)? My question basically was how can $\models Q(x)$ iff $\models \forall x Q(x)$ when $\not \models Q(x) \rightarrow \forall x Q(x)$? (for any $Q$) Doesn't $\models Q(x)$ iff $\models \forall x Q(x)$ imply that $\models Q(x) \rightarrow \forall x Q(x)$? –  Andrew Jan 10 '12 at 22:51
    
No, it doesn't. "$\models Q(x)$ implies $\models (\forall x) Q(x)$" says that if $Q(x)$ holds in absolutely every interpretation, then $(\forall x)Q(x)$ holds in absolutely every interpretation. That's a true claim. But "$\models Q(x) \to (\forall x)Q(x)$" claims that in any particular interpretation where $Q(x)$ holds, $(\forall x)Q(x)$ must also hold, even if $Q(x)$ may not hold in other interpretations. That's a false claim. –  Carl Mummert Jan 10 '12 at 23:10
    
Dear Carl: Thank you very much for having pointed out the stupid mistake contained in my (now deleted) answer to this question. That was very kind of you! –  Pierre-Yves Gaillard Jan 12 '12 at 23:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.