{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:15:51Z","timestamp":1767140151607,"version":"build-2238731810"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T00:00:00Z","timestamp":1663113600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T00:00:00Z","timestamp":1663113600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2018\/31\/B\/HS1\/04018"],"award-info":[{"award-number":["2018\/31\/B\/HS1\/04018"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In the framework of Stewart Shapiro, computations are performed directly on strings of symbols (numerals) whose abstract numerical interpretation is determined by a notation.  Shapiro showed that a total unary function (unary relation) on natural numbers is computable in every injective notation if and only if it is almost constant or almost identity function (finite or co-finite set).  We obtain a syntactic generalization of this theorem, in terms of quantifier-free definability, for functions and relations relatively intrinsically computable on certain types of equivalence structures. We also characterize the class of relations and partial functions of arbitrary finite arities which are computable in every notation (be it injective or not). We consider the same question for notations in which certain equivalence relations are assumed to be computable. Finally, we discuss connections with a theorem by Ash, Knight, Manasse and Slaman which allow us to deduce some (but not all) of our results, based on quantifier elimination.<\/jats:p>","DOI":"10.1007\/s00153-022-00836-4","type":"journal-article","created":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T07:03:00Z","timestamp":1663138980000},"page":"257-288","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalization of Shapiro\u2019s theorem to higher arities and noninjective notations"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3044-525X","authenticated-orcid":false,"given":"Dariusz","family":"Kaloci\u0144ski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Wroc\u0142awski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,14]]},"reference":[{"key":"836_CR1","doi-asserted-by":"crossref","unstructured":"Ash, C., Knight, J., Manasse, M., Slaman, T.: Generic copies of countable structures. Annals of Pure and Applied Logic 42(3), 195\u2013205 (1989). Publisher: North-Holland","DOI":"10.1016\/0168-0072(89)90015-8"},{"key":"836_CR2","first-page":"26","volume-title":"Aspects of Effective Algebra","author":"C Ash","year":"1981","unstructured":"Ash, C., Nerode, A.: Intrinsically recursive relations. In: Crossley, J. (ed.) Aspects of Effective Algebra, pp. 26\u201341. Upside Down A Book Company, Monash University, Australia (1981)"},{"key":"836_CR3","unstructured":"Ash, C.J., Knight, J.: Computable structures and the hyperarithmetical hierarchy. Elsevier (2000)"},{"issue":"5","key":"836_CR4","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/s00153-018-0650-3","volume":"58","author":"N Bazhenov","year":"2019","unstructured":"Bazhenov, N., Fokina, E., Rossegger, D., San Mauro, L.: Degrees of bi-embeddable categoricity of equivalence structures. Archive for Mathematical Logic 58(5), 543\u2013563 (2019). https:\/\/doi.org\/10.1007\/s00153-018-0650-3","journal-title":"Archive for Mathematical Logic"},{"key":"836_CR5","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.33048\/semi.2020.17.076","volume":"17","author":"N Bazhenov","year":"2020","unstructured":"Bazhenov, N., Marchuk, M.: A note on decidable categoricity and index sets. Siberian Elect. Math. Reports 17, 1013\u20131026 (2020). https:\/\/doi.org\/10.33048\/semi.2020.17.076","journal-title":"Siberian Elect. Math. Reports"},{"issue":"1","key":"836_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.2307\/2183530","volume":"74","author":"P Benacerraf","year":"1965","unstructured":"Benacerraf, P.: What Numbers Could Not Be. Philosophical Review 74(1), 47\u201373 (1965)","journal-title":"Philosophical Review"},{"issue":"2","key":"836_CR7","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1093\/philmat\/4.2.184","volume":"4","author":"P Benacerraf","year":"1996","unstructured":"Benacerraf, P.: Recantation or Any Old $$\\omega $$-sequence Would Do After All. Philosophia Mathematica 4(2), 184\u2013189 (1996)","journal-title":"Philosophia Mathematica"},{"issue":"6","key":"836_CR8","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1134\/S0037446621060033","volume":"62","author":"KV Blinov","year":"2021","unstructured":"Blinov, K.V.: Primitively Recursive Categoricity for Unars and Equivalence Structures. Siberian Math. J 62(6), 994\u20131009 (2021). https:\/\/doi.org\/10.1134\/S0037446621060033","journal-title":"Siberian Math. J"},{"key":"836_CR9","doi-asserted-by":"publisher","unstructured":"Calvert, W., Cenzer, D., Harizanov, V., Morozov, A.: Effective categoricity of equivalence structures. Annals of Pure and Applied Logic 141(1), 61\u201378 (2006). https:\/\/doi.org\/10.1016\/j.apal.2005.10.002. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0168007205001557","DOI":"10.1016\/j.apal.2005.10.002"},{"key":"836_CR10","volume-title":"Model theory, Studies in Logic and the Foundations of Mathematics","author":"CC Chang","year":"1973","unstructured":"Chang, C.C., Keisler, H.J.: Model theory, Studies in Logic and the Foundations of Mathematics, vol. 73. North-Holland Press, Amsterdam, New York (1973)"},{"issue":"3","key":"836_CR11","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.shpsa.2010.07.010","volume":"41","author":"BJ Copeland","year":"2010","unstructured":"Copeland, B.J., Proudfoot, D.: Deviant Encodings and Turing\u2019s Analysis of Computability. Studies in History and Philosophy of Science Part A 41(3), 247\u2013252 (2010)","journal-title":"Studies in History and Philosophy of Science Part A"},{"key":"836_CR12","doi-asserted-by":"publisher","unstructured":"Downey, R., Melnikov, A.G., Ng, K.M.: On $$\\Delta ^0_2$$-categoricity of equivalence relations. Annals of Pure and Applied Logic 166(9), 851\u2013880 (2015). https:\/\/doi.org\/10.1016\/j.apal.2015.04.003. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0168007215000354","DOI":"10.1016\/j.apal.2015.04.003"},{"issue":"02","key":"836_CR13","doi-asserted-by":"publisher","first-page":"1750008","DOI":"10.1142\/S0219061317500088","volume":"17","author":"RG Downey","year":"2017","unstructured":"Downey, R.G., Melnikov, A.G., Ng, K.M.: A Friedberg enumeration of equivalence structures. J. Math. Logic 17(02), 1750008 (2017). https:\/\/doi.org\/10.1142\/S0219061317500088","journal-title":"J. Math. Logic"},{"issue":"1","key":"836_CR14","doi-asserted-by":"publisher","first-page":"28","DOI":"10.2307\/2270580","volume":"30","author":"EM Gold","year":"1965","unstructured":"Gold, E.M.: Limiting Recursion. J. Symbolic Logic 30(1), 28\u201348 (1965)","journal-title":"J. Symbolic Logic"},{"key":"836_CR15","doi-asserted-by":"crossref","unstructured":"Knight, J.F.: Degrees Coded in Jumps of Orderings. The Journal of Symbolic Logic 51(4), 1034\u20131042 (1986). http:\/\/www.jstor.org\/stable\/2273915. Publisher: [Association for Symbolic Logic, Cambridge University Press]","DOI":"10.2307\/2273915"},{"key":"836_CR16","first-page":"176","volume":"38","author":"AA Markov","year":"1951","unstructured":"Markov, A.A.: The theory of algorithms. Trudy Matematicheskogo Instituta imeni V.A. Steklova 38, 176\u2013189 (1951)","journal-title":"Trudy Matematicheskogo Instituta imeni V.A. Steklova"},{"key":"836_CR17","doi-asserted-by":"crossref","unstructured":"Montalb\u00e1n, A.: Computable structure theory: Within the arithmetic. Cambridge University Press (2021)","DOI":"10.1017\/9781108525749"},{"issue":"1","key":"836_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.2307\/2270581","volume":"30","author":"H Putnam","year":"1965","unstructured":"Putnam, H.: Trial and Error Predicates and the Solution to a Problem of Mostowski. J. Symbolic Logic 30(1), 49\u201357 (1965)","journal-title":"J. Symbolic Logic"},{"issue":"3","key":"836_CR19","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s00153-019-00701-x","volume":"59","author":"SB Quinn","year":"2020","unstructured":"Quinn, S.B.: Scott sentences for equivalence structures. Archive for Mathematical Logic 59(3), 453\u2013460 (2020). https:\/\/doi.org\/10.1007\/s00153-019-00701-x","journal-title":"Archive for Mathematical Logic"},{"key":"836_CR20","doi-asserted-by":"crossref","unstructured":"Quinon, P.: A Taxonomy of Deviant Encodings. In: D.N. Florin\u00a0Manea Russell G.\u00a0Miller (ed.) 14th Conference on Computability in Europe, CiE 2018, Lecture Notes in Computer Science, vol. 10936 LNCS, p 338\u2013348. Springer Verlag, Kiel (2018)","DOI":"10.1007\/978-3-319-94418-0_34"},{"issue":"1","key":"836_CR21","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.shpsa.2011.11.002","volume":"43","author":"M Rescorla","year":"2012","unstructured":"Rescorla, M.: Copeland and Proudfoot on Computability. Studies in History and Philosophy of Science Part A 43(1), 199\u2013202 (2012)","journal-title":"Studies in History and Philosophy of Science Part A"},{"key":"836_CR22","volume-title":"Theory of Recursive Functions and Effective Computability. McGraw-Hill series in higher mathematics.","author":"H Rogers Jr","year":"1967","unstructured":"Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill series in higher mathematics. McGraw-Hill Book Company, New York, NY, USA (1967)"},{"issue":"1","key":"836_CR23","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1305\/ndjfl\/1093883561","volume":"23","author":"S Shapiro","year":"1982","unstructured":"Shapiro, S.: Acceptable Notation. Notre Dame Journal of Formal Logic 23(1), 14\u201320 (1982)","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"836_CR24","doi-asserted-by":"publisher","first-page":"644","DOI":"10.2307\/1970028","volume":"69","author":"JR Shoenfield","year":"1959","unstructured":"Shoenfield, J.R.: On degrees of unsolvability. Annal. math. 69, 644\u2013653 (1959)","journal-title":"Annal. math."},{"key":"836_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"RI Soare","year":"1987","unstructured":"Soare, R.I.: Recursively Enumerable Sets and Degrees. Springer-Verlag, New York Inc, New York, NY, USA (1987)"},{"issue":"345\u2013363","key":"836_CR26","first-page":"5","volume":"58","author":"AM Turing","year":"1936","unstructured":"Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. J. of Math 58(345\u2013363), 5 (1936)","journal-title":"J. of Math"},{"issue":"4","key":"836_CR27","first-page":"57","volume":"26","author":"M Wroc\u0142awski","year":"2018","unstructured":"Wroc\u0142awski, M.: Representing Numbers. Filozofia Nauki 26(4), 57\u201373 (2018)","journal-title":"Filozofia Nauki"},{"key":"836_CR28","doi-asserted-by":"crossref","unstructured":"Wroc\u0142awski, M.: Representations of Natural Numbers and Computability of Various Functions. In: F.\u00a0Manea, B.\u00a0Martin, D.\u00a0Paulusma, G.\u00a0Primiero (eds.) 15th Conference on Computability in Europe, CiE 2019, Lecture Notes in Computer Science. Springer Verlag (2019)","DOI":"10.1007\/978-3-030-22996-2_26"},{"key":"836_CR29","unstructured":"Wroc\u0142awski, M.: Representations of Numbers and their Computational Properties. Ph.D. thesis, Institute of Philosophy, University of Warsaw, Poland (2019)"}],"updated-by":[{"DOI":"10.1007\/s00153-022-00855-1","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T00:00:00Z","timestamp":1667952000000}}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-022-00836-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-022-00836-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-022-00836-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T08:04:48Z","timestamp":1674029088000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-022-00836-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,14]]},"references-count":29,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["836"],"URL":"https:\/\/doi.org\/10.1007\/s00153-022-00836-4","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,14]]},"assertion":[{"value":"12 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00153-022-00855-1","URL":"https:\/\/doi.org\/10.1007\/s00153-022-00855-1","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}