search for books and compare prices
Tables of Contents for Computability and Logic
Chapter/Section Title
Page #
Page Count
Preface
ix
2
Preface to the third edition
xi
 
1 Enumerability
1
10
2 Diagonalization
11
8
3 Turing machines
19
15
4 Uncomputability via the busy beaver problem
34
9
5 Uncomputability via diagonalization
43
9
6 Abacus computable functions are Turing computable
52
18
7 Recursive functions are abacus computable
70
19
8 Turing computable functions are recursive
89
7
9 First-order logic revisited
96
16
10 First-order logic is undecidable
112
9
11 First-order logic formalized: derivations and soundness
121
10
12 Completeness of the formalization; compactness
131
16
13 The Skolem-Lowenheim theorem
147
10
14 Representability in Q
157
13
15 Undecidability, indefinability and incompleteness
170
12
16 Provability predicates and the unprovability of consistency
182
9
17 Non-standard models of arithmetic
191
6
18 Second-order logic
197
10
19 On defining arithmetical truth
207
5
20 Definability in arithmetic and forcing
212
7
21 The decidability of arithmetic with addition, but not multiplication
219
9
22 Dyadic logic is undecidable: `eliminating' names and function symbols
228
6
23 The Craig interpolation lemma
234
9
24 Two applications of Craig's lemma
243
7
25 Monadic versus dyadic logic
250
10
26 Ramsey's theorem
260
8
27 Provability considered modal-logically
268
17
28 Undecidable sentences
285
8
29 Non-standard models of Z are not recursive
293
8
Index
301