Sendai Logic - 仙台ロジック Mathematical Institute, Graduate School of Science, Tohoku University

2018.07.06. 小俣 安彦

弱Paris-Harrington原理とDicksonの補題

  • 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 [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 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 [3].
    • 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.