×

zbMATH — the first resource for mathematics

Schmerl decompositions in first order arithmetic. (English) Zbl 07114353
Summary: Good \(m\)-tuples, \(m\)-tuples of r.e. sets without Schmerl decompositions, were introduced by Schmerl, who used them to investigate the reverse mathematics of Grundy colorings of graphs. Schmerl considered only standard \(m\), for which our definitions of weakly good, good, and strongly good coincide. The existence of good tuples for nonstandard \(m\) depends on how much induction is available in the model. We show that in models of first-order arithmetic, over a base theory of \(I \Delta_1^0 + B \Sigma_1^0 + EXP\), the existence of arbitrarily long weakly good tuples is equivalent to \(I \Sigma_1^0\) and the existence of arbitrarily long good or strongly good tuples is equivalent to \(B \Sigma_3^0\). Consequences for second-order arithmetic include that, over \(R C A_0^\ast\), the existence of arbitrarily long good tuples is equivalent to \(B \Sigma_3^0 + \neg A C A\).
MSC:
03F50 Metamathematics of constructive systems
03D25 Recursively (computably) enumerable sets and degrees
03C62 Models of arithmetic and set theory
03H15 Nonstandard models of arithmetic
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chong, C. T.; Lempp, S.; Yang, Y., On the role of the collection principle for \(\operatorname{\Sigma}_2^0\) formulas in second-order reverse mathematics, Proc. Amer. Math. Soc., 138, 3, 1093-1100, (2010) · Zbl 1195.03015
[2] Clote, P., Partition relations in arithmetic, (DiPrisco, C. A., Methods in Mathematical Logic. Methods in Mathematical Logic, Lecture Notes in Mathematics, vol. 1130, (1985), Springer), 32-68 · Zbl 0567.03029
[3] F. Dorais, S. Harris, Evasion, prediction, and graph colorings, in preparation.
[4] Z. Evans, Dartmouth College, Ph.D. thesis, in preparation.
[5] H. Friedman, unpublished.
[6] M. Groszek, T. Slaman, On Turing reducibility, preprint.
[7] Harris, S., On-Line Algorithms and Reverse Mathematics, (2017), Dartmouth College, Ph.D. thesis
[8] Paris, J. B.; Kirby, L. A.S.\(, \operatorname{\Sigma}_n\)-collection schemas in arithmetic, (Macintyre, A.; Pacholski, L.; Paris, J., Logic Colloquium ’77, (1978), North-Holland), 199-209
[9] Schmerl, J., Reverse mathematics and Grundy colorings of graphs, Math. Log. Q., 56, 5, 541-548, (2010) · Zbl 1206.03013
[10] Simpson, S., Subsystems of Second Order Arithmetic, Perspectives in Mathematical Logic, (1999), Springer-Verlag: Springer-Verlag Berlin · Zbl 0909.03048
[11] Slaman, T.\(, \operatorname{\Sigma}_n\)-bounding and \(\operatorname{\Delta}_n\)-induction, Proc. Amer. Math. Soc., 132, 8, 2449-2456, (2004) · Zbl 1053.03034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.