{"entities":{"Q512143":{"pageid":513910,"ns":120,"title":"Item:Q512143","lastrevid":62389737,"modified":"2026-04-11T05:45:38Z","type":"item","id":"Q512143","labels":{"en":{"language":"en","value":"Computable Ramsey's theorem for pairs needs infinitely many \\(\\Pi ^0_2\\) sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6688541"}},"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":"Q512143$C5F05C08-D0AB-46C0-9D34-D231339BA182","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"67f540915c8395d196adf70bbc4e217b6246a52b","datavalue":{"value":{"text":"Computable Ramsey's theorem for pairs needs infinitely many \\(\\Pi ^0_2\\) sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q512143$010651DF-6B70-4A66-88EF-CC8EA76DB469","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"58269c052e4dc9b79d38facc1b6de8f146942dae","datavalue":{"value":"1386.03056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512143$1A4D720B-896D-4EE7-9B62-0F4D8CD72D23","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2669d03ea949a35f9b784ce3db050cada6f79a08","datavalue":{"value":{"entity-type":"item","numeric-id":512142,"id":"Q512142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512143$E39C2890-6B88-4E52-9F80-F3E15862A3D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4aea1dd36182a052ff66ff5bfa454f46b990083b","datavalue":{"value":{"entity-type":"item","numeric-id":424578,"id":"Q424578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512143$5AE06AD3-4F7C-4808-9ED2-C067783CF5A0","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":"Q512143$8020E5C9-EFBE-4D0E-B900-0A997E763913","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f0603ea18d9047924c49ed7d920a19ba7519108b","datavalue":{"value":{"time":"+2017-02-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q512143$904B7B75-FD84-408B-A96E-8A55E637EC73","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ecafdd4b6ba690535cacb58bf38155e0d521001","datavalue":{"value":"https://arxiv.org/abs/1507.03256","type":"string"},"datatype":"url"},"type":"statement","id":"Q512143$FD7C1914-39C9-401B-A4AD-4BA0D2BF84FD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eeeaa2328027ad2f9da743c67dfe2f385cbd340c","datavalue":{"value":"\\textit{C. G. Jockusch jun.} [J. Symb. Log. 37, 268--280 (1972; Zbl 0262.02042)] initiated the study of the effective content of Ramsey's theorem and proved that for any computable \\(k\\)-coloring of pairs of integers, there is an infinite \\(\\Pi_2^0\\) homogeneous set. The proof used a countable collection of \\(\\Pi_2^0\\) sets as potential infinite homogeneous sets. He stated without proof that it can be shown that there is no computable way to prove this result with a finite number of \\(\\Pi_2^0\\) sets.  The authors prove the claim, showing that there is no computable way to take an index for an arbitrary computable coloring and produce a finite number of indices of \\(\\Pi_2^0\\) sets with the property that one of those sets will be homogeneous for that coloring. For proving this result, the authors introduce \\(n\\)-trains as objects with useful combinatorial properties which can be used as approximations to infinite \\(\\Pi_2^0\\) sets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q512143$A275CF71-41BC-4BA9-97EF-C0D1FB93397D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"22e22ff3ca06f883e91c2d57835216702c8be488","datavalue":{"value":{"entity-type":"item","numeric-id":593161,"id":"Q593161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512143$FA296CF8-BD5C-4612-9443-FCA3605A72C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"758b4d196a1f97708f26591fee42c00739e26cc0","datavalue":{"value":"03D80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512143$CCBA0C80-C7C0-410F-9230-D71BBB8609AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512143$17A6459F-5134-4238-BE13-E56622486809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512143$6DC098EA-99C1-44C8-8F1B-DDF54339B5A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"baa3a0649e53008a5b73f6450a2618cc58b44540","datavalue":{"value":"6688541","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512143$11EF4E70-A80C-4600-87FA-86881BAE98D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8d8b1d67384cd642422b7e762b22af41307ae4c","datavalue":{"value":"recursion theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q512143$A4245DE0-1CB8-4F52-8BD3-EDF16E2A9C2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"546f982464ca9e4d7b2d83e5ae55c43306696e3a","datavalue":{"value":"Ramsey's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q512143$F8ECAF80-B0FC-4DC8-95D5-4FD6E7EAEE14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697d4692382266a9be5b62597e2580cf843209d8","datavalue":{"value":"theory of computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q512143$FCA77939-B465-4FA2-BCDA-53B781D98827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80622b67c19bd5435237c2bda181dba6bacba045","datavalue":{"value":"\\(\\Pi_2^0\\) sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q512143$BB21F403-ED6E-49F8-B0F1-F87ABB5044DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79283f23522cce1dd26cd1d45950e5c789e14227","datavalue":{"value":"effective combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q512143$4B922D05-BD0C-4CB9-A684-3BC506B4C0D6","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":"Q512143$23F01F7F-4E48-4CC1-89AC-315083F8D46E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a62f9067a0c0f7f080638972e6019899b8471668","datavalue":{"value":"W2962726502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512143$EA2F9B5B-D3E7-4567-8B3E-A1197E599641","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bc68fbc256a340ad9770614b514ab49182f4bdd","datavalue":{"value":{"entity-type":"item","numeric-id":5677475,"id":"Q5677475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512143$826A2228-4D11-4D28-8DBF-B509CE2C0BD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8bcf4444f91b7dd2552e5eae0f668ea7d924f4f2","datavalue":{"value":"10.1007/S00153-016-0519-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512143$14B4EE0A-3CB8-4523-85F7-937C09C7F778","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fce7fc7d3326313a79361f0f0c4e3dd77d394b30","datavalue":{"value":{"entity-type":"item","numeric-id":2747723,"id":"Q2747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cff80945a1e47a64d824515fc6d955fdd67ac5db","datavalue":{"value":{"amount":"+0.8335843682289124","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":"Q512143$543BA35B-95D9-4A36-9568-E7197F167261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39b73d3d0ca97dd10dce841825c231f7475b8844","datavalue":{"value":{"entity-type":"item","numeric-id":2732267,"id":"Q2732267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"500b5c943a2fe823dabe92c0829f9756366db6ff","datavalue":{"value":{"amount":"+0.8305197358131409","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":"Q512143$95F44236-D7C3-4A57-9ECA-E27F79F95180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"906149f1516822330002e2a251afeb9f9791da2c","datavalue":{"value":{"entity-type":"item","numeric-id":4600456,"id":"Q4600456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fd4bc8a6c5389a4ce19982ecef24b34e964153f","datavalue":{"value":{"amount":"+0.830519437789917","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":"Q512143$A245BA62-D0F3-4BCD-9A34-86156D82E56C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d87cb4787ca121178180fe9c4328032cd29751e","datavalue":{"value":{"entity-type":"item","numeric-id":3630579,"id":"Q3630579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0a1942a2e24183341f7fb80c796e05c9c9783dc","datavalue":{"value":{"amount":"+0.8161818981170654","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":"Q512143$DEEAD955-CA05-486A-AAC2-2CA35613B8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e213e5a57a2230f087bf04f0c671ed2e5c54400","datavalue":{"value":{"entity-type":"item","numeric-id":4323045,"id":"Q4323045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1721c0baa0284ea5b908d595030696307bee7bb5","datavalue":{"value":{"amount":"+0.8001950979232788","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":"Q512143$EE12E969-DC79-49C1-8D35-A99AEE2595BA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computable Ramsey's theorem for pairs needs infinitely many \\(\\Pi ^0 2\\) sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computable_Ramsey%27s_theorem_for_pairs_needs_infinitely_many_%5C(%5CPi_%5E0_2%5C)_sets"}}}}}