Computability, Probability and Logic.pdf

Computability, Probability and Logic


Proefschrift
ter verkrijging van de graad van doctor
aan de Radboud Universiteit Nijmegen
op gezag van de rector magnificus prof. dr. Th.L.M. Engelen,
volgens besluit van het college van decanen
in het openbaar te verdedigen op woensdag 10 juni 2015
om 14:30 uur precies
door
Rutger Kuyper
geboren op 10 februari 1989
te Haarlem

Promotoren:
Prof. dr. M. Gehrke Universit´e Paris Diderot – Paris 7, Frankrijk
Prof. dr. P. Stevenhagen Universiteit Leiden
Copromotor:
Dr. S.A. Terwijn
Manuscriptcommissie:
Prof. dr. B.J.J. Moonen
Prof. dr. R.G. Downey Victoria University of Wellington, Nieuw-Zeeland
Prof. dr. A. Sorbi Universit`a degli Studi di Siena, Itali¨e

=========================================================

Contents
Acknowledgements ......................................vii
Chapter 1. Introduction ................................1
1.1. Computability and logic: the Medvedev and Muchnik lattices page - 2
1.2. Computability and probability: algorithmic randomness and genericity ..............................................5
1.3. Probability and logic: ε-logic .....................6
1.4. Notations and conventions ..........................8
Part I. The Medvedev and Muchnik Lattices............... 11
Chapter 2. The Medvedev and Muchnik Lattices
2.1. Prerequisites...................................... 13
Chapter 3. Natural Factors of the Muchnik Lattice Capturing IPC
3.1. Splitting classes ...................................17
3.2. Low and 1-generic below ∅ 0 are splitting classes ....18
3.3. The theory of a splitting class ....................21
3.4. Further splitting classes ..........................24
Chapter 4. Natural Factors of the Medvedev Lattice Capturing IPC
4.1. Upper implicative semilattice embeddings of P(I) into M 31
4.2. From embeddings of P(ω) to factors capturing IPC 33
4.3. Relativising the construction ........................37
Chapter 5. First-Order Logic in the Medvedev Lattice
5.1. Categorical semantics for IQC........................ 41
5.2. The degrees of ω-mass problems .......................45
5.3. The hyperdoctrine of mass problems................... 47
5.4. Theory of the hyperdoctrine of mass problems......... 51
5.5. Heyting arithmetic in the hyperdoctrine of mass problems ...........................................................55
5.6. Decidable frames .....................................60
Part II. Algorithmic Randomness and Genericity ............69
Chapter 6. Effective Genericity and Differentiability
6.1. Introduction .........................................71
6.2. 1-Genericity .........................................72
6.3. Effective Baire class 1 functions ....................73
6.4. Continuity of Baire class 1 functions ................75
6.5. Functions discontinuous at non-1-generics............ 76
6.6. n-Genericity .........................................79
6.7. Multiply differentiable functions 79
6.8. Complexity-theoretic considerations 80
Chapter 7. Coarse Reducibility and Algorithmic Randomness
7.1. Introduction........................................ 83
7.2. Coarsenings and embeddings of the Turing degrees ....84
7.3. Randomness, K-triviality and robust information coding 89
7.4. Further applications of cone-avoiding compactness ....95
7.5. Minimal pairs in the uniform and non-uniform coarse degrees ...................................................96
7.6. Open questions .......................................98
Part III. ε-Logic .........................................99
Chapter 8. ε-Logic
8.1. ε-Logic 101
8.2. ε-Models 104
Chapter 9. Model Theory of ε-Logic
9.1. A downward L¨owenheim–Skolem theorem 107
9.2. Satisfiability and Lebesgue measure 111
9.3. The L¨owenheim number 115
9.4. Reductions 116
9.5. Compactness 120
Chapter 10. Computational Hardness of Validity in ε-Logic
10.1. Many-one reductions between different ε 129
10.2. Validity is hard 133
Chapter 11. Computational Hardness of Satisfiability in ε-Logic
11.1. Towards an upper bound for ε-satisfiability ........140
11.2. Skolemisation in ε-logic........................... 143
11.3. Satisfiability is Σ11............................. 147
11.4. Decidability of 0-satisfiability ..................151
11.5. Satisfiability is Σ11 -hard .........................154
11.6. Compactness of 0-logic ..............................167
Bibliography ...........................................171
Index ....................................................179
Samenvatting .............................................183
Curriculum Vitae .......................................187