What is the meaning of $M \models \varphi$?

Question

I'm currently learning for a computer science exam (programming paradigms) by reading the slides the professor offers. There are a lot of symbols and I would like to know what they mean.

First of all, there is $\mathcal{M}$ introduced as a "model". Then it is called a "universe" for all variable values and it "interpretes" predicates. So what is $\mathcal{M}$? Is it simply a set?

Then there is the statement that this question is about:

$\mathcal{M} \models \varphi$ iff $\varphi$ is true in the model $\mathcal{M}$ iff $\mathcal{M}$ is a model for $\varphi$.
$\mathcal{M} \models \psi$ iff $\mathcal{M} \models \varphi$ for all $\varphi \in \psi$.

What does $\mathcal{M} \models \varphi$ mean? How should I read it?

He gives the following examples:

• $\mathbb{R} \models \forall x y.x+y=y+x$
• $\mathbb{N} \not\models \forall x. \exists y. x + y = 0$

I would read these examples as

• "For the set of the real numbers we know that for all $x,y$ (in $\mathbb{R}$) addition is commutative."
• "For the set of the natural numbers, we know that the following statement is false: for all $x$ (in $\mathbb{N}$) exists an additive inverse element $y$."

Is that how it should be read?

Answer 1

You're close, but your intuition is not quite right. The problem is that your professor is not showing you the complete picture here.

In general, a model $\mathcal M$ consists of two parts: A universe $\mathcal U$ and an interpretation $\mathcal I$. The universe is, indeed, "just" a set, namely the set of possible values for the variables in your formula. The interpretation describes what the predicates and functions in your formula mean. Here are some examples.

Take, for example, the formula $\varphi = \exists x. \forall z. P(x,z)$. To describe whether this formula holds, we need a universe from which we can take the values for $x$ and $z$, and an interpretation that tells us what $P$ is.

If we choose $\mathcal U = \{ \circ \}$, i.e., a universe with a single element, and interpret $P$ as equality, i.e. $\mathcal I(P)(a,b) = \text{true}$ if $a=b$, then the formula holds: $(\mathcal U, \mathcal I) \models \varphi$. If, instead, $\mathcal I(P)(a,b) = \text{true}$ if $a \neq b$, the formula doesn't hold: $(\mathcal U, \mathcal I) \not\models \varphi$.

We could also choose $\mathcal U = \mathbb N$, and interpret $P$ as "divides", i.e., $\mathcal I(P)(a,b) = \text{true}$ iff $a \mid b$. In this case, the formula holds: If we choose the value $1$ for $x$, then clearly 1 divides every possible value for $z$.

Note that we can use interpretations to give nonstandard meanings to "standard" symbols: There are models in which the formula $1+1=2$ does not hold. For example, choose $\mathcal U = \mathbb N$, and interpret $+$ as take the first argument, i.e., $\mathcal{I}(+)(a,b) = a$, and $=$ as normal equality.

Now, back to the notation your professor uses. If he writes $\mathbb R \models \forall x,y. x+y=y+x$, this means that the formula holds over the set of real numbers using the standard interpretations of the function and predicate symbols.