# Unexpected definition of structure in predicate logic

From "Logic for Computer Scientists" by Uwe Schoning:

A function symbol of arity 0 will also be called a constant.

A structure is a pair $$\mathcal{A} = (U_{\mathcal{A}}, I_{\mathcal{A}})$$ where $$U_{\mathcal{A}}$$ is an arbitrary, non-empty set and is called the ground set or universe. Further, $$I_{\mathcal{A}}$$ is a mapping that maps

• each $$k$$-ary predicate symbol $$P$$ to a $$k$$-ary predicate on $$U_{\mathcal{A}}$$ (if $$I_{\mathcal{A}}$$ is defined on $$P$$).

• each $$k$$-ary function symbol $$f$$ to a $$k$$-ary function on $$U_{\mathcal{A}}$$ (if $$I_{\mathcal{A}}$$ is defined on $$f$$).

• each variable $$x$$ to an element of $$U_{\mathcal{A}}$$ (if $$I_{\mathcal{A}}$$ is defined on $$x$$).

This sounds very much like the definition given for an 'interpretation' in another text, except that there the mapping is not defined for variables. It seems strange to me to have the mapping defined for variables. Why would this be done? Is this the difference between an interpretation and a structure?

• See structure; but sometimes the structure is the "object" side, and the signature is the language side. With this approach, the interpretation is the mapping from terms and sentences (or formulas) to objcets in the domain and truth-values. Commented Oct 7, 2018 at 19:32
• See also the post : Connection between interpretation, variable assignment and truth valuation. Commented Oct 7, 2018 at 19:35
• @MauroALLEGRANZA I'm sorry, I'm still not sure I quite understand. What is the difference between a variable and a constant in this approach? They both seem to be assigned an element of the domain at the same time and in the same manner. Commented Oct 7, 2018 at 19:59

Rif. Uwe Schöning, Logic for computer scientists, Birkhauser (1989).

The "usual" approach is to define an interpretation for the predicates, functions and constants symbols of the language.

On top of it, we have to add a mechanism, usually called variable assignment function to assign a "temporary" meaning to the free variables of a formula.

Thus, if we consider the formula $$(x=0)$$ and interpret it in the domain $$\mathbb N$$ of natural numbers, we have to consider a variable assignment :

$$\mu : \text {Var} \to \mathbb N$$

such that, e.g. : $$\mu(x)=0$$.

In this case, we have $$\mathbb N, \mu \vDash (x=0)$$.

With a different assignment $$\mu'(x)=1$$, we will have : $$\mathbb N, \mu' \nvDash (x=0)$$.

As you can see form Example, page 45 with formula $$F = ∀xP(x,f(x)) ∧ Q(g(a,z))$$, the author says :

In this structure [whith $$U_{\mathcal A}= \mathbb N$$, $$P$$ is interpreted with $$<$$, $$Q$$ is interpreted as "$$n$$ is prime", $$f$$ is the successor function, $$g$$ is sum, and where $$I_{\mathcal A}(a) = a^{\mathcal A} = 2$$ and $$I_{\mathcal A}(z) = z^{\mathcal A} = 3$$], $$F$$ is obviously "true", because every natural number is smaller than its successor, and the sum of $$2$$ and $$3$$ is a prime number.

Of course, for this formula $$F$$ one can also define suitable structures in which $$F$$ is "false". That is, $$F$$ is not a valid formula.

As you can see, the difference is only of terminology.