WorksComputer Science
Hereditary permutations for simple types revisited: A baby case for University Algebra
Abstract
It is a classical result that the definable isomorphisms of the simply typed lambda-calculus with function types are exactly the hereditary permutations, and that they are generated by and congruence. We give a new proof of this result that stays inside beta-normal eta-long typed terms and uses no completeness theorem: an induction that descends through both components of an isomorphism at once. We then go one level up and prove a coherence theorem: two derivations of an isomorphism denote the same isomorphism if and only if they are equal modulo an explicit list of equations (groupoid laws, functoriality, involution, naturality and the braid equation), so these equations present the groupoid of isomorphisms, a hereditary version of the Coxeter presentation of the symmetric groups. All results are formalised in Agda, on intrinsically typed syntax with hereditary substitution, without postulates. The work is a case study for the syntactic completeness conjecture of University Algebra, a proposed solution of Tarski's high school algebra problem using dependent types, whose semantic counterpart is open. We explain the motivation and which parts of the method we expect to carry over.
Introduction
Motivation. University Algebra [2, 3] is a proposed answer to Tarski’s high school algebra problem: the usual laws for , , and exponentiation are incomplete for the positive integers [32], and so is their categorified version, isomorphisms of types with sums [15]. With dependent types a short list of basic isomorphisms, including the type-theoretic axiom of choice, derives all high school laws and Wilkie’s identity, and it is conjectured to be complete for finite sets. The conjecture splits into a semantic half (finite sets are complete for definable isomorphism), which is open, and a syntactic half: every definable isomorphism is derivable, and in the strong, coherence, form, derivations modulo a chosen set of equations between derivations (the level-2 equations) are in bijection with definable isomorphisms. Since the semantic half is not available, a proof of the syntactic half cannot go through a completeness theorem, unlike the classical proofs for simple types: it has to analyse the normal forms of invertible terms directly and read off a derivation.
This paper. We treat the baby case of this programme: the simply typed -calculus with only. Here the characterisation of definable isomorphisms is classical (Section 7): the invertible terms are the hereditary permutations [10], and with congruence generates them [6, 7]. Our aims are to find out which lemmas a purely syntactic proof needs, to prove the coherence form, and to check everything formally. The contributions are:
A direct proof that every invertible -normal -long term is a hereditary permutation (Theorem 3), by a descent that analyses both components of an isomorphism simultaneously (Section 4). It uses no completeness theorem and does not pass through the untyped calculus. It isolates the one point where the two inverse equations interact, and shows that relevance () is a consequence of the descent.
A coherence theorem (Theorem 4): derivations modulo an explicit list of level-2 equations are in bijection with hereditary permutations (Section 5). The proof is a hereditary version of the normal-form proof for the Coxeter presentation of the symmetric groups.
A formalisation of all results in Agda without postulates, on intrinsically typed de Bruijn syntax with hereditary substitution [20] (Section 6).
A discussion of which parts of the method should carry over to University Algebra (Section 8).
Setting
Types. , with ranging over base types. Every type can be written uniquely as , which we write .
Terms and normal forms. Terms are those of the simply typed -calculus, taken modulo . Every term has a unique -normal, -long form:1
where is in and . We write for hereditary substitution [31, 20], which substitutes and normalises at once, by recursion on the type of . For a variable , its -long form is
defined by recursion on the type. It is the normal form of the term , so is the identity map on . Composition of maps and is ; it is associative and is its unit, by the substitution lemmas for hereditary substitution.
Isomorphisms. An isomorphism is a pair , with
as syntactic equalities of normal forms: both composites are the identity. We call invertible. The inverse is unique: if is another, then . So being invertible is a property of alone.
Derivations. The relation is generated by the axiom
together with , , composition (in diagrammatic order) and the congruence for , . Derivations are the terms of this signature. Each derivation has a meaning , an isomorphism, defined by recursion on . Both parts of are , with input variable ; , and are interpreted by the identity, by exchanging and , and by composition; and the first part of is . We also write for its first part .
Level-2 equations. The equations between derivations are:
the groupoid laws, and congruence for , and ;
functoriality of : and ;
;
naturality of : ;
the braid (Yang–Baxter) equation on : .
We write for equality modulo these equations. Swaps at non-adjacent positions commute: this is naturality with . Together these are the Coxeter relations of the symmetric groups, applied hereditarily.
Normal forms of types. Modulo swap, a type is determined by and the multiset . Hereditarily, types modulo are rooted unordered trees: the root is labelled by , and each subtree is one .
Hereditary permutations and the main results
Definition 1. The hereditary permutations , for and with , are the normal terms
where is a permutation of and has free variable . The case gives at a base type.
Proposition 2 (Easy direction).
Every hereditary permutation is invertible, and the inverse is again a hereditary permutation (with and the inverses of the ).
The meaning of every derivation is a hereditary permutation: swap gives a transposition, and -congruence gives the .
Conversely, every hereditary permutation is the meaning of a derivation , which decomposes into adjacent transpositions (Section 5).
Theorem 3 (Characterisation). Every invertible normal term is a hereditary permutation.
Theorem 4 (Coherence). Taking meanings, \varphi\mapsto\llbrbracket\varphi\rrbracket, is a bijection from derivations of modulo to . In particular, if and only if .
Theorem 3 together with Proposition 2 gives completeness: iff iff and have the same tree. Theorem 4 is the analogue, for , of the coherence form of syntactic completeness for University Algebra.
Proof of the characterisation
We give the proof with de Bruijn indices and context morphisms, as in the formalisation: all freshness conditions of a named proof then become typing. Contexts are lists of types built from the empty context by extension . Variables are de Bruijn indices: is the last variable of (of type ), and is the variable of , seen in . So is , with written , and the identity becomes .
Throughout, and are mutually inverse, with and ; the equations are and , where substitutes for .
Strategy. The two equations are used one at a time. Each lemma is stated for one equation and then applied to both, using the symmetry . The two equations interact at a single point, the matching of heads in Lemma 8(c).
Substitutions
Contexts are lists of types, and a telescope is a context that extends another one: . A substitution is a normal form in for each type of . We write:
for the th component of ;
for simultaneous hereditary substitution, where ;
for composition, applying to each component of ;
for pairing, where and ;
for the weakening projection, and for the -expanded variables of .
Contexts and substitutions form a category, and , , satisfy the usual laws. A term is head-free if its head is not bound in . Components of and are head-free.
Lemma 5 (No creation). Let and . If a variable of occurs in , then occurs in for some variable of that occurs in . If , then .
Lemma 6 (Heads). Let and .
If is bound in , the head of is the same variable of .
If is a variable of and is head-free with head , then the head of is , weakened past .
Both lemmas are by induction on , and on the type for the second clause of Lemma 6.
The descent
Idea. We want to read off the structure of top-down: first its head, then the heads of its arguments, and so on. The only information is the pair of equations and , and they are about the whole terms. Write and . In the head is replaced by , so the arguments are substituted into the body of . Comparing with says that the head of must be the variable that receives , and that the arguments of these heads again satisfy two equations of the same kind, one level deeper. The difference is that the deeper equations live in a larger context: the variables bound on the way down, and the parts of and that were already substituted.
A matched pair is the general form of such a pair of equations. is a family of subterms of at the current depth, is the matching family of subterms of , and the parameter substitutions record what has been substituted so far. The initial pair is itself. Lemma 8 shows that the form is preserved when we step from a pair of heads to a pair of their arguments. So the descent is an induction over the normal forms and , but over both at once, along matched positions: argument of a head in goes with argument in . It is not structural induction on one term, because each step uses one equation for the heads of and the other for the heads of (part (c)). It terminates because the pair of types gets smaller.
Definition 7. A matched pair consists of:
contexts (the bases) and (the parameters);
telescopes and (the targets);
and ;
parameter substitutions , , and , all of whose components are head-free;
such that
The definition is symmetric under , which exchanges (P) and (Q). There are no freshness conditions: lives over , so it cannot mention the targets .
The initial pair. All bases and parameters are empty, , , , , and the parameter substitutions are empty. Then (P) is and (Q) is .
Lemma 8 (Descent). For a matched pair:
(a) (one-sided) for each , write . Then is a variable of the -part of , say the one at position of . Dually, the head of is the variable at position of .
(b) (one-sided) every variable of occurs in the body of ; dually for .
(c) and are mutually inverse; in particular .
(d) for each , let , and . Then the argument families of and of form a matched pair with
So the new parameter substitution is the substitution of the old equation , and is that of .
Proof. (a) Apply Lemma 6 to at component . The right-hand side is of the th variable of , whose head is that variable.
If is bound in , the head of the left-hand side is in .
If is in , the head of the left-hand side is the head of a component of , which is in , since is head-free.
Neither is in , so is in . The dual is the same argument applied to .
(b) By Lemma 5, the left-hand side of at is with the same binders as , and each of them occurs in . No component of a substitution mentions , so by no creation each variable of occurs in the body of .
(c), (d) In at , the head is replaced by . By (a) for , its head is the th variable of , which maps to an -expanded variable. So the left-hand side is . Comparing heads with gives . Comparing arguments gives
This uses the substitution lemma to regroup the iterated substitution as a single one. Dually, at gives and equation of the new pair. The new parameter substitutions are head-free: the components of are -expanded variables, and the components of and have heads in and by (a).
Corollary 9 (Relevance). and are -terms: every bound variable occurs in the body of its binder.
Proof. In an -long normal form, every is a top binder of the whole term or of an argument of a head variable. Starting from the initial pair, Lemma 8(d) reaches every argument of every head in and in : passes all of on. Part (b) applies at each level. The descent terminates: a step goes from the pair of types to a pair of argument types of and of , and this relation is well founded.
Remark 10 (One equation is not enough). A single equation makes a retract of , and retractions of simple types are much less rigid [26]:
The head of a section need not be its input: via and .
A section may erase: for and , we have but is not . In terms of the descent, holds but fails, and part (b) for is exactly what detects the vacuous .
This is why the descent needs the heads of both families at each level, taking one from each equation. Every other step is one-sided.
From relevance to hereditary permutations
Lemma 11 (Preservation). If and all components of are , then so is , and a variable of occurs in if and only if it occurs in some with occurring in .
Proof. “Only if” is Lemma 5, which holds for all terms. For “if”, the only way hereditary substitution loses material is through a -step in which does not occur in . First consider a single substitution and the application , for -terms. We prove three facts simultaneously:
the result is ;
(keep) every occurrence of a variable other than in survives;
(insert) if occurs in , every variable occurring in survives. Dually, every variable occurring in occurs in .
The induction is the one that defines hereditary substitution: on for substitution, on and the type for application. Insert for application uses : in the variable occurs in , so by insert, every variable of survives in . The simultaneous case follows by induction on , lifting under binders. The lifted substitution is again , because weakenings and -expanded variables are. □
Lemma 12 (No stray variables). Write and , where and are the input variables. Then is a weakening of a term in the single variable at position of , and dually for .
Proof. The first level of the descent gives , in which only occurs. By Lemma 11:
does not occur in , since it would survive;
if the th variable of occurs in , then only occurs in . This term has head , so , i.e. .
Dually for . □
Proof of Theorem 3. We prove that and are both hereditary permutations, by well-founded induction on the pair of types . They are treated together because the recursive call reverses the direction (step 4). In names, write , and , with , and , with (in the formalisation the are the telescope and is a de Bruijn index).
Head. By Lemma 8(a) for the initial pair, is the input variable . So , and , because has type and is the body of a term of type .
Permutation. The descent assigns to the argument the position in , and to the argument of the position in . By Lemma 8(c) these are mutually inverse, so and is a permutation of .
Arguments. By Lemma 12, mentions only . Strengthening gives with . Likewise with .
Inverse at a smaller type. The first-level equations of the descent become and . So is an isomorphism , with inverse , and the pair is smaller than . By induction, .
5. Assembly. Putting the steps together,
which is the form of the definition of with and . The base case is .
By the symmetry , is the hereditary permutation with and components . In the formalisation, this assembly is characterisation-HP in STLC.Link.
Remark 13 (Retracts in both directions). Suppose , and is a retract of by some other pair of terms. In every interpretation of the base types by non-empty finite sets, is then injective and , so is a bijection and holds semantically. By Statman’s finite completeness theorem [30, 28], . So retracts in both directions give an isomorphism. We do not use this: the syntactic proof needs both equations anyway, and the semantic argument is exactly the kind of completeness theorem that is not available for University Algebra.
Proof of coherence
In this section we prove Theorem 4: two derivations are equal modulo the level-2 equations if and only if they have the same meaning, and every hereditary permutation is the meaning of a derivation.
Plan. We choose for every hereditary permutation a canonical derivation , defined below. The theorem then follows from three facts:
(S) soundness: if then ;
(N) normal forms: every derivation satisfies for some ;
(St) stability: .
Indeed, is well defined on derivations modulo by (S), surjective by (St), and injective: if , write and by (N); then by (St) and (S), so .
In the terminology of normalisation by evaluation, is the normaliser, hereditary permutations are the normal forms and is their embedding. (S) is soundness, (N) gives completeness, , and (St) is stability. As in NbE, stability is an equation between normal forms, not one up to .
The three facts are of different natures. (N) is pure combinatorics on derivations and uses no substitution at all; it is a hereditary version of the normal-form proof for the Coxeter presentation of the symmetric groups, and it is proved in § 5.1. (S) and (St) are short calculations with hereditary substitution, in § 5.2 and § 5.3.
Canonical derivations. Write when arises from by inserting at position . Let be the derivation that moves the first argument to position : and . A hereditary permutation is a triple (its insertion form): the first argument is inserted at , , and permutes the rest. The canonical derivation of is defined by recursion on : at a base type, and
This is the derivation of Proposition 2(3); that its meaning is is (St), proved in § 5.3.
Normal forms
Lemma 14 (Insertions commute). Let insert into , and insert into . Then there are (into ) and (into ) with
Proof. By induction on and . If , take and . If , the claim is . Otherwise both are successors. Then naturality moves past a swap, the braid equation applies, and so does the induction hypothesis.
Lemma 15 (Extraction). Let insert into , and . Then there are (into ), and with
Proof. By induction on . For , take the first insertion of . For , apply the induction hypothesis inside , use naturality of swap, and then Lemma 14.
Proposition 16 (Normal forms).
Let and . Then there is with .
Every derivation satisfies for some .
Proof. (1) By induction on the height of the types, and then on . By Lemma 15,
and both composites are canonical by induction: the first at smaller types, the second with fewer arguments. Composition alternates between arguments of the domain and of the codomain, so the induction is on a bound for the height of all three types.
(2) By induction on , proving the same statement for at the same time. Composition uses (1). For the canonical form is with and ; this is why is carried along. For swap it is .
Remarks. The equations used in Proposition 16 are exactly those of § 2: the groupoid laws and functoriality, (in Lemma 14), naturality (in both lemmas), and the braid equation (in Lemma 14). By (S), each of them holds for meanings, so the list is sound and, by Theorem 4, complete. The classical presentation of by Coxeter relations is the special case in which all are identities: Lemma 14 is the step in the usual normal-form proof where a new generator is absorbed, and the hereditary version needs only naturality in addition.
Soundness
In the formalisation the meaning is defined in every context , because -congruence uses it under binders. The meaning at is the closed meaning weakened to (by induction on the derivation). So it suffices to work with closed maps , applied to a term by substitution, . Composition is , and the category laws are the identity and associativity laws of substitution. Write . The remaining equations are computations of the following kind:
They give functoriality, , and . For naturality, both sides compute to . For the braid equation, both sides compute to . The same calculations show that the two parts of the meaning of every derivation are mutually inverse, by induction on the derivation; this is needed for the inverse laws.
Stability
We prove without computing by unfolding hereditary substitution. Instead we compute how meanings act on argument lists, and recover the term by : . For and arguments of types , write for the argument at position and for the others. Then
by induction on , from the actions of and of : and . It follows, by induction on , that for a variable and variables ,
where is the corresponding spine for . By induction, , and the spine for consists of the arguments of with the remaining variables substituted in the same way. Taking for the input with empty, and for the bound variables, gives
which is , written in insertion form.
The formalisation
All results of this paper are formalised in Agda 2.6.5, using only Agda’s builtin modules (no standard library), with no postulates, holes or termination pragmas. The development has about 5000 lines and is available at https://github.com/txa/stlc-iso; the version described here is tagged v1.1.
Syntax. Types, contexts and de Bruijn variables are as usual; normal forms are intrinsically typed and in spine form, -long by construction (neutral terms only at base types). Weakening, -expansion and hereditary substitution follow [20], and are accepted by the termination checker without help. Positions in contexts are telescopes ; three rewrite rules for (left unit, associativity, and moving a snoc out of a telescope) make all context equations definitional, and Agda’s local confluence check accepts them. Simultaneous substitution is defined by structural recursion on , using single-variable hereditary application at a neutral, so it needs no new termination argument.
Symmetry. Maps come as pairs with an involution that commutes definitionally with all operations. Every construction and every one-sided lemma (in particular the parts of Lemma 8) is stated once and applied in both directions.
Modules.
| module | lines | content |
| Syntax | 176 | types, normal forms, weakening, , hereditary substitution |
| Lemmas | 347 | substitution lemmas; normal forms form a category |
| Subst | 400 | simultaneous substitution, its category laws, pairing |
| Iso | 193 | isomorphisms, derivations and their meaning, list-based HP |
| Heads | 264 | occurrences, free and bound heads; Lemmas 5, 6 |
| LamI | 235 | the predicate; Lemma 11 |
| Tele | 349 | telescopes, bodies of -long terms, spines as substitutions |
| Descent | 305 | matched pairs, Lemma 8, Corollary 9 |
| Thin | 168 | thinnings, strengthening, cancellation of renamings |
| Char | 297 | Lemma 12, Theorem 3 |
| Easy | 280 | Proposition 2 |
| Link | 443 | from the predicate form of HP to the inductive family |
| Coherence | 394 | level-2 equations, insertion form, Proposition 16 |
| Sound | 440 | (S), and all derivations denote isomorphisms |
| Actions | 258 | how meanings act on argument lists; heads, distinct variables |
| Derivable | 140 | (St) for the list form; every isomorphism is the meaning of a derivation |
| Stable | 121 | (St) and faithfulness for insertion forms; Theorem 4 |
| Examples | 89 | checks by computation |
Table 1.
Remarks on the proofs. Freshness conditions disappear: in a matched pair, lives over , so by typing it cannot mention the targets. The descent recurses on accessibility of pairs of types, and the composition of canonical derivations in Proposition 16(1) on an explicit bound for the height of all three types. Hereditary permutations are used in three forms: as a predicate on normal forms (for Theorem 3), as an inductive family with list positions (the statement in Iso), and in insertion form with an inductive insertion relation (for Theorem 4), which avoids equations between lists. The first two are linked in Link. The insertion form is the output of (N). Injectivity in Theorem 4 is proved as in Section 5, from (S), (N) and (St) for insertion forms, together with their faithfulness (below); surjectivity combines (St) for the list form with the characterisation. Both proofs of (St) use the same action formula of Section 5.3, and recover the term by .
Faithfulness of the representation. In the paper, is a set of normal terms, so in Section 5 two hereditary permutations with the same meaning are equal by definition. In the formalisation, hereditary permutations are an inductive family of insertion forms, interpreted as terms by a function , and (St) reads . So we must also show that this representation is faithful: insertion forms with the same meaning are equal. This is a statement about terms only. In the bound variables are distinct, and the head of is , so comparing heads fixes the insertion position . Renaming by a single variable is injective, so induction applies to and to the rest.
Related work
Invertible terms. Dezani [10] showed that a normalisable untyped -term is invertible modulo iff it is a finite hereditary permutation; Bergstra and Klop [5] characterised invertible terms in general. Bucciarelli, De Faveri, Manzonetto and Salibra [8] recently showed that the finite hereditary permutations are the invertible terms in every -theory between and . Every finite hereditary permutation is typable, so the typed characterisation follows from the untyped one [7].
Isomorphisms of types. Bruce and Longo [6] and Bruce, Di Cosmo and Longo [7] showed that swap and congruence axiomatise isomorphism for , and extended this to and . Soloviev [29] showed, using the model of finite sets, that the corresponding axioms are complete for all cartesian closed categories. Di Cosmo’s book [11] surveys the area, including decision procedures and applications to library search. With sums and the empty type, Fiore, Di Cosmo and Balat [15] showed that isomorphism is not finitely axiomatisable; Ilik [19] studied decidability in this setting. Laurent characterised isomorphisms through game semantics [23].
Retractions. One-sided inverses are much less constrained; see Regnier and Urzyczyn [26] and the references there. Remark 10 shows the two phenomena that make one equation insufficient for the descent.
Coherence. The results above are about which types are isomorphic and which terms are isomorphisms. To our knowledge they do not address when two derivations denote the same isomorphism; Di Cosmo’s book [11] and survey [12] do not treat this question. The classical coherence theorems for closed categories answer a different one: Kelly and Mac Lane [21] and Mints [24] for (symmetric, monoidal) closed categories, and Babaev and Solov’ev [4] and Mints [25] for cartesian closed categories (see Zeilberger [33] for a modern account of Mints’ result), show that all canonical maps between two objects are equal when the objects are balanced, that is, when each atom occurs at most twice. For a balanced type every automorphism is trivial, so these theorems give no information about level 2. Theorem 4 covers arbitrary types, where the automorphism groups are non-trivial, and gives a complete set of equations. For symmetric monoidal and symmetric rig categories the corresponding questions are classical coherence problems (Mac Lane, Laplaza [22]); for the reversible language , with sums and products but no function types, Choudhury, Karwowski and Sabry [9] gave a complete set of level-2 equations, formalised in Agda. Group-theoretically, the automorphism group of a type tree is an iterated wreath product of symmetric groups, and Theorem 4 gives a presentation of these groups, and of the groupoid of all isomorphisms, read off the syntax of derivations.
What is new. (1) A direct typed proof of the characterisation that does not pass through the untyped calculus, isolates the lemmas needed, and uses no completeness theorem; the classical alternatives use the untyped analysis [10], finite sets [29], games [23], or Friedman’s theorem [16]. (2) The coherence theorem for . (3) A complete mechanisation; we have not found an earlier mechanisation of Dezani’s theorem or of its typed version.
From simple types to University Algebra
The proof was designed to be reused for the syntactic completeness conjecture of University Algebra. We indicate what we expect to carry over and what changes.
Normal forms and substitution. For , -normal -long forms with hereditary substitution are canonical. For UA the type theory has , , and an extensional boolean with a large eliminator, so equality of terms involves strong for , as for sums in the simply typed case [1, 27]. We expect normal forms in which case splits on neutral booleans are represented as finite maps, so that the order of splits does not matter.
The descent. The analysis of heads should carry over, with one new feature: a head may sit below case splits, so the permutation becomes a permutation per branch. Relevance has to be read per branch too, because erasure in UA is additive (a branch of a split may ignore a variable that another branch uses). The point where the two inverse equations interact should again be the matching of heads.
Derivations and level 2. The role of swap is taken by the basic isomorphisms of UA, and the hereditary permutations become hereditary combinations of permutations, case splits, relabelling of the partitions defined by boolean-valued functions, and reindexing of domains along automorphisms. The level-2 equations will include the groupoid laws, functoriality of and , naturality of the basic isomorphisms, and coherence equations of the kind known for polynomial functors [17] and for symmetric rig categories [22, 9]. The Coxeter presentation of is replaced by presentations in which only independent entries commute, closer to trace monoids [13]. The structure of the proof of Theorem 4—soundness, normal forms without substitution, and stability by computing actions on arguments—is independent of these details.
An intermediate step. Between simple types and UA lies the logical framework LF: -types over base type families. Hereditary substitution still terminates by recursion on the simple type obtained by erasing dependencies [31, 18], so the presentation of this paper should carry over, with swaps allowed only between independent arguments. We are pursuing an intrinsic formalisation of LF along these lines.
Conclusion
The characterisation of isomorphisms of simple types and its coherence form can be proved purely syntactically, by an analysis of normal forms that never appeals to a semantic completeness theorem, and the proof can be formalised directly on intrinsically typed syntax. The two parts of the coherence proof have very different natures: the normal-form argument is pure combinatorics on derivations, while soundness and stability are short calculations with hereditary substitution. This separation, and the descent on matched pairs, are what we intend to reuse for University Algebra.
Acknowledgements and use of AI tools. This paper and its Agda formalisation were developed in collaboration with Claude (Anthropic), used through Claude Code: Claude drafted Agda code and text, ran experiments and searched the literature, under the author’s direction. The author has checked the content and is responsible for it.
References
- [1]T. Altenkirch, P. Dybjer, M. Hofmann and P. Scott. Normalization by evaluation for typed lambda calculus with coproducts. LICS 2001, 303–310.DOI
- [2]T. Altenkirch. From high school to university algebra. Unfinished draft, June 2008. https://people.cs.nott.ac.uk/psztxa/publ/unialg.pdf.
- [3]T. Altenkirch. Towards University Algebra. In preparation.
- [4]A. A. Babaev and S. V. Solov’ev. A coherence theorem for canonical morphisms in cartesian closed categories. Journal of Soviet Mathematics 20(4):2263–2279, 1982 (Russian original 1979).DOI
- [5]J. A. Bergstra and J. W. Klop. Invertible terms in the lambda calculus. Theoretical Computer Science 11(1):19–37, 1980.DOI
- [6]K. B. Bruce and G. Longo. Provable isomorphisms and domain equations in models of typed languages. STOC 1985, 263–272.DOI
- [7]K. B. Bruce, R. Di Cosmo and G. Longo. Provable isomorphisms of types. Mathematical Structures in Computer Science 2(2):231–247, 1992.DOI
- [8]A. Bucciarelli, A. De Faveri, G. Manzonetto and A. Salibra. Groups and inverse semigroups in lambda calculus. FSCD 2026, LIPIcs 378, 9:1–9:22.
- [9]V. Choudhury, J. Karwowski and A. Sabry. Symmetries in reversible programming: from symmetric rig groupoids to reversible programming languages. Proc. ACM Program. Lang. 6(POPL), 2022.DOI
- [10]M. Dezani-Ciancaglini. Characterization of normal forms possessing inverse in the λ-β-η-calculus. Theoretical Computer Science 2(3):323–337, 1976.
- [11]R. Di Cosmo. Isomorphisms of Types: from λ-calculus to information retrieval and language design. Birkhäuser, 1995.DOI
- [12]R. Di Cosmo. A short survey of isomorphisms of types. Mathematical Structures in Computer Science 15(5):825–838, 2005.DOI
- [13]V. Diekert and G. Rozenberg (eds.). The Book of Traces. World Scientific, 1995.
- [14]J. Dunfield and N. Krishnaswami. Bidirectional typing. ACM Computing Surveys 54(5):1–38, 2021.DOI
- [15]M. Fiore, R. Di Cosmo and V. Balat. Remarks on isomorphisms in typed lambda calculi with empty and sum types. Annals of Pure and Applied Logic 141(1–2):35–50, 2006.
- [16]H. Friedman. Equality between functionals. Logic Colloquium ’73, LNM 453, 22–37, 1975.DOI
- [17]N. Gambino and J. Kock. Polynomial functors and polynomial monads. Math. Proc. Cambridge Philos. Soc. 154(1):153–192, 2013.DOI
- [18]R. Harper and D. R. Licata. Mechanizing metatheory in a logical framework. Journal of Functional Programming 17(4–5):613–673, 2007.DOI
- [19]D. Ilik. Axioms and decidability for type isomorphism in the presence of sums. CSL-LICS 2014, ACM, 1–7.
- [20]C. Keller and T. Altenkirch. Hereditary substitutions for simple types, formalized. MSFP 2010, ACM, 3–10.DOI
- [21]G. M. Kelly and S. Mac Lane. Coherence in closed categories. Journal of Pure and Applied Algebra 1(1):97–140, 1971.
- [22]M. L. Laplaza. Coherence for distributivity. Coherence in Categories, LNM 281, 29–65, 1972.DOI
- [23]O. Laurent. Classical isomorphisms of types. Mathematical Structures in Computer Science 15(5):969–1004, 2005.DOI
- [24]G. E. Mints. Closed categories and the theory of proofs. Journal of Soviet Mathematics 15(1):45–62, 1981 (Russian original 1977).DOI
- [25]G. E. Mints. A simple proof of the coherence theorem for cartesian closed categories. In Selected Papers in Proof Theory, Bibliopolis and North-Holland, 213–220, 1992.
- [26]L. Regnier and P. Urzyczyn. Retractions of types with many atoms. arXiv:cs/0212005, 2002.DOI
- [27]G. Scherer. Deciding equivalence with sums and the empty type. POPL 2017, 374–386.
- [28]R. Statman and G. Dowek. On Statman’s finite completeness theorem. Technical report CMU-CS-92-152, 1992; arXiv:2309.03602.
- [29]S. V. Soloviev. The category of finite sets and cartesian closed categories. Journal of Soviet Mathematics 22(3):1387–1400, 1983.DOI
- [30]R. Statman. Completeness, invariance and λ-definability. Journal of Symbolic Logic 47(1):17–26, 1982.DOI
- [31]K. Watkins, I. Cervesato, F. Pfenning and D. Walker. A concurrent logical framework I: judgments and properties. Technical report CMU-CS-02-101, 2002.
- [32]A. J. Wilkie. On exponentiation—a solution to Tarski’s high school algebra problem. In Connections between Model Theory and Algebraic and Analytic Geometry, Quaderni di Matematica 6, 107–129, 2000 (preprint 1981).
- [33]N. Zeilberger. Balanced polymorphism and linear lambda calculus. Abstract, TYPES 2015, Tallinn. https://www.lix.polytechnique.fr/~zeilberger/papers/linprin.pdf.