So-called classical logic--the logic developed in the early twentieth century by Gottlob Frege, Bertrand Russell, and others--is computationally the simplest of the major logics, and it is adequate for the needs of most mathematicians. But it is just one of the many kinds of reasoning in everyday thought. Consequently, when presented by itself--as in most introductory texts on logic--it seems arbitrary and unnatural to students new to the subject.
In Classical and Nonclassical Logics, Eric Schechter introduces classical logic alongside constructive, relevant, comparative, and other nonclassical logics. Such logics have been investigated for decades in research journals and advanced books, but this is the first textbook to make this subject accessible to beginners. While presenting an assortment of logics separately, it also conveys the deeper ideas (such as derivations and soundness) that apply to all logics. The book leads up to proofs of the Disjunction Property of constructive logic and completeness for several logics.
The book begins with brief introductions to informal set theory and general topology, and avoids advanced algebra; thus it is self-contained and suitable for readers with little background in mathematics. It is intended primarily for undergraduate students with no previous experience of formal logic, but advanced students as well as researchers will also profit from this book.
So-called classical logic--the logic developed in the early twentieth century by Gottlob Frege, Bertrand Russell, and others--is computationally the simplest of the major logics, and it is adequate for the needs of most mathematicians. But it is just one of the many kinds of reasoning in everyday thought. Consequently, when presented by itself--as in most introductory texts on logic--it seems arbitrary and unnatural to students new to the subject.
In Classical and Nonclassical Logics, Eric Schechter introduces classical logic alongside constructive, relevant, comparative, and other nonclassical logics. Such logics have been investigated for decades in research journals and advanced books, but this is the first textbook to make this subject accessible to beginners. While presenting an assortment of logics separately, it also conveys the deeper ideas (such as derivations and soundness) that apply to all logics. The book leads up to proofs of the Disjunction Property of constructive logic and completeness for several logics.
The book begins with brief introductions to informal set theory and general topology, and avoids advanced algebra; thus it is self-contained and suitable for readers with little background in mathematics. It is intended primarily for undergraduate students with no previous experience of formal logic, but advanced students as well as researchers will also profit from this book.
Classical and Nonclassical Logics: An Introduction to the Mathematics of Propositions
520
Classical and Nonclassical Logics: An Introduction to the Mathematics of Propositions
520eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
So-called classical logic--the logic developed in the early twentieth century by Gottlob Frege, Bertrand Russell, and others--is computationally the simplest of the major logics, and it is adequate for the needs of most mathematicians. But it is just one of the many kinds of reasoning in everyday thought. Consequently, when presented by itself--as in most introductory texts on logic--it seems arbitrary and unnatural to students new to the subject.
In Classical and Nonclassical Logics, Eric Schechter introduces classical logic alongside constructive, relevant, comparative, and other nonclassical logics. Such logics have been investigated for decades in research journals and advanced books, but this is the first textbook to make this subject accessible to beginners. While presenting an assortment of logics separately, it also conveys the deeper ideas (such as derivations and soundness) that apply to all logics. The book leads up to proofs of the Disjunction Property of constructive logic and completeness for several logics.
The book begins with brief introductions to informal set theory and general topology, and avoids advanced algebra; thus it is self-contained and suitable for readers with little background in mathematics. It is intended primarily for undergraduate students with no previous experience of formal logic, but advanced students as well as researchers will also profit from this book.
Product Details
| ISBN-13: | 9780691220147 |
|---|---|
| Publisher: | Princeton University Press |
| Publication date: | 10/06/2020 |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 520 |
| File size: | 9 MB |
About the Author
Read an Excerpt
Classical and Nonclassical Logics
An Introduction to the Mathematics of PropositionChapter One
Introduction for teachers
Readers with no previous knowledge of formal logic will find it more useful to begin with Chapter 2.
Purpose and intended audience
1.1. CNL (Classical and Nonclassical Logics) is intended as an introduction to mathematical logic. However, we wish to immediately caution the reader that the topics in this book are not the same as those in a conventional introduction to logic. CNL should only be adopted by teachers who are aware of the differences and are persuaded of this book's advantages. Chiefly, CNL trades some depth for breadth:
A traditional introduction to logic covers classical logic only, though possibly at several levels - propositional, predicate, modal, etc.
CNL is pluralistic, in that it covers classical and several non-classical logics - constructive, quantitative, relevant, etc. - though almost solely at the propositional level.
Of course, a logician needs both depth and breadth, but both cannot be acquired in the first semester. The depth-first approach is prevalent in textbooks, perhaps merely because classical logicdeveloped a few years before other logics. I am convinced that a breadth-first approach would be better for the students, for reasons discussed starting in 1.9.
1.2. Intended audience. This is an introductory textbook. No previous experience with mathematical logic is required. Some experience with algebraic computation and abstract thinking is expected, perhaps at the precalculus level or slightly higher. The exercises in this book are mostly computational and require little originality; thus CNL may be too elementary for a graduate course. Of course, the book may be used at different levels by different instructors.
CNL was written for classroom use; I have been teaching undergraduate classes from earlier versions for several years. However, its first few chapters include sufficient review of prerequisite material to support the book's use also for self-guided study. Those chapters have some overlap with a "transition to higher mathematics" course; CNL might serve as a resource in such a course.
I would expect CNL to be used mainly in mathematics departments, but it might be adopted in some philosophy departments as well. Indeed, some philosophers are very mathematically inclined; many of this book's mathematical theorems originated on the chalkboards of philosophy departments. Colleagues have also informed me that this book will be of some interest to students of computer science, but I am unfamiliar with such connections and have not pursued them in this book.
1.3. In what sense is this new? This book is a work of exposition and pedagogy, not of research. All the main theorems of this book have already appeared, albeit in different form, in research journals or advanced monographs. But those articles and books were written to be read by experts. I believe that the present work is a substantially new selection and reformulation of results, and that it will be more accessible to beginners.
1.4. Avoidance of algebra. Aside from its pluralistic approach (discussed at much greater length later in this chapter), probably CNL's most unusual feature is its attempt to avoid higher algebra.
In recent decades, mathematical logic has been freed from its philosophical and psychological origins; the current research literature views different logics simply as different kinds of algebraic structures. That viewpoint may be good for research, but it is not a good prescription for motivating undergraduate students, who know little of higher algebra.
CNL attempts to use as little algebra as possible. For instance, we shall use topologies instead of Heyting algebras; they are more concrete and easier to define. (See the remark in 4.6.i.)
1.5. Rethinking of terminology. I have followed conventional terminology for the most part, but I have adopted new terminology whenever a satisfactory word or phrase was not available in the literature. Of course, what is "satisfactory" is a matter of opinion.
It is my opinion that there are far too many objects in mathematics called "regular," "normal," etc. Those words are not descriptive - they indicate only that some standard is being adhered to, without giving the beginner any assistance whatsoever in identifying and assimilating that standard. Whenever possible, I have attempted to replace such terms with phrases that are more descriptive, such as "truth-preserving" and "tautology-preserving."
A more substantive, and perhaps more controversial, example of rejected terminology is "intuitionistic logic." That term has been widely used for one particular logic since it was introduced in the early 20th century by Brouwer, Heyting, and Kolmogorov. To call it anything else is to fight a strong tradition. But the word "intuitionistic" has connotations of subjectivity and mysticism that may drive away some scientifically inclined students. There is nothing subjective, mystical, or unscientific about this interesting logic, which we develop in Chapters 10, 22, 27, 28, and part of 29.
Moreover, not all mathematicians share the same intuition. Indeed, aside from logicians, most mathematicians today are schooled only in classical logic and find all other logics to be nonintuitive. It is only a historical accident that Brouwer, Heyting and Kolmogorov appropriated the word "intuitionistic" for their system. The term "BHK logic," used in some of the literature, is less biased, but it too is descriptive only to someone who already knows the subject.
A more useful name is "constructive logic," because BHK logic is to a large extent the reasoning system of constructive mathematics (discussed in 2.42{2.46). Mathematicians may not be entirely in agreement about the importance of constructivism, but at least there is consensus on what the term "constructive" means. Its meaning in mathematics is quite close to its meaning outside mathematics, and thus should be more easily grasped by beginning students.
1.6. What is not covered. This book is intended as an introductory textbook, not an encyclopedia - it includes enough different logics to illustrate some basic ideas of the subject, but it does not include all major logics. Derivations in CNL follow only the Hilbert style, because in my opinion that is easiest for beginners to understand. The treatment of quantifiers consists of only a few pages (sections 5.40-5.51), and that treatment is informal, not axiomatic. Omitted entirely (or mentioned in just a sentence or two) are [??], [??], formal predicate logic, Gentzen sequents, natural deduction, modal logics, Godel's Incompleteness Principles, recursive functions, Turing machines, linear logic, quantum logic, substructures logics, nonmonotonic logics, and many other topics.
Topics in the book
1.7. Order of topics. I have tried to arrange the book methodically, so that topics within it are not hard to find; but I have also provided frequent cross-referencing, to facilitate reading the book in other orders than mine.
Chapter 2 gives an overview of, and informal introduction to, the subject of logic. The chapter ends with a detailed discussion (2.42-2.46) of constructivism and Jarden's Proof, surely the simplest example of the fact that a different philosophy can require a different logic.
Chapters 3 and 4 give a brief introduction to naive set theory and general topology. Chapter 5 gives a more detailed introduction to informal classical logic, along with comments about how it compares with nonclassical logics and with ordinary nonmathematical English. Particular attention is given to the ambiguities of English.
Chapters 2-5 may be considered "prerequisite" material, in the sense that their content is not part of logic but will be used to develop logic. Different students will need different parts of this prerequisite material; by including it I hope to make the book accessible to a wide variety of students. Admittedly, these introductory chapters take up an unusually large portion of the book, but they are written mostly in English; the remainder of the book is written in the more concise language of mathematics.
Finally, in Chapter 6 we begin formal logic. This chapter presents and investigates a formal language that will be used throughout the remainder of the book. Among the terms defined in this chapter are "formula," "rank of a formula," "variable sharing," "generalization," "specialization," and "order preserving" and "order reversing."
There are several feasible strategies for ordering the topics after formal language. The most obvious would be to present various logics one by one - e.g., classical logic, then constructive logic, then relevant logic, etc. This strategy would juxtapose related results - e.g., constructive semantics with constructive syntactics - and perhaps it is the most desirable approach for a reference book. But I have instead elected to cover all of semantics before beginning any syntactics. This approach is better for the beginning student because semantics is more elementary and concrete than syntactics, and because this approach juxtaposes related techniques - e.g., constructive semantics and relevant semantics.
Semantics is introduced in Chapter 7, which defines "valuation," "interpretation," and "tautology." Then come some examples of interpretations - numerically valued in Chapter 8, set-valued in Chapter 9, and topological in Chapter 10. In the presentation of these examples, one recurring theme is the investigation of relevance: If A and B are formulas that are unrelated in the sense that they share no propositional variable symbols, and A -> B is a tautology in some interpretation, does it follow that [bar.A] or B are tautologies? Our conclusions are summarized in one column of the table in 2.37.
The aforementioned chapters deal with examples of semantic systems, one at a time. Chapter 11, though not lacking in examples, presents more abstract results. Sections 11.2-11.7 give shortcuts that are often applicable in verifying that a formula is tautologous. Sections 11.8-11.12 give sufficient conditions for one interpretation to be an extension of another. Sections 11.13-11.17 show that, under mild assumptions, the Dugundji formula in n symbols is tautological for interpretations with fewer than n semantic values, but not for interpretations with n or more semantic values; as a corollary we see that (again under mild assumptions) an infinite semantics cannot be replaced by a finite semantics.
Syntactics is introduced in Chapter 12, which defines "axiom," "assumed inference rule," "derivation," "theorem," etc. The chapters after that will deal with various syntactic logics, but in what order should those be presented? My strategy is as follows.
The logics of greatest philosophical interest in this book are classical, constructive (intuitionist), relevant, and fuzzy (Zadeh and Lukasiewicz), shown in the upper half of the diagram below. These logics have a substantial overlap, which I call basic logic; it appears at the bottom of the diagram. To reduce repetition, our syntactic development will begin with basic logic and then gradually add more ingredients.
Chapter 13 introduces the assumptions of basic implication,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],
and investigates their consequences. One elementary but important consequence is the availability of detachmental corollaries; that is, [??] A [right arrow] B [??] A [??] B. Chapter 14 adds the remaining assumptions of basic logic,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],
and then investigates their consequences. One consequence is a substitution principle: if S is an order preserving or order reversing function, then [??] A [right arrow] B implies, respectively, [??] S (A) [right arrow] S(B) or [??] S (B) [right arrow] S(A).
Next come several short chapters, each investigating a different one-axiom extension of basic logic:
Chapter axiom added to basic logic
15 Contraction [??](A [right arrow] (A [right arrow] B)) [right arrow] (A [right arrow] B),
16 Expansion and [??](A [right arrow] B) [right arrow] positive paradox (A [right arrow] (A [right arrow] B)), [??]A [right arrow] (B [right arrow] A)
17 Explosion [??](A [??] [bar.A]) [right arrow] or B (conjunctive) [??]A [right arrow] ([bar.A] [right arrow] B) (implicative)
18 Fusion [??][(A&B) [right arrow] X] [??] [A [right arrow] (B [right arrow] X)],
19 Not-elimination [??][??][right arrow] A,
20 Relativity [??]((A [right arrow] B) [right arrow] B) [right arrow] A.
Those extensions are considered independently of one another (i.e., results of one of those chapters may not be assumed in another of those chapters), with this exception:
relativity [??] not-elimination [??] fusion:
Anticipating the discussion below, we mention a few more one-axiom extensions :
24.5 Implicative disjunction [??]((A [right arrow] B) [right arrow] B) [right arrow] (A[??]B) 15.3.a Specialized contraction [??] (A [right arrow] (A [right arrow] [bar.A])) [right arrow] (A [right arrow] [bar.A]) 8.37.f Centering [??] (A [right arrow] A) [??] [bar.A [right arrow] A]
The preceding chapters have shown that various expressions are derivable. Chapter 21 introduces soundness, a new tool that will finally enable us to show that certain expressions are not derivable, a fact that we have only hinted at in earlier chapters. A pairing of an interpretation (semantic) with an axiomatization (syntactic) is sound if
{theorems of the [??] {tautologies of the axiomatization} interpretation}.
If equality holds, we have completeness, but that's much harder to establish and doesn't come until the end of the book. Soundness is introduced at this point because we can put it to good use in the next few chapters.
The next few chapters investigate our "major" logics:
Chapter assumptions: basic logic plus ...
22 Constructive positive paradox, contraction, explosion;
23 Relevant not-elimination and contraction;
24 Fuzzy positive paradox, implicative disjunction, specialized contraction, not-elimination;
25 Classical all of the above;
26 Abelian relativity and centering.
These chapters include, among other things, several deduction principles, converses to the detachmental corollary procedure; see 2.37.
Chapter 27 proves the propositional version of Harrop's admissibility rule for constructive logic. The proof is via Meyer's "metavaluation," a computational device that is a sort of mixture of semantics and syntactics. Two corollaries are the Disjunction Property and Mints's Admissibility Rule. The latter is the most elementary example of an admissibility rule that is not also a derivable inference rule. (That admissibility and derivability are the same in classical logic is proved in 29.15.)
Finally, we prove some completeness pairings. Proofs for constructive implication and relevant implication, in Chapter 28, use Kripke-style "multiple worlds" interpretations. Proofs for classical, fuzzy, and constructive logic are presented in Chapter 29, all using what I call "maximal Z-unproving sets" - i.e., sets S that are maximal for the property that S [??] Z.
1.8. What to cover; what to skip. That's up to the individual instructor's own taste, but here are a few suggestions and hints based on my own teaching experience.
(Continues...)
Excerpted from Classical and Nonclassical Logics by Eric Schechter Copyright © 2005 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
| A | Preliminaries | 1 |
| 1 | Introduction for teachers | 3 |
| Purpose and intended audience | 3 | |
| Topics in the book | 6 | |
| Why pluralism? | 13 | |
| Feedback | 18 | |
| Acknowledgments | 19 | |
| 2 | Introduction for students | 20 |
| Who should study logic? | 20 | |
| Formalism and certification | 25 | |
| Language and levels | 34 | |
| Semantics and syntactics | 39 | |
| Historical perspective | 49 | |
| Pluralism | 57 | |
| Jarden's example (optional) | 63 | |
| 3 | Informal set theory | 65 |
| Sets and their members | 68 | |
| Russell's paradox | 77 | |
| Subsets | 79 | |
| Functions | 84 | |
| The Axiom of Choice (optional) | 92 | |
| Operations on sets | 94 | |
| Venn diagrams | 102 | |
| Syllogisms (optional) | 111 | |
| Infinite sets (postponable) | 116 | |
| 4 | Topologies and interiors (postponable) | 126 |
| Topologies | 127 | |
| Interiors | 133 | |
| Generated topologies and finite topologies (optional) | 139 | |
| 5 | English and informal classical logic | 146 |
| Language and bias | 146 | |
| Parts of speech | 150 | |
| Semantic values | 151 | |
| Disjunction (or) | 152 | |
| Conjunction (and) | 155 | |
| Negation (not) | 156 | |
| Material implication | 161 | |
| Cotenability, fusion, and constants (postponable) | 170 | |
| Methods of proof | 174 | |
| Working backwards | 177 | |
| Quantifiers | 183 | |
| Induction | 195 | |
| Induction examples (optional) | 199 | |
| 6 | Definition of a formal language | 206 |
| The alphabet | 206 | |
| The grammar | 210 | |
| Removing parentheses | 215 | |
| Defined symbols | 219 | |
| Prefix notation (optional) | 220 | |
| Variable sharing | 221 | |
| Formula schemes | 222 | |
| Order preserving or reversing subformulas (postponable) | 228 | |
| B | Semantics | 233 |
| 7 | Definitions for semantics | 235 |
| Interpretations | 235 | |
| Functional interpretations | 237 | |
| Tautology and truth preservation | 240 | |
| 8 | Numerically valued interpretations | 245 |
| The two-valued interpretation | 245 | |
| Fuzzy interpretations | 251 | |
| Two integer-valued interpretations | 258 | |
| More about comparative logic | 262 | |
| More about Sugihara's interpretation | 263 | |
| 9 | Set-valued interpretations | 269 |
| Powerset interpretations | 269 | |
| Hexagon interpretation (optional) | 272 | |
| The crystal interpretation | 273 | |
| Church's diamond (optional) | 277 | |
| 10 | Topological semantics (postponable) | 281 |
| Topological interpretations | 281 | |
| Examples | 282 | |
| Common tautologies | 285 | |
| Nonredundancy of symbols | 286 | |
| Variable sharing | 289 | |
| Adequacy of finite topologies (optional) | 290 | |
| Disjunction property (optional) | 293 | |
| 11 | More advanced topics in semantics | 295 |
| Common tautologies | 295 | |
| Images of interpretations | 301 | |
| Dugundji formulas | 307 | |
| C | Basic syntactics | 311 |
| 12 | Inference systems | 313 |
| 13 | Basic implication | 318 |
| Assumptions of basic implication | 319 | |
| A few easy derivations | 320 | |
| Lemmaless expansions | 326 | |
| Detachmental corollaries | 330 | |
| Iterated implication (postponable) | 332 | |
| 14 | Basic logic | 336 |
| Further assumptions | 336 | |
| Basic positive logic | 339 | |
| Basic negation | 341 | |
| Substitution principles | 343 | |
| D | One-formula extensions | 349 |
| 15 | Contraction | 351 |
| Weak contraction | 351 | |
| Contraction | 355 | |
| 16 | Expansion and positive paradox | 357 |
| Expansion and mingle | 357 | |
| Positive paradox (strong expansion) | 359 | |
| Further consequences of positive paradox | 362 | |
| 17 | Explosion | 365 |
| 18 | Fusion | 369 |
| 19 | Not-elimination | 372 |
| Not-elimination and contrapositives | 372 | |
| Interchangeability results | 373 | |
| Miscellaneous consequences of notelimination | 375 | |
| 20 | Relativity | 377 |
| E | Soundness and major logics | 381 |
| 21 | Soundness | 383 |
| 22 | Constructive axioms: avoiding not-elimination | 385 |
| Constructive implication | 386 | |
| Herbrand-Tarski Deduction Principle | 387 | |
| Basic logic revisited | 393 | |
| Soundness | 397 | |
| Nonconstructive axioms and classical logic | 399 | |
| Glivenko's Principle | 402 | |
| 23 | Relevant axioms: avoiding expansion | 405 |
| Some syntactic results | 405 | |
| Relevant deduction principle (optional) | 407 | |
| Soundness | 408 | |
| Mingle: slightly irrelevant | 411 | |
| Positive paradox and classical logic | 415 | |
| 24 | Fuzzy axioms: avoiding contraction | 417 |
| Axioms | 417 | |
| Meredith's chain proof | 419 | |
| Additional notations | 421 | |
| Wajsberg logic | 422 | |
| Deduction principle for Wajsberg logic | 426 | |
| 25 | Classical logic | 430 |
| Axioms | 430 | |
| Soundness results | 431 | |
| Independence of axioms | 431 | |
| 26 | Abelian logic | 437 |
| F | Advanced results | 441 |
| 27 | Harrop's principle for constructive logic | 443 |
| Meyer's valuation | 443 | |
| Harrop's principle | 448 | |
| The disjunction property | 451 | |
| Admissibility | 451 | |
| Results in other logics | 452 | |
| 28 | Multiple worlds for implications | 454 |
| Multiple worlds | 454 | |
| Implication models | 458 | |
| Soundness | 460 | |
| Canonical models | 461 | |
| Completeness | 464 | |
| 29 | Completeness via maximality | 466 |
| Maximal unproving sets | 466 | |
| Classical logic | 470 | |
| Wajsberg logic | 477 | |
| Constructive logic | 479 | |
| Non-finitely-axiomatizable logics | 485 | |
| References | 487 | |
| Symbol list | 493 | |
| Index | 495 |
What People are Saying About This
This is a fine introduction to relevance and intuitionist logics and the basic notions of metalogic, with classical logic introduced as a necessary contrast. It will be a valuable addition to the literature, especially as some of the topics covered have long been the preserve of specialists. Though I have worked in philosophical logic for many years, it taught me things I should have known long ago.
— Bernard Linsky, University of Alberta, author of "Russell's Metaphysical Logic"
Offering a rich combination and breadth of material, this book is practically an encyclopedia of schools of logic; it is a convenient reference, lucidly describing complex ideas in various schools of logic that are traditionally not treated in a single book. The writing is fluent, clear, and detailed; the exposition is solid and successfully clarifies topics that are usually difficult for beginners to understand.
— Iraj Kalantari, Western Illinois University
This is a very good introduction to a broad array of logics. Particularly interesting is the treatment of algebraic and topological semantics, which are only found in more advanced treatments of the same topics. The author does a great job motivating, presenting, and addressing the different formalisms.
— G. Aldo Antonelli, University of California, Irvine; Editor, "Journal of Philosophical Logic"
"Offering a rich combination and breadth of material, this book is practically an encyclopedia of schools of logic; it is a convenient reference, lucidly describing complex ideas in various schools of logic that are traditionally not treated in a single book. The writing is fluent, clear, and detailed; the exposition is solid and successfully clarifies topics that are usually difficult for beginners to understand."—Iraj Kalantari, Western Illinois University
"This is a fine introduction to relevance and intuitionist logics and the basic notions of metalogic, with classical logic introduced as a necessary contrast. It will be a valuable addition to the literature, especially as some of the topics covered have long been the preserve of specialists. Though I have worked in philosophical logic for many years, it taught me things I should have known long ago."—Bernard Linsky, University of Alberta, author of Russell's Metaphysical Logic
"This is a very good introduction to a broad array of logics. Particularly interesting is the treatment of algebraic and topological semantics, which are only found in more advanced treatments of the same topics. The author does a great job motivating, presenting, and addressing the different formalisms."—G. Aldo Antonelli, University of California, Irvine; Editor, Journal of Philosophical Logic