Predicates
In this lesson, we introduce predicates as generalisations of propositions, define the domain of discourse, and classify predicates by their arity.
Learning Objectives
-
Define the domain of discourse (universe of discourse)
-
Understand interpretation as the assignment of meaning to formal expressions
-
Define a predicate (propositional function) rigorously
-
Distinguish predicates from propositions
-
Classify predicates by arity (unary, binary, \(n\)-ary)
-
Determine the truth domain of a predicate over a given domain of discourse
From Propositions to Predicates
In the previous lessons, we studied propositions: declarative sentences with a definite truth value. We observed that certain expressions, such as “\(x > 2\)”, fail to be propositions because they contain free variables whose values are unspecified.
Rather than discard these expressions as defective, we recognise them as belonging to a more general and more powerful category. They are predicates—expressions that become propositions once every free variable receives a value from a specified domain.
This generalisation is not merely notational. It is the conceptual bridge between propositional logic and first-order predicate logic, the formal system that underlies virtually all of modern mathematics and computer science.
The domain of discourse, denoted \(\mathcal{D}\) (or \(U\)), is a non-empty set of objects over which the variables of a logical expression range.
Formally:
\[ \mathcal{D} \neq \emptyset \]
Every variable in a predicate is understood to take values exclusively from \(\mathcal{D}\). Without specifying the domain, a predicate has no determinate meaning.
Domains of discourse
- \(\mathcal{D} = \mathbb{N}\) — the natural numbers: the predicate “\(x\) is even” ranges over \(0, 1, 2, 3, \ldots\)
- \(\mathcal{D} = \mathbb{Z}\) — the integers: the predicate “\(x < 0\)” now admits negative values
- \(\mathcal{D} = \{a, b, c, \ldots, z\}\) — the Latin alphabet: the predicate “\(x\) is a vowel” ranges over letters
- \(\mathcal{D} = \{\text{all students in this course}\}\) — a finite, non-numerical domain
Why the Domain Matters
The same syntactic expression can have different truth values—or different meanings entirely—depending on the domain of discourse.
Consider: “There exists \(x\) such that \(x^2 = 2\).”
- Over \(\mathcal{D} = \mathbb{Q}\) (the rationals): false
- Over \(\mathcal{D} = \mathbb{R}\) (the reals): true
The formula is identical. The domain determines its truth value. This is precisely why rigorous mathematics always specifies the domain before evaluating any predicate.
Interpretation
An interpretation \(\mathcal{I}\) of a formal language consists of:
- A non-empty domain of discourse \(\mathcal{D}\)
- An assignment of elements of \(\mathcal{D}\) to each constant symbol
- An assignment of functions over \(\mathcal{D}\) to each function symbol
- An assignment of meaning to each predicate symbol: a mapping from \(\mathcal{D}^n\) to \(\{T, F\}\)
Formally, an interpretation is a pair:
\[ \mathcal{I} = (\mathcal{D}, \cdot^{\mathcal{I}}) \]
where \(\cdot^{\mathcal{I}}\) is the interpretation function that maps each non-logical symbol to its denotation in \(\mathcal{D}\).
Two interpretations of the same formula
Let \(P(x, y)\) be a binary predicate symbol. Consider the formula \(P(a, b)\).
Interpretation \(\mathcal{I}_1\):
- \(\mathcal{D}_1 = \mathbb{Z}\)
- \(P^{\mathcal{I}_1}(x, y) \iff x < y\)
- \(a^{\mathcal{I}_1} = 3\), \(b^{\mathcal{I}_1} = 7\)
Under \(\mathcal{I}_1\): \(P(a, b)\) means \(3 < 7\) → true
Interpretation \(\mathcal{I}_2\):
- \(\mathcal{D}_2 = \mathbb{Z}\)
- \(P^{\mathcal{I}_2}(x, y) \iff x > y\)
- \(a^{\mathcal{I}_2} = 3\), \(b^{\mathcal{I}_2} = 7\)
Under \(\mathcal{I}_2\): \(P(a, b)\) means \(3 > 7\) → false
The syntactic formula \(P(a, b)\) is the same. The interpretation determines the truth value.
Syntax vs. Semantics
Syntax is the structure of formal expressions—the symbols and the rules for combining them.
Semantics is the meaning assigned to those expressions by an interpretation.
A formula is a syntactic object. It has no truth value until an interpretation is given. This distinction between syntax and semantics is one of the most fundamental ideas in mathematical logic and in theoretical computer science.
Predicate (Propositional Function)
A predicate (also called a propositional function or open sentence) is an expression containing one or more free variables that becomes a proposition when each variable is assigned a value from the domain of discourse.
Predicates vs. Propositions
- “\(x^2 = 4\)” → predicate (free variable \(x\); truth depends on the value of \(x\))
- “\(2^2 = 4\)” → proposition (no free variables; truth value is \(T\))
- “\(x + y > 10\)” → predicate (two free variables)
- “\(3 + 8 > 10\)” → proposition (truth value is \(T\))
- “Every even number is divisible by 2” → proposition (the quantifier “every” binds the variable)
Substitution turns a predicate into a proposition
Let \(P(x)\) denote “\(x\) is a prime number” over \(\mathcal{D} = \mathbb{N}\).
- \(P(7)\): “7 is a prime number” → \(T\)
- \(P(4)\): “4 is a prime number” → \(F\)
- \(P(1)\): “1 is a prime number” → \(F\)
The predicate \(P(x)\) itself is neither true nor false. Each instance \(P(a)\), for \(a \in \mathcal{D}\), is a proposition.
Arity
The arity of a predicate is the number of free variables (arguments) it takes.
- A unary predicate (arity 1) takes one argument: \(P(x)\). It defines a property of elements in \(\mathcal{D}\).
- A binary predicate (arity 2) takes two arguments: \(P(x, y)\). It defines a relation between pairs of elements in \(\mathcal{D}\).
- An \(n\)-ary predicate (arity \(n\)) takes \(n\) arguments: \(P(x_1, x_2, \ldots, x_n)\). It defines a relation on \(n\)-tuples of elements in \(\mathcal{D}\).
Predicate
An \(n\)-ary predicate over a domain \(\mathcal{D}\) is a function:
\[ P : \mathcal{D}^n \to \{ T, F \} \]
Equivalently, it corresponds to a subset of the Cartesian product \(\mathcal{D}^n\):
\[ P \subseteq \mathcal{D}^n \]
An \(n\)-tuple \((a_1, \ldots, a_n)\) satisfies the predicate if and only if \((a_1, \ldots, a_n) \in P\).
Predicates classified by arity
Unary (arity 1) — properties:
- \(\text{IsEven}(x)\): “\(x\) is even” over \(\mathcal{D} = \mathbb{Z}\)
- \(\text{IsVowel}(x)\): “\(x\) is a vowel” over \(\mathcal{D} = \{a, b, \ldots, z\}\)
Binary (arity 2) — relations:
- \(\text{LessThan}(x, y)\): “\(x < y\)” over \(\mathcal{D} = \mathbb{R}\)
- \(\text{Divides}(x, y)\): “\(x\) divides \(y\)” over \(\mathcal{D} = \mathbb{Z}^{+}\)
Ternary (arity 3):
- \(\text{Between}(x, y, z)\): “\(y\) is between \(x\) and \(z\)” over \(\mathcal{D} = \mathbb{R}\)
Propositions as Predicates of Arity Zero
Now that the notion of arity is established, we can state a unifying observation.
A proposition is a complete statement: it has a fixed truth value. It contains no free variables.
A predicate is an incomplete statement: it contains free variables that must be bound—either by substitution of specific values or by quantification—before it acquires a truth value.
Since a proposition takes zero arguments, it can be viewed as a predicate of arity zero:
\[ P : \mathcal{D}^0 \to \{T, F\} \]
Because \(\mathcal{D}^0 = \{()\}\) (the set containing only the empty tuple), such a function selects exactly one truth value. This is precisely what a proposition does.
Propositions and predicates are therefore not disjoint categories. They sit on a single spectrum parameterised by arity, with propositions as the degenerate case \(n = 0\).
Truth Domain (Truth Set) of a Predicate
Let \(P(x)\) be a unary predicate over a domain of discourse \(\mathcal{D}\). The truth domain (also called the truth set or solution set) of \(P\) is the set of all elements in \(\mathcal{D}\) for which \(P\) evaluates to true.
Formally:
\[ \mathcal{D}_P = \{ x \in \mathcal{D} \mid P(x) = T \} \]
Equivalently, the truth domain is the preimage of \(T\) under the function \(P : \mathcal{D} \to \{T, F\}\).
For an \(n\)-ary predicate \(P(x_1, \ldots, x_n)\):
\[ \mathcal{D}_P = \{ (x_1, \ldots, x_n) \in \mathcal{D}^n \mid P(x_1, \ldots, x_n) = T \} \]
The truth domain is always a subset of the domain of discourse (or of \(\mathcal{D}^n\) for \(n\)-ary predicates):
\[ \mathcal{D}_P \subseteq \mathcal{D}^n \]
Three Important Special Cases
The truth domain of a predicate can be:
- Empty (\(\mathcal{D}_P = \emptyset\)): no element of \(\mathcal{D}\) satisfies \(P\). The predicate is unsatisfiable (or contradictory) over \(\mathcal{D}\).
- Equal to the full domain (\(\mathcal{D}_P = \mathcal{D}\)): every element of \(\mathcal{D}\) satisfies \(P\). The predicate is universally valid (or a tautology) over \(\mathcal{D}\).
- A proper, non-empty subset (\(\emptyset \subset \mathcal{D}_P \subset \mathcal{D}\)): some elements satisfy \(P\) and some do not. The predicate is satisfiable but not universally valid.
This classification is directly analogous to the satisfiability problem in computer science. Determining whether a predicate is satisfiable—whether its truth domain is non-empty—is one of the central questions of theoretical CS (the SAT problem).
Computing truth domains
a) Let \(P(x)\): “\(x^2 = 4\)”
- Over \(\mathcal{D} = \mathbb{N}\): \(\mathcal{D}_P = \{2\}\)
- Over \(\mathcal{D} = \mathbb{Z}\): \(\mathcal{D}_P = \{-2, 2\}\)
- Over \(\mathcal{D} = \mathbb{R}\): \(\mathcal{D}_P = \{-2, 2\}\)
b) Let \(Q(x)\): “\(x\) is even” over \(\mathcal{D} = \{1, 2, 3, 4, 5, 6\}\):
\(\mathcal{D}_Q = \{2, 4, 6\}\)
c) Let \(R(x)\): “\(x^2 < 0\)” over \(\mathcal{D} = \mathbb{R}\):
\(\mathcal{D}_R = \emptyset\)
d) Let \(S(x)\): “\(x + 0 = x\)” over \(\mathcal{D} = \mathbb{R}\):
\(\mathcal{D}_S = \mathbb{R}\)
The domain of discourse changes the truth domain
Let \(P(x)\): “\(x > 3\)”
- Over \(\mathcal{D} = \{1, 2, 3, 4, 5\}\): \(\mathcal{D}_P = \{4, 5\}\)
- Over \(\mathcal{D} = \{1, 2, 3\}\): \(\mathcal{D}_P = \emptyset\) — the predicate is unsatisfiable over this domain
- Over \(\mathcal{D} = \{4, 5, 6, 7\}\): \(\mathcal{D}_P = \{4, 5, 6, 7\} = \mathcal{D}\) — the predicate is universally valid over this domain
The same predicate. Three different domains. Three fundamentally different truth domains. This underscores why specifying the domain of discourse is not optional—it is constitutive of the predicate’s meaning.
Predicates in Computer Science
In computer science, predicates appear everywhere. A Boolean function in a program is a predicate. A database query selects tuples satisfying a predicate. A type-checker verifies predicates about expressions. A precondition or postcondition in formal verification is a predicate.
In relational databases, a table with \(n\) columns is precisely an \(n\)-ary predicate: each row is an \(n\)-tuple that satisfies the predicate defined by the table’s schema. The SQL WHERE clause is a predicate that filters tuples. The set of rows returned by a query is the truth domain of that predicate.
Understanding predicates, their arity, and their truth domains is therefore not only a matter of logical rigour—it is the theoretical foundation for much of applied computer science.
Exercise 1
For each expression, decide whether it is a predicate (i.e., it contains at least one free variable).
Exercise 2
Determine the arity of each expression.
Exercise 3
Each item presents the same statement evaluated over two different domains. Determine the truth value in each case.
Exercise 4
Determine the truth domain of each predicate.
Question
Why is
“\(x\) divides \(y\)”
a predicate,
but
“3 divides 12”
a proposition?
Answer
First: contains free variables \(x\) and \(y\) → truth depends on the values assigned to them → predicate.
Second: all variables are replaced by specific constants → has a definite truth value (\(T\)) → proposition.
Substitution of specific values from the domain of discourse transforms a predicate into a proposition.
- The domain of discourse \(\mathcal{D}\) is the non-empty set over which variables range; it must always be specified before any predicate can be evaluated
- An interpretation \(\mathcal{I} = (\mathcal{D}, \cdot^{\mathcal{I}})\) assigns a domain, and maps each predicate symbol, constant symbol, and function symbol to its denotation—thereby giving meaning to purely syntactic expressions
- A predicate is a function \(P : \mathcal{D}^n \to \{T, F\}\); it becomes a proposition when every free variable is assigned a value from \(\mathcal{D}\)
- The arity of a predicate is the number of its free variables: unary predicates express properties, binary predicates express relations, and \(n\)-ary predicates express relations on \(n\)-tuples
- A proposition is a predicate of arity zero: \(P : \mathcal{D}^0 \to \{T, F\}\)
- The truth domain \(\mathcal{D}_P = \{x \in \mathcal{D} \mid P(x) = T\}\) is the set of all elements for which the predicate evaluates to true; it is always \(\mathcal{D}_P \subseteq \mathcal{D}^n\)
- A predicate is unsatisfiable if \(\mathcal{D}_P = \emptyset\), and universally valid if \(\mathcal{D}_P = \mathcal{D}\)