Syntactic Systems Cannot See Semantic Invariants

• URL: http://arxiv.org/abs/2606.17275v1
• Date: Mon, 15 Jun 2026 20:34:13 GMT
• Title: Syntactic Systems Cannot See Semantic Invariants
• Abstract summary: Hetzl and Vierling asked whether two theories of induction, open induction and clause set cycles, are incomparable.<n>They proved one direction and left the other open.<n>The thing that separates the two theories is the order of two constants, and that order is a fact about numbers, not about symbols.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit [42.15597840680038]
  We model the generation of valuable mathematics as nested language generation in the limit.<n>Every output is valuable ($in H$), trivial ($in F set H$), or a hallucination ($notin F$)
  arXiv  Detail & Related papers  (2026-06-12T17:52:24Z)
• Quantum Colorings of Spheres [0.0]
  We show that if $Sn-1$ is quantumly $n$-colorable, then either $n=2$ or $n$ is a multiple of 4, and show that the converse holds whenever a Hadamard matrix of order $n$ exists.<n>It also follows from this equivalence that $Sn-1$ admits a rank-one quantum $n$-coloring if and only if $n in 2,4,8$, thereby settling a conjecture of Zeng and Zhang.
  arXiv  Detail & Related papers  (2026-06-09T13:49:08Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Yanasse: Finding New Proofs from Deep Vision's Analogies, Part 1 [51.56484100374058]
  System extracts tactic usage distributions across 27 top-level areas of Mathlib.<n>It computes z-scores to identify tactics that are heavily used in a source area but rare or absent in a target area.<n>It matches source and target proof states via GPU-accelerated NP-hard analogy.
  arXiv  Detail & Related papers  (2026-04-19T03:27:16Z)
• A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem [0.0]
  Rice's theorem states that no non-trivial semantic property of programs is decidable.<n>We present a proof that is constructive relative to the undecidability of Hilbert's Tenth Problem (MRDP)<n>The argument is structured as two separate implications, never asserting a disjunction about solvability, and never examining P(bot)
  arXiv  Detail & Related papers  (2026-04-11T20:45:58Z)
• Burau representation, Squier's form, and non-Abelian anyons [53.92822954974537]
  We introduce a frequency-tunable, two-dimensional non-Abelian control of operation order constructed from the Burau representation of the braid group $B_3$.<n>The sign change of $Delta(omega)$ across the Squier positivity window reveals alternating constructive and destructive interference of causal orders.<n> Numerical simulations confirm both enhancement and suppression regimes, establishing a minimal $B_3$ braid control.
  arXiv  Detail & Related papers  (2025-10-21T00:25:21Z)
• Abductive Reasoning in a Paraconsistent Framework [7.4842212802498755]
  We consider two expansions of the well-known Belnap-Dunn paraconsistent four-valued logic $mathsfBD$. We show how to reduce abduction in $mathsfBD_circ$ and $mathsfBD_triangle$ to abduction in classical propositional logic.
  arXiv  Detail & Related papers  (2024-08-01T08:12:52Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Contra Bellum: Bell's theorem as a confusion of languages [0.0]
  Bell's theorem is a conflict of mathematical predictions formulated within an infinite hierarchy of mathematical models. Inequalities formulated at level $kinmathbbZ$, are violated by probabilities at level $k+1$.
  arXiv  Detail & Related papers  (2023-01-06T07:51:44Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy [0.12891210250935145]
  We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy. We show that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value.
  arXiv  Detail & Related papers  (2021-10-09T21:53:02Z)
• Agnostic Online Learning and Excellent Sets [18.557423328068122]
  We show that $epsilon$-excellent sets exist for any $epsilon frac12$ in $k$-edge stable graphs in the sense of model theory.<n>We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types.
  arXiv  Detail & Related papers  (2021-08-12T07:33:33Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Boosting Simple Learners [45.09968166110557]
  We focus on two main questions: (i) Complexity: How many weak hypotheses are needed to produce an accurate hypothesis? We design a novel boosting algorithm which circumvents a classical lower bound by Freund and Schapire ('95, '12) We provide an affirmative answer to the second question for well-studied corollary classes, including half-spaces and decision stumps.
  arXiv  Detail & Related papers  (2020-01-31T08:34:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.