Reduction games, provability and compactness

Journal of Mathematical Logic 22 (3) (2022)
  Copy   BIBTEX

Abstract

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. 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 [math] principles over [math]-models of [math]. They also introduced a version of this game that similarly captures provability over [math]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [math] 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. Wang (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 [math] 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 “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [math], uncovering new differences between their logical strengths.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,252

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Philosophy through video games.Jon Cogburn - 2009 - New York: Routledge. Edited by Mark Silcox.
Winning strategies in club games and their applications.Bernhard König - 2011 - Mathematical Logic Quarterly 57 (1):19-26.
Omniscience and omnipotence: How they may help - or hurt - in a game.Steven J. Brams - 1982 - Inquiry: An Interdisciplinary Journal of Philosophy 25 (2):217 – 231.
Circulant games.Ɖura-Georg Granić & Johannes Kern - 2016 - Theory and Decision 80 (1):43-69.
What's My Motivation? Video Games and Interpretative Performance.Grant Tavinor - 2017 - Journal of Aesthetics and Art Criticism 75 (1):23-33.
Parallel strategies.Pavel Pudlák - 2003 - Journal of Symbolic Logic 68 (4):1242-1250.
Games and the art of agency.C. Thi Nguyen - 2019 - Philosophical Review 128 (4):423-462.
Information Tracking in Games on Graphs.Dietmar Berwanger & Łukasz Kaiser - 2010 - Journal of Logic, Language and Information 19 (4):395-412.

Analytics

Added to PP
2022-06-23

Downloads
11 (#1,089,082)

6 months
9 (#269,798)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
Closed choice and a uniform low basis theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.
Using Ramsey’s theorem once.Jeffry L. Hirst & Carl Mummert - 2019 - Archive for Mathematical Logic 58 (7-8):857-866.

View all 12 references / Add more references