JournalspmVol. 66 , No. 1DOI 10.4171/pm/1832

The counting hierarchy in binary notation

  • Gilda Ferreira

    Universidade Lusófona de Humanidades e Tecnologias, Lisboa, Portugal
The counting hierarchy in binary notation cover

A subscription is required to access this article.

Abstract

We present a new recursion-theoretic characterization of FCH, the hierarchy of counting functions, in binary notation. Afterwards we introduce a theory of bounded arithmetic, TCA, that can be seen as a reformulation, in the binary setting, of Jan Johannsen and Chris Pollett's system D02. Using the previous inductive characterization of FCH, we show that a strategy similar to the one applied to D02 can be used in order to characterize FCH as the class of functions provably total in TCA.