The Logic of Predicates

Our final piece of logic we need is the notion of predicate logic. It’s an extension of propositional logic—the content of our past few posts. Predicate logic helps us discuss propositions like “for all real numbers, (insert favourable property)”, and whether it is true or not.

Ironically, we need a tiny bit of set notation in order to set this up properly. A set $K$ is a collection of objects, possibly empty. If $x \neq y$ as objects, then we write $K = \{x, y\}$ to mean that $K$ is the set containing the distinct objects $x$ and $y$ . (Formally, this is known as the axiom of pairing.)

In particular, we want to consider the set $\{\mathrm T, \mathrm F\}$ . Let $p$ be a propositional variable, and let $q$ be a propositional variable defined in terms of $p$ .

Then $p \lor \neg p = t$ means that regardless of substitution, $p \lor \neg p = \mathrm T$ . Equivalently, for all ( $\forall$ ) substitutions of $p$ , $p \lor \neg p = \mathrm T$ .

For any propositional variable $p$ , we will eventually abbreviate $p = t$ by $p$ , so that can write the preceding proposition as follows:

$\forall p \in \{\mathrm T,\mathrm F\} \quad p \lor \neg p.$

This motivates us to define predicates rigorously.

Definition 1. Let $K$ be a set. Suppose $\phi(x)$ is a proposition for each $x \in K$ . We call $\phi$ a predicate on the domain $K$ . The notation $\forall x \in K\ \phi(x)$ is shorthand to mean the proposition “for all distinct objects $x$ in the set $K$ , $\phi(x) = \mathrm T$ ”.

Note that we will assume that $x \in K$ implies $x \neq K$ , which should make intuitive sense: a set should not be able to contain itself. This is a consequence of the axiom of regularity.

Thus, $(\forall x \in K\ \phi(x) = \mathrm T) = \mathrm T$ means that the proposition “for all distinct objects $x$ in the set $K$ , $\phi(x) = \mathrm T$ ” is true. $\forall$ is known as a universal quantifier.

For brevity, we will abbreviate the proposition $p = \mathrm T$ by $p$ , so that we can abbreviate the proposition $p = \mathrm F$ , equivalent to $\neg p = \mathrm T$ , by $\neg p$ . This summarises the notation $(\forall x \in K\ \phi(x) = \mathrm T) = \mathrm T$ by $\forall x \in K\ \phi(x)$ .

Thus, $p \lor \neg p$ is a predicate on the set $\{\mathrm T,\mathrm F\}$ . Either substitution for $p \in \{\mathrm T, \mathrm F\}$ —namely $\mathrm T$ or $\mathrm F$ —yields the theorem $p \lor \neg p = \mathrm T$ . However, without any substitution, $p \lor \neg p$ is not a proposition, and thus does not have a truth value.

Let $K$ be a set. It is clear that $\forall x \in K\ \phi(x)$ means that for any substitution of $x$ by elements in $K$ , $\phi(x) = \mathrm T$ . What then does it mean that $\neg (\forall x \in K\ \phi(x))$ ?

Perhaps a non-example will help us illustrate the point.

Example 1. Let $p$ be a propositional variable. Then $p \neq t$ . Equivalently,

$p \neq t = \neg(p = t) = \neg (\forall p \in \{\mathrm T,\mathrm F\}\ p).$

Proof. In the substitution $p = \mathrm T$ , we do get $p =\mathrm T = \mathrm T = t$ is true. However, there exists a substitution, namely $p = \mathrm F$ , such that $p =\mathrm F \neq \mathrm T = t$ . This violates the condition $p = t$ . Therefore, $p \neq t$ .

This motivates the definition of the existential quantifier.

Definition 2. Let $K$ be a set and $\phi$ be a predicate on the domain $K$ . The proposition $\exists x \in K: \phi(x)$ is shorthand to mean the proposition “there exists some object $x$ in the set $K$ such that $\phi(x)$ ”. Hence, we have the following characterisation:

$\neg(\forall x \in K\ \phi(x)) := (\exists x \in K : \neg \phi(x)).$

By double negation, we obtain the following result.

Theorem 1. Let $\phi$ be a predicate on a set $K$ . Then

$\neg (\exists x \in K : \phi(x)) = (\forall x \in K\ \neg \phi(x)).$

From this post onward, we will use $\Rightarrow$ in place of $\to$ , and likewise with other arrows, especially when we want to abbreviate $\forall x \in K\ \phi(x) \to \psi(x)$ by its English counterpart “For any $x \in K$ , $\phi(x) \Rightarrow \psi(x)$ ”.

Just like modus ponens, universal modus ponens is one of the most crucial proof techniques in mathematics. Using our revised notation, universal modus ponens can be written as follows.

Example 2. Let $\phi, \psi$ be predicates on a set $K$ . Then

$\forall x \in K\quad (\phi(x) \wedge (\phi(x) \Rightarrow \psi(x)) \Rightarrow \psi(x).$

In fact, any valid proof technique captured by a tautology can be universalised.

Quantified statements are fundamental in mathematics. We can formulate the foundations of mathematics, namely, set theory, using quantified statements. Sometimes, our predicates would be defined in terms of two propositions $p$ and $q$ . This requires the use of double quantifiers, and it turns out that the quantifiers all have distinct meanings.

We will discuss both applications in subsequent posts.

—Joel Kindiak, 27 Nov 24, 2159H

Responses

Ground Zero Mathematics – KindiakMath

December 28, 2025 at 12:28 am

[…] Previously, we discussed predicate logic and claimed that it is ubiquitous in mathematics. In this post, we will apply said logic to a naïve notion of set theory. […]

LikeLike

How to Nest Your Predicates – KindiakMath

December 28, 2025 at 12:33 am

[…] our predicates would be defined in terms of two propositions and . This requires the use of double quantifiers, […]

LikeLike

Surjections as Sets – KindiakMath

December 28, 2025 at 1:02 am

[…] far, we have developed mathematics in the following manner: propositional logic, then predicate logic, then a sufficiently naïve set […]

LikeLike

The Logic of Predicates

Share this:

Responses

Leave a comment Cancel reply