On Arithmetical Numberings in Reverse Mathematics

The paper analyzes the strength of some statements of the theory of numberings from the point of view of reverse mathematics and Weihrauch reducibility. For a countable family S, a numbering is a surjection acting from the set of natural numbers onto S. The following types of numberings have been extensively studied in the literature: Friedberg, positive, and minimal numberings. Fix \(n\ge 2\) . After formalizing the needed notions in the language of second-order arithmetic, we prove that, over \(\textsf{RCA}_0\) , \(\textsf{ACA}_0\) is equivalent to the principle stating the existence of a (not necessarily \(\varSigma _n\) -computable) Friedberg numbering \(\nu \) for any infinite \(\varSigma ^0_n\) -computable family. Over \(\textsf{RCA}_0+ \textrm{I}\varSigma ^{}_{2}\) , \(\textsf{ACA}_0\) is also equivalent to a similar principle for positive numberings \(\nu \) . On the other hand, \(\textsf{RCA}_0+ \textrm{I}\varSigma ^{}_{2}\) is sufficient to prove the existence of a minimal numbering for any infinite \(\varSigma ^0_n\) -computable family. The reverse mathematics thus underlines a distinction between the considered types of numberings: intuitively, ‘being Friedberg’ and ‘being positive’ are internal properties of a numbering, while ‘being minimal’ is a more global property. The paper also includes a brief study of the Weihrauch reducibility strength for the existence of Friedberg numberings.