1
$\begingroup$

I was curious whether this statement is satisfied by some model?

And is it satisfied by Herbrand's model?

$∃xR(x)∧¬R(c)$

For the first question, I can take a model where domain is the real numbers and R is whether x is a natural number or not. So this is satisfied by taking x=4 and c=3 for instance. But regarding the second question - if it is not satisfied by some Herbrand model, isn't it suppose to be not satisfied by any model? Or maybe it is indeed satisfied by Herbrand model? But then, what if Herbrand's model is just has only the constant c?

Thanks in advance.

$\endgroup$
  • $\begingroup$ If the domain is the irrational numbers, then neither $4$ nor $2$ are there ... $\endgroup$ – Henning Makholm Feb 10 '17 at 11:50
  • $\begingroup$ Oops, I meant saying that the domain is real numbers instead. Sorry. $\endgroup$ – Eran Feb 10 '17 at 11:54
  • $\begingroup$ Of course, every model of $\exists x R(x) \land \lnot R(c)$ must have at least two elements. $\endgroup$ – Mauro ALLEGRANZA Feb 10 '17 at 12:07
  • $\begingroup$ If the language has only constant $c$ and no function symbol, then the Herbrand universe will be $U = \{ c \}$. $\endgroup$ – Mauro ALLEGRANZA Feb 10 '17 at 12:08
  • $\begingroup$ Mauro - every model of exists x R(x) and not R(c) must have two constants? Isn't Herbrand universe is only the constant c so only thing I can replace with x is c and then get a contradiction? $\endgroup$ – Eran Feb 10 '17 at 12:14
1
$\begingroup$

Every model of $∃xR(x) ∧ ¬R(c)$ must have at least two elements.

We can satisfy the formula with e.g. the domain $D = \{ 0, 1 \}$ and interpreting $c$ with $0$ and $R$ with the subset $\{ 1 \}$ of $D$, i.e. with the "property": $(x \ne c)$.

If the language has only the constant $c$ and no function symbol, then the Herbrand universe will be $U = \{ c \}$.

Thus, any Herbrand structure built up on the universe $U$ will not satisfy the formula.


See :

Theorem 9.24 A set of clauses $S$ has a model iff it has an Herbrand model.

Theorem 9.24 is not true if $S$ is an arbitrary formula.

Example 9.25 Let $S = p(a) ∧ ∃x¬p(x)$. Then

$(\{ 0, 1 \}, \{ \{ 0 \} \}, \{ \}, \{ 0 \} )$

is a model for $S$ since $v(p(0)) = T$ , $v(p(1)) = F$.

See page 179 : "An interpretation $\mathfrak I$ is a 4-tuple :

$I = (D, \{ R_1,\ldots, R_l \}, \{ F_1,\ldots, F_m \}, \{ d_1,\ldots, d_n \})$,

where $D$ is a non-empty set called the domain, $R_i$ is an $n_i$-ary relation on $D$ that is assigned to the $n_i$-ary predicate $p_i$, $F_j$ is an $n_j$-ary function on $D$ that is assigned to the function symbol $f_j$ and $d_i ∈ D$ is assigned to the constant $a_i$."

$S$ has no Herbrand models since there are only two Herbrand interpretations and neither is a model:

$( \{ a \}, \{ \{ a \} \}, \{ \}, \{ a \}), (\{ a \}, \{ \{ \} \}, \{ \}, \{ a \})$.

$\endgroup$
  • $\begingroup$ I don't get the part where he shows the 4-tuple - what is its use in here? I mean, for that v, why isn't there a Herbrand model? How come there are 2 Herbrand interpretations and neither is a model? How do you receive such result? $\endgroup$ – Eran Feb 10 '17 at 14:33
  • $\begingroup$ @Eran - how to build the Herbrand structures ? As said, H universe is $U = \{ c \}$; no function symbols, and thus no possibility to generate more closed terms. The constant symbol $c$ will be interpreted by the element $c \in U$. What about the predicate symol $p$ ? A unary predicate symbol is interpreted with a subset of the domain; the domain $U$ has only two subsets : $\{ \}$ (the emptyset) and $\{ c \}$. Conclusion: only two possible H structures : 1/2 $\endgroup$ – Mauro ALLEGRANZA Feb 10 '17 at 15:03
  • $\begingroup$ $( U , \{ \emptyset \}, \text{no function}, \{ c \} )$ and $( U , \{ U \}, \text{no function}, \{ c \} )$. 2/2 $\endgroup$ – Mauro ALLEGRANZA Feb 10 '17 at 15:03
  • $\begingroup$ Why aren't those Herbrand interpretations models? What I don't get is the second element in the tuple - what is that relation? Why is it a set of sets and how do you compute it? Also - if U={c} is the Herbrand universe. Does not it mean that I can only use c as x and get R(c) and not R(c) and thus the Herbrand model does not satisfy the statement? If so, isn't it known that if an "exists" statement (statements with only "exists" quantifers) is not satisfied for Herbrand, it means that it does not apply to any other model because Herbrand is the smallest model? $\endgroup$ – Eran Feb 10 '17 at 15:51
  • $\begingroup$ @Eran - sorry, but I'll not copy paste all the book; what defintions (interpretation, Herbrand univers) are you using ? Perhaps, it can be useful if you add them to the text; otherwise, you can like the ref to the relevant pages of your textbook. $\endgroup$ – Mauro ALLEGRANZA Feb 10 '17 at 15:58

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.