9.1 Universal and Existential Quantifiers

Quantifiers and Variables

Universal and Existential Quantifiers

Quantifiers let you make claims about elements in a group without having to name each one individually. There are exactly two quantifiers in standard predicate logic, and every quantified statement you'll encounter uses one or both.

The universal quantifier ($\forall$) expresses that a predicate holds for every element in the domain. It's read as "for all" or "for every."

• $\forall x \, P(x)$ is read: "For all $x$, $P(x)$ is true."
• If your domain is integers and $P(x)$ means "$x + 0 = x$," then $\forall x \, P(x)$ claims this holds for every integer. And it does.

The existential quantifier ($\exists$) expresses that a predicate holds for at least one element in the domain. It's read as "there exists" or "for some."

• $\exists x \, P(x)$ is read: "There exists an $x$ such that $P(x)$ is true."
• If your domain is integers and $P(x)$ means "$x$ is even," then $\exists x \, P(x)$ claims at least one integer is even. That's satisfied by 2, 4, 6, and so on.

Notice the difference in what it takes to make each quantifier true versus false. A universal statement $\forall x \, P(x)$ is false if even one counterexample exists. An existential statement $\exists x \, P(x)$ is true as soon as you find one witness that satisfies it.

Variables in Quantified Statements

A bound variable is a variable that falls within the scope of a quantifier. The quantifier "controls" it, so it doesn't refer to any particular value on its own.

• In $\forall x \, P(x)$, the variable $x$ is bound by $\forall$.

A free variable is a variable that is not governed by any quantifier in the statement. A formula with free variables isn't a full proposition yet because its truth value depends on what you plug in.

• In $P(x) \land Q(y)$, both $x$ and $y$ are free. You can't evaluate this as true or false until you assign values to them.

A single variable can appear both free and bound in different parts of a complex formula. For example, in $P(x) \land \forall x \, Q(x)$, the $x$ in $P(x)$ is free, while the $x$ in $\forall x \, Q(x)$ is bound. This kind of overlap is confusing and generally avoided in practice by renaming one of the variables.

Quantified Statements

Components of Quantified Statements

A quantified statement combines three pieces: a quantifier, a variable, and a predicate. Together they form a complete claim about the domain.

• $\forall x \, (P(x) \rightarrow Q(x))$ has the universal quantifier $\forall$, the variable $x$, and the predicate $(P(x) \rightarrow Q(x))$.
• This reads: "For every $x$, if $P(x)$ then $Q(x)$." If $P(x)$ means "$x$ is a dog" and $Q(x)$ means "$x$ is a mammal," the statement says all dogs are mammals.

A predicate is a statement containing one or more variables that becomes a proposition once those variables are assigned specific values. On its own, "$x$ is even" is neither true nor false. Substitute $x = 4$ and you get the proposition "4 is even," which is true. Substitute $x = 3$ and you get "3 is even," which is false.

Quantifiers turn predicates into propositions without needing to substitute a specific value. That's their whole purpose: they let you talk about all or some elements at once.

Domain of Discourse

The domain of discourse is the set of all values the variables in a quantified statement can take. It defines the "universe" you're reasoning about, and changing it can change whether a statement is true or false.

• "All students in this class passed the exam" has the domain: students in this specific class. The same sentence applied to a different class could have a different truth value.
• $\forall n \, (n^2 + n + 41 \text{ is prime})$ looks plausible if you test small natural numbers, but it actually fails at $n = 40$, where $40^2 + 40 + 41 = 1681 = 41^2$. The domain matters, and so does checking carefully.

The domain must be a non-empty set. Common choices include the natural numbers ($\mathbb{N}$), integers ($\mathbb{Z}$), real numbers ($\mathbb{R}$), or a specific set defined by context. Always identify the domain before evaluating a quantified statement, because the same formula can be true over one domain and false over another.