{"entities":{"Q2795915":{"pageid":2806653,"ns":120,"title":"Item:Q2795915","lastrevid":83417723,"modified":"2026-05-07T07:39:10Z","type":"item","id":"Q2795915","labels":{"en":{"language":"en","value":"Comparing the strength of diagonally nonrecursive functions in the absence of \\(\\Sigma_2^0\\) induction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6559648"}},"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":"Q2795915$6670F947-21D5-4330-B55D-E0F18A84C37D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd8f3e62b8c1cd473cd1dcea0aa3a94f09e766cc","datavalue":{"value":"1373.03016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$901C9A7E-0937-418F-8CE7-4E9F4AB8B7B1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"59e5184151e3553a752c4f6d8ea9021d0d6ae420","datavalue":{"value":{"entity-type":"item","numeric-id":1762360,"id":"Q1762360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$B018563D-E91D-4445-AA84-03E9AC1986DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5122a321cfb515186c4448a4fbfba8604b1bf26","datavalue":{"value":{"entity-type":"item","numeric-id":335001,"id":"Q335001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$F8A88424-B92D-4BA2-AB9D-05E3B85FFF2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e534880849b93db09a5c4bf78c5b4ca1b817f6f","datavalue":{"value":{"entity-type":"item","numeric-id":283111,"id":"Q283111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$F7B3CE8B-72A1-4E93-9D9A-60D5E7CA4A99","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"545d359c3736dad746c8015ce9f1a04448d43829","datavalue":{"value":{"time":"+2016-03-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2795915$7EE60DFF-A665-4270-AE30-3E88C0DB6E4F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f451689ac2666493cdf385dde70326844585151c","datavalue":{"value":"https://arxiv.org/abs/1401.3823","type":"string"},"datatype":"url"},"type":"statement","id":"Q2795915$E0E9E346-90D8-4046-9C03-AE3FDF1B43DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"03461926f3e59bb4fa9590e254171c62bb258415","datavalue":{"value":"https://biblio.ugent.be/publication/7175623","type":"string"},"datatype":"url"},"type":"statement","id":"Q2795915$ED86054C-4C87-48F1-BEFE-30F1C3321EC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"13841f0b96793f178ce9a7dcac9f232220625aee","datavalue":{"value":"03B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$162C6D30-C04D-42DE-9A19-96A152798E75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4cb4544bfd0397cd4a315ee326499c372f013de5","datavalue":{"value":"03F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$2A5F8FCB-B11B-4D80-8FFA-9FD2C55078D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$EA246C59-DA63-455B-9770-39E4A82264C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be3dc4708c9cf550a0fea428870c0b6c80fa756f","datavalue":{"value":"6559648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$B5916E7A-83E6-43FC-AFA3-34B400331955","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e325a72f0e26ab98b1e996e2e86ac8d7891b9a92","datavalue":{"value":"reverse mathematics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795915$109930FC-70F3-45A5-85D5-21C32ED0D6B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b97af56225077a16b53544922a29c89ad968156","datavalue":{"value":"DNR","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795915$26BDA66F-27E8-4452-B209-4850D89C74F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"971c3a87d61cd2b2dd145b9052225bdfe903feef","datavalue":{"value":"WKL","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795915$418ABCB3-964E-407C-901C-B5278CEB8FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfb78bb18f3a146f8ec0fba8087cdcd8dfdba88b","datavalue":{"value":"nonstandard models of arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795915$17045180-B90E-46F7-BA81-573E0B74F5D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a08c4af19f4fa0b9a01e366123579b17628792c","datavalue":{"value":"diagonally nonrecursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795915$5F320F8B-13B9-4912-A0C4-5B12366E01DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"def48283d510794913c58f78056b808e00633a5c","datavalue":{"value":"graph colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795915$AAFB1757-0258-4590-8F46-45BB6D7DDAFF","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":"Q2795915$D603C03A-6AC8-4A98-A688-3F2453641B58","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fdad8f084fb087dbc95be1b17c4dd2cdc14a6af5","datavalue":{"value":"W2964177411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$DDB91DD1-783E-4D27-8411-B9B5A285D414","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bef349325c5b421f1ec3b92a41c04fcde49108ff","datavalue":{"value":"Q59895724","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$7063D3D6-11BF-4C38-B35A-B72D87A81596","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ac8787e7c7893030486590f5fa75efd9f4d57e","datavalue":{"value":{"entity-type":"item","numeric-id":2639061,"id":"Q2639061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$C0953CCD-BB5D-4768-84A8-73E6697B3A42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9288bf9e5d4edf35ccf3b3881a1dda64b056728a","datavalue":{"value":{"entity-type":"item","numeric-id":4384146,"id":"Q4384146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$5D2ADDF4-16DC-46F6-BAEF-D765BC3B0D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83ddea84726f14b715b08d5cf1dcff0d6a0580bc","datavalue":{"value":{"entity-type":"item","numeric-id":4224080,"id":"Q4224080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$D9BCCD45-592F-4571-8161-8EB8EF360026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f42c36d3f2be7827491b5673d0e04c23217f1388","datavalue":{"value":{"entity-type":"item","numeric-id":3190948,"id":"Q3190948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$ABF5323E-4906-41DF-91AD-9F9F97A6F186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736c442fad7b5d4f015ebade6085c65d041e687b","datavalue":{"value":{"entity-type":"item","numeric-id":436224,"id":"Q436224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$3F17385A-C76E-4039-8834-BE8769F7139A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a19a31d4da0acf03baab24fd157492c5b117410","datavalue":{"value":{"entity-type":"item","numeric-id":5937666,"id":"Q5937666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$61D269D3-FAD0-48BF-997D-A5EDC239E946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a055d5458d7b36248a382e7a5e4ddf1f87bbaaf5","datavalue":{"value":{"entity-type":"item","numeric-id":1368581,"id":"Q1368581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$5BC7424C-3810-4C69-A865-7D40581F7E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c36b0c9973244414531d05b0f9be2844a192fe31","datavalue":{"value":{"entity-type":"item","numeric-id":2925331,"id":"Q2925331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$5682DDF2-4511-47FF-ABA8-574211EFE703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f7410f2b3f3aa678cbe756d1c8df423b0162108","datavalue":{"value":{"entity-type":"item","numeric-id":4813658,"id":"Q4813658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$F051A675-9203-43CF-B52F-7F5F78A323FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0430e4a9fe16a78c945c278746cad2959afea463","datavalue":{"value":{"entity-type":"item","numeric-id":3395521,"id":"Q3395521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$C2158D43-219D-48CA-85BD-152ACD2F0727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b77c0ece96a3917e762da5ff7180ef1928c99b0","datavalue":{"value":{"entity-type":"item","numeric-id":4521128,"id":"Q4521128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$376F0B96-FDD5-42B9-9888-A4B836CB3BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04918380c7e36dc72e72591ef80b07a5da57de19","datavalue":{"value":{"entity-type":"item","numeric-id":5659493,"id":"Q5659493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$F5552823-AA2E-4B22-B370-5A15E7502A7E","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"082670c0c63bfe163b3ad8e63619d1a9fcbf571c","datavalue":{"value":"journals/jsyml/DoraisHS15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$BD1863CC-7A01-4F1F-9A95-1EB0C7857496","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cd7b70ee55537f42655c35be3d24b85d5189a515","datavalue":{"value":"10.1017/JSL.2015.43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795915$86E17AC7-5AFB-4DD1-BF35-A40BFF171AB1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8e6c3ab758bcce0d2107c0a7a1366a38cf1667c4","datavalue":{"value":{"text":"Comparing the strength of diagonally nonrecursive functions in the absence of \\(\\Sigma_2^0\\) induction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2795915$0C6C8E23-6754-42BE-B117-A1EC1A5DC37F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cd9ebe56ec423ec5335930a0b1a45ca7ae3b5c0f","datavalue":{"value":{"entity-type":"item","numeric-id":6768298,"id":"Q6768298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795915$978ED252-1BF3-46B9-B389-546B938F84DD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e323bddfc548a6f23c7f453d3371a187705d2993","datavalue":{"value":"It is well-known that provably in the theory \\(\\mathrm{RCA}_0\\), the statement ``for every set \\(X\\) there is a \\(2\\)-bounded diagonally nonrecursive function relative to \\(X\\)'' is equivalent to weak K\u00f6nig's lemma. Moreover, it is known that for any \\(k \\geq 2\\), a DNR function that is \\(k\\)-bounded computes one that is \\(2\\)-bounded. Stephen Simpson had asked whether the latter result is also provable in \\(\\mathrm{RCA}_0\\). The authors of the present paper show that the usual proof goes through in \\(\\mathsf{RCA}_0\\) extended by the \\(\\Sigma^0_2\\) induction axiom. On the other hand, in the absence of \\(\\Sigma^0_2\\) induction, ``all standard \\(k\\) are alike, but each nonstandard \\(k\\) is nonstandard in its own unique way''.NEWLINENEWLINEMore precisely, the paper contains two main results. Firstly, the statement ``there exists \\(k\\) such that for every \\(X\\) there is a \\(k\\)-bounded DNR function relative to \\(X\\)'' does not imply \\(\\mathrm{WKL}\\) over \\(\\mathrm{RCA}_0\\), even in the presence of the \\(\\Sigma^0_2\\) collection axiom. Secondly, the statement ``for every \\(X\\) there is a bounded DNR function relative to \\(X\\)'' is even weaker, and cannot be used to obtain a bound independent of \\(X\\) within \\(\\mathrm{RCA}_0\\) + \\(\\Sigma^0_2\\) collection.NEWLINENEWLINETo prove these theorems, the authors refine a known construction of an (unbounded) DNR function \\(g\\) that does not compute any \\(2\\)-bounded DNR function, in a technically nontrivial way. Taking advantage of the failure of \\(\\Sigma^0_2\\) induction, they are able to implement the construction in a \\(\\Sigma^0_2\\) -definable proper cut, thus making the DNR function \\(g\\) bounded. The main results are obtained by iterating this basic construction.NEWLINENEWLINEThe paper also contains a section on connections between bounded DNR functions and graph colourings.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795915$E385C404-ED4B-4775-90FD-66E805B22B02","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53e493885db976f01affa0226da49a9c508bddf8","datavalue":{"value":{"entity-type":"item","numeric-id":892143,"id":"Q892143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b3483174755f44d310c6c09578065ae420a89ef","datavalue":{"value":{"amount":"+0.7390484809875488","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2795915$CEDF7466-242C-4062-8646-D79024E60BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f53fcc469e0f6f23ac5320095787000044d4296d","datavalue":{"value":{"entity-type":"item","numeric-id":5311768,"id":"Q5311768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f9d1831434d8e368314fba4741d5dbd338d4212","datavalue":{"value":{"amount":"+0.7377681136131287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2795915$3F86CA3B-8536-46B1-B92E-156A22D00FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c128cba860242835997e528fbe02e479bcf58b31","datavalue":{"value":{"entity-type":"item","numeric-id":2892679,"id":"Q2892679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d6a8c95cc222d99e33d5ae6c386e074ca751686","datavalue":{"value":{"amount":"+0.7364564538002014","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2795915$5118B1AC-03CD-47AE-B570-DC8ADAD13E54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"924e5be1763eeb87688ea92060f335587cbacbb9","datavalue":{"value":{"entity-type":"item","numeric-id":2402955,"id":"Q2402955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7c8935a670a75a5b80228a8fc6ccee9a7f16df2","datavalue":{"value":{"amount":"+0.7206071019172668","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2795915$D0096C9A-C6ED-4BED-B53C-5C4B9C22159B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1a70ecf6905bf625ce4e76970bd590e0725c1bf","datavalue":{"value":{"entity-type":"item","numeric-id":3824312,"id":"Q3824312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e3f8608eb9f3a5a5eb4aa948966a80b755938f1","datavalue":{"value":{"amount":"+0.7186412811279297","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2795915$FB9D3EEB-6630-44E7-841C-3CB3AF804B3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Comparing the strength of diagonally nonrecursive functions in the absence of \\(\\Sigma 2^0\\) induction","badges":[]}}}}}