## Slicing the Truth - University of Chicago Math

ods are ad hoc and not generally available. As we will ...... 2 (as well as principles such as ADS and CAC that will be discussed below ...... (They quote Gallier.

1

Contents 1 Setting off: An introduction 1.1 A measure of motivation . 1.2 Computable mathematics 1.3 Reverse mathematics . . . 1.4 An overview . . . . . . . . 1.5 Further reading . . . . . .

. . . . .

3 5 8 12 15 16

notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 18 21 23

3 Finding our path: K¨ onig’s Lemma and computability 0 3.1 Π1 classes, basis theorems, and PA degrees . . . . . . . . . . . . 3.2 Versions of K¨onig’s Lemma . . . . . . . . . . . . . . . . . . . . .

28 29 34

4 Gauging our strength: Reverse 4.1 RCA0 . . . . . . . . . . . . . 4.2 Working in RCA0 . . . . . . . 4.3 ACA0 . . . . . . . . . . . . . 4.4 WKL0 . . . . . . . . . . . . . 4.5 ω-models . . . . . . . . . . . . 4.6 First order axioms . . . . . . 4.7 Further remarks . . . . . . . .

38 41 45 50 52 53 58 61

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

2 Gathering our tools: Basic concepts 2.1 Computability theory . . . . . . . . 2.2 Computability theoretic reductions 2.3 Forcing . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

and . . . . . . . . .

. . . . .

. . .