12.1 Quantifier Rules: Universal Instantiation and Existential Generalization

Quantifiers and Variables

Quantifiers and Their Meanings

Quantifiers let you make claims about how many objects in a domain satisfy a given property. There are two:

• The universal quantifier $\forall$ says a statement holds for every object in the domain. Read $\forall x\, P(x)$ as "for all $x$, $P(x)$."
• The existential quantifier $\exists$ says a statement holds for at least one object in the domain. Read $\exists x\, P(x)$ as "there exists an $x$ such that $P(x)$."

Variables ($x$, $y$, $z$, etc.) are placeholders for unspecified objects in the domain. A variable is bound when it falls within the scope of a quantifier that governs it; otherwise it's free.

The scope of a quantifier is the part of the formula where that quantifier applies. It typically extends to the end of the smallest well-formed formula that immediately follows the quantifier. Parentheses control scope explicitly, so pay close attention to them when parsing complex statements.

Interpreting Quantified Statements

When a statement has multiple quantifiers, read them left to right. The leftmost quantifier has the widest scope. Changing the order of different quantifier types changes the meaning:

• $\forall x\, \exists y\, P(x, y)$: "For every $x$, there is at least one $y$ such that $P(x, y)$." Here the choice of $y$ can depend on which $x$ you pick.
• $\exists y\, \forall x\, P(x, y)$: "There is a single $y$ that works for every $x$." This is a much stronger claim because the same $y$ must satisfy $P$ no matter what $x$ is.

Getting comfortable with this distinction is one of the trickiest parts of predicate logic, and it comes up constantly in proofs.

Universal Instantiation

The Universal Instantiation (UI) Rule

Universal Instantiation (UI) lets you move from a universal claim to a specific instance. The idea is straightforward: if something is true of everything in the domain, it must be true of any particular thing you name.

Formally:

The step of swapping the bound variable for a specific constant is called instantiation.

Applying Universal Instantiation

1. Locate a universally quantified statement in your proof (e.g., $\forall x\, P(x)$).
2. Choose any constant $c$ that denotes an object in the domain. Unlike with some other rules, $c$ does not need to be fresh; you can instantiate to a constant already in use.
3. Replace every occurrence of the bound variable $x$ within the scope of $\forall x$ with $c$, producing $P(c)$.
4. Write $P(c)$ as a new line in the proof, citing UI and the line number of the universal statement.

Example: Suppose line 1 is $\forall x\,(Fx \rightarrow Gx)$. You can instantiate with any constant, say $a$, to get $Fa \rightarrow Ga$. This is especially useful when you already have $Fa$ on another line, because you can then apply Modus Ponens to derive $Ga$.

A key point: you can apply UI to the same universal statement more than once with different constants. If everything is $F$, then $a$ is $F$, $b$ is $F$, and so on.

Existential Generalization

The Existential Generalization (EG) Rule

Existential Generalization (EG) lets you move from a specific instance to an existential claim. If you know something is true of a particular object, you can conclude that something in the domain has that property.

Formally:

The step of swapping a constant for a bound variable under $\exists$ is called generalization.

Applying Existential Generalization

1. Locate a statement containing a specific constant in your proof (e.g., $P(a)$).
2. Choose a variable $x$ to serve as the existentially quantified variable.
3. Replace one or more occurrences of the constant $a$ with $x$, and prefix the statement with $\exists x$.
4. Write the resulting statement (e.g., $\exists x\, P(x)$) as a new line, citing EG and the line number of the original statement.

You don't have to replace every occurrence of the constant. For instance, from $Rab$ you could derive $\exists x\, Rxb$, $\exists x\, Rax$, or $\exists x\, Rxx$ (the last only if $a$ and $b$ are the same constant). This flexibility matters when your conclusion targets a specific pattern.

UI and EG Working Together

These two rules are natural partners. A common proof pattern goes like this:

1. Start with a universal premise, e.g., $\forall x\,(Fx \rightarrow Gx)$.
2. Use UI to instantiate it to a particular constant: $Fa \rightarrow Ga$.
3. Given $Fa$ as another premise, apply Modus Ponens to get $Ga$.
4. Use EG to generalize: $\exists x\, Gx$.

This UI-then-EG pattern shows up in many predicate logic proofs. Recognizing it quickly will save you time and help you plan your proof strategy before you start writing lines.