CS Paper Radar

Medvedev logic is undecidable

Rodrigo Nicolau Almeida, Søren Brinck Knudstorp

cs.LO math.LO ·submitted 2026-09-11 17:49 UTC · v1

Abstract

We show that Medvedev's logic of finite problems, a well-known superintuitionistic logic, is undecidable. The key method is a reduction from the periodic tiling problem to non-theoremhood in Medvedev's logic. This settles a longstanding open problem. Using similar techniques, but reducing instead to the ordinary tiling problem, we likewise obtain undecidability of Skvortsov's logic of infinite problems, and the fact that the two logics are distinct -- in fact, they are separated by any aperiodic tiling of the plane. Due to the fact that Medvedev's logic figures in so many different areas, these results have implications for several fields -- for example, the study of schematic fragments of logics such as propositional dependence logic, or the study of internal logics of toposes. The core idea and technical work of the undecidability proof were obtained using ChatGPT Sol 5.6, and formally verified in Lean by Claude Opus 5. A detailed methodology section outlines how such results were obtained.

Comment
32 pages; main result obtained via LLM (see methodology section)

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LO math.LO ·2026-09-10 ·Pawel Pawlowski
theory similarity 0.68
Abstract

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.

0.53

Non-finite Axiomatizability and Undecidability of $\mathsf{Cheq}$

cs.LO math.LO ·2026-09-30 ·Han Xiao
theory similarity 0.63
Abstract

We prove that $\mathsf{Cheq}$ is not finitely axiomatizable, resolving a longstanding open problem in intermediate and modal logics. We further prove that the undecidability of Medvedev logic implies the undecidability of $\mathsf{Cheq}$.

0.23

The Metacomplexity Structure of Search Problems

cs.CC ·2026-11-18 ·Shalev Ben-David, M. H. Ebtehaj
similarity 0.57
Abstract · 48 pages

We study the metacomplexity tasks of refuting an algorithm for a given search problem or refuting a mapping reduction between two search problems. We show that these tasks are deeply related to the structure of the lattice of search problems under mapping reductions: the "refutation of a reduction" task amounts to a certain Heyting-type arrow in this lattice. We then give several structural complexity results about search problems and show they have implications for metacomplexity. First, by relating metacomplexity to a Heyting algebra structure, we are able to translate results from intuitionistic logic into complexity theoretic consequences. For example, the propositional logic identity $x\wedge \neg x=\bot$ translates to the following complexity-theoretic fact: if a search problem $R$ reduces to both $S$ and to the refutation task of $S$, then $R$ is in $\mathsf{FP}$. All such logical identities that hold in intuitionistic logic translate to complexity in a black box way. We find prime ideals of the reducibility lattice of search problems; as a consequence, we show that for any verifiable search problem $S$, either $S$ is in $(\mathsf{FP/poly})_{io}$ or else the refutation task of $S$ is in $(\mathsf{FP/poly})_{io}$. Similarly, either $S$ has infinitely-often heuristic algorithms or else the refutation task of $S$ has infinitely often heuristic algorithms. Finally, we give a structural result that may be of independent interest: any "tamely semantic" class of search problems (one which can be enumerated using a Halting oracle) is characterized by its decidably verifiable hard problems.

0.41

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.56
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.49

The Sources of Unknowability and Self-refutation in Epistemic and Dynamic Epistemic Logic

cs.LO ·2026-09-18 ·Eiji Yamada
similarity 0.54
Abstract · 13 pages, no figures, accepted for presentation and presented at the Asian Workshop on Philosophical Logic (AWPL 2026)

In this paper, we define a formula $\varphi$ to be unbelievable if $\Box\varphi$ is unsatisfiable, and unknowable if $\Box\varphi\land\varphi$ is unsatisfiable. We then analyze the sources of unknowability and unbelievability in different classes of frames K, KD, KD45, and S5. We first show that any unbelievable formula is a fixed point of the Moore function defined by $f(\varphi)=\varphi\land\lnot\Box\varphi.$ Our main result shows that in S5, the static notions of unknowability and unbelievability in epistemic logic, and the dynamic notions of always informativeness and eventual self-refutation in dynamic epistemic logic are all equivalent to ``Moorean phenomena.'' We also generalize the result to the multi-agent case, showing that although all unknowable formulas still manifest Moorean phenomena, new mechanisms arise due to their interactive nature. Finally, we briefly analyze whether the Brandenburger-Keisler paradox in epistemic game theory can be considered Moorean.

0.59

Mechanizing Gödel's Incompleteness Theorems and Provability Logic

cs.LO math.LO ·2026-09-12 ·Shogo Saitou, Mashu Noguchi
theory similarity 0.54
Abstract · 52 pages, 2 figures. Also available the latest version: https://formalizedformallogic.github.io/Mechanizing-Godels-Incompleteness-Theorems-a…

We mechanized proof of Gödel's first and second incompleteness theorems, Solovay's arithmetical completeness theorem of \mathbf{GL}, and related results in the Lean 4 theorem prover.

0.34

Restricted Peirce's Law and Natural Deduction

cs.LO ·2026-10-29 ·Satoru Niki
publishedtheoryhot direction similarity 0.54
Abstract · In Proceedings NCL'26, arXiv:2610.34489

The constructive logic JP' is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by the double negation of ex falso quodlibet, neither of which is very intuitive. In order to have an alternative perspective on this negation, we study in this paper a couple of natural deduction systems for JP'. We first present a system that is normalisable and satisfies a restricted form of the subformula property. Then a modification of this system is introduced, whose rules satisfy the separation of connectives and the full subformula property. Afterwards we turn our attention to a typed lambda-calculus, with respect to which our natural deduction enjoys the Curry-Howard correspondence, followed by a concluding discussion.

0.40

Dynamic Polyhedral Logic

cs.LO ·2026-08-26 ·Nick Bezhanishvili, Laura Bussi, Vincenzo Ciancia, David Fernández-Duque, David Gabelaia
similarity 0.53
Abstract

We introduce spatio-temporal polyhedral reachability logics, extending dynamic topological logic with polyhedral semantics and a path-based spatial reachability operator. Formulas are interpreted over polyhedra, with admissible valuations ranging over polyhedral subsets; the spatial modality is interpreted as interior, the binary operator $γ(\varphi,ψ)$ expresses reachability of a $ψ$-point through a $\varphi$-region, and the temporal modalities are interpreted by a PL-homeomorphism and its inverse. We define h-dynamic reachability spaces and axiomatize the corresponding h-dynamic extensions of the known reachability logics of topological, finite, Alexandroff, and polyhedral spaces. The main result is soundness and completeness for the intended classes of invertible dynamical systems.

0.26