【逻辑与数学基础讲座】反推数学及其数学基础问题

0.00 undecidability of Hlting Problem

0.01 definition of 0'

0.1 RCA0 and ACA0

0.2 (minimal) models of reverse maths

1 Ramsey's theorem (e.g. any pair formed by elements in H is colored by the same colour)

2 RT_n^n can be reduced to RT_2^n二染色

• 3 proof of Ramsey's theorem (Ramsey used induction.for simplicity, we only go from RT^1_2 to ^2_2)

6 Another proof.可能如4跟0是染是红的，跟1染是蓝的（总有位置没人占，因此对数n，最多问n次，最后每个数都会出现）

7 analysis of two proofs

7.5 left turns mean red

8 ACA0 implies RTnk

9 RT32 implies ACA0

10 停机问题限制到前段（前a个阶段，如2，就看第0个程序（输入是0）和第1个程序（输入是1））(不可能永远变化，因为变成停机了就不会再变化，如a=100最多变100次)

11 如果e要停机一定在b之前停

12 RT22 and WKL0 (Liu, etc.)