3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The second formula ($\mathcal M \vDash \psi$) is written more correctly as $\mathcal M \vDash \Gamma$, because $\psi$, like $\phi$ usually stay for a single formula, and you are meaning that $\mathcal M \vDash \phi$, for all $\phi \in \Gamma$. $\endgroup$ – Mauro ALLEGRANZA Mar 8 '14 at 20:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi Johannes, thanks for making clear that the model is a tuple of a universe and an interpretation. That already helped me a lot (+1). Could you please also answer my question how to read $\mathcal{M} \models \varphi$? From your current answer, I think it is "In the model M the formula varphi holds.". Is that correct? $\endgroup$ – Martin Thoma Mar 8 '14 at 18:39
  • $\begingroup$ That is the right interpretation. $\endgroup$ – Johannes Kloos Mar 8 '14 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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