Predicates

Peter Susanszky

Predicates

Predicates in logic are used to express properties of objects or relations between them. Again, properties and relations are meant here in a very loose sense, and their representation, in set theory, is very minimal in detail.

Predicates of 1-place

Suppose you want your

$1$

-place predicate

$\mathfrak{P}^{1}_{1}$

in

$\mathcal{L}_0$

to express the property ‘is a physicist’. We already introduced the concept of a domain of discourse, or domain,

$\mathbf{D}$

about which our language should be about. So given our domain, how do we capture that

$\mathfrak{P}^{1}_{1}$

should have the meaning ‘is a physicist’? Well, we can specify a subset of the domain

$\mathbf{D}$

, let’s call it

$\mathbf{P}$

, which consists of just the physicists in our domain. In set-builder notation, we can say:

$\mathbf{P}=\{x\mid x\in \mathbf{D} \text{ and } x \text{ is a physicist}\}$ $\mathbf{P}$

here is a subset of the domain

$\mathbf{D}$

, since by definition, every

$x \in \mathbf{P}$

is also in

$\mathbf{D}$

. Moreover, it only includes those members of the domain that are physicists. That is, the set of physicists in the domain. This may be called the property ‘is a physicist’, as we noted in the last chapter. Then, we can use the interpretation function to connect our

$1$

-place predicate to the property (subset of the domain).

Again, represented in a figure:

$1$ -place predicates	$\mapsto$	Subsets of Domain (properties)
$1$ -place predicate	$\mapsto$	set of things

And in particular:

$1$ -place predicates	$\mapsto$	Subsets of Domain (properties)
$\mathfrak{P}^{1}_{1}$	$\mapsto$	$\mathbf{P}$ (‘is a physicist’)

Again, the meaning of our predicates can be anything, as long as it is a property in the domain, that is, a subset of things of the domain. For example, it can be the set of things (of the domain

$\mathbf{D}$

) that are singers (the property of being a singer), the set of things that are numbers (the property of being a number), the set of things that are world wars (the property of being a world war), and so on. You can even have properties that only have one member, like ‘is the first female artist with four Top 10 albums at once’.

$1$ -place predicates	$\mapsto$	Subsets of Domain (properties)
$\mathfrak{P}^{1}_{1}$	$\mapsto$	$\mathbf{P}$ (‘is a physicist’)
$\mathfrak{P}^{1}_{2}$	$\mapsto$	$\mathbf{S}$ (‘is a singer’)
$\mathfrak{P}^{1}_{3}$	$\mapsto$	$\mathbf{N}$ (‘is a number’)
$\mathfrak{P}^{1}_{4}$	$\mapsto$	$\mathbf{W}$ (‘is a world war’)
	$\vdots$

Predicates of 2-places

The above approach takes care of our

$1$

-place predicates. But predicates can come with more places (the superscript for

$\mathfrak{P}$

). Suppose you want to assign meaning to a

$2$

-place predicate

$\mathfrak{P}^{2}_{1}$

, and in particular, you want it to mean ‘

$x$

loves

$y$

’. Here, a set will not do, since we want to capture a relation, not a property. In particular we want to capture that a person is in the relation of loving another person (or thing in general).

If you think back to our discussion of set theory, you already know how to do this. Instead of a set of objects, you can take a set of pairs here, that represents two objects of the domain standing in the loving relation. Once again, we may introduce a relation

$\mathbf{L}$

on the domain, and specify it as such:

$\mathbf{L}=\{\langle x, y\rangle \mid x,y \in \mathbf{D} \text{ and } x\text{ loves }y\}$

So

$\mathbf{L}$

here is the set of pairs such that the first member of each pair loves the second member of that pair. So if our domain includes Julie and Jane, and Julie loves Jane, but Jane does not love Julie, we would have that

$\langle Julie, Jane\rangle \in \mathbf{L}$

, but

$\langle Jane, Julie\rangle \notin \mathbf{L}$

. So again:

2

-place predicates

\mapsto

Sets of Pairs of Domain (

$2$ -place relations)

2

-place predicate

\mapsto

pairs of things

And in particular:

2

-place predicates

\mapsto

Sets of Pairs of Domain (

$2$ -place relations)

\mathfrak{P}^{2}_{1}

\mapsto

\mathbf{L}

(‘loves’)

Again, you can introduce whatever relation you want here, as long as it can be represented by a set of pairs of members of the domain. For example, ‘is the favorite number of’, ‘is a sibling of’, ‘stands 2 feet to the right of’, and so on. That is:

$2$ -place predicates	$\mapsto$	Sets of Pairs of Domain ( $2$ -place relations)
$\mathfrak{P}^{2}_{1}$	$\mapsto$	$\mathbf{L}$ (‘loves’)
$\mathfrak{P}^{2}_{2}$	$\mapsto$	$\mathbf{F}$ (‘is the favorite number of’)
$\mathfrak{P}^{2}_{3}$	$\mapsto$	$\mathbf{B}$ (‘is a sibling of’)
$\mathfrak{P}^{2}_{4}$	$\mapsto$	$\mathbf{R}$ (‘stands 2 feet to the right of’)

In each case,

$\mathbf{L}$

,

$\mathbf{F}$

,

$\mathbf{B}$

,

$\mathbf{R}$

are just sets of pairs representing all pairs of members of the domain that are in the specified relation.

Notice that each member of these binary relations have, either on the left or the right side, a member of

$\mathbf{D}$

, the domain. By the Cartesian product of

$\mathbf{D}$

with itself once, i.e.,

$\mathbf{D} \times \mathbf{D}$

or

$\mathbf{D}^2$

, we can get the set of all pairs of members of

$\mathbf{D}$

. Now relations on

$\mathbf{D}$

will be subsets of

$\mathbf{D}^2$

, since each will be either the universal relation on

$\mathbf{D}$

, the empty set, or somewhere in between. In the above example,

$\langle Julie, Jane\rangle \in \mathbf{L}$

, but

$\langle Jane, Julie\rangle \notin \mathbf{L}$

, so

$\mathbf{L}$

is a non-empty proper subset of

$\mathbf{D}^2$

.

Note that it is very important to be clear about the directionality of a relation. For example, we may have a predicate with assigned meaning ‘loves’. But we may also have a predicate with assigned meaning ‘is loved by’. Now, if the relation

$\mathbf{L}$

is the relation ‘loves’, and

$\mathbf{L}'$

is the relation ‘is loved by’, then each pair will be reversed relative to the other one. For example, if

$\langle Julie, Jane\rangle \in \mathbf{L}$

, but

$\langle Jane, Julie\rangle \notin \mathbf{L}$

, then

$\langle Julie, Jane\rangle \notin \mathbf{L}'$

, but

$\langle Jane, Julie\rangle \in \mathbf{L}$

, since

$x$

loves

$y$

if, and only if,

$y$

is loved by

$x$

. That is, if Julie loves Jane but Jane does not love Julie, then Jane is loved by Julie but Julie is not loved by Jane.

Predicates of n-places

You may see a pattern here. Predicates of

$1$

-place (unary predicates) were interpreted as sets. Predicates of

$2$

-places (binary predicates) were interpreted as

$2$

-place relations. But of course, our language has predicates of every arity (every number of ‘place’), and to each, we may want to attribute some meaning. Well, this is not hard to do, since for any

$n$

-place predicate, we can assign an

$n$

-place relation. The important thing is just that if a predicate is of form

$\mathfrak{P}^{n}_{k}$

, then its meaning must agree with

$n$

, so it has to be a set of

$n$

-tuples.

Exercise 4.2. Give a natural example of a

$3$ -place,

$4$ -place, and

$5$ -place relation.

If you need a refresher on relations in logic, go back to the chapter on ordered sets and relations.

Following our handy figure, we have:

n

-place predicates

\mapsto

Sets of

$n$ -tuples of Domain (

$n$ -place relations)

n

-place predicate

\mapsto

set of

$n$ -tuples (

$n$ -place relation)

Making it a bit more concrete, but still quite abstract, we have:

$n$ -place predicates	$\mapsto$	Sets of $n$ -tuples of Domain ( $n$ -place relations)
$\mathfrak{P}^{1}_{1}$	$\mapsto$	$\mathbf{R}_1 \subseteq \mathbf{D}$
	$\vdots$
$\mathfrak{P}^{2}_{1}$	$\mapsto$	$\mathbf{R}_i \subseteq \mathbf{D}^2$
	$\vdots$
$\mathfrak{P}^{n}_{1}$	$\mapsto$	$\mathbf{R}_k \subseteq \mathbf{D}^n$
	$\vdots$

We can then extend our interpretation function

$\mathbf{I}$

to cover now not only constants, but predicates as well.

Definition 4.2. A domain (of discourse) is any set

$\mathbf{D}$ . An interpretation function for the predicates of

$\mathcal{L}_0$ , denoted by

$\mathsf{PRED}_{\mathcal{L}_0}$ , (relative to

$\mathbf{D}$ ) is a function

$\mathbf{I}$ such that for each predicate

$\mathfrak{P}^{n}_{k}$ ,

$\mathbf{I}(\mathfrak{P}^{n}_{k})=\mathbf{R}$ for some

$\mathbf{R} \subseteq \mathbf{D}^n$ (the Cartesian product of

$\mathbf{D}$ taken

$n$ -times with itself).

In fact, we can put together our definition of an interpretation function for constants, and our definition of an interpretation function for predicates, into one definition. We can also introduce a new notion; structure. Structure is just a shorthand for what we have been saying over and over again; that when giving meaning to our expressions, we do it with an interpretation function

$\mathbf{I}$

against the backdrop of a domain

$\mathbf{D}$

. So a structure

$\mathbf{S}$

is just a pair

$\langle\mathbf{D}, \mathbf{I}\rangle$

where

$\mathbf{D}$

is the domain, and

$\mathbf{I}$

is the interpretation function under consideration. With this in hand, we can say:

Definition 4.3. A structure

$\mathbf{S}$ is a pair

$\langle\mathbf{D}, \mathbf{I}\rangle$ , where

$\mathbf{D}$ is any set, and

$\mathbf{I}$ is a function from the constants and predicates of

$\mathcal{L}_0$ (i.e.,

$\mathsf{CON}_{\mathcal{L}_0} \cup \mathsf{PRED}_{\mathcal{L}_0}$ ) such that:

if
$c$ is any constant of

$\mathcal{L}_0$ ,

$\mathbf{I}(c) \in \mathbf{D}$ , and;
if
$P^n$ is any predicate of arity

$n$ (

$n$ -place predicate) of

$\mathcal{L}_0$ ,

$\mathbf{I}(P^n)=\mathbf{R}$ , where

$\mathbf{R} \subseteq \mathbf{D}^n$ .

As you can see, logicians can say a lot of stuff in very few words. This may seem intimidating at first. But remember that all these terse definitions hide quite intuitive ideas. We spent some time pondering these ideas so that you can read and understand the definition above, and the nuances and niceties it expresses so elegantly. This also gives you a very important skill: to go further. In more advanced logic textbooks, you won’t find such long explanations as we have given. But now you won’t need them either!³

A brief return to our language specification

Indeed, now that we are familiar with a lot more machinery than before, we can give a definition of our language in a manner that is a lot more succint.

Definition 4.4. Let

$\mathsf{ALPH}_{\mathcal{L}_0}$ be the alphabet of

$\mathcal{L}_0$ , specified as before, and thought of as forming a set. In particular, let

$\mathsf{PRED}_{\mathcal{L}_0} \subseteq \mathsf{ALPH}_{\mathcal{L}_0}$ and

$\mathsf{CONS}_{\mathcal{L}_0} \subseteq \mathsf{ALPH}_{\mathcal{L}_0}$ , and such that:

$\mathsf{CONS}_{\mathcal{L}_0}=\{\mathfrak{c}_{n} \mid n \in \mathbb{N}\}$
, and;
$\mathsf{PRED}_{\mathcal{L}_0}=\{\mathfrak{P}^{n}_{k} \mid n, k \in \mathbb{N}\}$
.

The set of (well-formed) formulas of

$\mathcal{L}_0$ is the smallest set

$\mathsf{FORM}_{\mathcal{L}_0}$ such that:

if
$P$ is a predicate of arity

$n$ in

$\mathsf{PRED}_{\mathcal{L}_0}$ , and

$c_1, c_2, ..., c_n$ are (not necessarily distinct) constants in

$\mathsf{CONS}_{\mathcal{L}_0}$ , then

$P(c_1, ..., c_n) \in \mathsf{FORM}_{\mathcal{L}_0}$ , and is an atomic formula;
if
$X$ and

$Y$ are in

$\mathsf{FORM}_{\mathcal{L}_0}$ , then:
1. $\neg X \in \mathsf{FORM}_{\mathcal{L}_0}$
  ;
2. $(X \wedge Y) \in \mathsf{FORM}_{\mathcal{L}_0}$
  ;
3. $(X \vee Y) \in \mathsf{FORM}_{\mathcal{L}_0}$
  ; and
4. $(X \rightarrow Y) \in \mathsf{FORM}_{\mathcal{L}_0}$
  .

Again, a few weeks ago, this may have seemed extremely cryptic and impossible to comprehend, but now you are familar with all the different ideas underlying this definition, and can understand its intended meaning.

In fact, when I was studying philosophy as an undergrad, I was reading papers from Russell, Quine, and others, and I really wanted to understand what they were saying. So I went and bought myself a book on semantics. I opened up the first page, and definitions not unlike 4.4 and 4.3 greeted me. Unlike you, I did not have a textbook like this, so I had no idea what was going on. Needless to say, my foray into semantics stopped right there, and did not continue for a few years.

License

Icon for the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

Predicates of 1-place

Predicates of 2-places

Predicates of n-places

A brief return to our language specification

License

Share This Book