Medvedev Logic is Not Decidable. It is π01 -complete. Who Would Have Guessed?

@misc{pawlowski2026medvedev,
  title = {{Medvedev Logic is Not Decidable. It is π01 -complete. Who Would Have Guessed?}},
  author = {Pawel Pawlowski},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.11576},
  eprint = {2609.11576},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.11576},
  note = {CC0},
}

TY  - UNPB
TI  - Medvedev Logic is Not Decidable. It is π01 -complete. Who Would Have Guessed?
AU  - Pawel Pawlowski
PY  - 2026
DA  - 2026/09/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.11576
UR  - https://arxiv.org/abs/2609.11576
AB  - This project began as an attempt to prove that Medvedev logic is decidable with the help of generative AI systems. The author (as well as the generative AI systems, or at least they claim to be since I have asked them) was surprised by its eventual conclusion. We prove that Medvedev logic ML, the intermediate logic of finite problems, is Pi-01-complete under computable many-one reductions. Consequently, ML is not recursively enumerable, a fortiori undecidable, and admits no recursively enumerable sound and complete proof calculus. The proof connects the periodic domino problem with intuitionistic formulas through a shared intermediate structure that we call a Wang-Medvedev pair. Such a pair consists of a finite partially ordered set of roles together with demands. Demands define the interaction between roles. A realization labels nonempty subsets of a finite set with these roles, respecting the order and satisfying the demands. We associate a pair with each finite Wang system and show that it has a realization iff the system tiles a finite torus. We then construct an intuitionistic formula that fails on some finite Medvedev frame iff the same pair is realizable. Realizability thus provides the link between periodic tilings and the countermodels.
ER  -