{"entities":{"Q1107528":{"pageid":1118277,"ns":120,"title":"Item:Q1107528","lastrevid":69659412,"modified":"2026-04-13T08:31:33Z","type":"item","id":"Q1107528","labels":{"en":{"language":"en","value":"Bounded arithmetic and truth definition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064986"}},"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":"Q1107528$DD450069-2A63-4ED1-9CC4-D2A197000386","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53f919770e2a71cdeabf632eeb39a77c72584499","datavalue":{"value":{"text":"Bounded arithmetic and truth definition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107528$995F0BA8-13BA-416C-A374-282FEBAEBEB7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df0a618b72a38dd3e68502a70bcc5c1c288ade13","datavalue":{"value":"0653.03038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107528$2D7B2D3F-C2AF-49AA-9622-68D9CDF0116E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"10948c68c7985a9258e1b6bc0c3bd0f9f144df9f","datavalue":{"value":"10.1016/0168-0072(88)90046-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107528$59297B61-8F99-47BE-9817-4AC1A6A9E367","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"057136d60f841fac35f8dec23b81e4925462b1bc","datavalue":{"value":{"entity-type":"item","numeric-id":768306,"id":"Q768306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107528$0531C229-8068-4F07-BE90-81490FE3C4CA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107528$D3E898C7-28A0-4CBE-AC9E-D5A63B91069C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1107528$62F25658-B2AC-48CC-B3D2-5C60F39F3FD5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"39ff14fbedc2ea5be3f6151c6cda146727e0e7fa","datavalue":{"value":"\\(S^1_2\\) is S. Buss' system of bounded arithmetic. \\(S^1_2\\) is the union o f theories \\(S^ i_2\\) which differ by the number of bounded but not sharply bounded quantifiers in formulas allowed in appropriate induction schemes. One of the most important problems is whether the theories \\(S^ i_2\\) form a proper hierarchy. This paper explores possibilities of deciding this question with the aid of the classical machinery of G\u00f6del sentences applied to some special consistency notions for subsystems of \\(S^1_2\\). \\(S^ i_{2,n}\\) is obtained from \\(S^ i_2\\) by adding to the language the function \\(x\\#\\mathstrut^ n_3 y\\) defined as \\(\\exp(| x| \\# | y|_ n)\\) where \\(| y|_ n\\) is \\(\\log_2(y+1)\\) iterated \\(n\\) times. The new functions provide bounds that are needed to define values of formalized terms of \\(S^ i_2\\) whose G\u00f6del numbers are \\(n\\)-small i.e. equal to \\(| u|_ n\\) for some \\(u\\). Consequently a truth formula for \\(S^ i_2\\) is constructed in \\(S\\) \\(i_{2,n}\\) together with a G\u00f6del sentence which is provable in \\(S_{2,n}^{i+1}\\) but not in \\(S^ i_2\\). Variants of the second incompleteness theorem follow. \\(\\overset\\circ U^1_2\\) and \\(\\overset\\circ T^1_2\\) are Buss' systems of second order bounded arithmetic related to PSPACE and EXPTIME respectively. It is shown that \\(\\overset\\circ U^1_2\\) has a truth formula for sharply bounded formulas of \\(S^1_2\\) and \\(\\overset\\circ V^1_2\\) has a truth formula for \\(\\Sigma^ b_1\\)-formulas. It follows that \\(\\overset\\circ U^1_2\\) is not a conservative extension of \\(\\tilde S^0_2\\) (a system for sharply bounded formulas defined in the paper) and \\(\\overset\\circ V^1_2\\) is not a conser vative extension of \\(S^1_2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107528$1154DF9A-CBE7-43C3-B9CB-ABDA3C7C4B02","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107528$4B0712FC-D244-4E9A-8281-901AFB16BC90","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3a868e0b2c1881d7fe8c737aa7b0caec4aa161b","datavalue":{"value":"4064986","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107528$843F2155-21C1-4FD6-AE61-1846ED742D27","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107528$AAC85165-93F1-443F-AE9A-394683653592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"438d03335673be9d3b6cadfceade6aa3809d401c","datavalue":{"value":"truth definitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107528$B9BD8B72-772B-4562-A663-E081754D19A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cba2903ab2dafc050042cd489ae05396ebe51a19","datavalue":{"value":"bounded arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107528$DCA213D0-98EA-4015-A58D-9CF302D3D626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5095003811abfc05976602508ff05a69920c7f11","datavalue":{"value":"G\u00f6del sentences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107528$BA1A2040-B584-4FA2-B6F7-7E7C7718128E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"adaf688f33c0b0859e2845e9d4ff0b1dce96cd93","datavalue":{"value":"Variants of the second incompleteness theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107528$103B0A8F-0AC0-4D07-8A48-A58DE94307B8","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":"Q1107528$09D45844-4E7F-4CBD-8138-071255DECFAA","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":"Q1107528$E31813E0-29ED-4CC0-8DFD-1190623F6CF0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4ea9f44157b2a7fcf650fff14f5c1e7929f539c7","datavalue":{"value":"https://doi.org/10.1016/0168-0072(88)90046-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107528$A5DA3259-BAA7-46F2-86A9-2840B5666751","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cd000ae47ca49b550b99680cc1c3c2b9c9e3dfe1","datavalue":{"value":"W1975433941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107528$99B29AB3-05D6-4F8F-A241-CE2B9576F9FD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d93c0216bb7a2404c766e146541a6f49efebe1b2","datavalue":{"value":{"entity-type":"item","numeric-id":1104318,"id":"Q1104318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107528$D3200A11-7228-4E64-8DAC-FB58AFF6600C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f40276e0be76d48d778707b521dd611651d9d10f","datavalue":{"value":{"entity-type":"item","numeric-id":3816072,"id":"Q3816072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eeb130165bd954d451e86c83e7aaf6ad357b9d8f","datavalue":{"value":{"amount":"+0.868651807308197","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":"Q1107528$697F98EA-0A0E-4F43-B949-4354FD2293CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c4391ef12e51c3ce2230d0e5e03d87c41a53878","datavalue":{"value":{"entity-type":"item","numeric-id":3794177,"id":"Q3794177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f485e8a1d5152de4911508ff8d16b3ec9dafb029","datavalue":{"value":{"amount":"+0.8671826720237732","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":"Q1107528$70871CA1-4FC1-456B-BC63-F5C54F0055A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b48df2ed64dac1e71e24bad9fbb0685bf802012","datavalue":{"value":{"entity-type":"item","numeric-id":4694224,"id":"Q4694224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e677508a6af875ef6ec58fb474d57387aedda01c","datavalue":{"value":{"amount":"+0.861017107963562","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":"Q1107528$5F999271-5E2B-440D-9993-8C7BABCA9DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"103340ea3d703c9c326ce3c339bea17c934afb2a","datavalue":{"value":{"entity-type":"item","numeric-id":4218532,"id":"Q4218532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb342efc334af938f37388fa9100d148b2fbbfda","datavalue":{"value":{"amount":"+0.8482545018196106","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":"Q1107528$C0FFB178-3F68-459D-A452-166AE31CBB78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4c07a104ef3611c77d55ac8140f0d7312a80e6d","datavalue":{"value":{"entity-type":"item","numeric-id":4527927,"id":"Q4527927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f760a918aea33e76d4da6245107874a024332e99","datavalue":{"value":{"amount":"+0.8482535481452942","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":"Q1107528$10A0C113-37D2-460E-AE30-8B4032264586","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded arithmetic and truth definition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_arithmetic_and_truth_definition"}}}}}