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

Question

This is an excerpt from Discrete Mathematics.

Universal generalization is the rule of inference that states that ∀xP(x) is true, given the premise that P(c) is true for all elements c in the domain. Universal generalization is used when we show that ∀xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true. The element c that we select must be an arbitrary, and not a specific, element of the domain.

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.

I have two questions:

1. What is meant by the second paragraph ?

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).

Answer 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$.

Answer 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.

Answer 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.

Answer 4

The domain, by definition, is a group of elements that share certain properties. It's worth noting that the elements in a domain may have additional properties, which are not qualified in the definition of the domain. For instance, in the domain of Natural numbers, the property "is even" is an additional property pertained only by some of the elements and does not define the domain.

"x" means "any element within the domain", and therefore "any element possessing the properties qualifying the domain, but not only such properties". Setting the domain is the same thing as setting common properties for its elements. So a proposition "P" is only true for all "x" if it is a statement about a property contained in the definition of the domain.

"c" means "any x" and not "a specific x". That's important, because if "c" stands for "a specific x", such specific "x" would have the properties qualified by the domain and potentially some other properties not defined in the domain. From there, we could set a proposition "P" concerning a property held by this specific "x" wich may not be shared by other elements in the domain.In this case P(c) being true does not make P(x) true for all "x".

"c" meaning "any x" restricts valid statements only to those concerning properties shared by all "x". It is sort of a pure element, having no properties other than those common to all "x". If "P" holds for "c", it must also hold for all "X". In other words, the statement P(c) is true only if it states a property that all possible "x" have (a property contained in the definition of the domain).