Search papers, labs, and topics across Lattice.
This paper resolves an open question regarding the comparability of two theories of induction鈥攐pen induction and clause set cycles鈥攂y demonstrating that the addition rules can only apply under specific conditions, which prevents the equality of terms from being provable. The authors introduce the Syntactic Invariance Principle, highlighting that the distinction between the two theories arises from the order of constants, which pertains to numerical properties rather than symbolic representations. Additionally, they draw speculative parallels to the barriers in resolving the P versus NP problem, suggesting that similar limitations may exist in computational techniques.
The Syntactic Invariance Principle reveals that some mathematical truths are fundamentally tied to numerical properties, not just symbolic manipulation, with implications for understanding computational limitations in P versus NP.
We start from a small open question, where Hetzl and Vierling asked whether two theories of induction, open induction and clause set cycles, are incomparable. They proved one direction and left the other open. Here we close it, and the proof is almost embarrassingly short, because the rules for addition can only fire when the first argument is $0$ or a successor, a Skolem constant is neither, so the terms $a{+}b$ and $b{+}a$ can never be touched, and a machine that can never touch them can never prove they are equal. The thing that separates the two theories is the order of two constants, and that order is a fact about numbers, not about symbols. We extract from this proof a small general principle, the Syntactic Invariance Principle, that names the shape of such arguments. We then close with a few speculative remarks on how this same shape appears, informally, in the known barriers to settling $\mathsf{P}$ versus $\mathsf{NP}$, where each barrier seems to point to a level of description that the techniques in the barrier cannot reach. We raise this as a suggestion rather than a theorem, since the analogy is real but we do not push it past the point where we can defend it. Along the way we raise an open question that the analogy suggests but does not settle, on whether a fast algorithm for $\SAT$, were it to exist, would always be exhibitable as a machine you can write down or whether it could be found, in some cases, only as a function on the numbers.
