ISBN-10:
0691122792
ISBN-13:
9780691122793
Pub. Date:
08/28/2005
Publisher:
Princeton University Press
Classical and Nonclassical Logics: An Introduction to the Mathematics of Propositions

Classical and Nonclassical Logics: An Introduction to the Mathematics of Propositions

by Eric Schechter

Hardcover

Current price is , Original price is $130.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

Product Details

ISBN-13: 9780691122793
Publisher: Princeton University Press
Publication date: 08/28/2005
Edition description: New Edition
Pages: 520
Product dimensions: 6.00(w) x 9.25(h) x (d)

About the Author

Eric Schechter, Associate Professor of Mathematics at Vanderbilt University, is the author of Handbook of Analysis and Its Foundations.

Read an Excerpt

Classical and Nonclassical Logics

An Introduction to the Mathematics of Proposition

Chapter 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





Chapter 1: Introduction for teachers 3

Purpose and intended audience, 3

Topics in the book, 6

Why pluralism?, 13

Feedback, 18

Acknowledgments, 19





Chapter 2: Introduction for students 20

Who should study logic?, 20

Formalism and certication, 25

Language and levels, 34

Semantics and syntactics, 39

Historical perspective, 49

Pluralism, 57

Jarden's example (optional), 63





Chapter 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





Chapter 4: Topologies and interiors (postponable) 126

Topologies, 127

Interiors, 133

Generated topologies and finite topologies (optional), 139





Chapter 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





Chapter 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





Chapter 7: Definitions for semantics 235

Interpretations, 235

Functional interpretations, 237

Tautology and truth preservation, 240

Chapter 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





Chapter 9: Set-valued interpretations 269

Powerset interpretations, 269

Hexagon interpretation (optional), 272

The crystal interpretation, 273

Church's diamond (optional), 277

Chapter 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





Chapter 11: More advanced topics in semantics 295

Common tautologies, 295

Images of interpretations, 301

Dugundji formulas, 307





C Basic syntactics 311





Chapter 12: Inference systems 313





Chapter 13: Basic implication 318

Assumptions of basic implication, 319

A few easy derivations, 320

Lemmaless expansions, 326

Detachmental corollaries, 330

Iterated implication (postponable), 332





Chapter 14: Basic logic 336

Further assumptions, 336

Basic positive logic, 339

Basic negation, 341

Substitution principles, 343





D One-formula extensions 349





Chapter 15: Contraction 351

Weak contraction, 351

Contraction, 355





Chapter 16: Expansion and positive paradox 357

Expansion and mingle, 357

Positive paradox (strong expansion), 359

Further consequences of positive paradox, 362





Chapter 17: Explosion 365





Chapter 18: Fusion 369





Chapter 19: Not-elimination 372

Not-elimination and contrapositives, 372

Interchangeability results, 373

Miscellaneous consequences of not-elimination, 375





Chapter 20: Relativity 377





E Soundness and major logics 381





Chapter 21: Soundness 383





Chapter 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





Chapter 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





Chapter 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





Chapter 25: Classical logic 430

Axioms, 430

Soundness results, 431

Independence of axioms, 431





Chapter 26: Abelian logic 437





F Advanced results 441





Chapter 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





Chapter 28: Multiple worlds for implications 454

Multiple worlds, 454

Implication models, 458

Soundness, 460

Canonical models, 461

Completeness, 464





Chapter 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

Bernard Linsky

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"

G. Aldo Antonelli

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"

Iraj Kalantari

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

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews