François G. Dorais

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^0_1 + B\Sigma^0_1 + EXP$, the existence of arbitrarily long weakly good tuples is equivalent to $I\Sigma^0_1$ and the existence of arbitrarily long good or strongly good tuples is equivalent to $B\Sigma^0_3$. Consequences for second-order arithmetic include that, over $RCA_0^*$, the existence of arbitrarily long good tuples is equivalent to $B\Sigma^0_3 + \lnot ACA$.