Section Progress:

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 be 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 “a” not to refer to Alberto, or Alice, or Amelia, but to an arbitrary object that we don’t have particular knowledge about. And then we are able to prove P(a).

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(a=a).

Proof. Assume “a” is arbitrary. No matter what a is, we know a=a. 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 “a” is arbitrary. Then a is a cat or dog. (prem 1). Proof by cases: Case 1: say a is a cat. Then a is a mammal (prem 2). Case 2: say a is a dog. Then a is a mammal (prem 3). Since in both cases a is a mammal, we know a is a mammal. Since a was arbitrary, we know all pets are mammals (UG). Done.

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

31.1 Universal Generalization