CS Paper Radar

Higher Tripos Theory

Yoshihiro Maruyama

cs.LO ·submitted 2026-10-19 18:59 UTC · v1

Abstract

Tripos theory constructs categorical models of higher-order logic from indexed logical data. We develop higher tripos theory and higher tripos-to-topos construction recovering the classical construction on zero-types through a covering criterion. The higher tripos-to-topos construction yields elementary $\infty$-toposes with closed bounded hierarchies of univalent universes, thus establishing a logical adjunction between $\infty$-triposes and elementary $\infty$-toposes with univalent universes. We also construct a logically conservative higher completion of regular $1$-categories with weak section families and a finite-limit-closed projective cover. This completion preserves original maps, predicates, and existing dependent products, and gives criteria for extending interpretations while preserving logical structure. With strongly inaccessible size bounds, Kleene assemblies instantiate the construction, producing a cumulative hierarchy of univalent universes that classifies every family in the completion and recovering the effective topos as the category of zero-types. We then establish an arithmetical completeness result: for a uniformly computably presented family, the numerical index set for identity with a fixed classifier code is $Π^0_2$-complete. We also construct two inequivalent univalent classifiers with the same global homotopy type: every internal map from one to the natural-number object is constant, whereas the other admits a nonconstant such map. These reconstruction, preservation, and computability results contribute to the higher effective-topos program of Awodey-Emmenegger and Anel-Awodey-Barton.

Closest papers

Nearest neighbours by meaning across the whole index.

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.62
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

Compact totally separated types

cs.LO math.LOmath.GN ·2026-09-09 ·Martín Hötzel Escardó
similarity 0.59
Abstract · 82 pages. v3 adds dedication to Gordon Plotkin on the occasion of his 80th birthday + several improvements. The Agda companion is that of Ty…

Perhaps surprisingly, there are infinite types that can be exhaustively searched mechanically in finite time. We use ideas from topology to build plenty of them, referring to searchable types as compact types, and we use ordinals to measure their logical complexity. We consider two systems of ordinal notations under which a single notation denotes both a discrete ordinal and a compact one, with an embedding of the former into the latter whose image has empty complement. A boolean valued function decides which points in the image of the embedding are isolated and which are topological limit points. The first system consists of the traditional Brouwer codes and the second is an inductive-recursive universe generalizing them. The discrete ordinals so obtained are trichotomous, and the compact ones have the least element property for complemented subsets, but these two desirable properties cannot be fulfilled simultaneously in a constructive setting. The ordinals obtained from Brouwer codes further enjoy a boolean Leibniz principle, which has the notion of total separatedness as its topological counterpart. This extends previous work from Gödel's system T to intensional Martin-Löf type theory with univalent universes, and is formalized in Agda in the TypeTopology repository.

0.32

Contravariant Universe Subtyping, Formalized, Mechanized

cs.PL ·2026-10-10 ·Shengyi Jiang, Jason Z. S. Hu
theory similarity 0.58
Abstract

In a type theory with a cumulative universe hierarchy, \emph{subtyping} is often incorporated to lift lower universe levels to higher ones. In practice, kernels of proof assistants typically implement universe subtyping conservatively: subtyping only propagates covariantly into the output types of $Π$ types, while input types must be equivalent. A full-blown subtyping relation also compares the input types contravariantly. However, contravariant subtyping is not justified by the existing set-theoretic model, and poses challenges in the development of a complete subtyping algorithm. We present \mclttsub, a complete mechanized study of contravariant universe subtyping for a core Martin-Löf type theory (MLTT), built as an extension of the verified McTT kernel in Rocq. We re-establish the syntactic meta-theory and the soundness and completeness properties of the normalization-by-evaluation (NbE) algorithm. To complete the verified pipeline for a type-checker, we give two complete and sound subtyping algorithms. The first one \emph{renormalizes} output types in every $Π$ iteration. Despite a simple completeness proof, this algorithm incurs additional computational cost. The second algorithm hence circumvents this cost by avoiding the renormalization at all. It simply recursively compares two already normalized types structurally. Nevertheless, a completeness proof of this algorithm in a semantic approach requires to reason about normalization in sub-contexts, a capability beyond what the current semantic gadget offers. Instead, we conduct a program equivalence proof through bisimulation relations. Using this technique, we prove that the NbE algorithm returns equal normal forms in sub-contexts up to universe levels, and successfully conclude the completeness of the subtyping algorithm.

0.33

HOL in HOL: mechanized soundness, completeness and consistency, with and without infinity

cs.LO math.LO ·2026-11-13 ·Christoph Benzmüller, Daniel Kirchner
similarity 0.57
Abstract · 23 pages, 1 figure. Formal proof artifacts: Archive of Formal Proofs entries HOL_in_HOL_Deep and HOL_in_HOL_Deep_Infinity_ZFC (Isabelle2026)…

What can a logic certify about a copy of itself? For Church's simple theory of types, formalized as a deep embedding in Isabelle/HOL with Henkin semantics and a natural-deduction calculus, the answer has two tiers. On the first tier, plain Isabelle/HOL certifies the logic without an axiom of infinity, by a standard model with one individual. On the second tier, the logic with a Dedekind-style axiom of infinity is certified only in Isabelle/HOL extended by a large enough set-theoretic universe. Both tiers appear in Harrison's self-verification of HOL Light. What the present formalization adds is Henkin completeness, and with it a semantics that matches the calculus exactly, compactness and model existence on the first tier, and the boundary between the tiers. Comparing two ways of adding infinity to the object logic shows where the boundary lies. One is an infinite domain of individuals, expressed by the first-order sentences "there are at least $n$ individuals", each of which has a finite model; the other is the Dedekind axiom, a single sentence with no finite model, and there the first tier ends. In the calculus the axiom is strictly stronger than the sentences together: it derives each of them, but they do not derive it. The witness is a countable Henkin model in which every sentence holds and the axiom fails, because its function domain is too sparse for an injective, non-surjective self-map. On the second tier, the universe serves one purpose only: to prove the Dedekind axiom consistent. Everything that follows, completeness and even the countable Henkin model of the axiom, is obtained in plain Isabelle/HOL. The universe axiom is Harrison-style, realized in Paulson's ZFC_in_HOL with the domain of every type in $V_{ω+ω}$; with it, full classical higher-order logic with infinity and relational choice is consistent relative to set theory.

0.38

Logics vs doctrines, a mirror symmetry

cs.LO math.CTmath.LO ·2026-10-21 ·Ivan Di Liberti, Umberto Tarantino, Lingyuan Ye
theory similarity 0.57
Abstract · Corrected typo in title and reworded abstract

We study the relationship between doctrines, encoding 2-categories of theories in predicate logic, and fragments of geometric logic, defined through Kan injectivity in the 2-category of topoi. After a brief historical account of the notion of doctrine, we propose our working definition. Our main result then establishes a Galois connection between doctrines and subgeometric logics. This connection suggests a mirror symmetry between the world of doctrines and the world of logics, in which constructions and results on either side admit counterparts on the other. We develop this symmetry through constructions of syntactic categories and classifying topoi in both settings, recovering the familiar examples from categorical logic. We prove paired Diaconescu-type theorems and give symmetric universal characterisations of the two closure operators induced by the Galois connection. Finally, we show that passing from a doctrine to its closure induces a reflection between the corresponding 2-categories of algebras, and we relate this reflection to conceptual completeness.

0.29

Strict Equality in Higher Identity Types: Axioms, Completeness, Decidability

cs.LO ·2026-10-20 ·Keri D'Angelo, Liron Cohen, Luke Serafin, Dexter Kozen
theory similarity 0.56
Abstract

Reasoning about higher identity types uses two equalities, strict equality and equivalence of cells witnessed by a path. Strict equality is a congruence for every operation on cells, but associativity and the identity laws fail for it. Equivalence of cells satisfies those two laws, but it is not a congruence. Representations of higher identity types often conflate equational properties that hold strictly with those that hold only up to a path. We separate the two and axiomatize the former, introducing SEq, an equational theory generated by eleven axioms for strict equality between cells. We prove soundness and completeness for homotopy models, and completeness already over finite CW-complexes. Nine of these axioms form a strongly normalizing rewrite system whose normal forms are unique up to picture equivalence, and the resulting word problem is decidable in exponential time. We also give presheaf models over a cubical base category in which composition arises from a pushout in the base category itself, without requiring Kan filling structure. The same pushout structure provides explicit higher-dimensional witnesses for associativity and the identity laws.

0.38

Completeness and incompleteness of basic matching logic

cs.LO ·2026-08-13 ·Xiaohong Chen, Grigore Rosu
theory similarity 0.56
Abstract

Basic matching logic is matching logic without definedness. Symbols are interpreted as set-valued operations, element variables denote singletons and are bound by $\exists$, and no connective uniformly internalizes totality. For basic matching logic without fixpoints over an arbitrary one-sorted finitary signature, we prove \emph{global completeness} ($Γ\vDash\varphi$ iff $Γ\vdash\varphi$, for arbitrary, possibly infinite $Γ$) and, as a corollary, conservativity of the definedness extension. The proof localizes $Γ$ to a theory $Δ_Γ$ and reduces semantic consequence and derivability to the same local relation: $Γ\vDash\varphi$ iff $Δ_Γ\vDash_\text{loc}\varphi$ iff $Γ\vdash\varphi$. A double-cover construction establishes the semantic equivalence. Least fixpoints destroy effective axiomatizability. Over a signature with one unary and two binary symbols and no constants, validity is not recursively enumerable; hence no sound calculus with a recursively enumerable proof relation is even weakly complete, already for the empty theory and without definedness. The positive result is also sharp in the number of sorts. Global completeness fails with three sorts for a satisfiable $Γ$. Thus the completeness conjecture holds for one sort and fails in general. The negative results arise from sort flow, fixpoint effectivity, and, for hybrid logic, an obstruction to every well-founded calculus whose leaves are hypotheses or valid patterns and whose rules respect localization. This yields a matching-logic-independent dichotomy: the language with state variables bound by $\exists$ and $\forall$ over modalities of arbitrary arity is globally complete without nominals, while no calculus in that well-founded class is globally complete once nominals are added.

0.04

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

cs.FL cs.LO ·2026-10-29 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.56
Abstract · 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555

Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.

0.32