Date/Time: July 6, 2018 (Friday) / 16:00 - 17:00
Speaker: 小俣 安彦 氏 (東北大学大学院 理学研究科)
Venue: Rm 1201, Science Complex A, Tohoku Univ.
Abstract: Abstract: The weak Paris-Harrington principle is a weak version of the Paris-Harrington principle, which was originally used as a convenient intermediate version in showing lower bounds for the Paris-Harrington principle for pairs . We compare it with Dickson’s lemma, which is a combinatorial theorem originally used in algebra, in particular for showing Hilbert’s basis theorem . We give a construction which shows the direct, level by level, equivalence between the weak Paris-Harrington principle for pairs and the Friedman-style miniaturization of Dickson’s lemma. Our studies result in a cascade of consequences:
- An explicit expression for weak Ramsey numbers for pairs.
- A sharp classification of the complexity classes of weak Paris-Harrington-Ramsey numbers.
- Bounds for weak Ramsey numbers in higher dimensions.
- A phase transition for the weak Paris-Harrington principle which is different from that for the Paris-Harrington principle .
- Level by level equivalence of Dickson’s lemma and a relativized version of the weak Paris-Harrington principle.
All of these are established in RCA_0^*. This is a joint work with Florian Pelupessy.