The Bridge That Only Holds the Finite ✛

Original: "On Strong Structural Completeness of Varieties and Quasivarieties"
arXiv:2607.01271 · 2026-06-30 · CC BY 4.0 · 3 min
A rule's admissibility doesn't guarantee its derivability, and for infinite rules, this chasm is often unbridgeable.

In the world of logic, there is a bridge. It spans the chasm between a rule's admissibility and its derivability from axioms. As long as rules involve only a finite number of premises, the bridge holds firm — for classical logic, anything that doesn't violate truth is already contained in the syntax. But add infinite premises, and the supports start to tremble. The bridge, alas, is not all-powerful.

Structural completeness is a property of a logical system where any admissible rule (one that doesn't add new theorems) can be derived from the axioms. Introduced by W. Pogorzelski in 1971, it has served as a touchstone for many non-classical logics. Intuitionistic logic, for instance, is not structurally complete: there are rules that preserve truth across all Heyting models but are not derivable from the axioms. Yet for some of its fragments — Dummett's logic (LC) and Medvedev's logic (ML)—the bridge carries the finite traffic.

A Heyting algebra of order ω+2 is merely a countable chain with two extra elements on top. A microscopic difference from an infinite chain, yet it's exactly what breaks the derivability of an infinite rule.

Trouble arrives when infinite sets of premises are allowed. The property called κ-structural completeness (where κ is a cardinal capping the number of premises and variables) turns out to be exceedingly fragile. The new work proves: if a congruence-distributive variety of finite type is generated by finite algebras, then for any κ > ω, κ-structural completeness is equivalent to tabularity — generation by a single finite algebra. In other words, the bridge holds only when the entire universe fits into a finite table. Logics LC and ML, whose model classes contain infinite subdirectly irreducible algebras, fail this test. An admissible infinite rule (for instance, a bounding ω-quasi-equation) cannot be derived from a finite basis.

The technique for constructing such counterexamples is elegant: for each pair of distinct elements of the algebra, a condition is introduced linking them to a distinguished pair from the monolith. If the algebra is finite, all conditions hold, and the conclusion is forced. For infinite algebras, a refuting valuation is found. This method generalizes the classic Jankov technique and relies on characteristic κ-quasi-equations for subdirectly irreducible algebras, which act as atoms in the structure of the variety.

The bridge of logic, it turns out, is a structure for finite worlds. Infinity, invading the rules, sends it crashing into the chasm between syntax and semantics. This discovery is more than a curiosity: it ties structural completeness to deep questions of finite axiomatizability and decidability. On the horizon: axiomatizing strongly complete fragments of intuitionistic logic, searching for optimal bases, and clarifying the fine line where finitary consequences transition into non-finitary ones. The bridge will endure only if we remain on the shore of the finite.

A Heyting algebra of order ω+2 looks like a countable chain with two extra elements on top. That microscopic difference is enough to make an infinite rule underivable.

\{ (x_j \leftrightarrow x_k) \to z \approx (x_j \leftrightarrow x_k) \to w \mid 0 \le j < k < \omega \} \Rightarrow z\approx w
This rule is true on all finite Heyting algebras but is refuted on the countable algebra of order ω+2.
Scientists
Claude Shannon
Concepts
quasicrystal