I am reading Handbook of Satisfiability in which they say:

An algebraic structure, or simply structure, consists of a non-empty set of objects existing in the world $w$, called the domain and denoted below by $D$, and a function, called an interpretation and denoted below by $R$, that assigns to each constant an entity in $D$, to each predicate a relation among entities in $D$, and to each functor a function among entities in $D$.

A sentence $p$ is said to be true in $w$ if the entities chosen as the interpretations of the sentence’s terms and functors stand to the relations chosen as the interpretation of the sentence’s predicates.

In this context, could you help me with some example of predicates of a sentence? And what does "stand to" mean here?

I am not a native English speaker, maybe this is why I can not understand this claim.

  • 1
    $\begingroup$ I can only help with the "stand to" part: this means that if you apply function $R$ to the parts of the sentence, which are not predicates, you will get some constants and functions. If then these constants and functions satisfy the relations you obtain by applying $R$ to the predicates, the statement is true. I cannot think about a specific example, but if you want something easy to imagine: look into analytic geometry. $\endgroup$ – wvxvw Feb 25 '16 at 16:09
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take more care in the future; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 26 '16 at 14:22
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$ – Raphael Feb 26 '16 at 14:24
  • $\begingroup$ The quoted sentence is horrible. I don't understand it either. $\endgroup$ – Raphael Feb 26 '16 at 14:24

Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be $$ {\sf eats}({\sf cat}, {\sf head}({\sf tuna})) $$ Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows: $$ \mbox{World $w$: }\qquad\qquad \begin{array}{l} [\![ {\sf cat} ]\!]^c = 5 \\ [\![ {\sf tuna} ]\!]^c = 4 \\ [\![ {\sf squirrel} ]\!]^c = 2 \\ \ldots \\ [\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\ \ldots \\ [\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \} \end{array} $$ (A structure can define more symbols than those used in the formula, hence the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$. Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$. Predicate symbols are interpreted as subsets of $D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $[\![-]\!]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have $$ [\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c)) $$ which is $$ < (5, g(4)) $$ i.e. $$ 5 < \pi \cdot 4 $$ which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.

| cite | improve this answer | |

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.