Trouble in understanding Predicate logic semantics

Question

I am studying predicate logic and I have a problem understanding its semantics. I am reading "Logic for computer scientists" by Uwe Schoning and the passage I have a problem with is this:

If $F$ has the form $F=P(t_1,\dots,t_k)$ where $t_1\dots t_k$ are terms and $P$ is a predicate symbol of arity $k$, then its semantics are defined by $$\mathcal{A}(F) =\begin{cases}1& \text{ if } (\mathcal{A}(t_1),\dots,\mathcal{A}(t_k)\in P^{\mathcal{A}}\\ 0& \text{ otherwise}\end{cases}$$

Here $\mathcal{A}$ is a structure and $P^{\mathcal{A}} = I_{\mathcal{A}(P)}$ is described as below: Predicate logic structure pair

I think I kinda get what structure is about, my problem is about the first picture. I didn't get what does it mean. Does it mean that if we had a predicate symbol, the value of that predicate symbol is true if all its terms are defined by that structure? If so then if for example we have $P^2(x,f(x))$ and both $x$ and $f(x)$ are defined then $P$ is true regardless? That doesn't seem right!

I tried googling and reading other documents but it confused me more. I'll be happy if someone explains the predicate logic semantics to me in a clear and simple way with a few examples. Thanks in advance

Answer 1

$\newcommand\A{\mathcal{A}}$ Admittedly, the usage of the symbol $\mathcal{A}$ both standing alone as a structure and in function notation to denote the value of an expression in that structure is confusing.

$\A(\Box)$ (where $\Box$ is some expression -- a term or a formula) does not mean that $\Box$ is defined in $\A$ at all (it has to be in order to be evaluate the expression at all), but it stands for the value of the expression $\Box$ in $\A$.

$$\mathcal{A}(F) =\begin{cases}1& \text{ if } (\mathcal{A}(t_1),\dots,\mathcal{A}(t_k)) \in P^{\mathcal{A}}\\ 0& \text{ otherwise}\end{cases}$$

means that the value of the atomic formula $F := P(t_1, \ldots, t_n)$ is $1$ iff the tuple consisting of the values of the terms $t_1$ to $t_k$ in the structure $\A$ is an element of the interpretation of the predicate $P$.

Those values $\A(\Box)$ are what is defined inductively in the clauses 1. - 2. + 1. - 6. on p. 46-47.

The value of a term is an object in the universe, and the interpretation of an $n$-place predicate symbol is a set of $n$-tuples of objects from the universe. So checking the value of an atomic formula comes down to checking if the tuple of objects that the terms denote is among the tuples of objects that $P$ is defined to be true of.
A $1$-tuple can simply be identified with its only object: $(a) = a$, so the interpretation of a $1$-place predicate like $\mathrm{prime}$ can be said to be a set of individual objects rather than a set of "$1$-tuples".

Take the example on p. 45, and restrict yourself subformula $Q(g(a,z))$ for the moment:

By a stepwise evaluation recursing down the definitions of $\A(\Box)$, we get that

$ \A(Q(g(a,z)) = 1\\ \Leftrightarrow \underbrace{(\A(g(a,z))) \in Q^\A}_{\text{def. } \A(P(t_1, \ldots, t_k))}\\ \Leftrightarrow \underbrace{g^\A(\A(a), \A(z))}_{\text{def. } \A(f(t_1, \ldots, t_k))} \in Q^\A\\ \Leftrightarrow g^\A(\underbrace{a^\A}_{\text{def. } \A(f(t_1, \ldots, t_k))}, \underbrace{z^\A}_{\text{def. } \A(x)}) \in Q^\A\\ \Leftrightarrow \underbrace{+}_{\text{def. } I_\A(g)} (\underbrace{2}_{\text{def. } I_\A(a)}, \underbrace{3}_{\text{def. } I_\A(z)}) \in \underbrace{\{n \in U_\A : n \text{ is prime }\}}_{\text{def. } I_\A(Q)}\\ \Leftrightarrow \underbrace{5}_{\text{def. } + } \in \{n \in \underbrace{\mathbb{N}}_{\text{def. } U_\A} : n \text{ is prime }\}\\ \text{Since 5 is prime, } \A(Q(g(a,z)) = 1. $

Answer 2

As per the linked definitions, a structure $\mathcal A$ is made of a domain $U$ of "objects" (like e.g. numbers) and an interpretation $I$, i.e. a function that maps terms and predicates of the languages to objects and subsets of the domain.

Intuitively, terms are "names" for objects.

An unary predicate $P$ (intuitively: a property of objects) is mapped by the interpretation to a subset of the domain, i.e. to the subset of the domain of all and only those objects for which $P$ holds.

Finally, formulas are evaluated true or false according to the interpretation of terms and predicates occuring in them.

This is the gist of the above definition:

$\mathcal A(F) = 1 \text { iff } (\mathcal A(t_1),\ldots,A(t_k)) \in P^{\mathcal A}$.

Consider a simple example with domain the set $\mathbb N$ of natural numbers.

Let $t$ a term, $P$ an unary predicate and consider a structure $\mathcal A =(\mathbb N, I)$ such that: $t^{\mathcal A}=2 \in \mathbb N$ and $P^{\mathcal A} = \{ n \mid n \text { is even } \} \subseteq \mathbb N$.

Thus $P(t)^{\mathcal A}=1$, because $2$ is even, and $(\forall n P(n))^{\mathcal A}=0$.

---

What happens when terms and formulas have free variables?

Here we need the third clause of the definition of interpretation: it provides a reference to every variable.

Thus, according to the previous example, let $I$ such that $x^I=2$ and consider the term $t := x+1$.

Now $t^{\mathcal A}$ will be $3$ and thus $P(t)^{\mathcal A}=0$.