1 Introduction ............................................... 1
Leon Horsten and Philip Welch
1.1 Gödel's Disjunction and Beyond ............................. 1
1.1.1 The Disjunctive Thesis .............................. 2
1.1.2 The First Disjunct .................................. 2
1.1.3 The Second Disjunct ................................. 3
1.2 Formal Frameworks .......................................... 4
1.2.1 Mathematical Philosophy to the Rescue? .............. 4
1.2.2 Epistemic Mathematics ............................... 5
1.2.3 Computation and the Nature of Algorithm ............. 6
1.3 Organisation of the Contributions .......................... 7
1.3.1 Algorithm, Consistency, and Epistemic Randomness .... 7
1.3.1.1 Dean ............................................ 7
1.3.1.2 Visser .......................................... 8
1.3.1.3 Moschovakis ..................................... 9
1.3.1.4 Achourioti ...................................... 9
1.3.2 Minds and Machines ................................. 10
1.3.2.1 Carlson ........................................ 10
1.3.2.2 Koellner ....................................... 10
1.3.2.3 Shapiro ........................................ 12
1.3.3 Absolute Undecidability ............................ 12
1.3.3.1 Leach-Krouse ................................... 12
1.3.3.2 Williamson ..................................... 13
1.3.3.3 Antonutti and Horsten .......................... 13
References ................................................ 14
PART I ALGORITHM, CONSISTENCY, AND EPISTEMIC RANDOMNESS
2 Algorithms and the Mathematical Foundations of Computer
Science ................................................... 19
Walter Dean
2.1 Introduction .............................................. 19
2.2 Motivating Algorithmic Realism ............................ 24
2.3 Algorithms in Theoretical Computer Science ................ 27
2.4 In Search of a Foundational Framework ..................... 34
2.5 Procedural Equivalence .................................... 41
2.5.1 Simulation Equivalence ............................. 42
2.5.2 The Exigencies of Simulation ....................... 44
2.5.2.1 Formalizing the Transitional Condition ......... 45
2.5.2.2 Formalizing the Representational Requirement ... 47
2.5.2.3 Implementing Recursion ......................... 48
2.6 Taking Stock ........................................ 51
2.6.1 Moschovakis, Gurevich, and the Level-Relativity
of Algorithms ...................................... 51
2.6.2 Algorithms, Identity, and Mathematical Practice .... 54
Acknowledgement ........................................... 57
Notes ..................................................... 57
References ................................................ 63
3 The Second Incompleteness Theorem: Reflections and
Ruminations ............................................... 67
Albert Visser
3.1 Introduction .............................................. 67
3.1.1 Status of the Technical Results in this Chapter .... 68
3.2 Versions of the Second Incompleteness Theorem ............. 68
3.2.1 A Basic Version of G2 .............................. 69
3.2.2 G2 as a Statement of Interpretability Power ........ 69
3.2.3 Feferman's Theorem ................................. 70
3.2.4 G2 as an Admissible Rule ........................... 70
3.3 Meaning as Conceptual Role ................................ 70
3.3.1 L-Predicates ....................................... 71
3.3.2 On HBL-Predicates .................................. 74
3.3.3 Feferman on L-Predicates ........................... 78
3.3.4 Philosophical Discussion ........................... 79
3.4 Solution of the Meaning Problem ........................... 80
3.5 Abolishing Arbitrariness .................................. 81
3.5.1 Consistency Statements as Unique Solutions of
Equations .......................................... 82
3.5.2 Bounded Interpretations ............................ 83
Notes ..................................................... 85
References ................................................ 86
Appendix A Basic Facts and Definitions ......................... 88
A.1 Theories ............................................. 88
A.2 Translations and Interpretations ..................... 88
A.3 Sequential Theories .................................. 90
A.4 Complexity Measures .................................. 90
4 Iterated Definability, Lawless Sequences, and Brouwer's
Continuum ................................................. 92
Joan Rand Moschovakis
4.1 Introduction .............................................. 92
4.2 Choice Sequences .......................................... 93
4.2.1 Brouwer's Continuum ............................... 93
4.2.2 The Problem of Defining "Definability" ............. 93
4.2.3 "Lawlike" versus "Lawless" Sequences ............... 94
4.3 The Formal Systems RLS( ) and FIRM() .................... 94
4.3.1 The Three-Sorted Language  () .................... 94
4.3.2 Axioms and Rules for Three-Sorted Intuitionistic
Predicate Logic .................................... 95
4.3.3 Axioms for Three-sorted Intuitionistic Number
Theory ............................................. 95
4.3.4 Lawless Sequences, Restricted Quantification,
and Lawlike Comprehension .......................... 96
4.3.5 Axioms for Lawless Sequences ....................... 96
4.3.6 Well-Ordering the Lawlike Sequences ................ 97
4.3.7 Restricted LEM, the Axiom of Closed Data and
Lawlike Countable Choice ........................... 97
4.3.8 Brouwer's Bar Theorem and Troelstra's Generalized
Continuous Choice .................................. 98
4.3.9 Classical and Intuitionistic Analysis as
Subsystems of FIRM() .............................. 99
4.3.10 Consistency of FIRM() ............................. 99
4.4 Construction of the Classical Model and Proof of
Theorem 1 ................................................ 100
4.4.1 Definability Over (A,A) by a Restricted
Formula of () .................................. 100
4.4.2 The Classical Model  ( ) ....................... 100
4.4.3 Outiine of the Proof of Theorem 1 ................. 102
4.5 The Г-Realizability Interpretation ....................... 103
4.5.1 Definitions ....................................... 103
4.5.2 Outline ofthe Proof of Theorem 2 .................. 104
4.6 Epilogue ............................................ 105
Acknowledgement .......................................... 106
Notes .................................................... 106
References ............................................... 106
5 A Semantics for In-Principle Provability ................. 108
T. Achourioti
5.1 Introduction ............................................. 108
5.2 In-Principle Provability and Intensionality .............. 109
5.3 Modelling Epistemic Mathematics; A Theory of
Descriptions ............................................. 111
5.4 Intensional Truth ........................................ 113
5.5 Towards Axioms for In-Principle Provability .............. 115
5.6 Intensional Semantics for 'It is In-Principle Provable
that' .................................................... 117
5.6.1 Dynamical Proofs .................................. 118
5.6.2 Bringing Provability Back into 'In-Principle
Provability' ...................................... 119
5.6.3 В and Theory Τ .................................... 122
5.7 Conclusion ............................................... 123
Notes .................................................... 124
References ............................................... 125
PART II MIND AND MACHINES
6 Collapsing Knowledge and Epistemic Church's Thesis ....... 129
Timothy J. Carlson
6.1 Introduction ............................................. 129
6.2 Knowing Entities and Syntactic Encoding .................. 133
6.3 Hierarchies and Stratification ........................... 134
6.4 Collapsing ............................................... 136
6.5 A Computable Collapsing Relation ......................... 137
6.6 A Machine That Knows EA + ECT ............................ 138
6.7 Remarks .................................................. 146
References ............................................... 147
7 Gödel's Disjunction ...................................... 148
Peter Koellner
7.1 The Disjunction .......................................... 150
7.1.1 Relative Provability and Truth .................... 150
7.1.2 Absolute Provability .............................. 151
7.1.3 Idealized Finite Machines and Idealized Human
Minds ............................................. 153
7.1.4 Summary ........................................... 154
7.2 Notation ................................................. 155
7.3 Arithmetic ............................................... 156
7.4 Incompleteness ........................................... 156
7.5 Epistemic Arithmetic ..................................... 157
7.6 Epistemic Arithmetic vidth Typed Truth ................... 159
7.7 The Disjunction in EAT ................................... 160
7.8 The Classic Argument for the First Disjunct .............. 162
7.9 The First Disjunct in EAT ................................ 163
7.10 Penrose's New Argument ................................... 164
7.11 Type-Free Truth .......................................... 166
7.12 A Failed Attempt ......................................... 167
7.13 The System DTK ........................................... 169
7.14 Basic Results in DTK ..................................... 170
7.15 The Disjunction in DTK ................................... 174
7.16 The Disjuncts in DTK ..................................... 176
7.17 Conclusion ............................................... 183
Acknowledgement .......................................... 185
Notes .................................................... 185
References ............................................... 186
8 Idealization, Mechanism, and Knowability ................. 189
Stewart Shapiro
8.1 Lucas and Penrose ........................................ 189
8.2 Gödel .................................................... 190
8.3 Idealization ............................................. 192
8.4 Epistemology ............................................. 197
8.5 Ordinal Analysis ......................................... 200
Notes .................................................... 206
References ............................................... 206
PART III ABSOLUTE UNDECIDABILITY
9 Provability, Mechanism, and the Diagonal Problem ......... 211
Graham Leach-Krouse
9.1 Two Paths to Incompleteness .............................. 212
9.1.1 Post's Path ....................................... 213
9.1.2 Gödel's Path ...................................... 217
9.2 Post's Response to Incompleteness: Absolutely
Undecidable Propositions ................................. 219
9.2.1 From Unsolvability to Undecidability .............. 221
9.2.2 Encounter, 1938 ................................... 223
9.3 Gödel's Response to Incompleteness: Anti-Mechanism ....... 223
9.4 Subgroundedness .......................................... 225
9.5 Studying Absolute Provability ............................ 228
9.5.1 Post's Approach ................................... 228
9.5.2 Gödel's Approach .................................. 229
9.6 Diagonalization Problem .................................. 231
9.7 Conclusions .............................................. 233
Notes .................................................... 234
References ............................................... 240
10 Absolute Provability and Safe Knowledge of Axioms ........ 243
Timothy Williamson
10.1 Absolute Provability ..................................... 243
10.2 Propositions and Normal Mathematical Processes ........... 244
10.3 The Epistemic Status of Axioms ........................... 245
10.4 Gödel on the Human Mind .................................. 248
10.5 Mathematical Certainty ................................... 250
Acknowledgement .......................................... 251
Notes .................................................... 251
References ............................................... 252
11 Epistemic Church's Thesis and Absolute Undecidability .... 254
Marianna Antonutti Marfori and Leon Horsten
11.1 Introduction ............................................. 254
11.2 Absolute Undecidability .................................. 255
11.2.1 Absolute Undecidability in Epistemic Arithmetic ... 255
11.2.2 Other Concepts of Absolute Undecidability ......... 256
11.2.2.1 Fitch's Undecidables ......................... 256
11.2.2.2 Formally Undecidable Arithmetical
Statements ................................... 256
11.2.2.3 Truth-Indeterminate Undecidables ............. 258
1.3 A New Disjunction ........................................ 258
11.3.1 Epistemic Church's Thesis ........................ 259
11.3.2 EGT and Absolute Undecidability .................. 260
11.4 Models for ECT ........................................... 262
11.4.1 Is ECT True? ..................................... 262
11.4.2 Simple Machines .................................. 263
11.4.3 More Realistic Models? ........................... 265
11.5 Conclusion ............................................... 267
Acknowledgements ......................................... 268
Notes .................................................... 268
References ............................................... 269
Index ......................................................... 273
|
