{"entities":{"Q2219096":{"pageid":2229839,"ns":120,"title":"Item:Q2219096","lastrevid":82661252,"modified":"2026-05-06T21:26:31Z","type":"item","id":"Q2219096","labels":{"en":{"language":"en","value":"A note on uniform density in weak arithmetical theories"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7297806"}},"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":"Q2219096$BB89FF91-BBC3-43B5-9352-96E35E5507FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"512f2e24372f23ee06fcbd2f1348bdf9f2110a0f","datavalue":{"value":{"text":"A note on uniform density in weak arithmetical theories","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2219096$C2C40B63-E21B-494B-8B96-B1739621BDCD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"242b01dde4d3957d3b791f18174dd3faf9f196ba","datavalue":{"value":"1477.03170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219096$317843D8-4A3C-4AF5-9872-894D47BBECF2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"803b92d7ec44162d7ca873aa947c19afebc6f450","datavalue":{"value":{"entity-type":"item","numeric-id":1945708,"id":"Q1945708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$714B768A-63E5-4A14-B429-A7E00E4759E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cb78a179ab7f7671775d8afe3c2e6cdc5cf26c4","datavalue":{"value":{"entity-type":"item","numeric-id":242615,"id":"Q242615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$383EAF4E-3093-4431-BE51-4B479341AAD1","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":"Q2219096$39D60224-CEC8-4582-8058-3E8726BA294B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a1a70f16fd8e81a4c35439aeec3d3645cd1e55e6","datavalue":{"value":{"time":"+2021-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2219096$D324BE56-7950-4891-9D91-E86124DA7D90","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0bb1894c94d9fad5d8cc98a9d696c572f2405e1f","datavalue":{"value":"\\textit{V. Yu. Shavrukov} and \\textit{A. Visser} [Notre Dame J. Formal Logic 55, No. 4, 569--582 (2014; Zbl 1339.03056)] asked whether the (pre-)lattice \\(L_{\\exists \\Sigma^b_1/S^1_2}\\) of \\(\\exists \\Sigma^b_1\\) sentences over Buss' theory \\(S^1_2\\) is uniformly dense. In other words, the question was whether there exists a computable procedure which, given \\(\\exists \\Sigma^b_1\\) sentences \\(\\varphi\\), \\(\\psi\\) such that \\(\\varphi\\) implies \\(\\psi\\) over \\(S^1_2\\) but not vice versa, outputs a third \\(\\exists \\Sigma^b_1\\) sentence which is strictly intermediate between \\(\\varphi\\) and \\(\\psi\\) in terms of implication over \\(S^1_2\\); the procedure is also required to respect equivalence over \\(S^1_2\\).  The authors obtain a positive answer, which generalizes to any consistent c.e. extension of \\(S^1_2\\). In fact, they show that \\(L_{\\exists \\Sigma^b_1/S^1_2}\\) is effectively inseparable, in the sense that there is a computable procedure which, given indices \\(x,y\\) of disjoint c.e. sets \\(W_x\\), \\(W_y\\) such that \\(W_x\\) contains all the (G\u00f6del numbers of) \\(S^1_2\\)-provable \\(\\exists \\Sigma^b_1\\) sentences and \\(W_y\\) contains all the \\(S^1_2\\)-disprovable ones, finds a number not contained in \\(W_x \\cup W_y\\). It then follows from earlier work of \\textit{U. Andrews} and the second author [``Effective inseparability, lattices, and pre-ordering relations'', Rev. Symb. Log. 14, No. 4, 838--865 (2021, \\url{doi:10.1017/S1755020319000273}] that \\(L_{\\exists \\Sigma^b_1/S^1_2}\\) is uniformly dense and has an additional property called local universality. To prove effective inseparability, the authors use a witness comparison argument, taking advantage of the \\(\\exists \\Sigma^b_1\\)-completeness of \\(S^1_2\\) and the fact that the property of being a computation of a given Turing machine is \\(\\Delta^b_1\\)-definable.  In the second part of the paper, analogous results are proved for the lattice of all arithmetical sentences over \\(iR\\) and \\(iQ\\), the intuitionistic counterparts of Robinson's arithmetic theories \\(R\\) and \\(Q\\). A careful analysis reveals that effective inseparability and its consequences still hold if one restricts the lattice of all sentences to one of Burr's intuitionistic formula complexity classes \\(\\Phi_3\\) or \\(\\Theta_2\\). The arguments are similar in spirit to those for \\(S^1_2\\), but additionally invoke Matiyasevich's Theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219096$264CA6BD-6955-4254-A99D-53AEE91C6D60","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219096$9E772342-B111-4CB3-9F75-AE627A473B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219096$900692F3-FCED-48B1-8D65-4829C4B014D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3068729a394ad5bf58a1a3e5b5d24254d962e1a7","datavalue":{"value":"03F55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219096$16781D29-F98A-411C-88E4-C10363A4AF0E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e2f5ec996829e1b3fb1ac8d631ae5801200e1302","datavalue":{"value":"7297806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219096$46D113F0-61F9-417F-8E5A-699E2AC02441","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f65eee17ac61c4dfca4509cfc3beca590b623dc","datavalue":{"value":"weak arithmetical theories","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219096$2B36F9F8-11DF-424F-A6C5-ED40AF98FAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a78b467e47fcd55079a6bd9bf71aeb670415c787","datavalue":{"value":"intuitionistic Robinson arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219096$75ED201D-B1D1-4818-93D3-E2826D22D622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75b90439e0aebe4e4101e14ba6a7a91331a1c4c2","datavalue":{"value":"effective inseparability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219096$23B023D8-11CC-49BE-A1F8-F3BBE277060C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"861f68b2d69a97d1d89e93b93ebe677b07a1df7e","datavalue":{"value":"uniform density","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219096$0B3213E1-39CF-4E01-A014-FA736BE2FBFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8311db7d3bbfb6cfc4b98e04594749c66c5c1339","datavalue":{"value":"local universality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219096$9B9A07D6-C95A-4BDD-A47E-9BE1BEB623ED","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":"Q2219096$B0060DBA-7917-4E33-AF71-3B9B2CB3E768","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"229ba34e23fff63b96f8d5e8baae8405462777ff","datavalue":{"value":"https://doi.org/10.1007/s00153-020-00741-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q2219096$63E48A16-D344-4C7C-9D21-336A48D23C7A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7753fba9b3cdcc8d73b7229288c5cbf9bf9b09bf","datavalue":{"value":"W3041304905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219096$0501BF16-75CD-44DD-9C91-944244216D59","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"18891fb596aa4b3587aa44463b90df7ca20545ca","datavalue":{"value":{"entity-type":"item","numeric-id":5027663,"id":"Q5027663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$6DF057DF-F979-49DA-A4B1-BBDACE0CE1FC","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":"Q2219096$0AB263F7-ED92-4753-8FC6-9FCFE2D1B5E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4dbb4032689e84f6793498eeb09f51fe34d965e","datavalue":{"value":{"entity-type":"item","numeric-id":4664249,"id":"Q4664249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$D08EB065-8C32-400C-BA71-AF01BFB460E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"035feb3d68e7fcb8cc1f5afc2267fb8cc293e0bf","datavalue":{"value":{"entity-type":"item","numeric-id":3794177,"id":"Q3794177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$89562B4B-2E55-429C-9881-6B3FAD68FBD3","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":"Q2219096$AC13E274-7791-4EBE-8988-C7245544263D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abd129e071aee2a849cee9987cb0ef34f83aa1aa","datavalue":{"value":{"entity-type":"item","numeric-id":5114808,"id":"Q5114808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$420E7E43-2143-42A1-A2C2-0E4FBEBC947F","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":"Q2219096$D9DCC8B7-AB7F-4208-8F8B-7CE27B9EFE66","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":"Q2219096$2F1F9A81-F91F-481D-BF97-5764550AE95E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d6c6e9c94939cd334c10993845a942fe3508935","datavalue":{"value":{"entity-type":"item","numeric-id":1171055,"id":"Q1171055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$B538D7E9-D240-4B45-8841-0A8AABA7C8D2","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":"Q2219096$C4796044-8027-405D-9B1A-24820CE8E3FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60c7bf56b39b8da2a69c9516d134c37f6cff24e7","datavalue":{"value":{"entity-type":"item","numeric-id":2258545,"id":"Q2258545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$03A74A21-ECB8-4A31-83D4-731B9D3571AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c333a78bda8d3d5daf7c3712a569b0871ea168d","datavalue":{"value":{"entity-type":"item","numeric-id":2651342,"id":"Q2651342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$02838B8A-4DCD-4670-BBA0-5674DCC23710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ed1ab1ab982fb306286f67c5d6fe7935ff48096","datavalue":{"value":{"entity-type":"item","numeric-id":5636859,"id":"Q5636859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$2AD5C643-B857-4B67-8FD5-22AC734355ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"967be0e0b49301f7ae3c8806d867a2983a3516e8","datavalue":{"value":{"entity-type":"item","numeric-id":4314671,"id":"Q4314671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$A16877AE-2395-471C-8FE3-CFCE8C02615F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"111a8f97398bf0e05a2f4a2219778fb9a69b9969","datavalue":{"value":{"entity-type":"item","numeric-id":1699730,"id":"Q1699730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219096$B2332585-7248-427B-A33E-B5AE7C8A1A5C","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":"Q2219096$32D9A4F2-7264-4607-ACFD-C8D4EDC0F273","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd40d9cae943aef14e770f14d7195a33da683012","datavalue":{"value":"10.1007/S00153-020-00741-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219096$77AA3538-05DF-42B9-A141-2047CB2F22CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aa49c9cfc1c94ee43b0697f929cee8acaaf6ed8","datavalue":{"value":{"entity-type":"item","numeric-id":2258545,"id":"Q2258545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"946787ac04c67d69ffbcfa0c08fd7cd0c5b05a3f","datavalue":{"value":{"amount":"+0.7932331562042236","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":"Q2219096$734F09D2-8479-4E44-A50B-9C93EDA9279F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49873c795c24c8453a536d38f5e608041975d421","datavalue":{"value":{"entity-type":"item","numeric-id":5027663,"id":"Q5027663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1c1d767fe4ce9cb54efa67a5673730016a55667","datavalue":{"value":{"amount":"+0.7657897472381592","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":"Q2219096$8D56257E-5BA2-4407-BA75-87639A6A35FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64a22da687281d9bd1767357626ef815f1342511","datavalue":{"value":{"entity-type":"item","numeric-id":2655144,"id":"Q2655144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64b2b1acdbd9afec6407bf581375510c95f43a70","datavalue":{"value":{"amount":"+0.7404137849807739","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":"Q2219096$CBA48E9D-5ADA-4208-AD0E-58C567F09E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"647718e05d2328572c2f0ff5741dfc644a5bb461","datavalue":{"value":{"entity-type":"item","numeric-id":4505908,"id":"Q4505908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f5e437b2071ac921fc29ac3d93b51261cbd73fb","datavalue":{"value":{"amount":"+0.7271812558174133","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":"Q2219096$CA5B503E-4EA4-4169-A61F-EBD4E49EDFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4d4ee7f4bda871da19ff0ed7838d57c1585ecc7","datavalue":{"value":{"entity-type":"item","numeric-id":535152,"id":"Q535152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f5e437b2071ac921fc29ac3d93b51261cbd73fb","datavalue":{"value":{"amount":"+0.7271812558174133","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":"Q2219096$7CFE1930-8B04-41A1-AA64-99DB4CD521ED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on uniform density in weak arithmetical theories","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_uniform_density_in_weak_arithmetical_theories"}}}}}