Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 5.1.13 Universal Generalization

Universal Generalization: P(c/x) P is true for the specific value c

(which appears everywhere a more

general value x might appear).

∴ ∀x (P(x)) P is true for any value x.

Restrictions:

• c must not appear as a free variable in P(x).

• c is not mentioned in any hypothesis or undischarged assumption. (Recall that, to use the Conditionalization inference rule, we introduce one or more assumptions, reason with them, and then discharge them when we capture their effect by writing that they imply the conclusion. What we’re saying here is that we cannot generalize any variable that was arbitrarily introduced for that purpose but that has not yet been discharged.) In other words, c is an arbitrary element of the universe.

So, if P(c) holds for some arbitrary element c of the universe, we can conclude that it must in fact hold for any element. Thus we can conclude, ∀x (P(x)).

But we must be careful. If c represents some specific element of the universe that may have properties that other elements don’t have, then the generalization is not valid.

For example, recall our proof that Lucy is not a bird:

[1] x (Cat(x)  Bird(x)) Premise

[2] Cat(Lucy) Premise

[3] Cat(Lucy)  Bird(Lucy) Universal Instantiation [1]

[4] Bird(Lucy) Modus Ponens [2] , [3]

Notice that, on line [2], we had Cat(Lucy). But Lucy wasn’t an arbitrary element. It was a specific element about which we had a premise. So we cannot generalize [2] to conclude that everything in the universe is a cat.

This is what we have been calling new-rule-to-come-2.

Use of Universal Generalization usually occurs at the end of proofs for which the conclusion has a universally quantified statement. Before we can apply it, we must go back through our proof to make sure that the value that we are generalizing is in fact an arbitrarily chosen one.

We can now write out a complete proof, in our standard notation, of the Breathes syllogism. Note that the Hypothetical Syllogism rule that we use here is the same one we’ve been using since we started writing Boolean proofs.

[1] x (Student(x)  Person(x)) Premise

[2] x (Person(x)  Breathes(x)) Premise

[1a] Student(c)  Person(c) Universal Instantiation [1]

[2a] Person(c)  Breathes(c) Universal Instantiation [2]

[3a] Student(c)  Breathes(c) Hypothetical Syllogism [1a], [2a]

[3] x (Student(x)  Breathes(x)) Universal Generalization [3a]

Notice that when we apply Universal Instantiation, we can pick any value we like (after all, the claim is universal. So, in particular, if we apply it twice, we can choose the same value both times. That’s what we’ve done here. And that’s often what we want to do.

So now we’ve seen that Universal Instantiation and Universal Generalization, taken together, give us a way to prove traditional syllogisms. Alternatively, we could have introduced a special syllogism rule. Many logicians have done that. We chose to go our way, however, because it does more than solve the syllogism problem. It’s more general. The idea that we start a predicate logic proof by first moving into the Boolean world, doing what we need to do (however many steps that takes) and finally moving back to quantified statements is very powerful.

Suppose that we are given two premises:

[1] x ((P(x)  Q(x))  R(x))

[2] x (P(x))

We want to prove: x (Q(x)  R(x))

This seems as though it ought to be true. If P(x) is true of everything anyway, we shouldn’t have to worry about it. But is that so? Let’s see if we can prove it.

[1] x ((P(x)  Q(x))  R(x)) Premise

[2] x (P(x)) Premise

[3] (P(c)  Q(c))  R(c) Universal Instantiation [1]

We’ve chosen c as an arbitrary element of the universe. This is allowed. We know nothing else about it.

While we’re at it, let’s also instantiate our other premise, [2]. This time, we won’t instantiate to a new arbitrary element. We’ll instantiate to the specific element c that we already have. This is allowed. If P(x) is true for all x, it must, in particular, be true of c, regardless of what c is. Thus c is still an arbitrary element.

[4] P(c) Universal Instantiation [2]

Now we can work with [3] and [4] completely in the Boolean world, applying as many identities and rules as we need.

[5] (P(c)  Q(c))  R(c) Conditional Disjunction [3]

[6] (P(c) Q(c))  R(c) De Morgan [5]

[7] P(c)  (Q(c)  R(c)) Associativity of or [6]

[8] (Q(c)  R(c))  P(c) Commutativity of or [7]

[9] Q(c)  R(c) Disjunctive Syllogism [8], [4]

[10] Q(c)  R(c) Conditional Disjunction [9]

Now we’re close to the claim we’re trying to prove. The only issue is that we know that it’s true of the arbitrary element c. We want to show that it must be true for any element. But that’s easy; Universal Generalization will do that for us (precisely because c is arbitrary). So we have:

[11] x (Q(x)  R(x)) Universal Generalization [10]

We just proved our claim for arbitrary predicates P, Q, and R. But we can see why it might be useful if we give meanings to them. Define:

P(x): True if x is a person.

Q(x): True if x was born in the United States.

R(x): True if x is a citizen of the United States.

Then our original claim is that if you’re a person and you were born in the U.S., you’re a citizen of the U.S. Given an arbitrary universe, we need the restriction that you must be a person since cats and mice, although born in the U.S., are not citizens. But if we assume a universe of people (thus assuming that everything in question is a person), we can drop the explicit person requirement and say simply that if you’re born in the U.S., you’re a U.S. citizen.