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 certi¯-

cation, 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 dia-

grams, 102 *²* Syllogisms (optional), 111 *²* In¯nite sets

(postponable), 116

4 Topologies and interiors (postponable) 126

*²* Topologies, 127 *²* Interiors, 133 *²* Generated topologies

and ¯nite topologies (optional), 139

5 English and informal classical logic 146

*²* Language and bias, 146 *²* Parts of speech, 150 *²* Semantic values, 151 *²* Disjunction (or), 152 *²* Con-

junction (and), 155 *²* Negation (not), 156 *²* Material

implication, 161 *²* Cotenability, fusion, and constants

vi *Contents*

(postponable), 170 *²* Methods of proof, 174 *²* Working

backwards, 177 *²* Quanti¯ers, 183 *²* Induction, 195 *²* Induction examples (optional), 199

6 De¯nition of a formal language 206

*²* The alphabet, 206 *²* The grammar, 210 *²* Removing

parentheses, 215 *²* De¯ned symbols, 219 *²* Pre¯x

notation (optional), 220 *²* Variable sharing, 221 *²* Formula schemes, 222 *²* Order preserving or reversing

subformulas (postponable), 228

B Semantics 233

7 De¯nitions for semantics 235

*²* Interpretations, 235 *²* Functional interpretations, 237

*²* Tautology and truth preservation, 240

8 Numerically valued interpretations 245

*²* The two-valued interpretation, 245 *²* Fuzzy interpre-

tations, 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 sym-

bols, 286 *²* Variable sharing, 289 *²* Adequacy of ¯nite

topologies (optional), 290 *²* Disjunction property (op-

tional), 293

*Contents* vii

11 More advanced topics in semantics 295

*²* Common tautologies, 295 *²* Images of interpreta-

tions, 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 *²* De-

tachmental corollaries, 330 *²* Iterated implication (post-

ponable), 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 para-

dox, 362

17 Explosion 365

18 Fusion 369

19 Not-elimination 372

*²* Not-elimination and contrapositives, 372 *²* Interchange-

ability results, 373 *²* Miscellaneous consequences of not-

elimination, 375

viii *Contents*

20 Relativity 377

E Soundness and major logics 381

21 Soundness 383

22 Constructive axioms: avoiding not-elimination 385

*²* Constructive implication, 386 *²* Herbrand-Tarski De-

duction 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 *²* Addi-

tional 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

*Contents* ix

28 Multiple worlds for implications 454

*²* Multiple worlds, 454 *²* Implication models, 458 *²* Soundness, 460 *²* Canonical models, 461 *²* Complete-

ness, 464

29 Completeness via maximality 466

*²* Maximal unproving sets, 466 *²* Classical logic, 470

*²* Wajsberg logic, 477 *²* Constructive logic, 479 *²* Non-¯nitely-axiomatizable logics, 485

References 487

Symbol list 493

Index 495

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 certi¯-

cation, 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 dia-

grams, 102 *²* Syllogisms (optional), 111 *²* In¯nite sets

(postponable), 116

4 Topologies and interiors (postponable) 126

*²* Topologies, 127 *²* Interiors, 133 *²* Generated topologies

and ¯nite topologies (optional), 139

5 English and informal classical logic 146

*²* Language and bias, 146 *²* Parts of speech, 150 *²* Semantic values, 151 *²* Disjunction (or), 152 *²* Con-

junction (and), 155 *²* Negation (not), 156 *²* Material

implication, 161 *²* Cotenability, fusion, and constants

vi *Contents*

(postponable), 170 *²* Methods of proof, 174 *²* Working

backwards, 177 *²* Quanti¯ers, 183 *²* Induction, 195 *²* Induction examples (optional), 199

6 De¯nition of a formal language 206

*²* The alphabet, 206 *²* The grammar, 210 *²* Removing

parentheses, 215 *²* De¯ned symbols, 219 *²* Pre¯x

notation (optional), 220 *²* Variable sharing, 221 *²* Formula schemes, 222 *²* Order preserving or reversing

subformulas (postponable), 228

B Semantics 233

7 De¯nitions for semantics 235

*²* Interpretations, 235 *²* Functional interpretations, 237

*²* Tautology and truth preservation, 240

8 Numerically valued interpretations 245

*²* The two-valued interpretation, 245 *²* Fuzzy interpre-

tations, 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 sym-

bols, 286 *²* Variable sharing, 289 *²* Adequacy of ¯nite

topologies (optional), 290 *²* Disjunction property (op-

tional), 293

*Contents* vii

11 More advanced topics in semantics 295

*²* Common tautologies, 295 *²* Images of interpreta-

tions, 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 *²* De-

tachmental corollaries, 330 *²* Iterated implication (post-

ponable), 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 para-

dox, 362

17 Explosion 365

18 Fusion 369

19 Not-elimination 372

*²* Not-elimination and contrapositives, 372 *²* Interchange-

ability results, 373 *²* Miscellaneous consequences of not-

elimination, 375

viii *Contents*

20 Relativity 377

E Soundness and major logics 381

21 Soundness 383

22 Constructive axioms: avoiding not-elimination 385

*²* Constructive implication, 386 *²* Herbrand-Tarski De-

duction 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 *²* Addi-

tional 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

*Contents* ix

28 Multiple worlds for implications 454

*²* Multiple worlds, 454 *²* Implication models, 458 *²* Soundness, 460 *²* Canonical models, 461 *²* Complete-

ness, 464

29 Completeness via maximality 466

*²* Maximal unproving sets, 466 *²* Classical logic, 470

*²* Wajsberg logic, 477 *²* Constructive logic, 479 *²* Non-¯nitely-axiomatizable logics, 485

References 487

Symbol list 493

Index 495