2020/06/05 by Lu Liu, Liu, Lu
Mathematics · #68Q30 #Advanced Topology and Set Theory #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO) #Mathematical Dynamics and Fractals #math.LO #msc:68Q30
paper · pdf · doi:10.48550/arxiv.2006.03228
25pages
arxiv created 2020/06/05 · openalex publication_date 2020/06/05 · arxiv updated 2020/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two combinatorial notions P0 and P1, can we encode P0 via P1. In this talk we address the question where P0 is 3-coloring of integers and P1 is product of finitely many 2-colorings of integers. We firstly reduce the question to a lemma which asserts that certain Π01 class of colorings admit two members violating a particular combinatorial constraint. Then we took a digression to see how complex does the class has to be so as to maintain the cross constraint. We weaken the two members in the lemma in certain way to address an open question of Cholak, Dzhafarov, Hirschfeldt and Patey, concerning a sort of Weihrauch degree of stable Ramsey's theorem for pairs. It turns out the resulted strengthen of the lemma is a basis theorem for Π01 class with additional constraint. We look at several such variants of basis theorem, among them some are unknown. We end up by introducing some results and questions concerning product of infinitely many colorings.