WorksComputer Science
Theorem prover Arend
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.
Introduction
Interactive theorem provers (ITPs) are software tools designed to assist in the creation, verification, and exploration of formal proofs by providing a rigorous framework for encoding and checking logical reasoning. They leverage formal systems, such as type theory or higher-order logic, to provide an interactive environment where users can encode theorems, construct proofs, and validate their correctness with absolute precision. By eliminating human error, ITPs have become invaluable not only in formalizing complex mathematical results but also in verifying the correctness of critical software and hardware systems, bridging the gap between pure mathematics and practical applications. Modern ITPs, such as Rocq [9], Agda [43], Lean [15], and HOL-based systems like Isabelle/HOL [42] and HOL4 [53], are used both to verify algorithms and protocols and to formalize mathematics. Earlier milestones in mathematical formalization include the Four-Color Theorem [17] and the Feit–Thompson Theorem [18], both verified in Rocq.
Recent Lean formalizations include the main theorem on liquid vector spaces (the Liquid Tensor Experiment) [56] and the polynomial Freiman–Ruzsa theorem in characteristic 2 [46]. AI-assisted formalization has also reached large mathematical developments: in September 2026, Anthropic released a complete Lean formalization of Fermat’s Last Theorem, produced with Claude agents and building on Mathlib, the Imperial College FLT project, and the formalization for regular primes [5]. In the same month, OpenAI released Lean formalizations of finite-time blowup for the three-dimensional Navier–Stokes equations with smooth forcing and for the unforced Euler equations [44]. Its October 2026 release contains over 700 mathematical manuscripts, grouped into 372 families; the accompanying repository reports that about 42% of its main results are formalized in Lean [45].
AlphaProof and Aristotle demonstrated automated proof search on formalized Olympiad problems [25, 1]. DeepSeek-Prover-V2 provides open models combining informal reasoning and Lean proof generation [47]. Leanstral targets proof development in existing Lean repositories [41]. In these systems, feedback from the prover guides proof search and revision, and completed proof terms are checked against the formal statements.
Central to many ITPs is dependent type theory, a formalism that unifies programs and proofs within a single framework. Systems like Rocq, Lean and Agda, built upon the Calculus of Inductive Constructions (CIC) or Martin-Löf Type Theory (MLTT) [39], exemplify the power of dependent type theory in encoding rich mathematical structures and reasoning about them formally. Whereas Rocq and Lean (based on CIC) do not particularly favor constructivism (Lean even has the axioms of choice and excluded middle built-in), Agda (based on MLTT) leans more towards constructive mathematics. HOL-based systems, rooted in classical higher-order logic, offer an alternative approach that is more familiar to traditional mathematicians and computer scientists. However, dependent type theories surpass HOL in expressiveness by allowing types to depend on values, enabling constructive reasoning with computational interpretations via term reductions, and unifying proofs and programs within a single framework, capabilities that HOL’s classical framework lacks.
In the early 2000s, the fields of formalized mathematics and dependently typed languages — previously limited mostly to communities of computer scientists and logicians — began to draw significant attention from pure mathematicians. A pivotal moment in this shift was the formulation of Univalent Foundations (UF) of mathematics by Vladimir Voevodsky between 2006 and 2009 [60]. This new approach, inspired by the homotopy semantics of MLTT, interprets types as homotopy types1 rather than as sets [31]. In particular, the equality type is interpreted as the type of paths between and in , for , the type is the type of homotopies between and in , and so on. The homotopy semantics suggested that MLTT can serve as a basis for a formal system where the notion of a homotopy type is taken as primitive instead of the notion of a set. This led to formulation of Homotopy Type Theory (HoTT) as an extension of MLTT with univalence axiom , which allows to identify two equivalent types, and higher inductive types, a certain generalization of inductive types allowing higher path constructors [57 Chapters 2 and 6].
The impact of HoTT/UF on formalization of mathematics is two-fold:
Many standard constructions and theorems in homotopy theory can now be elegantly formalized using HoTT, where homotopy types serve as primitives rather than sets. This method, known as synthetic homotopy theory, utilizes the equality type to encapsulate complex homotopy structures [57 Chapter 8]. Set-theoretic versions of these formalizations tend to be more cumbersome. This synthetic approach not only simplifies the formalization of existing theories but also has the potential to reshape many areas of modern mathematics by adopting a higher categorical perspective over traditional set-theoretic approaches.
HoTT/UF provides a framework for set-theoretic formalization where sets are homotopy types with trivial homotopy structure and propositions are sets with at most one element. One can do formalizations completely confined to this set theory fragment of HoTT. As such a framework HoTT/UF augments MLTT with a fair degree of extensionality:
(a) Quotients can be easily defined in HoTT using higher inductive types [57 Section 6.10]. Meanwhile quotients are notoriously hard to deal with in pure MLTT due to intensionality of equality [35].
(b) Univalence axiom implies propositional and function extensionality: any two equivalent propositions are equal and any two pointwise equal functions are equal [57 Sections 3.3 and 4.9].
(c) Univalence axiom implies structure identity principle: isomorphic structures (such as groups, topological spaces and so on) are equal [57 Section 9.8].
This approach can, in principle, be implemented using an ITP based on MLTT, such as Rocq or Agda2, by merely appending univalence and higher inductive types as axioms devoid of any computational content. However, this severely impairs the computational properties of MLTT, which are crucial for practical formalization efforts. Additionally, there are several other problematic issues stemming from the fact that these ITPs were not originally designed with native support for HoTT/UF. For example, the universe of propositions Prop in Rocq or Agda does not correspond to the type of propositions as defined in HoTT/UF.
Theorem prover Arend. The development of Arend began in 2015 at JetBrains Research with the goal of creating a modern ITP featuring native support for HoTT/UF. Its two principal components are the Arend language, which is based on a variant of MLTT specifically tailored to integrate seamlessly with HoTT/UF, and a suite of tooling provided by the Arend plugin for IntelliJ IDEA [6]. The key components of the Arend ITP are listed below. The language and command-line interface described here are those of Arend 1.12.33.
Type theory. At the core of the type theory of Arend is the homotopy type theory with interval type (HoTT-I) [27, 28], formulated by Valery Isaev in 2014. It consists of two components:
(a) Variant of MLTT with the interval type: a minor, more extensional modification of MLTT that incorporates a primitive type for the interval. The equality type (or path type) is defined in terms of . Function extensionality is derivable and is fully computational in this theory. This setup gives rise to a variant of cubical syntax: -dimensional homotopies in a type are naturally represented in HoTT-I as functions .
(b) Univalence axiom: a form of univalence axiom, which is a built-in axiom with some computational rules.
The native support for HoTT/UF in the type theory of Arend is further amplified by the following extensions of HoTT-I:
(a) Inductive types with conditions. Using the primitive , a path constructor can be defined simply as a constructor with an interval type parameter, or multiple parameters for higher-dimensional homotopies. The only difference with an ordinary constructor is that there could be conditions that dictate how evaluates at the ends of the interval to other constructors: , . In particular, it implies but does not lead to contradictions as in the case of standard inductive types in MLTT, thanks to a modified elimination principle that requires the preservation of conditions. This provides support for higher inductive types and, in particular, quotients with computational behavior [62].
(b) Universes Prop and Set matching h-propositions and h-sets. Arend incorporates an impredicative universe Prop that captures the logic of h-propositions and a predicative hierarchy of universes for h-sets. The universes Prop and Set provide a syntactic framework that facilitates working within the set theory domain, akin to the elementary topos of h-sets, and distinctively delineate the set-level aspect of the type theory from the higher levels, ensuring that set-theoretic formalization is confined strictly to the subtheory prescribed by these universes.
(c) Universes stratified by homotopy level. Alongside predicative universe polymorphism, Arend provides universes of propositions, sets and higher types. A definition can be placed in the appropriate universe using a proof of its homotopy level. In Arend 1.12 homotopy levels are constants, not polymorphic parameters; cumulativity allows a type to be used at a higher homotopy level.
The above outlines the core fragment of Arend’s type theory as it relates to HoTT/UF. Its key properties include:
(a) Computational behavior. Unlike MLTT augmented merely with axioms for univalence and higher inductive types, Arend’s type theory includes a number of computational reduction rules for involved terms, which prove crucial for practical usage. However, it lacks sufficient computational rules to render the theory fully computational: the MLTT property that every closed term of type Nat evaluates to a canonical number does not hold in Arend. The core theory of Arend represents one of the earliest and simplest forms of cubical type theory, in which the interval still functions as an ordinary type. Later cubical type theories make univalence derivable and recover canonicity by adding a language of dimensions and faces together with uniform Kan composition [12, 24]; some Cartesian variants additionally separate fibrant and non-fibrant types [4]. This machinery is substantially more elaborate than the coe/iso interface of HoTT-I; see § 3.5. The type theory of Arend could potentially be adjusted to enhance its computational aspects, but practical experiences in formalization have not demonstrated a significant need for such enhancements.
(b) Constructivity. The type theory of Arend is inherently constructive. In its core theory, the law of excluded middle does not hold, and the axiom of choice is valid only in the form of unique choice. While the axioms of classical logic can be consistently added and utilized in libraries, the main Arend library, arend-lib, is dedicated to constructive mathematics, and no standard metas utilize any classical axioms.
Finally, the type theory of Arend includes the following extensions, which are of significant practical importance for formalization and yet are not present in Rocq, Lean, or Agda:
(a) Records with partial implementations and anonymous extensions. In Arend, type classes and records support multiple inheritance with partial implementations. Specifically, if record extends record , it is possible to implement an arbitrary subset of ’s fields within . For instance, for a field of , its extension may include an expression that specifies a value for . This flexibility blurs the traditional distinction between parameters and fields in classes and records, enabling more versatile hierarchical structure development. Additionally, Arend allows for the creation of records and classes on-the-fly as an anonymous extension, denoted as . This feature facilitates dynamic customization of types without the need to define fully specified new classes or records, thus enhancing modularity and reusability.
(b) Array types. Arend introduces a specialized type for arrays, denoted as Array , where . This type encompasses several concepts including the type of lists of elements of type , the type of vectors of elements of type of fixed length and the type of functions from a finite set of cardinality to . The type Array is a record with fields , len : Nat and at : . The anonymous extension Array describes arrays of various lengths with elements of type , and the extension Array specifies arrays of a fixed length . A crucial feature of the array type in Arend is its computational extensionality: if two arrays of equal length are elementwise computationally identical, then they are considered computationally equivalent as entire structures.
Proof terms. In Arend, proof terms do not need to be fully detailed. Users can take advantage of the “inference of implicit arguments” mechanism, which allows them to omit some arguments in expressions (more concretely, the ones that can be inferred via the “inference of implicit arguments mechanism” built into the Arend type checker). Additionally, users can employ metas such as rewrite to construct particularly complicated parts of expressions. Metas should be seen as “expression-level tactics”, meaning they can be seamlessly interwoven with standard Arend term constructs. In other words, unlike Rocq, Arend does not have separate “proof” and “term” levels – everything (including proofs) in Arend happens on the “term” level.
IntelliJ IDEA plugin. The easiest way to use Arend is through the tooling provided by the Arend plugin for IntelliJ IDEA. IntelliJ IDEA, developed by JetBrains, is a versatile IDE with intelligent code assistance, robust refactoring tools, and seamless integration with languages like Java, Kotlin, and Python. It has a variety of built-in tools for version control, debugging and testing.
Arend plugin supports the following functionality:
(a) Incremental type checking. Under normal circumstances the Arend plugin uses the so-called “on-the-fly” (or smart) mode of type checking. In this mode, the type checker operates in a background thread, automatically reprocessing each code modification made by the user.
(b) Arend Messages tool window. The Arend Messages tool window serves as the primary interactive element in Arend, providing essential insight into proof goals, expected types, and error notifications. While writing terms the user can insert hole expressions {?} for arbitrary subterms, which would introduce goals shown in Arend Messages. This allows for a convenient way of writing proof terms by gradually breaking down the original proof goal into several subgoals.
(c) Editor features. The Arend editor supports a variety of features that greatly simplify working with Arend code such as: auto-completion of identifiers; quick fixes for Arend errors; intention actions such as adding missing clauses in pattern matching; refactorings such as handling consequences of changing signatures of definitions or moving definitions; navigation tools such as Go to Declaration or Find Usages; quick documentation popups supporting LaTeX; parameter hint tooltip which can be invoked in application expressions.
(d) Debugger for metas.
Arend CLI and LLM-assisted formalization. Besides the IDE plugin, Arend provides a command-line interface exposing the type checker and several library retrieval tools. This makes it possible to use Arend together with AI coding agents such as Claude Code; a collection of ready-made agent skills for Arend formalization is also available (see Section 5).
The library arend-lib. The main Arend library arend-lib covers three broad areas. Its main developments are constructive; results using excluded middle or choice are separated into modules that explicitly assume these principles.
Constructive mathematics. This is the main part of the library. The mathematical landscape in the constructive setting is richer than in the classical setting since classically equivalent definitions often become inequivalent constructively.
This part contains the following: schemes via locally ringed locales; principal ideal domains and the proof that they are Smith domains of Krull dimension at most one; splitting fields of polynomials and algebraic closure for countable, decidable fields; constructive forms of the Fundamental Theorem of Algebra, including Richman’s root-multiset construction and algebraic closedness of the algebraic numbers; connection between zero-dimensional and integral extensions; matrices over commutative rings, determinants, characteristic polynomials, Cayley-Hamilton theorem; linear algebra over Smith domains; integral ring extensions; polynomials over one or several variables; Nakayama’s lemma; derivative over topological rings; directed limits for sequences and functions; series and power series; natural, integer, rational, real and complex numbers and various structures on them; categories, functors, adjoint functors, Kan extensions, (co)limits; elementary topoi and Grothendieck topoi; topological spaces, locales, uniform and cover spaces, and their completions.
The main references are the books [40, 36], Richman’s constructive FTA [49], and Isaev’s paper on constructive complete spaces [29].
Synthetic homotopy theory. All of the synthetic homotopy theory of the HoTT Book [57] has been formalized in arend-lib, partly with AI assistance. It includes pointed types, loop spaces and homotopy groups; spheres, suspensions, joins and pushouts; truncations and connectedness; the fundamental group of the circle; the Hopf fibration and long exact sequences; the Freudenthal, van Kampen and Whitehead theorems; Eilenberg–MacLane spaces ; localizations, modalities and the generalized Blakers–Massey theorem (§ 7.2.1).
Computer science. This part includes abstract reduction systems, confluence and termination, higher-order term rewriting with the -calculus as an example, modularity of confluence, and first-order algebraic theories with their models and free models.
Future directions. So far, developments in synthetic homotopy theory in HoTT have been limited. One reason is that types in HoTT are necessarily -groupoids, a special kind of -categories where all morphisms are invertible. This is because equality is symmetric. Attempts to define more general -categorical structures in terms of -groupoids in HoTT have led to the still-open question of definability of (semi-)simplicial types in HoTT[33]. Recently, proposals for directed HoTT [11, 19], where types are -categories, have emerged. A variant of directed HoTT is being developed for Arend; its implementation is currently in the cat branch.4
The structure of this paper. § 2 introduces HoTT-I and Arend’s extensions, explains their use in set-theoretic formalization and synthetic homotopy theory, and compares their computational behavior with other cubical type theories, including open problems concerning additional computation rules. Section 3 presents universe polymorphism, classes and records, and arrays through code examples. Section 4 describes the IntelliJ IDEA plugin’s type checking, editing, navigation and refactoring tools. Section 5 explains how the Arend CLI supports LLM-assisted formalization with Claude Code. § 7 surveys arend-lib, focusing on constructive category theory, topology and algebra, followed by synthetic homotopy theory and further topics.
Underlying type theory of Arend
The type theory of Arend is an extension of the homotopy type theory with interval type (HoTT-I). It is a simple modification of Martin-Löf type theory (MLTT) which allows for native support of homotopy type theory and has certain important advantages over MLTT even for formalisations unrelated to homotopy theory.
Homotopy type theory with interval type
Interval type I: a new primitive which serves as a basis for the definition of equality type . Type I is defined as a data type with two constructors
left : I,right : Iand the elimination principle given by the functioncoe:
The second of these is called regularity: coercion in a family that does not mention the interval variable is the identity. It is referred to by that name below.
Functions from I to a type A can be interpreted as paths in A. In HoTT-I, the equality type is defined as the type of paths , which are maps from I to A with fixed endpoints and :
The standard J-eliminator for equality types in MLTT can be derived from these rules.
Univalence axiom: the function witnessing the principle “isomorphic types are equal” which implies the structure identity principle (see 2.3.3 below). Given types , , mutually inverse functions , and proofs , of and , the function constructs a family of types parameterized by interval , such that and :
Extensions of HoTT-I in Arend
The core type theory of Arend includes a number of extensions of HoTT-I:
Inductive types with conditions. Definitions of inductive types in the core type theory of Arend extend the standard definitions with conditions on constructors. Conditions allow to glue different constructors when evaluated at certain values of parameters. For example, for the type of integers with two constructors and a condition might be . In general a condition on a constructor is almost the same as a definition of a partial function by pattern matching which specifies how evaluates. The most interesting examples of conditions involve pattern matching on the interval (such pattern matching is not allowed for functions): it can be used to glue arbitrary constructors and by means of the constructor with conditions and . This allows to define quotient types and higher inductive types (see 2.3.2 and 2.4 below). The mechanism of inductive types with conditions in Arend has been analysed in the paper [62].
Propositions and sets. Type theory of Arend contains the type – an impredicative universe of all propositions, and a predicative hierarchy of universes of sets . Universes and constitute a fragment of the type theory which represents a variant of set theory and provide a framework for conventional set-theoretic formalization.
The following properties characterize the logic and the universe :
(a) The operations , , , as well as the constants , are defined as usual in propositions-as-types logic, corresponding to , , , and the types , , respectively. Operations , can be defined as inductive types or via , as and , where is an inductive type (see (2e) below). (b) Prop is impredicative and the logic of Prop is by default constructive: the law of excluded middle and general axiom of choice do not hold. Propositions are sets: and .
(c) Propositions satisfy propositional proof irrelevance . This is one of the main properties that distinguish propositions from other types: a proposition conveys no more information than a truth value.
(d) Propositional extensionality holds for Prop: if for then . This is a consequence of proof irrelevance and the univalence axiom.
(e) The universe Prop defines the syntactic notion of proposition: propositions are types in Prop and the main property of types in Prop is proof irrelevance. But there is also a more semantic notion of an h-proposition, which is any type satisfying proof irrelevance, namely such that is provable.
In the type theory of Arend any definition of an inductive type , which is an h-proposition, can be supplemented with a proof in which case gets placed in Prop and becomes a proposition syntactically. This applies also to record types and there are analogous extensions for function definitions which ensure, for example, that is in Prop. This mechanism allows to define the predicate 5 as inductive type with constructors and with conditions , and an obvious proof .
Another key mechanism: for an inductive type in Prop and an h-proposition functions can be defined by simplified elimination where constructors containing parameters of type are omitted. This implies for any : with this elimination one can construct a function which is inverse to the obvious function and prove that they are mutually inverse.
As an alternative to the mechanism for placement of inductive types with in Prop Arend supports a mechanism for marking inductive definitions as truncated definitions in Prop and limiting definitions of functions by elimination only to h-propositions . For example, propositions and can be defined directly as truncated inductive types rather than via nonempty. We call h-prop elimination this kind of elimination from truncated inductive types in Prop. If is not already inferred to lie in Prop, the eliminator includes a proof .
In the presence of univalence elimination from truncated definitions in Prop cannot be extended to all types. Full, unrestricted elimination from propositions to arbitrary types would imply the existence of a global choice operator , which is inconsistent with the univalence axiom [50 Corollary 17.5.3]. Moreover propositional proof irrelevance for cannot be strengthened to the computational one , . Although it is probably consistent, it causes some issues in a type theory with h-prop elimination.
The difference from Rocq and Lean can be illustrated by elimination from . Given and a proof that any two elements of are equal, Arend defines
The proof that is an h-proposition suffices; need not already be classified in Prop. In Rocq and Lean, the ordinary eliminator for the corresponding proposition expressing nonemptiness requires a target in Prop. Supplying a proof that all elements of a target are equal does not change this restriction.
Rocq and Lean do allow elimination into arbitrary types from certain other inductive propositions: for example, a proof of falsehood gives an element of any type, and a proof of equality allows transport between types. These exceptions depend on the form of the source inductive definition; they do not apply to nonemptiness of an arbitrary type . In Arend, the restriction to h-propositional targets applies to definitions declared truncated. An ordinary inductive definition placed in Prop using a proof of its homotopy level retains its ordinary eliminator. See Section 3 for examples in Arend language.
(f) As a consequence of h-prop elimination holds a weak form of the axiom of choice: the principle of unique choice UC. The principle UC essentially says that, for sets and a proposition-valued relation , if , where means “exists and unique”, then . Here existential quantifiers are propositionally truncated. h-prop elimination is a stronger form of UC, which, in particular, defines functions which compute at constructors. This implies, for example, that every bijection has an inverse with computational properties.
The axiom of choice for sets AC obtained by dropping uniqueness in this formulation is not provable in Arend, but can be consistently assumed. The restriction to sets matters when comparing this statement with choice principles for higher types [57 Section 3.8].
(g) h-prop elimination and the univalence axiom imply that Prop is isomorphic to totalities of h-propositions: for all . It follows from provability of using h-prop elimination and the univalence axiom. Moreover, with LEM the universe Prop is isomorphic to Bool.
To sum up, the logic of Arend provides a basis for either constructive or classical univalent formalization of mathematics where:
(a) Univalence axiom and the structure identity principle hold.
(b) The principle of unique choice UC holds in the computational form of h-prop elimination for Prop.
(c) The axiom of choice AC and the law of excluded middle LEM are not accepted in arend-lib, but can be consistently assumed in some formalizations.
Universes Set are characterized by the following properties:
For and the type lies in Prop. In particular, sets satisfy uniqueness of identity proofs .
, : the universe of sets is a 1-type, not itself a set. Here the second parameter denotes the homotopy level, as explained below. There is also a hierarchy of universes of all types satisfying .
As in the case of propositions, there is a semantic notion of an h-set, which is any type for which is provable. And similarly to propositions, definitions with a proof of can be placed in Set, and the elimination for truncated inductive types in Set is confined to h-sets (h-set elimination). This implies .
Homotopy levels
Sets in Arend are types such that their equality type is a proposition. This construction can be iterated by considering 1-types such that their equality type is a set, 2-types such that their equality type is a 1-type and so on. This leads to the notion of a homotopy level of a type: we say that propositions are of homotopy level and a type is of homotopy level if its equality type is of homotopy level . We say that a type is of homotopy level if no such exists.
In Arend a universe is parameterized by a homotopy level in addition to the usual predicative level ; we write for the universe of -types of predicative level . As in the case of Prop and Set there is a universe placement mechanism for definitions, -type elimination and an equivalence between and the type of all semantic -types: .
The two parameters are, however, not on the same footing. Definitions are polymorphic in the predicative level: such a level can be a variable, and level expressions are built from level variables, 0, suc and max. The homotopy level, by contrast, is always a constant — either , or a natural number, or . So although there is a universe Type for each , there is no polymorphism over : a definition cannot be abstracted over a homotopy level the way it is over a predicative one. Earlier versions of Arend did admit an implicit homotopy level parameter alongside the predicative one; this has since been dropped.
Subtyping and dependent record types
For some pairs of types in Arend holds (subsumptive subtyping), which means that the typing relation implies the typing relation . Subtyping is involved in two mechanisms: in cumulativity of the hierarchy of universes and, more significantly, in the system of dependent record types.
Cumulativity means that a type can be used at larger predicative and homotopy levels: Type Type when and . In particular,
Dependent record types provide a basis for working with hierarchies of mathematical structures by means of bundling data and creating new structures as extensions or specifications of other structures. Record types (where may depend on ) are similar to sigma-types: their elements are also dependent tuples . Variables are called the fields of . The difference from sigma-types is that a new record type can be formed as an extension of in which case becomes a subtype of . Record type can extend with new fields or with manifest fields of the form , , which assign a specific value for fields of . If contains then its objects would be tuples where -th component is computationally equal to .
Some of the properties of record types:
(a) Record type extensions model the concept of inheritance in programming languages. In Arend multiple inheritance is allowed: a record type can be an extension and therefore a subtype of several record types. Multiple inheritance together with manifest fields provide a flexible framework for grouping data associated to mathematical objects using sharing, extensions and subtyping.
(b) Record extensions consisting of just manifest fields can be anonymous. This implies that records’ fields also behave like parameters: if is a record, the application is the anonymous extension .
(c) If is an extension of and is a field of then the type of the field can be overridden in and changed to a subtype : , .
For example, a record MonoidHom can have fields Dom, Codom : Monoid. An extension GroupHom can override these fields with type Group, since Group extends Monoid. This is distinct from the coercion that sends a group or monoid record to its underlying set.
(d) Although propositions in Arend are not computationally proof irrelevant in general, a form of computational proof irrelevance holds for propositions inside record types. Namely, some fields whose type is a proposition can be declared properties in which case their value will be irrelevant in comparing elements of records.
For example, a record Cat for categories would have data fields for objects, morphisms, identity morphism and composition and property fields for associativity of composition and neutrality of identity morphism. One consequence of this would be that if then is computationally equal to .
Arrays
Arend has built-in type Array of arrays which subsumes the standard inductive type List of lists of varying length, the standard indexed inductive type Vec of lists of fixed length and the type of functions , where is the type corresponding to the finite set . The type Array is a special kind of record with the fields: for elements, for length and an indexing function at : . Types List and Vec can be defined via Array as anonymous extensions: List , Vec . The type is obviously isomorphic to the type of functions , but it satisfies additional computational equalities which is the central motivation for introducing :
There is also dependent version DArray with and .
We now explain what these modifications bring to MLTT and how it affects formalisation in general, not necessarily in the context of homotopy theory. We then outline some nice properties of the type theory of Arend specific for formalisations in homotopy theory.
Properties of the theory of Arend relevant for set-theoretic formalization
Function extensionality
Function extensionality principle says that if two functions are pointwise equal then they are equal:
This principle cannot be proven in MLTT and has to be added as an axiom. It is known to be provable from univalence axiom in HoTT, but the proof is not completely straightforward ([57], Section 4.9). Definition of equality type in HoTT-I allows to define FunExt very easily:
Moreover, this definition of FunExt is well behaved computationally. As a map between pointwise equalities to equalities between functions FunExt admits an obvious inverse such that composition on both sides is computationally the identity.
Derivation of FunExt in cubical type theories is also elementary (for example, in Cubical Agda [58]). In Lean FunExt is derived using built-in quotient primitives, including the quotient soundness axiom.
Quotient types
Given a set and a relation 6 the quotient type is the set obtained from by identifying all such that holds. More formally can be characterised as a set satisfying the following properties:
There is a function .
(Universal property) For any set any function respecting (that is such that whenever ) factorizes uniquely through : there exists a unique such that . The map corresponds to an eliminator for .
In the category of sets is the coequalizer of two projections . The concept of quotient type is well known to be hard to deal with in MLTT due to intensionality of equality [35, 23, 2]. Although quotient types can be defined in MLTT in some cases (say, for rationals) in general they are not definable in MLTT (say, for Cauchy reals)[35]. We briefly outline some of the proposed ways to introduce arbitrary quotient types:
Setoids. Instead of working with types one can work with types coupled with an equivalence relation [23, 2, 7]. If we think of types as sets, this corresponds to replacing sets with setoids. Quotient type would correspond to quotient setoid, which is defined simply by taking the equivalence relation generated by the original relation and the additional identifications. Rocq, for example, has a well developed setoid infrastructure that helps to adopt this approach. However, this approach is rather impractical because of all the complications of working with a custom term rewriting system for equivalence relations (as opposed to built-in one for the equality type).
Axioms for existence of quotient types. Quotient types can be introduced purely axiomatically by simply assuming the statement phrasing that there exists a type satisfying the universal property. Such existence axioms alone supply no reduction rules for the quotient eliminator. Computations using the postulated operations can therefore become stuck, even when the axioms are logically constructive. Computational behaviour depends on the additional rules: Lean, for example, has a built-in reduction for lifting a function and applying it to a quotient constructor.
Quotients of h-sets in the logic of h-propositions in HoTT. Quotients can be defined for h-sets using subuniverse hProp of h-propositions and univalence (or extensionality for functions and h-propositions): if is hProp-valued equivalence relation on an h-set hSet, then can be defined as the type of all hProp that define an equivalence class of in . This definition raises the universe level which can be dealt with by means of resizing rules ([57], Section 6.10).
Higher inductive types. An appealing perspective on dealing with constructs like quotient types systematically was brought by HoTT in the form of a mechanism to introduce equalities in definitions of inductive types. Definitions of higher inductive types (HITs) in HoTT apart from ordinary constructors contain constructors for equalities called path constructors, and the modified elimination principle ensures the universal property (see § 3.4 below and Chapter § 7 in [57]).
First, this allows to define the operation of set-truncation for types Type which produces h-set by trivializing the structure of the identity type on and enforces UIP on . The h-set can be defined as the higher inductive type with ordinary constructor and path constructor .
Second, for an h-set and hProp-valued relation the quotient h-set can be defined as where is the higher inductive type with ordinary constructor and path constructor . To define , one supplies a function and paths for . The rules are
where is the action of on paths. In the presentation of HITs in the HoTT Book [57], § 7.2, the first equation is judgemental and the second is propositional. Thus the second equation can be used in proofs, but does not itself reduce the expression on its left.
The type theory of Arend allows for particularly convenient definitions following the last two approaches. Definition (3) can be stated in Arend with the universe Prop in place of hProp and Set in place of hSet. Since Prop in Arend is impredicative, resizing rules are unnecessary in this case. Implementing this construction in another prover requires checking its universe and elimination rules. In particular, elimination into an arbitrary type proved to be an h-proposition is not generally supplied by the empty and singleton elimination exceptions of Rocq and Lean.
Arend also improves on the approach (4). It turns HITs into ordinary inductive types with conditions. Instead of the path constructor for we can define an ordinary constructor with conditions and . Moreover instead of using set-truncation HIT Arend allows to simply declare to be a truncated inductive type in Set with elimination restricted to h-sets. These constructor and eliminator equations do not give general computation rules for coercion through the quotient type; the limitation is discussed in Section 2.5. The same mechanism also allows quotients to be presented directly as inductive types with conditions, as in the case of integers (see the beginning of Section 2.2) or the type of univariate polynomials in arend-lib (see Section 6.1.3).
Isomorphic types are equal
One important property of MLTT is that it cannot distinguish between isomorphic types 8. Namely, if and are isomorphic types and is a property of types then and the negation of cannot be simultaneously proven in MLTT. This can be shown by constructing a homotopical model of MLTT where existence of isomorphism between and implies existence of elements in [31].
In fact, a stronger statement holds for MLTT: all properties of types are stable under isomorphism. Namely, for any predicate on types which is defined also for outside of universes9 there is a function . This is called external univalence - a metatheoretic property of theories capturing preservation of isomorphisms. It is metatheoretic the construction of is dependent on the structure of and is not uniform. External univalence can be shown using homotopical inverse diagram construction [32] or univalent parametricity translation [55]. It has been proven in the general setting of second-order generalized algebraic theories in [10] which implies that it holds for any type theory with identity types and any standard choice of type formers like -, -types, universes, inductive types and so on.
It is thus natural to avoid the routine of proving stability for each particular and pass to an extension or a modification of MLTT where univalence holds internally or more precisely where holds.
The simplest minimal such extension of MLTT would be just MLTT with added as an axiom. This is essentially the way univalence is introduced to HoTT-I: an isomorphism between types can be converted to equality between types by built-in function . A small advantage of HoTT-I over MLTT with the axiom is the presence of built-in computational rules for iso that make the use of univalence a bit more convenient.
Example: types of unary and binary natural numbers. A simple classical example of isomorphic types, where a mechanism for transferring proofs of properties from one to the other would be desirable, is given by different representations of natural numbers: unary and binary. This example is rather relevant for the formal verification: binary numbers are computationally efficient and are used in formal descriptions of algorithms whereas unary numbers are easier to reason about.
Unary natural numbers are defined as the standard inductive type Nat with constructors and . This definition is convenient for proving properties of natural numbers via standard induction but is computationally inefficient.
The type of natural numbers represented as binary strings without trailing zeros can be defined as an inductive type with constructors and where is an inductive type with constructors and . For example, the binary number 1010 is represented as the term . In contrast to the unary definition Nat above, this definition of natural numbers is computationally efficient, but proving even basic properties of and defined in computationally efficient way becomes rather involved.
Problems such as enabling Nat to be used for proving properties of have been central to a long line of research on mechanisms for transferring proofs of theorems between isomorphic types [38, 13, 63]. At the heart of many approaches lies the concept of parametricity [48] which is closely tied to developments on free theorems about observational equivalences [61], data refinements for free [13] and proofs for free [8].
Recent work [55] demonstrates how certain limitations of parametricity-based approaches can be addressed by combining parametricity and univalence. Parametricity enables a white-box translation of definitions and proofs of theorems between equivalent types by leveraging the internal structure of the terms being translated and their types. In contrast, univalence provides a universally applicable black-box translation through transport along equalities, such as for . Each approach, however, has its limitations when used in isolation.
For instance, transporting a function to does not by itself preserve its complexity: converting between representations can be costly, and transport must itself compute. Induction on remains available, but the transported function need not have useful judgemental equations for that induction. Parametric transport can instead use correspondences between chosen implementations, such as and . In dependent types this must also account for type-level computation: a family defined using the eliminator for satisfies computational rules which would be lost for its analogue for and that would create problems when translating functions defined using eliminator for .
As suggested in [55], these problems can be addressed by devising combined approach of univalent parametricity, which intertwines white-box and black-box translations in a complementary and effective manner.
Isomorphic structures. MLTT likewise cannot distinguish between various isomorphic structures on top of types such as groups, rings, topological spaces and so on. In other words MLTT cannot distinguish between isomorphic objects in various categories admitting a natural forgetful functor to the category of sets. And typically the function can be used to derive equality of isomorphic objects and freely transfer properties of the one to properties of the other. This is known as the structure identity principle in Univalent Foundations [57], Section 9.8.
Logic and set theory
For a fixed predicative level , impredicative and univalence make the category of sets in an elementary topos. With LEM and choice for sets it satisfies Lawvere’s Elementary Theory of the Category of Sets [57], Section 10.1. Interpretations of material set theories require a separate construction of sets and membership: the cumulative hierarchy of the HoTT Book gives a model of ZFC with choice [57], Section 10.5. Its construction uses a universe and a higher inductive type, with in a larger universe. Interpretations of CZF use different constructions and additional hypotheses [16]; they do not follow merely from the elementary-topos statement.
Hierarchies of structures
Formalization of mathematics crucially relies on mechanisms for grouping data and properties of mathematical structures. In languages based on variants of MLTT this is often done by means of dependent record types supplemented with typeclasses and instance inference mechanism. Dependent record types and typeclasses in such languages are closely related to module systems and typeclasses in functional programming languages [34, 21, 20]. Here we focus on record types since the mechanism of typeclasses does not require any extensions of the core type theory, we discuss it in more detail in § 4.2.
Record types can be used, for example, to define the type of monoids as follows:
Elements are essentially tuples containing as data the carrier set , monoid identity and binary operation together with proofs that this data defines a monoid structure on .
The challenges that arise when designing a dependently typed language with record types include the support of multiple inheritance, subtyping, partial implementations and sharing. For example, a field is both a commutative local ring and a GCD domain so it is natural to define the type Field of fields as an extension of LocalCRing and GCDDomain which requires multiple inheritance. Apart from making Field inherit the data and properties of LocalCRing and GCDDomain it involves making Field a subtype of the two. Finally, in the constructive setting definition of a domain contains apartness predicate as part of data10 which in Field can be defined as invertibility11 and this requires partial implementations. The tightness of the apartness relation then exactly says that non-invertible elements equal to 0 and is left as unimplemented field. We discuss this example in more detail in § 4.2.
In Arend these challenges are addressed both at the level of the core type theory and at a higher level. As described in § 2 the type theory of Arend has extensions for subsumptive subtyping and manifest fields for record types where the latter provides a mechanism for partial implementations and sharing. From theoretical point of view such extensions of MLTT were studied, for example, in [14]. There are also implementations: manifest fields are supported, for example, by the proof assistant Matita [51]. These extensions are extremely useful for working with hierarchies of so-called bundled or semi-bundled definitions where all or almost all operational data of a mathematical structure and its defining predicates are placed in fields of a record (and the rest of data is in parameters). For example, the definition of Monoid above is fully bundled, its less bundled variants would be records with parameters , , . Definitions like Is_Monoid are typically classified as unbundled since all its data components are parameters. Unbundled definitions allow to reduce partial implementations to usual applications, though at the price of losing key benefits of record types such as being a type of tuples with named projections. Still with the mechanism of typeclasses and instance inference unbundled approach can be made viable as suggested, for example, in [54].
Without manifest fields possibilities for defining record extensions become much more limited even in unbundled case. For example, manifest fields allow to define record Ring as an extension of Semiring. Some of defining properties of Semiring, namely and , become derivable in Ring and therefore these fields should be implemented (see also § 4.2). Without manifest fields, in bundled or unbundled case, typically one has to define more of the small, atomic records and combine them to define various composite records, the option of constructing composite records as specializations of other composite records becomes unavailable.
Arend language has numerous high level constructs on top of record types which we mainly discuss in § 4.2: typeclasses, coercive subtyping, anonymous extensions and so on. Parameters of records is also a high level construct in Arend: the mechanism of manifest fields allows to translate parameters to fields in the core type theory.
The development of major theorem provers from MLTT family such as Lean, Rocq and Agda has been avoiding subsumptive subtyping and manifest fields in the core theory thus making record types the same as sigma types. Subsumptive subtyping there is replaced with coercive subtyping in which case typechecker inserts an application of some function whenever a term is used in a context where a term of type is expected. There are also ways to deal with manifest fields without extending the core type theory as studied, for example, in [37].
Arrays
The primary application of the type Array is that it significantly simplifies recursion and induction for nested inductive types involving inductive types List and Vec . To illustrate this consider inductive type of terms Term with the constructor fun – constructor for the function application term , where is a functional symbol of arity and are terms.
In this case the nesting occurs when the type Term, which is being defined, is used as a parameter of type Vec in its constructor fun. By Vec here we mean the standard type of lists of length represented as indexed inductive type generated by the constructors nil : and cons.
A useful induction principle must supply an induction hypothesis for every entry of . Ordinary inductive vectors have a definable indexing operation get, but the induction principle for this nested definition must account for the vector structure as well. With arrays, the recursive arguments are directly presented as a function on , and the induction hypotheses take the form for a motive . Arrays also support constructor pattern matching and judgemental equality by recursive comparison of their entries, as in the rule in § 2.2. These are the computational conveniences of the built-in array presentation.
Type theory of Arend under types as homotopy types viewpoint
Higher inductive types. Higher inductive types (HITs) provide a mechanism for inductive definitions of types with non-trivial homotopical structure on them. HITs are akin to CW complexes which are defined by specifying cells of various dimensions and the way they glued. The original approach to defining HITs in HoTT was as follows: a HIT contains ordinary constructors, which are generating points of , and path constructors, which are generating paths of and have types of the form , and so on ([57], Chapter 6).
For example, the circle can be defined as HIT with the following constructors:
(a) Point constructor base : for the base point.
(b) Path constructor loop : for the loop.
A definition of the torus would involve cells of dimension 2, for example:
(a) Point constructor point : .
(b) Path constructors , : for two loops.
(c) Path constructor face : defining a cell of dimension 2, where is concatenation of paths.
The recursion principle for HITs is a straightforward generalisation of the one for ordinary inductive types. For example, in order to define a function from to a type one needs to specify a point and a loop in and the recursor gives a function such that and , where pmap is an obvious function mapping a path between arguments to a path between images of a function. Dependent case, that is the induction principle, is also not hard to state, but it is a bit more subtle ([57], Section 6.2).
With this approach to HITs it is far from obvious how to formulate a rigorous schema of general inductive definitions of this kind.
The interval type in Arend allows to use ordinary constructors with conditions instead of path constructors. For example, can be defined in Arend as an inductive type with conditions with the following constructors:
(a) .
(b) , with conditions and .
(c) with conditions:
face left .
face right .
face left .
face right .
The recursion and induction principles are just the standard ones with the requirement that conditions must be preserved by the function being defined. The general schema of inductive definitions of this kind can be easily formulated: it is the standard schema plus specification of valid forms of conditions, which is rather simple. Definitions of HITs in Arend are pretty similar to definitions of HITs in cubical type theories, however there are some differences [62], Section 2.4.4.
Elimination principles for HITs, as formulated in [57], can be derived in Arend, so all HoTT book style proofs can be carried out in Arend. But often inductive types with conditions allow for much simpler proofs. To illustrate this consider a proof of in Arend. The definition of mutually inverse functions and is completely straightforward:
(a) Using elimination for the function is defined by its values on constructors: , , , .
(b) Using double elimination for the inverse is defined by its values on constructors: , , , .
The identities and are proven by reflexivity for each of the constructors and thus can be proven trivially using elimination. In contrast, the HoTT book style proof of is rather involved [57], Exercise 6.3).
Comparison with other cubical type theories
Arend’s interval and the interval of the cubical type theories serve the same purpose, namely presenting an -dimensional cube as a term depending on coordinates, but they are different kinds of object, and that difference decides what computes. This subsection states the difference, measures how far computation actually goes by means of a concrete example, describes what the cubical theories do instead, and says what would have to be added here.
Interval variables. In HoTT-I the interval is a type and is an ordinary assumption of the same standing as . A substitution may replace by an arbitrary term of type , including one containing coe, path application, or a function defined by any means whatever. In the cubical type theories a dimension is a separate syntactic class, rather than a term of an ordinary fibrant type. Dimension expressions are generated by a fixed grammar — names and the two endpoints, together with , and in the De Morgan case — and only expressions of that grammar may be substituted for a dimension variable. This distinction constrains the available computation rules, although regularity and the particular constructor clauses are further design choices. HoTT-I’s interval is an ordinary fibrant type, while the cubical dimension interval is not. We explain the fibrancy obstruction after introducing faces and composition below.
Cube operations are available. It is not the case that HoTT-I lacks the operations on cubes. The cartesian ones cost nothing at all, precisely because interval variables are ordinary variables: a face is the substitution , a degeneracy is weakening, a diagonal is , and an exchange of coordinates is a permutation of the context. None of these needs a rule, and each is automatically stable under substitution, being an operation of the ambient theory rather than of a separate syntactic class.
The operations that a cartesian cube category does not have are also available, as ordinary definitions rather than as primitive dimension syntax. Reversal of paths is definable, so with of type the term exchanges the endpoints of I. The connection squeeze is also definable in HoTT-I: iterating coe in path types gives horn fillers from which it can be constructed [27], § 2.1. Its judgemental boundary equations have the form of those for a minimum:
Read as a square, with running horizontally and vertically, it has two constant sides and two that are the interval itself:
Figure 3.
The dual connection squeezeR : can be constructed explicitly from squeeze using one coercion in a nested path type. Put
An element of is a square whose left side is , whose right and top sides are constant at , and whose bottom side is . The picture shows these boundary values, with horizontal and vertical; write and in the diagrams.

Figure 4.
At all four sides are constant at , so inhabits . Define
The coercion transports this constant square to one with the required boundary:

Figure 5.
Since and , the type of is
The endpoint equations for the outer path give the first row below, and those for the inner path give the second:
Operations of this kind are what the cubical literature calls connections, the De Morgan ones being and .
What they are for is contracting a path to reflexivity. Given from to , the path is the initial segment of up to the point : it is constant at when is left, and it is itself when is right. That family is exactly the data the J-eliminator needs, and with it J is defined in the familiar way,
its reflexivity computation holding judgementally by regularity, the second coe equation of §2. On this last point the comparison runs the other way round. In CCHM and in Cubical Agda the corresponding equation holds only up to a path [12, 58]. Transport is computed there by recursion on the head of the type, with one clause per type former, so it reduces whenever the type is concrete; but the family occurring in J has a variable as its head, and no clause applies. This costs no canonicity — a closed transport always meets a type former eventually, and canonicity for CCHM is a theorem [24] — and what it does cost is the definitional equation for an arbitrary family. HoTT-I obtains that equation from regularity, whose side condition is of a different kind: it asks whether the bound variable occurs in the family, and not what the family looks like. The J instance is exactly the case that separates the two conditions. Substituting leaves the family , since and . Its head is the variable , so no clause keyed to a type former can fire; but does not occur in it, so regularity does. Iterating coe in path families in the same style yields fillers for every finite full cubical horn [27]. So the distinction between HoTT-I and a structural cubical theory is not the availability of connections, reversal, J, or box filling.
What the interval does not carry. What is absent is an equational theory on the interval. In a De Morgan theory the dimension terms form a free De Morgan algebra and are compared by a decision procedure for that algebra, so that and are the same term before any rule is consulted. Here squeeze is an ordinary function: one can prove using the two connections, but the two sides are not judgementally equal, and a term of has in general no normal form as a dimension expression at all.
One consequence is immediate. There is no strict lattice of faces. Internally one may of course form the proposition and combine such propositions with products and truncated sums, but no such family can play the role of the face : a face must be inhabited at and empty at , whereas inhabits the displayed family for every , the interval being contractible. The other consequences are the subject of the rest of this subsection.
How far does computation go? The question is best asked of an example. Take the circle of §2.4, presented in the Arend style by a point base and a constructor loop with an interval argument, subject to the conditions . The two are different things and both are needed below: loop is a function , while the path it generates is
Write for concatenation of paths and for inversion, both defined from J in the usual way: for and one has and , with
judgementally, by the reflexivity computation of J. Let next and prev be the successor and predecessor of Int. The universal cover is the function given on constructors by
and the winding number of a loop is obtained by transporting 0 along it,
This is the standard test of computational univalence, and it is a fair one: each of the equations below is provable in Arend, so the question is only whether the kernel reduces the term or whether one has to prove the equation by hand. Normalizing in Arend 1.12 gives the following.
| term | normal form |
| winding(idp) | 0 |
| winding() | 1 |
| winding() | no reduction: a residual coe through |
| winding() | no reduction: a residual coe through |
| winding(path()) | no reduction: a residual coe through |
Table 1.
So the univalence round trip computes once, and stops there. Note that two separate transports do compose: transporting along and then transporting the result along again reduces to . It is only the transport along the composite path that does not.
What goes wrong. All three failures have one cause. The computation rule for in §2 applies only when three conditions hold together:
the family is , its last argument being the bound variable itself;
the isomorphism data do not mention ;
the target is right.
The third condition already excludes a generic target. The failures in the table, however, all violate the first, and for two different reasons.
For the composite , the path is built by J, so is not an application of loop to anything and never exposes an iso line. The inverse fails for the same reason. In the fifth row the family is , which does have iso as its head and the correct endpoints, since and ; but its last argument is a term of I that does not reduce to the bound variable, so the rule still does not apply, and there is no equational theory on I to normalize to first. In a De Morgan cubical theory the corresponding reparametrization uses a dimension expression, and is already . Cartesian dimension syntax has no such connection operation.
It should be said plainly what this does and does not mean. Nothing is unprovable: the winding number of is , and one proves it in a line from the standard transport laws. What fails is computation by reduction, and with it canonicity, since is a closed term of in normal form that is not a numeral.
Composition is coercion in a path type. Two of the three failures have a common source, and it is not composition as such. Concatenation and inversion are defined from J, and J, by the definition displayed above, is a coercion; so they are coercions. It is worth carrying out the two unfoldings.
For concatenation, take
noting that the second argument does not occur in the body of . The path argument of J is , so the family appearing in its definition is
the witness being discarded, and therefore
The types are as they should be: the base case is , which is , and that is where goes, while the result is , which is .
For inversion, with , take to be and the path argument to be itself. The same two steps give
with base case , that is , and result , that is . In the first coercion the right endpoint of the path family moves and the left is fixed; in the second the left moves and the right is fixed.
The two computation rules recorded above are recovered at once. Put in the first coercion: then , so the family is , which does not depend on , and regularity gives . Put in the second and the same argument gives .
With these coercion-based implementations, the concatenation and inversion examples expose the same gap: there is no computation rule for in a family of path types. The fifth row concerns reparametrized univalence: it calls for either an equation on the interval or a coercion rule that handles the reparametrized family directly.
Faces, partial elements and composition. The cubical theories build everything on one further notion, which the dimension grammar makes available and which is worth describing before Glue. A face formula is a formula of that grammar, built from equations and by conjunction and disjunction, describing part of the boundary of a cube. A partial element is a term defined only where holds. The basic operation consumes one: given a family along a direction , a partial element on , and a starting point agreeing with at , composition produces the value at ,
and
and the result restricts to where holds. The bracket is the partial element itself: is the element whose value is where holds, and it may carry several clauses, one for each face on which a value is prescribed. For a small example, the concatenation of and is a square whose bottom is and whose two vertical sides are the constant path at and the path , and its top is their concatenation:

Figure 6.
path application being written by juxtaposition as in that notation. The partial element is given only on , the two disjuncts do not overlap, and the premise of the rule is discharged by the judgemental equations and . The face is not prescribed; it is the result.
Two degenerate cases have names. Taking false leaves no partial element and recovers transport, that is . Taking the family not to depend on the filling direction gives homogeneous composition , which fills a box inside one fixed type and so needs no transport along ; the example just given is of that form. Conversely coe and hcomp together reconstruct dependent composition, by transporting the cap along and then filling homogeneously in the fibre over . CCHM takes comp as primitive, Cubical Agda exposes transp and hcomp, and Cartesian cubical type theory uses coe and hcom [12, 58, 3].
This apparatus is what HoTT-I does not have, and the reason is the one given above: ranges over a lattice of strict faces, and no internal family of propositions can be one. Arend’s constructor conditions prescribe faces for a particular inductive constructor, as the definition of the torus in §2.4 illustrates, but they are syntactic conditions attached to a constructor and not a general calculus of partial elements. What HoTT-I has in place of the general operation is full horn filling, which is the special case in which the partial element is given on all faces of a cube but one; the example above is of that special case, which is why path concatenation is available here without any of this machinery.
Fibrancy of the dimension interval. Composition also explains why cubical dimension variables are kept separate from ordinary type-theoretic variables. A fibrant type must support the prescribed filling operations, uniformly under substitution. The dimension interval itself does not support these operations. In the standard cubical models, this interval is the representable presheaf whose elements are exactly the expressions allowed by the dimension grammar. The obstruction therefore depends on that grammar.
In cartesian cubical syntax, a dimension expression is either , , or a dimension variable; there is no operation [3]. If the dimension interval were fibrant, every compatible open box in it would have a filler given by such an expression. Consider the three sides of a square prescribed by
which agree at the two corners they share. A filler supplies the missing side , and the two vertical sides force and $q(1)=0:
Figure 7 (PDF p. 22).
Here must be a dimension expression with as its only variable, so the only possibilities are , , and . Their endpoint pairs are respectively , , and . The required pair is absent, so this open square has no filler in the dimension interval.
De Morgan syntax does contain a reversal , so that particular box can be filled, and in fact every individual box can. What CCHM asks for is stronger: the fillers must be chosen uniformly, that is, so as to commute with every substitution of dimensions, diagonals and connections included. It is uniformity that fails. The witness is a box with outer dimensions and filling direction , whose cap at is and whose tube is given only on the two disjoint corner faces
each of which agrees with the cap at . In the cube below, the tube consists of the two colored vertical edges; the other side faces are unspecified. The whole shaded bottom face has value .

Figure 8.
Writing for the resulting top face at , the tube forces and . Substitute . The face formula becomes false, so the box turns into the empty box with cap , whose filler is one chosen element not depending on ; uniformity therefore forces to be that constant. No element of the free De Morgan algebra on meets these three requirements at once [52]. Cubical Agda reflects all of this by placing I in the non-fibrant universe IUniv, without transp or hcomp [58].
In HoTT-I, by contrast, fillers in I may contain coercions and path applications; they are not confined to a grammar of dimension expressions. Its interval is an ordinary contractible fibrant type. A model may take for it any contractible fibrant object whose endpoint inclusion is a cofibration [28]. This provides the full horn fillers used earlier, without supplying the strict face lattice needed by cubical composition.
Glue types and univalence. In CCHM, a univalence line is constructed from a more general type former, Glue [12]. Its purpose is to extend a type given on a face to the whole context, using an equivalence to a type already defined there.
For a concrete picture, consider a square of parameters and the face consisting of its left and bottom edges. A type is given over the whole square, while a type and an equivalence are given only on these two edges. The construction extends to a type over the square, together with an equivalence extending :

Figure 1 (PDF p. 23).
The squares depict the parameter domain, and the thick edges mark . In the left panel, the dotted edges indicate the part of the domain on which no type has been specified. In the right panel, is defined throughout and agrees judgementally with on the marked edges. The map to is an equivalence throughout, restricting to the given on those edges.
In general, suppose that is defined in , while and are defined in the restricted context . Then
is a type in . It comes with a projection , which is an equivalence. For , the restriction equations are
Here and below, also denotes the underlying function of the equivalence. Thus has the same homotopy type as , while its restriction to the chosen face is judgementally the specified type .
The introduction form makes the elements of explicit. Given in and on , with on that face, one forms
The compatibility condition is a judgemental equality; no path witnessing it is an additional argument. The computation rules are
Conversely, an element supplies both its projection to and, on , an element of ; reconstructing it from these data gives .
For an equivalence , take as the base and glue along at the left endpoint and along the identity equivalence at the right endpoint:
The restriction rule gives and , so is a path from to in the universe. The projections to the base fit into the diagram

Figure 2 (PDF p. 23).
The horizontal lines are families of types, and the vertical maps are equivalences. At a variable , the family retains the Glue structure, including the projection to and the prescribed endpoint data.
To obtain computational univalence, one also needs composition in this family. The composition rule for Glue first projects the given partial element and starting point to the base type and composes there. It then uses the equivalence on the target face to obtain compatible data in the partial type, corrects the base component, and applies glue. The equivalence witnesses and the composition operations of the constituent types provide these steps, with the required agreement on the prescribed faces. In particular, transport along is computed by this general rule. In CCHM its agreement with the underlying map of is propositional:
The computation can retain transports in a constant type, which are connected to the identity by paths but do not disappear by a general regularity rule. This propositional agreement suffices to prove univalence [12].
The advantage over the iso rule discussed above is that composition is defined for every family whose outer type former is Glue. If is a cubical dimension expression, substituting in changes the face formulas. The result either reduces on a true face or retains Glue as its outer type former, so the same composition algorithm applies whenever the restriction rule does not already determine the type. This avoids the specific obstruction in HoTT-I, where a coercion rule recognizes only the canonical iso line.
Cartesian cubical type theory implements a related construction with -types, which use a single distinguished face. They satisfy and , and have introduction, projection, coercion and homogeneous composition rules [4]. Here denotes the primitive cubical coercion of along the family ; is bound in the family, and is the target dimension. For fixed , , an equivalence and , the coercion rule from the left endpoint has the form
At a variable , the constructor retains the source element and its image transported in . Its endpoint rules are and . Consequently, at the displayed rule returns the remaining coercion in , and yields whenever that coercion reduces to the identity. Rules for other source endpoints and for homogeneous composition complete the computational structure.
Isaev’s structural computation rules. Isaev’s manuscript [26] describes how finite horn fillers can compute by the outer type former: pairs are filled componentwise, functions transport their arguments backwards, and paths expose another boundary direction. We give the structural schemata here and leave their completion for univalence as an open problem. These are not computation rules of HoTT-I, are not implemented in Arend, and are not proposed additions to it: practical formalization has not justified adopting them. They illustrate a possible more computational variant; we do not claim canonicity for this extension.
Write , . Consider ordinary interval variables and a family , where . The filling direction is : the given face at is the cap, the missing face at is the lid, and the other faces are the side walls. A horn consists of a cap and terms
The subscript means that is omitted. These terms must agree judgementally at every intersection: for example, , and the two substitutions describing any intersection of side walls must give the same term. All these are ordinary typing and equality judgements after endpoint substitution. No face formulas or restricted contexts are added.
In the square below, ; in the cube, . The blue cap and grey side walls are given; the dashed orange lid is computed.

Figure 9 (PDF p. 25).

Figure 10 (PDF p. 25).
Abbreviate the finite list of cap and side arguments by . Isaev’s operation returns the lid at arbitrary terms of type :
The notation is only an abbreviation for this list of arguments. On each boundary of the lid the operation reduces to the corresponding side wall at :
For there are no side walls or output coordinates, and . Although the higher operations are definable using coercion in nested path types in base HoTT-I, here they are primitive operations with the displayed reductions, not transparent abbreviations for those definitions.
The whole filler, including its value at an arbitrary , is obtained by shortening the filling interval. As in Isaev’s computational presentation, take as primitive with its four endpoint equations; its earlier HoTT-I definition is not an unfolding rule here. Define
The substitution changes the side arguments; the cap is unchanged. We retain regularity: transport in a family independent of the transport variable reduces to its input. Its horn version returns when both and every side wall are independent of . A constant ambient type alone is insufficient when the side walls move. Together with the four endpoint equations of , these rules give
and the prescribed side values at every .
Pairs, paths and natural numbers. In the following structural clauses, the cap and side arguments are pairs, path abstractions, or lambda abstractions, respectively. For a horn of pairs in , let and denote the componentwise projections of all its arguments. First fill the first components over the entire box, obtaining . Then fill the second components in the family determined by :
The boundary equations of ensure that each second component has exactly the type required by the recursive filling.
For paths, applying every cap and side argument to a fresh coordinate gives a horn in the underlying family. The two endpoint sections and become its two additional side walls:
Thus the one-dimensional instance makes the square implicit in path transport explicit:
Iteration handles any finite nest of paths, retaining all its boundaries. For natural numbers the constructor clauses are
Here 0 means that the cap and every side are zero, and means that every argument is a successor.
Functions. For a horn of functions in , fix an output point and an argument . The argument must be transported from this point to every point of the box before the cap and side functions can be applied. For a family and endpoints , write for transport of from to $t; the notation binds the family coordinate . Contractibility of supplies chosen paths , so this operation can be defined by
Isaev writes for the iteration of this operation along the coordinates in order:
Put . Write for the horn obtained by applying each given function to the corresponding restriction of . The function clause is
It transports the argument backwards, applies the given functions, and fills their values forwards, including when the domain depends on the transverse coordinates . For the result to have the required type judgementally, this presentation requires
The path-based definition above alone does not establish this diagonal computation. Thus the function clause is conditional on an implementation of with this equation and compatible reductions.
Open problem: computation for iso and the universe. The structural clauses do not supply a general rule for
where all the displayed data, including , may depend on . The existing iso rule covers only transport along the canonical line with fixed isomorphism data. A general rule must also handle varying data, arbitrary interval arguments, and every supplied higher boundary.
The universe requires attention as well. In dimension one regularity gives , but a higher universe horn may have moving type-valued sides. One possibility is to retain its lid as a new type expression, instead of reducing it to an existing type former. For example, let be compatible square horns in , varying with an ordinary interval variable . For we obtain
The first line constructs a type; the second transports an element of that type. Retaining the first expression does not yet give a reduction for the second. The clauses for pairs, functions and paths do not apply, since the type family now has Fill as its outermost operation. A computation rule for filling in these new types is therefore needed, already for ordinary transport.
There is no fixed bound on the nesting that this rule must handle. A later universe horn may use among its cap and side data. Its lid is then another type expression containing the earlier universe filler, and this construction can be repeated. Filling in the resulting types must compute at every finite nesting depth, with reductions that agree with the boundary equations and regularity. Isaev’s manuscript explicitly leaves this nested case unfinished.
Open problem. Complete the structural schemata with general computational rules for iso and universe fillers, in ordinary HoTT-I contexts and without a separate language of dimensions or face conditions. Include the diagonal computation needed by the function clause and check its compatibility with the other reductions. The rules should respect all prescribed boundaries, retain regularity, and be stable under substitution of arbitrary terms of type I. Establish subject reduction, compatibility of overlapping rules, and canonicity for the resulting system; normalization and decidability of judgemental equality are further metatheoretic questions. The structural schemata alone do not establish these properties. Higher inductive types would also require their own compatible computation rules.
Arend language
In this section we present the most essential language constructs of Arend.
Levels and universe polymorphism
Since there is no way to assume consistently the existence of the set Set of all sets any construction that aims at producing a set out of the totality of all sets has to be applied to a universe of small sets Set producing a set in a universe of large sets Set . Then such constructions can typically be iterated and produce a set in the universe Set of level out of the universe Set of level . And typically this routine is straightforward and can be automated.
Arend language allows to use Set and Type in practice as if they were types of types and delegate the routine of dealing with levels to the typechecker. Typechecker replaces Set and Type with hierarchies of universes, converts definitions accordingly and checks if definitions are not contradictory because of a circularity in universe hierarchy. This is achieved by the following mechanisms:
Universe polymorphism. Definitions are made polymorphic on universe levels: there are implicit level parameters associated with each definition.
Level inference. In each occurrence of Set or Type typechecker infers level according to some natural procedure.
Universe management in Arend is rather similar to the one in Lean and recent versions of Rocq. It is quite different in Agda: Agda has considerably less automation, one has to be much more explicit about levels. Also, unlike level expressions in Agda where they are terms of type Level, level expressions in Arend are not typed.
Homotopy levels
The universe and the hierarchy are two members of a family of universes indexed additionally by the homotopy level discussed in § 2.2. Since the homotopy level is always a constant, each member of the family has its own notation: is the universe of -types, that of -types, — with a literal numeral — that of -types for , and that of all types. Thus and are the same universe. The library’s Eilenberg–MacLane type K1, mentioned in § 7.2.1, is a .
Definitions in Prop, Set n and k-type universes
By default a definition is inferred to be of some homotopy level according to certain rules and is placed in the corresponding universe. However one often needs to use a definition which is not inferred by the typechecker to be in \Prop, \Set or \k-Type to define a proposition, a set or a -type in the corresponding universe. There are two ways to do this in Arend:
Use level. Assume D is a definition of a record, class or inductive type is provably a -type which means that the predicate
isOfHLevel D kis provable (in arend-lib this predicate is spelledD ofHLevel_-1+ k, with a variantofHLevel_-2+for the other indexing convention, and the two special casesisPropandisSet). In that case D can be turned into a definition in \k-Type n by means of extending it with a proof ofisOfHLevel D kwhich is done in Arend via \use \level construct. In particular, extending D with a proof ofisProp DorisSet Dwould place D in \Prop or \Set respectively. For example, the predicate nonempty A — which in arend-lib is the propositional truncationTruncP Awith constructorsinPandtruncP— can be defined in \Prop as follows:
\data nonempty (A : \Type)
| in A
| trunc (a a’ : nonempty A) : a = a’ -- just another syntax for the constructor
-- trunc (a a’ : nonempty A) (i : I) with
-- conditions trunc a a’ left => a
-- trunc a a’ right => a’
\where {
\use \level levelProp {A : \Type} (a a’ : nonempty A) : a = a’ => path (trunc a a’)
}
As mentioned in Section 2 elimination to h-propositions from inductive types in \Prop does not involve constructors with parameters of the type I. This means that such constructors can be omitted in definitions of functions by pattern matching in this case. Eliminator corresponding to the recursion principle for nonempty can be defined using pattern matching as follows:
\lemma rec {A B : \Type} (p : isProp B) (t : nonempty A) (f : A -> B) : B \level p \elim t
| in a => f a
This simplified pattern matching allows to derive proof irrelevance for types in \Prop using nonempty:
\lemma prop-pi {A : \Prop} {a a’ : A} : a = a’
=> path \case trunc (in a) (in a’) __ \with { -- \case f __ is unfolded to
| in x => x -- \lam i => \case f i
}
Truncated inductive types. Any definition of an inductive type can be placed in a universe of any given homotopy level by marking the definition as truncated. This marking is done by means of the keyword \truncated in front of a definition. It places the definition in a universe \k-Type n, but at the cost of restricting elimination to types A satisfying
isOfHLevel A k. In other words, pattern matching cannot be used to define functions from truncated inductive types in \k-Type n to a type A unless there is a proof ofisOfHLevel A k. For example, the quotient set can be defined as follows:
\truncated \data Quotient {A : \Type} (R : A -> A -> \Type) : \Set
| in~ A
| ~-equiv (x y : A) (R x y) : in~ x = in~ y -- again, this is unfolded to
-- ~-equiv (x y : A) (R x y) (i : I) with conditions
The recursion principle for Quotient would be:
\sfunc rec {A B : \Type} (R : A -> A -> \Type) (p : isSet B)
(f : A -> B) (f-R : \Pi (x y : A) (R x y) -> f x = f y) (x : Quotient R) : B
\level p
\elim x
| in~ a => f a
| ~-equiv a a’ r i => f-R a a’ r @ i
Typeclasses and records
Here we highlight some aspects of the system of typeclasses and records in Arend. This system is built upon the system of records in the core type theory discussed in Section 2.
Partial implementations. As described in Section 2 the mechanism of manifest fields allows to partially implement parent records or classes12 inside a child record or class. For example, as mentioned in Section 2.3.5 the type of rings can be defined in Arend as an extension of the type of semirings using partial implementation:
\class PseudoSemiring \extends AbMonoid, Semigroup {
| ldistr {x y z : E} : x * (y + z) = x * y + x * z
| rdistr {x y z : E} : (x + y) * z = x * z + y * z
| zro_*-left {x : E} : zro * x = zro
| zro_*-right {x : E} : x * zro = zro
}
\class PseudoRing \extends PseudoSemiring, AbGroup {
| zro_*-left {x} => {?} -- proof of 0 * x = 0 using invertibility wrt ’+’
| zro_*-right {x} => {?} -- proof of x * 0 = 0 using invertibility wrt ’+’
}
-- Adding a multiplicative unit on top of the two definitions above gives
\class Semiring \extends PseudoSemiring, Monoid { -- ... }
\class Ring \extends PseudoRing, Semiring
Here PseudoSemiring extends AbMonoid and Semigroup which are additive commutative monoidal and multiplicative semigroup structures on the same carrier E13. Since AbGroup extends AbMonoid with the group structure, the type PseudoRing is defined as a pseudo-semiring where + operation is strengthened to a group operation.
Another example: tight apartness relation . It is constructively better behaved variant of inequality Not () since it satisfies the tightness condition Not () -> (whereas Not () constructively does not). Such relations are useful, for example, for defining domains constructively as rings satisfying -> -> () (the field #0-* of the class Domain). It is natural to define the base class Set# of sets with apartness relation and various types of structures with apartness as its extensions. However, for example, in case of groups specifying the full binary relation is redundant since it can be expressed in terms of . This can be done using partial implementations:
-- groups with ’+’ operation (not necessarily commutative) and apartness relation ’#’.
-- The class below lives in the \where block of ’AddGroup’ and is referred to
-- from the outside as ’AddGroup.With#’
\class With# \extends AddGroup, Set#
| \fix 8 #0 : E -> \Prop
| #0-zro : Not (zro ‘#0)
| #0-negative {x : E} : x ‘#0 -> negative x ‘#0
| #0-+ {x y : E} : (x + y) ‘#0 => x ‘#0 || y ‘#0
| #0-tight {x : E} : Not (x ‘#0) -> x = zro
| # x y => (x - y) #0
-- we omit implementations of properties of x # y
Finally, another example from Section 2.3.5 - the type of Heyting fields which is by definition a commutative local ring where all noninvertible elements are equal to zero. This example illustrates the usefulness of partial implementations for defining structures which extend several branches of hierarchies in such a way that some data and properties of one branch is implemented in terms of data and properties of other branches.
\class Field \extends LocalCRing, GCDDomain
| #0 x => Inv x
| #0-+ => LocalRing.sumInv=>eitherInv -- property of local rings: if x + y is invertible
-- then either x or y is invertible.
-- we omit implementations of isGCDDomain and other properties of apartness ’#’
-- the tightness ’#0-tight’ remains unimplemented and represents one of defining
-- properties of the Heyting field: all noninvertible elements are equal to zero
Anonymous extensions. Extensions of records and classes can be defined on the fly: if C is a record containing a field f : A then the term C { f => a } refers to a record extension obtained from C by specifying f to a term a : A.
For example, one can use the class of all semirings to define the type of all semiring structures on natural numbers:
\func SemiringsOnNat : \Set => Semiring { E => Nat } -- or simply ’=> Semiring Nat’
Here SemiringsOnNat is a subtype of Semiring.
Properties. As mentioned in Section 2 a form of computational proof irrelevance holds in Arend for records and classes. Arend makes an explicit distinction between property fields and data fields. The result of comparison of two objects depends only on comparison of data fields, proofs of properties are ignored. By default a field is a property if its type is a proposition which in particular is the case if the type is equality between elements of a set.
For example, the class PseudoSemiring has four property fields: ldistr, rdistr, zro_-left and zro_-right. Proofs of these are ignored when two pseudo-semirings are compared.
Static and dynamic blocks. All fields of a record or class D as well as definitions of inductive types and functions declared in the inner block of D have an implicit parameter
\this : Dwhich represents the instance 14. Fields and definitions in this block are thus called dynamic analogously to dynamic class methods in Java or C++. Although dynamic definitions can be replaced with external static definitions with an extra parameter of type D, dynamic definitions of basic operations and properties of D are more concise and neat. For example, part of dynamic block of Monoid might look as follows:
-- ’\infixl 7 *’ and ’*-assoc’ are inherited from ’Semigroup’
\class Monoid \extends Pointed, Semigroup {
| ide-left {x : E} : ide * x = x
| ide-right {x : E} : x * ide = x
\func pow (a : E) (n : Nat) : E \elim n
| 0 => ide
| suc n => pow a n * a
\lemma pow-+ {a : E} {n m : Nat}: pow a (n + m) = pow a n * pow a m \elim m
| 0 => inv ide-right
| suc m => pmap (* a) pow-+ *> *-assoc
}
Just like any other definition in Arend classes and records have \where block for associated static definitions. These static blocks are quite useful, for example, for defining some standard structures on top of a mathematical structure like having an apartness relation or decidable equality. For example, for rings one use the static block as follows:
\class Ring \extends Semiring, AbGroup {
-- ...
} \where {
-- | A ring with a tight apartness relation.
\class With# \extends Ring, AddGroup.With# {
-- ...
}
-- | A ring with decidable equality.
\class Dec \extends AddGroup.Dec, With# {
-- ...
}
}
5. Type classes. The concept of a type class originates in Haskell programming language. The mechanism of type classes enables ad-hoc polymorphism, a form of polymorphism similar to operator overloading in object-oriented programming: type classes specify bundles of operations on types which can be implemented differently for different types.
In Arend type classes are definitions which start with the keyword \class and are similar to records. The key difference is the instance inference mechanism for type classes: some of objects of a type class can be declared as instances which would enable the typechecker to infer a suitable instances whenever necessary. For example, a semiring structure on natural numbers can be defined as an instance of class Semiring:
\instance NatSemiring : Semiring Nat
| zro => 0
| + => +
| * => *
| ide => 1
-- we omit proofs of semiring properties for Nat
At a place where multiplication of natural numbers is used typechecker can infer the instance NatSemiring and make applicable at this place everything that is applicable to semirings, for example, a simplification tactic erasing subexpressions multiplied by 0.
\func example (n : Nat) : n * 0 + 1 = 1
=> simplify -- the tactic ’simplify’ infers NatSemiring and uses proofs
-- of properties of +, * to derive the equality
With respect to the behavior of instances and instance inference Arend is very similar to other theorem provers like Rocq, Lean or Agda.
Arrays
The type Array is defined in Prelude.ard as a record:
\record DArray {len : Nat} (A : Fin len -> \Type)
(\coerce at : \Pi (j : Fin len) -> A j)
\func Array (A : \Type) => DArray { | A _ => A }
There are also functions nil and a :: l which can be used in pattern matching as if DArray were an inductive type. Coercion at allows to use arrays as if they were functions. A function G, as mentioned in § 3.3.6, can be defined by recursion on terms as follows:
\data Term (F : \Set) (a : F -> Nat) | fun (f : F) (v : Array (Term F a) (a f))
\func G {F : \Set} {a : F -> Nat} (t : Term F a) \elim t
| fun f v => fun f (\lam i => G (v i))
IDE for Arend: IntelliJ IDEA plugin
Remarks on implementation
Scoping and dependency analysis. Arend files can depend on other Arend files, and Arend also allows circular dependencies within a single Arend library (aka IntelliJ IDEA module of type “Arend”). Furthermore, the scope of any Arend definition or theorem is not restricted to the text that follows it, but rather extends throughout the entire enclosing scope. For instance, the scope of a top-level definition spans the entire Arend file to which it belongs. This behavior is similar to the scoping mechanisms found in many general-purpose programming languages and contrasts with typical proof assistants like Rocq or Mizar. On the positive side, this approach simplifies import management and code migration for the user. On the negative side, it creates a need for Arend’s type checker to track dependencies between individual definitions across different files and to handle potential circular dependencies between them, as these can result in inconsistent theory. In Arend, circular dependencies are only allowed between recursively defined functions, and even then, only if the termination checker can detect that parameters of recursive function calls become “smaller” from one call to another call. The termination checker algorithm largely follows the one outlined in A. Abel’s master’s thesis FOETUS.
Incremental type checking. The dependency analysis mechanism enables another key feature in Arend: incremental type checking. When a user modifies one or more definitions, the type checker selectively discards cached information related to those definitions, as well as any other definitions that depend on them, either directly or through a chain of dependencies. This ensures that unaffected parts of the code are not reprocessed, significantly speeding up the type-checking process and helping to conserve laptop battery life.
Smart mode and Dumb mode. Under normal circumstances the Arend plugin uses the so-called ”on-the-fly” (or Smart) mode of type checking. In this mode, the type checker operates in a background thread, automatically reprocessing each code modification made by the user. Running the type checker in the background prevents the IDE from freezing during the process. Since the type checking can be time-consuming and may involve extensive computations, a special mechanism halts the process if it exceeds the user-defined time limit (defaulted to 5 seconds). Additionally, there is an option to disable on-the-fly inspection entirely, switching the IDE into ”Dumb mode”. In this mode, the IDE still resolves identifiers on the fly but does not automatically perform type checking which can still be manually run via IntelliJ IDEA’s standard mechanism of run configurations.
Editor features of Arend plugin
Parameter Hints. Parameter Hints feature displays a tooltip showing the function or datatype’s signature used in expression, including expected parameters (both explicit and implicit) along with their types. The tooltip also highlights the parameter corresponding to the argument where the caret is positioned. Moving the caret to a different argument updates the highlighted parameter accordingly. When the caret is moved away from the call expression, the tooltip disappears. For example, when invoked on the expression IsContAt {TopSub S} f x on the argument f the tooltip shows the signature of IsContAt (is continuous at a point):
with f : X → Y highlighted.
This feature requires the target definition to be fully type-checked, as definitions in Arend may include dynamically inferred implicit parameters that are not explicitly listed in their signatures. However, a fallback mechanism is available: it tries to match the arguments of the selected expression to the parameters of the definition, even when the definition has not been type-checked (e.g., when the typechecker is in Dumb mode).
Auto-completion. Auto-completion is a feature that helps identify available identifiers in the current scope and to complete partially entered identifiers. Also, it imports definitions from scopes that have not yet been imported. The current scope is determined by the set of active imports, along with surrounding local and global declarations and variables.
Intention Actions and Quick Fixes. Quick Fixes and Intention Actions are standard features in IntelliJ IDEA that provide suggestions for modifying code. The main distinction between Quick Fixes and Intention Actions lies in their purpose. Quick Fixes are specifically aimed at resolving errors detected by the Arend type checker, while Intention Actions offer general improvements or suggestions not directly linked to specific errors.
Replace a meta with result. Replaces a meta with the proof term it generates.
Replace an expression with weak head normal form. Replaces a selected expression with its partially normalized version. Recall that an expression is said to be in WHNF if it is reduced to the point where it cannot be further simplified at the outermost level, but may still contain unevaluated or partially evaluated expressions within it. WHNF is a representation of terms used internally by the Arend type checker. It is used mainly for efficiency, as fully normalizing (reducing to a normal form) can be computationally expensive.
Extract code as a function. Moves a selected part of an expression into a separate function within the same namespace, replacing the original part with a function call. This action also generates the necessary function arguments.
Generate function from goal. This action can be invoked on an unfilled goal, replacing it with a call to an auxiliary function in the namespace of the current definition or theorem. The function’s type will match the goal’s type, and its arguments will include the minimal subset of context variables required for the goal.
Replace with constructor. This action fills an unfilled goal with the appropriate constructor. For example, a goal with a
\Pitype will be filled with a lambda expression, a sigma type with a tuple, and an inductive type with one of its constructors (with a prompt if multiple constructors exist), etc.
Implement fields quick fix. When applied to an empty
\instancestatement with a specified type class, this quick fix generates a skeleton for implementing the class. It lists all fields inherited from ancestor classes that are not yet implemented or lack a default implementation.
Implement clauses quick fix and Split pattern variable intention. If an Arend definition or pattern-matching construct is missing some or all of its clauses, the type checker suggests adding them using this quick fix. It works for both
\caseexpressions and pattern-matching constructs using the\elimor\withkeywords.
The Split Pattern action can be applied to pattern variables used in pattern-matching clauses. This action performs the following 3 steps:
(a) Type Analysis: It determines the type of the pattern variable and identifies its associated constructors.
(b) Clause Duplication: It creates as many copies of the current pattern-matching clause as there are constructors.
(c) Constructor Substitution: It replaces every instance of the original pattern variable with a call to the respective constructor in each of the newly created clauses.
Auto import quick fix. If the user clicks on an unresolved identifier, this quick fix searches for definitions with this name among the imported Arend libraries. If multiple matches are found, the user can choose one. Once selected, the quick fix updates the identifier to a valid reference and adds the necessary
\importdirectives.
Additionally, several other quick fixes perform simpler tasks, such as removing unnecessary elements or making basic corrections. These include adding a missing argument or class instance to a function call if the type checker can infer it, or fixing import directives in case of errors in the Arend file preamble.
Navigating Arend projects
This section introduces essential tools for efficiently navigating Arend projects in IntelliJ IDEA.
Go to declaration. The user can jump to the location where an identifier is defined.
Find usages. This command locates all occurrences of the identifier within the specified scope, organizes them by the type of usage and the containing file, and also displays a brief snippet of the surrounding code.
Go to Class/File/Symbol. The user can navigate to a definition or a file with a given name.
Class Hierarchy. The Arend plugin supports IntelliJ IDEA’s Class Hierarchy feature, enabling the user to visualize and navigate the inheritance structure of an Arend class or record, showing its parent and child classes. There is a dedicated tool window displaying the hierarchy tree. The user can toggle between views of superclasses and subclasses. The hierarchy panel is interactive, allowing the user to navigate directly to any class by clicking on it. Clicking the Visualize as Orthogonal Diagram button opens a separate window with an orthogonal diagram of the class hierarchy. The contents of the diagram depend on whether the subclasses or superclasses view is active.
Proof search. Nearly every proof assistant struggles with the problem of efficient location of relevant theorems or lemmas in their formal libraries. Consider, for instance, the problem of recalling the name of a lemma that encodes the property that addition is commutative. Is it labeled as add_comm, or +-comm in the library?
The Arend plugin helps address this issue by allowing the user to search for functions based on the definitions they reference. This functionality, called Proof Search, is comparable to the Search vernacular command in Rocq, Type-Directed Search in Idris, or Loogle in Lean.
The user needs to type a query pattern in the input field. Proof Search then lists all definitions whose parameter or result types contain a subexpression matching the specified pattern. In the simplest case this pattern consists of a single reference to an Arend definition and the Proof Search lists all definitions mentioning this identifier in their parameters or result type.
For example, the user can enter a pattern resembling a partial application of a function or a type. Such patterns are allowed to be written in infix form. The placeholder _ can be used as a wildcard pattern to match any arbitrary term. For instance, the query List Nat will return only those definitions that explicitly include the subexpression List Nat within the types of their parameters (or within their result type). On the other hand, the following definitions can be found using the search pattern _ + _ = _ + _:
\func foo (a b : Nat) : a + b = b + a
\func bar (a b : Int) : a + b = b + a
Refactoring Arend projects
This section introduces refactoring tools for Arend in IntelliJ IDEA.
Code formatting. Arend file can be automatically formatted according to Arend’s text formatting conventions.
Optimize Imports. Similar to other languages supported by IntelliJ IDEA, the Arend plugin provides a tool to analyze import headers in each file for potentially superfluous import directives. These unnecessary directives are highlighted in gray and can be removed using the corresponding intention action.
Rename refactoring. The Rename feature in IntelliJ IDEA allows the user to change the name of variables, classes, functions, data types, or other identifiers across the Arend project.
Change Signature refactoring. The Arend plugin supports the Change Signature refactoring feature of IntelliJ IDEA, providing a tool for modifying function or theorem signatures while preserving the correctness of call expressions and types throughout the entire Arend codebase.
This feature applies signature changes across the codebase, ensuring that type dependencies — such as variables referenced in the types of other parameters — are accurately adjusted. For example, renaming a parameter used in a type declaration automatically updates all type definitions that reference it.
Move refactoring. The Arend plugin implements IntelliJ IDEA’s Move Refactoring feature, enabling the user to reorganize code by moving classes, functions, data types, or fields to a new location within the same file or to a different Arend file. This operation automatically updates all references and corrects file imports.
Using Claude Code with Arend CLI
The IntelliJ IDEA plugin described in the previous section is not the only way to interact with the Arend type checker. Arend also ships with a command-line interface (CLI), which opens up the possibility of using the prover outside the IDE. One use case that has recently become practical is LLM-assisted formalization: coupling the type checker with an AI coding agent such as Claude Code developed by Anthropic. An agent of this kind works in an edit–check loop: it modifies source files, invokes external tools, reads their textual output and iterates. A command-line type checker with textual feedback is therefore a natural fit for such an agent, and the absence of a graphical environment is no obstacle.
Arend CLI. In its default mode of operation the CLI resolves and type checks a library, a module, or a single definition in a module, and prints the list of errors and remaining goals:
arend [<Library>] [<Module>[:<def>]]
In Arend 1.12, --serialize persists successfully typechecked modules as binary cache files (.arc); ordinary one-shot invocations do not write these files by default. Subsequent invocations can reuse valid module caches. The flag -r (--recompile) forces recompilation from source, ignoring the caches. Besides type checking, the CLI provides retrieval tools that query the loaded library:
-ss <pattern>(symbol search) finds definitions by name pattern and prints their locations and one-line signatures;-ps <pattern>(proof search) finds lemmas by the shape of their signature, similarly to the Proof Search feature of the IDE plugin, e.g.-ps "_ + _ = _ + _";-fu <name>(find usages) lists the usage sites of a definition;-ch <class>(class hierarchy) prints the superclasses and subclasses of a class together with its\new-and\instance-sites;-sc <name>(scope info) lists everything visible in scope at the position of a given definition.
Symbol search uses an on-disk index cached by modification time. All five retrieval commands accept --json for machine-readable output. They provide an agent with names, signatures, locations and usages without requiring it to scan the entire library.
The flag -p Module:definition prints an elaborated definition after type checking, while -c additionally checks the resulting core terms. For repeated interactions, -d starts a daemon that retains a typechecked library in memory and persists its module caches. Subsequent commands normally use this daemon; --no-daemon forces an independent invocation. Thus an agent can combine retrieval with ordinary source edits and typechecking feedback in an edit–check loop.
Skills. Claude Code can be supplied with reusable domain knowledge in the form of skills: self-contained instruction files whose frontmatter describes the situations in which the agent should load them. A collection of such skills for Arend is available in the repository arend-skills15, which can be installed by symlinking or copying the skill directories into the agent’s skills directory. The collection consists of the following skills:
arend-formalize — a procedural workflow for turning an informal mathematical statement into a typechecking Arend definition or lemma: how to orient oneself in arend-lib using the retrieval flags above, how to choose the classes and lemmas to reuse, and the order of operations up to the point where the only remaining errors are the unproven goals
{?};arend-prove — a workflow for filling in the
{?}placeholders once the statement type checks, together with a catalog of metas (rewrite, cases, mcases, simplify, equation, cong, ext, linarith, unfold, etc.), their semantics, decision tables and common failure modes;arend-quirks — a collection of notes on the ways in which the syntax and semantics of Arend differ from what a user of Rocq, Agda or Lean would naively expect;
arend-error-type-mismatch and arend-error-extraneous-input — reference material for diagnosing two families of misleading error messages, in which the reported type mismatch or the reported unexpected token is merely a downstream effect of an upstream name-resolution or parsing problem.
The skills arend-formalize and arend-prove form the intended pipeline: the first brings a file to the state where only goal errors remain, and the second attempts to close them, introducing auxiliary lemmas when needed. Remaining holes are unfinished work; completion requires a typecheck with no errors or goals. The error-diagnosis skills are consulted when a check fails. The skills also record newly learned language and meta behaviour for later use.
The library arend-lib
In this section we highlight some parts of arend-lib; listings are abridged where marked by omissions.
Constructive mathematics
Category theory
Categories and precategories. The approach to definition of categories in arend-lib follows the UF approach outlined in [57], Chapter 9. According to it, the term category is used not for any category in the usual sense, but for a univalent category where isomorphic objects are equal. Arbitrary category in the usual sense is called a precategory.
\class Precat (Ob : \Type) {
| Hom : Ob -> Ob -> \Set
| id {X : Ob} : Hom X X
| \fixl 8 o \alias \infixl 8 ◦ {X Y Z : Ob} : Hom Y Z -> Hom X Y -> Hom X Z
| id-left {X Y : Ob} {f : Hom X Y} : id o f = f
| id-right {X Y : Ob} {f : Hom X Y} : f o id = f
| o-assoc {X Y Z W : Ob} {h : Hom Z W} {g : Hom Y Z} {f : Hom X Y} : (h o g) o f = h o (g o f)
-- Iso {C : Precat} {dom cod : C} (f : Hom dom cod) is the type of isomorphisms;
-- it is obtained by successively extending the record
-- Map {C : Precat} {dom cod : C} (\coerce f : Hom dom cod) with the properties
-- of a monomorphism, a split monomorphism and, finally, of an isomorphism
\func idtoiso {a b : Ob} (p : a = b) : Iso {_} {a} {b} \elim p
| idp => idIso -- the identity isomorphism
}
\class Cat \extends Precat {
| univalence {a b : Ob} : IsEquiv (idtoiso {_} {a} {b}) -- ’idtoiso’ is an equivalence
}
Functors and natural transformations are defined as follows:
\class Functor (C : Precat) (D : Precat) (\classifying F : C -> D) {
-- ’F’ is the classifying field of ’Functor’
-- This implies that ’Functor’ is implicitly coerced to ’C -> D’
-- Moreover it affects the instance inference mechanism
| Func {X Y : C} : Hom X Y -> Hom (F X) (F Y)
| Func-id {X : C} : Func (id {_} {X}) = id
| Func-o {X Y Z : C} {g : Hom Y Z} {f : Hom X Y} : Func (g ◦ f) = Func g ◦ Func f
}
\record NatTrans {C : Precat} {D : Precat} (F G : Functor C D) {
| \coerce trans (X : C) : Hom (F X) (G X)
-- ’NatTrans’ is coerced to a function from objects to morphisms
-- Records do not have classifying fields and do not take part in
-- instance inference mechanism
| natural {X Y : C} (f : Hom X Y) : trans Y ◦ F.Func f = G.Func f ◦ trans X
}
Earlier versions of arend-lib declared NatTrans with four explicit, linearly ordered predicative level parameters, so as to allow the two categories and to live in different universes:
\record NatTrans \plevels obj >= hom >= iobj >= ihom {C : Precat \levels (iobj,ihom) _}
{D : Precat \levels (obj,hom) _} (F G : Functor C D)
The syntax for levels has since been simplified: the keywords \plevels and \levels have been removed from the language, level parameters of a definition are now declared by a suffix .{l1, ..., ln} on its name, and level arguments are supplied by the same suffix at the use site, as in Precat.{iobj,ihom} or \instance PosetCat.{u} : Cat Poset.{u}. In the case of NatTrans the explicit declaration turned out to be unnecessary altogether and the current definition relies on level inference.
Standard theory. The library arend-lib contains formalization of the basic theory from standard textbooks on categories: adjoint functors, Kan extensions, (co)limits, comma and slice categories, Yoneda lemma, cartesian closed and preadditive categories, subobjects and factorization systems, displayed categories, reflective subcategories and the simplex category. There is also a solver Category.Solver for equations between composites of morphisms.
Topoi. The library arend-lib contains elements of the theory of elementary and Grothendieck topoi. A site is defined in arend-lib as a precategory together with a predicate on presieves which is stable under pullback:
\func Presieve {C : Precat} (x : C) => Set (ObOver x)
-- ’ObOver x’ is the type of pairs (y : C, f : Hom y x)
-- ’Set X’ is the type of subsets ’X -> \Prop’ of ’X’
\class Site \extends Precat {
| isCover (x : Ob) : Presieve x -> \Prop
| cover-stable {x y : Ob} (h : Hom x y) : \forall {S : isCover y} \exists (T : isCover x)
\forall {px : T} \exists (py : S) (f : Hom px.1 py.1) (py.2 o f = h o px.2)
}
The saturation of isCover under the usual closure rules is given by a truncated inductive type Covering, and sheaves on a site with values in a category form the class VSheaf of -valued presheaves satisfying the descent condition.
Topology
Locales. The concept of a locale captures the system of open subsets of a topological space without reference to its underlying set of points. Locales align better with constructive mathematics, as many natural systems of “open subsets” lack enough points without the axiom of choice. For instance, classically, an affine scheme is defined as the topological space , whose points are the prime ideals of a ring , equipped with a canonical sheaf of rings. However, in a constructive setting, prime ideals may not exist. In contrast, the locale of “open subsets” corresponding to radical ideals of always preserves the meaningful structure. Therefore, it is more natural in constructive mathematics to define an affine scheme as this locale of radical ideals, together with its sheaf of rings. There are also reasons to use locales instead of topological spaces in the classical setting, we will discuss this in the context of algebraic geometry in § 7.1.3.
Formally, is defined as a frame, which is a poset with all small joins and all finite meets satisfying the infinite distributive law: . In particular, a frame is a complete, distributive lattice, and hence also a Heyting algebra. A frame homomorphism is a homomorphism of posets preserving finite meets and small joins. This defines the category Frm of frames. The category Locale of locales is the dual of Frm: Locale := Frm. In particular, a locale is given by the same data as a frame.
In arend-lib the type of locales is defined as the class Locale, which extends three classes: CompleteLattice, the class of Heyting algebras16 and Site. The last of these makes every locale a site, whose covers are the families of opens whose join dominates the given open (§ 7.1.1).
The class Locale thus forms a diamond in the lattice hierarchy. On one side, CompleteLattice descends from BoundedLattice, adding the operations Join and Meet of type (E -> \Prop) -> E, that is, joins and meets of arbitrary subsets of E. On the other side sits the class of Heyting algebras. It descends from the class of bounded distributive lattices, BoundedDistributiveLattice, and so from BoundedLattice as well, and it adds the implication --> : E -> E -> E. Two of the inherited fields are implemented in Locale in terms of the infinite distributivity law Join-ldistr>=: the implication, and the finite distributivity
| ldistr>= {x y z : E} : x ∧ (y ∨ z) <= (x ∧ y) ∨ (x ∧ z)
Indexed joins are recovered from Join as the derived operations IJoin and SJoin:
\func IJoin {J : \Type} (f : J -> E) : E -> Join (TSetIm f)
\func SJoin {A : \Type} (f : A -> E) (P : A -> \Type) : E -> Join (SetIm f P)
The categories of frames and locales are defined as follows:
\record FrameHom \extends PosetHom {
\override Dom : Locale
\override Cod : Locale
-- Properties expressing that ’func’, the field of PosetHom, is a homomorphism of frames.
-- Every equality below comes with a ’>=’ variant containing the nontrivial inequality;
-- the two are interderivable with a ’default’ implementation, so an instance may
-- implement whichever of the two is more convenient.
| func-top : func top = top
| func-top>= : top <= func top
| func-meet {x y : Dom} : func (x ∧ y) = func x ∧ func y
| func-meet>= {x y : Dom} : func x ∧ func y <= func (x ∧ y)
| func-Join {C : Dom -> \Prop} : func (Join C) = SJoin func C
| func-Join>= {C : Dom -> \Prop} : func (Join C) <= SJoin func C
\default func-Join>= => _ <=_<= func-Join
\default func-Join => <=-antisymmetric func-Join>= $ SJoin-univ \lam Ca => func-<= (Join-cond Ca)
-- ...
}
-- ’FrameHom.id’ and ’FrameHom.◦’ are the identity and the composition of frame
-- homomorphisms; since the underlying function of a composite is a literal
-- composition, the category laws hold by reflexivity
\func FrameCat.{u} : Cat Locale.{u} \cowith
| Hom => FrameHom
| id => FrameHom.id
| o => FrameHom.◦
| id-left => idp -- proof by reflexivity
| id-right => idp
| o-assoc => idp
| univalence => sip \lam {X} {S1} {S2} h1 h2 => exts Locale {
-- ’sip’ is a meta implementing the structure identity principle: it reduces
-- univalence to the statement that two frame structures on the same carrier
-- admitting frame homomorphisms in both directions along the identity are equal
| <= x y => ext (h1.func-<=, h2.func-<=)
| meet x y => h1.func-meet
| top => h1.func-top
| Join C => -- ...
}
-- A homomorphism of locales is a frame homomorphism in the opposite direction
\func LocaleHom (L M : Locale) => FrameHom M L
-- Declaring ’LocaleCat’ an \instance (as opposed to \func in case of ’FrameCat’)
-- enables instance inference mechanism to infer ’LocaleCat’ instance for locales
\instance LocaleCat.{u} : Cat Locale.{u}
=> FrameCat.op
The library constructs terminal objects, binary products and equalizers in the category of locales, and hence all finite limits. It also constructs an initial locale:
\instance LocaleCartesianPrecat.{u} : CartesianPrecat
| Precat => LocaleCat.{u}
| terminal => \new Product {
| apex => discreteLocale (\Sigma) -- the locale of subsets of the unit type
-- ...
}
| Bprod L M => \new Product { | apex => ProductLocale L M | -- ... }
\func localeEqualizer {L M : Locale} (f g : LocaleHom L M) : Equalizer {LocaleCat} f g
-- the apex is the locale of fixed points of a nucleus on ’L’
\func InitialLocale : Locale (\Sigma)
The library also characterizes classes of maps: a map of locales is a regular monomorphism (that is, exhibits its domain as a sublocale) exactly when the corresponding frame homomorphism is surjective, and there are two orthogonal factorization systems on Locale, (dense, closed) and (strongly dense, weakly closed). Sites are related to locales by an adjunction. A preorder site is a site whose underlying category is a preorder; every locale gives one, and conversely every preorder site P generates a locale SiteLocale P of its ideals, which is the reflection of P into locales:
\class PreorderSite \extends Preorder, Site
\func LocaleSite (L : Locale) : PreorderSite L
\instance SiteLocale (P : PreorderSite) : Locale (Opens P)
\func FrameReflectiveSubcat.{u} : ReflectiveSubPrecat FrameCat.{u} PreorderSiteCat.{u}
This is what makes it practical to construct locales by generators and relations, which is used, for instance, for the locale of reals and for the spectra of rings (§ 7.1.3).
Limits and derivatives. Derivatives in arend-lib are defined for maps where is a certain kind of a topological ring and , are topological -modules. More specifically, is required to be a near skew field which is a topological ring such that invertible elements are dense. Moreover, for the uniqueness and other key properties of derivatives to hold, the codomain topological -module is required to be Hausdorff.
\class TopSpace \extends BaseSet {
| isOpen : Set E -> \Prop -- here ’Set E’ is the power set ’E -> \Prop’
-- We omit properties of open sets
}
\class TopSemigroup \extends TopSpace, Semigroup
| *-cont : ContMap (ProductTopSpace \this \this) \this \lam s => s.1 * s.2
-- ’* : E x E -> E’ is continuous
\class TopMonoid \extends TopSemigroup, Monoid
\class TopAbGroup \extends TopSpace, AbGroup, UniformSpace {
| +-cont : ContMap (ProductTopSpace \this \this) \this \lam s => s.1 + s.2
-- ’+ : E x E -> E’ is continuous
| negative-cont : ContMap \this \this negative
-- ’negative : E -> E’ is continuous
| neighborhood-uniform {C : Set (Set E)} :
isUniform C <-> ∃ (U : isOpen) (U 0) ∀ x ∃ (V : C) ∀ {y} (U (x - y) -> V y)
-- ∃ and ∀ are metas simplifying the work with arguments
-- ’isUniform C’ is a predicate of ’UniformSpace’ (see further sections for details)
-- For abelian groups it can be defined in terms of neighborhoods of 0
-- For technical (computational) reasons ’isUniform’ is left unimplemented
-- We omit implementations of fields from parent classes of ’TopAbGroup’
}
\class TopRing \extends TopAbGroup, TopMonoid, Ring
\class NearSkewField \extends TopRing
| inv-dense : IsDenseSet \lam (x : E) => Monoid.Inv x
\class NearField \extends NearSkewField, CRing
Examples of near skew fields of interest include topological fields , and . A non-field example: if is a near skew field then the ring of dual numbers is a near skew field as well. Dual numbers arise, for example, as follows: if is a manifold over then the tangent manifold is naturally a manifold over .
The directional derivative at a point in a direction is defined as where , . The library defines convergence of nets by the usual neighborhood condition:
-- The following function is a dynamic member of ’class TopSpace’
-- ’f : I -> E’ is a schlicht generalization of a sequence of points in ’this’
\func IsLimit {I : DirectedSet} (f : I -> E) (l : E) : \Prop
=> ∀ {U : isOpen} (U l) ∃ (N : I) ∀ {n} (N <= n -> U (f n))
In arend-lib both and are defined relative to a subset .
-- Definition of qf
-- ’Set.Total S’ for ’S : Set X’ is the type of pairs (x : X, p : S x)
\func dquot {R : NearSkewField} {X Y : TopLModule R} {S : Set X} (f : Set.Total S -> Y)
{x : Set.Total S} (h : Inv {R}) (a : X) (\property s : S (x.1 + h.val *c a))
=> h.inv *c (f (_,s) - f x)
\func IsDirDerivAt {R : NearSkewField} {X Y : TopLModule R} {S : Set X}
(So : isOpen S) (f : Set.Total S -> Y) (x : Set.Total S) (a : X) (d : Y) : \Prop
=> Y.IsLimit {DirSet So} (\lam h => dquot f h.6.1 _ h.6.2) d
-- Denote G : R -> X, G := \lam r => x + ra. G^{-1}(G(R) ∧ S) ⊆ R is open and contains 0.
-- ’DirSet’ consists of open subsets U ⊆ R intersecting
-- G^{-1}(G(R) ∧ S) ∧ (\lam h => Monoid.Inv h) at some h_U and containing 0.
-- h.6.1 is precisely h_U.
\where {
-- Proof that G^{-1}(G(R) ∧ S) is open (by continuity of G)
\private \lemma aux1 (So : isOpen S)
=> func-cont {+-cont ◦ tuple (const x.1) (*c-cont ◦ tuple id (const a))} So
-- Proof that G^{-1}(G(R) ∧ S) contains 0
\private \lemma aux2 => transportInv S (pmap (x.1 +) (X.*c_zro-left {a}) *> zro-right) x.2
\protected \func DirSet (So : isOpen S) => InvDirectedSet (aux1 So) aux2
-- InvDirectedSet {R : NearSkewField} {S : Set R} (So : isOpen S) (S0 : S 0)
-- Constructs a family of open sets U ⊆ R intersecting S ∧ (\lam h => Monoid.Inv h)
-- and containing 0.
}
The predicate IsDerivAt allows the direction to vary as well: for each , it requires as , with the base point fixed.
\func IsDerivAt {R : NearSkewField} {X Y : TopLModule R} {S : Set X} (So : isOpen S)
(f : Set.Total S -> Y) (x : Set.Total S) (Df : X -> Y) : \Prop
=> \Pi (a0 : X) -> Y.IsLimit {DirSet So a0} (\lam h => dquot f h.6.1 _ h.6.2) (Df a0)
-- In this case ’DirSet’ consists of open subsets of R x X
This condition alone does not imply linearity. The lemma deriv-linear proves linearity when the candidate is already a continuous additive map and is Hausdorff. The module Analysis.StrongDerivative instead requires a continuous extension of to , with also varying. For Hausdorff , it constructs a linear derivative from this stronger condition.
Topological hierarchy. At the bottom of topological hierarchy in arend-lib are normed spaces (classes NormedAbGroup, NormedRing, PseudoValuedRing etc) and metric spaces (class MetricSpace) together with a number of intermediate superclasses obtained by dropping separatedness (PseudoMetricSpace, PseudoNormedAbGroup) or admitting infinite distances (ExMetricSpace, ExPseudoNormedAbGroup), and their complete variants (CompleteMetricSpace, CompleteNormedAbGroup, BanachSpace, RealBanachAlgebra, StoneC*Algebra etc).
These are generalized to uniform spaces (class UniformSpace), where one can define uniformly continuous maps. A compatible uniform structure is specified by a predicate isUniform C on covers C of the underlying set, satisfying the uniformity axioms. The covers need not consist of open sets. The axioms are distributed over three classes: the basic closure properties of isUniform live in PreuniformSpace; the requirement that the induced cover space be regular, so that uniform covers can be refined by star-smaller ones, is added in RegularPreuniformSpace; and the star refinement axiom itself, which is what makes the induced cover space completely regular, lives in UniformSpace. The relation appearing below means that V is star-below U, i.e. that some uniform cover C satisfies .
\class PreuniformSpace \extends PrecoverSpace {
| isUniform : Set (Set E) -> \Prop
| uniform-cover {C : Set (Set E)} : isUniform C -> \Pi (x : E) -> ∃ (U : C) (U x)
| uniform-top : isUniform (single top)
| uniform-refine {C D : Set (Set E)} : isUniform C -> Refines C D -> isUniform D
| uniform-inter {C D : Set (Set E)} : isUniform C -> isUniform D -> isUniform (CoverInter C D)
| uniform-cauchy {C : Set (Set E)} : isCauchy C <-> Closure isUniform C
-- the Cauchy covers of the underlying cover space (see below) are exactly
-- those generated by the uniform ones
-- We omit the rest of the class, which deals with the parent class fields
}
\class RegularPreuniformSpace \extends PreuniformSpace, CoverSpace {
| uniform-regular {C : Set (Set E)} : isUniform C -> isCauchy \lam V => ∃ (U : C) (V <==* U)
-- ...
}
\class UniformSpace \extends RegularPreuniformSpace, CompletelyRegularCoverSpace {
| uniform-star {C : Set (Set E)}
: isUniform C -> ∃ (D : isUniform) ∀ {V : D} ∃ (U : C) ∀ {W : D} (Given (V ∧ W) -> W ⊆ U)
-- We omit the rest of the class, which deals with the parent class fields
}
\record LocallyUniformMap \extends CoverMap {
\override Dom : RegularPreuniformSpace
\override Cod : RegularPreuniformSpace
| func-locally-uniform {E : Set (Set Cod)} : isUniform E
-> ∃ (C : isUniform) ∀ {U : C} (isUniform \lam V => ∃ (W : E) (U ∧ V ⊆ func ^-1 W))
-- We omit the rest of the class, which deals with the parent class fields
}
\lemma uniform-subset {X : PreuniformSpace} {C D : Set (Set X)} (Cc : isUniform C)
(e : \Pi {U : Set X} -> C U -> D U) : isUniform D
=> uniform-refine Cc \lam {U} CU => inP (U, e CU, <=-refl)
\record UniformMap \extends LocallyUniformMap {
| func-uniform {E : Set (Set Cod)} : isUniform E
-> isUniform \lam U => ∃ (V : E) (U = func ^-1 V)
| func-locally-uniform Eu => inP (_, func-uniform Eu,
\lam (inP (V,EV,p)) => uniform-subset (func-uniform Eu)
\lam _ => inP $ later (V, EV, rewrite p meet-left))
}
Constructively, completing ℚ with its usual metric does not by itself establish the Heine–Borel property: one cannot in general prove that every open cover of the resulting real interval has a finite subcover. Localic completion provides another approach, yielding the locale of real numbers, whose closed bounded intervals are compact as locales [59]. Maps between locales are described by their action on opens. For constructions such as power series, it can be more convenient to work directly with real numbers and functions on them.
Isaev’s cover spaces [29] retain this point-set approach. A cover space equips a set with a distinguished collection of Cauchy covers, satisfying the axioms below. For a uniform space, these covers are generated from its uniform covers. Morphisms are functions whose inverse images take Cauchy covers to Cauchy covers.
Completion is constructed using Cauchy filters; for it yields the Dedekind reals. A cover space is totally bounded if every Cauchy cover has a finite subcover, and compact if it is also complete. Closed bounded real intervals are compact in this sense [29 Section 9]. The distinction is that an arbitrary open cover need not be a Cauchy cover constructively.
The connection with locales is concrete in this example: the locale associated with the cover space of real numbers is the usual locale of reals, and cover maps correspond exactly to morphisms of that locale [29 Proposition 8.16 and Corollary 8.17].
The cover spaces are defined in arend-lib as follows:
\class PrecoverSpace \extends TopSpace {
| isCauchy : Set (Set E) -> \Prop
| cauchy-cover {C : Set (Set E)} : isCauchy C -> \Pi (x : E) -> ∃ (U : C) (U x)
| cauchy-top : isCauchy (single top)
| cauchy-refine {C D : Set (Set E)} : isCauchy C -> Refines C D -> isCauchy D
| cauchy-glue {C : Set (Set E)} : isCauchy C ->
\Pi {D : Set E -> Set (Set E)} -> (\Pi {U : Set E} -> C U -> isCauchy (D U))
-> isCauchy (\lam U => ∃ (V W : Set E) (C V) (D V W) (U = V ∧ W))
| cauchy-open {S : Set E} : isOpen S <-> ∀ {x : S} (isCauchy \lam U => U x -> U ⊆ S)
\default isOpen S : \Prop => ∀ {x : S} (isCauchy \lam U => U x -> U ⊆ S)
-- We omit the rest of the class
}
\class CoverSpace \extends PrecoverSpace {
| isRegular {C : Set (Set E)} : isCauchy C -> isCauchy \lam V => ∃ (U : C) (V <== U)
}
\type \infix 4 <== {X : PrecoverSpace} (V U : Set X) : \Prop
=> isCauchy \lam W => Given (V ∧ W) -> W ⊆ U
Completions, the relation to locales and other results from [29] have been formalized in arend-lib, in the modules Complete and Locale under Topology/CoverSpace. Metric and normed spaces are integrated into this hierarchy: pseudometric spaces are defined as an extension of UniformSpace whose uniform covers are those refined by the covers by balls of a fixed radius, so all of the above applies to them. On this basis arend-lib develops the constructive theory of real numbers, series and power series, differentiation (both the topological notion of Section 6.1.2 and a synthetic one), Banach spaces and algebras, commutative -algebras and the beginnings of measure theory.
Algebra
Algebraic geometry. The part of library arend-lib devoted to algebraic geometry contains basics of the theory of schemes. The constructive theory of schemes developed in arend-lib is based on locales, which are better suited for constructive algebraic geometry than topological spaces as explained in Section 6.1.2.
Schemes in arend-lib are defined in terms of locally ringed locales as follows:
A ringed locale is a locale together with a ring-valued sheaf on it:
\record RingedLocale (\coerce L : Locale) (R : VSheaf CRingCat L)
-- Here 'VSheaf D C' is the type of D-valued sheaves on a site C (i.e. on a category
-- with a covering for objects). Note that 'Locale' extends 'Site'.
-- 'R a' abbreviates 'R.F a', the ring of sections over the open 'a : L', and
-- 'R.F.Fun ba : RingHom (R a) (R b) is the restriction along 'ba : b <= a'.
Standardly, locally ringed spaces are defined as ringed spaces such that the stalk at every point is a local ring. This definition is not suitable for locales since it refers to points and this
does not work constructively as explained in § 7.1.2. Nevertheless, a locally ringed locale can be defined by using an alternative formulation of the locality condition which is classically equivalent to the standard one: for every section over the two opens on which , respectively , is invertible cover .
\record LocallyRingedLocale \extends RingedLocale {
| isLRLNonTrivial (a : L) : 0 = {R a} 1 -> a <= bottom
| isLocallyRinged (a : L) (x : R a) : a <= Join (\lam b => \Sigma (p : b <= a)
(Inv (R.F.Func p x) || Inv (R.F.Func p (x + 1))))
-- ’Join’ here is the join of a subset of ’L’ (see the previous section)
}
Earlier versions of arend-lib defined a scheme as a locally ringed locale which is locally equal (by univalence, equivalently locally isomorphic) to the spectrum of a ring. The current version avoids referring to the spectrum in the definition and instead expresses affineness of an open intrinsically, in terms of localizations of the ring of sections over . The building block is the notion of a principal open: is the largest open on which a given section over becomes invertible.
-- Both definitions below are dynamic members of ’\record RingedLocale’
\protected \func IsPrincipalOpenAt {a b : L} (ba : b <= a) (x : R a) : \Prop
=> Given (Inv (R.F.Func ba x)) ∀ {c} (ca : c <= a) (Inv (R.F.Func ca x)) (c <= b)
\type IsAffineOpen (a : L) => Given
-- 1. the sections over a principal open ’b <= a’ are the localization of ’R a’
-- at the powers of the corresponding section
(∀ {x : R a} {b} (ba : b <= a) (IsPrincipalOpenAt ba x)
(Localization (powers x) (R b) (R.F.Func ba)))
-- 2. if a principal open ’b <= a’ is covered by ’U’, then the corresponding
-- section lies in the radical of the ideal generated by the sections
-- cutting out the principal opens subordinate to ’U’
(∀ {b} (ba : b <= a) (x : R a) (IsPrincipalOpenAt ba x) {U} (b<=U : b <= Join U)
((Ideal.sclosure \lam y => ∃ (d : U) (c : L) (c <= d) (cb : c <= b)
(Localization (powers y) (R c) (R.F.Func (cb <=◦ ba)))).radical x))
-- 3. principal opens form a basis below ’a’
(∀ {b} (ba : b <= a) (b <= Join \lam c => Given (cb : c <= b)
∃ (x : R a) (IsPrincipalOpenAt (cb <=◦ ba) x)))
\func IsAffineScheme : \Prop => IsAffineOpen top
A scheme is then simply a locally ringed locale covered by affine opens:
\record Scheme \extends LocallyRingedLocale
| isLocallyAffine : top <= Join IsAffineOpen
Affine schemes themselves are constructed not by presenting the frame of opens of Spec directly, but through an intermediate notion of a scheme site: a preorder of “formal principal opens” together with a ring-valued presheaf on it such that restriction along always exhibits as a localization of , in a way stable under further restriction.
\record SchemeSite (\coerce P : Preorder) (R : Functor P.op CRingBicat) {
| loc-stable {a’ a b : P} (r : a’ <= a) (p : b <= a) : ∃ (b’ : P) (p’ : b’ <= a’)
(b’ <= b) (x : R a) (Localization (powers x) (R b) (R.Func p))
(Localization (powers (R.Func r x)) (R b’) (R.Func p’))
}
\func IsLocalizationAt {a b : P} (ba : b <= a) (x : R a) : \Prop
=> Localization (powers x) (R b) (R.Func ba)
-- ’P’ is turned into a preorder site (see the previous section) whose basic covers
-- are the families of principal opens whose defining sections generate the unit ideal
\func toSite : PreorderSite \cowith
| Preorder => P
| isBasicCover a U => Ideal.sclosure (\lam x => ∃ (b c : P) (b <= c) (U c)
(ba : b <= a) (IsLocalizationAt ba x)) 1
| basic-cover-stable => -- ... (uses ’loc-stable’)
\func toLocale : Locale => SiteLocale toSite -- the reflection of ’toSite’ into locales
\func toSheaf : VSheaf CRingCat toSite -- ’R’ is a sheaf for these covers
}
-- A scheme site is ’saturated’ if every section already cuts out an object of ’P’
\record SatSchemeSite \extends SchemeSite {
| loc-exists {a : P} (x : R a) : ∃ (b : P) (p : b <= a) (Localization (powers x) (R b) (R.Func
p))
\lemma basis-affineOpen {a : P} : toLRLSite.toLocale.IsAffineOpen (SiteLocale.embed a)
\func toScheme : Scheme \cowith
| LocallyRingedLocale => toLRLSite.toLocale
| isLocallyAffine {x} _ => cover-refl $ inP (SiteLocale.embed x, basis-affineOpen, cover-refl
idp)
}
-- Every scheme site can be saturated by adjoining formal localizations
\func SatSite (S : SchemeSite) : SatSchemeSite
The spectrum of a ring is obtained from the one-object scheme site. The projective spectrum of a graded ring uses the preorder of positive-degree homogeneous elements ordered by divisibility, with the degree-zero parts of their localizations as its rings of sections:
\func Spec (R : CRing) : Scheme
=> (satSite R).toScheme
\where {
\func site (R : CRing) : SchemeSite \cowith
| P => TrivialPoset -- a single object
| R { | F _ => R | Func _ => RingHom.id | Func-id => idp | Func-o => idp }
| loc-stable _ _ => inP ((), (), (), 1, Localization.id1, Localization.id1)
\func satSite (R : CRing) : SatSchemeSite => SatSite (site R)
\lemma isAffineScheme : (Spec R).IsAffineScheme => -- ...
}
\func Proj (R : GradedCRing) : Scheme => (site R).toScheme
Finally, Spec is shown to be right adjoint to the global sections functor, with the affine schemes cut out exactly by the unit of this adjunction being an isomorphism. This is the place where univalence for the category of locales (the field univalence of FrameCat above) is used.
-- The unit of the adjunction between affine schemes and locally ringed locales
\func specUnit {X : LocallyRingedLocale} : LocallyRingedLocaleHom X (Spec X.GlobalSections)
\lemma IsAffineScheme-char {X : LocallyRingedLocale} : X.IsAffineScheme <-> (specUnit {X}).IsIso
\func SpecFunctor : FullyFaithfulFunctor CRingCat.op SatSchemeSitePrecat
\func SchemeSiteFunctor : FullyFaithfulFunctor SatSchemeSitePrecat LocallyRingedLocaleCat
\func SpecLRLFunctor : ReflectiveSubPrecat CRingCat.op LocallyRingedLocaleCat
-- affine schemes are a reflective subcategory of locally ringed locales,
-- the reflector being ’GlobalSections’ and the unit being ’specUnit’
Principal ideal domains. As we mentioned earlier (§ 4.2), domains are defined constructively as rings with apartness relation satisfying . According to the standard classical definition a domain is a Principal Ideal Domain (PID) if every ideal is principal, that is there exist such that is generated by : . This requirement is too strong for the intended constructive examples. For an arbitrary proposition , consider the ideal . If , decidable equality in lets us distinguish from . In the first case is false, since would put in ; in the second case implies . Conversely, a decision of makes either or . Thus the assertion that every ideal of is principal implies excluded middle, and cannot be used to establish constructively that is a PID.
A constructively more well-behaved property is the requirement that every finitely generated ideal be principal. This is equivalent to the Bezout condition, which is defined in arend-lib as follows:
\func IsBezout => \Pi (a b : E) -> ∃ (s t : E) (LDiv (s * a + t * b) a) (LDiv (s * a + t * b) b)
\class BezoutRing \extends CRing, GCDMonoid {
| isBezout : IsBezout
| isGCD a b => -- proof of TruncP (GCD a b)
| gcd-ldistr c {a} {b} {z} (g : GCD a b z) => -- proof of TruncP (GCD (c * a) (c * b) (c * z))
}
where LDiv x y is the type of left divisors and GCD is the type of greatest common divisors:
\record DivBase {M : Monoid} (\coerce val : M) (elem inv : M)
\record LDiv \extends DivBase
| inv-right : val * inv = elem
\record GCD {M : CMonoid}
(val1 val2 : M) (\coerce res : M)
(res|val1 : LDiv res val1)
(res|val2 : LDiv res val2)
(res-univ : \Pi (g : M) -> LDiv g val1 -> LDiv g val2 -> LDiv g res)
Now, if we assume LEM, then the classical definition of PID can be equivalently reformulated as follows: PID is a domain satisfying Bezout condition and such that all ideals are finitely generated. The latter condition is one of equivalent definitions of Noetherian property assuming LEM. Constructively, however, this condition is too strong. Instead, we say that a ring is weakly Noetherian if for every ascending sequence of finitely generated ideals of there is such that .
\class WeaklyNoetherianCRing \extends CRing
| isWeaklyNoetherian (I : Nat -> Ideal \this) : (\Pi (n : Nat) -> (I n).IsFinitelyGenerated) ->
Ideal.ChainCondition I
-- function accompanying the class ’Ideal’
\func ChainCondition {R : CRing} (I : Nat -> Ideal R) =>
(\Pi (n : Nat) {a : R} -> I n a -> I (suc n) a) -> ∃ (n : Nat) ∀ {a} (I (suc n) a -> I n a)
The condition above is the weakest of several constructive readings of the Noetherian property, and it is the one PIDs are required to satisfy. The library also has a stronger notion, phrased in terms of bar induction rather than of sequences, which avoids the choice needed in passing from an indefinitely extendible finite chain to an infinite sequence; this is the class NoetherianCRing extending WeaklyNoetherianCRing, and it is what Euclidean domains are shown to satisfy.
\func IsNoetherian (R : CRing) : \Prop => Bar (PausesElem {R}) nil
-- ’PausesElem l’ holds if some element of the array ’l’ lies in the ideal generated
-- by the elements after it. The inductive predicate ’Bar P l’ is generated by
-- P l, or by Bar P (a :: l) for every a. It implies that every infinite
-- extension meets P; the converse is not part of its definition.
\class NoetherianCRing \extends WeaklyNoetherianCRing
| isNoetherian : IsNoetherian \this
| isWeaklyNoetherian I Ifg Ic => -- derivation of the chain condition from the bar
\class EuclideanDomain \extends PID, NoetherianCRing
In arend-lib PIDs are defined as domains satisfying Bezout condition, the weak Noetherian property and such that equality is a decidable predicate. For Bezout rings the weak Noetherian property admits an equivalent formulation which is more convenient to work with. To state it, consider equivalence relation on and consider the quotient monoid . Then every sequence satisfying necessarily has for some if and only if satisfies the weak Noetherian condition.
The combination of the Bezout condition and the weak Noetherian property places PIDs in an important class of domains known as Smith domains. The distinguishing property of Smith domains is existence of the Smith normal form for matrices over them. Namely, for every , matrix over a Smith domain there exist invertible matrices , over such that is diagonal matrix followed by zero matrix and . In other words, if we say for matrices if there exist invertible , such that , then for every there exist a matrix in the normal form such that . Among discrete Bezout domains, the Smith property is equivalent to the Kaplansky condition.
\class SmithRing \extends StrictBezoutRing {
| isKaplansky : IsKaplansky \this
-- Dynamic lemma (using \this parameter)
\lemma toSmith {n m : Nat} (A : Matrix E n m) : ∃ (B : Matrix E n m) (IsSmith B) (A M~ B)
=> Smith-char 0 3 (isStrictBezout,isKaplansky) A
} \where {
\type IsKaplansky (R : CRing) => \Pi (a b c : R) -> IsCoprimeArray (a,b,c) -> ∃ (t s : R)
(IsCoprime (t * a) (t * b + s * c))
-- The Smith normal form theorem is proven as part of the equivalence below
\lemma Smith-char {R : CRing} : TFAE
-- The four conditions below are equivalent
\Sigma R.IsStrictBezout (IsKaplansky R),
\Sigma R.IsStrictBezout (\Pi (A : Matrix R 2 2) -> A 1 0 = 0 -> IsCoprimeArray (A 0 0, A 0 1,
A 1 1) -> ∃ (B : Matrix R 2 2) (IsDiagonal B) (A M~ B)),
-- here M~ is equivalence as in the Smith normal form
\Pi {n m : Nat} -> n <= m -> m <= 2 -> \Pi (A : Matrix R n m) -> ∃ (B : Matrix R n m)
(IsDiagonal B) (A M~ B),
\Pi {n m : Nat} (A : Matrix R n m) -> ∃ (B : Matrix R n m) (IsSmith B) (A M~ B)
) => -- ...
}
\class SmithDomain \extends BezoutDomain.Dec, SmithRing
Since PIDs are Smith domains, in arend-lib they are defined as extension:
\class PID \extends SmithDomain, WeaklyNoetherianCRing {
| divChain : CMonoid.DivChain {DivQuotientMonoid nonZeroCMonoid}
| isWeaklyNoetherian I Ifg => Ideal.fromMonoidChainCondition
(IntegralDomain.Dec.fromNonZeroDivChain divChain) I \lam n =>
bezout_finitelyGenerated_principal.1 isBezout (Ifg n) -- f.g. ideals
-- are principal in Bezout rings
| isKaplansky => adequate_kaplansky \lam a/=0 => adequate'_adequate (domain_adequate' divChain
a/=0)
-- PIDs have Krull dimension at most one
\lemma is1Dim : Dim<= 1
=> bezout_1Dim<->adequate'.2 \lam a/=0 => domain_adequate' divChain a/=0
}
The proof of Kaplansky condition goes via the proof of the adequate condition for PIDs first, following Helmer [22] and Kaplansky [30]. The dimension condition used above is defined as follows:
-- Dynamic type (using \this parameter) in CRing class
\type Dim<= (k : Nat) => \Pi (x : Array E (suc k)) ->
∃ (a : Array E (suc k)) (m : Array Nat (suc k)) (fold x a m = 0)
\where
\func fold {k : Nat} (xs as : Array E k) (ms : Array Nat k) : E \elim k, xs, as, ms
| 0, nil, nil, nil => 1
| suc k, x :: xs, a :: as, m :: ms => pow x m * (fold xs as ms - x * a)
Polynomials of one or several variables. Polynomials of one variable over any pointed type (a type with 0) have two equivalent representations in arend-lib: as an inductive type with conditions Poly and as a quotient set QPoly. Both are essentially arrays of coefficients quotiented by cutting trailing zeros, but sometimes it is more convenient to work with Poly instead of QPoly and vice versa.
\data Poly (R : AddPointed)
| pzero
| padd (Poly R) R
| peq : padd pzero 0 = pzero
\func QPoly (R : AddPointed) => Quotient {Array R} (__ = __ ++ 0 :: nil)
Multivariate polynomials are defined as a monoid algebra:
\func MPoly (J : \Set) (R : CRing) => MonoidAlgebra (PermSetMonoid J) R
\instance PermSetMonoid (A : \Set) : CMonoid (PermSet A)
\type PermSet (A : \Set) => Quotient {Array A} EPerm
-- here the relation EPerm l l’ holds iff l’ can be obtained by permuting elements in l
Matrices over commutative rings. The library arend-lib defines matrices over any type as two-dimensional arrays and then formalizes operations on matrices and their properties for a variety of structures on . In case of commutative rings arend-lib has definitions of determinant, characteristic polynomial and proofs of a number of their properties including the proof of Cayley-Hamilton theorem.
\func determinant {R : CRing} {n : Nat} (M : Matrix R n n)
=> R.FinSum \lam (e : Sym n) => sign e * R.BigProd (\lam j => M (e j) j)
\func charPoly {R : CRing} {n : Nat} (M : Matrix R n n) : Poly R
=> determinant $ padd 1 0 *c matrix-map (padd 0) 1 - matrix-map (padd 0) M
-- det (x * I - M)
-- ’matrix-map’ maps in this case a matrix over ’R’ to a matrix over ’Poly R’
\lemma cayley-hamilton {R : CRing} {n : Nat} (A : Matrix R n n)
: polyMapEval (CAlgebra.coefHom {MatrixAlgebra R n}) (charPoly A) A = 0
-- ’polyMapEval’ converts a polynomial over R to polynomial over ’MatrixAlgebra R n’
-- and then evaluates it at the matrix A
=> -- ...
Among the properties of determinant formalized in arend-lib is the cofactor expansion and the existence of adjugate matrices.
\func adjugate {R : CRing} {n : Nat} (M : Matrix R n n) : Matrix R n n \elim n
| 0 => M
| suc n => mkMatrix \lam i j => Monoid.pow -1 (j + i) * determinant (minor M j i)
\lemma adjugate-left {R : CRing} {n : Nat} {M : Matrix R n n} : adjugate M * M = determinant M *c 1
=> -- ...
\lemma adjugate-right {R : CRing} {n : Nat} {M : Matrix R n n}
: M * adjugate M = determinant M *c 1
=> -- ...
As a corollary we have that is invertible if and only if is invertible.
\lemma determinant-inv {R : CRing} {n : Nat} {M : Matrix R n n} : Inv M <-> Inv (determinant M)
Another corollary is Nakayama’s lemma, which says the following. Let be a commutative ring, an ideal and a finitely generated module over . If then there exist such that such that .
\lemma nakayama {R : CRing} {M : LModule R} {I : Ideal R} (fg : M.IsFinitelyGenerated)
(c : topSubLModule M <= I *m topSubLModule M)
: ∃ (e : R) (I (1 - e)) ∀ (m : M) (e *c m = 0)
Linear algebra over Smith domains. Here we sketch some elements of linear algebra over Smith domains formalized in arend-lib.
Definition of the rank of a matrix over a Smith domain:
\func rank {R : SmithDomain} {n m : Nat} (A : Matrix R n m) : Nat => -- ...
Let be a Smith domain. For any finite-dimensional free modules , over and every linear the image and the kernel modules are finite-dimensional free.
\class FinModule \extends LModule
| isFinModule : ∃ (l : Array E) (IsBasis l)
\instance image-fin {R : SmithDomain} {U V : FinModule R} (f : LinearMap U V) : FinModule
| LModule => ImLModule f
| isFinModule => \case U.isFinModule, V.isFinModule \with {
| inP (lu,bu), inP (lv,bv) => TruncP.map (basis f bu bv) \lam s => (s.1,s.2)
}
\where {
\protected \lemma basis {U V : LModule R} (f : LinearMap U V) {lu’ : Array U}
(bu’ : U.IsBasis lu’) {lv’ : Array V} (bv’ : V.IsBasis lv’)
: ∃ (l : Array (ImLModule f)) (IsBasis {ImLModule f} l)
(l.len = rank (LinearMap.toMatrix lu’ bv’ f))
=> -- ...
}
\instance kernel-fin {R : SmithDomain} {U V : FinModule R} (f : LinearMap U V) : FinModule
| LModule => IModule (KernelLModule f)
| isFinModule => -- ...
Let be a Smith domain and a finite-dimensional free module over . Linear dependence for a set of vectors in is decidable.
\func dependency-dec {R : SmithDomain} {U : FinModule R} (l : Array U)
: Or (U.IsDependent l) (U.IsIndependent l)
Algebraic closure of countable, discrete fields. The library arend-lib defines integral extensions of rings, splitting fields for polynomials over discrete fields and algebraic closure for countable, discrete fields.
\func isIntegral (f : RingHom) (x : f.Cod) : \Prop
=> ∃ (p : Poly f.Dom) (isMonic p) (polyEval (polyMap f p) x = 0)
The library proves that an integral algebra over a discrete field is 0-dimensional. The condition can equivalently be expressed as follows:
-- Dynamic type (using \this parameter) in Ring class
\type IsZeroDimensional => \Pi (a : E) -> ∃ (b : E) (n : Nat) (pow a n = pow a (suc n) * b)
A discrete field is a commutative ring such that every element is either zero or invertible (see § 4.2 for a definition of a field).
\class DiscreteField \extends Field, EuclideanDomain {
| finv : E -> E
| finv_zro : finv 0 = 0
| finv-right {x : E} (x/=0 : x /= 0) : x * finv x = 1
\field eitherZeroOrInv (x : E) : (x = 0) || Inv x
}
\func integralExt-zeroDim {K : DiscreteField} {R : CRing} {f : RingHom K R} (fi : isIntegralExt f)
: R.IsZeroDimensional
=> -- ...
The definition of a splitting field for a polynomial:
\type IsSplittingField {k K : DiscreteField} (p : Poly k) (f : RingHom k K)
=> ∃ (l : Array K) (c : K) (RingHom.isAlgebraGenerated f l)
(polyMap f p = c PolyRing.*c Monoid.BigProd (map (\lam a => padd 1 (negative a)) l))
A ring is algebraically closed if every monic polynomial over of non-zero degree has a root.
\type IsAlgebraicallyClosed (K : Ring)
=> \Pi {p : Poly K} -> ∃ (n : Nat) (n /= 0) (degree<= p n) (polyCoef p n = 1) -> ∃ (a : K)
(polyEval p a = 0)
Every countable discrete field has an algebraic closure:
\sfunc countableAlgebraicClosure {k : DiscreteField} (c : Countable k)
: \Sigma (K : DiscreteField) (f : RingHom k K) (IsAlgebraicClosure f)
=> -- ...
The Fundamental Theorem of Algebra. The module Arith/Complex/FTA formalizes Richman’s formulation [49]: every monic polynomial of degree determines a point in the completion of the space of unordered -tuples of complex numbers. This represents its roots with multiplicities, determines the polynomial, and depends continuously on its coefficients. The construction uses Kneser’s approximate-root argument and Cauchy filters of approximate factorizations, without choice. The module Arith/Algebraic/FTA obtains actual roots for nonconstant separable monic polynomials by Newton iteration, proves root existence for nonconstant polynomials over discrete subfields of C, and shows that the algebraic numbers are algebraically closed. Finally, Arith/Complex/FTA/Classical derives root existence for arbitrary monic nonconstant complex polynomials using countable choice.
Other parts of the library
Synthetic homotopy theory
All of the synthetic homotopy theory developed in the HoTT Book [57] has been formalized in arend-lib. Parts of this formalization were carried out with AI assistance; the resulting proofs are Arend terms subject to the same type checking as manually written proofs. This development includes:
Pointed types, loop spaces, homotopy groups, and the Eckmann–Hilton argument.
Higher inductive constructions: the circle, spheres, the torus, suspensions, joins, and pushouts.
The hierarchy of -levels, -truncations, connected types and connected maps.
The equivalence , the fundamental group of the circle, and covering spaces.
Fibrations and the long exact sequence of homotopy groups; the Hopf fibration with total space and the calculation .
The Freudenthal suspension theorem and the calculations for and for .
The van Kampen theorem and Whitehead’s theorem for -types.
Eilenberg–MacLane spaces and the equivalence .
Localizations, modalities, and the generalized Blakers–Massey theorem.
Further topics
The parts of arend-lib selected above are far from exhaustive. We close with a very brief list of the remaining major topics, to indicate the overall coverage of the library.
Group theory. Subgroups, quotients, products, free groups, symmetric and automorphism groups, Lagrange’s theorem, group actions (-sets) and their category, and linear representations: intertwining maps, irreducibility, Maschke’s lemma and characters.
More commutative algebra. Ideals (including graded ones) and factor rings, localization, integral and integrally closed extensions, minimal polynomials, valuations, Euclidean domains, GCD and Bezout domains, zero-dimensional and reduced rings, Noetherian rings with the Hilbert basis theorem, graded rings, monoid rings, formal power series, Boolean rings, and the Grothendieck ring.
More linear algebra. Modules and their category, submodules, bilinear maps, linear maps and their matrices, tensor products, traces, and vector spaces.
Numbers. Natural numbers, integers and rationals; the constructive reals (including lower and upper reals, roots, the intermediate value theorem, and ); exponentials and logarithms; trigonometric functions; and the complex numbers, with the argument, roots and Euler’s formula. On the number-theoretic side: primality, Euler’s totient function, factorials, binomial coefficients and combinations.
Logic and rewriting. Classical principles and their interrelations, TFAE for stating chains of equivalent conditions, accessibility and well-founded induction, bar induction and the fan theorem, first-order algebraic theories with their models and free models, and a substantial development of term rewriting: abstract reduction systems, confluence and termination, higher-order rewriting systems — with the -calculus as a worked example — and modularity of confluence for unions of rewriting systems.
Sets, finiteness and data. Subsets, filters, decidable and Kuratowski finiteness, the pigeonhole principle, countability, Hedberg’s theorem, and the category of sets; lists, arrays with sorting and permutations, and sequential colimits.
Order theory. Partial, linear and strict orders, lattices and complete lattices, Heyting and Boolean algebras, directed sets, and lexicographic orders.
Solvers. A family of metas discharging equational goals in a given algebraic structure: semigroups, monoids, groups, semirings, rings and Boolean rings (in commutative and non-commutative variants), linear arithmetic over ordered rings, linear algebra, and composites of morphisms in a category.
References
- [1]Tudor Achim, Alex Best, Kevin Der, et al. Aristotle: IMO-level automated theorem proving. arXiv:2510.01346, 2025.arxiv.org/abs/2510.01346
- [2]Thorsten Altenkirch. Extensional equality in intensional type theory. In Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, LICS ’99. IEEE Computer Society, 1999.
- [3]Carlo Angiuli, Guillaume Brunerie, Thierry Coquand, Robert Harper, Kuen-Bang Hou (Favonia), and Daniel R. Licata. Syntax and models of cartesian cubical type theory. Mathematical Structures in Computer Science, 31(4):424–468, 2021.DOI
- [4]Carlo Angiuli, Kuen-Bang Hou (Favonia), and Robert Harper. Computational higher type theory iii: Univalent universes and exact equality. arXiv:1712.01800, 2017.arxiv.org/abs/1712.01800
- [5]Anthropic. Formalizing Fermat’s Last Theorem. Anthropic research announcement, September 2026. Formal proof: Lean repository.
- [6]Arend site. https://arend-lang.github.io.
- [7]Gilles Barthe, Venanzio Capretta, and Olivier Pons. Setoids in type theory. Journal of Functional and Logic Programming, 13:261–293, 2003. Special Issue on Logical Frameworks and Metalanguages.
- [8]Jean-philippe Bernardy, Patrik Jansson, and Ross Paterson. Proofs for free: Parametricity for dependent types. J. Funct. Program., 22(2):107–152, March 2012.
- [9]Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program Development: Coq’Art: The Calculus of Inductive Constructions. Springer, 2004.
- [10]Rafaël Bocquet. External univalence for second-order generalized algebraic theories. arXiv:2211.07487, 2022.arxiv.org/abs/2211.07487
- [11]Denis-Charles Cisinski, Bastiaan Cnossen, Kim Nguyen, and Tashi Walde. Formalization of higher categories. https://drive.google.com/file/d/11Kaq7watGG13xvjqw9qHjm6SDPFJ2-0o/view.
- [12]Cyril Cohen, Thierry Coquand, Simon Huber, and Anders Mörtberg. Cubical type theory: A constructive interpretation of the univalence axiom. In 21st International Conference on Types for Proofs and Programs (TYPES 2015), volume 69 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:34. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
- [13]Cyril Cohen, Maxime Dénès, and Anders Mörtberg. Refinements for free! In Certified Programs and Proofs: Third International Conference, CPP 2013, Melbourne, VIC, Australia, December 11-13, 2013, Proceedings, page 147–162, Berlin, Heidelberg, 2013. Springer-Verlag.DOI
- [14]Thierry Coquand, Randy Pollack, and Makoto Takeyama. A logical framework with dependently typed records. Fundam. Inf., 2004.
- [15]Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction—CADE 28, volume 12699 of Lecture Notes in Computer Science, pages 625–635. Springer, 2021.DOI
- [16]Cesare Gallozzi. Homotopy Type-Theoretic Interpretations of Constructive Set Theories. PhD thesis, University of Leeds, July 2018. https://etheses.whiterose.ac.uk/22317/.DOI
- [17]Georges Gonthier. Formal proof—the Four-Color Theorem. Notices of the American Mathematical Society, 55(11):1382–1393, 2008.
- [18]Georges Gonthier, Andrea Asperti, Jeremy Avigad, Yves Bertot, Cyril Cohen, François Garillot, Stéphane Le Roux, Assia Mahboubi, Russell O’Connor, Sidi Ould Biha, Ioana Pasca, Laurence Rideau, Alexey Solovyev, Enrico Tassi, and Laurent Théry. A machine-checked proof of the Odd Order Theorem. In Interactive Theorem Proving (ITP 2013), volume 7998 of Lecture Notes in Computer Science, pages 163–179. Springer, 2013.DOI
- [19]Daniel Gratzer, Jonathan Weinberger, and Ulrik Buchholtz. Directed univalence in simplicial homotopy type theory. https://arxiv.org/pdf/2407.09146.
- [20]Cordelia V. Hall, Kevin Hammond, Simon L. Peyton Jones, and Philip L. Wadler. Type classes in haskell. ACM Trans. Program. Lang. Syst., page 109–138, 1996.
- [21]Robert Harper and Mark Lillibridge. A type-theoretic approach to higher-order modules with sharing. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’94, page 123–137. Association for Computing Machinery, 1994.DOI
- [22]Olaf Helmer. The elementary divisor theorem for certain rings without chain condition. Bulletin of the American Mathematical Society, 49(4):225–236, 1943.DOI
- [23]M. Hofmann. Extensional Concepts in Intensional Type Theory. Thesis. University of Edinburgh, Department of Computer Science, 1995.
- [24]Simon Huber. Canonicity for cubical type theory. Journal of Automated Reasoning, 63:173–210, 2019.arxiv.org/abs/1607.04156
- [25]Thomas Hubert, Rishi Mehta, Laurent Sartran, et al. Olympiad-level formal mathematical reasoning with reinforcement learning. Nature, 651:607–613, 2026.DOI
- [26]Valery Isaev. Canonicity for homotopy type theory with an interval type. Unpublished, undated manuscript.
- [27]Valery Isaev. Homotopy type theory with an interval type. Unpublished manuscript, https://valis.github.io/doc.pdf.
- [28]Valery Isaev. Models of homotopy type theory with an interval type. arXiv:2004.14195, 2020.arxiv.org/abs/2004.14195
- [29]Valery Isaev. A constructive approach to complete spaces, 2024. Available at: https://arxiv.org/abs/2412.20835.
- [30]Irving Kaplansky. Elementary divisors and modules. Transactions of the American Mathematical Society, 66:464–491, 1949.
- [31]Chris Kapulkin and Peter LeFanu Lumsdaine. The simplicial model of univalent foundations (after voevodsky). arXiv:1211.2851, 2018.
- [32]Krzysztof Kapulkin and Peter LeFanu Lumsdaine. Homotopical inverse diagrams in categories with attributes. Journal of Pure and Applied Algebra, 2021.arxiv.org/abs/1808.01816
- [33]Nikolai Kraus. On the role of semisimplicial types. https://nicolai kraus.github.io/docs/on_semisimplicial_types.pdf.
- [34]Xavier Leroy. Manifest types, modules, and separate compilation. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’94, page 109–122. Association for Computing Machinery, 1994.DOI
- [35]Nuo Li. Quotient types in type theory. PhD thesis, University of Nottingham, https://eprints. nottingham.ac.uk/28941/, July 2015.
- [36]H. Lombardi and C. Quitté. Commutative Algebra: Constructive Methods: Finite Projective Modules. Algebra and Applications. Springer Netherlands, 2015.
- [37]Zhaohui Luo. Manifest fields and module mechanisms in intensional type theory. In Types for Proofs and Programs: International Conference, TYPES 2008 Torino, Italy, March 26-29, 2008 Revised Selected Papers, page 237–255. Springer-Verlag, 2009.DOI
- [38]Nicolas Magaud and Yves Bertot. Changing data structures in type theory: A study of natural numbers. In Selected Papers from the International Workshop on Types for Proofs and Programs, TYPES ’00, page 181–196, Berlin, Heidelberg, 2000. Springer-Verlag.
- [39]Per Martin-Löf. Intuitionistic Type Theory. Studies in Proof Theory. Bibliopolis, Naples, 1984. Notes by Giovanni Sambin.
- [40]R. Mines, F. Richman, and W. Ruitenburg. A Course in Constructive Algebra. Springer, New York, 1987.
- [41]Mistral AI. Leanstral: Open-source foundation for trustworthy vibe-coding. https://mistral.ai/ news/leanstral/, March 2026.
- [42]Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel. Isabelle/HOL: A Proof Assistant for Higher-Order Logic, volume 2283 of Lecture Notes in Computer Science. Springer, 2002.DOI
- [43]Ulf Norell. Towards a Practical Programming Language Based on Dependent Type Theory. PhD thesis, Chalmers University of Technology and Göteborg University, 2007.
- [44]OpenAI. Finite time blowup for Navier–Stokes and Euler equations. Lean formalization repository, September 2026.
- [45]OpenAI. Sharing AI progress in mathematics. Research announcement, October 2026. Manuscripts and Lean formalisations. Accessed October 2026.
- [46]PFR project contributors. The Polynomial Freiman–Ruzsa Conjecture: A digitisation of the proof in Lean 4. https://teorth.github.io/pfr/. Formalization project. Accessed October 2026.
- [47]Z. Z. Ren, Zhihong Shao, Junxiao Song, et al. DeepSeek–Prover-V2: Advancing formal mathematical reasoning via reinforcement learning for subgoal decomposition. arXiv:2504.21801, 2025.arxiv.org/abs/2504.21801
- [48]John C. Reynolds. Types, abstraction and parametric polymorphism. In IFIP Congress, 1983.
- [49]Fred Richman. The fundamental theorem of algebra: A constructive development without choice. Pacific Journal of Mathematics, 196(1):213–230, 2000.DOI
- [50]Egbert Rijke. Introduction to homotopy type theory. arXiv:2212.11082, 2022.arxiv.org/abs/2212.11082
- [51]Claudio Sacerdoti Coen and Enrico Tassi. Working with mathematical structures in type theory. In Types for Proofs and Programs, pages 157–172. Springer Berlin Heidelberg, 2008.
- [52]Christian Sattler. The interval cannot be trivially fibrant. https://www.cse.chalmers.se/~sattler/docs/interval-non-fibrant.txt. Unpublished note recording an argument of Thierry Coquand.
- [53]Konrad Slind and Michael Norrish. A brief overview of HOL4. In Theorem Proving in Higher Order Logics (TPHOLs 2008), volume 5170 of Lecture Notes in Computer Science, pages 28–32. Springer, 2008.DOI
- [54]Bas Spitters and Eelis van der Weegen. Type classes for mathematics in type theory. Mathematical Structures in Computer Science, 21:795–825, 2011.arxiv.org/abs/1102.1323
- [55]Nicolas Tabareau, ÉricTanter, and Matthieu Sozeau. The marriage of univalence and parametricity. Journal of the ACM, 68(1):5:1–5:44, 2021.arxiv.org/abs/1909.05027
- [56]The Mathlib Community. Completion of the Liquid Tensor Experiment. Lean community blog, July 2022.
- [57]The Univalent Foundations Program. Homotopy Type Theory: Univalent Foundations of Mathematics. https://homotopytypetheory.org/book, Institute for Advanced Study, 2013.arxiv.org/abs/1308.0729
- [58]Andrea Vezzosi, Anders Mörtberg, and Andreas Abel. Cubical agda: a dependently typed programming language with univalence and higher inductive types. Proc. ACM Program. Lang., 2019.
- [59]Steven Vickers. Localic completion of generalized metric spaces II: Powerlocales. Journal of Logic & Analysis, 1(11):1–48, 2009.DOI
- [60]Vladimir Voevodsky. The origins and motivations of Univalent Foundations. The Institute Letter, Institute for Advanced Study, https://www.ias.edu/ideas/2014/voevodsky-origins, 2014.
- [61]Philip Wadler. Theorems for free! In Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture, FPCA ’89, page 347–359, New York, NY, USA, 1989. Association for Computing Machinery.DOI
- [62]Tesla Zhang and Valery Isaev. (co)condition hits the path. arXiv:2405.12994, 2024.arxiv.org/abs/2405.12994
- [63]Théo Zimmermann and Hugo Herbelin. Automatic and transparent transfer of theorems along isomorphisms in the coq proof assistant. CoRR, abs/1505.05028, 2015.arxiv.org/abs/1505.05028

