Unit 1 Lesson 4

The Universal Quantifier and the Existential Quantifier

In this lesson, we define the two fundamental quantifiers of first-order logic and show how they transform predicates into propositions.

Learning Objectives

    • Define the universal quantifier and the existential quantifier

    • Apply quantifiers to predicates to obtain propositions

    • Determine the truth value of quantified statements over a given domain

    • Distinguish bound and free variables in quantified expressions

    • Quantify binary predicates partially or fully

Motivation

In Lesson 3, we established that a predicate \(P(x)\) is not a proposition: its truth value depends on the variable \(x\). The sentence “\(x > 0\)” is neither true nor false until we know what \(x\) is.

There are exactly two mechanisms in classical logic for converting a predicate into a proposition:

  • Substitution — replace the variable by a specific element of the domain (covered in Lesson 3)
  • Quantification — assert something about all elements or about the existence of at least one element

This lesson treats the second mechanism.

Quantifier

A quantifier is a logical operator that, applied to a predicate over a specified domain of discourse, binds the free variable of the predicate and produces a proposition — a statement with a definite truth value.

Classical first-order logic admits exactly two quantifiers: the universal quantifier and the existential quantifier.

The Universal Quantifier

Let \(P(x)\) be a predicate with domain of discourse \(D\). The universal quantification of \(P(x)\) is the proposition

\[ \forall\, x \in D,\; P(x) \]

read “for all \(x\) in \(D\), \(P(x)\)” (or equivalently: “for every \(x\) in \(D\), \(P(x)\)”).

The symbol \(\forall\) is called the universal quantifier.

Truth condition. The proposition \(\forall\, x \in D,\; P(x)\) is true if and only if \(P(a)\) is true for every element \(a \in D\). It is false if there exists at least one element \(a \in D\) for which \(P(a)\) is false. Such an element is called a counterexample.

Universal quantifier — examples

  • “\(\forall\, x \in \mathbb{R},\; x^{2} \geq 0\)” → true. The square of every real number is non-negative.
  • “\(\forall\, n \in \mathbb{N},\; n \text{ is even}\)” → false. Counterexample: \(n = 3\).
  • “\(\forall\, x \in \{2, 4, 6\},\; x \text{ is even}\)” → true. Every element of this finite domain is even.

The Existential Quantifier

Let \(P(x)\) be a predicate with domain of discourse \(D\). The existential quantification of \(P(x)\) is the proposition

\[ \exists\, x \in D,\; P(x) \]

read “there exists an \(x\) in \(D\) such that \(P(x)\)” (or equivalently: “there is at least one \(x\) in \(D\) for which \(P(x)\)”).

The symbol \(\exists\) is called the existential quantifier.

Truth condition. The proposition \(\exists\, x \in D,\; P(x)\) is true if and only if there is at least one element \(a \in D\) for which \(P(a)\) is true. Such an element is called a witness. The proposition is false if \(P(a)\) is false for every \(a \in D\).

Existential quantifier — examples

  • “\(\exists\, x \in \mathbb{R},\; x^{2} = 2\)” → true. Witness: \(x = \sqrt{2}\).
  • “\(\exists\, n \in \mathbb{N},\; n + 1 = 0\)” → false. No natural number satisfies this.
  • “\(\exists\, x \in \{1, 3, 5\},\; x \text{ is even}\)” → false. No element of this domain is even.

Bound Variables and the Predicate–Proposition Boundary

Before quantification, \(x\) in \(P(x)\) is a free variable: the predicate’s truth value depends on it. After quantification — whether by \(\forall\) or \(\exists\) — the variable \(x\) becomes bound. The resulting expression no longer depends on \(x\); it is a proposition with a definite truth value determined solely by the predicate and the domain.

In summary:

  • \(P(x)\) with \(x\) free → predicate (no fixed truth value)
  • \(\forall\, x \in D,\; P(x)\) → proposition (definite truth value)
  • \(\exists\, x \in D,\; P(x)\) → proposition (definite truth value)

This is the precise mechanism by which quantifiers close the gap between predicates and propositions, a theme that has been present since Lesson 1.

The role of the domain

The truth value of a quantified statement depends critically on the domain of discourse. The same predicate can yield different truth values under different domains.

Let \(P(x)\!:\; x^{2} \geq 1\).

  • Over \(D = \{2, 3, 4\}\): \(\forall\, x \in D,\; P(x)\) is true.
  • Over \(D = \mathbb{R}\): \(\forall\, x \in D,\; P(x)\) is false (counterexample: \(x = 0.5\)).

The predicate is the same; the domain changes the truth value of the quantified proposition.

Binary Predicates and Quantification

So far, all predicates in this lesson have been unary: they depend on a single variable, \(P(x)\). However, many mathematical statements involve two or more variables. A binary predicate (a predicate of arity 2) depends on two variables:

\[ P(x, y) \]

For example, “\(x < y\)” is a binary predicate with two free variables. Its truth value depends on both \(x\) and \(y\).

When a binary predicate has two free variables, a single quantifier binds only one of them. The result is no longer a binary predicate, but it is not yet a proposition either — it is a unary predicate in the remaining free variable. This is called partial quantification.

To obtain a proposition from a binary predicate, one must bind both variables, either by applying two quantifiers or by combining a quantifier with a substitution. This is called full quantification.

Partial and full quantification

Let \(Q(x, y)\!:\; x < y\), with \(x, y \in \mathbb{R}\).

  • No quantification: \(Q(x, y) = \text{``}x < y\text{''}\) — binary predicate, two free variables, no truth value.
  • Partial quantification (one variable bound): \(\exists\, y \in \mathbb{R},\; x < y; \, x \in \mathbb{R}\) — unary predicate in \(x\). For any given \(x\), we can always find a larger \(y\), so this predicate happens to be true for every \(x\), but it is formally still a predicate until \(x\) is also bound or substituted.
  • Full quantification (both variables bound): \(\forall\, x \in \mathbb{R},\; \exists\, y \in \mathbb{R},\; x < y\) — proposition. Both variables are bound. Truth value: true (for every real number, there exists a larger one).

 

Quantifier order matters

When two different quantifiers are applied to a binary predicate, the order in which they appear can change the meaning — and the truth value — of the resulting proposition.

Let \(Q(x, y)\!:\; x < y\), with \(x, y \in \mathbb{R}\).

  • \(\forall\, x \in \mathbb{R},\; \exists\, y \in \mathbb{R},\; x < y\) → true. For every real number, there exists one that is larger.
  • \(\exists\, y \in \mathbb{R},\; \forall\, x \in \mathbb{R},\; x < y\) → false. This claims there is a single real number \(y\) that is larger than every real number — a greatest real number. No such number exists.

Swapping \(\forall\) and \(\exists\) produced a different proposition with a different truth value.

Exercise 1

Determine whether each quantified statement is true or false.

a)

\(\forall\, x \in \mathbb{R},\; x + 1 > x\)

b)

\(\forall\, n \in \mathbb{N},\; n^{2} > n\)

c)

\(\exists\, x \in \mathbb{Z},\; x^{2} = 9\)

d)

\(\exists\, x \in \mathbb{N},\; x + 1 = 0\)

Exercise 2

Classify each expression as a proposition or as a predicate (not a proposition).

a)

\(x^{2} + 1 > 0\)

b)

\(\forall\, x \in \mathbb{R},\; x^{2} + 1 > 0\)

c)

\(\exists\, n \in \mathbb{N},\; 2n = 6\)

d)

\(2n = 6\)

e)

Every prime number greater than 2 is odd.

Exercise 3

For each expression, determine whether it is a proposition, a unary predicate, or a binary predicate.

a)

\(\forall\, x \in \mathbb{Z},\; x + y = 0; y \in \mathbb{Z}\)

What kind of expression is this?

b)

\(\forall\, x \in \mathbb{R},\; \exists\, y \in \mathbb{R},\; x + y = 0\)

What kind of expression is this?

c)

\(x \cdot y = 1\)

What kind of expression is this?

d)

\(\exists\, y \in \mathbb{R},\; \forall\, x \in \mathbb{R},\; x + y = 0\)

What kind of expression is this?

Question

Why do the two propositions

\(\forall\, x \in \mathbb{R},\; \exists\, y \in \mathbb{R},\; x < y\)

and

\(\exists\, y \in \mathbb{R},\; \forall\, x \in \mathbb{R},\; x < y\)

have different truth values, even though they use the same predicate, the same domain, and the same two quantifiers?

Answer

In the first proposition, the quantifier \(\exists\, y\) is inside the scope of \(\forall\, x\). This means that the witness \(y\) is allowed to depend on \(x\): for each \(x\), we may choose a different \(y\) (e.g., \(y = x + 1\)). That is easily achieved, so the proposition is true.

In the second proposition, the quantifier \(\exists\, y\) is outside. This means we must choose a single, fixed \(y\) before we know \(x\), and that one \(y\) must work for every \(x\) simultaneously. No real number is larger than all others, so the proposition is false.

The lesson: when quantifiers of different types are nested, their order determines the dependency structure between the bound variables, and changing that order changes the meaning of the statement.

  • A quantifier binds the free variable of a predicate and produces a proposition
  • The universal quantifier \(\forall\) asserts that a predicate holds for all elements of the domain; a single counterexample refutes it
  • The existential quantifier \(\exists\) asserts that a predicate holds for at least one element (a witness); it is false only when no witness exists
  • The truth value of a quantified statement depends on both the predicate and the domain of discourse
  • A single quantifier applied to a binary predicate binds only one variable, yielding a unary predicate; to obtain a proposition, all free variables must be bound
  • When quantifiers of different types are nested, their order matters: swapping \(\forall\) and \(\exists\) can change the truth value