{"entities":{"Q1944337":{"pageid":1955079,"ns":120,"title":"Item:Q1944337","lastrevid":43438490,"modified":"2025-07-25T20:38:36Z","type":"item","id":"Q1944337","labels":{"en":{"language":"en","value":"The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6150721"}},"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":"Q1944337$61CFBD40-1DA5-4B22-80FF-A8F8CEC18297","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"64cff9f28b70c3f1d9176074f58815f8ce050e8d","datavalue":{"value":{"text":"The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1944337$C9E0DFA9-10DE-4E19-8014-99B01622B37A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c3f00c5b5a802f6c50441353f1efb7f4aeaa088d","datavalue":{"value":"1275.03132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1944337$D3D07016-0DDA-4C43-8362-B06FED95FCEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d3a71e906f136e04e36e28f361a65aadd8942bd","datavalue":{"value":{"entity-type":"item","numeric-id":1944335,"id":"Q1944335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1944337$07600DA2-E469-462E-8F5B-1ADB8F2425A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2096cc3615b2876a859beddb3407ff2bc96d7c0f","datavalue":{"value":{"entity-type":"item","numeric-id":173434,"id":"Q173434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1944337$9C7D1362-FC47-4A66-B022-76902D35A015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fb2011abf9d0420ac8bf8ece04a2d3cb181bf0a","datavalue":{"value":{"entity-type":"item","numeric-id":1944336,"id":"Q1944336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1944337$AF9659AD-8566-463D-864E-BD17EA625AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b09a388965329c926d542d4fdd3e9db9fa7e3d1","datavalue":{"value":{"entity-type":"item","numeric-id":162061,"id":"Q162061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1944337$5B6DD560-7DE1-4124-A585-75A440203526","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":"Q1944337$A4B8A07D-0596-4E7F-B607-BF627727DAB5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7ac0237a4c838e7410fae458f0b3bdcfef1a1db","datavalue":{"value":{"time":"+2013-04-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1944337$EB151941-342F-45BA-9FC7-89D3F0D18B6A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b6acc53f7ba961faa7f7b5624050838d121ff47f","datavalue":{"value":"In this article the authors complete the proof that the two partial orderings \\(({\\mathbf R}_{\\text{ibT}},\\leq)\\) and \\(({\\mathbf R}_{\\text{cl}},\\leq)\\) do not share the same first-order properties. \\({\\mathbf R}_{\\text{ibT}}\\) is the class of all the c.e. identity-bounded Turing degrees, and \\({\\mathbf R}_{\\text{cl}}\\) is the class of all the c.e. computable Lipschitz degrees. The first part of the paper contains the main result: (1) There is a c.e. cl-degree \\({\\mathbf a}>{\\mathbf 0}\\) such that the class of \\({\\mathbf a}\\)-noncuppable c.e. cl-degrees is not bounded by any c.e. cl-degree strictly below \\({\\mathbf a}\\). The first-order property (1) is not true in \\(({\\mathbf R}_{\\text{ibT}},\\leq)\\), due to a result shown in [\\textit{K. Ambos-Spies}, ``On the strongly bounded Turing degrees of the computably enumerable sets'' (to appear)]. Exactly, Ambos-Spies showed the following: (2) For any c.e. ibT-degree \\({\\mathbf a}>{\\mathbf 0}\\), \\({\\mathbf {NCu}}({\\mathbf a})\\subseteq\\{{\\mathbf b}\\in{\\mathbf R}_{\\text{ibT}}:{\\mathbf b}\\leq{\\mathbf a}+1\\}\\). In (2) \\({\\mathbf {NCu}}({\\mathbf a})\\) denotes the class of \\({\\mathbf a}\\)-noncuppable c.e ibT-degrees, while \\({\\mathbf a}+1\\) denotes the ibT-degree determined by \\({\\mathbf a}\\) and the constant shift function 1; moreover, the ibT-degree \\({\\mathbf a}+1\\) is strictly below \\({\\mathbf a}\\) [loc. cit.; \\textit{K. Ambos-Spies} et al., Theory Comput. Syst. 52, No. 1, 2--27 (2013; Zbl 1273.03140)]. The paper under review also contains a short proof of (2). In the second part of the article it is shown that the converse of (2) is not true. Actually, a more general result is shown which extends to every computable shift function, namely: (3) Given any computable shift function \\(f\\), there is a c.e. ibT-degree \\({\\mathbf a}>{\\mathbf 0}\\) such that the \\(f\\)-shift ibT-degree \\({\\mathbf a}_f\\) of \\({\\mathbf a}\\) cups to \\({\\mathbf a}\\). A result similar to (3) is also shown for the c.e. cl-degrees. The paper ends with a section dedicated to some interesting open questions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1944337$2F9E58D9-A0AD-4D1A-B180-C39A59D67726","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1944337$2530B7A0-E075-4FA9-AE74-B3792699186B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1944337$1491241F-FA35-48CE-8E4E-3A9AEFF2791F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1a228c5bcac35d5298e8cccf2823e6a5b533cb7e","datavalue":{"value":"6150721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1944337$1B233967-645C-4FFC-8E0B-A5C98F017F49","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef8c9852ef7c401fecf3da98d430ea61e2f15921","datavalue":{"value":"identity-bounded Turing reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1944337$B6B5B28D-F467-484E-B147-D6F5115ADE03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2396c6a6ceb0a94e57be8790ef1648553d829fbb","datavalue":{"value":"computable Lipschitz reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1944337$BBD6832C-A6EC-4AC1-BA8E-8D64B0336CAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4eb313d3005a5865e8a1b33f13a1c66f607feb6","datavalue":{"value":"elementary equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1944337$11BF5894-AA62-49B3-9A41-AAE9C511247B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbce388cc861e9c4b8e46f7a2f30d9130e9c9cf1","datavalue":{"value":"degree structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1944337$8547156D-F958-4749-85F2-9C347D764666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85febe3462707c2c5b5e1d0fedefe383d6ecdfef","datavalue":{"value":"cuppable degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1944337$AF1961D6-283E-4184-8152-7F1DE659A1E2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3f64638a8e946e0d81e5fb7bc20fa3f4b6703c8d","datavalue":{"value":{"entity-type":"item","numeric-id":286989,"id":"Q286989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1944337$73CB0537-96EA-4EEB-B654-0C117297615B","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":"Q1944337$FA688EB3-5EE3-4CD1-A977-5B89FE8B123D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a40863d6d22b79057458af526b335e873ceb5973","datavalue":{"value":"https://doi.org/10.1016/j.apal.2012.11.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1944337$930638F6-C108-4279-A3B5-AEC2A1372ECF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ea1cae32d5c659f0f7186ee93373095c91cfe31a","datavalue":{"value":"W1984904260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1944337$32AF69EC-BB16-4C7D-B141-0A4ABC0E26FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e2452e59d757957e0273a87f4459f8b12ef88d3e","datavalue":{"value":"10.1016/J.APAL.2012.11.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1944337$BB999D0C-6DE0-4E3E-904A-F3C99671E546","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"772feb1fd035ce6681d968e29c7d7353febe0165","datavalue":{"value":{"entity-type":"item","numeric-id":5417040,"id":"Q5417040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"644bb98fa8c4c8ed6e94f2dade06e8ec3c9b533c","datavalue":{"value":{"amount":"+0.9030462","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$6695C49A-628E-40D6-8A78-428005A4B802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ab75cff94a92b7c43ae55e02ce2e60209460d99","datavalue":{"value":{"entity-type":"item","numeric-id":2498899,"id":"Q2498899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebd981a0d38db6b844a434b7ed0ff80d4381aca8","datavalue":{"value":{"amount":"+0.8746463","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$EF27E2DA-4D22-41D4-B891-A2E81938E11A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ace40e261989fe631ab7ea374219027249c577bf","datavalue":{"value":{"entity-type":"item","numeric-id":1673673,"id":"Q1673673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15087593c2f535caa8ccf89fab1f38ba44cac2e1","datavalue":{"value":{"amount":"+0.84275854","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$4B8EDD25-07C1-4004-80FC-2DEA8D2B4814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5abaf90cc212f39ddcef7228d7be108f22b548f3","datavalue":{"value":{"entity-type":"item","numeric-id":4904461,"id":"Q4904461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3f35e86e6f087b5fcfab7e5ff77e7833c0dcb3d","datavalue":{"value":{"amount":"+0.8398248","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$40AD98F2-65C1-4AEE-ABD2-339BA02BDA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56be1e9e5165fe39eb6fc209c91e919cfdd91591","datavalue":{"value":{"entity-type":"item","numeric-id":2700830,"id":"Q2700830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e9a54dca3da1a3dc24132201bb27ce892bc60d8","datavalue":{"value":{"amount":"+0.83340245","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$D90A7581-4000-4EA6-A12B-EE1B0BC16047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cc00a7e91cd4994df0dc90d1fe60cafbce2137a","datavalue":{"value":{"entity-type":"item","numeric-id":1425651,"id":"Q1425651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61f2d098870fe1351177f3683b6d5a5e4264f1e9","datavalue":{"value":{"amount":"+0.82824624","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$1D74FD71-0278-4198-95E3-45CA1D5CAFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"961d8ce2f1f632fad661796c406f88c44ae35269","datavalue":{"value":{"entity-type":"item","numeric-id":3521597,"id":"Q3521597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0ab44471fb3f86439365a65f7898bb3ce56bfcd","datavalue":{"value":{"amount":"+0.8249892","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$AE71CE06-2E74-44BF-AC57-0633DED86649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c3008a0ce1d94d970fb8bb2de0719a55802d0fd","datavalue":{"value":{"entity-type":"item","numeric-id":2907064,"id":"Q2907064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df20e7dafeb8a4361283fea26c896ed6ae9da2cc","datavalue":{"value":{"amount":"+0.8248695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$9B89EA34-1D18-43D9-B969-7E9006BCC03E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"715b01fc6be514e4fb8aa21bf8b0b6a48d1f7ebe","datavalue":{"value":{"entity-type":"item","numeric-id":3380356,"id":"Q3380356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"824c327d9727d95c7eef0de995b8512753bcc7be","datavalue":{"value":{"amount":"+0.8243362","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$F2B0186C-5E88-4E7B-8615-86AD8715CA98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa841a48497f7f335f16fdfe159b618f280a9c9b","datavalue":{"value":{"entity-type":"item","numeric-id":5898859,"id":"Q5898859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac2811b1e9b51b90377e8cb21460e4585c647098","datavalue":{"value":{"amount":"+0.82289326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1944337$7892D81E-5D40-4921-969F-8313E28C7FD3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1944337","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1944337"}}}}}