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!
Best Answer
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:
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:
(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: