{"entities":{"Q2565991":{"pageid":2576734,"ns":120,"title":"Item:Q2565991","lastrevid":72794697,"modified":"2026-04-14T07:53:07Z","type":"item","id":"Q2565991","labels":{"en":{"language":"en","value":"Sets without subsets of higher many-one degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2210071"}},"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":"Q2565991$1A4A8D42-2AC6-4B63-B399-FD2771AE70E6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a1a5f761b667a3186ad914964a437d09d6798417","datavalue":{"value":{"text":"Sets without subsets of higher many-one degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2565991$C2E56B5A-BA06-48F7-8598-60623A3B9C0B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c3b1778fa47524093b98eb3b4ca075dfe5622f8f","datavalue":{"value":"1077.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565991$FD1F37E7-1F8C-40B2-995B-4516FB755109","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$EE1D762B-8F30-4134-9812-E624E288A831","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"149818fcb8bed0a5b750a95fd3a49925c0920292","datavalue":{"value":{"time":"+2005-09-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2565991$58645A7B-E024-4CD7-B425-D22272FF11EC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43b48f0d18783cbf2ca563959fc14e95126eaca3","datavalue":{"value":"For a reducibility \\(r\\), a set \\(A\\) is called \\(r\\)-introimmune iff there is no set \\(B \\subseteq A\\) such that \\(A-B\\) is infinite and \\(A\\) is \\(r\\)-reducible to \\(B\\). \\textit{R. I. Soare} [``Sets with no subset of higher degree'', J. Symb. Log. 34, 53--56 (1969; Zbl 0182.01602)] showed that there are Turing-introreducible sets. This result translates of course directly to all stronger reducibilities like many-one reducibility or polynomial-time Turing reducibility. Therefore, the author asks more for the complexity of such sets than for their existence. He investigates this question in the context of the many-one reducibility. In the present paper, he shows that many-one introimmune sets are immune. Furthermore, cohesive sets are many-one introimmune and hence there are \\(\\Pi^0_1\\)-sets with this property. Also, the author constructs a \\(\\Delta^0_2\\)-set \\(A\\) such that whenever \\(A \\leq_m B\\) and \\(B\\) is a subset of \\(A\\) or its complement then \\(B\\) is a finite variant of \\(A\\) or its complement, respectively. Such a set \\(A\\) is called bi-many-one-introimmune. Bi-many-one-introimmune sets cannot be \\(\\Pi^0_1\\)-sets or \\(\\Sigma^0_1\\)-sets, so the example given fits into the lowest possible level of Kleene's hierarchy. The author's example \\(A\\) has some further properties: if \\(A \\leq_m B\\) then the many-one reduction witnessing this is one-one on a cofinite domain, what is called strongly bi-many-one-introimmune; furthermore, the set \\(A\\) has large gaps, that is, for a fixed \\(K\\)-recursive function \\(f\\) dominating all recursive functions, there are infinitely many numbers \\(x\\) such that \\(x+1,x+2,\\ldots,f(x) \\notin A\\); the same type of gaps occur in the complement of \\(A\\). It could be noted, that one can obtain (strongly) bi-many-one-introimmune sets also from the theory of randomness as every Martin-L\u00f6f random set has this property and Chaitin's \\(\\Omega\\) is a \\(\\Delta^0_2\\)-set of this type. Furthermore, every \\(1\\)-generic set Turing reducible to the halting-problem \\(K\\) admits all types of recursive gaps although only some \\(1\\)-generic sets below \\(K\\) admit the types of gaps desired by the author. In the last section, the construction of this set \\(A\\) is transferred into the complexity-theoretic setting. \\textit{K. Ambos-Spies} [``Problems which cannot be reduced to any proper subproblems'', Lect. Notes Comput. Sci. 2747, 162--168 (2003)] constructed already an exponential-time computable set that is Turing-introimmune. The author constructs a strongly bi-polynomial-time many-one-introimmune set \\(A\\) such that both \\(A\\) and its complement have gaps with respect to a given recursive function \\(f\\). In the paper, some concrete function \\(f\\) is given, but indeed, any recursive function \\(f\\) could be used.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2565991$B1608C51-9996-41EE-953D-4125EEB56C08","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4f5d929e6d799449b9b757c7574900483de9ffa4","datavalue":{"value":{"entity-type":"item","numeric-id":324251,"id":"Q324251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$594C3E33-D37E-4D21-A753-7B0FA72CD3E3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565991$8A5E04AD-1D0F-41E3-87BE-73C3299B4F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565991$8FC48628-9C02-4A7E-A8EE-EA3B82A05CA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565991$A770D1C4-5F9F-4DC9-B42B-62CB2BE3D232","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"357f8679d02bcbf8fbe26eeb50c896280b045d65","datavalue":{"value":"2210071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565991$7EB30204-9E2F-49AD-8970-1FED6787A29E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"214cfd74473bc6d0eae3b8ca28189646d43fd7f1","datavalue":{"value":"many-one reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2565991$C6117F21-C434-41D8-AE4B-EFE1DF0BA5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1028605681bc0f1a3529a6a566859aa944f37170","datavalue":{"value":"Kleene hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2565991$4C229668-F6C6-40E7-89F1-DCBEBCE9BBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2565991$55EFECD7-7F49-4189-8EFC-5C9A2FC103FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eff58747a1a4cc34d105163062db80f613ccbfd5","datavalue":{"value":{"entity-type":"item","numeric-id":286989,"id":"Q286989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$560384DA-2868-4266-9D32-F55625CA9C47","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":"Q2565991$ABD2AFD1-140C-4330-8F43-C2966789252C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"15f5031c01aa8b444a98a38c2d41d551cd9cc4bf","datavalue":{"value":"https://doi.org/10.1305/ndjfl/1117755150","type":"string"},"datatype":"url"},"type":"statement","id":"Q2565991$E6733161-DD2D-4211-801A-324D3CA6437B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0cfc34f2e823b35024db5d92c16ddae70818047a","datavalue":{"value":"W2020372113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565991$DEA6E4BD-1EA2-4747-887C-5BAE99FB8A7D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b05154039e62ae55b73b924ba38bcf76fd10fcd","datavalue":{"value":{"entity-type":"item","numeric-id":5431301,"id":"Q5431301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$FB1E847E-B364-4E10-9422-CDE84CA175F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$8052849E-E9EA-4CF0-9F73-134E9F06942D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$C63C9CD8-6B09-4989-941C-0D4191E714BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4f9b219f54da4cc88e481211745b7b70548f30","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$9DDD9AC4-F90B-4B96-AE66-27371ED893E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd90f9daaeb4d762fab84117a161e37a40441abf","datavalue":{"value":{"entity-type":"item","numeric-id":4293543,"id":"Q4293543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$940316C6-EAF2-4AD6-A800-5D79EA1C3D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9962de275cdea4302e7700f00429e11ae25341fc","datavalue":{"value":{"entity-type":"item","numeric-id":1405796,"id":"Q1405796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$364C0AC6-5301-4129-A383-91360419D67D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ebb5fb55527efe055ecf16741949ed831da4c1","datavalue":{"value":{"entity-type":"item","numeric-id":3250596,"id":"Q3250596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$89F651E3-852C-4EB5-AC5C-8D5C02732FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$C01A36ED-B73F-4F26-97F9-F887DFC0A9D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad61c7d7518dfa08e2f5eedc27b2c0b0e1b56cc0","datavalue":{"value":{"entity-type":"item","numeric-id":915447,"id":"Q915447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$6CF53B85-EC96-4962-91AE-2FB4081018A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$1981B488-E0F0-4A71-B593-B2A63FBEF9BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3f4f13509c05ca44b6aa78d129e88e614ae0100","datavalue":{"value":{"entity-type":"item","numeric-id":1307029,"id":"Q1307029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$C2C1DEF0-A5D1-4E77-B1F5-B78EBF7FA689","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":"Q2565991$05AC89F6-2748-4761-99C9-1CA316B7CA04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7caaae22ec3438480bd906a275efa207942ce68","datavalue":{"value":{"entity-type":"item","numeric-id":2521032,"id":"Q2521032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$50F18AE9-1670-4BBE-8B18-F0E688E56203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3145791be41afb1e842f815f01a740997a825544","datavalue":{"value":{"entity-type":"item","numeric-id":1913632,"id":"Q1913632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$E02F0A6B-017A-435F-9A84-FCDBEEB093DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"278c13c64bf4570beeb708d82c5a73ea4bd21d62","datavalue":{"value":{"entity-type":"item","numeric-id":4186305,"id":"Q4186305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$297EC1AA-B540-4D45-B8FD-C6CD6DB9DE67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c388b60232439703fa64a3e14f0b073849f7bb2a","datavalue":{"value":{"entity-type":"item","numeric-id":5573379,"id":"Q5573379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$65D90276-7996-4E9F-BE1B-35AC559FA6C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce38d666d23d39801802e7eff3732bc0ae06ca41","datavalue":{"value":{"entity-type":"item","numeric-id":2395863,"id":"Q2395863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565991$DCA02F8B-8A75-4D60-B2DF-B0DF59BB22B7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ca3a379d9cb6f89d846643d5d1ae2a05787ac1c","datavalue":{"value":"10.1305/NDJFL/1117755150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565991$E28726AF-CC93-4BAE-B0E7-209E5E92DEA8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5f6fd353561538c2d8da17358c5f90c2bd45977","datavalue":{"value":{"entity-type":"item","numeric-id":3096087,"id":"Q3096087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43d9e808d8a10e852179b543c61e7f1f3b0e6851","datavalue":{"value":{"amount":"+0.9080851078033448","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":"Q2565991$6CAA21C6-F422-496E-84A5-7533D50F19CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52f1449305ebdbc706c49cf1f25d0006283e7059","datavalue":{"value":{"entity-type":"item","numeric-id":2752147,"id":"Q2752147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4945928c9cf6560913cfe5fab47c342928490d15","datavalue":{"value":{"amount":"+0.8888232111930847","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":"Q2565991$44321709-9830-433D-B784-1DA1DCC136E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33c739d13719a107babd9391c1e0ebd47847e1cc","datavalue":{"value":{"entity-type":"item","numeric-id":5431301,"id":"Q5431301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e13b9c5f63d219001b74cdfab1805d7b691c39b","datavalue":{"value":{"amount":"+0.8323118686676025","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":"Q2565991$D121D767-B730-440C-86E7-6D74F8F7ECD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee6c66b2ac7f5947fe7308ba1ca97c70ca857a52","datavalue":{"value":{"entity-type":"item","numeric-id":1405796,"id":"Q1405796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51cd1d2daff3d1dd67a338a7da57ac846d76d2dd","datavalue":{"value":{"amount":"+0.8180035352706909","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":"Q2565991$3D4EC564-D354-4DC1-9599-65FB505D7C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"583016fee0f1bcb3313162b9ae335859dd07c83b","datavalue":{"value":{"entity-type":"item","numeric-id":4627721,"id":"Q4627721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5461919f125d2cba04f13ae94fac607d4bb35d","datavalue":{"value":{"amount":"+0.8033545613288879","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":"Q2565991$968DF7E3-6299-4EBC-9082-27BA921C4D0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sets without subsets of higher many-one degree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sets_without_subsets_of_higher_many-one_degree"}}}}}