betaFeedback

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 A→B→C≅B→A→CA \to B \to C \cong B \to A \to C 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 11, ++, ×\times and exponentiation are incomplete for the positive integers [32], and so is their categorified version, isomorphisms of types with sums [15]. With dependent types (1,2,Σ,Π)(1, 2, \Sigma, \Pi) 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 λ\lambda-calculus with →\to only. Here the characterisation of definable isomorphisms is classical (Section 7): the invertible terms are the hereditary permutations [10], and swap:A→B→C≅B→A→C\mathit{swap}: A \to B \to C \cong B \to A \to C 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:

  1. A direct proof that every invertible β\beta-normal η\eta-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 (λI\lambda I) is a consequence of the descent.

  1. 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.

  1. A formalisation of all results in Agda without postulates, on intrinsically typed de Bruijn syntax with hereditary substitution [20] (Section 6).

  1. A discussion of which parts of the method should carry over to University Algebra (Section 8).

Setting

Types. A::=X∣A→BA ::= X \mid A \to B, with XX ranging over base types. Every type can be written uniquely as A1→⋯→An→XA_1 \to\cdots\to A_n \to X, which we write A⃗⇒X\vec{A} \Rightarrow X.

Terms and normal forms. Terms are those of the simply typed λ\lambda-calculus, taken modulo βη\beta\eta. Every term has a unique β\beta-normal, η\eta-long form:1

Nf⁡(Γ,A⃗⇒X)∋λy⃗.n,n∈Ne⁡(Γ,y⃗ ⁣: ⁣A⃗;X),h t1…tk∈Ne⁡(Δ;X),\operatorname{Nf}(\Gamma, \vec{A} \Rightarrow X) \ni\lambda\vec{y}.n,\qquad n \in\operatorname{Ne}(\Gamma,\vec{y}\!:\!\vec{A};X),\qquad h\ t_1\ldots t_k \in\operatorname{Ne}(\Delta;X),

where h ⁣: ⁣B⃗⇒Xh\!:\!\vec{B} \Rightarrow X is in Δ\Delta and ti∈Nf⁡(Δ,Bi)t_i \in\operatorname{Nf}(\Delta,B_i). We write t[s/x]t[s/x] for hereditary substitution [31, 20], which substitutes and normalises at once, by recursion on the type of xx. For a variable x ⁣: ⁣A⃗⇒Xx\!:\!\vec{A} \Rightarrow X, its η\eta-long form is

ηx=λy1…yn.x  (ηy1)…(ηyn),\eta x = \lambda y_1\ldots y_n.x\;(\eta y_1)\ldots(\eta y_n),

defined by recursion on the type. It is the normal form of the term xx, so ηa∈Nf⁡(a ⁣: ⁣A,A)\eta a \in\operatorname{Nf}(a\!:\!A,A) is the identity map on AA. Composition of maps t∈Nf⁡(a ⁣: ⁣A,B)t \in\operatorname{Nf}(a\!:\!A,B) and u∈Nf⁡(b ⁣: ⁣B,C)u \in\operatorname{Nf}(b\!:\!B,C) is u∘t=u[t/b]u \circ t = u[t/b]; it is associative and η\eta is its unit, by the substitution lemmas for hereditary substitution.

Isomorphisms. An isomorphism A≅BA \cong B is a pair f∈Nf⁡(a ⁣: ⁣A,B)f \in\operatorname{Nf}(a\!:\!A,B), g∈Nf⁡(b ⁣: ⁣B,A)g \in\operatorname{Nf}(b\!:\!B,A) with

g[f/b]=ηa,f[g/a]=ηb,g[f/b] = \eta a,\qquad f[g/a] = \eta b,

as syntactic equalities of normal forms: both composites are the identity. We call ff invertible. The inverse is unique: if g′g' is another, then g′=g′∘(f∘g)=(g′∘f)∘g=gg' = g' \circ(f \circ g) = (g' \circ f) \circ g = g. So being invertible is a property of ff alone.

Derivations. The relation A≅axBA \cong_{\mathrm{ax}} B is generated by the axiom

swap:A→B→C≅B→A→C\mathrm{swap}: A \to B \to C \cong B \to A \to C

together with id\mathrm{id}, −1^{-1}, composition ;; (in diagrammatic order) and the congruence φ→ψ:A→B≅A′→B′\varphi\to\psi: A \to B \cong A' \to B' for φ:A≅A′\varphi: A \cong A', ψ:B≅B′\psi: B \cong B'. Derivations are the terms of this signature. Each derivation φ\varphi has a meaning ⟦φ⟧=(f,g)\llbracket\varphi\rrbracket=(f,g), an isomorphism, defined by recursion on φ\varphi. Both parts of ⟦swap⟧\llbracket\mathrm{swap}\rrbracket are λb a. u a b\lambda b\,a.\,u\,a\,b, with input variable uu; id\mathrm{id}, −1^{-1} and ;; are interpreted by the identity, by exchanging ff and gg, and by composition; and the first part of ⟦φ→ψ⟧\llbracket\varphi\to\psi\rrbracket is λa′. fψ(u(gφ a′))\lambda a'.\,f_\psi(u(g_\varphi\,a')). We also write ⟦φ⟧\llbracket\varphi\rrbracket for its first part ff.

Level-2 equations. The equations between derivations are:

  • the groupoid laws, and congruence for ;;, −1^{-1} and →\to;

  • functoriality of →\to: id→id=id\mathrm{id}\to\mathrm{id}=\mathrm{id} and (φ;φ′)→(ψ;ψ′)=(φ→ψ);(φ′→ψ′)(\varphi;\varphi')\to(\psi;\psi')=(\varphi\to\psi);(\varphi'\to\psi');

  • swap;swap=id\mathrm{swap};\mathrm{swap}=\mathrm{id};

  • naturality of swap\mathrm{swap}: swap;(ψ→φ→χ)=(φ→ψ→χ);swap\mathrm{swap};(\psi\to\varphi\to\chi)=(\varphi\to\psi\to\chi);\mathrm{swap};

  • the braid (Yang–Baxter) equation on A→B→C→DA\to B\to C\to D: swap;(id→swap);swap=(id→swap);swap;(id→swap)\mathrm{swap};(\mathrm{id}\to\mathrm{swap});\mathrm{swap}=(\mathrm{id}\to\mathrm{swap});\mathrm{swap};(\mathrm{id}\to\mathrm{swap}).

We write φ∼ψ\varphi\sim\psi for equality modulo these equations. Swaps at non-adjacent positions commute: this is naturality with χ=swap\chi=\mathrm{swap}. Together these are the Coxeter relations of the symmetric groups, applied hereditarily.

Normal forms of types. Modulo swap, a type A⃗⇒X\vec{A}\Rightarrow X is determined by XX and the multiset { ⁣{A1,…,An} ⁣}\{\!\{A_1,\ldots,A_n\}\!\}. Hereditarily, types modulo ≅ax\cong_{\mathrm{ax}} are rooted unordered trees: the root is labelled by XX, and each subtree is one AiA_i.

Hereditary permutations and the main results

Definition 1. The hereditary permutations HP(A,B)⊆Nf(a:A,B)\mathrm{HP}(A,B)\subseteq\mathrm{Nf}(a:A,B), for A=A⃗⇒XA=\vec{A}\Rightarrow X and B=B⃗⇒XB=\vec{B}\Rightarrow X with ∣A⃗∣=∣B⃗∣=n|\vec{A}|=|\vec{B}|=n, are the normal terms

λy1…yn. a (h1[yπ1/z1])…(hn[yπn/zn]),\lambda y_1\ldots y_n.\,a\,(h_1[y_{\pi_1}/z_1])\ldots(h_n[y_{\pi_n}/z_n]),

where π\pi is a permutation of {1,…,n}\{1,\ldots,n\} and hi∈HP(Bπi,Ai)h_i\in\mathrm{HP}(B_{\pi_i},A_i) has free variable ziz_i. The case n=0n=0 gives ηa\eta_a at a base type.

Proposition 2 (Easy direction).

  1. Every hereditary permutation is invertible, and the inverse is again a hereditary permutation (with π−1\pi^{-1} and the inverses of the hih_i).

  1. The meaning of every derivation is a hereditary permutation: swap gives a transposition, and →\to-congruence gives the hih_i.

  1. Conversely, every hereditary permutation hh is the meaning of a derivation der⁡h\operatorname{der}h, which decomposes π\pi 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 A≅axBA \cong_{\mathrm{ax}} B modulo ∼\sim to HP(A,B)\mathrm{HP}(A,B). In particular, φ∼ψ\varphi\sim\psi if and only if ⟦φ⟧=⟦ψ⟧\llbracket\varphi\rrbracket= \llbracket\psi\rrbracket.

Theorem 3 together with Proposition 2 gives completeness: A≅BA \cong B iff A≅axBA \cong_{\mathrm{ax}} B iff AA and BB have the same tree. Theorem 4 is the analogue, for →\to, 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 ε\varepsilon by extension Γ▹A\Gamma\triangleright A. Variables are de Bruijn indices: vz\mathsf{vz} is the last variable of Γ▹A\Gamma\triangleright A (of type AA), and vs x\mathsf{vs}\ x is the variable xx of Γ\Gamma, seen in Γ▹A\Gamma\triangleright A. So Nf⁡(ε▹A,B)\operatorname{Nf}(\varepsilon\triangleright A,B) is Nf⁡(a:A,B)\operatorname{Nf}(a:A,B), with aa written vz\mathsf{vz}, and the identity ηa\eta_a becomes η vz\eta\ \mathsf{vz}.

Throughout, f∈Nf⁡(ε▹A,B)f \in\operatorname{Nf}(\varepsilon\triangleright A,B) and g∈Nf⁡(ε▹B,A)g \in\operatorname{Nf}(\varepsilon\triangleright B,A) are mutually inverse, with A=A⃗⇒XA=\vec{A}\Rightarrow X and B=B⃗⇒YB=\vec{B}\Rightarrow Y; the equations are f[g]=η vzf[g]=\eta\ \mathsf{vz} and g[f]=η vzg[f]=\eta\ \mathsf{vz}, where t[u]t[u] substitutes uu for vz\mathsf{vz}.

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 (f,g)↦(g,f)(f,g)\mapsto(g,f). 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: Γ++Δ\Gamma++ \Delta. A substitution ρ∈Sub⁡(Γ,Δ)\rho\in\operatorname{Sub}(\Gamma,\Delta) is a normal form in Γ\Gamma for each type of Δ\Delta. We write:

  • ρi\rho_i for the iith component of ρ\rho;

  • t[ρ]∈Nf⁡(Γ,τ)t[\rho]\in\operatorname{Nf}(\Gamma,\tau) for simultaneous hereditary substitution, where t∈Nf⁡(Δ,τ)t\in\operatorname{Nf}(\Delta,\tau);

  • σ[ρ]\sigma[\rho] for composition, applying t↦t[ρ]t\mapsto t[\rho] to each component of σ\sigma;

  • ⟨ρ,σ⟩∈Sub⁡(Γ,Δ++Θ)\langle\rho,\sigma\rangle\in\operatorname{Sub}(\Gamma,\Delta++\Theta) for pairing, where ρ∈Sub⁡(Γ,Δ)\rho\in\operatorname{Sub}(\Gamma,\Delta) and σ∈Sub⁡(Γ,Θ)\sigma\in\operatorname{Sub}(\Gamma,\Theta);

  • p∈Sub⁡(Γ++Θ,Γ)p\in\operatorname{Sub}(\Gamma++\Theta,\Gamma) for the weakening projection, and qΘ∈Sub⁡(Γ++Θ,Θ)q_\Theta\in\operatorname{Sub}(\Gamma++\Theta,\Theta) for the η\eta-expanded variables of Θ\Theta.

Contexts and substitutions form a category, and ⟨−,−⟩\langle-,-\rangle, pp, qq satisfy the usual laws. A term λΘ. h n⃗\lambda\Theta.\ h\ \vec{n} is head-free if its head hh is not bound in Θ\Theta. Components of pp and qq are head-free.

Lemma 5 (No creation). Let t∈Nf⁡(Δ,τ)t\in\operatorname{Nf}(\Delta,\tau) and ρ∈Sub⁡(Γ,Δ)\rho\in\operatorname{Sub}(\Gamma,\Delta). If a variable zz of Γ\Gamma occurs in t[ρ]t[\rho], then zz occurs in ρv\rho_v for some variable vv of Δ\Delta that occurs in tt. If t=λΘ.Mt=\lambda\Theta.M, then t[ρ]=λΘ.M[⟨ρ[p],qΘ⟩]t[\rho]=\lambda\Theta.M[\langle\rho[p],q_\Theta\rangle].

Lemma 6 (Heads). Let t=λΘ. h r⃗∈Nf⁡(Δ,τ)t=\lambda\Theta.\ h\ \vec{r}\in\operatorname{Nf}(\Delta,\tau) and ρ∈Sub⁡(Γ,Δ)\rho\in\operatorname{Sub}(\Gamma,\Delta).

  • If hh is bound in Θ\Theta, the head of t[ρ]t[\rho] is the same variable of Θ\Theta.

  • If h=vh=v is a variable of Δ\Delta and ρv\rho_v is head-free with head h′h', then the head of t[ρ]t[\rho] is h′h', weakened past Θ\Theta.

Both lemmas are by induction on tt, and on the type for the second clause of Lemma 6.

The descent

Idea. We want to read off the structure of ff top-down: first its head, then the heads of its arguments, and so on. The only information is the pair of equations g[f/b]=ηag[f/b] = \eta a and f[g/a]=ηbf[g/a] = \eta b, and they are about the whole terms. Write f=λy⃗.at⃗f = \lambda\vec{y}.a\vec{t} and g=λx⃗.bs⃗g = \lambda\vec{x}.b\vec{s}. In f[g/a]f[g/a] the head aa is replaced by gg, so the arguments t⃗\vec{t} are substituted into the body of gg. Comparing with ηb\eta b says that the head of sjs_j must be the variable that receives tσjt_{\sigma j}, 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 ff and gg that were already substituted.

A matched pair is the general form of such a pair of equations. PP is a family of subterms of ff at the current depth, QQ is the matching family of subterms of gg, and the parameter substitutions α,β\alpha,\beta record what has been substituted so far. The initial pair is (f,g)(f,g) 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 ff and gg, but over both at once, along matched positions: argument ii of a head in ff goes with argument τi\tau i in gg. It is not structural induction on one term, because each step uses one equation for the heads of PP and the other for the heads of QQ (part (c)). It terminates because the pair of types gets smaller.

Definition 7. A matched pair consists of:

  • contexts Γ1,Γ2\Gamma_1,\Gamma_2 (the bases) and ΓP,ΓQ\Gamma_P,\Gamma_Q (the parameters);

  • telescopes XX and YY (the targets);

  • P∈Sub⁡(ΓP++Y,X)P \in\operatorname{Sub}(\Gamma_P ++ Y,X) and Q∈Sub⁡(ΓQ++X,Y)Q \in\operatorname{Sub}(\Gamma_Q ++ X,Y);

  • parameter substitutions α∈Sub⁡(Γ1,ΓP)\alpha\in\operatorname{Sub}(\Gamma_1,\Gamma_P), β∈Sub⁡(Γ1,ΓQ)\beta\in\operatorname{Sub}(\Gamma_1,\Gamma_Q), α0∈Sub⁡(Γ2,ΓP)\alpha_0 \in\operatorname{Sub}(\Gamma_2,\Gamma_P) and β0∈Sub⁡(Γ2,ΓQ)\beta_0 \in\operatorname{Sub}(\Gamma_2,\Gamma_Q), all of whose components are head-free;

such that

(P)P[⟨α[p],Q[⟨β[p],qX⟩]⟩]=qXin Sub⁡(Γ1++X,X),(Q)Q[⟨β0[p],P[⟨α0[p],qY⟩]⟩]=qYin Sub⁡(Γ2++Y,Y).\begin{aligned} \text{(P)}\quad&P\left[\langle\alpha[p],Q[\langle\beta[p],q_X\rangle]\rangle\right] = q_X && \text{in }\operatorname{Sub}(\Gamma_1 ++ X,X),\\ \text{(Q)}\quad&Q\left[\langle\beta_0[p],P[\langle\alpha_0[p],q_Y\rangle]\rangle\right] = q_Y && \text{in }\operatorname{Sub}(\Gamma_2 ++ Y,Y). \end{aligned}

The definition is symmetric under (Γ1,ΓP,X,P,α,α0)↔(Γ2,ΓQ,Y,Q,β0,β)(\Gamma_1,\Gamma_P,X,P,\alpha,\alpha_0) \leftrightarrow(\Gamma_2,\Gamma_Q,Y,Q,\beta_0,\beta), which exchanges (P) and (Q). There are no freshness conditions: α\alpha lives over Γ1\Gamma_1, so it cannot mention the targets XX.

The initial pair. All bases and parameters are empty, X=ε▹BX = \varepsilon\triangleright B, Y=ε▹AY = \varepsilon\triangleright A, P=(f)P = (f), Q=(g)Q = (g), and the parameter substitutions are empty. Then (P) is f[g]=η vzf[g] = \eta\,vz and (Q) is g[f]=η vzg[f] = \eta\,vz.

Lemma 8 (Descent). For a matched pair:

(a) (one-sided) for each ii, write Pi=λWi.hiv⃗P_i = \lambda W_i.h_i\vec{v}. Then hih_i is a variable of the YY-part of ΓP++Y++Wi\Gamma_P ++ Y ++ W_i, say the one at position τi\tau i of YY. Dually, the head of Qj=λZj.kju⃗Q_j = \lambda Z_j.k_j\vec{u} is the variable at position σj\sigma j of XX.

(b) (one-sided) every variable of WiW_i occurs in the body of PiP_i; dually for ZjZ_j.

(c) σ\sigma and τ\tau are mutually inverse; in particular ∣X∣=∣Y∣|X| = |Y|.

(d) for each ii, let j=τij=\tau i, W=WiW=W_i and Z=ZjZ=Z_j. Then the argument families u⃗∈Sub⁡(ΓQ++X++Z,W)\vec{u}\in\operatorname{Sub}(\Gamma_Q ++ X ++ Z,W) of QjQ_j and v⃗∈Sub⁡(ΓP++Y++W,Z)\vec{v}\in\operatorname{Sub}(\Gamma_P ++ Y ++ W,Z) of PiP_i form a matched pair with

P′=u⃗,Q′=v⃗,X′=W,Y′=Z,ΓP′=ΓQ++X,ΓQ′=ΓP++Y,P'=\vec{u},\qquad Q'=\vec{v},\qquad X'=W,\qquad Y'=Z,\qquad\Gamma'_P=\Gamma_Q ++ X,\qquad\Gamma'_Q=\Gamma_P ++ Y,
Γ1′=Γ1++X,Γ2′=Γ2++Y,\Gamma'_1=\Gamma_1 ++ X,\qquad\Gamma'_2=\Gamma_2 ++ Y,
α′=⟨β[p],qX⟩,β′=⟨α[p],Q[⟨β[p],qX⟩]⟩,\alpha'=\langle\beta[p],q_X\rangle,\qquad\beta'=\langle\alpha[p],Q[\langle\beta[p],q_X\rangle]\rangle,
α0′=⟨β0[p],P[⟨α0[p],qY⟩]⟩,β0′=⟨α0[p],qY⟩.\alpha'_0=\langle\beta_0[p],P[\langle\alpha_0[p],q_Y\rangle]\rangle,\qquad\beta'_0=\langle\alpha_0[p],q_Y\rangle.

So the new parameter substitution β′\beta' is the substitution of the old equation (P)(P), and α0′\alpha'_0 is that of (Q)(Q).

Proof. (a) Apply Lemma 6 to (P)(P) at component ii. The right-hand side is η\eta of the iith variable of XX, whose head is that variable.

  • If hih_i is bound in WiW_i, the head of the left-hand side is in WiW_i.

  • If hih_i is in ΓP\Gamma_P, the head of the left-hand side is the head of a component of α[p]\alpha[p], which is in Γ1\Gamma_1, since α\alpha is head-free.

Neither is in XX, so hih_i is in YY. The dual is the same argument applied to (Q)(Q).

(b) By Lemma 5, the left-hand side of (P)(P) at ii is λWi.…\lambda W_i.\ldots with the same binders as ηxi\eta x_i, and each of them occurs in ηxi\eta x_i. No component of a substitution mentions WiW_i, so by no creation each variable of WiW_i occurs in the body of PiP_i.

(c), (d) In (P)(P) at ii, the head hih_i is replaced by Qτi[⟨β[p],qX⟩]Q_{\tau i}[\langle\beta[p],q_X\rangle]. By (a) for QQ, its head is the στi\sigma\tau ith variable of XX, which ⟨β[p],qX⟩\langle\beta[p],q_X\rangle maps to an η\eta-expanded variable. So the left-hand side is λW.xστi(…)\lambda W.x_{\sigma\tau i}(\ldots). Comparing heads with ηxi\eta x_i gives στ=id⁡\sigma\tau=\operatorname{id}. Comparing arguments gives

(P′)u⃗⟨α′[p],v⃗⟨β′[p],qW⟩⟩=qW.(P')\qquad\vec{u}\langle\alpha'[p],\vec{v}\langle\beta'[p],q_W\rangle\rangle=q_W.

This uses the substitution lemma to regroup the iterated substitution as a single one. Dually, (Q)(Q) at j=τij=\tau i gives τσ=id⁡\tau\sigma=\operatorname{id} and equation (Q′)(Q') of the new pair. The new parameter substitutions are head-free: the components of qq are η\eta-expanded variables, and the components of Q[…]Q[\ldots] and P[…]P[\ldots] have heads in XX and YY by (a).

Corollary 9 (Relevance). ff and gg are λI\lambda I-terms: every bound variable occurs in the body of its binder.

Proof. In an η\eta-long normal form, every λ\lambda 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 ff and in gg: Pi=λWi.hiv⃗P_i=\lambda W_i.h_i\vec{v} passes all of v⃗\vec{v} on. Part (b) applies at each level. The descent terminates: a step goes from the pair of types (Xi,Yτi)(X_i,Y_{\tau i}) to a pair of argument types of XiX_i and of YτiY_{\tau i}, and this relation is well founded.

Remark 10 (One equation is not enough). A single equation g∘f=id⁡g\circ f=\operatorname{id} makes AA a retract of BB, and retractions of simple types are much less rigid [26]:

  • The head of a section need not be its input: X◃(X→X)→XX\triangleleft(X\to X)\to X via f=λa.λh.haf=\lambda a.\lambda h.ha and g=λb.b(λz.z)g=\lambda b.b(\lambda z.z).

  • A section may erase: for f=λa.λh.x.axf=\lambda a.\lambda h.x.ax and g=λb.λx.b(λz.z)xg=\lambda b.\lambda x.b(\lambda z.z)x, we have g∘f=id⁡g\circ f=\operatorname{id} but ff is not λI\lambda I. In terms of the descent, (Q)(Q) holds but (P)(P) fails, and part (b) for (P)(P) is exactly what detects the vacuous λh\lambda h.

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 tt and all components of ρ\rho are λI\lambda I, then so is t[ρ]t[\rho], and a variable zz of Γ\Gamma occurs in t[ρ]t[\rho] if and only if it occurs in some ρv\rho_v with vv occurring in tt.

Proof. “Only if” is Lemma 5, which holds for all terms. For “if”, the only way hereditary substitution loses material is through a β\beta-step (λq.N) r(\lambda q. N)\ r in which qq does not occur in NN. First consider a single substitution t[a/x]t[a/x] and the application app⁡ tr⃗\operatorname{app}\ t\vec r, for λI\lambda I-terms. We prove three facts simultaneously:

  • the result is λI\lambda I;

  • (keep) every occurrence of a variable other than xx in tt survives;

  • (insert) if xx occurs in tt, every variable occurring in aa survives. Dually, every variable occurring in r⃗\vec r occurs in app⁡ tr⃗\operatorname{app}\ t\vec r.

The induction is the one that defines hereditary substitution: on tt for substitution, on r⃗\vec r and the type for application. Insert for application uses λI\lambda I: in app⁡ (λq.N) (r,r⃗)\operatorname{app}\ (\lambda q. N)\ (r,\vec r) the variable qq occurs in NN, so by insert, every variable of rr survives in N[r/q]N[r/q]. The simultaneous case follows by induction on tt, lifting ρ\rho under binders. The lifted substitution is again λI\lambda I, because weakenings and η\eta-expanded variables are. □

Lemma 12 (No stray variables). Write f=λB⃗. a⃗t⃗f = \lambda\vec B.\,\vec a\vec t and g=λA⃗. b⃗s⃗g = \lambda\vec A.\,\vec b\vec s, where aa and bb are the input variables. Then tit_i is a weakening of a term in the single variable at position τi\tau i of B⃗\vec B, and dually for sjs_j.

Proof. The first level of the descent gives ti[⟨a,s⃗[f]⟩]=ηxit_i[\langle a,\vec s[f]\rangle] = \eta x_i, in which only xix_i occurs. By Lemma 11:

  • aa does not occur in tit_i, since it would survive;

  • if the jjth variable of B⃗\vec B occurs in tit_i, then only xix_i occurs in sj[f]s_j[f]. This term has head xσjx_{\sigma j}, so σj=i\sigma j = i, i.e. j=τij = \tau i.

Dually for sjs_j. □

Proof of Theorem 3. We prove that ff and gg are both hereditary permutations, by well-founded induction on the pair of types (A,B)(A,B). They are treated together because the recursive call reverses the direction (step 4). In names, write A=A1…Am⇒XA = A_1\ldots A_m \Rightarrow X, B=B1…Bn⇒YB = B_1\ldots B_n \Rightarrow Y and f=λy1…yn. h t1…tkf = \lambda y_1\ldots y_n.\,h\ t_1\ldots t_k, with yj:Bjy_j : B_j, and g=λx1…xm. b s1…sng = \lambda x_1\ldots x_m.\,b\ s_1\ldots s_n, with xi:Aix_i : A_i (in the formalisation the yjy_j are the telescope B⃗\vec B and hh is a de Bruijn index).

  1. Head. By Lemma 8(a) for the initial pair, hh is the input variable aa. So k=mk = m, and X=YX = Y, because a t1…tma\ t_1\ldots t_m has type XX and is the body of a term of type BB.

  1. Permutation. The descent assigns to the argument tit_i the position τi\tau i in B⃗\vec B, and to the argument sjs_j of gg the position σj\sigma j in A⃗\vec A. By Lemma 8(c) these are mutually inverse, so m=nm = n and τ\tau is a permutation of {1,…,n}\{1,\ldots,n\}.

  1. Arguments. By Lemma 12, tit_i mentions only yτiy_{\tau i}. Strengthening gives ti′∈Nf⁡(zi:Bτi,Ai)t'_i \in\operatorname{Nf}(z_i:B_{\tau i},A_i) with ti=ti′[yτi/zi]t_i = t'_i[y_{\tau i}/z_i]. Likewise sτi=sτi′[xi/wi]s_{\tau i} = s'_{\tau i}[x_i/w_i] with sτi′∈Nf⁡(wi:Ai,Bτi)s'_{\tau i} \in\operatorname{Nf}(w_i:A_i,B_{\tau i}).

  1. Inverse at a smaller type. The first-level equations of the descent become ti′[sτi′/zi]=ηwit'_i[s'_{\tau i}/z_i] = \eta w_i and sτi′[ti′/wi]=ηzis'_{\tau i}[t'_i/w_i] = \eta z_i. So ti′t'_i is an isomorphism Bτi≅AiB_{\tau i} \cong A_i, with inverse sτi′s'_{\tau i}, and the pair (Bτi,Ai)(B_{\tau i},A_i) is smaller than (A,B)(A,B). By induction, ti′∈HP⁡(Bτi,Ai)t'_i \in\operatorname{HP}(B_{\tau i},A_i).

5. Assembly. Putting the steps together,

f=λy1…yn. a (t1′[yτ1/z1])…(tn′[yτn/zn]),f = \lambda y_1 \ldots y_n.\ a\ (t'_1[y_{\tau1}/z_1]) \ldots(t'_n[y_{\tau n}/z_n]),

which is the form of the definition of HP⁡(A,B)\operatorname{HP}(A,B) with π=τ\pi=\tau and hi=ti′h_i=t'_i. The base case n=0n=0 is f=η af=\eta\ a.

By the symmetry (f,g)↦(g,f)(f,g)\mapsto(g,f), gg is the hereditary permutation with π=σ=τ−1\pi=\sigma=\tau^{-1} and components sj′s'_j. In the formalisation, this assembly is characterisation-HP in STLC.Link.

Remark 13 (Retracts in both directions). Suppose g∘f=id⁡Ag\circ f=\operatorname{id}_A, and BB is a retract of AA by some other pair of terms. In every interpretation of the base types by non-empty finite sets, ff is then injective and ∣B∣≤∣A∣|B|\le|A|, so ff is a bijection and f∘g=id⁡f\circ g=\operatorname{id} holds semantically. By Statman’s finite completeness theorem [30, 28], f∘g=βηid⁡f\circ g={}_{\beta\eta}\operatorname{id}. 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 h∈HP⁡(A,B)h\in\operatorname{HP}(A,B) a canonical derivation der⁡h:A≅axB\operatorname{der}h:A\cong_{\mathrm{ax}}B, defined below. The theorem then follows from three facts:

  • (S) soundness: if φ∼ψ\varphi\sim\psi then ⟦φ⟧=⟦ψ⟧\llbracket\varphi\rrbracket=\llbracket\psi\rrbracket;

  • (N) normal forms: every derivation φ:A≅axB\varphi:A\cong_{\mathrm{ax}}B satisfies φ∼der⁡h\varphi\sim\operatorname{der}h for some h∈HP⁡(A,B)h\in\operatorname{HP}(A,B);

  • (St) stability: ⟦der⁡h⟧=h\llbracket\operatorname{der}h\rrbracket=h.

Indeed, ⟦−⟧\llbracket-\rrbracket is well defined on derivations modulo ∼\sim by (S), surjective by (St), and injective: if ⟦φ⟧=⟦ψ⟧\llbracket\varphi\rrbracket=\llbracket\psi\rrbracket, write φ∼der⁡h\varphi\sim\operatorname{der}h and ψ∼der⁡h′\psi\sim\operatorname{der}h' by (N); then h=⟦der⁡h⟧=⟦φ⟧=⟦ψ⟧=⟦der⁡h′⟧=h′h=\llbracket\operatorname{der}h\rrbracket=\llbracket\varphi\rrbracket=\llbracket\psi\rrbracket=\llbracket\operatorname{der}h'\rrbracket=h' by (St) and (S), so φ∼ψ\varphi\sim\psi.

In the terminology of normalisation by evaluation, ⟦−⟧\llbracket-\rrbracket is the normaliser, hereditary permutations are the normal forms and der⁡\operatorname{der} is their embedding. (S) is soundness, (N) gives completeness, φ∼der⁡⟦φ⟧\varphi\sim\operatorname{der}\llbracket\varphi\rrbracket, and (St) is stability. As in NbE, stability is an equation between normal forms, not one up to ∼\sim.

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 i:B↪B⃗′i:B\hookrightarrow\vec{B}' when B⃗′\vec{B}' arises from B⃗\vec{B} by inserting BB at position ii. Let move⁡i:B→B⃗⇒X≅B⃗′⇒X\operatorname{move}_i:B\to\vec{B}\Rightarrow X\cong\vec{B}'\Rightarrow X be the derivation that moves the first argument to position ii: move⁡0=id⁡\operatorname{move}_0=\operatorname{id} and move⁡i+1=swap⁡;(id⁡→move⁡i)\operatorname{move}_{i+1}=\operatorname{swap};(\operatorname{id}\to\operatorname{move}_i). A hereditary permutation h∈HP⁡(A1→A⃗⇒X,B⃗′⇒X)h\in\operatorname{HP}(A_1\to\vec{A}\Rightarrow X,\vec{B}'\Rightarrow X) is a triple (i,h1,h′)(i,h_1,h') (its insertion form): the first argument is inserted at i:B↪B⃗′i:B\hookrightarrow\vec{B}', h1∈HP⁡(B,A1)h_1 \in\operatorname{HP}(B,A_1), and h′∈HP⁡(A⃗⇒X,B⃗⇒X)h' \in\operatorname{HP}(\vec{A} \Rightarrow X,\vec{B} \Rightarrow X) permutes the rest. The canonical derivation der⁡h:A≅axB\operatorname{der} h : A \mathrel{\cong_{\mathrm{ax}}} B of h∈HP⁡(A,B)h \in\operatorname{HP}(A,B) is defined by recursion on hh: der⁡h=id⁡\operatorname{der} h = \operatorname{id} at a base type, and

der⁡(i,h1,h′)=((der⁡h1)−1→der⁡h′);move⁡i.\operatorname{der}(i,h_1,h') = ((\operatorname{der} h_1)^{-1} \to\operatorname{der} h');\operatorname{move}_i.

This is the derivation of Proposition 2(3); that its meaning is hh is (St), proved in § 5.3.

Normal forms

Lemma 14 (Insertions commute). Let j:C↪D⃗j : C \hookrightarrow\vec{D} insert CC into E⃗\vec{E}, and j1:D↪C⃗j_1 : D \hookrightarrow\vec{C} insert DD into D⃗\vec{D}. Then there are j1′:D↪E⃗′j'_1 : D \hookrightarrow\vec{E}' (into E⃗\vec{E}) and j′:C↪C⃗j' : C \hookrightarrow\vec{C} (into E⃗′\vec{E}') with

swap⁡;(id⁡→move⁡j);move⁡j1∼(id⁡→move⁡j1′);move⁡j′.\operatorname{swap};(\operatorname{id} \to\operatorname{move}_j);\operatorname{move}_{j_1} \sim(\operatorname{id} \to\operatorname{move}_{j'_1});\operatorname{move}_{j'}.

Proof. By induction on j1j_1 and jj. If j1=0j_1 = 0, take j1′=0j'_1 = 0 and j′=j+1j' = j + 1. If j=0<j1j = 0 < j_1, the claim is swap⁡;swap⁡∼id⁡\operatorname{swap};\operatorname{swap} \sim\operatorname{id}. Otherwise both are successors. Then naturality moves id⁡→id⁡→move⁡\operatorname{id} \to\operatorname{id} \to\operatorname{move} past a swap, the braid equation applies, and so does the induction hypothesis. □\square

Lemma 15 (Extraction). Let i:B↪B⃗i : B \hookrightarrow\vec{B} insert BB into B⃗0\vec{B}_0, and k∈HP⁡(B⃗⇒X,C⃗⇒X)k \in\operatorname{HP}(\vec{B} \Rightarrow X,\vec{C} \Rightarrow X). Then there are j:C↪C⃗j : C \hookrightarrow\vec{C} (into C⃗0\vec{C}_0), k0∈HP⁡(C,B)k_0 \in\operatorname{HP}(C,B) and k′∈HP⁡(B⃗0⇒X,C⃗0⇒X)k' \in\operatorname{HP}(\vec{B}_0 \Rightarrow X,\vec{C}_0 \Rightarrow X) with

move⁡i;der⁡k∼((der⁡k0)−1→der⁡k′);move⁡j.\operatorname{move}_i;\operatorname{der} k \sim((\operatorname{der} k_0)^{-1} \to\operatorname{der} k');\operatorname{move}_j.

Proof. By induction on ii. For i=0i = 0, take the first insertion of kk. For i+1i + 1, apply the induction hypothesis inside id⁡→−\operatorname{id} \to-, use naturality of swap, and then Lemma 14. □\square

Proposition 16 (Normal forms).

  1. Let h∈HP⁡(A,B)h \in\operatorname{HP}(A,B) and k∈HP⁡(B,C)k \in\operatorname{HP}(B,C). Then there is m∈HP⁡(A,C)m \in\operatorname{HP}(A,C) with der⁡h;der⁡k∼der⁡m\operatorname{der} h;\operatorname{der} k \sim\operatorname{der} m.

  1. Every derivation φ:A≅axB\varphi: A \mathrel{\cong_{\mathrm{ax}}} B satisfies φ∼der⁡h\varphi\sim\operatorname{der} h for some h∈HP⁡(A,B)h \in\operatorname{HP}(A,B).

Proof. (1) By induction on the height of the types, and then on h=(i,h1,h′)h = (i,h_1,h'). By Lemma 15,

der⁡h;der⁡k∼((der⁡h1)−1→der⁡h′);((der⁡k0)−1→der⁡k′);move⁡j∼((der⁡k0;der⁡h1)−1→(der⁡h′;der⁡k′));move⁡j′.\begin{aligned} \operatorname{der} h;\operatorname{der} k \sim((\operatorname{der} h_1)^{-1} \to\operatorname{der} h');((\operatorname{der} k_0)^{-1} \to\operatorname{der} k');\operatorname{move}_j \\ &\sim((\operatorname{der} k_0;\operatorname{der} h_1)^{-1} \to(\operatorname{der} h';\operatorname{der} k'));\operatorname{move}_{j'}. \end{aligned}

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 φ\varphi, proving the same statement for φ−1\varphi^{-1} at the same time. Composition uses (1). For φ→ψ\varphi\to\psi the canonical form is (0,h1,h′)(0,h_1,h') with φ−1∼der⁡h1\varphi^{-1} \sim\operatorname{der} h_1 and ψ∼der⁡h′\psi\sim\operatorname{der} h'; this is why φ−1\varphi^{-1} is carried along. For swap it is (1,id⁡,(0,id⁡,id⁡))(1,\operatorname{id},(0,\operatorname{id},\operatorname{id})). □\square

Remarks. The equations used in Proposition 16 are exactly those of § 2: the groupoid laws and functoriality, swap⁡;swap⁡\operatorname{swap};\operatorname{swap} (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 SnS_n by Coxeter relations is the special case in which all h1h_1 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 Γ\Gamma, because →\to-congruence uses it under binders. The meaning at Γ\Gamma is the closed meaning weakened to Γ\Gamma (by induction on the derivation). So it suffices to work with closed maps t∈Nf⁡(x:A,B)t \in\operatorname{Nf}(x:A,B), applied to a term by substitution, t⟨u⟩=t[u/x]t\langle u\rangle= t[u/x]. Composition is g⟨f⟩g\langle f\rangle, and the category laws are the identity and associativity laws of substitution. Write h⇒k=λf a. k⟨f(h⟨a⟩)⟩h \Rightarrow k = \lambda f\,a.\,k\langle f(h\langle a\rangle)\rangle. The remaining equations are computations of the following kind:

(h⇒k)⟨λa.L⟩=λa′. k⟨L[h⟨a′⟩/a]⟩,swap⁡⟨λa b.X⟩=λb a. X.(h \Rightarrow k)\langle\lambda a.L\rangle= \lambda a'.\,k\langle L[h\langle a'\rangle/a]\rangle,\qquad\operatorname{swap}\langle\lambda a\,b.X\rangle= \lambda b\,a.\,X.

They give functoriality, (h2⇒k2)⟨h1⇒k1⟩=h1⟨h2⟩⇒k2⟨k1⟩(h_2 \Rightarrow k_2)\langle h_1 \Rightarrow k_1\rangle= h_1\langle h_2\rangle\Rightarrow k_2\langle k_1\rangle, and swap⁡⟨swap⁡⟩=id⁡\operatorname{swap}\langle\operatorname{swap}\rangle= \operatorname{id}. For naturality, both sides compute to λf b′ a′. c⟨f(a⟨a′⟩)(b⟨b′⟩)⟩\lambda f\,b'\,a'.\,c\langle f(a\langle a'\rangle)(b\langle b'\rangle)\rangle. For the braid equation, both sides compute to λf c b a. f a b c\lambda f\,c\,b\,a.\,f\,a\,b\,c. 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 ⟦der⁡h⟧=h\llbracket\operatorname{der} h\rrbracket= h without computing ⟦der⁡h⟧\llbracket\operatorname{der} h\rrbracket by unfolding hereditary substitution. Instead we compute how meanings act on argument lists, and recover the term by η\eta: t=λy⃗. t y⃗t = \lambda\vec{y}.\,t\,\vec{y}. For i:B↪B′i : B \hookrightarrow B' and arguments a⃗\vec{a} of types B′⃗\vec{B'}, write aia_i for the argument at position ii and a⃗∖i\vec{a}\setminus i for the others. Then

⟦move⁡i⟧⟨F⟩a⃗=F ai (a⃗∖i),\llbracket\operatorname{move}_i\rrbracket\langle F\rangle\vec{a} = F\,a_i\,(\vec{a}\setminus i),

by induction on ii, from the actions of swap⁡\operatorname{swap} and of →\to: ⟦swap⁡⟧⟨F⟩ b a s⃗=F a b s⃗\llbracket\operatorname{swap}\rrbracket\langle F\rangle\,b\,a\,\vec{s} = F\,a\,b\,\vec{s} and (h⇒k)⟨F⟩ a s⃗=k⟨F(h⟨a⟩)⟩s⃗(h \Rightarrow k)\langle F\rangle\,a\,\vec{s} = k\langle F(h\langle a\rangle)\rangle\vec{s}. It follows, by induction on h=(i,h1,h′)h = (i,h_1,h'), that for a variable xx and variables y⃗\vec{y},

⟦der⁡h⟧⟨x s⃗0⟩y⃗=x s⃗0 (⟦der⁡h1⟧⟨yi⟩) sp⁡h′(y⃗∖i),\llbracket\operatorname{der} h\rrbracket\langle x\,\vec{s}_0\rangle\vec{y} = x\,\vec{s}_0\,(\llbracket\operatorname{der} h_1\rrbracket\langle y_i\rangle)\,\operatorname{sp}_{h'}(\vec{y}\setminus i),

where sp⁡h′\operatorname{sp}_{h'} is the corresponding spine for h′h'. By induction, ⟦der⁡h1⟧⟨yi⟩=h1[yi/z]\llbracket\operatorname{der} h_1\rrbracket\langle y_i\rangle= h_1[y_i/z], and the spine for h′h' consists of the arguments of h′h' with the remaining variables substituted in the same way. Taking for xx the input aa with s⃗0\vec{s}_0 empty, and for y⃗\vec{y} the bound variables, η\eta gives

⟦der⁡h⟧=λy⃗. ⟦der⁡h⟧⟨a⟩y⃗=λy⃗. a (h1[yi/z]) sp⁡h′(y⃗∖i),\llbracket\operatorname{der} h\rrbracket= \lambda\vec{y}.\,\llbracket\operatorname{der} h\rrbracket\langle a\rangle\vec{y} = \lambda\vec{y}.\,a\,(h_1[y_i/z])\,\operatorname{sp}_{h'}(\vec{y}\setminus i),

which is hh, 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, η\eta-long by construction (neutral terms only at base types). Weakening, η\eta-expansion and hereditary substitution follow [20], and are accepted by the termination checker without help. Positions in contexts are telescopes (Γ▹σ)++Δ(\Gamma\triangleright\sigma) \mathbin{++} \Delta; three rewrite rules for ++\mathbin{++} (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 t[ρ]t[\rho] is defined by structural recursion on tt, using single-variable hereditary application at a neutral, so it needs no new termination argument.

Symmetry. Maps come as pairs with an involution op\mathop{\mathrm{op}} 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.

modulelinescontent
Syntax176types, normal forms, weakening, η\eta, hereditary substitution
Lemmas347substitution lemmas; normal forms form a category
Subst400simultaneous substitution, its category laws, pairing
Iso193isomorphisms, derivations and their meaning, list-based HP
Heads264occurrences, free and bound heads; Lemmas 5, 6
LamI235the λI\lambda I predicate; Lemma 11
Tele349telescopes, bodies of η\eta-long terms, spines as substitutions
Descent305matched pairs, Lemma 8, Corollary 9
Thin168thinnings, strengthening, cancellation of renamings
Char297Lemma 12, Theorem 3
Easy280Proposition 2
Link443from the predicate form of HP to the inductive family
Coherence394level-2 equations, insertion form, Proposition 16
Sound440(S), and all derivations denote isomorphisms
Actions258how meanings act on argument lists; heads, distinct variables
Derivable140(St) for the list form; every isomorphism is the meaning of a derivation
Stable121(St) and faithfulness for insertion forms; Theorem 4
Examples89checks by computation

Table 1.

Remarks on the proofs. Freshness conditions disappear: in a matched pair, α\alpha lives over Γ1\Gamma_1, 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 η\eta.

Faithfulness of the representation. In the paper, HP(A,B)\mathrm{HP}(A,B) 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 ⟦−⟧HP\llbracket- \rrbracket_{\mathrm{HP}}, and (St) reads ⟦der h⟧=⟦h⟧HP\llbracket\mathrm{der}\ h\rrbracket= \llbracket h\rrbracket_{\mathrm{HP}}. 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 ⟦h⟧HP=λy⃗. a  (⟦h1⟧HP[yi/z])…\llbracket h\rrbracket_{\mathrm{HP}} = \lambda\vec{y}.\,a\;(\llbracket h_1\rrbracket_{\mathrm{HP}}[y_i/z])\ldots the bound variables y⃗\vec{y} are distinct, and the head of ⟦h1⟧HP[yi/z]\llbracket h_1\rrbracket_{\mathrm{HP}}[y_i/z] is yiy_i, so comparing heads fixes the insertion position ii. Renaming by a single variable is injective, so induction applies to h1h_1 and to the rest.

Related work

Invertible terms. Dezani [10] showed that a normalisable untyped λ\lambda-term is invertible modulo βη\beta\eta 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 λ\lambda-theory between βη\beta\eta and H+\mathcal{H}^{+}. 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 →\to, and extended this to ×\times and 11. 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 Π\Pi, 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 →\to. (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 →\to, β\beta-normal η\eta-long forms with hereditary substitution are canonical. For UA the type theory has Σ\Sigma, Π\Pi, 11 and an extensional boolean 22 with a large eliminator, so equality of terms involves strong η\eta for 22, 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 π\pi 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 Σ\Sigma and Π\Pi, 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 SnS_n 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: Π\Pi-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. [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. [2]T. Altenkirch. From high school to university algebra. Unfinished draft, June 2008. https://people.cs.nott.ac.uk/psztxa/publ/unialg.pdf.
  3. [3]T. Altenkirch. Towards University Algebra. In preparation.
  4. [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. [5]J. A. Bergstra and J. W. Klop. Invertible terms in the lambda calculus. Theoretical Computer Science 11(1):19–37, 1980.DOI
  6. [6]K. B. Bruce and G. Longo. Provable isomorphisms and domain equations in models of typed languages. STOC 1985, 263–272.DOI
  7. [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. [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. [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. [10]M. Dezani-Ciancaglini. Characterization of normal forms possessing inverse in the λ-β-η-calculus. Theoretical Computer Science 2(3):323–337, 1976.
  11. [11]R. Di Cosmo. Isomorphisms of Types: from λ-calculus to information retrieval and language design. Birkhäuser, 1995.DOI
  12. [12]R. Di Cosmo. A short survey of isomorphisms of types. Mathematical Structures in Computer Science 15(5):825–838, 2005.DOI
  13. [13]V. Diekert and G. Rozenberg (eds.). The Book of Traces. World Scientific, 1995.
  14. [14]J. Dunfield and N. Krishnaswami. Bidirectional typing. ACM Computing Surveys 54(5):1–38, 2021.DOI
  15. [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. [16]H. Friedman. Equality between functionals. Logic Colloquium ’73, LNM 453, 22–37, 1975.DOI
  17. [17]N. Gambino and J. Kock. Polynomial functors and polynomial monads. Math. Proc. Cambridge Philos. Soc. 154(1):153–192, 2013.DOI
  18. [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. [19]D. Ilik. Axioms and decidability for type isomorphism in the presence of sums. CSL-LICS 2014, ACM, 1–7.
  20. [20]C. Keller and T. Altenkirch. Hereditary substitutions for simple types, formalized. MSFP 2010, ACM, 3–10.DOI
  21. [21]G. M. Kelly and S. Mac Lane. Coherence in closed categories. Journal of Pure and Applied Algebra 1(1):97–140, 1971.
  22. [22]M. L. Laplaza. Coherence for distributivity. Coherence in Categories, LNM 281, 29–65, 1972.DOI
  23. [23]O. Laurent. Classical isomorphisms of types. Mathematical Structures in Computer Science 15(5):969–1004, 2005.DOI
  24. [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. [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. [26]L. Regnier and P. Urzyczyn. Retractions of types with many atoms. arXiv:cs/0212005, 2002.DOI
  27. [27]G. Scherer. Deciding equivalence with sums and the empty type. POPL 2017, 374–386.
  28. [28]R. Statman and G. Dowek. On Statman’s finite completeness theorem. Technical report CMU-CS-92-152, 1992; arXiv:2309.03602.
  29. [29]S. V. Soloviev. The category of finite sets and cartesian closed categories. Journal of Soviet Mathematics 22(3):1387–1400, 1983.DOI
  30. [30]R. Statman. Completeness, invariance and λ-definability. Journal of Symbolic Logic 47(1):17–26, 1982.DOI
  31. [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. [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. [33]N. Zeilberger. Balanced polymorphism and linear lambda calculus. Abstract, TYPES 2015, Tallinn. https://www.lix.polytechnique.fr/~zeilberger/papers/linprin.pdf.

Paper details

vlnc:W_d56ay3x9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents