{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T12:11:18Z","timestamp":1761826278853,"version":"build-2065373602"},"reference-count":0,"publisher":"European Mathematical Society - EMS - Publishing House GmbH","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Port. Math."],"published-print":{"date-parts":[[2009,3,31]]},"abstract":"<jats:p>\n                    We present a new recursion-theoretic characterization of\n                    <jats:inline-formula>\n                      <jats:tex-math>\\mathsf{FCH}<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , the\n                    <jats:italic>hierarchy of counting functions<\/jats:italic>\n                    , in binary notation. Afterwards we introduce a theory of\n                    <jats:italic>bounded arithmetic<\/jats:italic>\n                    ,\n                    <jats:inline-formula>\n                      <jats:tex-math>\\mathsf{TCA}<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , that can be seen as a reformulation, in the binary setting, of Jan Johannsen and Chris Pollett's system\n                    <jats:inline-formula>\n                      <jats:tex-math>\\mathsf D^0_2<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . Using the previous inductive characterization of\n                    <jats:inline-formula>\n                      <jats:tex-math>\\mathsf{FCH}<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , we show that a strategy similar to the one applied to\n                    <jats:inline-formula>\n                      <jats:tex-math>\\mathsf{D}^0_2<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    can be used in order to characterize\n                    <jats:inline-formula>\n                      <jats:tex-math>\\mathsf{FCH}<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    as the class of functions provably total in\n                    <jats:inline-formula>\n                      <jats:tex-math>\\mathsf{TCA}<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.4171\/pm\/1832","type":"journal-article","created":{"date-parts":[[2009,12,22]],"date-time":"2009-12-22T19:14:17Z","timestamp":1261509257000},"page":"81-94","source":"Crossref","is-referenced-by-count":0,"title":["The counting hierarchy in binary notation"],"prefix":"10.4171","volume":"66","author":[{"given":"Gilda","family":"Ferreira","sequence":"first","affiliation":[{"name":"Universidade Lus\u00f3fona de Humanidades e Tecnologias, Lisboa, Portugal"}]}],"member":"2673","container-title":["Portugaliae Mathematica"],"original-title":[],"link":[{"URL":"http:\/\/www.ems-ph.org\/fulltext\/10.4171\/PM\/1832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T12:06:54Z","timestamp":1761826014000},"score":1,"resource":{"primary":{"URL":"https:\/\/ems.press\/doi\/10.4171\/pm\/1832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,31]]},"references-count":0,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.4171\/pm\/1832","relation":{},"ISSN":["0032-5155","1662-2758"],"issn-type":[{"type":"print","value":"0032-5155"},{"type":"electronic","value":"1662-2758"}],"subject":[],"published":{"date-parts":[[2009,3,31]]}}}