Why does universal generalization work? (the rule of inference)

Solution 1:

1. What is meant by the second paragraph ?

That is, when we assert from ∀xP(x) the existence of an element c in the domain, we have no control over c and cannot make any other assumptions about c other than it comes from the domain. Universal generalization is used implicitly in many proofs in mathematics and is seldom mentioned explicitly. However, the error of adding unwarranted assumptions about the arbitrary element c when universal generalization is used is all too common in incorrect reasoning.

This paragraph is (in my opinion) a little less than clear, but it is trying to give a description of what "$\forall x \; P(x)$" means. It means that, if you give me any $x$, $P(x)$ is true. I am not allowed to request any particular kind of $x$; there is no assumption that $x$ is blue or $x$ is greater than $3$. $P(x)$ is true for all $x$, not just for some particular $x$s which satisfy some particular assumptions.

This results in a common error in proving $\forall x \; P(x)$, but it does not come in so much in using $\forall x \; P(x)$. The error is that one proves that $\forall x \; P(x)$ holds by proving it holds for some particular kind of $x$'s, which is not allowed. To prove $\forall x \; P(x)$ holds, you must show that $P(x)$ is true, under no assumptions about $x$.

2. How come just by taking arbitrary c in domain, we can conclude that if P(c) is true then so is ∀xP(x). (There may exist some counterexamples).

Universal generalization can be stated as the following:

If $P(c)$ must be true, and we have assumed nothing about $c$, then $\forall x P(x)$ is true.

To get a grasp on this rule (which is one of the more counter-intuitive ones!) you should try to get a grasp on the part and we have assumed nothing about $c$. What does that mean? It means we really could have proven $P(x)$ for any value of $x$, not just $x = c$; the same proof would apply! So we have actually shown that $\forall x \; P(x)$.

You are right that we could not prove $\forall x \; P(x)$ just by proving $P(c)$ for some particular $c$. However, if we prove it and we have made no assumptions about that particular $c$, then that $c$ is in some sense "general"; without loss of generality we may say that $P(x)$ is true for all $x$.

Solution 2:

We can sum up the thinking process in a short sentence:

If any x has property P, then all x have property P.

The salient point is that $x$ is chosen completely arbitrarily, i.e. $c$ is any $x$. If I can show that $P(c)$, I base this proof on absolutely nothing else, and so it must hold that $P(x)$ is true for all $x$. There can be no counterexample, because then I could not have shown $P(c)$ to begin with.

Solution 3:

When you prove a universal property, you pick an abstract (or generic) element $c$ from your domain, but cannot assume any additionnal property.

For example, if your domain is the natural numbers $\mathbb{N}$, you have defined a property $P(c)$ and want to show that $\forall n, P(n)$, you must prove $P(c)$ for a generic natural number $c$.

You don't get to chose $c$ : the second paragraph says that you cannot assume anything more on $c$ than it's a natural number. You cannot assume it is even, you cannot assume it is odd, you cannot assume it is $3$, you cannot assume it is prime, and so on. On the other hand, you can use the fact that $c \geq 0$, or that $c$ can be decomposed as a product of primes : these properties are true for any such $c$. Doing so, if you succeed in proving $P(c)$, you know that you can replace $c$ in your proof by any concrete natural number (say $3$) you want, and since you used only properties that are common to all natural numbers, this will provide you with a valid proof of $P(3)$.

This is exactly the meaning of $\forall n, P(n)$ is true.