2018.07.06. 小俣 安彦
弱ParisHarrington原理とDicksonの補題

Date/Time: July 6, 2018 (Friday) / 16:00  17:00

Speaker: 小俣 安彦 氏 (東北大学大学院 理学研究科)

Venue: Rm 1201, Science Complex A, Tohoku Univ.

Abstract: Abstract: The weak ParisHarrington principle is a weak version of the ParisHarrington principle, which was originally used as a convenient intermediate version in showing lower bounds for the ParisHarrington principle for pairs [1]. We compare it with Dickson’s lemma, which is a combinatorial theorem originally used in algebra, in particular for showing Hilbert’s basis theorem [2]. We give a construction which shows the direct, level by level, equivalence between the weak ParisHarrington principle for pairs and the Friedmanstyle 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 ParisHarringtonRamsey numbers.
 Bounds for weak Ramsey numbers in higher dimensions.
 A phase transition for the weak ParisHarrington principle which is different from that for the ParisHarrington principle [3].
 Level by level equivalence of Dickson’s lemma and a relativized version of the weak ParisHarrington principle.
All of these are established in RCA_0^*. This is a joint work with Florian Pelupessy.