Weaker cousins of Ramsey's theorem over a weak base theory (Q2231700)

The paper is devoted to a detailed study of the reverse mathematics status of several Ramsey type principles. As in the earlier work of \textit{K. Yokoyama} [Math. Log. Q. 59, No. 1--2, 108--111 (2013; Zbl 1267.03031)], the base theory is \(\mathsf{RCA}_0^*\), introduced in [\textit{S. G. Simpson} and \textit{R. L. Smith}, Ann. Pure Appl. Logic 31, 289--306 (1986; Zbl 0603.03019)]. \(\mathsf{RCA}_0^*\) is a version of \(\mathsf{RCA}_0\) in which \(\Sigma^0_1\) induction is replaced by \(\Delta^0_0\) induction and the axiom of totality of the exponential function. Ramsey principles declare existence of large solutions of combinatorial problems, where ``large'' in the standard case often simply means infinite. If \((M,{\mathcal X})\) is a nonstandard model, then one can say that \(A\in {\mathcal X}\) is infinite if it is unbounded in \(M\), or if for every \(n\in M\), \(A\) contains a coded subset \(\{a_i: i<n\}\). Over \(\mathsf{RCA}_0\) both definitions are equivalent, but this is not the case for \(\mathsf{RCA}_0^*\), and therefore in this case each combinatorial principle involving infinite solutions has at least two versions, one using the former definition -- called the \textit{ normal} version -- and the latter -- called the \textit{ long} version. The main focus is on the following consequences of the infinite Ramsey theorem for pairs: the chain-antichain principle \(\mathsf{CAC}\), the ascending-descending sequence principle \(\mathsf{ADS}\), and the cohesive Ramsey theorem for Pairs \(\mathsf{CRT}^2_2\). The long version of \(\mathsf{ADS}\) splits into two versions, depending on whether the solution set is a set or a sequence. Among other results, it is shown that the normal versions of the principles listed above are \(\mathsf{RCA}_0^*\) but not \(\Pi^1_1\)-conservative over \(\mathsf{RCA}_0^*\). The long versions either imply \(\mathsf{RCA}_0\) over \(\mathsf{RCA}_0^*\), or are \(\Pi^0_3\)-conservative over \(\mathsf{RCA}_0^*\). A crucial observation is that in models of \(\mathsf{RCA}_0^*+\lnot I\Sigma^0_1\) certain second-order sentences retain some first-order features. This is formalized in a technical definition of \textit{ pseudo-second-order} sentence. It is shown that if \(\chi\) is pseudo-first-order then for every \((M,{\mathcal X})\models \mathsf{RCA}_0^*\), and every proper \(\Sigma^0_1\)-cut \(I\) in \((M,{\mathcal X})\) it holds that \((M,{\mathcal X})\models \chi\) if and only if \((I,\mathrm{Cod}(M/I))\models \chi\), where \(\mathrm{Cod}(M/I)\) is the set of all subsets of \(I\) which are coded in \(M\). As a corollary, it follows that if \(A\in {\mathcal X}\) is such that \((M,A)\models\lnot I\Sigma_1(A)\), then \((M,{\mathcal X})\models \chi\) if and only if \((M,\Delta^0_1\text{-Def}(M,A))\models \chi\). It is shown that the normal versions of \(\mathsf{RT}^n_k\), \textsf{CAC}, \textsf{ADS}, and \(\mathsf{CRT}^2_2\) are pseudo-first-order. It follows that they all are not \(\Pi^1_1\)-conservative over \(\mathsf{RCA}_0^*\). Many other interesting consequences are derived. The last section is devoted to the cohesive set principle \textsf{COH}. Answering a question of Belanger, it is shown that \textsf{COH} is not \(\Pi^1_1\)-conservative over \(\mathsf{RCA}_0^*\). Moreover, in contrast with many other principles, \textsf{COH} can never be computably true in a model of \(\mathsf{RCA}_0^*+\lnot I\Sigma^0_1\).