How to find a Herbrand-Model to a given set

Question

I have a Language $L=L(\{R,P\},\emptyset,\{c_0,c_1,c_2\})$ where $R$ denotes a two-digit and $P$ a one-digit relation symbol. And I got the set $S=\{\forall x R(x,x), \forall x\exists y \neg R(x,y), \forall x\exists y R(x,y), P(c_0), \forall x\forall y ((P(x) \land R(x,y)) \rightarrow P(y)) \}$.
I have to find a Herbrand-Model $M$ for $L$ such that all elements of $S$ are satisfied.
My problem is that I don't really see what I have to do here since the domain of the Herbrand-Model is simply all closed terms of $L$ (so nothing I can change) and I am not quite sure how to define the interpretaion of $M$ such that it would actually help.
Thx in advance!

Answer 1

An Herbrand structure $\mathcal M$ for a certain language $\mathcal L$ is a structure made of "syntactical stuff".

Thus, constants of the language plays a double role : they are "names" in the language to denote objects and thy are the "objects" themselves. And so on with "complex" terms buit up from constants and function symbols.

In the FOL language above, with constant symbols $c_0,c_1, c_2$, no function symbols and two predicate symbols: $R$ and $P$, we have that the constants must be considered as "objects": the elements of the domain $M$ of the model.

Consider now the set of formulas:

$S = \{ ∀xR(x,x),∀x∃y¬R(x,y),∀x∃yR(x,y),P(c_0),∀x∀y((P(x)∧R(x,y))→P(y)) \}$

to be satisfied by $\mathcal M$.

Obviously (fourth formula) we need: $P(c_0)$, i.e. we need that $\{ c_0 \} \subseteq P^M$ (the intepretation of the unary predicate symbol $P$).

In order to satisfy the first formula: $∀xR(x,x)$, we need that: $R(c_0,c_0), R(c_1,c_1), R(c_2,c_2)$. Thus: $\{ (c_0,c_0), (c_1,c_1), (c_2,c_2) \} \subseteq R^M$.

This satisfy also the third formula.

For the second one, we need e.g.: $\lnot R(c_0,c_1), \lnot R(c_1,c_2), \lnot R(c_2, c_0)$.

The remaining cases must be handled accordingly, taking into account the fifth formula.

---

In conclusion, we can define $\mathcal M$ with:

$M = \{ c_0, c_1, c_2\}, P^M = \{ c_0 \}$ and $R^M = \{ (c_0,c_0), (c_1,c_1), (c_2,c_2) \}$

and check that all the formulas in $S$ are satisfied in $\mathcal M$.