CHAPTER 4 SECTION 1

Chapter Four Many-Place Predicates

In chapter 3 we studied the concept of formal validity in the Monadic Predicate Calculus, validity that is due to the logical forms that can be expressed using names, variables, connectives, quantifiers, and oneplace predicates. In this chapter the restriction to monadic (one-place) predicates is lifted. We are now focusing simply on Predicate Calculus formal validity: validity that is due to the logical forms that can be expressed using logical signs plus predicates of any number of places.

1 MANY-PLACE PREDICATES
In earlier chapters we used predicate letters that combine with one name to make a sentence: Antarctica is peaceful Fido is a giraffe Cynthia ran Pa Gf Rc

There are also expressions that combine with two names to form sentences: Andria is taller than Bill Cynthia is a friend of David Fred sees Bella or with three names, or more: Cary gave Fido to Andy Egbert sent Beatrice to Compton Fred drove Anna to Chicago with David To accommodate these expressions we use predicate letters that are followed by two or more names or variables enclosed in parentheses. Some examples with names are: Andria is taller than Bill Cynthia is a friend of David Fred sees Bella Cary gave Fido to Andy Egbert sent Beatrice to Compton T(ab) F(cd) S(fb) G(cfa) S(ebc)

These are atomic sentences, on a par with atomic sentences consisting of a single sentence letter or of a predicate letter followed by a name. They also occur with variables to form atomic formulas: Andria is taller than x x is a friend of y z sees Bella Cary gave x to y z sent u to v T(ax) F(xy) S(zb) G(cxy) S(zuv)

We can use any capital letter for a many-place predicate. You can tell whether a predicate letter is being used as a one-place predicate or a many-place predicate by seeing what follows it. If it is followed by a single name or variable, it is being used as a one-place predicate; if it is followed by a pair of parentheses containing two or more names or variables, it is being used as a many-place predicate. An atomic formula is now either a sentence letter alone, or a one-place predicate letter followed by a name or variable, or a many-place predicate letter followed by a pair of parentheses containing two or more names or variables. These new atomic formulas combine with connectives and quantifiers as in the previous chapter, yielding formulas such as:

Copyrighted material

Chapter 4 -- 1

Version of 21-Mar-11

CHAPTER 4 SECTION 1

xA(bx) yB(yy) x(Ax B(xd)) etc We are now using parentheses for two different purposes: to surround the terms following a many-place predicate symbol, and to surround molecular formulas. It is common to use either parentheses or square brackets for the latter purpose, and using square brackets instead of parentheses sometimes increases readability. So we will often write complex formulas as follows: x[Ax B(xd)] xy[[A(xy)B(yx)] A(yx)B(yx)] xF(ax) y[G(ay) G(yx)] Our official account of formulas is now: A sentence letter is any capital letter between 'P' and 'Z'. A one-place predicate is any capital letter between 'A' and 'O'. A many-place predicate is any capital letter between 'A' and 'Z'. An atomic formula is: a sentence letter alone, a one-place predicate letter followed by a name or variable, or a many-place predicate letter followed by a pair of parentheses containing two or more names or variables. If '' and '' are formulas, so are: () () () ~

x (Sentence letters, predicates, names, and variables may also occur with subscripts, as in F3(a2x7).) EXERCISES 1. Which of the following are formulas in official notation? Which are formulas in informal notation? Which are not formulas at all? a. b. c. d. e. f. g. h. i. ~~F(xa) [xG(bx) ~yG(yx)] xG(bx) ~yG(yx) ~Fa ~G(aa) ~Fb Gxb ~F(a) ~G(ab) ~Fa ~Gab ~x[~Fx yG(yy)] xy~Fxy xyF[xy]

()

Copyrighted material

Chapter 4 -- 2

Version of 21-Mar-11

CHAPTER 4 SECTION 2

2 SYMBOLIZING SENTENCES USING MANY-PLACE PREDICATES

Symbolizing sentences with many-place predicates mostly involves the same techniques as those we used earlier. For example, when there is one quantificational expression and a name, the symbolizations follow the same patterns as before. Some examples: Every giraffe is happy Every giraffe sees Fido Some dog is spotted Some dog loves Bobby x[Gx Hx] x[Gx S(xf)] x[Dx Sx] x[Dx L(xb)] x[Dx S(fx)] x[Dx L(bx)]

The pattern is similar when the name is the subject of the sentence: Fido sees every dog Bobby loves some dog

When there are two quantificational expressions, the translations may often be produced in stages: Some dog likes every cat Partial translation: x[Dx x likes every cat] y[Cy L(xy)] x[Dx x likes every cat ] x[Dx y[Cy L(xy)] ]

Then 'x likes every cat' is handled just as if 'x' were a name: x likes every cat The whole sentence then has the form: Some dog likes every cat

Some dog likes every cat Some additional examples are: Some dog chased a cat Some dog chased no cat Every dog chased a cat Every dog chased no cat

x[Dx x chased a cat] x[Dx x chased no cat] x[Dx x chased a cat] x[Dx x chased no cat]

x[Dx y[Cy H(xy)]] x[Dx ~y[Cy H(xy)]] x[Dx y[Cy H(xy)]] x[Dx ~y[Cy H(xy)]]

Some examples with three-place predicates: Some nurse gave a doll to a child x[Nx x gave a doll to a child] x[Nx y[Dy x gave y to a child]] x[Nx y[Dy z[Cz x gave y to z]]] x[Nx y[Dy z[Cz G(xyz)]]] No child gave a doll to a nurse ~x[Cx x gave a doll to a nurse] ~x[Cx y[Dy x gave y to a nurse]] ~x[Cx y[Dy z[Nz x gave y to z]]] ~x[Cx y[Dy z[Nz G(xyz)]]] Every child gave some doll to every nurse x[Cx x gave some doll to every nurse] x[Cx y[Dy x gave y to every nurse]] x[Cx y[Dy y[Ny x gave y to z]]] x[Cx y[Dy y[Ny G(xyz)]]] Sometimes in English the wording is unclear regarding which quantificational expression has wider scope; that is, which quantificational expression has the other within its scope. For example, the sentence:

Copyrighted material

Chapter 4 -- 3

Version of 21-Mar-11

CHAPTER 4 SECTION 2

Some freshman dated every sophomore can be read in two ways. One is the "super-dater" reading, which says that there is a certain freshman who dated every sophomore. Its symbolization is: x[Fx x dated every sophomore] x[Fx y[Oy D(xy)]] Here, the quantifier 'x' which originates from the 'some freshman' has widest scope, and the 'y' which originates from the 'every sophomore' is within the scope of 'x'. The other reading expresses the more natural situation, which merely says that for every sophomore, some freshman dated him/her: y[Oy some freshman dated y] y[Oy x[Fx D(xy)]] In this symbolization the 'y' which originates from the 'every sophomore' has widest scope, and the quantifier 'x' which originates from the 'some freshman' is within the scope of 'y'. A slightly more complicated example of this is: Every ambulance went to a location in a mall This could mean that all the ambulances went to the same location: y[My x[Lx I(xy) z[Az W(zx)]]] "there is a mall, and a location in it, and every ambulance went there" This gives the 'y' widest scope, and within its scope the 'x' has wider scope than the 'z'. Or it could mean that they were sent to locations in the same mall, though not necessarily to the same location: y[My z[Az x[Lx I(xy) W(zx)]]] "there is a mall and every ambulance was sent to some location in it" In this symbolization the 'y' still has widest scope, but the 'x' and 'z' are interchanged. Or it could merely mean that each ambulance was sent to some location in some mall: z[Az y[My x[Lx I(xy) W(zx)]]] "every ambulance is such that there is a mall and a location in it and the ambulance went there" In this symbolization the 'z' now has widest scope, and the 'x' is within the scope of the 'y'. All three symbolizations have the same ingredients; they differ with respect to how those ingredients are arranged. Certain words have as their main function indicating that the quantifier they occur with has a wide scope. An example is 'certain' in: Every reporter admired a certain car. The 'certain' gives the existential quantifier with 'car' wide scope: x[Cx y[Ey A(yx)]] The phrase 'the same' can also work in this way, as in: Every reporter admired the same car. x[Cx y[Ey A(yx)]] At every hoe-down the same fiddler played the same song x[fiddler x y[song y at every hoe-down x played y]] x[fiddler x y[song y z[hoe-down z x played y at z]]] x[Fx y[Gy z[Hz P(xy)]]] As in earlier chapters, some linguistic constructions have no obvious rationale in terms of their parts. An example is the medieval example 'No man lectures in Paris unless he is a fool'. Here are equivalent symbolizations (using 'L' for 'lectures in' and 'a' for 'Paris'): x[Mx ~L(xa)Fx] ~x[MxL(xa)~Fx]

Copyrighted material

Chapter 4 -- 4

Version of 21-Mar-11

CHAPTER 4 SECTION 2

EXERCISES 1. Symbolize each of the following: a. b. c. d. f. g. h. i. j. k. l. m. n. o. p. q. Hans sees every doctor but Amanda doesn't see any doctor. Hans, who owns a dog, doesn't own a cat. Hans loves Amanda but she doesn't love him. Neither Hans nor Amanda has a cat. Some hyena and some giraffe like each other. Some giraffe likes every baboon. Some giraffe that likes every baboon likes no hyena. Some giraffe likes every baboon that likes no hyena Some giraffe likes every baboon that likes it Eileen resides in a big city. <use 'R' for 'resides in'> Eileen and Betty both reside in the same city. If Hank resides in Brea then he attends UCLA; otherwise he doesn't attend UCLA. If David and Hank both live in Brea then David attends a private school and Hank attends a public school. Nobody who comes from Germany attends a California school. No giraffe likes Fido unless it is crazy Nobody gives a book to a freshman unless it is inexpensive

Copyrighted material

Chapter 4 -- 5

Version of 21-Mar-11

CHAPTER 4 SECTION 4

3 DERIVATIONS
Adding many-place predicates to the notation has no effect on the rules of inference; they are already adequate as they stand. Here are two examples, using familiar techniques. Any giraffe that is taller than Harriet is taller than every zebra. Some giraffes aren't taller than some zebras. So there is a giraffe that is not taller than Harriet. x[Gx T(xh) y[Ey T(xy)]] x[Gx y[Ey ~T(xy)]] x[Gx ~T(xh)] 1. Show x[Gx ~T(xh)] 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. Gu y[Ey ~T(uy)] Gu y[Ey ~T(uy)] Ev ~T(uv) Gu T(uh) y[Ey T(uy)] Show ~T(uh) T(uh) Gu T(uh) y[Ey T(uy)] Ev T(uv) T(uv) ~T(uv) pr2 ei 2s 2s 4 ei pr1 ui ass id 3 8 adj 6 9 mp 10 ui 5 s 11 mp 5 s 12 id 3 7 adj 14 eg dd

14. Gu ~T(uh) 15. x[Gx ~T(xh)]

Betty scolded every dog that chased a cat. Betty is a jeweler. Some dog that chased Cleo was grey. Cleo is a cat. So a jeweler scolded some grey dog. x[Dx y[Cy H(xy)] S(bx)] Jb x[Dx H(xc) Gx] Cc x[Jx y[Dy Gy S(xy)]] 1. Show x[Jx y[Dy Gy S(xy)]] 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Du H(uc) Gu Du y[Cy H(uy)] S(bu) H(uc) Cc H(uc) y[Cy H(uy)] Du Du y[Cy H(uy)] S(bu) Du Gu Du Gu S(bu) y[Dy Gy S(by)] Jm y[Dy Gy S(by)] x[Jx y[Dy Gy S(xy)] pr3 ei pr1 ui 2ss pr4 4 adj 5 eg 2ss 7 6 adj 8 3 mp 2 s 7 adj 9 10 adj 11 eg pr2 12 adj 13 eg dd

Copyrighted material

Chapter 4 -- 6

Version of 21-Mar-11

CHAPTER 4 SECTION 4

When existential quantifiers combine with universal ones, in general, a formula beginning with an existential followed by a universal is stronger than a universal followed by an existential. This simple derivation illustrates this: xyF(xy) yxF(xy) 1. Show yxF(xy) 2. 3. 4. 5. 6. Show xF(xy) yF(uy) F(uy) xF(xy) pr1 ei 3 ui 4 eg dd 2 ud something forces everything everything is forced by something

If we try to prove the reverse: yxF(xy) xyF(xy) we won't be able to. The obvious strategy would be to set up a universal derivation, trying to derive 'F(uy)' in order to show 'yF(uy)'. If we could do this, we could existentially generalize, and the derivation would be done. So we set things up for that: 1. Show xyF(xy) 2. Show yF(xy) 3. xF(xy) 4. F(uy)

pr1 ui 3 ei ud?????

But this is not in the right form for a universal derivation; there is an 'F(uy)' when a 'F(xy)' is needed. And there is no way to get 'F(xy)' from 'xF(xy)' by ei, since ei requires that the variable be new. One might naturally then try to derive the conclusion indirectly, by an indirect derivation: 1. Show xyF(xy) 2. ~xyF(xy) 3. x~yF(xy) 4. ~yF(xy) 5. y~F(xy) 6. xF(xy) 7. ?????????? ass id 2 qn 3 ui 4 qn pr1 ui

The problem at this point is that when one uses ei on lines 5 and 6, different variables need to be used, and there seems to be no way to derive a contradiction. In fact, the argument is invalid, and so no derivation will work. This will be shown in section 9.

Copyrighted material

Chapter 4 -- 7

Version of 21-Mar-11

CHAPTER 4 SECTION 4

STRATEGY HINTS: The strategy hints given at the end of chapters 2 and 3 remain unchanged.
They are repeated here for convenience. Try to reason out the argument for yourself. Begin with a sketch of an outline of a derivation, and then fill in the details. Write down obvious consequences. When no other strategy is obvious, try indirect derivation.

To derive:
Conjunction Disjunction Conditional Biconditional Negation of conjunction ~( ) Negation of disjunction ~( ) Negation of conditional ~( ) Negation of biconditional ~( )

Try this:
Derive each conjunct, and adjoin them Derive either disjunct and use add. (Often this is not possible.) Assume '~( )' for id and immediately use dm. Derive '~ ' and use cdj Use cd Derive both conditionals and use cb. Use id.

Derive '~ ~' and use dm.

Then use sc (applied to the assumed ' ' and the conditionals) to derive 'P~P'. Use id. Derive ' ~' and use nb.

Perhaps assume ' ' for id and try to derive both ' P~P' and 'P~P'.

If you have this available:

Conjunction Disjunction Conditional Biconditional Negation of conjunction ~( ) Negation of disjunction ~( )
Copyrighted material

Try this:
Simplify and use the conjuncts singly. Try to derive the negation of one of the disjuncts, and use mtp.. Derive the conditionals ' ' and ' ', where '' is something you want to derive. Then use sc with the disjunction and two conditionals. Try to derive the antecedent to set up mp, or derive the negation of the consequent, to set up mt. Infer both conditionals and use them with mp, mt, and so on. Use dm to turn this into '~ ~', and then try to derive either '' or '' to use mtp. Use dm to turn this into '~ ~'; then simplify and use the conjuncts singly.

Chapter 4 -- 8

Version of 21-Mar-11

CHAPTER 4 SECTION 4

Negation of conditional ~( ) Negation of biconditional ~( )

Use nc to derive ' ~', then simplify and use the conjuncts singly. Use nb to turn this into ' ~', and use bc to get the corresponding conditionals.

To derive:
Universal Quantification x

Try this:
Set up a universal derivation. Write a show line containing x, and then immediately follow this with a show line containing . When the second show is cancelled, use rule ud to cancel the first. Or write a show line with 'x', and then assume '~x' for an indirect derivation. Turn this into 'x~', and proceed from there.

Existential Quantification x Negation of a Universal Quantification ~x Negation of an Existential Quantification ~x

Derive an instance and then use rule eg. Or write a show line with 'x', and then assume '~x' for an indirect derivation. Turn this into 'x~', and proceed from there. State a show line with '~x', and then assume 'x' for an indirect derivation. Or derive 'x~' and apply derived rule qn. State a show line with '~x', and then assume 'x' for an indirect derivation. Or derive 'x~' and apply derived rule qn.

If you have this available:

Universal Quantification x Existential Quantification x Negation of a Universal Quantification ~x Negation of an Existential Quantification ~x

Try this:
Use rule ui to derive an instance. (But use rule ei first if that is an option.) Use rule ei to derive an instance. Use derived rule qn to turn this into an existential quantification.

Use derived rule qn to turn this into a universal quantification.

Use rule av if necessary: If you are having difficulty with capturing when you use rule ui or ei, change what you are trying to derive to an alphabetic variant. Complete the derivation, and then use derived rule av to convert this into a derivation of what you are after.

Copyrighted material

Chapter 4 -- 9

Version of 21-Mar-11

CHAPTER 4 SECTION 4

EXERCISES Show each of the following arguments to be valid. 1. xyz[S(xy) S(yz) S(xz)] S(bc) S(ab) S(ac) xy[Ax By [S(xy) ~S(yx)]] xy[Ax By [S(xy) S(yx)]] xyS(xy) xy[Cx S(xy) Dx] xy[Dx S(yx) Dy] ~x[Cx ~Dx] xEx x~Ex xy[Ex S(xy) Ey] xy~S(xy) xy[S(xy) S(yx)] xy[Ax By S(xy)] xy[By Ax S(xy)]] x[Ax y[By S(xy)]] xy[Bx Cy] x[Cx yS(yx)]

2.

3.

4.

5.

6.

7. Prove the following biconditional theorems.

T251 xyF(xy) yxF(xy) T252 xyF(xy) yxF(xy) T255 xyF(xy) yxF(yx)

<universal quantifiers permute> <existential quantifiers permute> <an application of av>

T261 x[yF(xy)yG(xy)] xyz[F(xy)G(xz)]

Copyrighted material

Chapter 4 -- 10

Version of 21-Mar-11

CHAPTER 4 SECTION 4

4 THE RULE "INTERCHANGE OF EQUIVALENTS"

Although no new rules are needed when many-place predicates are added, some new rules are convenient. One of these is called "Interchange of Equivalents". This rule allows us to change any part of a formula to a known equivalent part. For example, it allows us to change: x[Gx ~~H(xx)] into: x[Gx H(xx)] by changing the part '~~H(xx)' to the equivalent 'H(xx)'. We know that '~~H(xx)' is equivalent to 'H(xx)' because rule dn says so. This new rule is given by: Rule ie ("interchange of equivalents") <preliminary statement> any available line whose formula contains '' we may infer a line with the same formula but with If we have a rule stating that a certain formula '' is equivalent to another formula '', then from

'' changed to ''. The justification consists of writing 'ie' followed by '/' and the name of the rule giving the equivalence. A rule establishes that one formula is equivalent to another if the rule can be applied to either to infer the other. These rules all establish equivalents: dn nc cdj dm nb qn av <double negation> <negation of conditional> <conditional/disjunction> <demorgan's> <negation of biconditional> <quantifier negation> <alphabetic variation>

Plus any theorem that is biconditional in form. Here is an example of a derivation using the new rule: x[~ [Ax Bx) y~Hy] x[~Ax ~Bx ~yHy] 1. 2. 3. Show x[~Ax ~Bx ~yHy] x[~ [Ax Bx) ~yHy] x[~Ax ~Bx ~yHy] pr1 ie/qn 2 ie/dm dd

Step 2 uses one of the cases of quantifier negation to change 'y~Hy' in the premise to '~yHy'. Step 3 then uses a case of De Morgan's law to change '~ [Ax Bx]' on line 2 to '~Ax ~Bx'. This rule also works when the equivalence of the formulas being replaced is given to us by a premise or an earlier available line, as in this derivation: PQR S ~P S ~[QR] 1. Show S ~[QR] 2. 3. S ~[QR] S ~[QR] pr2 ie/pr1 2 bc dd

Here the first premise tells us that 'P' and 'QR' are equivalent, so on line 2 we may replace 'P' in the second premise by 'QR'. (Step 3 is already familiar.) A full statement of rule IE is:

Copyrighted material

Chapter 4 -- 11

Version of 21-Mar-11

CHAPTER 4 SECTION 4

Rule ie ("interchange of equivalents") any available line whose formula contains '' we may infer a new line with the same formula but If we have a rule stating that a certain formula '' is equivalent to another formula '', then from

with '' changed to ''. The justification consists of writing 'ie' followed by '/' and the name of the rule giving the equivalence. A rule establishes that one formula is equivalent to another if the rule can be applied to either to infer the other. These rules all establish equivalents: dn nc cdj dm nb qn av <double negation> <negation of conditional> <conditional/disjunction> <demorgan's> <negation of biconditional> <quantifier negation> <alphabetic variation>

Plus any theorem that is biconditional in form. Also: then from any available line whose formula contains '' we may infer a line with the same formula but with '' changed to ''. The justification consists of writing 'ie' followed by '/' and the name of the premise or line used. If we have a premise or available line that is a biconditional of the form ' ', or ' ',

EXERCISES In the following derivations, several lines appeal to the rule for interchanging equivalents. Say which of these lines are correct, and which incorrect. (In each case, when judging a given line assume that all previous lines are OK.) 1. PQR ~Q ~S P R ~Q 1. 2. 3. 4. 5. 6. 7. 8. Show R ~Q ~~P Q R ~~P P ~~P P ~S P ~Q R ~Q pr1 ie/dn 2 ie/pr2 3 ie/dn 4 ie/dn 5 add 6 ie/pr2 7 add dd

Copyrighted material

Chapter 4 -- 12

Version of 21-Mar-11

CHAPTER 4 SECTION 4

2.

xy[Ax R(xy)] zy[R(zy) S(yz)] x[[AxAx] Ax] Au 1. 2. 3. 4. 5. 6. 7. 8. 9. Show x[R(xx) ~Ax] y[Ax R(xy)] Au R(xu) R(xu) S(ux) Au S(ux) Au S(ux) Au Au [AuAu] Au Au pr1 ui 2 ei pr2 ui ui 4 ie/3 3 ie/4 5 ei/6 pr3 ui 7 ie/8 dd

Copyrighted material

Chapter 4 -- 13

Version of 21-Mar-11

CHAPTER 4 SECTION 5

5 BICONDITIONAL DERIVATIONS
When proving a biconditional informally, people sometimes give a string of equivalences. For example, to show informally that this is a theorem: ~P ~~Q ~[P ~Q] one might reason as follow: By double negation, '~P ~~Q ' is equivalent to '~P Q', and by De Morgan's laws, that is equivalent to '~[~~P ~Q]', and again by double negation, that is equivalent to '~[P ~Q]'. So the first (namely '~P ~~Q') is equivalent to the last (namely, '~[P ~Q]'). You can establish a biconditional by showing that one of its sides is equivalent to something, which is equivalent to some further thing, etc, ending up with the other side of the biconditional. This idea can be implemented by means of a new technique, called "biconditional derivation". It goes as follows: Biconditional Derivations a line containing either '', or '', justified by the notation 'ass bd' (meaning, "assumption for a biconditional derivation"). Any show line with a biconditional formula ' ' may be followed by an assumption consisting of

A derivation may be continued so that each additional step follows from the immediately preceding step by rule IE, so that eventually you reach a line containing '' or '' (whichever was not on the assumption line). Then 'bd' may be written at the end of the last line; box all lines starting with the assumption line, and cancel the 'show'. (Alternative: As usual, you may end the derivation by writing an empty line following the line containing '' or '', writing the line number of the previous line and 'bd'; then you box and cancel.) Here is a derivation for the example above: ~P ~~Q ~[P ~Q] 1. Show ~P ~~Q ~[P ~Q] 2. 3. 4. 5. ~P ~~Q ~P Q ~[~~P ~Q] ~[P ~Q] ass bd 2 ie/dn 3 ie/dm 4 ie/dn bd

Line 1 contains the biconditional to be shown. Line 2 assumes its left-hand side for the purpose of a biconditional derivation. Lines 3-5 make inferences of formulas equivalent to that on line 2. Since this series of IE steps ends up with the right-hand side of the biconditional on the show line, we conclude the derivation, boxing and canceling. The alternative form of the derivation is to delay until line 6 the "bd" justification with boxing and cancelling: 1. Show ~P ~~Q ~[P ~Q] 2. 3. 4. 5. 6. ~P ~~Q ~P Q ~[~~P ~Q] ~[P ~Q] ass bd 2 ie/dn 3 ie/dm 4 ie/dn 5 bd

Copyrighted material

Chapter 4 -- 14

Version of 21-Mar-11

CHAPTER 4 SECTION 5

This new derivation technique is not essential, since whatever we can do with it we can also do without it. But doing without it requires a longer derivation -- sometimes a much longer derivation. In particular, we can always derive the biconditional by giving two conditional derivations, followed by an application of rule cb. Following this pattern, we can convert the above derivation to one without rule bd as follows: 1. Show ~P ~~Q ~[P ~Q] 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Show ~P ~~Q ~[P ~Q] ~P ~~Q ~P Q ~[~~P ~Q] ~[P ~Q] ~[P ~Q] ~[~~P ~Q] ~P Q ~P ~~Q ass cd 3 ie/dn 4 ie/dm 5 ie/dn cd

Show ~[P ~Q] ~P ~~Q ass cd 8 ie/dn 9 ie/dm 10 ie/dn cd 2 7 cb dd

12. ~P ~~Q ~[P ~Q]

Clearly, using biconditional derivation simplifies matters considerably. (The derivation could also be done without any use of rule ie as well; this would make it much longer.) It is important when applying rule bd that every step after the assumption is justified by rule ie. If other rules are used, then even though every line follows correctly by an established rule, one cannot apply rule bd to box and cancel. This is because bd derives an equivalence, and so only lines that infer equivalences of previous lines are permitted. For example, the last line of this derivation is incorrect: ~P ~~Q ~P 1. Show ~P ~~Q ~P 2. 3. 4. 5. ~P ~~Q ~P Q ~P ass bd 2 ie/dn 3s 4 bd <Invalid argument>

incorrect

Line 5 is incorrect because a rule other than ie is used to get line 4 from line 3. The derivation is thus incorrect -- which is good, since the sentence that it purports to derive from no premises is not a tautology; it is false when 'P' and 'Q' are both false.

EXERCISES 1. Prove the biconditional above without using a biconditional derivation and also without using the rule for interchange of equivalents: ~P ~~Q ~[P ~Q] 2. Prove the following, using a biconditional derivation.

T250 xyzF(xyz) ~xyz~F(xyz) <a generalization of qn>

Copyrighted material

Chapter 4 -- 15

Version of 21-Mar-11

CHAPTER 4 SECTION 6

6 SENTENCES WITHOUT OVERLAY OF QUANTIFIERS

When showing invalidities in chapter 3 we saw that it is sometimes difficult to assess the truth values of formulas, particularly when their quantifiers have overlapping scopes, although when the quantifiers do not have overlapping scopes it is easy. For example, given that Agatha is happy but not carefree, and that Beatrice is carefree but not happy, and that they are the only two things in the universe, it is easy to evaluate certain kinds of quantified formulas, such as: xHx x~Hx xCx yHy but this is harder to assess: xy[Cx Hy] This sentence is true. It's true because for anyone you choose, either they're carefree, and there's someone who is happy, and the biconditional is true, or they aren't carefree, and there's someone who isn't happy, and again the biconditional is true true, because Agatha is happy true, because Beatrice isn't happy false because 'xCx' is true, and 'yHy' is false

The point is that when one quantifier falls inside the scope of another, especially if one quantifier is universal and the other existential, it is a sophisticated matter to decide whether the sentence is true or not. This is why truth-functional expansions of formulas, although complex and artificial to produce, can sometimes be helpful in deciding what is true and what is false in a counter-example. For sentences containing only monadic predicates, there is a way to eliminate the problem cases entirely. This is because when there are no many-place predicates, every formula is provably equivalent to one in which no quantifier falls within the scope of another quantifier. (This is sometimes described as a formula "without overlay", where 'overlay' refers to a situation in which one quantifier contains another within its scope.) The proof of this in any given case can be developed using what in chapter 3 were called laws of confinement. Here are some confinement laws, repeated from the previous chapter: Derived Rule conf <confinement> 'conf' refers to any use of any of the following theorems. T215 T216 T217 T218 T219 T220 T221 T222 x[PFx] PxFx x[PFx] PxFx x[PFx] PxFx x[PFx] PxFx x[PFx] [PxFx] x[PFx] [PxFx] x[FxP] [xFxP] x[FxP] [xFxP] or or or or x[FxP] xFxP x[FxP] xFxP x[FxP] FxP x[FxP] xFxP

These laws may be applied for any sentence letter in place of 'P', or for any formula that has no free occurrence of 'x' in place of 'P'. They are called "confinement" laws because when 'x' is not free in 'P', a quantifier governing the whole molecular formula may be confined to one part of the formula. These laws are very useful when used in conjunction with a few other derived rules for commutativity, associativity, distribution, quantifier distribution, and biconditional expansion. Derived Rule com <commutativity> 'com' refers to any use of any of the following theorems. T24 T53 T92 PQ QP PQ QP (PQ) (QP)

Copyrighted material

Chapter 4 -- 16

Version of 21-Mar-11

CHAPTER 4 SECTION 6

Derived Rule assoc <associativity> 'assoc' refers to any use of any of the following theorems. T25 T54 T94 P (QR) (PQ) R P (QR) (PQ) R (P (QR)) ((PQ) R)

Derived Rule dist <distribution> 'dist' refers to any use of any of the following theorems. T61 T62 T116 T117 P (QR) (PQ) (PR) P (QR) (PQ) (PR) (PQ) (RS) (PR) (PS) (QR) (QS) (PQ) (RS) (PR) (PS) (QR) (QS)

Derived Rule qdist <quantifier distribution> 'qdist' refers to any use of either of the following theorems. T207 T208 x(Fx Gx) xFx xGx x(Fx Gx) xFx xGx

Derived Rule bex <biconditional expansion> 'bex' refers to any use of either of the following theorems. T81 T83 (PQ) (PQ) (QP) (PQ) (PQ) (~P~Q)

Derived Rule vac <vacuous quantification> 'vac' refers to any use of either of the following theorems. T227 T228 xP P xP P

Suppose, for example, we are given the sentence 'xy[Px Qy]'. We can prove that this is equivalent to the sentence 'xPx yQy'. We do so using a biconditional derivation, using the confinement laws with commutativity: xy[Px Qy] xPx yQy 1. 2. 3. 4. Show xy[Px Qy] xPx yQy xy[Px Qy] x[Px yQy] xPx yQy ass bd 2 ie/conf 3 ie/conf bd

Another example: We can eliminate the overlay in: x[yPy z[Qz Rx]] as follows:

Copyrighted material

Chapter 4 -- 17

Version of 21-Mar-11

CHAPTER 4 SECTION 6

1. Show x[yPy z[Qz Rx]] [yPy zQz xRx] 2. 3. 4. 5. x[yPy z[Qz Rx]] yPy xz[Qz Rx] yPy x[zQz Rx] yPy zQz xRx ass bd 2 ie/conf 3 ie/conf 4 ie/conf bd

Any formula with no many-place predicates can be transformed into a logically equivalent formula in which there is no quantifier overlay. Here is a simple routine for doing so: First, replace all biconditionals in the formula by combinations of formulas without biconditional signs. For example, convert 'PQ' into '[PQ][~P~Q]' using the ie/bex. Then turn all conditionals into disjunctions using ie/cdj. For example, convert 'PQ' into '~PQ'. Whenever a quantifier immediately precedes a negation, apply ie/qn to move the quantifier to the right. When a quantifier immediately precedes a conjunction or disjunction, you may be able to move the quantifier inside the conjunction or disjunction using ie/conf or ie/qdist. For example, using ie/conf: x[PFx] x[PFx] x[PFx] x[PFx] x[GxFx] x[GxFx] becomes becomes becomes becomes P xFx P xFx P xFx P xFx xGx xFx xGx xFx

And using ie/qdist: becomes becomes

If ie/conf does not apply, and you have a universal quantifier immediately preceding a disjunction, or an existential quantifier immediately preceding a conjunction, you will often be able to modify the disjunction or conjunction using ie/dist. If a universal quantifier precedes a disjunction, use ie/dist to turn the disjunction into a conjunction, and ie/qdist then applies; if an existential quantifier precedes a conjunction, use ie/dist to turn the conjunction into a disjunction, and ie/qdist then applies. Examples: x[Fx[GxyHy]] x[Fx [GxyHy]] becomes by ie/dist becomes by ie/dist x[[FxGx][FxyHy]] and then ie/qdist applies x[[FxGx][FxyHy]] and then ie/qdist applies

Sometimes it may be necessary to use ie/assoc before applying one of the above rules. For example, suppose you are given 'x[Fx[GxyHy]]'. Then none of the above rules apply. But the conjuncts may be reordered: x[Fx[GxyHy]] becomes by ie/assoc x[[FxGx]yHy] and then ie/conf applies.

Finally, a quantifier may end up having scope over another when it is actually binding nothing at all, as in 'xyFy'. In this case rule ie/vac just lets you drop the quantifier that isn't binding anything: xyFy becomes by ie/vac yFy

Copyrighted material

Chapter 4 -- 18

Version of 21-Mar-11

CHAPTER 4 SECTION 6

The good news is that if a formula contains no many-place predicates it is provably equivalent to a formula without overlay, and formulas without overlay are often much easier to assess. The bad news is that when a formula contains at least one many-place predicate, no such equivalence is guaranteed. There are plenty of examples of formulas that are not equivalent to any without overlay. Here are two: xyF(xy) yxF(xy) Suppose that 'F' stands for loving, and that we are discussing a universe consisting only of people. Then the first says that everyone loves someone, and the second says that there is someone loved by everyone. There is no simpler way to symbolize either of these.

EXERCISES 1. For each of the following formulas, find an equivalent formula which has no overlay of quantifiers, and prove that it is equivalent. (The derivations are easiest using biconditional derivations.) a. b. c. d. e. z[u[Pu Qz] Pz] zx[Px Pz] xPx y~Qy x[x[Px Qx] [Px Qx]] xyz[Px Qz Pz Qy]

Copyrighted material

Chapter 4 -- 19

Version of 21-Mar-11

CHAPTER 4 SECTION 7

7 PRENEX NORMAL FORMS

A formula is in prenex normal form when all of its quantifiers are in a string on the front of the formula, with each quantifier having scope over everything to its right. These formulas are in prenex normal form: xyzu~[P(xy) Q(yz)] xyz[R(xz) ~S(zy)] x[Hx Gx Ky] These are not: xyz~u[P(xy) Q(yz)] xy[R(xz) ~zS(zy)] xyR(xy) Gy 'u' is not part of the string of quantifiers on the front 'z' is not part of the string of quantifiers on the front 'x' and 'y' do not have scope over the whole formula

Every formula that we can express is logically equivalent to one that is in prenex normal form. In fact, any formula can easily be converted into prenex normal form. That is, any formula can be transformed into a logically equivalent formula which is in prenex normal form. Here is a routine for doing so: First, replace all biconditionals by combinations of formulas without biconditional signs. For example, convert 'PQ' into '[PQ] [QP]' or '[PQ][~P~Q]' using the derived rule ie/bex. Second, use ie/av to change bound variables within the formula so that every quantifier uses a different variable, and so that no quantifier uses the same variable as one that occurs free in the original formula. For example, convert 'x[Hx Jy yK(xy)]' into 'x[Hx Jy wK(xw)]'. Now move each quantifier to the front of the formula by a series of steps in accordance with these patterns: If the quantifier is immediately preceded by a negation, move the quantifier to the left of the negation, changing the quantifier from existential to universal, or vice versa. This step is justified by ie/qn. ~x ~x becomes becomes x~ x~

The remaining patterns appeal to the confinement laws. If the quantifier is on the front of a disjunct, move the quantifier to the front of the whole disjunction. This rule is justified by ie/conf. P xFx xFx P P xFx xFx P becomes becomes becomes becomes x[P Fx] x[Fx P] x[P Fx] x[Fx P]

If the quantifier is on the front of a conjunct, move the quantifier to the front of the whole conjunction, having scope over it. This rule is justified by ie/conf. P xFx xFx P P xFx xFx P becomes becomes becomes becomes x[P Fx] x[Fx P] x[P Fx] x[Fx P]

If the quantifier is on the front of a consequent of a conditional, move the quantifier to the front of the conditional, having scope over it. This rule is justified by ie/conf. P xFx P xFx becomes becomes x[P Fx] x[P Fx]

If the quantifier is on the front of an antecedent of a conditional, move the quantifier to the front of the conditional, having scope over it, changing the quantifier from existential to universal, or vice versa. This rule is justified by ie/conf. xFx P xFx P
Copyrighted material

becomes becomes

x[Fx P] x[Fx P] Chapter 4 -- 20

Version of 21-Mar-11

CHAPTER 4 SECTION 7

The moves above are to be made first using a quantifier that is not within the scope of any other quantifier; this quantifier migrates to the very front of the formula. Then any remaining quantifier that is not within the scope of any remaining quantifier migrates to a point just to the right of the previous quantifier, and so on until all quantifiers are moved to the prenex string. Notice that once biconditionals have been eliminated, the remaining quantifier moves leave the internal molecular structure of the formula intact. For example, if the quantifiers were erased, this would be a conditional with a conjunction as antecedent and a disjunction as consequent. yx[Fx Gy] z[Hz uS(zu)] When the quantifiers are moved to the front, the internal structure actually is a conditional with a conjunction as antecedent and a disjunction as consequent: yx[Fx Gy] z[Hz uS(zu)] y[ x[Fx Gy] z[Hz uS(zu)] ] yx[ Fx Gy z[Hz uS(zu)] ] yx z[ Fx Gy [Hz uS(zu)] ] yx z[ Fx Gy u[Hz S(zu)] ] yx z u[ FxGy HzS(zu) ] conditional with a conjunction as antecedent and disjunction as consequent The process described above may sometimes be applied in more than one way. For example, in xHx yKy neither quantifier is within the scope of the other, and so either one may be moved first. The two options are: xHx yKy x[Hx yKy] xy[Hx Ky] xHx yKy y[xHx Ky] yx[Hx Ky] The two resulting formulas are not the same; they differ in having an existential and a universal quantifier permuted. Generally such permutation produces nonequivalent formulas, but in this special case they are equivalent. A proof of the equivalence in this case can be produced by giving a biconditional derivation in which one starts with one of the forms, goes back by stages to the original formula, and then moves to the other form, like this: yx[Hx Ky] xy[Hx Ky] 1. 2. 3. 4. 5. 6. Show yx[Hx Ky] xy[Hx Ky] yx[Hx Ky] y[xHx Ky] xHx yKy x[Hx yKy] xy[Hx Ky] ass bd 2 ie/conf 3 ie/conf 4 ie/conf 5 ie/conf

bd

Copyrighted material

Chapter 4 -- 21

Version of 21-Mar-11

CHAPTER 4 SECTION 7

EXERCISES 1. The following theorems resemble the last example from the text above. Prove them. T263 xy[FxGy] yx[FxGy] T264 xy[FxGy] yx[FxGy] T265 xy[FxGy] yx[FxGy] T266xyz[FxGyHz] yzx[FxGyHz] 2. Put each of the following formulas into prenex normal form. In each case give a biconditional derivation that shows that the prenex form is equivalent to the original formula. a. b. c. d. xyP(xy) uP(uu) x[uR(ux) uR(xu)] xyA(xy) xyA(yx) xy[R(xy)R(yx)]

Copyrighted material

Chapter 4 -- 22

Version of 21-Mar-11

CHAPTER 4 SECTION 8

8 SOME THEOREMS
Here are a few theorems that are of special interest. T249 xyF(xy) xyF(xy) T253 xyF(xy) yxF(xy) T254 xyF(xy) xy[F(xy) F(yx)] T256 xy[F(xy)Gy] xy[F(xy)Gx] T259 xz[Fx y[GyHz]] [xFxxGx xHx] T260 X[Fx y[Gy [HyHx]]] x[GxHx] ~xFx [xGxx[FxHx]] T262 y[xF(xy)Gy] yxz[[F(xy)Gy] [GyF(zy)] The following theorems are of interest in the application in which 'M' stands for set membership; that is, where 'M(xy)' means that x is a member of the set y. (We also read this as saying that set y "contains" x.) In what is generally called "nave" set theory, it is assumed that there is a set corresponding to any condition you can express. For example, there is a set, x, whose members are things that are giraffes: xz[M(zx) Gz] There is also a set whose members are all the things that aren't giraffes: xz[M(zx) ~Gz] Likewise, there is a set whose members are themselves sets which contain at least one giraffe: xz[M(zx) y[Gy M(yz)]] There is a set that contains every set that contains something that contains something: xz[M(zx) yu[M(uy) M(yz)]] In the early 1900's, Bertrand Russell considered the set whose members don't contain themselves. Nave set theory says that there must be a set which contains exactly the sets that do not contain themselves: xz[M(zx) ~M(zz)] This purported set is called "the Russell set". Russell (among others) showed that there can't be a Russell set. You can show this also. Just construct an easy derivation for this theorem which denies that there is a Russell set: T269 ~yx[M(xy)~M(xx)] <a Russell set does not exist> <a generalization of T238> <a "quantifier switch". Note that the quantifiers do not switch in the opposite direction>

A "Russell subset" of a set w is that set which contains all and only those subsets of w which are not members of themselves. Generally, there is no problem about there being a Russell subset of a set. But one can show that if every set has a Russell subset, then there is no universal set; that is, there is no set which contains everything:
T270

zyx[M(xy) M(xz)~M(xx)] ~zxM(xz)

<if "Russell subsets" always exist, there is no universal set>

Copyrighted material

Chapter 4 -- 23

Version of 21-Mar-11

CHAPTER 4 SECTION 8

Here are two more general statements about sets: T271 ~yx[M(xy) ~z[M(xz)M(zx)]] <there is no set whose members include a thing if and only if it has no member which it is a member of>

T272 yx[M(xy)M(xx)] ~xyz[M(zy)~M(zx)] <if there is a set of all sets that are members of themselves, not every set x has another set whose members are all the things that are not members of x>

EXERCISES Prove the theorems above.

Copyrighted material

Chapter 4 -- 24

Version of 21-Mar-11

CHAPTER 4 SECTION 9

9 SHOWING INVALIDITY
The introduction of many-place predicates requires some refinements in our technique for showing predicate calculus invalidity. The fundamental idea remains the same: describe a possible situation in which the premises of an argument of the given form are all true and the conclusion false. But the presence of many-place predicates brings with it two complications, a simple one and a complex one. The simple complication is due to the fact that when we interpret a many-place predicate there are combinations of things in the universe to take into account. For example, consider this argument: xyF(xy) yxF(xy) Suppose we consider a situation in which exactly three things exist; in particular, our universe is {0, 1, 2}. Previously, for a given predicate we needed to choose for each entity, 0, 1, and 2 whether or not it was in the extension of the predicate. But two-place predicates don't have extensions of that sort; it makes no sense to ask which individual things a two-place predicate is true of. This is because a two-place predicate holds of pairs of things. So we need to say which pairs of things are in the extension of each predicate. For example, we might decide that 'F' holds of the following pairs: <0,1>, <1,2>, <2,0> We indicate these choices by writing: COUNTER-EXAMPLE Universe: {0, 1, 2} F: {<0,1>, <1,2>, <2,0>} With these choices the first premise is true, because for each thing in the universe, 'F' relates it to something: 'F' relates 0 to 1, and 1 to 2, and 2 to 0. But the conclusion is false, because there is nothing in the universe that 'F' relates to everything. 0 won't do because it isn't related to 2, and 1 won't do because it isn't related to 0, and 2 won't do because it isn't related to 1. This counter-example shows that the argument is not valid in the predicate calculus. Another example: x[Fx yR(xy)] Fa Fb R(ab) R(ba) COUNTER-EXAMPLE: Universe: {0, 1, 2} a: 0 b: 1 F: {0,1} R: {<0,2>, <1,2>} With these choices the first premise is true because the things that are F are 0 and 1, and the things that bear relation R to something are also 0 and 1. The second premise is true because both 'a' and 'b' stand for things in the extension of 'F'. And the conclusion is false because R does not relate 0 to 1, or 1 to 0. As in the previous chapter, if it is difficult to assess the truth of sentences in a finite model, one may be able to produce an equivalent truth-functional expansion. Here is an example; suppose that you want to show the invalidity of this argument: xyzR(xyz) xzyR(xyz) The following counter-example is proposed, in which the three-place relation R has an extension consisting of triples: Universe: {0,1} R: {<0,0,1>, <0,1,0>, <1,0,1>, <1,1,0>}
Copyrighted material

Chapter 4 -- 25

Version of 21-Mar-11

CHAPTER 4 SECTION 9

Then the premise is true and the conclusion false. But this may not be obvious. If so, one may expand the premise and conclusion as follows. Suppose that a0 stands for 0 and a1 for 1. Begin with the premise. Eliminating its first (universal) quantifier we get the conjunction: yzR(a0yz) yzR(a1yz) Eliminating the next universal quantifier in each conjunct gives a four-part conjunction: zR(a0a0z) zR(a0a1z) zR(a1a0z) zR(a1a1z) Finally, eliminating the existential quantifiers in each conjunct gives the following sentence: [R(a0a0a0) R(a0a0a1)] [R(a0a1a0) R(a0a1a1)] [R(a1a0a0) R(a1a0a1)] [R(a1a1a0) R(a1a1a1)] The atomic sentences are now easy to evaluate. For example, we know that 'R(a0a0a0)' is false because <0,0,0> is not in the extension of F. And 'R(a0a0a1)' is true because <0,0,1> is in the extension of F. And so on. Each disjunctive conjunct is true, so the premise is true: [R(a0a0a0) R(a0a0a1)] [R(a0a1a0) R(a0a1a1)] [R(a1a0a0) R(a1a0a1)] [R(a1a1a0) R(a1a1a1)] F T T F F T T F T T T T

Regarding the conclusion, eliminating its first (universal) quantifier we get the conjunction: zyR(a0yz) zyR(a1yz) Now eliminating the initial existential quantifiers in each conjunct, we get: [yR(a0ya0) yR(a0ya1)] [yR(a1ya0) yR(a1ya1)] Finally, eliminating the remaining universal quantifiers we get the following sentence, which is a twoconjunct conjunction each of whose conjuncts is a disjunction of conjuncts. [[R(a0a0a0) R(a0a1a0)] [R(a0a0a1) R(a0a1a1)]] [[R(a1a0a0) R(a1a1a0)] [R(a1a0a1) R(a1a1a1)]] Assessing the atomic sentences as above yields these truth values: [[R(a0a0a0) R(a0a1a0)] [R(a0a0a1) R(a0a1a1)]] [[R(a1a0a0) R(a1a1a0)] [R(a1a0a1) R(a1a1a1)]] F T T F F T T F F F F F

The disjuncts are all false, so each conjunct is false, and the conclusion is false. EXERCISES 1. Give counter-examples to show that each of the following arguments are invalid in the predicate calculus. a. x[Fx y[Gy R(xy)]] x[Gx ~R(xx)] x[Fx y[Gy R(xy)]] b. c. x[F(xa) G(xb)] xy[F(xy) G(xy)] x[Hx R(ax)] xy[R(xy) R(yx)] yxR(xy) x[Fx yR(xy)] x[~Fx yR(yx)] xy[R(xy) R(yx)] xy[F(xy) z[G(xz) ~G(yz)]] xy[F(xy) F(yx)] xy[G(xy) G(yx)]

d.

e.

Copyrighted material

Chapter 4 -- 26

Version of 21-Mar-11

CHAPTER 4 SECTION 9

Infinite Universes: The second complication to our technique arises only in some cases. It has to do with infinite universes. Consider the following argument: xyR(xy) xyz[R(xy) R(yz) R(xz)] xR(xx) The first premise says that each thing is related by R to something. The second says that relation R is transitive: if something is related by R to something else, and that something else is related to a further thing, the first thing must be related to this further thing. Finally, the conclusion says that something is related by R to itself. This argument is invalid, but this cannot be shown using a counter-example with a finite universe. Instead, we have to devise a counter-example using an infinite universe. Here is why a finite universe will not work. Consider an attempt to create a counter-example using a finite universe. Let us start with the smallest choice: there is only 0. Now by the first premise, 'R' relates 0 to something. Since 0 is all there is, in order to make the first premise true, 'R' must relate 0 to 0. But then the conclusion will be true. So a one-element universe won't do. OK, let's try two things, 0 and 1. Again, 'R' must relate 0 to something. It can't relate 0 to 0, as we saw above. So 'R' must relate 0 to 1. Looking at the first premise again, 'R' must relate 1 to something. It can't relate 1 to 1, for the same reason as before; making the conclusion false forbids anything being related to itself. So 'R' must relate 1 to 0. Fine. But now the second premise comes into play. The second premise says that 'R' is transitive: if it relates one thing to a second, and that second to a third, it relates the first to the third. But it does relate one thing (0) to a second thing (1), and it relates that second thing (1) to a third thing (0), so it must now relate the first (0) to the third (0). Which is ruled out by the third premise. (You might think that this reasoning doesn't work, since we have talked about a "first" thing and a "second" thing, and a "third" thing. And in the application we used, we made 0 be the "third" thing. But there are only two of them: 0 and 1, and so it seems wrong to talk of a third thing. The answer to this objection is that this use of 'first', 'second', and 'third' is just a manner of speaking that is used in natural language to keep track, not of three things, but of three variables. There aren't any variables in English so we speak in this way. This usage can be avoided if we argue as follows: "The second premise says that 'R' is transitive: if it relates one thing, x, to a thing, y, and it relates thing, y, to a thing, z, then it relates thing x to thing z. But it relates one thing, 0, to 1, and it relates 1 to 0, so it must now relate 0 to 0. Which is ruled out by the required falsehood of the conclusion.") Trying three things won't work either. The premises require that 0 is related to 1, and 1 to something else, 2, but then 2 must be related to something. Not to itself, because we need the conclusion to be false, and not to either 0 or 1, because the reasoning given above reapplies. And so on. These premises require that each thing is related to something new, and so on ad infinitum ("to infinity"). We therefore need to consider a situation in which there are an infinite number of things, say, all of the integers {0, 1, 2, . . }. Previously we gave the extensions of predicates by listing the things, or the pairs of things, in their extensions. But if the extensions happen to be infinite, their members can't be given in a finite list. Instead, we need to explain in words how things are related by each predicate. Here is a way to do this, describing a situation in which the premises are all true and the conclusion false: COUNTER-EXAMPLE: Universe = the non-negative integers: {0, 1, 2, 3, . . } R(xy) holds when x<y That is, 'R' relates two things if and only if the first is arithmetically less than the second. Now consider how the parts of the argument fare in this counter-example.

Copyrighted material

Chapter 4 -- 27

Version of 21-Mar-11

CHAPTER 4 SECTION 9

xyR(xy) xyz[R(xy) R(yz) R(xz)] xR(xx) Here is another invalid argument: xy[R(xy) ~R(yx)] xyR(yx) xyz[R(xy) R(yz) R(xz)] xyR(xy)

True: Every integer is less than some integer True: For any integers, x, y, z, if x is less than y and y is less than z then x is less than z False: No integer is less than itself

Again, a finite universe will not work to produce a counter-example. (Try it and see.) But a counterexample with an infinite universe is possible. For example: COUNTER-EXAMPLE Universe: {0, 1, 2, . . . } R(xy) holds when x>y The first premise is true in this counter-example because whenever one thing is greater than another, that other is not greater than the first. The second premise says that for anything there is something greater than it, which is true in our infinite universe. The third is the transitivity condition again, which holds for greater-thanness. And the conclusion is false because there isn't a thing in this universe which is greater than everything. In constructing counter-examples in this way one must keep in mind that each name must be assigned something that is actually in the chosen universe. EXERCISES Give counterexamples with infinite domains to show that each of the following arguments is invalid. a. x~R(xx) xyR(xy) xyz[R(xy) R(yz) ~R(xz)] xyz[R(xy) R(yz) R(xz)] ~x[Ex R(xx)] xy[Oy R(xy)] x~[Ox Ex] x[Ex y[Fy S(yx)]] x[Fx y[Ey S(yx)]] x[Ex Fx] xyz[S(xy) S(yz) S(xz)] xS(xx)

b.

c.

Copyrighted material

Chapter 4 -- 28

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

Answers to the Exercises -- Chapter 4

SECTION 1
1. Which of the following are formulas in official notation? Which are formulas in informal notation? Which are not formulas at all? a. b. c. d. e. f. g. h. i. ~~F(xa) [xG(bx) ~yG(yx)] xG(bx) ~yG(yx) ~Fa & ~G(aa) & ~Fb & Gxb ~F(a) ~G(ab) ~Fa ~Gab ~x[~Fx yG(yy)] xy~Fxy xyF[xy] Formula official notation Formula official notation Formula informal notation Not a formula -- lacks parentheses around 'xb' Not a formula -- parentheses not used with 1-place predicates Not a formula lacks parentheses around ab Formula official notation Not a formula lacks parentheses around xy Not a formula parentheses required; not brackets

2 SYMBOLIZING SENTENCES USING MANY-PLACE PREDICATES

1. Symbolize each of the following: a. Hans sees every doctor but Amanda doesn't see any doctor. x[Dx Hans sees x] but ~x[Dx Amanda sees x] x[Dx S(hx)] ~x[Dx S(ax)] Hans, who owns a dog, doesn't own a cat. Hans owns a dog ~ Hans owns a cat x[Dx O(hx)] ~x[Cx O(hx)] Hans loves Amanda but she doesn't love him. L(ha) ~L(ah) Neither Hans nor Amanda has a cat. ~Hans has a cat ~ Amanda has a cat ~x[Cx H(hx)] ~x[Cx H(ax)] Some hyena and some giraffe like each other. xy[Hx Gy x and y like each other] xy[Hx Gy L(xy) L(yx)] Some giraffe likes every baboon. x[Gx x likes every baboon] x[Gx y[By L(xy)]] Some giraffe that likes every baboon likes no hyena. x[x is a giraffe that likes every baboon x likes no hyena] x[Gx x likes every baboon x likes no hyena] x[Gx y[By L(xy)] ~z[Hz L(xz)]] Some giraffe likes every baboon that likes no hyena x[Gx x likes every baboon that likes no hyena] x[Gx y[y is a baboon that likes no hyena x likes y]] x[Gx y[By ~z[Hz L(yz)] L(xy)]] Some giraffe likes every baboon that likes it x[Gx y[y is a baboon that likes x x likes y]] x[Gx y[By L(yx) L(xy)]]

b.

c. d.

f.

g.

h.

i.

j.

Copyrighted material

Chapter 4 -- 29 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

k.

Eileen resides in a big city. x[x is a big city Eileen resides in x] x[Bx Cx R(ex)]

<use 'R' for 'resides in'>

l.

Eileen and Betty both reside in the same city. x[x is a city Eileen resides in x Betty resides in x] x[Cx R(ex) R(bx)] If Hank resides in Brea then he attends UCLA; otherwise he doesn't attend UCLA. [Hank resides in Brea Hank attends UCLA] [Hank doesn't reside in Brea Hank doesn't attend UCLA] [R(hb) A(ha)] [~R(hb) ~A(ha)] If David and Hank both live in Brea then David attends a private school and Hank attends a public school. D: private E: public C: school David lives in Brea Hank lives in Brea x[x is a private school David attends x] x[x is a public school Hank attends x] L(db) L(db) x[Dx Cx A(dx)] x[Ex Cx A(hx)] Nobody who comes from Germany attends a Californian school. F: Californian ~x[x comes from Germany x attends a Californian school] ~x[x comes from Germany y[y is a Californian school x attends y]] ~x[C(xg) y[Fy Cy A(xy)]] No giraffe likes Fido unless it is crazy x[x is a giraffe x doesn't like Fido unless x is crazy] x[Gx ~L(xf) Cx] or ~x[x is a giraffe x likes Fido x isn't crazy] ~x[Gx L(xf) ~Cx] Nobody gives a book to a freshman unless it is inexpensive xy[x is a person y is a book x doesn't give y to a freshman unless y is inexpensive] xy[Ex By ~z[FzG(xyz)] Iy] or ~xy[Ex By z[FzG(xyz)] ~Iy]

m.

n.

o.

p.

q.

3 DERIVATIONS
Show each of the following arguments to be valid. 1. xyz[S(xy) S(yz) S(xz)] S(bc) S(ab) S(ac) 1. Show S(ac) 2. 3. 4. 5. S(ab) S(bc) S(ac) S(ab) S(bc) S(ac) pr1 ui ui ui pr2 s pr2 s 3 4 adj 2 mp dd

Copyrighted material

Chapter 4 -- 30 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

2.

xy[Ax By [S(xy) ~S(yx)]] xy[Ax By [S(xy) S(yx)]] 1. Show xy[Ax By [S(xy) S(yx)]] 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Show Ax By [S(xy) S(yx)] Ax By Ax By [S(xy) ~S(yx)] S(xy) ~S(yx) ~S(yx) S(xy) Show S(xy) S(yx) ~[S(xy) S(yx)] ~S(xy) ~S(yx) ~S(yx) S(xy) ~S(xy) ass cd pr1 ui ui 3 4 mp 5 bc ass ud 8 dm 9s 6 10 mp 9 s 11 id 7 cd 2 dd

3.

xyS(xy) xy[Cx S(xy) Dy] xy[Dx S(yx) Dy] ~x[Cx ~Dx] 1. Show ~x[Cx ~Dx] 2. 3. 4. 5. 6. 7. 8. 9. 10. x[Cx ~Dx] Cu ~Du yS(uy) S(uv) Cu S(uv) Dv Dv Dv S(uv) Du Du ~Du ass id 2 ei pr1 ui 4 ei pr2 ui ui 3 s 5 adj 6 mp pr3 ui ui 7 5 adj 8 mp 3s 9 id

4.

xEx x~Ex xy[Ex S(xy) Ey] xy~S(xy) 1. Show xy~S(xy) 2. 3. 4. 5. 6. 7. 8. 9. 10. xEx Eu x~Ex ~Ev Eu S(uv) Ev ~[Eu S(uv)] ~Eu ~S(uv) ~S(uv) xy~S(xy) pr1 s 2 ei pr1 s 4 ei pr2 ui ui 5 6 mt 7 dm 3 dn 8 mtp 9 eg eg dd

Copyrighted material

Chapter 4 -- 31 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

5.

xy[S(xy) S(yx)] xy[Ax By S(xy)] xy[By Ax S(yx)]] 1. Show xy[By Ax S(xy)]] 2. 3. 4. 5. 6. 7. 8. 9. Au Bv S(uv) S(uv) S(uv) S(vu) S(vu) Au Bv Bv Au S(vu) xy[By Ax S(yx)] pr2 ei ei 2s pr1 ui ui 4 bc 3 mp 2ss 2ss 7 6 adj 5 adj 8 eg eg dd

6.

x[Ax y[By S(xy)]] xy[Bx Cy] x[Cx yS(yx)] 1. Show x[Cx yS(yx)] 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Show Cx yS(yx) Cx Au y[By S(uy)] y[By S(uy)] Bx S(ux) Bx Cx Bx S(ux) yS(yx) ass cd pr1 ei 4s 5 ui pr2 ui ui 7 bc 3 mp 6 8 mp 9 eg cd 2 ud

7. Answers are not supplied for derivations of numbered theorems.

Copyrighted material

Chapter 4 -- 32 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

4 THE RULE "INTERCHANGE OF EQUIVALENTS"

1. PQR ~Q ~S P R ~Q 1. 2. 3. 4. 5. 6. 7. 8. 2. Show R ~Q ~~P Q R ~~P P ~~P P ~S P ~Q R ~Q pr1 ie/dn 2 ie/pr2 3 ie/dn 4 ie/dn 5 add 6 ie/pr2 7 add dd OK no -- appeals to wrong premise no -- does not result from 3 by interchanging OK an equivalent part no -- premise 2 is not a biconditional

xy[Ax R(xy)] zy[R(zy) S(yz)] x[[AxAx] Ax] Au 1. 2. 3. 4. 5. 6. 7. 8. 9. Show x[R(xx) ~Ax] y[Ax R(xy)] Au R(xu) R(xu) S(ux) Au S(ux) Au S(ux) Au Au [AuAu] Au Au pr1 ui 2 ie pr2 ui 4 ie/3 3 ie/4 5 ie/6 pr3 ui 7 ie/8

OK OK OK dd no -- does not result from 8 by interchanging an equivalent part

5 BICONDITIONAL DERIVATIONS
1. Prove the given biconditional without using a biconditional derivation and also without using the rule for interchange of equivalents: ~P ~~Q ~[P ~Q] 1. Show ~P ~~Q ~[P ~Q] 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Show ~P ~~Q ~[P ~Q] ~P ~~Q Show ~[P ~Q] P ~Q ~Q ~~Q Show ~[P ~Q] ~P ~~Q ~[P ~Q] ~P ~~Q ~P ~~Q ~[P ~Q] ass cd 9 dm cd 2 8 cb dd ass cd ass id 3 s 5 mtp 3 s 6 id

2. Derivations are not given here for numbered theorems.

Copyrighted material

Chapter 4 -- 33 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

6 SENTENCES WITHOUT OVERLAY OF QUANTIFIERS

For each of the following formulas, find an equivalent formula which has no overlay of quantifiers, and prove that it is equivalent. a. z[u[Pu Qz] Pz] 1. Show z[u[Pu Qz] Pz] [[uPu Qz] zPz] 2. z[u[Pu Qz] Pz] 3. u[Pu Qz] zPz 4. [uPu Qz] zPz 5. b. zx[Px Pz] One way to do this kind of problem is to ask yourself how to express what a formula says in terms of a formula without overlay, and then prove that that formula is equivalent to the original. Here is an example, that leads to a long derivation. ass bd 2 ie/conf 3 ie/conf 4 bd

Copyrighted material

Chapter 4 -- 34 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

1. Show zx[Px Pz] xPx ~xPx 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. zx[Px Pz] xPx ~xPx Show xPx ~xPx zx[Px Pz] xPx ~xPx Show zx[Px Pz] ~zx[Px Pz] z~x[Px Pz] ~x[Px Pz] x~[Px Pz] ~[Pu Pz] Pu ~Pz Show ~xPx xPx Pu ~Pz Pz ~xPx x~Px ~Pz Pu ~Pu ass cd ass id 22 qn 23 ui 24 qn 25 ei 26 nb ass id 29 ui 27 bc 30 mp 29 ui 31 id 28 20 mtp 33 qn 34 ui 27 bc 35 mp 34 ui 36 id 21 cd 2 19 cb dd Show zx[Px Pz] xPx ~xPx zx[[Px Pz] Show xPx ~xPx ~[xPx ~xPx] ~xPx ~~xPx ~xPx x~Px ~Pu xPx Pv x[Px Pw] Pv Pw Pw Pu Pw Pu ass cd ass id 5 dm 6s 7 qn 8 ei 6 s dn 10 ei 3 ei 12 ui 13 bc 11 mp 12 ui 15 bc 14 mp 9 16 id 4 cd

Another way to do it is to just go through and change parts to their equivalents. This is convenient if you make use of derived rules, beginning by setting up the derivation before you know what the final formula will be. Your goal will be to turn subformulas into disjunctions and conjunctions and use the laws: assoc associativity com commutativity dist distribution conf confinement qdist quantifier distribution bex biconditional expansion

Copyrighted material

Chapter 4 -- 35 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

1. Show zx[Ax Az] ????? 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. zx[Ax Az] ass bd zx[[Ax Az] [Az Ax]] 2 ie/bex "biconditional expansion" z[x[Ax Az] x[Az Ax]] 3 ie/qdist "quantifier distribution" z[[xAx Az] [Az xAx]] 4 ie/conf ie/conf z[[~xAx Az] [~Az xAx]] 5 ie/cdj ie/cdj z[(~xAx~Az) (~xAxxAx) (Az~Az) (AzxAx)] 6 ie/dist z((~xAx~Az) (~xAxxAx) (Az~Az)) z(AzxAx) 7 ie/qdist z(~xAx~Az) z(~xAxxAx) z(Az~Az) z(AzxAx) 8 ie/qdist (~xAxz~Az) z(~xAxxAx) z(Az~Az) z(AzxAx) 9 ie/conf (~xAxz~Az) z(~xAxxAx) z(Az~Az) (zAzxAx) 10 ie/conf (~xAxz~Az) (~xAxxAx) z(Az~Az) (zAzxAx) 11 ie/vac

One may then replace the question marks with the formula on line 12, and then add: 13. and box and cancel the original 'show'. 12 bd

c. xPx y~Qy

This sentence already lacks quantifier overlays.

d. x[x[Px Qx] [Px Qx]] 1. Show x[x[Px Qx] [Px Qx]] [x[Px Qx] x[Px Qx]] 2. 3. x[x[Px Qx] [Px Qx]] x[Px Qx] x[Px Qx] ass bd 2 ie/conf bd

e. xyz[Px Qz Pz Qy] The strategy here is to manipulate the parts to get the two atomic formulas containing 'z' together as a unit (lines 3-5) and then apply the confinement laws. 1. Show xyz[Px Qz Pz Qy] xPx [z[~Qz Pz] yQy] 2. 3. 4. 5. 6. 7. 8. 9. 10. xyz[Px Qz Pz Qy] xyz[Px [Qz Pz Qy]] xyz[Px [~Qz Pz Qy]] xyz[Px [[~Qz Pz] Qy]] xy[Px z[[~Qz Pz] Qy]] xy[Px [z[~Qz Pz] Qy]] x[Px y[z[~Qz Pz] Qy]] x[Px [z[~Qz Pz] yQy]] xPx [z[~Qz Pz] yQy] ass bd 2 ie/exp 3 ie/cdj 4 ie/assoc 5 ie/conf 6 ie/conf 7 ie/conf 8 ie/conf 9 ie/conf bd

Copyrighted material

Chapter 4 -- 36 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

7 PRENEX NORMAL FORMS

1. Derivations are not given here for numbered theorems. 2. Put each of the following formulas into prenex normal form. In each case give a biconditional derivation that shows that the prenex form is equivalent to the original formula. a. xyP(xy) uP(uu)

Begin by setting up a biconditional derivation. You won't know at the beginning exactly what form the right-hand side of the biconditional will take. So just leave a place for it: 1. Show [xyP(xy) uP(uu)] ????? 2. [xyP(xy) uP(uu)] ass bd Then carry out the series of equivalences: 1. Show [xyP(xy) uP(uu)] ????? 2. 3. 4. 5. xyP(xy) uP(uu) x[yP(xy) uP(uu)] xy[P(xy) uP(uu)] xyu[P(xy) P(uu)] ass bd 2 ie/conf 3 ie/conf 4 ie/conf

Finally fill in the right-hand side of the top biconditional with what you have shown on line 5, and box and cancel: 1. Show [xyP(xy) uP(uu)] xyu[P(xy) P(uu)] 2. 3. 4. 5. xyP(xy) uP(uu) x[yP(xy) uP(uu)] xy[P(xy) uP(uu)] xyu[P(xy) P(uu)] ass bd 2 ie/conf 3 ie/conf 4 ie/conf bd

Derivations for the other examples will be generated in this way: set up a biconditional derivation and then carry it out. Only the final derivations are given below: b. x[uR(ux) uR(xu)] 1. Show x[uR(ux) uR(xu)] xyu[R(yx) R(xu)] 2. 3. 4. 5. c. x[uR(ux) uR(xu)] x[yR(yx) uR(xu)] xy[R(yx) uR(xu)] xyu[R(yx) R(xu)] xyA(xy) xyA(yx) 1. Show [xyA(xy) xyA(yx)] xyuv[A(xy) A(vu)] 2. 3. 4. 5. 6. 7. 8. xyA(xy) xyA(yx) xyA(xy) xvA(vx) xyA(xy) uvA(vu) x[yA(xy) uvA(vu)] xy[A(xy) uvA(vu)] xyu[A(xy) vA(vu)] xyuv[A(xy) A(vu)] ass bd 2 ei/av 3 ei/av 4 ei/conf 5 ei/conf 6 ei/conf 7 ei/conf bd ass bd 2 ie/av 3 ie/conf 4 ie/conf bd

The trick here is to use rule av to change bound variables so that the confinement rules will apply.

d.

xy[R(xy)R(yx)] This is already in prenex normal form.

Copyrighted material

Chapter 4 -- 37 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

8 SOME THEOREMS Derivations are not given here for numbered theorems. 9 SHOWING INVALIDITY
1. Give counter-examples to show that these arguments are invalid in the predicate calculus. a. x[Fx y[Gy R(xy)]] x[Gx ~R(xx)] x[Fx y[Gy R(xy)]] Universe: {0} F: {} G: R: <any choice will do> <any choice will do>

Both premises are true because they contain conditionals with false antecedents for any value of 'x'; the conclusion is false because nothing is F. Another answer: Universe: {0,1} F: {0,1} G: {0,1} R: {<1,0>, <0,1>} The first premise is true because for any choice of 'x' (either 0 or 1) there is something which is G and related to the choice of 'x' by R. The second premise is true because nothing is related to itself by R. The conclusion is false because whatever you pick for 'x' the universal quantifier 'y' will require that that thing be related to itself by R. b. x[F(xa) G(xb)] xy[F(xy) G(xy)] Universe: {0,1} a: b: F: G: 1 0 {<0,1>} {<0,0>}

The premise is true because its instances are all true; choosing 0 for 'x' both sides of the biconditional are true; choosing 1 for 'x' both sides of the biconditional are false. The conclusion is false since there is nothing you can pick for 'x' and 'y' which give you a pair of things that is in the extensions of both F and G. c. x[Hx R(ax)] xy[R(xy) R(yx)] yxR(xy) Universe: {0,1} a: 0 H: {0} R: {<0,0>} The first premise is true because there is only one thing that is H, and that is 0, and it is related to the thing that 'a' stands for (namely, 0) by R. The second premise says that any pair of things that are related by R are also related in reverse order; the only thing that R applies to is the pair <0,0>, and reversing it makes no difference. The conclusion is false since there isn't anything that is related to everything by R.

Copyrighted material

Chapter 4 -- 38 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

d.

x[Fx yR(xy)] x[~Fx yR(yx)] xy[R(xy) R(yx)] Universe: {0,1} F: {0} R: {<0,1>}

The first premise is true because whatever is F, namely, 0, is related to something (namely, 1) by R. The second premise is true because for whatever isn't F, namely, 1, something (namely, 0) is related to it by R. The conclusion is false since it says that everything is related to something by R in both directions, and nothing is related to anything by R in both directions. e. xy[F(xy) z[G(xz) ~G(yz)]] xy[F(xy) F(yx)] xy[G(xy) G(yx)] Universe: {0,1,2} F: {<0,1>, <1,0>, <1,2>, <2,1>, <2,0>, <0,2>} G: {<0,1>, <1,2>, <2,0>} The first premise is true since it comes out true for all choices of 'x' and 'y'. (There are nine choices in all; each can be checked on its own.) The second premise says that F is symmetric; this is clearly true since for every pair in the extension of F the reverse pair is also there. The conclusion says falsely that G is symmetric; G holds of <2,0> but not of <0,2>. Another answer: Universe: {0,1} F: {} G: {<0,1>, <1,1>} The first premise is true since both sides of the biconditional are false for any choices of 'x' and 'y'; this is clear for the left-hand side since F is true of no pairs at all; the other side can be checked by cases. The second premise is vacuously true. The conclusion falsely says that G is symmetric; but G holds of <0,1> and not of <1,0>.

2. Give counterexamples with infinite domains to show that each of the following arguments is invalid. a. x~R(xx) xyR(xy) xyz[R(xy) R(yz) ~R(xz)] Universe: {0, 1, 2, . . . } R(xy) : x<y The first premise says truly that nothing is less than itself. The second says truly that for every nonnegative integer there is another non-negative integer that it is less than. The conclusion is false since less than is transitive. zero and all the positive integers

Copyrighted material

Chapter 4 -- 39 -- Answers to the Exercises

Version of 21-Mar-11

Answers to Exercises -- Chapter 4

b.

xyz[R(xy) R(yz) R(xz)] ~x[Ex R(xx)] xy[Oy R(xy)] x~[Ox Ex] Universe: {0, 1, 2, . . . } Ex : x is even Ox : x is even R(xy) : x<y zero and all the positive integers

The first premise is true since less than is transitive. The second is true since no even number is less than itself. The third premise says truly that for every non-negative integer there is an even non-negative integer that it is less than. The conclusion says falsely that for some non-negative integer it isn't the case that it's even if and only if it's even. x[Ex y[Fy S(yx)]] x[Fx y[Ey S(yx)]] x[Ex Fx] xyz[S(xy) S(yz) S(xz)] xS(xx) Universe: {0, 1, 2, . . . } Ex : x is even Fx : x is odd S(xy) : x>y The first premise is true since for every even non-negative integer there is an odd non-negative integer that is greater than it. The second premise is true since for every odd non-negative integer there is an even non-negative integer that is greater than it. The third premise says truly that every non-negative integer is either even or odd. <if you think that 0 is neither even nor odd, then just change the interpretation of 'E' to 'x is even or x=0'> The fourth premise says truly that greater than is transitive. The conclusion says falsely that some non-negative integer is greater than itself. zero and all the positive integers

c.

Copyrighted material

Chapter 4 -- 40 -- Answers to the Exercises

Version of 21-Mar-11