CS Paper Radar

Contravariant Universe Subtyping, Formalized, Mechanized

Shengyi Jiang, Jason Z. S. Hu

cs.PL ·submitted 2026-10-10 13:58 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A General Construction of Strict Models in HoTT

cs.LO cs.PLmath.CT ·2026-10-20 ·Niyousha Najmaei, Niels van der Weide
similarity 0.73
Abstract

Homotopy type theory (HoTT) provides a natural setting for studying the metatheory of type theory, as it comes with additional extensionality principles compared to ordinary Martin-Löf type theory. In particular, it is especially suitable for developing semantics of type theory, where one distinguishes two kinds of models: strict models, which give us sound interpretations, and pseudomodels. Pseudomodels are useful as they occur prevalently and can be turned into strict models by constructions called strictifications. However, the commonly used strictifications do not translate well to HoTT, as they require assumptions that are generally not satisfied by concrete examples of models. We show how to carry out the universe model construction, due to Voevodsky, in HoTT. Under this construction, every pseudomodel together with a universe type closed under enough type formers gives rise to a strict model. We also show how to interpret type formers in the resulting model assuming that the universe is closed under them. Finally, we demonstrate that this construction generalises existing instances of strict set models in the literature, and we apply it to more examples, yielding presheaf models and assembly models of type theory in HoTT. Our results are formalised in Rocq using the UniMath library.

0.27

Typed Knowledge over Constructive Institutions: A Proof-Relevant Type Theory for Verified Science

cs.LO cs.AIcs.CL ·2026-11-11 ·Hans-Martin Will
theory similarity 0.71
Abstract

Mathematical proof assistants such as Coq, Agda, and Lean 4 build proof irrelevance into definitional conversion ($p \equiv q$ for $p, q : P$ with $P : Prop$), erasing which derivation established a theorem. While natural for mathematics over fixed axioms, judgmental proof irrelevance is incompatible with verified scientific stores, which must inspect and compare independent derivations of a claim to assess consilience and compute counterfactual retractions when an assay, reagent, or model is invalidated. Moreover, combining definitional proof irrelevance with subsingleton elimination breaks normalization and makes algorithmic conversion non-transitive. We present the type-theoretic and institutional foundations of Eigenius, a verified knowledge substrate for science. First, we formulate a dependent kernel with cumulative universes ($Prop, Set, Type_k$), impredicative $Prop$, inductive families with index-forced subsingleton elimination, and intensional identity types, where definitional equality $\equiv$ is untyped joinability under an orthogonal CRS and proof irrelevance is a witnessed axiom ($irrel : ΠP{:}Prop.\,Πp,q{:}P.\,Id\,P\,p\,q$). Second, we unify universe cumulativity, $Π$-covariant subtyping, and ontology class inclusions in a coercion-free subsumption judgment whose bidirectional fragments ($\mathcal{K}_0, \mathcal{K}_1$) satisfy subject reduction, compile to unification-free checkers ($\mathcal{A}_0, \mathcal{A}_1$), and match declarative typing. Third, we organize external verifiers into a three-level institutional hierarchy with explicit axiom policies (Adopt, Discharge, Relativize), internalize a justification logic with Why-provenance support $supp(j,P)$, and embed Cooper's Type Theory with Records (TTR) for open-world knowledge graphs. Finally, we prove consistency in Grothendieck universes and mechanize the metatheory in Lean 4 with zero sorry axioms.

0.10

Typed Knowledge over Constructive Institutions

cs.LO cs.AIcs.DB ·2026-11-05 ·Hans-Martin Will
publishedtheory similarity 0.70
Abstract

Type theories designed for mathematics or program verification need only that a proposition holds; proof irrelevance in conversion erases, at the kernel level, how a claim was established. A persistent knowledge store, by contrast, must retain that record: who established a claim, by which derivation or external tool, and under which assumptions. This volume presents the theory of Eigenius---a store of typed knowledge over constructive institutions---and develops its metatheory from that requirement. The kernel theory is a dependent type theory with cumulative universes, an impredicative universe of propositions, inductive families, and an intensional identity type. Proof irrelevance is an axiom with an explicit witness rather than a conversion rule, so proofs of a proposition are provably equal yet remain distinct terms. Definitional equality is joinability under an orthogonal rewriting system---confluent, injective on type formers, and decidable by a type-free test---while a separate subsumption judgment covers universe cumulativity, codomain-covariant function types, and declared class inclusions. We prove consistency via a set-theoretic model; develop a justification logic over the kernel's propositions to track evidence and support; organize environments as an institution so that store extensions are signature morphisms and external verdicts enter via comorphisms; formulate a typed knowledge-graph theory with records, classes, and refinements; and prove the correctness of conversion, normalization by evaluation, and bidirectional type checking relative to termination. A Lean 4 formalization accompanies the volume.

0.45

Typechecking without Minimum Types: Finite Bases and Backward Checking for $F_{<:}^{\top}$

cs.PL ·2026-10-14 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.70
Abstract · 44 pages, 8 figures, 2 tables. Includes appendices

System $F_{<:}^{\top}$ has decidable subtyping but lacks minimum types. We prove that typechecking is decidable for arbitrary explicitly annotated terms with unrestricted subsumption. The difficulty is that type abstraction uses a variable's declared bound to type its body, while quantified subtyping forgets that bound. We construct finite covers that preserve all required subtype comparisons across this change of context. These covers yield a compositional finite typing basis and a decision procedure. We then derive a backward checker that propagates acceptable targets without constructing the complete typing basis. Rectangularity of typing families gives a uniform elimination domain while retaining every result type, even when the canonical type is not least. Finite inverse families transport targets through type substitution. The same inverse specification recovers bound forgetting and yields finite type-avoidance families. Both typechecking procedures are total Rocq functions proved equivalent to the original typing judgment. For a separate symbolic word-RAM realization, we prove a quartic worst-case work bound. We measure family representation sizes and comparison storage in independent OCaml prototypes on synthetic checking judgments.

0.25

Internal Languages for Thin Epsilon-Hyperdoctrines: Soundness, Completeness, and Rocq Formalization

cs.LO math.LOmath.CT ·2026-10-10 ·Zoltán Gábor Molnár, Csaba Tóth
code/data similarity 0.65
Abstract · 41 pages, 1 figure. Rocq formalization: https://github.com/mozow01/HyperLogic

We present a typed proof-term calculus for intuitionistic intensional first-order logic with Hilbert's epsilon-operator and prove its soundness and completeness with respect to hyperdoctrinal models with thin bicartesian closed setoid categories (BiCCCs) as fibres and formula-indexed witness selections. The calculus provides an explicit internal language for these epsilon-hyperdoctrines: for each fixed typed signature, its syntactic term model is initial for syntax-indexed, interpretation-preserving model morphisms, with uniqueness up to setoid equality. The nested epsilon syntax is organized by a well-founded dependency relation on formula labels. Concrete countermodels exhibit failure of excluded middle and show that formula conversion need not identify the selected witnesses. We also compare the full calculus with its epsilon-free and epsilon-only fragments. The principal constructions and metatheorems are formalized in Rocq. With setoid BiCCCs, proof irrelevance is a choice of equality, not the erasure of proofs: the proofs and their categorical operations remain available as the basis for a future proof-relevant categorical semantics.

0.43

CIRT: Calculus of Inductive Refinement Types

cs.PL ·2026-11-16 ·Alessio Ferrarini, Niki Vazou, G. A. Kavvos
publishedhot direction similarity 0.64
Abstract · Extended version of the POPL 2027 paper

Refinement types are a powerful mechanism for statically verifying properties of programs. They have been successfully integrated into practical languages such as Haskell, Scala, and Rust. However, their metatheory is not yet fully understood. In this paper we present the first semantic model for a refinement type system that supports the full feature combination of subtyping, SMT-style equality, impredicative polymorphism, and (stratified) inductive types. Interactions between these features have led to inconsistencies in the past, and existing formalizations of refinement type systems omit at least one of them. We present a realizability model based on partial equivalence relations (PERs) over a Scott domain, which overcomes these obstacles. We use our model to prove the consistency of a core refinement type system and to give a semantic account of the annotation-independence property of refinement types. Our semantics uses two interpretations: a refined one, which interprets types and their refinements as PERs; and an unrefined one, consisting of complete uniform PERs with a bottom element (CUPERs), which models computational behaviour independently of refinements. We extend the model to positive and stratified inductive types, showing that both are consistent in the presence of impredicativity.

0.51

Theorem prover Arend

cs.LO cs.AI ·2026-10-19 ·Fedor Part, Valery Isaev, Sergey Sinchuk
theory similarity 0.63
Abstract

This paper is an exposition of the theorem prover Arend developed at JetBrains Research. Arend language has been designed to facilitate the formalization of mathematics within the framework of univalent foundations and with the focus on constructive mathematics. It is based on a variant of homotopy type theory with cubical syntax that is more closely aligned with Martin-Löf Type Theory (MLTT) than fully computational cubical type theories, while still retaining some of their computational properties useful in practice. Among the most notable features of the Arend language is its powerful system of classes and records supporting subsumptive subtyping, partial implementations and anonymous extensions, which provides extensive flexibility for constructing hierarchies of definitions. Formalization in Arend is streamlined by the IntelliJ Arend plugin, which transforms IntelliJ IDEA into a full-fledged integrated development environment (IDE) for the Arend language. The main Arend library arend-lib includes formalizations in constructive algebra, topology and synthetic homotopy theory.

0.25

A sound pure type system with ranks as sorts and Type-in-Type

cs.LO math.LO ·2026-10-18 ·Pavel Sokolov, Alexander Kuklev
code/data similarity 0.62
Abstract · 28 pages, 3 figures, supplementary material to be found at http://github.com/TurtlePU/pts-rk

We present a dependently typed pure type system that contains a circular axiom $s : s$ for a certain sort $s$ and is nonetheless strongly normalizing. Girard's paradox is avoided because our sorts are not closed under a $Π$-former: function types are placed in sorts according to their rank. Turns out that this system has a unique set of characteristics: it has similar normalization behaviour as STLC (so complexity of normalization is TOWER-complete) while at the same time allowing non-uniform representation of arbitrary elementary recursive functions; furthermore, it has a nontrivial set-theoretical model in ZF+GCH and allows to carry out nontrivial proof developments. Base normalization proof is surprisingly simple (modulo general metatheoretical properties of pure type systems) and has been fully formalized in vanilla Rocq (formerly Coq) without additional axioms.

0.30