# What is the “common” definition of model in first order logic?

While reading the note "First-Order Logic in a Nutshell" from Lorenz Halbeisen (can't find it online, but it's also a section in his book Combinatorial Set Theory page 31-44.), I got confused by the remark at the end of the following paragraph:

Now, let $\mathsf T$ be an arbitrary set of $\mathcal L$-formulas. Then an $\mathcal L$-structure $\mathfrak A$ is a model of $\mathsf T$ if for every assignment $j$ in $\mathfrak A$ and for each formula $\varphi \in \mathsf T$ we have $(\mathfrak A,j) \models \varphi$, i.e. $\varphi$ holds in the $\mathcal L$-interpretation $I=(\mathfrak A,j)$. We usually denote models by bold letters like $\mathbf M$, $\mathbf N$, $\mathbf V$, et cetera. Instead of saying "$\mathbf M$ is a model of $\mathsf T$" we just write $\mathbf M \models \mathsf T$. If $\varphi$ fails in $\mathbf M$, then we write $\mathbf M \nvDash \varphi$, which is equivalent to $\mathbf M \vDash \neg \varphi$ (this is because for any $\mathcal L$-formula $\varphi$ we have either $\mathbf M \models \varphi$ or $\mathbf M \models \neg \varphi$).

What confused me initially is that he defined previously that a sentence is a formula with no free variables. To me, the above remark seems only valid if "formula" is replaced by "sentence" (because $\neg \forall x \varphi \Leftrightarrow \exists x \neg \varphi \not\Leftrightarrow \forall x \neg \varphi$). I then tried to read other texts about first order logic (for example in Wikipedia and SEP) in order to learn whether these definitions of sentence and formula are common. However, these texts are long, and instead of resolving my initial confusion, they turned up another question. They seem to define model only for an $\mathcal L$-interpretation $I=(\mathfrak A,j)$, but not for an $\mathcal L$-structure $\mathfrak A$. Lorenz Halbeisen on the other hand defines model only for an $\mathcal L$-structure $\mathfrak A$, but not for an interpretation.

Here is my main question:

When people talk about first order logic, it's common to use the notion of a model. But I'm confused now of whether this notion refers to an interpretation or to a structure. Is there a "common" definition of model in first order logic, and does this definition refer to an interpretation (instead of referring to a structure)?

And here is my initial question, which caused the confusion:

Is the mentioned remark invalid?

-
I think I found the main reason for my confusion now: The notion "interpretation" as used by Wikipedia and SEP doesn't include a variable assignment, contrary to the way "interpretation" is used by Lorenz Halbeisen. So I'm probably back to the point where I'm wondering whether some occurrences of "formula" have to be replaced by "sentence" in the cited paragraph. –  Thomas Klimpel Apr 14 '12 at 13:33

It is, in the sense you are using the terms, structures and not interpretations. That is so also in the definition that you quote (I looked up the section 31-44 that you mentioned). And it is structure in the definition you quote. For recall that the definition says "in every $\mathcal{L}$-interpretation."

A definition of the type given here is quite common. Essentially, what it does is to define a formula (with free occurrences of variables) to be true if the universally quantified version of the formula is true.

For technical reasons, allowing free occurrences of variables is useful. We will be wanting to define truth of sentences $\varphi$ in $\mathbf{M}$ by induction on the complexity of $\varphi$. So for example we will want to say that the sentence $\exists x \psi(x)$ is true in the structure $\mathbf{M}$ if for every element $m$ of $M$, $\psi(m)$ is true in $\mathbf{M}$. That raises the immediate problem that $\psi(m)$ is not a sentence, you cannot put an object into a sentence.

There are two standard workarounds. One is to invent a new constant symbol for every element of $M$, extend the language $\mathcal{L}$ by adding these symbols. The other is to introduce assignments in the style that Halbeisen uses. If we do that, it is easier to work with formulas than with only those formulas that happen to be sentences.

-
OK, so my main problem is probably that his remark "... for any $\mathcal L$-formula $\varphi$ we have either $\mathbf M \models \varphi$ or $\mathbf M \models \neg \varphi$" is as valid as your example "...that the sentence $\exists x \psi(x)$ is true in the structure $\mathbf M$ if for every element $m$ of...". So let's introduce an universal quantifier into his remark, to see what happens: "... for any $\mathcal L$-formula $\varphi$ we have either $\mathbf M \models \forall x \varphi$ or $\mathbf M \models \forall x \neg \varphi$". So his remark is invalid, correct? –  Thomas Klimpel Apr 14 '12 at 14:06
@ThomasKlimpel: Yes, I was concentrating on the various definitions, missed the error. At that point he should have switched to sentence. –  André Nicolas Apr 14 '12 at 15:09
Thanks for your answer. My confusion is finally gone now, and everything seems to be consistent. (For example, the Generalisation inference rule seemed to be inconsistent with the "Soundness Theorem", because I used the wrong interpretation of model.) I suddenly like Halbeisen's note again. I found it very readable on first reading, but the second reading turned into a nightmare. I tried to prove some "obvious" formulas myself, but had to consult other resources with different definitions. Then I got confused about variable renaming, substitution, axiom schemas and meta-theorems. –  Thomas Klimpel Apr 14 '12 at 19:39
Unfortunately, in logic perhaps more than elsewhere, there is a lack of uniformity. Everybody is going to the same place, but the roads are not the same. That often makes it difficult to answer questions on this site, since the choice of path is instructor-dependent. –  André Nicolas Apr 14 '12 at 19:47
@André Nicolas: I think you have hit the nail on the head. I wonder if it would be helpful to have an answer the explains that at length, so that we can link to it from time to time. –  Carl Mummert Apr 14 '12 at 21:05