Ajtai's theorem for $T^2_2(R)$ and pebble games with backtracking
<|reference_start|>Ajtai's theorem for $T^2_2(R)$ and pebble games with backtracking: We introduce a pebble game extended by backtracking options for one of the two players (called Prover) and reduce the provability of the pigeonhole principle for a generic predicate $R$ in the bounded arithmetic $T^2_2(R)$ to the existence of a particular kind of winning strategy (called oblivious) for Prover in the game. While the unprovability of the said principle in $T^2_2(R)$ is an immediate consequence of a celebrated theorem of Ajtai (which deals with a stronger theory $T_2(R)$), up-to-date no methods working for $T^2_2(R)$ directly (in particular without switching lemma) are known. Although the full analysis of the introduced pebble game is left open, as a first step towards resolving it, we restrict ourselves to a simplified version of the game. In this case, Prover can use only two pebbles and move in an extremely oblivious way. Besides, a series of backtracks can be made only once during a play. Under these assumptions, we show that no strategy of Prover can be winning.<|reference_end|>
@article{ken2024ajtai's,
    title={Ajtai's theorem for $T^2_2(R)$ and pebble games with backtracking},
    author={Eitetsu Ken and Mykyta Narusevych},
    journal={arXiv preprint arXiv:2406.10924},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.10924},
    primaryClass={math.LO cs.LO}
}