Predicates - Mathematical Sentences

Mathematical Writing - Vivaldi Franco 2014

Predicates
Mathematical Sentences

The sentence

The integer $$x$$ is divisible by 7

contains an unspecified symbol, and thus it assumes a logical value only if the symbol is assigned an integer value. We are prompted to introduce the following function:

$$\begin{aligned} {\fancyscript{P}}:\mathbb {Z}\rightarrow \{{\textsc {t}},{\textsc {f}}\}\qquad x\mapsto 7\mid x. \end{aligned}$$

(4.14)

We see that $${\fancyscript{P}}(x)$$ is the symbolic translation of our sentence, and that $${\fancyscript{P}}(22)={\textsc {f}}$$, $${\fancyscript{P}}(-91)={\textsc {t}}$$.

Using a function to encode a sentence is a simple idea with far-reaching consequences. Let us thus define a predicate (or boolean function) to be any function that assumes boolean values. If the domain of a predicate $${\fancyscript{P}}$$ is $$X$$, then we speak of a predicate on (or over) $$X$$. So (4.14) is a predicate on the integers.

Let $${\fancyscript{P}}:X\rightarrow \{{\textsc {t}},{\textsc {f}}\}$$ be a predicate on $$X$$. There is a distinguished subset $$A_{\fancyscript{P}}$$ of $$X$$, determined by $${\fancyscript{P}}$$ via the following Zermelo definition:

$$\begin{aligned} A_{\fancyscript{P}}:=\{x\in X\,:\,{\fancyscript{P}}(x)\}. \end{aligned}$$

(4.15)

With reference to Eq. (2.9) and the discussion that follows, we see that the expression $${\fancyscript{P}}(x)$$, which means ’$$x$$ has property $$P$$’, is the definiens of the set $$A_{\fancyscript{P}}$$. So the Zermelo definition (4.15) may be expressed in the language of functions using an inverse image:

$$ \{x\in X\,:\,{\fancyscript{P}}(x)\}\mathop {=}\limits ^\mathrm{def}{\fancyscript{P}}^{-1}(\{{\textsc {t}}\}) $$

[cf. Definition (2.20)].

Conversely, let $$X$$ be a set and let $$A$$ be a subset of $$X$$. The predicate

$$\begin{aligned} {\fancyscript{P}}_A:X\rightarrow \{{\textsc {t}},{\textsc {f}}\}\quad \qquad x\mapsto x\in A \end{aligned}$$

(4.16)

is called the characteristic function of $$A$$ (in $$X$$). Explicitly, $${\fancyscript{P}}(x)$$ is equal to $${\textsc {t}}$$ if $$x$$ belongs to $$A$$ and to F otherwise. For example, the function (4.14) is the characteristic function of the set $$7\mathbb {Z}$$ of integer multiples of 7.

So to every predicate on a set $$X$$ we associate a unique subset of $$X$$, and vice-versa. We say that there is a bi-unique correspondence between these two classes of objects, established by expressions (4.15) and (4.16).

Sets are manipulated using set operators. Predicates are manipulated using boolean operators in a natural way by defining, say,

$$ (\fancyscript{P}\wedge \fancyscript{Q})(x) \mathop {=}\limits ^\mathrm{def} \fancyscript{P}(x)\wedge \fancyscript{Q}(x) $$

and similarly for all other operators. The following theorem establishes correspondences between these two classes of objects.

Theorem 4.2

Let $$X$$ be a set, let $$A,B\subseteq X$$, and let $${\fancyscript{P}}_A$$, $${\fancyscript{P}}_B$$ be the corresponding characteristic functions. The following holds (the prime denotes taking the complement):

(This baroque display of symbols is unappealing. In Sect. 6.6 we’ll make it more digestible by writing a short essay about it without symbols.)

PROOF. To prove (i) we note that the function $$x\mapsto \lnot {\fancyscript{P}}_A(x)$$ evaluates to TRUE if $$x\not \in A$$ and to FALSE otherwise. However, from the definition of the complement of a set, we have $$x\not \in A \Leftrightarrow x\in A^\prime $$.

Next we prove (iv). We’ll prove instead

$$ \lnot ({\fancyscript{P}}_A\Rightarrow {\fancyscript{P}}_B)\, =\, {\fancyscript{P}}_{(A{\backslash }B)} $$

which, together with (i), gives us (iv). Let $${\fancyscript{P}}_A:=(x\in A)$$ and let $${\fancyscript{P}}_B:=(x\in B)$$. From the truth table (4.9) of the operator $$\Rightarrow $$, we find that $$\lnot ({\fancyscript{P}}_A\Rightarrow {\fancyscript{P}}_B)(x)$$ is TRUE precisely when $${\fancyscript{P}}_A(x)$$ is TRUE and $${\fancyscript{P}}_B(x)$$ is FALSE. This means that

$$ (x\in A) \wedge (x\not \in B), $$

but this is just the definition of the characteristic function of the set $$A{\backslash }B$$, as desired.

The proof of (ii), (iii), (v) is left as an exercise. $$\square $$

We illustrate the significance of this theorem with examples.

EXAMPLE. Let $$a$$ and $$b$$ be real numbers. The predicates $$x\mapsto (x\geqslant a)$$ and $$x\mapsto (x< b)$$ (over $$\mathbb {R}$$) are the characteristic functions of two rays, the latter without end-point. According to Theorem 4.2 part (ii), the predicate $$x\mapsto ((x\geqslant a)\, \wedge \,(x< b))$$ is the characteristic function of the intersection of these rays. Depending on whether $$a<b$$, or $$a\geqslant b$$, this intersection is the half-open interval $$[a,b)$$ or the empty set.

EXAMPLE. Let $$X,Y$$ be sets, and let $$f,g:X\rightarrow Y$$ be functions. An equation (on $$X$$) is a predicate of the type

$$ {\fancyscript{P}}:X\rightarrow \{{\textsc {t}},{\textsc {f}}\}\qquad x\mapsto (\,f(x)=g(x)). $$

In the language of predicates, an equation is the characteristic function of its own solution set $$\{x\in X\,:\,{\fancyscript{P}}(x)\}$$ (Sect. 3.3). The system of two equations

$$ f_1(x)=g_1(x) \qquad f_2(x)=g_2(x) $$

defined over the same set corresponds to the predicate $$x\mapsto {\fancyscript{P}}_1(x)\wedge {\fancyscript{P}}_2(x)$$. From Theorem 4.2, part (ii), it follows that the solution set of a system of two equations is the intersection of the solution sets of the individual equations. The same holds for any number of equations—see (3.19).

EXAMPLE. The standard form of the sigma-notation (see Sect. 3.2) has the following syntax:

$$\begin{aligned} \sum _{{\fancyscript{P}}(k)}a_{k} \end{aligned}$$

(4.17)

where $${\fancyscript{P}}$$ is any predicate over $$\mathbb {Z}$$. The range of summation consists of those values of $$k$$ for which $${\fancyscript{P}}(k)$$ is TRUE.

EXAMPLE. If $$A\subset B$$, then $$A{\backslash }B$$ is empty, and from part (iv) of the theorem we obtain

$$ ({\fancyscript{P}}_A\Rightarrow {\fancyscript{P}}_B)\,=\,{\fancyscript{P}}_{\emptyset ^\prime }={\fancyscript{P}}_X. $$

The subset relation has been translated into an identity of functions. For example, the functional identity

$$ ({\fancyscript{P}}_{4\mathbb {Z}}\Rightarrow {\fancyscript{P}}_{2\mathbb {Z}})\,=\,{\fancyscript{P}}_{\mathbb {Z}} $$

says that every multiple of four is even.