<<

. 105
( 107 .)



>>




General Index
General Index / 577



extension of a predicate, 422, 497, partial on a domain, 427
498 range of, 428
total on a domain, 427
¬les function symbols, 31, 31“34, 229,
naming, 6“7 308, 514, 516
submitting, 5“10 and quanti¬cation, 251“253
¬rst-order completeness for languages with,
consequence, 267, 505 544
logic, 2 of arithmetic, 38
structure, 498, 495“498, 500 functional calculus, 2
validity, 267, 505
vs. second-order, 257
game, 67, 77
¬rst-order languages, 2
Henkin-Hintikka, 67
arithmetic, 38
rules, 78, 237
expressive limitations of, 397“
for §, 72
398
for ”, 182
set theory, 37
for ¬, 68
¬rst-order logic
for ’, 178
language of, (fol), 2
for ∨, 75
Fitch, 5“10, 14, 58
for quanti¬ers, 237“238
bar, 43, 54
winning strategy, 78
format, 43
general conditional proof, 323“327,
Fitch, Frederic, 43, 54
329, 332, 342, 442
Fitch-style deductive system, 14, 54,
G¨del
o
149, 163
Incompleteness Theorem, 552“
extended, 376
555
FO Con, 115, 158, 271, 272, 286,
numbering, 553
524
G¨del, Kurt, 526, 546
o
fo-satis¬able, 506
Grade Grinder, 5“10, 12“13
formal proof, 54, 142, 206, 376
Grice, H. P., 188
formally complete theory, 472
Grice™s cancellability test, 188
formally consistent theory, 471
free logic, 20n
Henkin
free variable, 232
construction, 528, 540“545
Frege, Gottlob, 3
Construction Lemma, 540
function, 427
theory, 528, 532
domain of, 427
Henkin, Leon, 67
modeling in set theory, 427“
Henkin-Hintikka game, 67
428
Hintikka, Jaakko, 67
partial
de¬ned on an object, 428 Horn, Alfred, 479



General Index
578 / General Index


Horn sentence, 479 inductive clause, 444, 445
theory of, 465
conditional form of, 481
inductive hypothesis, 446
satisfaction algorithm for, 479,
inductive proof, 445“449
481, 484
in¬x notation, 23, 33, 37, 38, 90
inherently vacuous claim, 246
idempotence
instantiation
of §, 119
existential, 322“323
of ∨, 119
intended domain of discourse, 236
identity, 25, 37
interpreted language, 15
elimination, 55
intersection, 415, 416
in proofs, 49
introduction rules, 142
introduction, 55
intuitionism, 355
re¬‚exivity of, 50, 51
invariance under motion, 400, 401
symmetry of, 50, 51
inventor™s paradox, 447
transitivity of, 51
inverse, 52
i¬, 182
irrational numbers, 131, 136, 205
if. . . then. . . else, 194
irre¬‚exivity, 422
implicature, 187, 188, 244“247, 381
inclusive disjunction, 74
Jabberwocky, 268
Incompleteness Theorem, 526, 552“
Je¬rey, Richard, 555
555
inconsistent premises, 140
Kleene, Stephen, 515
independence, 297
Independence lemma, 531 language
indirect proof, 136“138 arti¬cial, 2“4
indiscernibility of identicals, 49, 51 blocks world, 19, 21
individual constants, 19, 20, 32 ¬rst-order, 28
induction, 376 interpreted, 15
and proving programs correct, natural, 4
458“464 uninterpreted, 15
mathematical, 70, 442 language of ¬rst-order logic, 2
on the natural numbers, 453“ expressive limitations, 71, 85,
455 176, 383
induction step for arithmetic, 38
of proof by induction, 449 for set theory, 37
inductive clause law of excluded middle, 97
of inductive de¬nition, 444, 445 laws of logic, 1
inductive de¬nition, 39, 442“445 lemma, 452
base clause, 444, 445 Levy, Azriel, 435
in set theory, 451“453 liar™s paradox, 555



General Index
General Index / 579



tw-, 102
literal, 68, 69, 118, 122, 123, 479
condition, 179
L¨b™s paradox, 556
o
logically, 103, 137
logical
negation, 67, 68
consequence, 2, 4“5, 505, 526
double, 68, 83, 83
dependence, 51, 105
elimination, 155
truth, 94, 505
introduction, 136, 155
validity, 42
normal form, 118“122
logically equivalent w¬s, 276
scope of, 80
Lo´, J., 400
s
non-logical truth in all worlds, 363
L¨wenheim, Leopold, 546
o
nonstandard models
L¨wenheim-Skolem Theorem, 546
o
of arithmetic, 548
lower predicate calculus, 2
of set theory, 547
Mary Ellen™s World, 496, 498, 499 normal form
material biconditional, 181, 198 conjunctive (CNF), 121“125, 312,
material conditional, 178 479
usefulness of, 198 disjunctive (DNF), 121“125
meaning, 84 negation, 118“122
meaning postulates, 284 prenex, 281, 311“315
method of counterexample, 5, 15, Skolem, 515
63 noun phrase, 239
method of proof, 5, 46, 128, 198, complex, 243
329 plural, 398
by cases, 131“134 quanti¬ed, 298, 304
by contradiction, 136“138 existential, 243, 247
conditional, 199 universal, 243, 248
general, 325 null quanti¬cation, 281
mixed quanti¬ers, 293, 296, 329 numerical claim, 366, 374
modus ponens, 198, 199, 206
ordered pair, 420, 421
modus tollens, 203, 212
monkey principle, 187
pa, 456
monotone operator, 465
palindrome, 448, 450
multiple quanti¬ers, 289
paraphrasing English, 300
names, 19, 20 parentheses, 79, 80, 101, 147, 148,
in English, 20 233
introducing new, 29 alternatives to, 90
natural deduction, 142 partition, 426
natural language, 4 Peano, Giuseppe, 456
necessary Peano arithmetic, 456“457
tt-, 102 Peano, Giuseppe, 3



General Index
580 / General Index


Peirce, Charles Sanders, 3 formal vs informal, 48“49
persistence general conditional, 323“327,
329, 342
through expansion, 400
under growth, 401 indirect, 136“138
Phred, 260“261 informal
plural noun phrases, 398 purposes of, 129“130
Polish notation, 90, 91, 196 style, 48, 129
possessives, 515 involving numerical determin-
possible ers, 374“376
involving the identity symbol,
tt-, 102
49
tw-, 102
of nonconsequence, 15, 63
logically, 95, 137
of uniqueness claims, 375
powerset, 429
purported, 327
axiom, 436
step, 198, 319
predicate, 19, 21, 25
strategy, 167, 171, 206, 210,
vs function symbol, 32
352
argument, 21
with no premises, 173
arity, 21
working backwards, 167
extension of, 422, 497, 498
proposition, 24
introducing new, 28
symbols, 20
quanti¬cation
pre¬x notation, 23, 33, 90
numerical, 366“371
premises, 41, 44
inconsistent, 140 and proofs, 374“376
quanti¬ed noun phrase, 227, 298,
prenex form, 281, 289, 311“315, 520
304
presuppositions, 286
quanti¬er
and determiners, 380
equivalences, 280, 282
and the axiomatic method, 287
existential, 230“231
prime number, 242, 332, 333
scope, 233
Prolog, 3
uniqueness, 375

<<

. 105
( 107 .)



>>