2.2 Quantifiers and Scope

Quantifiers are the symbols that allow first order logic to express statements about many objects at once, and they are the main feature that separates first order logic from propositional logic.

Universal and Existential Quantifiers

There are two basic quantifiers:

and:

The universal quantifier $\forall$ is read as “for all”, and it is used to state that a formula holds for every object in the domain under consideration.

The existential quantifier $\exists$ is read as “there exists”, and it is used to state that a formula holds for at least one object in the domain under consideration.

For example:

says that every object has property $P$, while:

says that at least one object has property $P$.

Definition 2.9 (Scope)

The scope of a quantifier is the part of the formula to which the quantifier applies.

In the formula:

the scope of $\forall x$ is:

Thus both occurrences of $x$ in this formula are controlled by the quantifier.

In contrast, in the formula:

the scope of $\forall x$ is only:

The occurrence of $x$ in $Q(x)$ is outside the scope of the quantifier and is therefore free.

Definition 2.10 (Free and Bound Occurrences)

An occurrence of a variable in a formula is bound if it lies inside the scope of a quantifier for that same variable.

An occurrence of a variable is free if it is not bound.

For example, in:

the occurrence of $x$ is bound, while the occurrence of $y$ is free.

In:

the occurrences of $y$ are bound, while the occurrence of $x$ is free.

This distinction is important because the truth of a formula with free variables depends on an assignment of values to those variables.

Example 2.11

Consider:

The variable $x$ is bound, because it occurs within the scope of $\forall x$.

The variable $y$ is free, because no quantifier binds it.

Thus the formula says that every object is less than the object assigned to $y$, and its truth depends on which object $y$ denotes.

Definition 2.12 (Sentence)

A sentence is a formula with no free variables.

For example:

is a sentence.

The formula:

is not a sentence, because the variable $x$ occurs freely.

Sentences are the formulas that can be assigned truth values in a structure without requiring an additional assignment for free variables.

Order of Quantifiers

The order of quantifiers matters.

The formula:

says that for every object $x$, there is some object $y$ related to $x$.

The formula:

says that there is one object $y$ that is related to every object $x$.

These two formulas generally have different meanings.

For example, if $R(x, y)$ means:

then:

says that every object has a larger object.

But:

says that there is one object larger than every object.

In the natural numbers, the first statement is true, while the second statement is false.

Definition 2.13 (Restricted Quantifiers)

A restricted universal quantifier:

is an abbreviation for:

A restricted existential quantifier:

is an abbreviation for:

The difference between implication and conjunction in these translations is important.

For a universal statement, objects outside $S$ should not matter, so implication is used.

For an existential statement, the object must both belong to $S$ and satisfy $A(x)$, so conjunction is used.

Example 2.14

The statement:

means:

The statement:

means:

These are not new primitive forms of first order logic, but convenient abbreviations.

Lemma 2.15 (Negating Quantifiers)

For every formula $A(x)$, the following equivalences hold:

and:

Proof

The formula:

says that it is not the case that $A(x)$ holds for every object $x$.

This means that there is at least one object $x$ for which $A(x)$ fails.

Thus:

Similarly, the formula:

says that there is no object $x$ for which $A(x)$ holds.

This means that every object $x$ fails to satisfy $A(x)$.

Thus:

Example 2.16

The negation of:

is:

This says that not every object has property $P$ exactly when at least one object fails to have property $P$.

The negation of:

is:

This says that there is no object with property $P$ exactly when every object fails to have property $P$.

Definition 2.17 (Variable Capture)

Variable capture occurs when a substitution causes a variable that was free to become bound by a quantifier.

For example, consider:

The variable $y$ is free.

If we replace $y$ by $x$ without changing bound variables first, we obtain:

The newly inserted $x$ now lies inside the scope of $\forall x$, so it has become bound.

This changes the syntactic role of the variable and may change the meaning of the formula.

Lemma 2.18 (Renaming Bound Variables)

Bound variables may be renamed as long as no free variable becomes captured.

For example:

may be renamed as:

provided that $z$ does not already occur in a way that would create confusion or capture.

Proof

A bound variable functions only as a placeholder for objects ranging over the domain.

Changing the name of a bound variable does not change the structure of quantification, as long as the change is made consistently throughout the scope of the quantifier and does not capture any free variables.

Thus the formulas:

and:

have the same logical content.

The restriction about capture is necessary because replacing $x$ by a variable already free in the formula can change which occurrences are bound and which occurrences remain free.