Errata and Addenda for CNL

Classical and Nonclassical Logics
known errata and addenda for the 2005 edition

2 Apr 2008 is latest update to this page, which lists all known mistakes as well as some things I'd like to add to the book. Please report to me any additional errors that you find, or additions that you care to suggest.

page § correction or alteration

20 2.1 Add remark: This chapter is intended merely as a preview or overview of the rest of the book. It can be read, skimmed, or skipped entirely, according to the reader's taste; skipping it will not interfere with reading subsequent chapters. Beginners who read this chapter should not concern themselves about understanding its every detail until they read the later parts of the book that are referred to here.

25 2.9 Add remark: The formal definition of "subset" presented in this section is a bit advanced and is not intended as part of the course presented in this book. For that purpose we recommend the informal definition presented in section 3.13. This book uses informal set theory; we are only briefly mentioning some of formal set theory in this section to try to illustrate the difference between "formal" and "informal".

109 3.55.b Add remark: This result will be used in 4.17.

126-145 ch.4 Perhaps a better order for this material would be to the definition of "interior" from 4.10 to immediately after 4.5, so that each of the examples would only have to be covered once.

132 4.7 A better name for the "usual topology" is the "Euclidean topology." Also, here is an alternate definition of that topology (equivalent to the definition given in the book, but perhaps easier to understand): First, define an open interval to mean any set of the form (x,y)={r: x<r<y}. Then define an open set to mean any union of open intervals. The interior of a set then turns out to be equal to the union of all the open intervals contained in that set.

134 4.10 Here is an alternative definition of interior (equivalent to the definition given in the book, but perhaps easier to understand): A point x is in the interior of a set S if and only if x is a member of some open set that is a subset of S.

135 4.12 (This is not actually an error, but it has confused enough students that perhaps it deserves to be explained at greater length.) Consider the real line, equipped with its usual topology, as a topological space, and consider each of the following sets as a subset of the real line. Find the interior of that subset.

137 4.16 (Again, this is not an error, but a longer explanation might help.) For problem 4.16.a, we consider [0,1) as a subset of a topological space, where the topological space is R with one of the three topologies listed. For 4.16.b, we consider {1,2,5} as a subset of a topological space, where the topological space is N with one of the three topologies listed.

143 4.26 In the first line of the page, "varphi" is written instead of the Greek lowercase letter phi (in the form used later on that page, not for empty set but for the function defined on Omega).

152 5.9 One of my students has informed me that Arabic, like Latin, has two different words for "inclusive or" and "exclusive or." I will try to find out more about this.

156 5.13 The first De Morgan's Law is incorrectly stated as . It should be stated as -- that is, the first "and" should be an "or".

165 5.26 Clarification: This exercise requires the definitions that were given in 2.38.

174 5.34 The algebraic definitions of Ackermann's constants are reversed. They should be

(However, those definitions aren't used subsequently in the book.)

245 8.1 This might be a good place to add the following remark: One of the most common errors I've seen students make is to try applying one logic's formula for implication to another logic's problems -- e.g., applying the formula in 8.2c or 8.28 to problem 8.21. Apparently it needs to be emphasized more strongly that different semantic systems have different evaluation rules that yield different results. Students who have not yet grasped that fact will flip through the pages, looking for any formula for computing implications, and unfortunately may use the first or simplest such formula that they find.

251-258 8.16-8.27 The following results would make interesting additional exercises.
Show that fuzzy negation cannot be expressed in terms of the other logical operations. Hint: Use the valuation where all the p_j's have value 1.)
Show that fuzzy implication cannot be expressed in terms of the other logical operations. Hint: Consider the valuation in which p₁ has the value 3/4 and all the other p_j's have the value 1/4.
Show that fuzzy "or" can be expressed in terms of "and" and "not".
Show that fuzzy "and" can be expressed in terms of "or" and "not".
Insert a few pages earlier, that [[ (A ® B) ® B ]] = [[A Ú B]] in the fuzzy interpretation. Thus fuzzy "or" can be expressed in terms of fuzzy "implies".

258 8.26.e The brackets aren't balanced. Omit the final right bracket. Thus, this formula should say:

260 8.29.c The parentheses are not balanced. To correct this, omit the last left parenthesis; that is,

260 8.29.f The first right doubled bracket is missing. Here is the corrected expression:

261 8.32 or thereabouts The following results would make interesting additional exercises. In the comparative and the Sugihara interpretation,

"or" can be expressed in terms of "and" and "not"
"and" can be expressed in terms of "or" and "not"
"not" can be expressed in terms of "implies". Hint: 8.30.b(viii).
In the comparative interpretation, "implies" cannot be expressed in terms of "and", "or", and "not". Hint: Consider the valuation where all the p_j's have value 1. [What about the Sugihara interpretation? I'm still thinking about that one.]

265 8.39.d This assertion is wrong, as can be demonstrated by giving A and B the values -1 and -2 respectively. ... However, the subsequent remark -- i.e., that "the semantic version of the Herbrand-Tarski deduction principle is not applicable to Sugihara's interpretation" -- is correct; a correct (and simpler) demonstration of that is given by 8.32.d.

286 10.8 At this point it should be mentioned that every topological interpretation also satisfies strong adjunction (22.10.a). But the tautologousness of that formula follows easily from 10.7.c.

299 11.5 The first uncircled arrow on page 299 should be a circled arrow.

300 11.6 In the verification of arrow-prefixing, the first sentence requires for its justification not only 11.5.a but also 11.2.h(i).

317 add to end of chapter 12 Perhaps this would be a good place to put the material that presently is in section 21.1. That way, we could use it throughout the next few chapters, to show that various formulas are not theorems of basic logic, etc.

332 13.9 It would be good to add a particular example of irreversibility. Here is one: It is fairly easy to prove A |- B®A in the logic of basic implication. (It's a one-line proof, because you don't need the hypothesis and therefore don't even have to include it in the proof.) But it is not possible to prove |- B®(A®A) in this logic; that's the formula called "irrelevant conclusion" in 16.3.b. In fact, it is not even possible to prove the weaker formula |- A®(A®A) in this logic; that's the formula called "mingle" in 16.2.a. By that I don't just mean that no one has found a proof yet. Rather, I mean that we can demonstrate that a proof is not possible. Indeed, that follows from the soundness principle (21.1.a), using any of the semantics at the end of chapter 9: crystal, Church's diamond, or Church's chain. I'd recommend using Church's chain -- it's certainly the simplest of those several semantics. See 9.13.d.

334-335 13.23 It would be good to add a few examples. For instance, |- [A ® (B ® (D ® C))] ® [D ® (A ® (B ® C))] is the instance of 13.23, and [A ® (B ® (D ® C))] |- [D ® (A ® (B ® C))] is the instance of 13.23.delta, that we need for the last line of section 16.3.

337 14.1 The word "appear" was omitted from this sentence in the middle of the page: "Most of our introduction and elimination rules appear in at least two forms..."

338 14.2 There's a mistake here. The detachmental corollaries of and-introduction and or-elimination are not dual to each other on the left sides of their turnstiles, because they both have and's there. What I really should have said is that their adjunctional corollaries, 14.4.a and 14.4.b, are dual to each other.

339 14.4.b Actually, 14.4.b.delta can be proved without using and-introduction. See 22.10.b. In the remainder of Chapter 14 and in the next few chapters after it, it might be interesting to take note of those places where 14.4.b.delta isn't strong enough -- i.e., where one actually needs 14.4.b or and-introduction.

340 14.7. Some additional remarks are called for. The four inference rules presented here are obviously detachmental corollaries of four would-be theorems, except that we can't prove those theorems under the assumptions of the present chapter. Here are two ways to demonstrate that fact, by borrowing later material: (1) It's easy to demonstrate that those four formulas are not tautological in comparative logic. (I suspect that they also fail in the crystal logic and the three Church's logics covered at the end of chapter 9, but that's harder to check and I haven't checked it yet.) Now apply 8.34 and 21.1. (2) The first two of those formulas appear at the end of 23.18 (and the other two are easily equivalent to them). Thus they are equivalent to positive paradox, as an extension of relevant logic.>

340 14.8.f Perhaps a slightly bigger hint is needed. Here it is: One of the steps in my proof is [(A Ù B) ® (B ® C)] ® {(A Ù B) ® [(A Ù B) ® C]}.

343-345 14.14-14.16 This material is way too abstract. It should begin with one or two very specific examples, and end with several more as exercises. A good type of example/exercise would be the following: "Here is an implication that is a theorem of basic logic. Its converse is not a theorem of basic logic (although we postpone proving that fact). From that short theorem, we can (easily, after we've proved the substitution principle) deduce that one of the two following long formulas is also a theorem. Which one is it?"

362 16.3, last derivation The justification of step (6) should be 13.23.delta, not just 13.23. Also, this proof could be one step shorter, and it will be in the second edition of the book if such a thing ever comes into existence. There are two ways to justify one of the steps in this proof (I won't say which one, I'm leaving that as an exercise) -- one way is the justification I originally had in mind, but the other way makes one of the earlier steps unnecessary.

383 21.1. See note for the end of chapter 12.

431 25.4 The formula that is labeled as and-introduction would be better labeled as strong adjunction (to make it more consistent with other parts of the book.

446 27.6 The statement of 27.6, though correct, is unnecessarily complicated. The hypothesis "H turnstile C" is superfluous -- since C is an axiom, we actually have "turnstile C" even without the H. Thus, a simpler statement of 27.6 would be the following: "Each of the axioms of constructive logic (as listed in 25.4) has value 1 in the Meyer valuation."

page	§	correction or alteration
20	2.1	Add remark: This chapter is intended merely as a preview or overview of the rest of the book. It can be read, skimmed, or skipped entirely, according to the reader's taste; skipping it will not interfere with reading subsequent chapters. Beginners who read this chapter should not concern themselves about understanding its every detail until they read the later parts of the book that are referred to here.
25	2.9	Add remark: The formal definition of "subset" presented in this section is a bit advanced and is not intended as part of the course presented in this book. For that purpose we recommend the informal definition presented in section 3.13. This book uses informal set theory; we are only briefly mentioning some of formal set theory in this section to try to illustrate the difference between "formal" and "informal".
109	3.55.b	Add remark: This result will be used in 4.17.
126-145	ch.4	Perhaps a better order for this material would be to the definition of "interior" from 4.10 to immediately after 4.5, so that each of the examples would only have to be covered once.
132	4.7	A better name for the "usual topology" is the "Euclidean topology." Also, here is an alternate definition of that topology (equivalent to the definition given in the book, but perhaps easier to understand): First, define an open interval to mean any set of the form (x,y)={r: x<r<y}. Then define an open set to mean any union of open intervals. The interior of a set then turns out to be equal to the union of all the open intervals contained in that set.
134	4.10	Here is an alternative definition of interior (equivalent to the definition given in the book, but perhaps easier to understand): A point x is in the interior of a set S if and only if x is a member of some open set that is a subset of S.
135	4.12	(This is not actually an error, but it has confused enough students that perhaps it deserves to be explained at greater length.) Consider the real line, equipped with its usual topology, as a topological space, and consider each of the following sets as a subset of the real line. Find the interior of that subset.
137	4.16	(Again, this is not an error, but a longer explanation might help.) For problem 4.16.a, we consider [0,1) as a subset of a topological space, where the topological space is R with one of the three topologies listed. For 4.16.b, we consider {1,2,5} as a subset of a topological space, where the topological space is N with one of the three topologies listed.
143	4.26	In the first line of the page, "varphi" is written instead of the Greek lowercase letter phi (in the form used later on that page, not for empty set but for the function defined on Omega).
152	5.9	One of my students has informed me that Arabic, like Latin, has two different words for "inclusive or" and "exclusive or." I will try to find out more about this.
156	5.13	The first De Morgan's Law is incorrectly stated as . It should be stated as -- that is, the first "and" should be an "or".
165	5.26	Clarification: This exercise requires the definitions that were given in 2.38.
174	5.34	The algebraic definitions of Ackermann's constants are reversed. They should be (However, those definitions aren't used subsequently in the book.)
245	8.1	This might be a good place to add the following remark: One of the most common errors I've seen students make is to try applying one logic's formula for implication to another logic's problems -- e.g., applying the formula in 8.2c or 8.28 to problem 8.21. Apparently it needs to be emphasized more strongly that different semantic systems have different evaluation rules that yield different results. Students who have not yet grasped that fact will flip through the pages, looking for any formula for computing implications, and unfortunately may use the first or simplest such formula that they find.
251-258	8.16-8.27	The following results would make interesting additional exercises. Show that fuzzy negation cannot be expressed in terms of the other logical operations. Hint: Use the valuation where all the p_j's have value 1.) Show that fuzzy implication cannot be expressed in terms of the other logical operations. Hint: Consider the valuation in which p₁ has the value 3/4 and all the other p_j's have the value 1/4. Show that fuzzy "or" can be expressed in terms of "and" and "not". Show that fuzzy "and" can be expressed in terms of "or" and "not". Insert a few pages earlier, that [[ (A ® B) ® B ]] = [[A Ú B]] in the fuzzy interpretation. Thus fuzzy "or" can be expressed in terms of fuzzy "implies".
258	8.26.e	The brackets aren't balanced. Omit the final right bracket. Thus, this formula should say:
260	8.29.c	The parentheses are not balanced. To correct this, omit the last left parenthesis; that is,
260	8.29.f	The first right doubled bracket is missing. Here is the corrected expression:
261	8.32 or thereabouts	The following results would make interesting additional exercises. In the comparative and the Sugihara interpretation, "or" can be expressed in terms of "and" and "not" "and" can be expressed in terms of "or" and "not" "not" can be expressed in terms of "implies". Hint: 8.30.b(viii). In the comparative interpretation, "implies" cannot be expressed in terms of "and", "or", and "not". Hint: Consider the valuation where all the p_j's have value 1. [What about the Sugihara interpretation? I'm still thinking about that one.]
265	8.39.d	This assertion is wrong, as can be demonstrated by giving A and B the values -1 and -2 respectively. ... However, the subsequent remark -- i.e., that "the semantic version of the Herbrand-Tarski deduction principle is not applicable to Sugihara's interpretation" -- is correct; a correct (and simpler) demonstration of that is given by 8.32.d.
286	10.8	At this point it should be mentioned that every topological interpretation also satisfies strong adjunction (22.10.a). But the tautologousness of that formula follows easily from 10.7.c.
299	11.5	The first uncircled arrow on page 299 should be a circled arrow.
300	11.6	In the verification of arrow-prefixing, the first sentence requires for its justification not only 11.5.a but also 11.2.h(i).
317	add to end of chapter 12	Perhaps this would be a good place to put the material that presently is in section 21.1. That way, we could use it throughout the next few chapters, to show that various formulas are not theorems of basic logic, etc.
332	13.9	It would be good to add a particular example of irreversibility. Here is one: It is fairly easy to prove A \|- B®A in the logic of basic implication. (It's a one-line proof, because you don't need the hypothesis and therefore don't even have to include it in the proof.) But it is not possible to prove \|- B®(A®A) in this logic; that's the formula called "irrelevant conclusion" in 16.3.b. In fact, it is not even possible to prove the weaker formula \|- A®(A®A) in this logic; that's the formula called "mingle" in 16.2.a. By that I don't just mean that no one has found a proof yet. Rather, I mean that we can demonstrate that a proof is not possible. Indeed, that follows from the soundness principle (21.1.a), using any of the semantics at the end of chapter 9: crystal, Church's diamond, or Church's chain. I'd recommend using Church's chain -- it's certainly the simplest of those several semantics. See 9.13.d.
334-335	13.23	It would be good to add a few examples. For instance, \|- [A ® (B ® (D ® C))] ® [D ® (A ® (B ® C))] is the instance of 13.23, and [A ® (B ® (D ® C))] \|- [D ® (A ® (B ® C))] is the instance of 13.23.delta, that we need for the last line of section 16.3.
337	14.1	The word "appear" was omitted from this sentence in the middle of the page: "Most of our introduction and elimination rules appear in at least two forms..."
338	14.2	There's a mistake here. The detachmental corollaries of and-introduction and or-elimination are not dual to each other on the left sides of their turnstiles, because they both have and's there. What I really should have said is that their adjunctional corollaries, 14.4.a and 14.4.b, are dual to each other.
339	14.4.b	Actually, 14.4.b.delta can be proved without using and-introduction. See 22.10.b. In the remainder of Chapter 14 and in the next few chapters after it, it might be interesting to take note of those places where 14.4.b.delta isn't strong enough -- i.e., where one actually needs 14.4.b or and-introduction.
340	14.7.	Some additional remarks are called for. The four inference rules presented here are obviously detachmental corollaries of four would-be theorems, except that we can't prove those theorems under the assumptions of the present chapter. Here are two ways to demonstrate that fact, by borrowing later material: (1) It's easy to demonstrate that those four formulas are not tautological in comparative logic. (I suspect that they also fail in the crystal logic and the three Church's logics covered at the end of chapter 9, but that's harder to check and I haven't checked it yet.) Now apply 8.34 and 21.1. (2) The first two of those formulas appear at the end of 23.18 (and the other two are easily equivalent to them). Thus they are equivalent to positive paradox, as an extension of relevant logic.>
340	14.8.f	Perhaps a slightly bigger hint is needed. Here it is: One of the steps in my proof is [(A Ù B) ® (B ® C)] ® {(A Ù B) ® [(A Ù B) ® C]}.
343-345	14.14-14.16	This material is way too abstract. It should begin with one or two very specific examples, and end with several more as exercises. A good type of example/exercise would be the following: "Here is an implication that is a theorem of basic logic. Its converse is not a theorem of basic logic (although we postpone proving that fact). From that short theorem, we can (easily, after we've proved the substitution principle) deduce that one of the two following long formulas is also a theorem. Which one is it?"
362	16.3, last derivation	The justification of step (6) should be 13.23.delta, not just 13.23. Also, this proof could be one step shorter, and it will be in the second edition of the book if such a thing ever comes into existence. There are two ways to justify one of the steps in this proof (I won't say which one, I'm leaving that as an exercise) -- one way is the justification I originally had in mind, but the other way makes one of the earlier steps unnecessary.
383	21.1.	See note for the end of chapter 12.
431	25.4	The formula that is labeled as and-introduction would be better labeled as strong adjunction (to make it more consistent with other parts of the book.
446	27.6	The statement of 27.6, though correct, is unnecessarily complicated. The hypothesis "H turnstile C" is superfluous -- since C is an axiom, we actually have "turnstile C" even without the H. Thus, a simpler statement of 27.6 would be the following: "Each of the axioms of constructive logic (as listed in 25.4) has value 1 in the Meyer valuation."