2 of 2

31.1 Universal Generalization

In Chapter 29 you learned how to reason from a universal claim. You instantiate it for a specific name.

It worked the same way in formal proofs, with ∀Elim.

But how do you reason to a universal claim? For example, how would we prove that every object has some property P?

We can’t just prove P(a), and P(b), and P(c), etc., for every object in the domain, because the domain might be infinite.

For example, the domain could be the natural numbers, {0, 1, 2, 3, …}. We could never complete a proof that each one has the property, one at a time.

Arbitrary name: a name for an arbitrary member of the domain.

But there’s a solution: arbitrary names. An arbitrary name is a name which we declare to stand for an arbitrary member of the domain.

Say we decide to use “n” not to refer to Nick, or Nancy, or Neha, but to an arbitrary object that we don’t have particular knowledge about. And then we are able to prove P(n).

Universal Generalization (UG): inferring that something is true for all objects, once we prove that it is true for an arbitrary object.

Then we know that every object has property P. That inference is called Universal Generalization (UG).

For example, here’s how we can prove that every object is identical to itself: ∀x(x=x).

Proof. Assume “n” is arbitrary. No matter what “n” is, we know n=n. Thus for any object x, x=x (by UG). Done.

That proof is so simple, it might be hard to tell how Universal Generalization works in it.

Here’s an argument with premises. Say the domain is pets in the shelter right now.

1. All pets are cats or dogs.
2. All cats are mammals.
3. All dogs are mammals.
So,
4. All pets are mammals.

Here’s how the UG proof works.

Proof. Assume “n” is arbitrary. Then n is a cat or dog. (prem 1). Proof by cases: Case 1: say n is a cat. Then n is a mammal (prem 2). Case 2: say n is a dog. Then n is a mammal (prem 3). Since in both cases n is a mammal, we know n is a mammal. Since n was arbitrary, we know all pets are mammals (UG). Done.

Notice that the second-to-last maneuver you are already familiar with. The sentence “Since in both cases n is a mammal, we know n is a mammal” is doing proof by cases.

But the last inference is new: “Since n was arbitrary, we know all pets are mammals (UG).” That inference uses the fact that “n” is an arbitrary name.

The key idea to remember is that a UG proof starts with a temporary assumption: that some name will be arbitrary.

The key idea to remember is that a UG proof starts with a temporary assumption: that some name will be arbitrary.

We made that assumption first, before we made the temporary assumptions for the proof by cases.