Tag: math

Difficulty: What the hell

Today we move from baby predicate logic’s quantified-negation rules to the four quantifier rules themselves:

• universal instantiation (U.I.)
• universal generalization (U.G.)
• existential instantiation (E.I.)
• existential generalization (E.G.)

These are the rules that let you move between quantified statements and statements about particular individuals. And yes, this is also where flagging shows up and starts annoying people.

The basic idea

Predicate logic talks not just about whether P and Q are true, but about whether things are true of all individuals or of some individual. That is why we need quantifiers in the first place:

(∀x)Px = everything is P

(∃x)Px = something is P

The quantifier rules tell you when you are allowed to move from those quantified claims to singular claims like Pa, and when you are allowed to move back up again.

1. Universal Instantiation (U.I.)

U.I. is the easy one.

(∀x)Px

∴ Pa

If everything is P, then of course a is P. And likewise:

(∀x)(Px ⊃ Qx)

∴ Pa ⊃ Qa

Whatever is true of everything can be applied to any particular individual you like.

2. Existential Generalization (E.G.)

E.G. is also pretty easy.

Pa

∴ (∃x)Px

If a is P, then something is P. Likewise:

Pa • Qa

∴ (∃x)(Px • Qx)

If some particular individual has the relevant properties, then there exists at least one thing with those properties.

3. Existential Instantiation (E.I.)

This is where the mild irritation begins.

Suppose you know:

(∃x)Px

You are allowed to introduce a new name, say a, and write:

Pa

But only under a restriction: a has to be a new flagged name.

What does that mean? It means you are not allowed to pretend that the existential claim is about some already familiar individual. You are just saying: “Fine, let’s call the thing whose existence is guaranteed by the premise ‘a’.” But that ‘a’ is temporary and special. It is standing in for an arbitrary witness to the existential claim.

So E.I. looks like this:

(∃x)Px

∴ Pa     (a is a new flagged name)

Why the flag? Because if you are sloppy here, you can prove ridiculous garbage. Existential claims give you some individual, not necessarily one you were already talking about.

4. Universal Generalization (U.G.)

U.G. goes the other direction:

Pa

∴ (∀x)Px

But again, there is a restriction. You are only allowed to do this when a is a properly flagged arbitrary individual.

In other words, you cannot just notice that Socrates is mortal and then conclude that everyone is mortal. That would be insane. You need a to stand for an arbitrary individual, not a special one. If you prove something about an arbitrary individual, then you are allowed to generalize it to everybody.

So U.G. looks like this:

Pa     (a is arbitrary / properly flagged)

∴ (∀x)Px

So what the hell is flagging?

Flagging is just a way of marking a name as special for proof purposes.

There are two main uses:

• In E.I., the flagged name is a temporary witness to an existential claim.
• In U.G., the flagged name must be arbitrary if you want to generalize from it.

So the short version is:

• E.I. gives you a new flagged individual.
• U.G. requires an arbitrary flagged individual.

If you blur those roles, predicate logic becomes a mess very quickly.

How Q.N. and C.Q.N. fit in

Q.N. and C.Q.N. often help you get a quantified statement into a form where you can actually use the four quantifier rules.

For example, from:

¬(∃x)Px

you may first use Q.N. to get:

(∀x)¬Px

and only then use U.I. to get:

¬Pa

Likewise, from:

¬(∀x)(Px ⊃ Qx)

you may use C.Q.N. first to get:

(∃x)(Px • ¬Qx)

and then use E.I. to work with:

Pa • ¬Qa

So Q.N. and C.Q.N. are often what let the rest of the machinery start moving.

What students tend to screw up

• They instantiate an existential claim with a name that is not new.
• They generalize from a name that was never arbitrary.
• They forget that Q.N. and C.Q.N. often need to happen before the quantifier rules can be applied nicely.
• They panic when they see a flagged name and start pushing symbols around like a raccoon in a trash can.

Exercises

Now derive the indicated conclusions. These are not one-step gimmies. Each of them should take at least several steps if you do them cleanly.

Exercise 1

1. (∀x)(Px ⊃ Qx)

2. (∃x)Px

∴ (∃x)Qx

Exercise 2

1. (∀x)(Px ⊃ Qx)

2. (∀x)(Qx ⊃ Rx)

3. (∃x)Px

∴ (∃x)Rx

Exercise 3

1. ¬(∃x)Px

2. (∃x)Qx

∴ (∃x)(Qx • ¬Px)

Exercise 4

1. (∀x)(Px ⊃ Qx)

2. (∀x)(Qx ⊃ Rx)

∴ (∀x)(Px ⊃ Rx)

That last one is where the idea of an arbitrary flagged individual really starts to matter.

Next time, I’ll probably post the answers. Until then, try not to let the quantifiers and flags make you spiral.