{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T12:31:45Z","timestamp":1766493105974,"version":"3.41.2"},"reference-count":31,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","funder":[{"name":"a Focused Research Group","award":["DMS-1854355","DMS-1854279"],"award-info":[{"award-number":["DMS-1854355","DMS-1854279"]}]},{"name":"the NSF","award":["DMS-1600543"],"award-info":[{"award-number":["DMS-1600543"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Math. Log."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p> Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [Formula: see text] principles over [Formula: see text]-models of [Formula: see text]. They also introduced a version of this game that similarly captures provability over [Formula: see text]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [Formula: see text] between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H.\u00a0Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [Formula: see text] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is \u201cpurely proof-theoretic\u201d, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [Formula: see text], uncovering new differences between their logical strengths. <\/jats:p>","DOI":"10.1142\/s021906132250009x","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T09:27:13Z","timestamp":1655890033000},"source":"Crossref","is-referenced-by-count":3,"title":["Reduction games, provability and compactness"],"prefix":"10.1142","volume":"22","author":[{"given":"Damir D.","family":"Dzhafarov","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Connecticut, 341 Mansfield Road, U-1009, Storrs CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis R.","family":"Hirschfeldt","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Chicago, 5734 South University Avenue, Chicago IL 60637, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarah","family":"Reitzes","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Chicago, 5734 South University Avenue, Chicago IL 60637, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"journal-title":"Computability and Complexity in Analysis","year":"2014","author":"Bauer A.","key":"S021906132250009XBIB004"},{"key":"S021906132250009XBIB005","first-page":"10","volume-title":"Abstracts from Computability, Continuity, Constructivity 2019 \u2014 From Logic to Algorithms","author":"Bauer A.","year":"2019"},{"key":"S021906132250009XBIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.12.020"},{"key":"S021906132250009XBIB007","series-title":"Theory and Applications of Computability","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/978-3-030-59234-9_11","volume-title":"Handbook of Computability and Complexity in Analysis","author":"Brattka V.","year":"2021"},{"key":"S021906132250009XBIB008","first-page":"1","volume":"14","author":"Brattka V.","year":"2018","journal-title":"Log. Methods Comput. Sci."},{"key":"S021906132250009XBIB009","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2017.43"},{"key":"S021906132250009XBIB010","doi-asserted-by":"publisher","DOI":"10.2307\/2694910"},{"key":"S021906132250009XBIB011","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-09-10115-6"},{"key":"S021906132250009XBIB012","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00789-X"},{"key":"S021906132250009XBIB013","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6465"},{"key":"S021906132250009XBIB014","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2014-12261-1"},{"key":"S021906132250009XBIB015","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2016.1"},{"key":"S021906132250009XBIB016","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1002\/malq.201200025","volume":"58","author":"Frittaion E.","year":"2012","journal-title":"Math. Log. Q."},{"key":"S021906132250009XBIB017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3"},{"key":"S021906132250009XBIB018","doi-asserted-by":"publisher","DOI":"10.1142\/9208"},{"key":"S021906132250009XBIB019","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061316500021"},{"key":"S021906132250009XBIB020","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04847-8"},{"key":"S021906132250009XBIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-019-00664-z"},{"key":"S021906132250009XBIB023","doi-asserted-by":"publisher","DOI":"10.2307\/2272972"},{"key":"S021906132250009XBIB024","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1090\/S0002-9939-1990-0984802-2","volume":"108","author":"Kossak R.","year":"1990","journal-title":"Proc. Amer. Math. Soc."},{"key":"S021906132250009XBIB025","doi-asserted-by":"crossref","first-page":"1438","DOI":"10.1017\/jsl.2016.61","volume":"82","author":"Kuyper R.","year":"2017","journal-title":"J. Symb. Log."},{"key":"S021906132250009XBIB026","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.107903"},{"key":"S021906132250009XBIB027","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2017.76"},{"key":"S021906132250009XBIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.08.003"},{"key":"S021906132250009XBIB030","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1433-3"},{"issue":"2","key":"S021906132250009XBIB031","first-page":"11","volume":"14","author":"Pauly A.","year":"2018","journal-title":"Log. Methods Comput. Sci."},{"key":"S021906132250009XBIB032","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59971-2"},{"key":"S021906132250009XBIB033","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581007"},{"key":"S021906132250009XBIB034","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-31933-4","volume-title":"Turing Computability: Theory and Applications","author":"Soare R. I","year":"2016"},{"key":"S021906132250009XBIB036","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1017\/jsl.2020.53","volume":"86","author":"Uftring P.","year":"2021","journal-title":"J. Symb. Log."},{"key":"S021906132250009XBIB038","doi-asserted-by":"publisher","DOI":"10.3233\/COM-200295"}],"container-title":["Journal of Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021906132250009X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T03:38:33Z","timestamp":1670816313000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S021906132250009X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,22]]},"references-count":31,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1142\/S021906132250009X"],"URL":"https:\/\/doi.org\/10.1142\/s021906132250009x","relation":{},"ISSN":["0219-0613","1793-6691"],"issn-type":[{"type":"print","value":"0219-0613"},{"type":"electronic","value":"1793-6691"}],"subject":[],"published":{"date-parts":[[2022,6,22]]},"article-number":"2250009"}}