Source author record

Katarzyna W. Kowalik

Katarzyna W. Kowalik appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

1works
1topics
2close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

1 published item(s)

preprint2021arXiv

How strong is Ramsey's theorem if infinity can be weak?

We study the first-order consequences of Ramsey's Theorem for $k$-colourings of $n$-tuples, for fixed $n, k \ge 2$, over the relatively weak second-order arithmetic theory $\mathrm{RCA}^*_0$. Using the Chong-Mourad coding lemma, we show that in a model of $\mathrm{RCA}^*_0 + \neg \mathrm{I}Σ^0_1$, $\mathrm{RT}^n_k$ is equivalent to its own relativization to any proper $Σ^0_1$-definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe. We give an axiomatization of the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^n_k$ for $n \ge 3$. We show that they form a non-finitely axiomatizable subtheory of PA whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_{\ell+3}$ fragment for $\ell \ge 1$ lies between $\mathrm{I}Σ_\ell \Rightarrow \mathrm{B}Σ_{\ell+1}$ and $\mathrm{B}Σ_{\ell+1}$. We also consider the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^2_k$. We show that they form a subtheory of $\mathrm{I}Σ_2$ whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_4$ fragment is strictly weaker than $\mathrm{B}Σ_2$ but not contained in $\mathrm{I}Σ_1$. Additionally, we consider a principle $Δ^0_2$-$\mathrm{RT}^2_2$, defined like $\mathrm{RT}^2_2$ but with both the $2$-colourings and the solutions allowed to be $Δ^0_2$-sets. We show that the behaviour of $Δ^0_2$-$\mathrm{RT}^2_2$ over $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2$ is similar to that of $\mathrm{RT}^2_2$ over $\mathrm{RCA}^*_0$, and that $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2 + Δ^0_2$-$\mathrm{RT}^2_2$ is $Π_4$- but not $Π_5$-conservative over $\mathrm{B}Σ_2$. However, the statement we use to witness lack of $Π_5$-conservativity is not provable in $\mathrm{RCA}_0 +\mathrm{RT}^2_2$.