{"entities":{"Q1377910":{"pageid":1388650,"ns":120,"title":"Item:Q1377910","lastrevid":70284285,"modified":"2026-04-13T13:43:56Z","type":"item","id":"Q1377910","labels":{"en":{"language":"en","value":"End extensions of models of linearly bounded arithmetic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1110521"}},"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":"Q1377910$2713271C-4A49-443F-8C8F-38D01F0BED55","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3610f994374fefaba73793f4d7009e5905bd2413","datavalue":{"value":{"text":"End extensions of models of linearly bounded arithmetic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1377910$8008828E-164B-406A-A5BA-4171462585F7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1bea03e452d107c4eeb88ecde23c8c4ceebd3184","datavalue":{"value":"0891.03032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377910$37F6A113-5EDE-46FF-8EA1-951F2CC65582","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ff364cf9a91a70f395c8297fbbfac66eee6ca7fc","datavalue":{"value":"10.1016/S0168-0072(97)00026-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377910$E3C6A13C-D80F-4BBC-8741-DF2CA30D9935","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6246c94f6083cffc3dda1ad223e304fff6f9a9a9","datavalue":{"value":{"entity-type":"item","numeric-id":494637,"id":"Q494637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$1EFD0141-5F15-4FEE-A5F8-4F9EF8BF2E63","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":"Q1377910$17CA4ED0-72B0-4302-9B3C-D259970A179F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f63f05c7298731805d9d06e3b2f6f086002af74","datavalue":{"value":{"time":"+1998-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1377910$240C0B3E-11D0-40F7-80CF-DF082706FC71","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b17fd2a0c53a5efa0360f723df22318132a0ae2e","datavalue":{"value":"The paper is about the end extension problem for bounded second order arithmetic, linear arithmetic LA and \\(\\Sigma^{p}_{0}\\) first-order recursion schema, denoted \\(\\Sigma^{p}_{0}\\)-rec -- both subsystems (the second one possibly not proper) of second order bounded arithmetic BA. \\(\\Sigma^{p}_{0}\\) is the class of bounded polynomial formulas (no second order quantifiers). Axioms of LA consist of the usual ordered semiring axioms plus statements expressing that every set is bounded and has a least upper bound, and the comprehension schema for formulas of the language of bounded Presburger arithmetic (no multiplication). \\(\\Sigma^{p}_{0}\\)-rec is axiomatized by \\(\\Sigma^{p}_{0}\\)-comprehension schema and the recursion schema  \\[ \\forall<a\\exists a\\varphi(x,y)\\rightarrow\\exists Z \\forall w<b\\varphi(Z(w),Z(w+1)), \\]  where \\(\\varphi\\in\\Sigma^{p}_{0}\\) and \\(Z(x)\\) is the value at \\(x\\) of the function coded by \\(Z\\). In section 2 an argument is offered to show that functions computable in polynomial time are provably total in \\(\\Sigma^{p}_{0}\\)-rec. The rest of the paper is devoted to the proof of the main result: every model of LA has an end extension to a model of \\(\\Sigma^{p}_{0}\\). The article concludes with results concerning the relative strength of \\(\\Sigma^{p}_{0}\\)-rec and \\(\\Sigma^{p}_{0}\\)-(rec+choice).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377910$56199BAE-C357-4A55-976A-501A8A3C7D19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4cb4544bfd0397cd4a315ee326499c372f013de5","datavalue":{"value":"03F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377910$D1FBDBB8-6E9D-4F5C-9E69-9B99563D77D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"31eb4b2fe460225d8220386b6d12b964cafd1ca3","datavalue":{"value":"03C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377910$0DC215CB-DAB9-4FAF-929E-1C4773B6E43E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377910$66152B1C-16B2-48F1-B3D0-82225C314907","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b90f71dc1c0df7b87f6970563c95d6c909bb4751","datavalue":{"value":"1110521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377910$B26B1900-51B3-4421-A943-3DB3C60FAC7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cba2903ab2dafc050042cd489ae05396ebe51a19","datavalue":{"value":"bounded arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377910$2BF67E54-6693-47BD-AFBB-A21ED4EBBDB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cddb03d56641bd0c8c383d3410940d6449caeec8","datavalue":{"value":"end extensions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377910$A0F27645-C4B0-4C98-AA45-846D74BC49E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377910$9D22461A-ACED-42C3-9D09-F9D49B639DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4881b59035d29df92f521fb7f6c93516b972baeb","datavalue":{"value":"models of arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377910$CB1FF76D-D980-4024-90A7-91E62D9305E0","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":"Q1377910$89BD1B99-D432-4D95-895C-D9CF8439FF55","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":"Q1377910$A3059178-32BF-4963-8D58-C2F0717C39CB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f59ac051da90312b45e1a154b6bcf5dbaee2e7f1","datavalue":{"value":{"entity-type":"item","numeric-id":1899144,"id":"Q1899144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$A8E0E9AF-C113-4C2E-B4C5-7380BC8442D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"305afa85a8cc04e13d160761258e43b79fcfb022","datavalue":{"value":{"entity-type":"item","numeric-id":1182430,"id":"Q1182430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$3DE6F8DD-B616-491E-B721-7AF2A8099973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dccf19753fdc4aceb4fe2e72e418d7c4420dcc62","datavalue":{"value":{"entity-type":"item","numeric-id":5286672,"id":"Q5286672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$D2F6330B-E415-4759-8026-C4B0561CD53A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fa34ae3e34f6a863a9f8db67c2bfb8bb6401943","datavalue":{"value":{"entity-type":"item","numeric-id":4856172,"id":"Q4856172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$0946662D-1BE7-4442-8D18-06447AF709D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3b936472256c474ab8250b72e7c010873198894","datavalue":{"value":{"entity-type":"item","numeric-id":4206725,"id":"Q4206725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$9204F7CB-8BC5-4FCC-AAF6-650F09E2C036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ce246582a5108381469f1c390aac000359d6944","datavalue":{"value":{"entity-type":"item","numeric-id":3140644,"id":"Q3140644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$4FAFB704-A90E-454F-A695-B04548100297","rank":"normal"},{"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":"Q1377910$781F89A8-7BC0-4634-878A-E73C97F4041E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"132e856a3211ec285e510979fe8754f1d205170f","datavalue":{"value":{"entity-type":"item","numeric-id":3030804,"id":"Q3030804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$E149D22E-2E78-48D2-818B-73D711413411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd225d509accf443965fd398d8d1fca16775d4f6","datavalue":{"value":{"entity-type":"item","numeric-id":3470461,"id":"Q3470461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$B52E5788-255E-45C1-9E3B-27EDE14BB606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0c45ca7e85b7fc779ac39c5df64bc8fcd404d7c","datavalue":{"value":{"entity-type":"item","numeric-id":5687325,"id":"Q5687325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377910$FAB0FCF5-69C3-4DD1-99F4-7390E97A4924","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d97b38e458bfbf91e3dd365dbcf7b5505f079a42","datavalue":{"value":{"entity-type":"item","numeric-id":2976370,"id":"Q2976370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb66037f4c2631e4d7d550cb470ab52f970d0b74","datavalue":{"value":{"amount":"+0.7798929214477539","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":"Q1377910$952EFDEF-4F3D-4893-8FB9-F7D7C7B6B555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1a80d172741676065dedf65024bce02053cd787","datavalue":{"value":{"entity-type":"item","numeric-id":3971940,"id":"Q3971940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adb1fdd4af970f85ec1475553a17c494a45411a2","datavalue":{"value":{"amount":"+0.7679040431976318","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":"Q1377910$9D89A965-48D7-485C-8976-131F0EF66567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4236c1d0af8d7c0f7abc80f4eba37327b39d445f","datavalue":{"value":{"entity-type":"item","numeric-id":5687325,"id":"Q5687325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a84d876612614ae90aa1b7baf5bb7f0a36d0965","datavalue":{"value":{"amount":"+0.7557917833328247","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":"Q1377910$187D4254-DE5C-41EF-840B-73B3DCC8B8EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"End extensions of models of linearly bounded arithmetic","badges":[]}}}}}