{"entities":{"Q964451":{"pageid":966299,"ns":120,"title":"Item:Q964451","lastrevid":50955590,"modified":"2026-01-15T22:26:16Z","type":"item","id":"Q964451","labels":{"en":{"language":"en","value":"Provably recursive functions of constructive and relatively constructive theories"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5693388"}},"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":"Q964451$53773B16-29D8-4D4F-960D-428B3AC1D3C3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2e4368b09b4780d1103ef998feea3ab9bae85917","datavalue":{"value":{"text":"Provably recursive functions of constructive and relatively constructive theories","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q964451$B7324334-3E97-47B1-856A-69F603281F09","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"da6e3d603825c94aa434036202f9606301fcf8db","datavalue":{"value":"1197.03050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964451$DD53883B-B1A6-4794-91D2-6D9163AAD19D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c3d9bcc49ce8479a4f74748257e9fdb44ab539c","datavalue":{"value":{"entity-type":"item","numeric-id":535157,"id":"Q535157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$C0E796DC-B984-48AD-B587-D9B3DE11099B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a0a7cd28a9f85b9c6ad57bd5bb1ae477bfe37846","datavalue":{"value":{"entity-type":"item","numeric-id":114337,"id":"Q114337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$F5438008-471A-4450-A829-CE6FC61B3B88","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35759f2c57e380463f3872b667008da8bd531cd4","datavalue":{"value":{"time":"+2010-04-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q964451$A4B14BCB-2A87-467C-8F81-AE9559A67667","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ce7f4abb9010bc3cfb9c71b2b5984a5599568d8","datavalue":{"value":"The property that an intuitionistic theory \\(T^i\\) has the same provably recursive functions as its classical closure \\(T^c\\) is studied for two groups of theories.   The first group includes subsystems of Heyting Arithmetic HA based on induction on formulas in the classes \\(E_n\\) and \\(U_n\\) corresponding to the classes \\(\\Sigma_n\\) and \\(\\Pi_n\\) of the classical arithmetical hierarchy. The classes \\(E_n\\) and \\(U_n\\) are defined inductively: 1) \\(E_0=U_0\\) is the set of quantifier-free formulas; 2a) \\(U_n\\subseteq E_{n+1}\\); 2b) if \\(A\\in E_{n+1}\\), then \\(\\exists x\\,A\\in E_{n+1}\\); 2c) if \\(A\\) and \\(B\\) are in \\(E_{n+1}\\), then \\(A\\land B\\) and \\(A\\lor B\\) are in \\(E_{n+1}\\); 2d) if \\(A\\in E_{n+1}\\) and \\(B\\in U_{n+1}\\), then \\(B\\to A\\in E_{n+1}\\); 3) the definition of the class \\(U_{n+1}\\) is obtained by interchanging in 2a)--2d) ``\\(U\\)'' and ``\\(E\\)'' and replacing \\(\\exists\\) by \\(\\forall\\). The theories \\(IU_n^i\\) and \\(IE_n^i\\) are fragments of HA with the induction scheme restricted to \\(U_n\\) and \\(E_n\\) formulas, respectively; \\(IU_n^c\\) and \\(IE_n^c\\) are their classical versions. In fact, \\(IU_n^c\\) is \\(I\\Pi_n\\) and \\(IE_n^c\\) is \\(I\\Sigma_n\\). It is proved that for each \\(n\\geq 0\\) the theories \\(I\\Sigma_n\\) and \\(IE_n^i\\) have the same \\(\\Pi_2\\)-consequences; therefore these theories have the same provably recursive functions. A method described by \\textit{D. Leivant} [``Syntactic translations and provably recursive functions'', J. Symb. Log. 50, 682--688 (1985; Zbl 0593.03038)] and based on the negative translation combined with a variant of Friedman's translation is used. The same method can be applied to show that \\(IU_n^i\\) and \\(IU_n^c\\) have the same \\(\\Pi_2\\)-consequences. A similar result is obtained for the relatively constructive theories \\(IE_n^{i+\\text{PEM}_k}\\), where \\(\\text{PEM}_k\\) is the principle of excluded middle for all formulas with at most \\(k\\) nested quantifiers.   The second group of theories consists of the intuitionistic theories of bounded arithmetic \\(IS_2^n\\) introduced by \\textit{V. Harnik} [``Provably total functions of intuitionistic bounded arithmetic'', J. Symb. Log. 57, 466--477 (1992; Zbl 0778.03019)]. In fact, \\(IS_2^n\\) are intuitionistic versions of Buss's theories \\(S_2^n\\). Using a general forcing method for establishing \\(\\Pi_2\\)-conservativity for classical theories over their intuitionistic versions proposed by \\textit{J. Avigad} [``Interpreting classical theories in constructive ones'', J. Symb. Log. 65, 1785--1812 (2000; Zbl 0981.03061)], the author proves that if \\(A\\) is a positive \\(\\Sigma_n^b\\)-formula and \\(S_2^n\\vdash\\forall x\\,\\exists y\\,A\\) then \\(S_2^n\\vdash\\forall x\\,\\exists y\\,A\\). This result is obtained as a corollary of the similar result for the theories \\(CPV_n\\) and \\(IPV_n\\) also considered by Harnik.","type":"string"},"datatype":"string"},"type":"statement","id":"Q964451$F0E2E20C-7893-40C8-978C-B6DB25ECD8F8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b1f73afd33192153e94113807fdc62b87cbaa1ee","datavalue":{"value":{"entity-type":"item","numeric-id":234728,"id":"Q234728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$95C2BA3D-434C-4DF7-8DB9-97B68A7FEB30","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964451$F0681CEC-3FBA-4716-AEAD-A4FB57A9F783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8612eb3fa5372f4e40168b827ed17a01cee8d8f6","datavalue":{"value":"03F50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964451$A564ECE8-AC37-41F8-8FE1-03ED27C33A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3068729a394ad5bf58a1a3e5b5d24254d962e1a7","datavalue":{"value":"03F55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964451$73305DA3-FC41-4D84-820E-429A35E2D50B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d8e94eb29185936e7bea99c169348f201f445340","datavalue":{"value":"5693388","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964451$56592C15-BE59-4F62-BC69-4A94ABA1D750","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84331a07bac944f3977ea25921f60f89db46e3cf","datavalue":{"value":"intuitionistic bounded arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q964451$9D2C5053-F1F6-46B4-AB7B-B52C93DCA8AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b23248042bd506455f51600d00d7ec5443276f9","datavalue":{"value":"forcing","type":"string"},"datatype":"string"},"type":"statement","id":"Q964451$4E8CFFDC-B0F5-45A0-9772-4D84A7C45265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a88312ee7af70bd186761c2cc392b1873486539","datavalue":{"value":"Friedman's translation","type":"string"},"datatype":"string"},"type":"statement","id":"Q964451$F0CA4E1E-63FA-470A-AF4D-E873DF351124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97c6b970990dab40d69357bafd674174e833bc7d","datavalue":{"value":"Heyting arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q964451$861740C3-4700-44A3-8352-CD67F3A27673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf7a16970906ea298ae5fc08e919cf7a255a92aa","datavalue":{"value":"negative translation","type":"string"},"datatype":"string"},"type":"statement","id":"Q964451$A7C54FE8-A5C2-47F6-9C80-01238F8E8AD0","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":"Q964451$88E1F4CD-07FB-4F5B-A303-1644A7B87918","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"342cdf533a696659324ac0ec98da56a2e07fa670","datavalue":{"value":"https://doi.org/10.1007/s00153-009-0172-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q964451$05DC4153-5437-46C2-91CE-E6E166778227","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a43acac09b6c4963dbce36b5d46d684d6884662","datavalue":{"value":"W2091271932","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964451$AB142B27-9707-4486-8CA9-398A52F98EC9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb13f0e26bedc43a55f423a26969b5bdef66af80","datavalue":{"value":{"entity-type":"item","numeric-id":2710607,"id":"Q2710607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$1025368C-D5B2-4448-9F61-363A0D8339FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ca3374f38546cd0b5f3c54b80aae548e59ad030","datavalue":{"value":{"entity-type":"item","numeric-id":4678943,"id":"Q4678943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$17FBB072-A5A2-4F3A-B3D4-D910F9B45A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80ccd5e47c36eb1694ba8279960f4a7853e4783b","datavalue":{"value":{"entity-type":"item","numeric-id":4458699,"id":"Q4458699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$7874485D-3685-4C0D-B1D2-913ABB7C3A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"861675e070d01c6709765fae78f1b2b9e9a93b52","datavalue":{"value":{"entity-type":"item","numeric-id":4527922,"id":"Q4527922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$4F35231F-92D3-4E43-9122-5EEB8F6F7DAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a628cb64400cb3daffe7c8b3b6a4710e9daa6946","datavalue":{"value":{"entity-type":"item","numeric-id":3800030,"id":"Q3800030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$60E90F05-871C-4FB9-A16F-68816F6CE246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7d8b6d3273c9d452cc54c762042193e6ccc7c32","datavalue":{"value":{"entity-type":"item","numeric-id":3138830,"id":"Q3138830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$F3E4607B-E7EF-4F11-95F4-848636D2B520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a20b645023a8d04cad0a14618e2426e86442be9","datavalue":{"value":{"entity-type":"item","numeric-id":4704759,"id":"Q4704759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$301A9783-0507-452D-8012-69228548945D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92eb5e0d6bdd856710fcc42356898918428a387c","datavalue":{"value":{"entity-type":"item","numeric-id":685962,"id":"Q685962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$C2E10CE8-86DF-4BDF-AD3A-5711468FADD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec0f8183cbda123ce43acce41bfdebc0fdb8836d","datavalue":{"value":{"entity-type":"item","numeric-id":4032632,"id":"Q4032632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$6DA989DA-0F25-4F02-8578-47961BA1C819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4622804a4a5864d5bd07b0d1d16a6f64d614c609","datavalue":{"value":{"entity-type":"item","numeric-id":3722497,"id":"Q3722497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$BA84921B-2A87-483B-A362-E4F5C07D758F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f23806c904ca7df4a1c521b2a2b49d3663fc016","datavalue":{"value":{"entity-type":"item","numeric-id":4419272,"id":"Q4419272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$5239475D-E939-4786-B07D-7A7905ADDE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5acededece661d0888a84c39d950ecee00a68c","datavalue":{"value":{"entity-type":"item","numeric-id":4812318,"id":"Q4812318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$C2F1D39F-7846-4B40-8400-DC17970CE87F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da9050e0e689fa74d61905eaacaedcbb02e9d6c","datavalue":{"value":{"entity-type":"item","numeric-id":3520239,"id":"Q3520239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$162B9F49-357D-4A93-9E9D-28C27C1C16D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17618ddb1fd34bf255fc52b39503d1e91d300018","datavalue":{"value":{"entity-type":"item","numeric-id":5654035,"id":"Q5654035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$640851EA-3CD5-483D-AABC-75419017CD74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25fc0f83d5ec3109942a6da644b57709f31b1dc6","datavalue":{"value":{"entity-type":"item","numeric-id":1188522,"id":"Q1188522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$A2C23F37-37D9-4D43-8982-A5AEA9F7F8AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"556c63d3d5fbb69adda2aaeb321f31370f38a3b9","datavalue":{"value":{"entity-type":"item","numeric-id":4716271,"id":"Q4716271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$977BC08F-C3A1-4EDE-A02F-FE91C5A557A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7f2ccab9193bb053da1a9b2571d3b5f979d9014","datavalue":{"value":{"entity-type":"item","numeric-id":1920237,"id":"Q1920237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964451$898C8651-197A-4572-B604-54A35938BEF2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ff3ce37d306e63b924a66f7acb707fb58559e7c","datavalue":{"value":"10.1007/S00153-009-0172-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964451$4086993D-B967-4825-80B0-8D5B927C7CE4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e5b370b531941c076ac9ce6950a132f453014dc","datavalue":{"value":{"entity-type":"item","numeric-id":3722497,"id":"Q3722497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc033adf25c99357b742c014dc73bb8b1fd6474d","datavalue":{"value":{"amount":"+0.7943548560142517","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":"Q964451$93E8CEB3-7A76-4DB1-94EB-EE9B36475DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fed2653cb0003aa59f2b74f8d96d7d06fc08296","datavalue":{"value":{"entity-type":"item","numeric-id":1920237,"id":"Q1920237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82c257e6fd43bf47f86ccdbca159123bd045c20b","datavalue":{"value":{"amount":"+0.7884852290153503","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":"Q964451$E986607D-0F1C-4329-BBD7-25A915186DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cdef7b785745d544e7a903a143eaa101e1bcd61","datavalue":{"value":{"entity-type":"item","numeric-id":3800030,"id":"Q3800030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22dd6ee1693787efb38be5940c350d54a6dcba74","datavalue":{"value":{"amount":"+0.7827368974685669","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":"Q964451$00A41EC0-7E33-4889-AD18-D03B0D54A727","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":"1703bbf56ccdede22bacac1225493c760e302b33","datavalue":{"value":{"amount":"+0.7826682925224304","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":"Q964451$570C7364-7DFE-47E7-B6A4-F8C743D68959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bccb27d047c72219b5e53b79a1b9773d81b035f6","datavalue":{"value":{"entity-type":"item","numeric-id":685962,"id":"Q685962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"433bbf8a1169694ae818d21d79a8ca8523f88dd7","datavalue":{"value":{"amount":"+0.7793569564819336","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":"Q964451$9BB326B6-70A3-4538-83BA-A07E4294EFCE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:964451","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:964451"}}}}}