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:

Shape	Typical 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. A claim that every integer has a larger integer requires a witness for each input; one input with no such witness would refute 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 to the module project

Use this concept to state, justify or challenge one claim in the workflow project. Name the mathematical model and the execution assumptions separately; software behavior is not established by an analogy alone.

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

Use the bounded reading guide to locate this lesson's topic in MCS or Rosen. These links open book indexes. Find the named topic in your edition, read one relevant explanation, then reconstruct the argument with the book closed.

Total predicates and empty domains

On a declared domain, each predicate instance must have a truth value. The expression 1/x>0 is undefined at x=0 over the reals; it needs a restricted domain or a separately defined zero case before quantification is meaningful. Do not let a programming exception silently stand for false.

For an empty domain D, ∀x∈D P(x) is true and ∃x∈D P(x) false. In the first there is no violating element; in the second there is no witness. This explains why an empty function is injective and why a nonempty codomain still prevents its surjectivity.

Unique existence needs existence as well as at-most-one: “any two solutions are equal” can hold when there are no solutions at all. Transfer attempt: construct a predicate on an empty domain satisfying at-most-one but not unique existence, and complete the domain changes in P1.

Use Practice Solutions and Feedback after your attempt, and Proof and Model Contracts to audit assumptions.