Language, Proof and Logic

Title Page......Page 3
Acknowledgements......Page 5
Contents......Page 7
The special role of logic in rational inquiry......Page 13
Web address......Page 27
Why learn an artificial language?......Page 14
Consequence and proof......Page 16
Essential instructions about homework exercises......Page 17
To the instructor......Page 22
1.1 Individual constants......Page 31
1.2 Predicate symbols......Page 32
1.3 Atomic sentences......Page 35
1.4 General first-order languages......Page 40
1.5 Function symbols......Page 43
1.6 The first-order language of set theory......Page 49
Exercise 1.19......Page 50
1.8 Alternative notation......Page 52
Exercises 1.1 -- 1.7......Page 37
Exercises 1.8 -- 1.11......Page 41
Exercises 1.12 -- 1.18......Page 46
Exercises 1.20 -- 1.22......Page 51
2.1 Valid and sound arguments......Page 53
2.2 Methods of proof......Page 58
2.3 Formal proofs......Page 66
2.4 Constructing proofs in Fitch......Page 70
2.5 Demonstrating nonconsequence......Page 75
2.6 Alternative notation......Page 78
Exercises 2.1 -- 2.4......Page 56
Exercises 2.5 -- 2.14......Page 65
Exercises 2.15 -- 2.20......Page 74
Exercises 2.21 -- 2.27......Page 77
3 The Boolean Connectives......Page 79
3.1 Negation symbol: ¬......Page 80
3.2 Conjunction symbol: ∧......Page 83
3.3 Disjunction symbol: ∨......Page 86
3.4 Remarks about the game......Page 89
Exercise 3.11......Page 91
3.6 Equivalent ways of saying things......Page 94
3.7 Translation......Page 96
3.8 Alternative notation......Page 101
Exercises 3.1 -- 3.4......Page 82
Exercises 3.5 -- 3.7......Page 85
Exercises 3.8 -- 3.10......Page 88
Exercises 3.12 -- 3.17......Page 93
Exercises 3.18 -- 3.19......Page 95
Exercises 3.20 -- 3.25......Page 98
Exercises 3.26 -- 3.29......Page 103
4 The Logic of Boolean Connectives......Page 105
4.1 Tautologies and logical truth......Page 106
4.2 Logical and tautological equivalence......Page 118
4.3 Logical and tautological consequence......Page 122
4.4 Tautological consequence in Fitch......Page 126
4.5 Pushing negation around......Page 129
4.6 Conjunctive and disjunctive normal forms......Page 133
Exercises 4.1 -- 4.11......Page 116
Exercises 4.12 -- 4.19......Page 121
Exercises 4.20 -- 4.25......Page 125
Exercises 4.26 -- 4.30......Page 128
Exercises 4.31 -- 4.37......Page 132
Exercises 4.38 -- 4.43......Page 137
5 Methods of Proof for Boolean Logic......Page 139
5.1 Valid inference steps......Page 140
Exercises 5.1 -- 5.6......Page 143
5.3 Indirect proof: proof by contradiction......Page 148
5.4 Arguments with inconsistent premises......Page 152
Exercises 5.7 -- 5.14......Page 146
Exercises 5.15 -- 5.26......Page 151
Exercise 5.27......Page 153
6 Formal Proofs and Boolean Logic......Page 154
6.1 Conjunction rules......Page 155
6.2 Disjunction rules......Page 160
Exercises 6.1 -- 6.6......Page 166
6.4 The proper use of subproofs......Page 175
6.5 Strategy and tactics......Page 179
6.6 Proofs without premises......Page 185
Exercises 6.7 -- 6.16......Page 173
Exercises 6.17 -- 6.20......Page 178
Exercises 6.21 -- 6.32......Page 184
Exercises 6.33 -- 6.42......Page 186
7 Conditionals......Page 188
7.1 Material conditional symbol: →......Page 190
7.2 Biconditional symbol: ↔......Page 193
7.3 Conversational implicature......Page 199
Exercises 7.22 -- 7.24......Page 202
7.5 Alternative notation......Page 208
Exercises 7.1 -- 7.21......Page 195
Exercises 7.25 -- 7.32......Page 206
8.1 Informal methods of proof......Page 210
8.2 Formal rules of proof for → and ↔......Page 218
8.3 Soundness and completeness......Page 226
8.4 Valid arguments: some review exercises......Page 234
Exercises 8.1 -- 8.16......Page 215
Exercises 8.17 -- 8.38......Page 224
Exercises 8.39 -- 8.43......Page 233
Exercises 8.44 -- 8.53......Page 235
9 Introduction to Quantification......Page 239
9.1 Variables and atomic wffs......Page 240
9.2 The quantifier symbols: ∀, ∃......Page 242
9.3 Wffs and sentences......Page 243
Exercises 9.1 -- 9.3......Page 246
9.5 The four Aristotelian forms......Page 251
9.6 Translating complex noun phrases......Page 255
9.7 Quantifiers and function symbols......Page 263
9.8 Alternative notation......Page 267
Exercises 9.4 -- 9.7......Page 250
Exercises 9.8 -- 9.14......Page 253
Exercises 9.15 -- 9.21......Page 259
Exercises 9.22 -- 9.25......Page 265
Exercise 9.26......Page 268
10.1 Tautologies and quantification......Page 269
10.2 First-order validity and consequence......Page 278
10.3 First-order equivalence and DeMorgan’s laws......Page 287
10.4 Other quantifier equivalences......Page 292
10.5 The axiomatic method......Page 295
Exercises 10.1 -- 10.7......Page 276
Exercises 10.8 -- 10.19......Page 285
Exercises 10.20 -- 10.22......Page 291
Exercises 10.23 -- 10.29......Page 294
Exercises 10.30 -- 10.31......Page 300
11.1 Multiple uses of a single quantifier......Page 301
11.2 Mixed quantifiers......Page 305
11.3 The step-by-step method of translation......Page 310
11.4 Paraphrasing English......Page 312
11.5 Ambiguity and context sensitivity......Page 316
11.6 Translations using function symbols......Page 320
11.7 Prenex form......Page 323
Exercises 11.33 -- 11.38......Page 327
Exercises 11.1 -- 11.7......Page 303
Exercises 11.8 -- 11.15......Page 308
Exercises 11.16 -- 11.17......Page 311
Exercises 11.18 -- 11.23......Page 314
Exercises 11.24 -- 11.28......Page 319
Exercises 11.29 -- 11.32......Page 322
Exercises 11.39 -- 11.45......Page 328
12.1 Valid quantifier steps......Page 331
12.2 The method of existential instantiation......Page 334
12.3 The method of general conditional proof......Page 335
12.4 Proofs involving mixed quantifiers......Page 341
12.5 Axiomatizing shape......Page 350
Exercises 12.1 -- 12.10......Page 339
Exercises 12.11 -- 12.29......Page 346
Exercises 12.30 -- 12.38......Page 353
13.1 Universal quantifier rules......Page 354
13.2 Existential quantifier rules......Page 359
13.3 Strategy and tactics......Page 364
Exercises 13.40 -- 13.58......Page 373
Exercises 13.1 -- 13.9......Page 358
Exercises 13.10 -- 13.18......Page 362
Exercises 13.19 -- 13.39......Page 370
14 More about Quantification......Page 376
14.1 Numerical quantification......Page 378
14.2 Proving numerical claims......Page 386
14.3 The, both, and neither......Page 391
14.4 Adding other determiners to fol......Page 395
14.5 The logic of generalized quantification......Page 401
14.6 Other expressive limitations of first-order logic......Page 409
Exercises 14.1 -- 14.9......Page 383
Exercises 14.55 -- 14.63......Page 410
Exercises 14.33 -- 14.54......Page 407
Exercises 14.30 -- 14.32......Page 400
Exercises 14.26 -- 14.29......Page 394
Exercises 14.10 -- 14.25......Page 389
15 First-order Set Theory......Page 417
15.1 Naive set theory......Page 418
15.2 Singletons, the empty set, subsets......Page 424
15.3 Intersection and union......Page 427
15.4 Sets of sets......Page 431
15.5 Modeling relations in set theory......Page 434
15.6 Functions......Page 439
15.7 The powerset of a set......Page 441
15.8 Russell’s Paradox......Page 444
15.9 Zermelo Frankel set theory ZFC......Page 445
Exercises 15.1 -- 15.6......Page 423
Exercises 15.7 -- 15.13......Page 426
Exercises 15.14 -- 15.22......Page 430
Exercises 15.23 -- 15.28......Page 433
Exercises 15.29 -- 15.45......Page 437
Exercises 15.46 -- 15.53......Page 440
Exercises 15.54 -- 15.61......Page 443
Exercises 15.62 -- 15.74......Page 452
16 Mathematical Induction......Page 454
16.1 Inductive definitions and inductive proofs......Page 455
16.2 Inductive definitions in set theory......Page 463
Exercises 16.11 -- 16.13......Page 465
16.4 Axiomatizing the natural numbers......Page 468
Exercises 16.19 -- 16.26......Page 470
Exercises 16.1 -- 16.10......Page 461
Exercises 16.14 -- 16.18......Page 467
Exercises 16.27 -- 16.31......Page 476
17.1 Truth assignments and truth tables......Page 480
Exercises 17.1 -- 17.3......Page 482
17.3 Horn sentences......Page 491
17.4 Resolution......Page 500
Exercises 17.4 -- 17.16......Page 489
Exercises 17.17 -- 17.30......Page 498
Exercises 17.31 -- 17.45......Page 504
18.1 First-order structures......Page 507
18.2 Truth and satisfaction, revisited......Page 512
18.3 Soundness for FOL......Page 521
Exercises 18.14 -- 18.17......Page 524
Exercises 18.18 -- 18.19......Page 526
Exercises 18.20 -- 18.21......Page 528
Exercises 18.22 -- 18.26......Page 531
Exercises 18.1 -- 18.6......Page 510
Exercises 18.7 -- 18.13......Page 519
Exercises 18.27 -- 18.30......Page 536
19 Completeness and Incompleteness......Page 538
19.1 The Completeness Theorem for fol......Page 539
19.2 Adding witnessing constants......Page 541
Exercise 19.1......Page 543
19.4 The Elimination Theorem......Page 546
19.5 The Henkin Construction......Page 552
19.6 The L¨owenheim-Skolem Theorem......Page 558
19.7 The Compactness Theorem......Page 560
19.8 The G¨odel Incompleteness Theorem......Page 564
Exercises 19.2 -- 19.9......Page 545
Exercises 19.10 -- 19.18......Page 550
Exercises 19.19 -- 19.23......Page 557
Exercises 19.24 -- 19.31......Page 563
Exercises 19.32 -- 19.34......Page 567
Summary of Rules......Page 569
Glossary......Page 574
General Index......Page 585
Exercise Files Index......Page 597