{"entities":{"Q2909622":{"pageid":2920347,"ns":120,"title":"Item:Q2909622","lastrevid":51546209,"modified":"2026-01-18T17:43:33Z","type":"item","id":"Q2909622","labels":{"en":{"language":"en","value":"The \\(n\\)-r.e. degrees: undecidability and \\(\\Sigma_1\\) substructures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6078209"}},"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":"Q2909622$62219966-BD90-4926-9040-B971E9D6B2FB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d3fcac1bf518034be71a86d424789c2c836e6284","datavalue":{"value":"1253.03068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909622$513D2554-5E3E-478F-B229-1790C8F2F03A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b17094c631a9cf5f0370cef2c5a2a8b3c0910cd","datavalue":{"value":"10.1142/S0219061312500055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909622$AE58E646-0992-4159-928C-38C06B7C5D27","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":"Q2909622$2C0AE281-FA28-41AD-823E-6E1AEF3A3404","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":"Q2909622$9C46FCDD-1896-429E-8DB3-6BECC930C589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a89229a66bdfdb3e2e5619b7e8031866b3343269","datavalue":{"value":{"entity-type":"item","numeric-id":189917,"id":"Q189917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$F9ADD651-CAFF-45B8-AF21-90879F4E058E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7c127e90f3bdb626ec3e36ebc57f0604031b78a6","datavalue":{"value":{"entity-type":"item","numeric-id":2732505,"id":"Q2732505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$7203BD91-B235-477A-95D2-9CAB6899014E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a2e785076c925608e90781bb4173656a454ded85","datavalue":{"value":{"time":"+2012-09-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2909622$569D057D-630B-4436-A02D-3D94DC2AAE7B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909622$45D4521E-5C01-48CB-8F81-F8BFC076DCC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"86e7d9065663fa3ffd8f6c70df93df9f4742e385","datavalue":{"value":"03D28","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909622$53228DC6-9DF1-4A8B-84B7-6295894B2786","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b29e6a050a890de8815b2f1e2fb16541781b5d76","datavalue":{"value":"6078209","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909622$1DEFEF9C-4E77-41A5-A33A-D97DD1D69897","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91fe4280e2e06a0a064865358db087007d3f302b","datavalue":{"value":"Turing degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909622$CB272DC2-2F5C-4915-90A4-B5DC565123EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d926ce35a8474f9ab59d49ba429799909de14fe","datavalue":{"value":"\\(n\\)-recursively enumerable","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909622$4B4BA179-89A1-4DF9-A33B-F71817D0EE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909622$2BD5B7D5-1A98-472C-82AD-4B43B2B0FA8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be91e74a48ae14221f26475b85afc8a9d660f7f7","datavalue":{"value":"\\(\\Sigma_1\\)-substructure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909622$830A1F0E-FA15-44B9-889F-F9111D02FD85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"108a37540fa32d40b6da41594780bf2f0b9aef37","datavalue":{"value":"\\(n\\)-computably enumerable","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909622$989EF7A1-4A44-42CA-B1A9-A25225655ECD","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":"Q2909622$41F25338-6715-4E90-BFE8-CA1456EFAD7B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d665f0108660181ae2d07065779ff20d6d23d716","datavalue":{"value":{"entity-type":"item","numeric-id":3570156,"id":"Q3570156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$B70ECCB7-A0D1-4693-AA13-576B3D07479F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"944cc543495ec883d4fff588e35bcb43c0150adf","datavalue":{"value":{"entity-type":"item","numeric-id":1182487,"id":"Q1182487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$BAAC4310-DD07-4D0B-A525-2915C975E415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c929ecfa8f2db0dd69585ea5ecd0d74b52ed4269","datavalue":{"value":{"entity-type":"item","numeric-id":3764144,"id":"Q3764144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$DF864D4F-7D7D-4A68-9760-9D9A713C45EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98d3ab541b99faabf87b841c92b776d995f9d8fe","datavalue":{"value":{"entity-type":"item","numeric-id":755574,"id":"Q755574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$E7A4D514-8524-4CFF-B250-3B5F402B29F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2837e149efc9bf90cefe3576175ece9ca24506ed","datavalue":{"value":{"entity-type":"item","numeric-id":2551104,"id":"Q2551104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$AB3B3E76-2E8C-4EBA-BAD2-091AF313D3F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ad62835a55923ec861c71dbb6edfd53ffd42573","datavalue":{"value":{"entity-type":"item","numeric-id":5601468,"id":"Q5601468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$2AA191B5-7BBF-4D48-9E22-EF73FE821E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80e10ad025d9092a4bf339636fc9e15f8e0ef7fb","datavalue":{"value":{"entity-type":"item","numeric-id":3666835,"id":"Q3666835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$A244EA5A-8221-4309-A0A3-AEA0CD83AA43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93b39fcacfb292781455b7119d8e582f4040aa22","datavalue":{"value":{"entity-type":"item","numeric-id":3691653,"id":"Q3691653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$E0F887D3-1685-4F61-96BA-F6E1B252BC06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bdc477ea51711f0cface25143923945c4f939c6","datavalue":{"value":{"entity-type":"item","numeric-id":5566515,"id":"Q5566515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$311E639E-7AE2-45A6-BF72-E2517C7B1FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abc749d216d7ef73d2e4f1819d8a2b21835f381f","datavalue":{"value":{"entity-type":"item","numeric-id":3839947,"id":"Q3839947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$0D37F6F9-B74A-4F32-A8D7-A1086FF3EC34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0afd5532278da9a5d9cf1957582e7e12c5b70b","datavalue":{"value":{"entity-type":"item","numeric-id":2626398,"id":"Q2626398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$71D4E221-989F-4E22-A3B5-8C8BCBDEA383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37e8448e22f226dbbe4c1db043600eece03aaa3d","datavalue":{"value":{"entity-type":"item","numeric-id":3412461,"id":"Q3412461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$5B2BCFC9-3FA7-44F4-9F63-6B5BA1D2346E","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":"Q2909622$4C093638-CFB3-451F-ADD8-4A61F0B96F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8f50469b41c3ab481af5e1d67324db96d3e5dc4","datavalue":{"value":{"entity-type":"item","numeric-id":1234682,"id":"Q1234682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$CC901FEF-7922-46D2-BA5B-20B6C5ED0C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c95e506ae27112d9fbac80150d60aecf156bd303","datavalue":{"value":{"entity-type":"item","numeric-id":3416112,"id":"Q3416112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$1197DC2C-FFF3-43E0-A6CC-86655E8F77E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8827bb25975fd126f345bc5a9b6c2a45f53f8adf","datavalue":{"value":{"entity-type":"item","numeric-id":5519131,"id":"Q5519131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$A2CB213B-4A3F-4C13-92FB-7BB1E9C9404D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7a9d674e81fcaacc72479f4f0b993e1b43155bdf","datavalue":{"value":"https://doi.org/10.1142/s0219061312500055","type":"string"},"datatype":"url"},"type":"statement","id":"Q2909622$DF6DF1D7-0D86-4797-9165-73362264E238","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c86e9a39b3de5b5a6651785871db8d15985dbf47","datavalue":{"value":"W2151818063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909622$8B6739EA-A33A-4FD8-A543-3B47FFE97716","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"453aced9293966f1818e72de7fbd3b3d1b01942c","datavalue":{"value":{"text":"The \\(n\\)-r.e. degrees: undecidability and \\(\\Sigma_1\\) substructures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2909622$85EC7B6D-9E2A-4738-A0A7-6980D5E6F71F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"008c490b347a8117b5c353e4a50d0c35e8a875c2","datavalue":{"value":"A recursive function \\(f(x,s)\\) approximates the set \\(A\\) if for all \\(x\\), \\(f(x,0)=0\\), \\(\\lim_s f(x,s) \\in \\{0,1\\}\\), and \\(\\lim_s f(x,s) = 1\\) if and only if \\(x \\in A\\). The \\(n\\)-r.e.~sets are those which have a recursive approximation with at most \\(n\\) changes of value for each \\(x\\). Thus, the \\(1\\)-r.e.~sets are the familiar recursively enumerable sets. The \\(n\\)-r.e.~sets are also called \\(n\\)-c.e.~in the literature, and arise from the \\(n\\)-trial predicates of \\textit{H. Putnam} [``Trial and error predicates and the solution to a problem of Mostowski'', J. Symb. Log. 30, 49--57 (1965; Zbl 0193.30102)]. This paper addresses the global properties of \\(\\mathcal D_n\\), the Turing degrees of the \\(n\\)-r.e.~sets, showing that the structure of each \\(\\mathcal D_n\\) is very complicated. In particular, the authors prove (1) for every \\(n\\) the theory of \\(\\mathcal D_n\\) is undecidable, and (2) if \\(n<m\\) then \\(\\mathcal D_n\\) is not a \\(\\Sigma_1\\)-substructure of \\(\\mathcal D_m\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909622$10BF14D4-0FE4-41F9-A7CE-8AFE31BE8BA9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c2c7a0f70c0b7cc2161585e985e86183cb70d3ef","datavalue":{"value":{"entity-type":"item","numeric-id":335001,"id":"Q335001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909622$1A8C9C1A-00B4-4007-A997-758035E22559","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68d3b5aaea404df4cfd41e81335c744a5b5abf0a","datavalue":{"value":{"entity-type":"item","numeric-id":1009444,"id":"Q1009444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbab645d9154f2f2144fefa2fd32e45d843b76d0","datavalue":{"value":{"amount":"+0.8208725452423096","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":"Q2909622$97A10CE0-4A4D-4636-944B-8FA9B3897E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d2889752b4fe8d6ceeaa51aa5a8ed21ef0e5aa1","datavalue":{"value":{"entity-type":"item","numeric-id":4813796,"id":"Q4813796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02b0959ba47c85d1883ff1395bfbfdb10aa242da","datavalue":{"value":{"amount":"+0.8135148882865906","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":"Q2909622$8F3CDF85-43FF-423A-958F-384F83686D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e56cc276cc928c3a43d55987918919264ee506d3","datavalue":{"value":{"entity-type":"item","numeric-id":3491535,"id":"Q3491535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6220fa45437e0926af6c2c67d5843c9f2d769c5a","datavalue":{"value":{"amount":"+0.7906159162521362","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":"Q2909622$3ABB490C-A72F-444B-93E5-8963D780FD81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23b72d95cc306d4898f3169fd08a1090a10e3ae9","datavalue":{"value":{"entity-type":"item","numeric-id":4348130,"id":"Q4348130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77d9b667bb684d1871f367176424fee751f3ef3b","datavalue":{"value":{"amount":"+0.7893205285072327","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":"Q2909622$48E723B1-91D8-4226-89B2-F1055670453C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"192edd5b9ec4f14e2877b43cb4fcc22c93ce85cf","datavalue":{"value":{"entity-type":"item","numeric-id":607833,"id":"Q607833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77d9b667bb684d1871f367176424fee751f3ef3b","datavalue":{"value":{"amount":"+0.7893205285072327","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":"Q2909622$F884A47A-7015-4C24-BFE5-43799A85B9B9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2909622","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2909622"}}}}}