{"entities":{"Q929636":{"pageid":931484,"ns":120,"title":"Item:Q929636","lastrevid":65423151,"modified":"2026-04-12T02:30:05Z","type":"item","id":"Q929636","labels":{"en":{"language":"en","value":"Tennenbaum's theorem and unary functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5289529"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q929636$92A5FF53-760F-498F-B3B7-94801FCDC66F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c0595b271ed0a8cfb9d4c2b5bd7e574e3f9fd468","datavalue":{"value":{"text":"Tennenbaum's theorem and unary functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q929636$1311D32A-D1EB-441C-935E-6D3255271C4D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"36af6749fa7eb2c1673699a11cd86e7c76d1ca1e","datavalue":{"value":"1143.03037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$D778F800-4E60-41DC-B4FD-77824613C7BC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"428c09cc40526bcdf00f4b2221cbdc0b1346e22b","datavalue":{"value":"10.1215/00294527-2008-006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$E544F86B-0CE7-4FC1-8159-C0A98F5F2305","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b31353c43b181598a300268e38db5c616714bc74","datavalue":{"value":{"entity-type":"item","numeric-id":929635,"id":"Q929635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q929636$4A697E83-0C62-461C-A01B-C36000C4CC4F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q929636$A0EFE675-C1E1-48BE-9725-DBBEDC414FE7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"356eea10e764deb786aa3952f426bffa667794bd","datavalue":{"value":{"time":"+2008-06-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q929636$5D436087-ED89-4A91-A02D-0B043F55E26B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ede3d3e67f52cbd8f5ab4c8c7659b556ec772763","datavalue":{"value":"The main theorem of the paper gives a general condition under which realizations of tuples of PA-provably total functions in a nonstandard model of PA cannot have simultaneous computable presentations. As a corollary, it is shown that the pairs of functions \\(\\{2x, 2x+1\\}\\), \\(\\{x^2,2x^2\\}\\), and \\(\\{2^x,3^x\\}\\) in a nonstandard model of PA do not have computable presentations. In the opposite direction, it is shown that for each computable injection \\(f\\) there is a nonstandard model whose \\(f\\) has a computable presentation. This is a strengthening of a result of \\textit{P. D'Aquino} from ``Towards the limits of the Tennenbaum phenomenon'' [Notre Dame J. Formal Logic 38, No. 1, 81--92 (1997; Zbl 0889.03052)]. The result is optimal. There are primitive recursive functions whose nonstandard realizations do not admit computable presentations. An example is given in the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q929636$0F8AC02D-BFA6-4993-9224-EB54E6539A1B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a22eb1f642cbb79777784e33676c61b720925aab","datavalue":{"value":"03H15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$272643A1-2F91-4CE9-B802-AA79984D11D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"31eb4b2fe460225d8220386b6d12b964cafd1ca3","datavalue":{"value":"03C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$A76B4C16-EAA7-47E9-B406-859D33392CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$9308B570-CBDA-4663-8F0E-0E83592156DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51c3dc27e13e59ca92a9af5f9c02c332a8b9421a","datavalue":{"value":"03C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$AF7B4E17-1280-435B-ABD4-8BAA48D1DA23","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1ff5b25ed16d05a629ea1553ee731b4f1474d08b","datavalue":{"value":"5289529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$DE0D038E-78F6-42A7-8641-DD76E40247FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11bae5b20bd836c1cfcedbce77a2c9381030e51b","datavalue":{"value":"nonstandard models","type":"string"},"datatype":"string"},"type":"statement","id":"Q929636$1AB345E1-3BBD-423D-9CF1-0870B21B2227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f19cbfd979f077b20d52e4b29476e07fb73906a4","datavalue":{"value":"Tennenbaum's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q929636$1DB5D43A-937E-44D8-9119-4909784B71A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7090cb2b2cefa03cee6b50a67ca057c086ad0f00","datavalue":{"value":"Peano arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q929636$40861EC8-8AD4-41AC-8C75-5D20F8692069","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc2fe705c7d582d4c8ad19b50ec74a3e6e0c8ae1","datavalue":{"value":{"entity-type":"item","numeric-id":384285,"id":"Q384285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q929636$E2707C93-C680-44DB-8848-721A63ADB3CC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q929636$E5B3CFA8-9C57-425E-AD48-422C58E7AEA5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"62d942196598d57f3fa5d3961e01f8314f7a3e42","datavalue":{"value":"https://doi.org/10.1215/00294527-2008-006","type":"string"},"datatype":"url"},"type":"statement","id":"Q929636$1D303929-D97F-4359-8DAE-1F9986F9531B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"72a7b53c8877b4982b82604dc542f89d8c51c334","datavalue":{"value":"W2035465455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q929636$F4378F04-1B60-40D8-9DCE-BED35E753709","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73b371a9e1e3deb2ea76d9e43f164457050b27ac","datavalue":{"value":{"entity-type":"item","numeric-id":4288293,"id":"Q4288293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90634bf52af412e116aebf504ff5f0a9eb8d94c7","datavalue":{"value":{"amount":"+0.8787754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$5EA37E60-F4CA-419D-AE01-6645B69707E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa6695dd1717bb437d7e958f02d77b02b46660db","datavalue":{"value":{"entity-type":"item","numeric-id":795831,"id":"Q795831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4f2c1efa918aaaed1d504553e9e261d57790268","datavalue":{"value":{"amount":"+0.86982226","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$D32FE3AD-26C3-4E17-A68A-4EF84DFAC14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72372c968907fe18ba48619fa4ff73fdd98f0123","datavalue":{"value":{"entity-type":"item","numeric-id":1884913,"id":"Q1884913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8be81dd70756e8ff956ae8198d1ae6aa3b4cc2c7","datavalue":{"value":{"amount":"+0.86885","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$975CE2D1-87E1-46A8-8A21-1E8F7B28D1A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50ff98fd1feabc1c606e6ace1076517b011e0c8e","datavalue":{"value":{"entity-type":"item","numeric-id":3416446,"id":"Q3416446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f979fbf1cb27408fd0a8edbd355a32c736132cc","datavalue":{"value":{"amount":"+0.8684344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$316EA716-95B6-4637-BA6A-637BF8AF6A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d3ec09085c684568faeced324fbdc31473413bb","datavalue":{"value":{"entity-type":"item","numeric-id":5636976,"id":"Q5636976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95ab23ff9ee644de664b8d9a0a6f800e198b7cf4","datavalue":{"value":{"amount":"+0.8646188","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$22D2111F-A8B5-4C68-AAA7-02D5B05A87F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"068acd0d442099bb107062b5fcb7506f8057d817","datavalue":{"value":{"entity-type":"item","numeric-id":1312940,"id":"Q1312940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"688823c6b20c9663c46822a7c2d46f6b0581be78","datavalue":{"value":{"amount":"+0.8604547","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$7B24A16E-AB39-4DB5-B24C-8BAB10CDA8FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"358be25918b943583cc10a79dcc0557d1a4ae744","datavalue":{"value":{"entity-type":"item","numeric-id":3118401,"id":"Q3118401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92f6b384b59d8654d2d2237db847b99cab475ee6","datavalue":{"value":{"amount":"+0.8603977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$B19875E6-B7A1-4507-9F1D-29FF7EA3ABA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a65a786b0ed6756d718af3995aec2f1bb325785b","datavalue":{"value":{"entity-type":"item","numeric-id":3785104,"id":"Q3785104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dade5d67a0a624dcd83d7f4c9f1e603e31c76f9d","datavalue":{"value":{"amount":"+0.86024773","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$CF3E9F32-FBC0-4705-B560-21E113E4B7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89968012b9aabcd263be1e486c5456453104ab3c","datavalue":{"value":{"entity-type":"item","numeric-id":1079493,"id":"Q1079493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3df3a26f087f7736c0593cf32a59fa9440d1d685","datavalue":{"value":{"amount":"+0.85685945","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$B0970D6E-07A7-4D8E-894C-CDCEC97CD572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c29bea006d350c0559b7f4691efd2114866fe8bc","datavalue":{"value":{"entity-type":"item","numeric-id":4386803,"id":"Q4386803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f92131d511fc0adcf0004fa5f2dbe8c5a84be1a","datavalue":{"value":{"amount":"+0.8561801","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q929636$83FDA44B-3240-4E16-AC7B-2F1EF829BFAE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tennenbaum's theorem and unary functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tennenbaum%27s_theorem_and_unary_functions"}}}}}