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?
Best Answer
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.