{"entities":{"Q365661":{"pageid":367428,"ns":120,"title":"Item:Q365661","lastrevid":61278375,"modified":"2026-04-10T22:19:49Z","type":"item","id":"Q365661","labels":{"en":{"language":"en","value":"A note on definability in fragments of arithmetic with free unary predicates"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6206975"}},"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":"Q365661$28ABD167-7E5E-47A1-9439-9C859FFF0618","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6eab4706327abc83a01a3dc64878bccbecaa50b7","datavalue":{"value":{"text":"A note on definability in fragments of arithmetic with free unary predicates","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q365661$432493EA-90F8-45E7-88E3-B31FE0D2B181","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"293374e399c6f8bae7c0d0d070b97fd71d0deed2","datavalue":{"value":"1279.03066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$7814194A-34F6-4B97-9F8D-CCF67F983C3E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f517762c8bf8d062c2939388e57760160d03abdd","datavalue":{"value":{"entity-type":"item","numeric-id":365660,"id":"Q365660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$C279BE95-0736-4341-A9A0-CD70B3121C9A","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":"Q365661$C326DF2D-DD08-4749-905A-20076581D663","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6e8c017497806797f217f1d658e3d224a2498206","datavalue":{"value":{"time":"+2013-09-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q365661$21ED8E1A-4742-460B-8FC7-8A1AD0B5859F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"248024db4cc65ca6a215be24befc4c7b51644fae","datavalue":{"value":"For a signature \\(\\sigma\\), a \\(\\Pi^1_n\\)-\\(\\sigma\\)-formula is a second-order \\(\\sigma\\)-formula of the form \\(\\forall X_1\\exists X_2\\dots\\varphi\\) with \\(n-1\\) alternating quantifiers, where all second-order variables are unary, and \\(\\varphi\\) has no second-order quantifiers. The paper presents several results on \\(\\Pi^1_n\\)-\\(\\sigma\\) definability over the set of natural numbers \\(\\omega\\), where \\(\\sigma\\) is one of \\(\\{+\\}\\), \\(\\{\\times\\}\\), \\(\\{+,\\times\\}\\). \\textit{J. Y. Halpern} [J. Symb. Log. 56, No. 2, 637--642 (1991; Zbl 0738.03017)] proved that the set of \\(\\Pi^1_1\\)-\\(\\{+\\}\\) sentences true in \\((\\omega,+)\\) is \\(\\Pi^1_1\\)-complete. The main result of the paper is a direct proof of Halpern's result with some generalizations. The author shows that there is a \\(\\{+,U\\}\\)-sentence \\(\\Psi\\), such that for any expansion \\(B=(\\omega,+,U^B)\\), \\(B\\models\\Psi\\) iff \\(\\Psi_\\times\\) defines multiplication in \\(B\\), where \\(\\Psi_\\times\\) is a \\(\\{+,U\\}\\)-formula defining multiplication in \\((\\omega, +,\\{n^2:n\\in\\omega\\})\\). This is used to prove that there is an effective translation from \\(\\Pi^1_n\\)-\\(\\{+,\\times\\}\\)-formulas to \\(\\Pi^1_n\\)-\\(\\{+\\}\\)-formulas and this allows him to show that the set of \\(\\Pi^1_n\\)-\\(\\{+\\}\\) sentences true in \\((\\omega, +)\\) is \\(\\Pi^1_n\\)-complete and that each \\(\\Pi^1_n\\)-set is definable by a \\(\\Pi^1_n\\)-\\(\\{+\\}\\)-formula. There are also analogous results concerning \\(\\Pi^1_n\\)-\\(\\{\\times\\}\\) completeness and definability in \\((\\omega, \\times)\\). One of the corollaries is that there are no unary predicates \\(P_1,\\dots, P_n\\) such that \\(+\\) is definable in \\((\\omega, s, P_1,\\dots, P_n)\\), where \\(s\\) is the successor function. The paper includes a list of interesting open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q365661$780FA6E2-6181-4D96-A50D-C421B2EAF1E9","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":"Q365661$CA691B0F-A865-4840-9833-32258A44567D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$D199513C-0807-41E4-9084-297BC4588BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"31eb4b2fe460225d8220386b6d12b964cafd1ca3","datavalue":{"value":"03C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$48631615-62F3-475C-97B0-336CAA046F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c1d2d83da0d870574277144fdd1db9abaae162ec","datavalue":{"value":"03C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$3CA39FB9-3FD1-4539-9FE3-03D5ABBEA8A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$066E2C1F-A350-4BEA-BD39-AF1EAB26BB07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4cb4544bfd0397cd4a315ee326499c372f013de5","datavalue":{"value":"03F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$458FFBDD-FA23-4531-AFC7-A2967A957BF8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f6d2d7c2fe37a775964b50b1e13d8309604bd76","datavalue":{"value":"6206975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$7E1469EE-29EE-474A-A8B3-C93BCBA52D4C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ac3f30d773ef1894fb2eb52711e135b17d0158","datavalue":{"value":"definability","type":"string"},"datatype":"string"},"type":"statement","id":"Q365661$833D6D16-903B-41B2-8702-74C5CE2B2660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78e469cb56ef748b3f9619abee5f10dfa052a7b9","datavalue":{"value":"expressiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q365661$9D1652E2-4FCE-4A64-A1BA-4298AE7C1507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q365661$51643820-BCFC-400F-92E0-06E64236FF1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q365661$DB38460D-4389-406E-A482-524813DFA722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e5e6e64f7f171dc89f3c77310230730ce57088b","datavalue":{"value":"Presburger arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q365661$B84468C1-58CE-4FDF-911A-781B945DA434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1eecaf608f8364efad07406e615bb4f5ba45d6c3","datavalue":{"value":"Skolem arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q365661$ABD42595-C15D-48CF-AF86-FF0E233B1E6B","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":"Q365661$706691B6-31EE-4450-BF64-AC79893107B2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2fe11480a1599c640e834ce0f38266c520400a16","datavalue":{"value":"https://doi.org/10.1007/s00153-013-0328-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q365661$73EDF0E0-5A0D-45E3-8EED-8BB36E1B3142","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ebdbc7354690444ad5b524b821f322cb02ab850","datavalue":{"value":"W2031648800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$7CF34BAA-8F8C-4728-9AE6-13AED79B5CC9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ede61bbf47dfc5f96e9420622c0600314318cdac","datavalue":{"value":{"entity-type":"item","numeric-id":1327387,"id":"Q1327387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$A4C13438-DE92-4A3A-B440-FACBCC1AB64C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64b7a836e71e0ce2b635352f5a5ed06e35f4c8fb","datavalue":{"value":{"entity-type":"item","numeric-id":4781602,"id":"Q4781602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$CE0E4246-AFFD-42E0-BA10-E4AE51442D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a208b293f41828902e2a641b95f780423438f6d1","datavalue":{"value":{"entity-type":"item","numeric-id":4212909,"id":"Q4212909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$646FCC0E-99C2-4A96-A69E-A225BF21E980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73ea1a986b8212f90121d21e0a14bb9807498264","datavalue":{"value":{"entity-type":"item","numeric-id":5791204,"id":"Q5791204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$09C5BAE1-9844-4D8F-B392-CC92089F6E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b866bba96ae151ad3a477a3bb46c2f09c1a0b68","datavalue":{"value":{"entity-type":"item","numeric-id":5596785,"id":"Q5596785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$DEC6C140-7313-43BE-8F73-D7E7B3052AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8a009afd89699667ed724d9f70e3e84d8884a2f","datavalue":{"value":{"entity-type":"item","numeric-id":5181677,"id":"Q5181677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$EC2E75F2-D10A-4282-969A-7F0900D2CF3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db983e8102f84f2e9c46ae125c2043290b8a63d3","datavalue":{"value":{"entity-type":"item","numeric-id":3984438,"id":"Q3984438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$D26B691B-B236-4BCD-AB64-760E3518FE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e51636baa00b00ee9af6bbcde64f417bff981286","datavalue":{"value":{"entity-type":"item","numeric-id":792083,"id":"Q792083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$F7D55CDB-C8D0-472E-93E1-7D8C091777F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e6ee93c6a75b541cd72652bc62d7edbd6011d59","datavalue":{"value":{"entity-type":"item","numeric-id":5941257,"id":"Q5941257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$7BCBD432-4272-4CDC-8516-E85CB436F9AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcd6848b24e9913c5da4423092f863726cd004c0","datavalue":{"value":{"entity-type":"item","numeric-id":3245363,"id":"Q3245363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$EAECE55F-A43C-4548-8BB6-E6E4109D11AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$ED087F8B-9775-48A4-AE89-1E8D5CEDDAE5","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":"Q365661$D052B2A7-270A-4EF2-B2F6-4D3FCB7C1E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22ac26f3797a96fa80c31bb9da67c7e2d4caf1bd","datavalue":{"value":{"entity-type":"item","numeric-id":2863169,"id":"Q2863169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q365661$EE40A6B2-3DB5-4687-B7C4-FB0994B6475D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6a648a6d7424224702adb6869eac6584b0e00ca","datavalue":{"value":"10.1007/S00153-013-0328-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q365661$76C69B5A-DC94-482A-B3E1-F93E5E6CF502","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcde9f6fc954f54c5ab82496136e658e5334f0af","datavalue":{"value":{"entity-type":"item","numeric-id":3984438,"id":"Q3984438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"015345e56b8f79e2c8e83bf3a16e9dc0923b56ea","datavalue":{"value":{"amount":"+0.832449734210968","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":"Q365661$CB8445B6-C222-4463-8560-00B3860F6F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24a577747d5f8516938761057ed1d8fecc69b2ff","datavalue":{"value":{"entity-type":"item","numeric-id":1885035,"id":"Q1885035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89120341a7d139c6764f2217ecf1e2abf807b87c","datavalue":{"value":{"amount":"+0.8310413360595703","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":"Q365661$73287065-D87C-4BB3-B193-AE7B6191F9E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"779081257e8b62c2b584b321d750c49e49ecaf90","datavalue":{"value":{"entity-type":"item","numeric-id":1401169,"id":"Q1401169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c4c41c8809321cf89986d81bb815abfb88f16f7","datavalue":{"value":{"amount":"+0.7535501718521118","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":"Q365661$BB253D7A-6A5E-483B-B1A4-7A8A9EB95EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c9e82815c99d3da47eafea6716622144a536960","datavalue":{"value":{"entity-type":"item","numeric-id":4635632,"id":"Q4635632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"504d83256eb7d79dd87b80f8190d097df1b79089","datavalue":{"value":{"amount":"+0.7493494749069214","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":"Q365661$51711A8E-4EB1-42F0-89F1-EFF4254BCB85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8732e26f8d15ae4cae8412877dd84cfa77075d38","datavalue":{"value":{"entity-type":"item","numeric-id":1406364,"id":"Q1406364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a7df2072e0f0a6f86a98c9f51ef73655b14cd97","datavalue":{"value":{"amount":"+0.7414121031761169","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":"Q365661$C5F12435-149B-4FE8-B17E-10D05A11BD5F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on definability in fragments of arithmetic with free unary predicates","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_definability_in_fragments_of_arithmetic_with_free_unary_predicates"}}}}}