💻 computer science

Groups and Inverse Semigroups in Lambda Calculus

This paper utilizes inverse semigroups to characterize the invertible $\lambda$ -terms (specifically finite and infinite hereditary permutations) across various $\lambda$ -theories, demonstrating that their natural order corresponds to $\eta$ -expansion and proving that finite hereditary permutations constitute the invertible elements in all theories between $\lambda\eta$ and Morris' observational theory $H^+$ .

Original authors: Antonio Bucciarelli, Arturo De Faveri, Giulio Manzonetto, Antonino Salibra

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonio Bucciarelli, Arturo De Faveri, Giulio Manzonetto, Antonino Salibra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the world of computer science as a giant, infinite library of instructions called Lambda Calculus. In this library, every piece of code is a "term" (a recipe for doing something). Usually, we care about whether two recipes produce the same result. But this paper asks a much more specific question: Which recipes can be perfectly "undone"?

In math terms, if you have a recipe $M$ , is there another recipe $N$ such that if you do $M$ then $N$ , you end up exactly where you started (like pressing "Undo" perfectly)? If so, $M$ is invertible.

The authors of this paper discovered that the set of all these "undoable" recipes isn't just a random list; it forms a very specific, beautiful mathematical structure called an Inverse Semigroup.

Here is the breakdown using simple analogies:

1. The Library of Recipes (Lambda Calculus)

Think of Lambda Calculus as a language where you can build complex machines out of simple gears.

The Problem: In most versions of this language, the only machine that can be perfectly undone is the "Identity Machine" (a machine that does nothing). It's like saying, "The only thing you can undo is doing nothing." That's boring!
The Twist: But if you change the rules of the library slightly (adding "extensionality," which means looking at how the machine behaves rather than just its code), suddenly, many more machines become undoable.

2. The "Hereditary Permutations" (The Undoable Machines)

The paper focuses on a special family of these undoable machines called Finite Hereditary Permutations (FHPs) and their infinite cousins (HPs).

The Analogy: The Sorting Machine
Imagine a machine that takes a stack of boxes, rearranges them in a specific order, and then passes them to the next machine.

A Finite Hereditary Permutation (FHP) is like a machine that takes a finite stack of boxes, shuffles them around in a complex way, but guarantees that you can always find a "reverse shuffle" machine to put them back in the original order.
These machines are special because they don't just shuffle; they can also "expand" (add empty boxes to the stack) and "contract" (remove them), as long as the final result is reversible.

3. The New Structure: Inverse Semigroups

The authors realized that these machines don't just form a "Group" (where everything has an inverse). They form something richer called an Inverse Semigroup.

The Analogy: The Partial Mirror

A Group is like a perfect mirror: If you look in it, you see your whole self, and the reflection is perfect.
An Inverse Semigroup is like a broken mirror or a partial mirror.
- Some parts of the mirror show your whole self (the "Identity").
- Other parts only show your left arm, or just your eyes.
- However, even if the mirror is broken, there is still a specific "reverse" piece that fits perfectly to undo the specific view you have.
- The paper shows that the "undoable" Lambda terms are exactly these partial mirrors. They are flexible enough to handle partial information but strict enough to be reversible.

4. The "Natural Order" (The Ladder of Complexity)

One of the coolest discoveries is that these machines have a natural "ladder" or order.

The Analogy: Zooming In and Out
- Imagine a picture. You can have a "zoomed-out" version (simple) and a "zoomed-in" version (detailed).
- In this math world, you can take a simple "undoable" machine and expand it (add more detail/structure) to make a more complex one.
- The paper proves that this "expansion" is exactly the same as the mathematical "order" in the Inverse Semigroup.
- FHPs (Finite): You can only expand a finite number of times.
- HPs (Infinite): You can expand infinitely, creating machines with infinite depth.

5. The "Kite" of Theories

The paper looks at different "rulesets" (Theories) for this library.

The Bottom Rule ( $\lambda\eta$ ): The strictest rule where only finite expansions are allowed. Here, the undoable machines are the FHPs.
The Top Rule ( $H^*$ ): The most relaxed rule where infinite expansions are allowed. Here, the undoable machines are the HPs.
The Middle Rule ( $H^+$ ): This is the tricky middle ground. For a long time, mathematicians wondered: "If we are in the middle, do we get a mix of finite and infinite machines?"
- The Big Discovery: The authors proved that NO. Even in the middle ground, the only undoable machines are the Finite ones (FHPs).
- The Metaphor: Imagine a river flowing from a mountain (infinite) to a lake (finite). You might think the middle of the river has both deep and shallow water. But this paper says, "Actually, the middle of the river is shallow all the way through." The "infinite" machines only appear if you go all the way to the very top rule.

Summary of the Main Contributions

New Lens: They stopped looking at these code recipes as just "code" and started looking at them as Inverses Semigroups (partial mirrors). This revealed hidden structure.
The Connection: They proved that the "order" of these machines (how complex they are) is exactly the same as the "expansion" of the code (adding more steps).
Solving a Mystery: They settled a decades-old guess (Barendregt's conjecture) that in a specific middle-ground rule of the language, the only machines you can "undo" are the finite ones, not the infinite ones.

In a nutshell: The authors took a complex problem about "undoing code," realized it behaves like a system of "partial mirrors," and used that insight to prove exactly which types of code can be undone in different versions of the programming language. It's a beautiful blend of algebra, logic, and computer science.

1. Problem Statement

The paper addresses the fundamental problem of characterizing invertible $\lambda$ -terms modulo various $\lambda$ -theories.

Context: In the $\lambda$ -calculus, a term $M$ is invertible in a theory $T$ if there exists a term $N$ such that $M \circ N = N \circ M = I$ (where $\circ$ is composition and $I$ is the identity).
Known Results:
- In the minimal theory ( $=\beta$ ), only $I$ is invertible.
- In the extensional theory ( $=\beta\eta$ ), the invertible terms are the Finite Hereditary Permutations (FHPs).
- In the greatest sensible theory ( $H^*$ ), the invertible terms are the Hereditary Permutations (HPs), which allow for infinite Böhm trees.
The Gap: A long-standing conjecture by Barendregt asked whether the FHPs constitute the group of invertible terms for all $\lambda$ -theories lying between $=\beta\eta$ and $H^+$ . $H^+$ is Morris's observational theory where equality is defined by the existence of $\beta$ -normal forms. Previous methods struggled to characterize invertibility in intermediate theories like $H^+$ because they did not account for the interaction between finite and infinite structures.

2. Methodology

The authors introduce a novel algebraic framework based on Inverse Semigroups to generalize the study of invertibility beyond groups.

A. Inverse Semigroups

Instead of treating the set of invertible terms strictly as a group, the authors model them as inverse semigroups.

An inverse semigroup is a structure where every element $u$ has a unique inverse $u^*$ such that $uu^*u = u$ and $u^*uu^* = u^*$ .
Crucially, inverse semigroups possess a natural partial order ( $u \leq v$ iff $u = ev$ for some idempotent $e$ ).
They distinguish between E-unitary and F-inverse semigroups. An F-inverse semigroup ensures that every equivalence class under the "minimum group congruence" ( $\sigma$ ) has a unique maximal element.

B. Permutation Trees (PT)

To provide a concrete representation, the authors define a monoid of Permutation Trees (PT):

Structure: Labelled ordered trees where internal nodes are labeled with permutations from the symmetric group $S_n$ .
Operations: They define a product operation and a unary inverse operation ( $^*$ ) on these trees coinductively.
Isomorphism: They prove that the monoid of Permutation Trees is isomorphic to the monoid of Hereditary Permutations (HP) modulo Böhm tree equality.

C. The Natural Order and $\eta$ -Expansion

The core insight is the correspondence between the algebraic natural order on inverse semigroups and $\eta$ -expansion in $\lambda$ -calculus:

In the context of FHP (finite trees), the natural order corresponds to finite $\eta$ -expansion.
In the context of HP (infinite trees), the natural order corresponds to infinite $\eta$ -expansion.
The authors define specific "maximal element" operators ( $t^m$ and $t^{m'}$ ) that map any tree to its unique maximal representative in its congruence class.

3. Key Contributions

1. Algebraic Characterization of Invertibility

The paper recasts the invertibility of $\lambda$ -terms using the theory of inverse semigroups:

FHP/ $\lambda$ forms an inverse monoid.
HP/Böhm forms an inverse monoid.
The quotient of these monoids by the minimum group congruence ( $\sigma$ ) yields the group of invertible elements in the corresponding $\lambda$ -theory.

2. Resolution of Barendregt's Conjecture

The authors prove that for any $\lambda$ -theory $T$ such that $\lambda\eta \subseteq T \subseteq H^+$ , the set of invertible terms is exactly FHP.

This settles the conjecture that FHPs are the invertible terms for theories like $B\eta$ and $B\omega$ (which lie between $\lambda\eta$ and $H^+$ ).
The proof relies on showing that in $H^+$ , the interaction between Böhm trees and finite $\eta$ -expansions forces any invertible term to be finite (i.e., an FHP), even though the theory allows for infinite trees in general.

3. New Congruences for Intermediate Theories

The paper introduces a refined congruence relation, $\sigma'$ , distinct from the standard minimum group congruence $\sigma$ .

$\sigma$ corresponds to $H^*$ (infinite $\eta$ -expansion).
$\sigma'$ corresponds to $H^+$ (finite $\eta$ -expansion).
This distinction allows the authors to separate the behavior of invertible terms in theories that are extensional but do not equate all unsolvable terms in the same way $H^*$ does.

4. Structural Properties of Permutation Trees

The monoid of finite permutation trees (FPT) is proven to be residually finite.
The paper characterizes the covering relation in the natural order of FPTs, linking structural tree changes directly to single $\eta$ -reduction steps.

4. Key Results

Theorem 39 & 43: Establishes that for $M, N \in HP$ (or FHP), $M = N$ in $H^*$ (or $\lambda\eta$ ) if and only if their maximal representatives (under the natural order) are identical. This links syntactic equality in $\lambda$ -theories to algebraic maximality in inverse semigroups.
Theorem 49: Proves that a term $M$ $M$ is invertible in $H^+$ $H^{+}$ if and only if $M \in \text{FHP}$ $M \in FHP$ .
- Logic: If $M$ is invertible in $H^+$ , it is invertible in $H^*$ , so $M \in HP$ . However, the specific constraints of $H^+$ (requiring $\beta$ -normal forms) force the composition $M \circ N$ to be a finite $\eta$ -expansion of $I$ , implying $M$ itself must be finite.
Theorem 51: Generalizes the result: For any theory $T$ where $\lambda\eta \subseteq T \subseteq H^+$ , the group of invertible elements is FHP. If $T$ is non-extensional and semisensible, the only invertible element is $I$ .

5. Significance

Unification: The paper unifies the study of invertibility across a wide spectrum of $\lambda$ -theories (from $\lambda\eta$ to $H^*$ ) under a single algebraic framework (Inverse Semigroups).
Conceptual Clarity: It clarifies the role of idempotents in $\lambda$ -calculus. In inverse semigroups, idempotents form a semilattice; in $\lambda$ -calculus, these correspond to $\eta$ -expansions. The "minimum group congruence" effectively collapses these idempotents to the identity, recovering the group structure.
Solving Open Problems: It definitively answers Barendregt's conjecture regarding the invertible terms in the "kite" of $\lambda$ -theories (specifically $B\eta$ and $B\omega$ ), confirming they are FHPs.
Future Directions: The framework provides a roadmap for studying theories strictly between $H^+$ and $H^*$ , suggesting that the group of invertible elements in such theories might be strictly intermediate between FHP and HP, governed by different semilattices of idempotents.

In summary, the paper demonstrates that Inverse Semigroups are the natural algebraic structure for understanding $\lambda$ -term invertibility, replacing the limited view of groups with a richer structure that accounts for partial symmetries and $\eta$ -expansions, thereby solving a decades-old problem in the semantics of the $\lambda$ -calculus.