Predicates and Open Sentences

Predicates and open sentences are the semantic backbone of first-order logic, the formal system underlying essentially all of modern mathematics, and they appear the moment any mathematical definition uses a variable: "$G$ is a group," "$f$ is measurable," "$p$ is prime" are all predicates over their respective domains, and every theorem of the form "for all $x$ in $D$, $P(x)$" is a quantified closure of an open sentence exactly as described here. In computer science, predicates are the direct ancestor of boolean-valued functions and of the `WHERE` clauses in database query languages (relational algebra's selection operator literally filters a table by a predicate's truth set). In programming language theory, type predicates and preconditions/postconditions in Hoare logic are open sentences with free variables standing for program state, closed by substitution when a specific input is supplied. In set theory, the Axiom Schema of Specification (Separation) is stated precisely in terms of predicates: given a set $A$ and a predicate $P(x)$, one forms $\{x \in A : P(x)\}$ — literally the truth-set construction of this article, promoted to an axiom. In model theory, a predicate's truth set generalizes to the notion of a definable subset of a structure, and much of the subject studies which subsets of a domain arise as truth sets of first-order predicates. In statistics and cryptography, predicates appear as hypothesis-testing conditions ("the null hypothesis holds for parameter $\theta$") and as verification predicates in zero-knowledge proofs, both requiring the same free-variable/closure discipline to be stated without ambiguity.

Ask the tutor: How does quantifying a predicate ($\forall x\, P(x)$ or $\exists x\, P(x)$) formally turn it into a proposition, and what proof rules govern manipulating such quantified statements?

Think of a predicate as a machine with an input slot labeled $x$. You cannot ask "does the machine light up?" until you drop something into the slot; the question only makes sense post-insertion. The variable $x$ in $P(x)$ is the shape of the slot, not an object sitting in it. This is why $x$ is called free: it is free to be replaced, and the expression makes no assertion about any fixed thing until that replacement happens. The domain of discourse is the set of legal objects that fit the slot. "$x$ is divisible by 3" behaves very differently as a predicate over $\mathbb{Z}$ than as a predicate over $\mathbb{R}$: over $\mathbb{Z}$ every input yields a genuine true/false verdict (12 yes, 7 no), but over $\mathbb{R}$ the phrase "divisible by 3" does not even parse for something like $x = \pi$, so it fails to be a predicate over $\mathbb{R}$ at all under the usual meaning of divisibility. Fixing the domain is not bookkeeping; it is part of the definition of the predicate, because it determines whether substitution always succeeds in producing a proposition. Once the domain is fixed, a one-variable predicate carves the domain into two pieces: the truth set (where it's true) and its complement (where it's false). This is exactly the picture of a function $D \to \{T,F\}$, and it is the most useful mental model: a predicate is a two-valued function, substitution is function evaluation, and the truth set is the preimage of $T$.

:::svg[The predicate $P(x)$: "$x$ is divisible by 3" as a function $\mathbb{Z} \cap [0,12] \to \{T,F\}$]

Example 1 — a number-theoretic predicate with an infinite, non-uniform domain. Let $D = \mathbb{Z}$ and let $P(n)$ be the open sentence

— let us instead use a clean, checkable example. Define, over $D = \mathbb{Z}$,

Step 1: verify $P$ is a genuine predicate over $\mathbb{Z}$. For any specific integer $a$, the sentence "$a^2 - 5a + 6 = 0$" is an equation between two specific integers ($a^2-5a+6$ and $0$), and equality of integers is a relation with a determinate truth value for every pair of integers (given integers, we can always compute both sides and compare — this is part of what it means for $\mathbb{Z}$ with its arithmetic and equality to be well-defined). Hence Part 1 of the Substitution Theorem applies: $P(a)$ is a proposition for every $a \in \mathbb{Z}$. Step 2: compute the truth set. Factor: $n^2 - 5n + 6 = (n-2)(n-3)$. This product is $0$ exactly when $n = 2$ or $n = 3$. So

Step 3: exhibit substitution explicitly, including non-uniformity. Substituting $n = 2$: $P(2)$ is "$4 - 10 + 6 = 0$", i.e., "$0 = 0$", true. Substituting $n = -1$: $P(-1)$ is "$1 + 5 + 6 = 0$", i.e., "$12 = 0$", false. Substituting $n = 100$: $P(100)$ is "$10000 - 500 + 6 = 0$", i.e., "$9506 = 0$", false. Note the asymmetry: the truth set is the tiny finite set $\{2,3\}$ sitting inside the infinite domain $\mathbb{Z}$ — most substitutions produce false propositions, and exactly two produce true ones. This illustrates that "predicate" carries no presumption of symmetry or of a "nice" truth set; the truth set can be any subset of $D$ that arises from evaluating the defining condition. Step 4: an equivalent predicate. The predicate $Q(n): (n-2)(n-3)=0$ over $\mathbb{Z}$ has the same truth set $\{2,3\}$, hence $P$ and $Q$ are equivalent predicates in the sense of the definition, even though they are syntactically different open sentences.

Example 2 — a two-variable predicate over a non-numeric domain (sets), with asymmetric behavior in its two arguments. Let $U = \{1,2,3,4\}$ and let $D_1 = D_2 = \mathcal{P}(U)$ (the power set of $U$, so each variable ranges over subsets of $U$, not elements). Define the two-variable predicate

Step 1: verify $P$ is a predicate over $\mathcal{P}(U)\times\mathcal{P}(U)$. For any specific subsets $A, B \subseteq U$, "$A \subseteq B$" is a proposition (subset containment between two fixed, fully-specified sets is decidable by checking each element of $A$ against $B$ — a finite check since $U$ is finite), and "$|A| < |B|$" is a proposition (comparison of two specific natural numbers). A conjunction of two propositions is a proposition (this uses only the propositional connective rules already established for Propositions and Truth Values). So $P(A,B)$ is a proposition for every choice of $A, B \in \mathcal{P}(U)$, confirming Part 1 of the Substitution Theorem. Step 2: substitute an asymmetric pair. Let $A = \{1,3\}$, $B = \{1,2,3\}$. Then $A \subseteq B$ (every element 1, 3 of $A$ is in $B$ — check directly) and $|A| = 2 < 3 = |B|$. Both conjuncts true, so $P(A,B)$ is true. Step 3: show the two argument slots are not interchangeable — substitute the reverse order. Now evaluate $P(B,A)$, i.e., swap the roles: is $B \subseteq A$? We need every element of $B=\{1,2,3\}$ to lie in $A = \{1,3\}$; but $2 \in B$ and $2 \notin A$, so $B \not\subseteq A$. Hence the first conjunct of $P(B,A)$ is false, making $P(B,A)$ false overall (regardless of the size comparison). This demonstrates concretely that a two-variable predicate need not be symmetric: $P(A,B) \ne P(B,A)$ in general, here with $P(A,B) = T$ but $P(B,A) = F$ for this very pair. Step 4: a boundary case. Let $C = \{1,2,3,4\} = U$ itself and $D=\{1,2,3,4\}=U$. Then $P(C,D)$: is $C \subseteq D$? Yes ($C=D$). Is $|C| < |D|$? No, $4 < 4$ is false. So $P(C,D)$ is false — this shows the strict inequality in the definition is doing real work: without it (i.e. using $\subseteq$ and $\le$ instead of $<$), the pair $(U,U)$ would instead satisfy the predicate, changing the truth set. This is exactly the kind of check the Substitution Theorem guarantees will always terminate in an answer — every substitution here produced a definite T or F, never an ambiguous case — but it does not by itself tell us which answer; that requires actually working through the definitions, as we just did.