# Proofs in Predicate Logic

So, you may be wondering why we move inside the simple statement with the machinery of propositional logic, and try to show the structure of the predication.

Consider that propositional logic cannot handle this argument (which categorical logic handles quite well): All dogs are mammals, and all mammals are animals, so all dogs are animals. Surprising, but true.

D / M / / A

is how you’d represent these three statements in propositional logic. There is no way to avoid judging that an invalid form. But in categorical logic, it’s your old friend Barbara.

And consider that categorical logic cannot handle an argument like this one: Paris is an ancient, beautiful French city, and any city that is either ancient or beautiful is a famous tourist destination, so Paris is a famous tourist destination.  Part of the problem is that “French” is in the predicate of one premise, but not part of the term in the other, and part of it is that one premise disjoins “ancient” and “beautiful” while the other one conjoins them.

But with the approach of predicate logic, we can integrate the two levels of analysis, and say:

1. Cp. (Bp . Ap)

2. (x) [(Cx . (Bx v Ax)) > Px] / Pp

What’s new is moving from a strict universal statement (x), to a case of that statement. In order to proceed into this argument completely, we’d have to be able to write that application of the universal to a case (which is called an instantiation of the universal).

If All ancient beautiful cities are popular is accepted, then

If Paris is ancient and beautiful, it’s popular is no more true than is

If Quantico is ancient and beautiful, it’s popular, or than

If Buffalo is ancient and beautiful, it’s popular.

These are all instances of that universal statement, and each of them is just as true as it is.

That notion of an instance is important to doing proofs in predicate logic. The other thing that’s especially important is realizing that the quantifiers (x) and (∃x) that stand in front of expressions in brackets or parentheses are the main operators of those expressions. They are said to govern those expressions that follow them (and this is like the way that a “~” governs the operator in an expression that follows it, as in ~(C v B), in which the tilde is affecting the wedge, not either of the two letters). Because of this, we need to be able to know when it is alright to disregard the quantifier; we do this by removing it and later putting it back on.

An Analogy that might help

If you’ve ever had a light switch on the wall stop working, then you probably learned that there are a couple of steps involved in fixing it. Once you’ve bought the new switch, you a) shut off the power to the switch, b) unscrew the screws that hold the faceplate on, c) remove the faceplate, d) pull out the switch, e) unscrew the screws that hold the wires on. Then you f) attach the new switch to the wires, g) push it into the wall, h) put on the faceplate, i) screw in the screws, and j) turn the power back on. A trivial and obvious set of steps –in one order, and then reversed.

I see an analogy between that series of steps and what we call in Logic:

Universal Instantiation (UI) (removing a universal quantifier) and Universal Generalization (UG)(putting a universal quantifier onto an expression).

Likewise there is the pair,

Existential Instantiation (EI) (removing an existential quantifier) and Existential Generalization(EG) (putting an existential quantifier onto an expression.)

In the argument above, we need to invoke UI, and when we do, we remove the quantifier, leaving the expression from line 2 looking like this (see line 3):

1. Cp. (Bp . Ap)

2. (x) [(Cx . (Bx v Ax)) > Px]

3. [Cx . (Bx v Ax)] > Px                UI 2

The x’s, or variables, are now called « free » because they are no longer governed by a quantifier. In a sense, you don’t know what the line says, it’s just a series of symbols; without that quantifier, you don’t know how to read it. That is one of two options you have when you remove a universal quantifier: you can just free up the variables. And that’s the right move to make if you think that later on you are going to want to put a universal quantifier back on. This is because the presence of free variables indicates that they were previously bound by a universal quantifier, so it will be appropriate to let them be subject to one again. But there is another choice, and this second one is the pertinent one to this case. Note that the conclusion is about Paris, not about “all cities.” So it will be more useful to instantiate the universal statement to:

4. [Cp . (Bp v Ap)] > Pp                     UI 2

This clearly reads “If Paris is either an ancient or beautiful city, then it’s popular.” This is called instantiating to a name (also called a “constant,” in contrast to “variables”). Constants are lower case letters a – p.

Given line 1, the conclusion follows immediately now:

5. Pp                            MP 4,1

I hope you can see how this is a merging of the logic of categories with the logic of propositions.

{Note: actually, that conclusion does not follow quite immediately, because line 1 contained a dot where line 4 has a wedge.  Intuitively, it is obvious that if the claim “these are both true” is true, then so is the claim “either one or the other of these is true.” To spell this out, we’ll need a series of quite trivial moves. We’d need to SM line 1 to Cp . Bp, using AS first.  Then SM to both Cp  and to Bp on separate lines, so we can use AD to get the wedge that line 4 has in it:  Bp v Ap. Finally CN this to Cp, and we have exactly the antecedent of line 4.  Here it is laid out in six trivial steps:

4.1  (Cp . Bp) . Ap     AS 1

4.2   Cp . Bp    SM  4.1

4.3   Cp        Sm   4.2

4.4   Bp        CM, SM 4.2

4.5    Bp v Ap      AD 4.4

4.6     Cp . (Bp v Ap)    CN 4.3, 4.5  }

The Rules Themselves

So UI (Universal Instantiation), written as a rule, says this:

(x) Fx  //  Fx   or   Fa

This means that removing a universal quantifier from an expression (which has to be the main operator of the line, by the way) can be done in either of two ways, replacing the formerly bound variable with a free one, or with a constant.

The rule called UG (Universal Generalization) allows you to put a universal quantifier onto an expression, binding the free variables, but it can only be done to expressions that have free variables:

Fx //  (x) Fx

For instance, you cannot move from

Tj . Tp (John and Paul are thieves) to

Tj    (John’s a thief) to

(x) Tx (everyone’s a thief)

But if you had Tx already, because of an earlier UI, the variable would be free, and UG would be allowed.

So that’s not so complicated; it’s like remembering to put the face plate back on the wall after you replace the switch.

Removing the existential quantifier is the same sort of thing. But it has this restriction: you have to replace the variable with a new constant (i.e., one that has not shown up at all in the premises or in the proof yet). You cannot replace it with a free variable (for the reason stated above about what a free variable signifies).

So as a form, the rule called EI looks like this:

(Эx) Fx  // Fb

Lastly, there are cases when you might be required to put an existential quantifier onto an expression -and there are no restrictions doing that. You can replace a constant or a free variable with an existentially quantified variable. So here’s EG as a rule:

Fa or   Fx  //  (Эx) Fx

An example :

All tenors are singers, and Placido Domingo is a tenor, so some people are singers.

1. (x) (Tx > Sx)

2. Td / (Эx) (Tx . Sx)

You have a choice about how to remove the universal quantifier, and the conclusion provides the answer : the conclusion is not a universal statement, but one about “some” individuals, so instantiate to the individual name.

3. Td > Sd UI 1

4. Sd MP 2,3

5. Td . Sd CN 2,4

6. (Эx) (Tx . Sx) EG 5

Proofs in Predicate Logic

Try translating these and working a proof for them:

1. Oranges are sweet. Oranges are citrus fruits. So oranges are sweet citrus fruits.

Since universals like this conclusion are written using the > operator, an approach to this proof is to use CP (conditional proof): assume the antecedent of the conclusion (without the quantifier), and add the quantifier by invoking UG after you arrive at the needed consequent)

2. Since tomatoes are vegetables, the tomatoes in the garden are vegetables.

3. Apples and pears grow on trees, so pears grow on trees.

4. Socrates is a man, and all men are mortal, so Socrates is mortal.

5. Carrots are vegetables and peaches are fruit. There are carrots and peaches in this garden. So there are vegetables and fruit in this garden.

6. Since there are no legumes in the garden, and beans and peas are legumes, there are no beans or peas in the garden.

7. Only philosophers are logicians, and anyone who’s a philosopher is a thinker. Frege and Russell are logicians, so they’re also thinkers.

8. If Wittgenstein invented truth tables, then there was no truth-table logic in the 19th century. If Quine refuted the dogma of the analytic/ synthetic distinction, then not all of Leibniz’s ideas are correct. Wittgenstein did invent them, and Quine has refuted the distinction, so not all of Leibniz’s idea are correct.

9. Some philosophers are idealists. Some scientists are materialists. If anyone is a philosopher, the scientists are skeptics if they are materialists. Therefore some scientists are skeptics.

10. If the artichokes in the kitchen are ripe, the guests will be surprised. If they are flavorful, the guests will be pleased. They are ripe and they are also flavorful, so the guests will be surprised as well as pleased.