Predicates and Quantifiers

The Big Idea

Propositional logic treats a complete statement as one unit: \(p\) is true or false. Mathematics often needs to look inside the statement and describe which objects make a condition true.

The sentence “\(x\) is even” is not yet a proposition because \(x\) has not been identified. It is a predicate: a condition that an object may or may not satisfy.

A quantifier tells us how broadly the condition applies. It can claim that every object satisfies the predicate, that at least one object does, or that exactly one object does. Predicates supply the condition; quantifiers turn that condition into a complete claim.

What Is a Predicate?

A predicate is an open sentence containing one or more variables. It becomes true or false when values are assigned to those variables.

Let

\[ E(n):\quad n\text{ is even}. \]

The notation \(E(n)\) names the predicate. Substitution creates propositions:

A predicate behaves like a truth-valued rule: give it an allowed object, and it produces the truth value true or false.

The Domain Is Part of the Predicate

The domain, or universe of discourse, is the collection of objects the variables are allowed to represent. A predicate cannot be interpreted reliably without a domain.

Consider

\[ P(x):\quad x^2=2. \]

• Over the integers, no value satisfies \(P(x)\).
• Over the rational numbers, no value satisfies \(P(x)\).
• Over the real numbers, \(x=\sqrt2\) and \(x=-\sqrt2\) satisfy \(P(x)\).

The symbols did not change, but the allowed inputs did. State the domain explicitly when context does not make it clear.

Predicates May Involve Several Variables

A predicate involving one variable is unary. A predicate involving two variables is binary, and predicates may involve any finite number of variables.

Binary predicates describe relations between objects. For example, \(x\lt y\), \(x\mid y\), and \(x=y\) are all relations because their truth depends on an ordered pair of inputs.

Free and Bound Variables

A variable is free when no assignment or quantifier controls it. A variable is bound when a quantifier governs it.

In

\[ x+y=10, \]

both \(x\) and \(y\) are free. The expression is an open sentence.

In

\[ \exists x\in\mathbb{R}\quad x+y=10, \]

the variable \(x\) is bound by \(\exists x\), but \(y\) remains free. The formula is still open with respect to \(y\).

In

\[ \forall y\in\mathbb{R}\ \exists x\in\mathbb{R}\quad x+y=10, \]

both variables are bound, so the formula is a complete proposition. It is true: for any real \(y\), choose \(x=10-y\).

The Universal Quantifier

The symbol \(\forall\) means for every or for all. The proposition

\[ \forall x\in\mathbb{R},\quad x^2\ge0 \]

says that every real number has a nonnegative square. It is true because an arbitrary real input satisfies the predicate.

A universal proposition is demanding: every allowed object must pass the test. One counterexample is enough to make it false.

Words that often signal universal quantification include all, every, each, any, and whenever.

The Existential Quantifier

The symbol \(\exists\) means there exists or for at least one. The proposition

\[ \exists n\in\mathbb{Z}\quad n^2=25 \]

is true because \(n=5\) is one allowed value that satisfies the predicate. The value \(-5\) works as well, but one example is enough.

An object that establishes an existential claim is called a witness. To disprove an existential claim, however, we must show that no object in the domain can satisfy it.

Words such as some, at least one, there is, and for some commonly signal existential quantification.

Universal and Existential Claims

The quantifier determines how much evidence is needed. One example can prove existence, but it cannot prove a universal rule.

Restricted Quantifiers

The notation \(\forall x\in D\) and \(\exists x\in D\) restricts attention to a domain \(D\). These are compact versions of statements using membership and logical connectives.

Universal restriction uses a conditional:

\[ \forall x\in D\,P(x) \quad\text{means}\quad \forall x\,(x\in D\to P(x)). \]

Existential restriction uses a conjunction:

\[ \exists x\in D\,P(x) \quad\text{means}\quad \exists x\,(x\in D\land P(x)). \]

This difference matters. A universal claim considers every object but promises \(P(x)\) only for members of \(D\). An existential claim needs one object that both belongs to \(D\) and satisfies \(P(x)\).

Scope Tells Us What a Quantifier Controls

The scope of a quantifier is the part of a formula governed by it. Parentheses make the scope visible.

Compare:

• \(\forall x\,(P(x)\to Q(x))\): every \(x\) satisfying \(P\) also satisfies \(Q\).
• \((\forall x\,P(x))\to Q(x)\): the quantifier controls only \(P(x)\), leaving the \(x\) in \(Q(x)\) free.

The second form is usually not what the writer intends. Use parentheses and repeat domains when needed, especially in formulas containing several connectives or quantifiers.

Predicates Define Sets

The truth set of a predicate is the collection of domain elements that make it true. If

\[ P(x):\quad x^2\lt10,\qquad x\in\mathbb{Z}, \]

then the truth set is

\[ \{x\in\mathbb{Z}:x^2\lt10\} = \{-3,-2,-1,0,1,2,3\}. \]

This connects logic to set-builder notation. A predicate supplies the membership test, and the resulting set collects every object that passes it.

Under this view, \(\exists x\,P(x)\) says the truth set is nonempty, while \(\forall x\,P(x)\) says the truth set is the entire domain.

Negating Quantified Statements

Negation switches the quantifier and negates the predicate:

\[ \neg\forall x\,P(x) \quad\equiv\quad \exists x\,\neg P(x), \]

\[ \neg\exists x\,P(x) \quad\equiv\quad \forall x\,\neg P(x). \]

The negation of “every” is “not every,” which means “at least one does not.” It does not mean “none.”

The Order of Quantifiers Matters

When a formula contains different quantifiers, changing their order can change the meaning and truth value.

Over the real numbers, compare:

\[ \forall x\in\mathbb{R}\ \exists y\in\mathbb{R}\quad y\gt x \]

and

\[ \exists y\in\mathbb{R}\ \forall x\in\mathbb{R}\quad y\gt x. \]

The first statement is true: given any \(x\), choose \(y=x+1\). The choice of \(y\) may depend on \(x\).

The second statement is false: it asks for one fixed real number \(y\) greater than every real number. No greatest real number exists.

Universal-then-existential often allows a new witness for each input. Existential-then-universal demands one witness that works for all inputs.

When Order Does Not Change the Meaning

Consecutive quantifiers of the same type can usually be exchanged:

\[ \forall x\,\forall y\,P(x,y) \quad\equiv\quad \forall y\,\forall x\,P(x,y), \]

\[ \exists x\,\exists y\,P(x,y) \quad\equiv\quad \exists y\,\exists x\,P(x,y). \]

Trouble usually arises when \(\forall\) and \(\exists\) trade places. Even then, the surrounding predicate and domain must be examined rather than relying on a slogan.

Unique Existence

The symbol \(\exists!\) means there exists exactly one. For example,

\[ \exists!x\in\mathbb{R}\quad x+3=7 \]

is true because \(x=4\) satisfies the equation and no other real number does.

A unique-existence claim contains two parts:

1. Existence: at least one object satisfies the predicate.
2. Uniqueness: no two distinct objects satisfy it.

Finding one witness proves existence but not uniqueness. A complete proof must establish both parts.

Quantifying Over an Empty Domain

If a domain contains no objects, an existential claim over it is false because no witness exists. A universal claim over it is true vacuously because no object violates the predicate.

Let \(D=\varnothing\). Then:

• \(\exists x\in D\,P(x)\) is false.
• \(\forall x\in D\,P(x)\) is true.

This convention keeps universal statements aligned with their conditional form \(\forall x\,(x\in D\to P(x))\). No object can make \(x\in D\) true and \(P(x)\) false.

Translating Words and Symbols

Use the domain \(\mathbb{Z}\) unless another domain is shown.

Preserve the strength and order of the original sentence. “Some” cannot become “every,” and a witness that depends on \(x\) cannot be moved in front of \(\forall x\) without changing the claim.

Match the Proof to the Quantifier

The quantifier tells you what kind of evidence the argument must supply. This is one of the most useful planning tools in proof.

Where Predicates and Quantifiers Reappear

• Sets: predicates define membership conditions and truth sets.
• Functions: existence and uniqueness specify whether each input receives exactly one output.
• Relations: predicates involving two or more variables describe connections among objects.
• Definitions: quantified biconditionals classify every object in a domain.
• Calculus: limits and continuity use nested quantifiers whose order is essential.
• Algebra: equations ask which values make a predicate true.
• Databases: filters behave like predicates, while queries search for witnesses or verify universal conditions.
• Programming: assertions, loops, and tests express quantified claims about data.

These concepts are introduced gently here because they become working tools across the rest of mathematics.

A Predicate-and-Quantifier Routine

1. Identify the predicate. What condition is being tested?
2. List the variables. Which are free, assigned, or bound?
3. State the domain. What may each variable represent?
4. Find the quantifier and its scope.
5. Check the order. May a witness depend on an earlier variable?
6. Translate into plain language. Preserve “every,” “some,” and “exactly one.”
7. Choose the right evidence. Arbitrary object, witness, counterexample, or impossibility proof?
8. For negation, switch the quantifier and negate the predicate.

Once the variables, domains, and scopes are visible, a complicated formula becomes a sequence of manageable instructions.

Common Confusions

Working Summary

A predicate is a condition involving variables; a quantifier turns that condition into a claim about a domain. The universal quantifier \(\forall\) covers every allowed object, the existential quantifier \(\exists\) requires at least one witness, and \(\exists!\) requires exactly one.

Domains, free and bound variables, scope, and quantifier order are part of the meaning. Predicates define sets and relations, while quantified statements guide proof through arbitrary objects, witnesses, counterexamples, and uniqueness arguments.

Check Your Understanding