Solda, Giovanni (2021) Calibrating the complexity of combinatorics: reverse mathematics and Weihrauch degrees of some principles related to Ramsey’s theorem. PhD thesis, University of Leeds.
Abstract
In this thesis, we study the proof-theoretical and computational strength of some combinatorial principles related to Ramsey's theorem: this will be accomplished chiefly by analyzing these principles from the points of view of reverse mathematics and Weihrauch complexity.
We start by studying a combinatorial principle concerning graphs, introduced by Bill Rival and Ivan Sands as a form of ``inside-outside'' Ramsey's theorem: we will determine its reverse mathematical strength and present the result characterizing its Weihrauch degree. Moreover, we will study a natural restriction of this principle, proving that it is equivalent to Ramsey's theorem.
We will then move to a related result, this time concerning countable partial orders, again introduced by Rival and Sands: we will give a thorough reverse mathematical investigation of the strength of this theorem and of its original proof. Moreover, we will be able to generalize it, and this generalization will itself be presented in the reverse mathematical perspective.
After this, we will focus on two forms of Ramsey's theorem that can be considered asymmetric. First, we will focus on a restriction of Ramsey's theorem to instances whose solutions have a predetermined color, studying it in reverse mathematics and from the point of view of the complexity of the solutions in a computability theoretic sense. Next, we move to a classical result about partition ordinals, which will undergo the same type of analysis.
Finally, we will present some results concerning a recently introduced operator on the Weihrauch degrees, namely the first-order part operator: after presenting an alternative characterization of it, we will embark on the study the result of its applications to jumps of Weak Kőnig's Lemma.
Metadata
Supervisors: | Shafer, Paul and Rathjen, Michael |
---|---|
Keywords: | reverse mathematics; Weihrauch reducibility; infinitary combinatorics; computability theory; Ramsey's theorem |
Awarding institution: | University of Leeds |
Academic Units: | The University of Leeds > Faculty of Maths and Physical Sciences (Leeds) > School of Mathematics (Leeds) > Pure Mathematics (Leeds) |
Identification Number/EthosID: | uk.bl.ethos.839175 |
Depositing User: | Mr Giovanni Solda |
Date Deposited: | 28 Sep 2021 14:38 |
Last Modified: | 11 Nov 2021 10:53 |
Open Archives Initiative ID (OAI ID): | oai:etheses.whiterose.ac.uk:29548 |
Download
Final eThesis - complete (pdf)
Filename: Solda_G_Mathematics_PhD_2021.pdf
Licence:
This work is licensed under a Creative Commons Attribution NonCommercial ShareAlike 4.0 International License
Export
Statistics
You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.