Deductive Reasoning with Quantifiers

Applying logical rules to move from premises to a conclusion. When quantifiers are involved, need to take special care to maintain logical validity throughout manipulation.

Universal Instantiation

From a universally quantified statement $∀x P(x)$, you can conclude $P(c)$ for any particular value $c$. This is because the statement is true for all $x$.

Existential Instantiation

If $∃x P(x)$ is true, there exists some particular $x$ such that $P(x)$ is true, though we may not know the exact value.

In this case, we can again say that $P(c)$ holds for some $c$, but this must be the same $c$ throughout our reasoning process

Universal Generalization

If $P(c)$ is true for any arbitrary element $c$, we can generalize that $∀x P(x)$ is true.

Example: If for any arbitrary $x$, we can show that $x + 0 = x$, then we can generalize that $∀x (x + 0 = x)$.

Existential Generalization

If $P(c)$ is true for some specific value $c$, then we can conclude $∃x P(x)$.

Example: If $4 > 3$ is true for $x = 4$, we can conclude $∃x (x > 3)$.

Advice for proving validity with quantifiers

The process is quite similar to when we did not have quantifiers, but we must take special care of a few points

Usually, we will assign some constant to a quantified variable, manipulate the statements, and reapply a quantifier, make sure to apply the correct one at the end.
When manipulating (or assigning a constant to) a variable bounded by an existential quantifier, we must ensure that it is indeed constant throughout the proof (we cannot generalize for any constant value)
The order of quantifiers is very important, $\forall x \exists y$ is very different from $\exists y \forall x$. Make sure you are working with the correct one!