To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
We investigate the relationship between various versions of Ramsey’s theorem and bounding schemes in a model $\mathcal {N}$ of a fragment of arithmetic $F$. Our primary objective is to recast and extend the seminal results of Hirst [15] (see Theorem 1) through the modern lens of Weihrauch reducibility. By extracting explicit Weihrauch reductions from classical proofs, we expose the uniform computational content underlying these combinatorial principles, yielding a deeper and more refined understanding of their reverse mathematical strength.
Our results, informally stated in our terminology and established inside $\mathcal {N}$, are as follows: The following are equivalent: $\mathrm {B}\Sigma ^0_2$, the statement that the finite union of finite c.e. sets is finite, and the Infinite Pigeonhole Principle (see Theorem 3). We also discuss the Weihrauch relations between these logically equivalent principles (see Section 4). The Infinite Pigeonhole Principle is Weihrauch reducible to $\mathrm {RT}^2_2$ (see Theorem 4). There is also another principle logically equivalent to $\mathrm {B}\Sigma ^0_2$ which is Weihrauch reducible to $\mathrm {SRT}^2_2$ (see Theorem 5). We show that there is a principle which is equivalent to $\mathrm {B}\Sigma ^0_3$ (see Theorem 6) and Weihrauch reducible to $\mathrm {SRT}^2_{<\infty }$ (Theorem 7). We discuss some equivalences with $\mathrm {B}\Sigma ^0_{n}$ (see Section 6.1) and end with a problem Weihrauch reducible to $\mathrm {RT}^{n+1}_{2}$ (Section 6.2).
Since we work within the model $\mathcal {N}$, many standard definitions must be adjusted. Due to the expository nature of this article, these definitions are introduced throughout the text as needed. Reading the article from start to finish will provide a better understanding of the ideas involved than focusing only on individual theorems.
Recommend this
Email your librarian or administrator to recommend adding this to your organisation's collection.