Difficulty in understanding predicate symbols in FOL

Question

I'm a beginner in First-Order Logic, and I have the following difficulty in understanding predicate symbols:

From what I know, $n$-ary predicate symbols, are represented by $p_i^n$. If $x$ is a variable, what does $p^1x$ really mean? The $1$ in the superscript simply denotes that $p$ is unary. I know that functions $f_i^n$ applied to terms return a value, i.e. another term $f^nt_1t_2...t_n$. What does $p^1x$ return? True or False, possibly?

I have an example in mind! Consider the binary predicate symbol $<$, and the wff $2 < 1$. This returns False, but is it always the case that predicate symbols return True/False? I'm not quite sure about the definition.

In addition, I was told that given an interpretation $\mathcal{I}$ and a domain of discourse $\mathcal{D}$, each predicate symbol $p_i^n$ is mapped to an $n$-ary relation, i.e. $\mathcal{I}(p_i^n) \subseteq D^n$. Could someone please give an example for this? In the example that I took above for the binary predicate $p^2$ = $<$, $\mathcal{D} = \mathbb{N}$, $<$ seems to be the following map - $<:\mathbb{N}\times \mathbb{N} \to \{T,F\}$ which doesn't seem like $\mathcal{I}(p_i^n) \subseteq D^n$. Where am I going wrong? Could someone please help me better understand these concepts? Thank you!

Answer 1

Re: the "set vs. function" issue: these are really two different ways to phrase the same thing.

There is a natural way to identify a map $f$ from a set $X$ to $\{True,False\}$ with a subset $Set_f$ of $X$: namely, we use $$Set_f=\{x: f(x)=True\}.$$ Note that this is "dual" to the Boolean version of the characteristic function of a set, that is, the assignment to a set $A\subseteq X$ of the function $$Func_A: x\mapsto\begin{cases} True & \mbox{ if }x\in A,\\ False & \mbox{ if }x\not\in A.\\ \end{cases}$$ In fact, you should check that in fact we always have $$Set_{Func_A}=A\quad\mbox{and}\quad Func_{Set_f}=f,$$ so these are literally inverse constructions.

Similarly, we can equivocate between $n$-ary relations on $X$ (= subsets of $X^n$) and $n$-ary Boolean functions on $X$ (= maps from $X^n$ to $\{True,False\}$). This should explain how e.g. "$<$" can be thought of both as a set of ordered pairs and as a function which takes in a pair of inputs and spits out either "True" or "False." The former approach tends to be used more for whatever reason, but per the above they're really equivalent in an explicit way.

---

This takes us to the question of how to interpret expressions with free variables. Let's think about terms first. If I have a unary function symbol $f^1$ and a variable $x$, "$f^1x$" is a term. But this term isn't "determined" yet in a sense: even after I specify a structure (and so in particular an interpretation of $f$), I haven't given a value for the variable $x$. So this shouldn't be thought of as referring to a definite object. Rather:

The term "$f^1x$" describes a way of taking a structure $(D,\mathcal{I})$ and a variable assignment $\nu$ for that structure and outputting an element of the domain $D$ of that structure.

It may help to consider a slightly less trivial example, say the term "$g^2xx$" where $g^2$ is a binary function symbol. This (unlike the above example) isn't just a function symbol "repackaged," I'm doing something interesting to the inputs.

Of course an individual term doesn't actually "use" the entirety of any variable assignment; e.g. "$f^1x$" only cares about what gets assigned to $x$. So really we should be a bit more parsimonious:

A term with some free variables corresponds, given a structure $(D,\mathcal{I})$, to a function $D^n\rightarrow D$ where $n$ is the number of free variables occurring in that term.

(There's some nuance here, but I'd ignore that at first.)

Predicates - or more generally, formulas (possibly with free variables) - will behave the same way:

Given a structure $(D,\mathcal{I})$, a formula $\varphi$ describes a subset of $D^n$ where $n$ is the number of free variables occurring in $\varphi$ - or, per the start of this answer, it describes a map $D^n\rightarrow\{True,False\}$.

Answer 2

If $x$ is a variable, what does $p^1x$ really mean?

As you say, $p^1$ is a unary predicate, i.e. a predicate with one argument-place.

Predicate symbols are syntactical objects, i.e. part of the formal language.

They are the formal counterpart of natural language predicates, like e.g. "... is a Philosopher".

Thus, the natural way to read $p(x)$ is: "$x$ is a $p$".

When we apply a unary predicate to a closed term (a "name") we get a meaningful statement, like: "Socrates is a Philosopher" (that has the form $\text {Phil}(\text {Socrates})$).

You example with $<$ as $p^2$ is correct.

If we use an interpretation $\mathfrak I$ with domain $\mathbb N$ and we interpret the binary predicate $p^2$ as $<$ we will have:

$(p^2)^{\mathfrak I} = \{ (n,m) \mid n,m \in \mathbb N \text { and } n < m \}$.

Thus, we have that $(p^2)^{\mathfrak I} \subseteq \mathbb N \times \mathbb N$ and we have that:

$p^2(x,y)[x/n,y/m]$ is True in $\mathfrak I$ iff $n < m$.

Answer 3

$\newcommand{\sem}[1]{[\![#1]\!]^{(\mathcal{D}, \mathcal{I}), v} } \newcommand{\semI}[1]{[\![#1]\!]^{(\mathcal{D}, \mathcal{I}), v'} } \newcommand{\tpl}[1]{\langle #1 \rangle}$

We can write "$\sem{\cdot}$" to mean "the semantic value of the string of symbols $\cdot$ in the model with domain $\mathcal{D}$, interpretation $\mathcal{I}$ and variable assignment $\mathcal{v}$".
The semantic value of a term (= a variable like $x$, an individual constant like $0$, or a function symbol applied to a matching number of arguments like $5 + 4$) will be an object from the domain.
The semantic value of a formula (= a predicate applied to a matching number of arguments like $2 < 1$, or a complex formula involving connectives and quantifiers like $\forall x (x > 0 \to even(x))$) will be a truth value.

So your guess is correct: An $n$-ary predicate symbol applied to an appropriate number of arguments returns a truth value. This follows from the definition of the semantics of FOL:

If $P$ is an $n$-ary predicate symbol and $t_1, \ldots, t_n$ are terms, then $\sem{P(t_1, \ldots t_n)}= \begin{cases} \text{True} & \text{iff} \langle \sem{t_1}, \ldots, \sem{t_n} \rangle \in \sem{P}\\ \text{False} & \text{otherwise} \end{cases}$

The semantic value of non-logical symbols (= individual constants, function symbols and predicate symbols) is determined by the interpretation function; and indeed, the interpretation of an $n$-ary predicate symbol is an $n$-ary relation on $\mathcal{D}$:

If $c$ is a constant symbol, then $\sem{c} = \mathcal{I}(c) \in \mathcal{D}$
If $f$ is an $n$-ary function symbol, then $\sem{f} = \mathcal{I}(f) : \mathcal{D}^n \to \mathcal{D}$
If $P$ is an $n$-ary predicate symbol, then $\sem{P} = \mathcal{I}(P) \subseteq \mathcal{D}^n$

A reasonable interpretation for the languge in your example would be

$\mathcal{D} = \mathbb{N}\\ \mathcal{I}(0) = 0, \mathcal{I}(1) = 1, \ldots\\ \mathcal{I}(<) = \{\tpl{x, y} \in \mathbb{N} \times \mathbb{N}: x < y\} = \{\tpl{0, 1}, \tpl{0, 2}, \ldots, \tpl{1, 2}, \tpl {1, 3}, \ldots\}$

We then have

$\sem{2 < 1} = \text{True}\\ \Longleftrightarrow \tpl{\sem{2}, \sem{1}} \in \sem{P}\\ \Longleftrightarrow \tpl{\mathcal{I}(2), \mathcal{I}(1)} \in \mathcal{I}(P)\\ \Longleftrightarrow\ \tpl{2, 1} \in \{\tpl{x,y}: x < y\}\\ \text{Since} \tpl{2, 1} \not \in \{\tpl{x,y}: x < y\},\\ \sem{2 < 1}= \text{False}$

One could say that interpretation of an $n$-ary predicate symbol itself is an $n$-ary relation on the domain, and the process of evaluating an atomic formula, i.e. a predicate occurring together with an argument vector, consists of implicitly forming its characteristic function (see Noah Schweber's post) to combine the interpretation of the predicate symbol as a set and the interpretation of its arguments as objects into a truth value; this is what happens in the definition of $\sem{P(t_1, \ldots t_n)}$ above.

---

If $x$ is a variable, what does $p^1x$ really mean?

Variables are like pronouns: $p^1x$ means "It is $P$", or "This is $P$". To make sense of variables, we need an assignment function, which maps variables to objects in the domain:

$v: VAR \to \mathcal{D}$
If $x$ is a variable, then $\sem{x} = v(x) \in \mathcal{D}$

A variable assignment is a way of pointing at objects: By fixing e.g. $v: x \mapsto 1$, I am pointing with my finger at the object $x$, thereby giving a meaning to the pronoun "it". Without specifying an assignment, i.e. pointing at an object, we can not make sense of the pronoun.
We often have to deal with more than one variable, but luckily I also have more than one finger: The assignment $v : x \mapsto 1, y \mapsto 0$ could mean that with my left index finger which I'm using when saying "this" I'm pointing at 1 and with my right hand which I use for "that" I'm pointing at 0. Under this particular assignment, the formula $x < y$, "This is smaller than that" means that 1 is smaller than 0, so $\sem{x < y}$ comes out as false; under another assignment where I point $v': x \mapsto 3, y \mapsto 5$, it means that 3 is smaller than 5, and $\semI{x < y}$ = True.
Usually variables occur in the scope of quantifiers. $\forall x (x > 0 \to even(x))$ means "Every way of pointing at an object makes the proposition "If this is larger than 0, then it is even" true". Likewise, $\exists x (x > 0 \land even(x))$ means "I can find a way of pointing at an object so that the proposition "This object is larger than 0 and even" true." The semantics of the quantifers $\forall, \exists$ is to loop over variable assignments, i.e. ways of pointing at things.
$\sem{P(x)}$ then means "$P$ holds of the object $x$", whatever it is that $v$ tells us $x$ refers to: $\sem{P(x)} = \text{True iff } v(x) \in \mathcal{I}(P)$.