Predicates

A predicate in English is everything except the subject in a declarative sentence. For example, if we take the sentence:

Smith is more than six feet tall.

The statement “is more than six feet tall” is a predicate. It does not become a complete sentence until we specify a subject. Once we have identified a subject, this declarative sentence might or might not be true. Therefore, a predicate describes a property that a subject may or may not possess.

Luckily, in mathematics, we can use variables to denote unspecified subjects. Using variables becomes a powerful way of expressing many ideas precisely: this is the basis of first-order logic. As we’ll see, this logic is so powerful that we can state several open problems in mathematics (and other areas) using first-order logic.

What is a predicate?

In mathematical logic, predicates are propositions containing one or more variables. We can view these variables as placeholders. These variables are allowed to take any value from a set called their domain. The predicate asserts some property the elements of the domain may or may not possess. For a statement to qualify as a bona fide predicate, the predicate must become a proposition each time we substitute any value from the domain.

To see a concrete example, consider three students, Jane, Jim, and Zain, who took a discrete maths course. Let’s assume we want to know which students have secured an A in the course. We can craft the following sentence with a variable $x$:

• $A(x)$: $x$ has secured an A in discrete math.

The statement “has secured an A in discrete math” is a predicate. The variable $x$ allows us to use this predicate in a complete sentence. $A(x)$ is not a proposition because it has a variable. But if we substitute $x$ with some specific value, that is, the name of a student in the class, it will become a proposition. It will have a definite truth value. In this case, we say that we are instantiating the predicate. What is important is that each instantiation of the variable from the domain should yield a proposition.

The domain should always be clear. If there is any possible ambiguity, we must mention the domain explicitly. For the $A(x)$, the domain of $x$ is the students registered in the discrete maths class. To be concrete, let’s define the domain to be $D = \{$ Jim, Jane, Zain $\}.$

We can instantiate this predicate by substituting a value for $x$ for any value from $D$. Instantiating $A(x)$ will turn it into a proposition with a definite truth value. For example, when we substitute Jim for $x$, we get the proposition,

• $A($Jim$)$: Jim has secured an A in discrete math.

We can also visualize a predicate as a row of truth values. The columns are labeled values given in the domain. So, for example, if Jim is the only student who did not get an $A$ in the course, then $A($Jane$)$ = true, $A($Jim$)$ = false, $A($Zain$)$ = true, we can view $A(x)$ as the following table:

In this table, T represents true and F represents false.

Let’s define another predicate with the same domain $D$. Let,

• $F(x)$: $x$ scored at least $90\%$ on the final.

For $F(x)$, we notice that:

• $x$ is a variable.
• The domain of $x$ is once again $D$.
• The predicate captures a property of the elements in the subject.

If only Zain scored at least $90\%$ on the final, then $P($Zain$)=$ true and $P$(Jane)$) = P($Smith$)=$ false . Once again, we can visualize the truth values of this predicate using the following table:

Let,

• $P(x)$: x>7, \:\:\:\:\:\:\:\: Where, $x$ is an integer.

What are the truth values of $P\left(4\right), P\left(-3\right),P\left(0\right),P\left(7\right),P\left(14\right),$ and $P\left(517\right)$?

These are worked out in the following table:

In this case, the above table is not complete. We have only determined the truth values for a subset of the domain. The entire truth table will have infinitely many entries, one for each integer.

Let’s look at an example involving more than one variable.

Consider the following predicate:

• $P\left(x,y,z\right)$: $5x + 2y = 3z,\:\:\:\:\:\:\:\:$ Where, $x,y,$ and $z$ are integers.

Let’s look at a few possibilities for values of variables.

Predicate code example

In computer programs, we use predicates in conditional statements. As an example, look at the following Python code. Run this code to know the truth value of the resulting proposition from the predicate for different x variable values. The predicate is P(x):x<7.

> Note: We can change the values in the domain to experiment with different values of x.

Explanation

• Line 1: This line specifies the domain for the x variable.

• Line 2: We will look at the predicate for each value of the x variable.

• Line 3: The if statement has the predicate $P(x)$: $x<7$.

• Line 4: This line will execute when the predicate is true.

• Line 6: This line will execute when the predicate is false.

Leap year code example

In the following program, the truth value of $L(y)$ is computed for different values of $y$. The predicate $L$ is as follows:

$$L(y):y \text{ is a leap year.}$$

The year is a leap year if it is divisible by $4$ and not by $100$ or if it is divisible by $400$.

Note: We can change the values in the domain to experiment with different values of y and check if a year is a leap year or not.

Explanation

• Line 1: Notice that this line specifies the domain containing different values for the y variable.

• Line 2: We will check for the leap year for each value of the y variable from the domain.

• Line 3: The if statement has the predicate $L(y): y$ is leap year.

• Line 4: This line will execute when the predicate is true.

• Line 6: This line will execute when the predicate is false.