Skip to main content

Predicates, Domains, and Quantified Statements

What This Concept Is​

A predicate is a sentence with one or more free variables that becomes a proposition once those variables are given values from a specified domain (also called a universe of discourse). "$x$ is prime" is a predicate on integers; plug in $x = 7$ and it becomes the true proposition "$7$ is prime."

Quantifiers bind free variables and turn a predicate into a full mathematical claim:

  • Universal: $\forall x \in D,\ P(x)$ -- "for every $x$ in $D$, $P$ holds of $x$"
  • Existential: $\exists x \in D,\ P(x)$ -- "for some $x$ in $D$, $P$ holds of $x$"
  • Unique existential: $\exists! x \in D,\ P(x)$ -- "exactly one $x$ in $D$ satisfies $P$"

Two distinctions that constantly matter:

  • Free vs bound variables. In $\forall x \in \mathbb{Z},\ x + 1 > x$, the variable $x$ is bound by the quantifier. In $x + 1 > x$ alone, $x$ is free and the sentence is still a predicate, not a proposition.
  • Domain is part of the statement. "For all $x$, $x^2 \ge x$" is true over $\mathbb{Z}_{\ge 0}$, false over $\mathbb{R}$. The predicate did not change; the universe did.

Multiple quantifiers compose. The meaning of $\forall x \in A,\ \exists y \in B,\ P(x, y)$ reads left-to-right as: for every $x$, a (possibly different) $y$ exists such that $P(x, y)$ holds. The order matters -- swapping the quantifiers changes the theorem.

A compact reference for the shapes you will meet repeatedly:

ShapeTypical proof move
$\forall x \in D,\ P(x)$"Let $x$ be an arbitrary element of $D$." Then derive $P(x)$.
$\exists x \in D,\ P(x)$Exhibit a specific $x_0 \in D$ and verify $P(x_0)$.
$\exists! x \in D,\ P(x)$Existence plus uniqueness: show any two witnesses coincide.
$\forall x \in D,\ P(x) \rightarrow Q(x)$"Let $x$ be arbitrary; assume $P(x)$." Derive $Q(x)$.
$\forall x \in A,\ \exists y \in B,\ P(x,y)$For each $x$, construct a $y$ that may depend on $x$.

Why It Matters Here​

Proofs almost never live at the purely propositional level for long. Sets, functions, relations, and every induction statement are quantified. If you do not track the domain and variable roles carefully, you will prove a different theorem from the one that was asked. Common failure modes:

  • leaving a variable free, proving a predicate instead of a proposition;
  • dropping the domain and accidentally broadening or narrowing the claim;
  • confusing the order of nested quantifiers and proving a stronger or weaker statement than intended.

Quantifier discipline is also the single biggest gateway to reading textbook definitions accurately. Definitions of injectivity, continuity, convergence, primality, and graph properties are all nested quantifiers. If you cannot parse them, you cannot use them.

Concrete Examples​

Example 1 -- domain changes everything.

Take the predicate $P(x) : x^2 \ge x$.

  • Over the domain $\mathbb{Z}_{\ge 0}$ (nonnegative integers), $\forall x,\ P(x)$ is true. Quick check: $0^2 = 0 \ge 0$; for $x \ge 1$, $x^2 - x = x(x-1) \ge 0$.
  • Over $\mathbb{R}$, $\forall x,\ P(x)$ is false: at $x = \tfrac{1}{2}$, $x^2 = \tfrac{1}{4} < \tfrac{1}{2}$.

The predicate $P$ did not change. The universe did. Reporting "$x^2 \ge x$ is true" without domain is a category error in mathematical writing.

Example 2 -- nested quantifiers define a real theorem.

Parse carefully: $\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \ge N,\ |a_n - L| < \varepsilon$.

That is the definition of "the sequence $a_n$ converges to $L$." Read it out loud in the correct order: no matter how small $\varepsilon$ is chosen, there is some index $N$ such that from that index onward, every $a_n$ is within $\varepsilon$ of $L$. A student who swaps the first two quantifiers -- "there exists $N$ such that for every $\varepsilon$..." -- has defined something much stronger and usually false.

Example 3 -- unique existence.

The statement "every integer has a unique successor" is $\forall n \in \mathbb{Z},\ \exists! m \in \mathbb{Z},\ m = n + 1$. Proving uniqueness always requires two moves: (a) exhibit a witness, (b) show any two witnesses are equal. Missing step (b) is the most common proof gap in uniqueness arguments.

Example 4 -- reading a definition as nested quantifiers.

Textbook definition of injective function: "$f$ is injective when $f(a) = f(b)$ implies $a = b$." Fully quantified:

$$\forall a \in \text{dom}(f),\ \forall b \in \text{dom}(f),\ (f(a) = f(b) \rightarrow a = b).$$

Two universal quantifiers on the same domain, guarding a single implication. The proof skeleton is always the same: "let $a, b$ be arbitrary domain elements, assume $f(a) = f(b)$, derive $a = b$." The skeleton drops out of the quantifier structure, not from anyone's cleverness.

Common Confusion / Misconceptions​

  1. Omitting the domain. "For all $x$, $P(x)$" with no universe is underspecified. Counter-example habit: always write $\forall x \in D$, never bare $\forall x$. When reading someone else's claim with a missing domain, reconstruct it before engaging.
  2. Free variables mistaken for universally quantified. A sentence "if $x$ is even then $x^2$ is even" with a free $x$ is conventionally read as universal, but the convention is lossy. When you write your own statements, bind every variable explicitly.
  3. Quantifier order treated as stylistic. $\forall x \exists y$ and $\exists y \forall x$ assert genuinely different things. Contrast "for every person there is someone they love" ($\forall x \exists y$) with "there is someone everyone loves" ($\exists y \forall x$).
  4. "There exists" read as "usually." $\exists x,\ P(x)$ only requires one witness, no matter how exotic. "Every even integer is a sum of two primes" (Goldbach) is an existence claim about each even integer; one known counterexample would disprove it.

How To Use It​

When translating a statement into symbolic form or reading one for the first time:

  1. Name the domain explicitly. If the text does not give one, pick one and state it.
  2. Underline each variable once to confirm it is bound exactly by one quantifier.
  3. Decide, for each variable, whether it is universally quantified, existentially quantified, or uniquely existentially quantified.
  4. Keep the predicate body separate from the quantifier structure -- do not collapse them into "that messy formula."
  5. Re-read the statement aloud, tracing quantifiers left to right, and verify the English matches.
  6. If the statement is nested, try small concrete values to see if the intended meaning matches the symbolic form.
  7. Before proving, write the proof skeleton: universal $\rightarrow$ "let $x$ be arbitrary"; existential $\rightarrow$ "consider the witness $x_0 = \ldots$."

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Algorithmic correctness is "for every input of size $n$, the output satisfies $P$." Runtime bounds are "there exists $C, n_0$ such that for every $n \ge n_0$, $T(n) \le C \cdot f(n)$" -- the big-O definition is three nested quantifiers in disguise.
  • Semester 5 (concurrency). Liveness properties are existential ("eventually every request gets a response"), safety properties are universal ("every pair of threads never both hold the same lock"). Mixing them up is a class of bug that only a correct parse of quantifiers prevents.
  • Semester 6 (distributed systems). A quorum argument reads "for every failure scenario with $\le f$ crashed nodes, there exists a quorum intersection." The "for every scenario" is the universe of discourse.
  • Semester 7 (architecture). Availability targets ("for every hour in the quarter, at least 99.9% of requests succeed") are universally quantified over time windows; misread as existential, the SLA becomes trivial.

Check Yourself​

  1. Why is "$x > 3$" not yet a proposition? What is the minimum you must supply to make it one?
  2. What changes when the domain of a quantified statement changes? Give one example where the truth value flips.
  3. Write the definition of an injective function from $A$ to $B$ using only $\forall$, $\exists$, $=$, $\ne$, $\rightarrow$, and name the domain(s).
  4. Distinguish, with a concrete example, $\forall x \exists y,\ P(x,y)$ from $\exists y \forall x,\ P(x,y)$.
  5. What extra obligation does $\exists!$ introduce compared with $\exists$?
  6. Is $\forall x \in \emptyset,\ P(x)$ true, false, or undefined? Justify.

Mini Drill or Application​

Translate each into quantified form with an explicit domain, then state whether the claim is (a) true, (b) false, or (c) depends on a convention you should name:

  1. "Every student in the class has submitted at least one proof."
  2. "There is an integer whose square is prime."
  3. "Every nonempty finite set of integers has a smallest element."
  4. "For every real number there is a strictly larger real number."
  5. "Some real number is strictly larger than every other real number."
  6. "Each person in this room shares a birthday month with someone else in the room."

For each, also write the negation in symbolic form (this is practice for the next concept page on negation and quantifier order).

Read This Only If Stuck​