{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T07:20:17Z","timestamp":1774596017683,"version":"3.50.1"},"reference-count":3,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":11607,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1982,6]]},"abstract":"<jats:p>The category of enumerations over <jats:italic><jats:bold>P<\/jats:bold><\/jats:italic><jats:sub>1<\/jats:sub> is investigated. <jats:italic>Objects<\/jats:italic> are the enumerations of the set of partial recursive functions in one variable \u03c6: <jats:italic><jats:bold>N<\/jats:bold><\/jats:italic> \u2192 <jats:italic><jats:bold>P<\/jats:bold><\/jats:italic><jats:sub>1<\/jats:sub> where \u03c6 is a total effective function from the natural numbers <jats:italic><jats:bold>N<\/jats:bold><\/jats:italic> onto <jats:italic><jats:bold>P<\/jats:bold><\/jats:italic><jats:sub>1<\/jats:sub>.<\/jats:p><jats:p>To each <jats:italic>a<\/jats:italic> \u2208 <jats:italic><jats:bold>P<\/jats:bold><\/jats:italic><jats:sub>1<\/jats:sub> we call \u03c6<jats:sup>\u22121<\/jats:sup>(<jats:italic>a<\/jats:italic>) the set of all indices for <jats:italic>a<\/jats:italic>, the <jats:italic>fibre<\/jats:italic> over <jats:italic>a<\/jats:italic>.<\/jats:p><jats:p><jats:italic>Morphisms<\/jats:italic> from one enumeration \u03c6 to another one \u03c8 are (partial) recursive functions <jats:italic>f<\/jats:italic>, for which \u03c6(<jats:italic>n<\/jats:italic>) = \u03c8(<jats:italic>f<\/jats:italic>(<jats:italic>n<\/jats:italic>)) holds for all <jats:italic>n<\/jats:italic> where <jats:italic>f<\/jats:italic> is denned, i.e. <jats:italic>f<\/jats:italic> is fibrepreserving. They are also called <jats:italic>translators<\/jats:italic> if <jats:italic>f<\/jats:italic> is total. The existence of a translator induces a partial ordering on the enumerations:<\/jats:p><jats:p>Let \u03c6 \u2264 \u03c8, iff there exists a translator <jats:italic>f<\/jats:italic> with \u03c6 = \u03c8\u00b7<jats:italic>f<\/jats:italic>; \u03c6 \u2261 \u03c8 iff \u03c6 \u2264 \u03c8 and \u03c8 \u2264 \u03c6. Two enumerations are called incomparable iff \u03c6 \u2270,\u03c8 and \u03c8 \u2270 \u03c6.<\/jats:p><jats:p>Given a recursively enumerable family of enumerations {\u03c6<jats:sup><jats:italic>i<\/jats:italic><\/jats:sup>}<jats:sub><jats:italic>i<\/jats:italic>\u2208\u03c9<\/jats:sub> then their <jats:italic>direct sum<\/jats:italic><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200044236_inline01\"\/> = \u03c0 is defined by a bijective recursive pairing function <jats:italic>g<\/jats:italic>(<jats:italic>i, n<\/jats:italic>) (e.g. <jats:italic>g<\/jats:italic>(<jats:italic>i, n<\/jats:italic>) = (<jats:italic>i + n<\/jats:italic>)(<jats:italic>i + n<\/jats:italic> + 1)\/2 + <jats:italic>i<\/jats:italic>) summing up the \u03c6<jats:sup><jats:italic>i<\/jats:italic><\/jats:sup> by \u03c6<jats:sup><jats:italic>i<\/jats:italic><\/jats:sup>(<jats:italic>n<\/jats:italic>) = <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200044236_inline02\"\/> = \u03c0<jats:sub><jats:italic>g<\/jats:italic>(<jats:italic>i, n<\/jats:italic>)<\/jats:sub> into \u03c0. We also say \u03c0 <jats:italic>decomposes<\/jats:italic> into <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200044236_inline01\"\/>.<\/jats:p><jats:p>Direct sums satisfy the universal property of sums in categories.<\/jats:p><jats:p>We want to operate decompositiontheory on special kinds of objects in our category, the G\u00f6delnumberings and the Friedbergnumberings.<\/jats:p><jats:p>A <jats:italic>G\u00f6delnumbering<\/jats:italic> \u03c6 is defined by (a) enumeration theorem (i.e. \u03c6 is object of our category) and (b) <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200044236_inline03\"\/>-theorem, which means that each <jats:italic>m + n<\/jats:italic>-place p.r. function can be effectively replaced by an enumeration of <jats:italic>n<\/jats:italic>-place p.r. functions given by means of the total <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200044236_inline03\"\/>-function (see Rogers [3]).<\/jats:p>","DOI":"10.2307\/2273141","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:59:42Z","timestamp":1146952782000},"page":"267-274","source":"Crossref","is-referenced-by-count":7,"title":["On decomposition of G\u00f6delnumberings into Friedbergnumberings"],"prefix":"10.1017","volume":"47","author":[{"given":"Britta","family":"Schinzel","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200044236_ref002","article-title":"G\u00f6delnumberings versus Friedbergnumberings","volume":"15","author":"Pour-El","year":"1964","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S0022481200044236_ref003","volume":"23","author":"Rogers","year":"1958","journal-title":"G\u00f6delnumberings of partial recursive functions"},{"key":"S0022481200044236_ref001","first-page":"309","volume":"23","author":"Friedberg","year":"1958","journal-title":"Three theorems on recursive enumeration"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200044236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T21:16:08Z","timestamp":1558732568000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200044236\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,6]]},"references-count":3,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1982,6]]}},"alternative-id":["S0022481200044236"],"URL":"https:\/\/doi.org\/10.2307\/2273141","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,6]]}}}