The logical strength of minimal bad arrays
Anton Freund, Fedor Nikolaevich Pakhomov, Giovanni Soldà · Proceedings of the American Mathematical Society · 2024
This paper studies logical aspects of the notion of better-quasi-order, which was introduced by C. Nash-Williams [Proc. Cambridge Philos. Soc. 61 (1965), pp. 697–720; Proc. Cambridge Philos. Soc. 64 (1968), pp. 273–290]. A central tool in the theory of better-quasi-orders is the minimal bad array lemma. We show that this lemma is exceptionally strong from the viewpoint of reverse mathematics, a framework from mathematical logic. Specifically, it is equivalent to the set existence principle of Π 2 1 \Pi ^1_2 -comprehension, over the base theory A T R 0 \mathsf {ATR_0} .