{"entities":{"Q2869914":{"pageid":2880634,"ns":120,"title":"Item:Q2869914","lastrevid":42356989,"modified":"2025-06-12T18:02:26Z","type":"item","id":"Q2869914","labels":{"en":{"language":"en","value":"Low level nondefinability results: domination and recursive enumeration"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6243239"}},"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":"Q2869914$6857A430-EDB8-4F2B-AF42-6AB0633A8A0A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"426a595c04ff1052cc6f20cfd8d24bf997699903","datavalue":{"value":"1325.03047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2869914$80CDB22C-338A-432E-ADCB-67B46CBB800E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e1ad4777d758a68f569c6a49a3227fddd471be9","datavalue":{"value":{"entity-type":"item","numeric-id":386643,"id":"Q386643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$37584C30-9F05-4379-B203-FE925286B7AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31b4e48a13833dd9894b366d4966e95d03977c89","datavalue":{"value":{"entity-type":"item","numeric-id":175054,"id":"Q175054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$3B4EB426-2EED-4897-92DF-A00536E0365F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b62054087ecfdb4f075fe42226b4bf080bcbce33","datavalue":{"value":{"time":"+2014-01-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2869914$2FEA8F39-00DD-448E-9BF8-29F08A95D357","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1f6433aae6cc6f511bfc787a1ee927b5fe077d6c","datavalue":{"value":"https://projecteuclid.org/euclid.jsl/1389032288","type":"string"},"datatype":"url"},"type":"statement","id":"Q2869914$FF6E0178-F27C-46BA-8B52-B1270E333924","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"86e7d9065663fa3ffd8f6c70df93df9f4742e385","datavalue":{"value":"03D28","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2869914$14C355B6-D1F6-40DB-B216-D93007159A5A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5a002790acbb7f62efc8404bc57f59cfe7964a9","datavalue":{"value":"6243239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2869914$65117220-0607-40EF-BECC-49CCEE9CC1E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a72e966b72ee8dad420e672db1cfa6f4582d2051","datavalue":{"value":"nondefinabilty","type":"string"},"datatype":"string"},"type":"statement","id":"Q2869914$538FEBBC-A27D-480F-884D-7869AB973539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91fe4280e2e06a0a064865358db087007d3f302b","datavalue":{"value":"Turing degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2869914$7C133B4E-780E-4F54-970E-E0CC84BCF2FF","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":"Q2869914$AA6EAB98-00D1-4696-90DD-2C02CDDEFAB8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c83b8882249b0c86b349134efa77a2096909030e","datavalue":{"value":"W2050725079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2869914$24A26D34-0DA2-4A09-9C24-4D5B4B98FF18","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a75fb05ff45c85c418587a5c71d455d08c4df02a","datavalue":{"value":{"entity-type":"item","numeric-id":768100,"id":"Q768100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$4869741F-F323-4851-ABA2-03EFBB7D970A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe67cddb1d2e8d4582eb3ba360c56bb29576a54c","datavalue":{"value":{"entity-type":"item","numeric-id":3329452,"id":"Q3329452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$2B636D0C-0061-4632-9D07-8A44A5E2B493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f7f5dc4897411d93abbd3a2d3e5175ae629894b","datavalue":{"value":{"entity-type":"item","numeric-id":3984430,"id":"Q3984430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$04C26610-20C8-4D6B-9F72-463939A996DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90eb7d75e6fca9de70cdc48d7be275c197b0e5d5","datavalue":{"value":{"entity-type":"item","numeric-id":4863240,"id":"Q4863240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$6DBE9F19-E4D6-45D3-A319-A974292BC744","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f4a725bedd32c77a5c003602168428e90131956","datavalue":{"value":{"entity-type":"item","numeric-id":609761,"id":"Q609761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$C1C05D52-5386-4D04-A0C0-0DEBE7120BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfb078a634c706cbd62b7bd9238620283960fed5","datavalue":{"value":{"entity-type":"item","numeric-id":1574741,"id":"Q1574741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$C2E43B16-E512-46D6-A386-C23AC7521339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d3d026dc9a07669becc6d693bbccbd5cac0e957","datavalue":{"value":{"entity-type":"item","numeric-id":3521600,"id":"Q3521600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$F07746E0-5833-40B9-97F1-B4F1997DF927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e28e6243e923b1cbee2c358beb9aacd363a2de0b","datavalue":{"value":{"entity-type":"item","numeric-id":4433097,"id":"Q4433097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$E7DFD9F6-4EBF-45D3-AF28-28A0C86A7B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef4d119b96249a259a6fb4119eb0dc81dccf586d","datavalue":{"value":{"entity-type":"item","numeric-id":1295423,"id":"Q1295423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$0FA7A781-D4C9-4DB8-9D01-794ABBA6A980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b594827bbb97fd6f0e0591659a18d718463bdd7a","datavalue":{"value":{"entity-type":"item","numeric-id":5619821,"id":"Q5619821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$5281741E-55F0-4549-9569-5E6BBCE39709","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85376cf55ea63ecbc91cf000fb26868ee2e13a35","datavalue":{"value":"10.2178/JSL.7803180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2869914$E135FACB-7EFF-4562-94C9-C99380BBC0EB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b46411e482fe7557062ceea980053753d87b3db3","datavalue":{"value":{"entity-type":"item","numeric-id":3521600,"id":"Q3521600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47adb8b5c61491ef99c5dff134ec17de22c529eb","datavalue":{"value":{"amount":"+0.82864887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$98D32A97-13EF-4864-A38E-0FFC5395F1B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68c65a1c68cf7d478c0d76ce9ae7e2df14efa40d","datavalue":{"value":{"entity-type":"item","numeric-id":3491536,"id":"Q3491536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de287250b2d36af4ff3592eb814834569bdd7baa","datavalue":{"value":{"amount":"+0.8222758","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$96921A4A-45D4-482C-ABC6-CF4534D4C8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b60901ad0d984995ab44928195bb34943a26b13b","datavalue":{"value":{"entity-type":"item","numeric-id":4683152,"id":"Q4683152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"234a11d7421f9eaed806b932d0e974fe2ea939b0","datavalue":{"value":{"amount":"+0.81574315","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$68ED6AF8-1D1D-4D13-8A56-88223949CF46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0205c67c3a781994bb46bb84578d880ef801fce3","datavalue":{"value":{"entity-type":"item","numeric-id":3691653,"id":"Q3691653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77d8af0a192ace6872983af5f2b2a267ba3146b1","datavalue":{"value":{"amount":"+0.81478375","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$F106EB56-747D-4117-90DB-20E26DF0113F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c03d92efcc7437b943b3de01277169ebb3c2b0b","datavalue":{"value":{"entity-type":"item","numeric-id":5316382,"id":"Q5316382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"047e3af0fdbafad56d385dd97c0b42b849475ed6","datavalue":{"value":{"amount":"+0.8128795","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$F0DF3154-5524-4450-ABC7-1A5D5D0C16DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a679387854785355084b4390a21b5ebf21e1c86","datavalue":{"value":{"entity-type":"item","numeric-id":2750871,"id":"Q2750871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5e78f26486b219f8d76871c050cbe243ebe184","datavalue":{"value":{"amount":"+0.8063499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$6FFB53E1-E196-4CC3-92B6-15CFC4AF5D99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6476354346c00b5e33a350ae745598ebe01149c","datavalue":{"value":{"entity-type":"item","numeric-id":3216640,"id":"Q3216640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2b74656bcce1fc95f81cc7459a136c1831b3b86","datavalue":{"value":{"amount":"+0.7988528","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$D654741A-570E-4FE0-AF62-780856FB8368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30edd4d88f8d2e7948fccf6b14d9cdb15e4e0576","datavalue":{"value":{"entity-type":"item","numeric-id":3026991,"id":"Q3026991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9651a89b2a45f65f04662682d0b4df29a2b805d","datavalue":{"value":{"amount":"+0.7946507","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$557827CD-9F84-4D87-B789-7BA32EC9C308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11df3696bceb15b1241a073d67629ed74c8ead70","datavalue":{"value":{"entity-type":"item","numeric-id":3128481,"id":"Q3128481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a67867f991bdfe8567f695023133fed0dcbd7e8c","datavalue":{"value":{"amount":"+0.79288805","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$4F42192D-0C16-427E-BD22-42A711697BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"371bc4737b2416d139910a35bb807ba0ee317e12","datavalue":{"value":{"entity-type":"item","numeric-id":2784783,"id":"Q2784783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8630858c186296b05ef10c19ae3866f465dfc7c","datavalue":{"value":{"amount":"+0.791103","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2869914$6BC1819A-C7A8-485F-825B-7CCF87B24691","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e7831b549cfc4b103b22778f55389dff177eaf71","datavalue":{"value":{"text":"Low level nondefinability results: domination and recursive enumeration","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2869914$7A6BDEAE-51EE-4291-9763-B7F60D2731E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cd9ebe56ec423ec5335930a0b1a45ca7ae3b5c0f","datavalue":{"value":{"entity-type":"item","numeric-id":6768298,"id":"Q6768298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$AE6126D8-D053-4398-9E0E-0E7014AE07A1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6770cb0701d2fdbe28990921a3aef74023bb0147","datavalue":{"value":"This study was motivated by a suggestion of \\textit{W. Miller} and \\textit{D. A. Martin} [Z. Math. Logik Grundlagen Math. 14, 159--166 (1968; Zbl 0216.29102)]. Recall that, for Turing degrees \\(a\\) and \\(b\\), \\(a \\mathrm{REA} b\\) means \\(a\\) is r.e. in \\(b\\) and \\(a \\geq b\\). A degree \\(a\\) is array nonrecursive (ANR) iff every \\(b \\geq a\\) bears REA to another degree [\\textit{M. Cai}, J. Symb. Log. 77, No. 1, 21--32 (2012; Zbl 1269.03044)]; otherwise it is array recursive (AR).NEWLINENEWLINEAmong the paper's many results: In the language \\((\\leq, \\mathrm{REA})\\) with the Turing degrees as universe, none of the classes of RE degrees, arithmetic degrees, or ANR degrees is definable by a \\(\\Sigma_1\\) or \\(\\Pi_1\\) formula. The jump operation is definable in that language by a \\(\\Pi_1\\) formula but not by a \\(\\Sigma_1\\) formula. Even with a parameter \\(c\\) added to the language, neither AR nor the hyperimmune-free degrees are definable by a \\(\\Sigma_1\\) formula. The arithmetic degrees are neither \\(\\Sigma_1\\) nor \\(\\Pi_1\\) definable in the language \\((\\leq, \\mathrm{jump})\\) and are neither \\(\\Sigma_2\\) nor \\(\\Pi_2\\) definable in the language \\((\\leq)\\). Neither the ANR degrees nor the hyperimmune degrees are definable by a \\(\\Sigma_1\\) formula in the language \\((\\leq, c)\\) nor by a \\(\\Sigma_0\\) formula in \\((\\leq, \\mathrm{jump}, c)\\). The \\(\\Sigma_1\\) theory of degrees in \\((\\leq, \\mathrm{REA})\\) is decidable.NEWLINENEWLINESeveral open questions are cited. Can the hyperimmune degrees be defined by a \\(\\Sigma_1\\) formula in \\((\\leq, \\mathrm{REA})\\)? Which degrees \\(> 0'\\) are jumps of hyperimmune-free degrees? If we replace REA in the language by the broader relation of relative recursive enumerability, which analogues of the paper's results still hold?","type":"string"},"datatype":"string"},"type":"statement","id":"Q2869914$7063B63D-62D5-4561-96BC-8FD88284C699","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b80b8bd1054c5101cd01e496a6e5c79a0223fa9f","datavalue":{"value":{"entity-type":"item","numeric-id":591980,"id":"Q591980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2869914$F439DCEF-8203-42FD-B152-DFFCCEC30D97","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2869914","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2869914"}}}}}