🔢 mathematics

On the structure and theory of McCarthy algebras

This paper provides a structural analysis of McCarthy algebras by defining them as a subvariety of involutive unital bands, offering new axiomatizations, a semilattice decomposition theorem, and a representation via decorated posets to unify various non-classical logics.

Original authors: Stefano Bonzio, Gavin St. John

Published 2026-06-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Stefano Bonzio, Gavin St. John

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

The Big Picture: A New Way to Organize Logic

Imagine you are a librarian trying to organize books. You have a standard section for "True" books and a section for "False" books. This is how classical logic works (like a light switch: on or off).

But in the real world of computers, things aren't always so simple. Sometimes a program tries to do something, but it crashes or gets stuck. It's not "True" (it worked), and it's not "False" (it didn't work); it's in a state of "Error" or "Undefined."

This paper is about a specific mathematical system called McCarthy Algebra. It's the rulebook for handling that third state (the "Error" state) when you are combining instructions in a computer program. The authors, Stefano Bonzio and Gavin St. John, have built a new "filing cabinet" to understand exactly how these rules work, how they are built, and how they relate to other types of logic.

The Main Characters: The Three-Valued System

The paper focuses on a specific 3-element system (let's call it M3). Think of these three elements as three types of traffic lights:

Green (1): Go (True).
Red (0): Stop (False).
Yellow/Flashing (ε): Caution/Error (Undefined).

In standard logic, if you combine "Green" and "Red," you get a clear result. But in McCarthy logic, the order matters. If you check a condition before you check a second one, and the first one is "Error," the second one never gets checked. This is called lazy evaluation (like a chef who stops cooking a dish the moment they realize they are out of eggs; they don't bother checking if they have salt).

The paper studies the algebraic "machinery" behind this behavior.

The New Filing Cabinet: "i-ubands"

To understand McCarthy logic, the authors didn't just look at the traffic lights; they looked at the whole warehouse they live in. They introduced a new, broader category of mathematical structures they call i-ubands (which stands for "unital bands with involution").

The Analogy:
Imagine i-ubands as a massive, flexible warehouse.

Inside this warehouse, you can find Boolean Algebras (the standard True/False logic).
You can find Kleene Algebras (logic with a "Maybe" state, used in fuzzy logic).
And you can find McCarthy Algebras (the specific logic for computer errors).

The authors realized that McCarthy logic is just a special, slightly more complex version of these other logics. It's like realizing that a "sports car" is just a specific type of "vehicle" with a few extra rules about speed and steering. By studying the whole warehouse (i-ubands), they can understand the sports car (McCarthy) better.

The Three Major Discoveries

The paper makes three main contributions, which we can think of as three new tools for the mathematician's toolbox:

1. The "Simplified Rulebook" (Axiomatization)

For a long time, the rules for McCarthy logic were a bit messy or incomplete. The authors found a short, clean list of rules (axioms) that perfectly describes how this system works.

The Metaphor: Imagine you have a complicated instruction manual for a machine with 50 steps. The authors found that you can actually run the machine perfectly with just 3 or 4 core rules. They proved that if you follow these specific rules, you must be doing McCarthy logic, and nothing else.

2. The "Layer Cake" (Semilattice Decomposition)

This is perhaps the most visual discovery. The authors proved that any complex McCarthy algebra can be broken down into a stack of simpler layers.

The Metaphor: Think of a McCarthy algebra as a layer cake.
- The frosting between the layers is a simple "True/False" (Boolean) logic.
- The cake layers themselves are also simple "True/False" logic.
- The "glue" holding them together is a specific ordering system (a semilattice).
Why it matters: Instead of trying to understand the whole giant cake at once, you can take it apart. You see that every complex McCarthy system is actually just a collection of simple True/False systems stacked on top of each other in a specific way. This makes them much easier to study.

3. The "Blueprint" (Decorated Posets)

Finally, the authors showed that you can draw a map of these algebras.

The Metaphor: Imagine a family tree or a hierarchy chart.
- The "nodes" on the chart represent the values (True, False, Error).
- The "lines" show who is "greater than" whom.
- The authors proved that if you have this specific type of chart (which they call a "decorated poset"), you can rebuild the entire algebra just by looking at the drawing.
The Result: They even counted how many different "shapes" of these charts exist for small sizes (up to 14 items), creating a "Fine Spectrum" (a census) of all possible McCarthy algebras.

What This Means (According to the Paper)

The paper does not claim to fix bugs in Java or Python, nor does it predict the future of AI. Its claims are strictly mathematical:

Definition: They defined a new, broader family of algebras (i-ubands) that includes McCarthy logic.
Structure: They proved that McCarthy algebras are made of simpler Boolean algebras stacked in a specific order.
Representation: They showed that these algebras can be perfectly represented by specific types of diagrams (posets).
Classification: They identified that McCarthy logic sits right on top of Boolean logic in the hierarchy of logical systems (it "covers" Boolean algebras).

Summary

In short, the authors took a specific, tricky logic used by computers to handle errors, and they built a comprehensive mathematical map for it. They showed that this complex logic is actually built out of simple, familiar pieces (True/False logic) arranged in a very specific, orderly structure. They provided the exact rules to build it, the method to take it apart, and a way to draw it on paper so anyone can see how it works.

Technical Summary: On the Structure and Theory of McCarthy Algebras

Problem Statement
McCarthy algebras constitute the algebraic counterpart to McCarthy logic, a three-valued logic based on non-commutative conjunction used to model lazy evaluation of partial predicates in computer science (e.g., in Haskell, OCaml, Java, and Python). While the utility of McCarthy logic in process algebras for modeling error handling and conditional guards is established, its algebraic structure has remained underexplored. Specifically, while Guzmán and Squier [13] provided a finite basis for the constant-free reduct (Conditional algebras or C-algebras), and Konikowska [18] proposed a list of identities for the three-element algebra $M_3$ , a comprehensive structural analysis and a reduced equational basis for the full variety of McCarthy algebras (including constants) were lacking. Furthermore, the relationship between McCarthy algebras and other non-classical logics (such as Kleene logics and Boolean algebras) within a unified algebraic framework required clarification.

Methodology
The authors introduce a general algebraic framework called i-ubands (unital bands with involution). An i-uband is defined as an idempotent monoid $\langle M, \cdot, e \rangle$ equipped with a unary involutive operation $'$ satisfying $x'' \approx x$ . This structure serves as a common ground for various non-classical logics, including Boolean algebras, ortholattices, De Morgan algebras, and Kleene algebras.

The methodology proceeds as follows:

Definition and Classification: The authors analyze the variety of i-ubands, specifically focusing on subclassical i-ubands (those containing the two-element Boolean algebra as a subalgebra). They classify all non-isomorphic 3-element i-ubands, identifying four subclassical models: the weak Kleene algebra ($WK$), the strong Kleene algebra ($SK$), the McCarthy algebra ( $M_3$ ), and its mirror $M_3^{op}$ .
Identity Analysis: The paper investigates the identities satisfied by $M_3$ within the context of i-ubands. This involves deriving weak distributive laws (left-distributivity, orthodistributivity), weak absorption laws, and weak commutative laws (local-unit commutativity).
Axiomatization: By analyzing the interaction of these identities, the authors derive reduced and equivalent equational bases for the variety of McCarthy algebras.
Structural Decomposition: The authors utilize the partial order induced by the addition operation ( $+$ ) to decompose McCarthy algebras. They define a "semilattice skeleton" and "fibers" to establish a semilattice decomposition theorem.
Representation: The algebraic structure is characterized via sℓ-decorated posets (partially ordered sets decorated with a semilattice skeleton), demonstrating that the operations are uniquely determined by the order and the membership in the skeleton.

Key Contributions and Results

Unified Framework (i-ubands): The paper establishes i-ubands as a general setting for studying non-commutative versions of classical and non-classical logics. It clarifies the distinction between i-ubands and involution band semigroups, noting that i-ubands only require $x'' \approx x$ rather than the stronger $(xy)' \approx y'x'$ .
Reduced Axiomatization: The authors provide a finite equational basis for the variety $\mathcal{M}$ $M$ of McCarthy algebras. They prove that $\mathcal{M}$ $M$ coincides with the variety of MK-algebras (McCarthy-Konikowska algebras). The basis is presented in terms of three components:
1. Weak Distributivity: At least one of left-distributivity with left-decomposition, left-divisibility with right-orthodistributivity, or right-paradistributivity.
2. Weak Absorption: At least one of left-boundedness or left-absorption.
3. Weak Commutativity: At least one of local-unit commutativity, local commutativity, or wk-commutativity.
  This result confirms that Konikowska's postulates form an equational basis and provides alternative, reduced formulations.
Subdirectly Irreducible Members: The paper proves that the only subdirectly irreducible McCarthy algebras are the two-element Boolean algebra ($2$) and the three-element McCarthy algebra ( $M_3$ ). Consequently, the variety $\mathcal{M}$ is generated by $M_3$ .
Semilattice Decomposition: A central result is the Semilattice Decomposition Theorem (Theorem 6.1). Every McCarthy algebra $A$ $A$ decomposes into a semilattice direct system of Boolean algebras $\langle I_A, \mathcal{B}_A, \mathcal{P}_A \rangle$ $⟨ I_{A}, B_{A}, P_{A} ⟩$ , where:
- $I_A$ is the semilattice skeleton of $A$ (isomorphic to the set of local units $\{x \cdot 0 \mid x \in A\}$ ).
- $\mathcal{B}_A$ is the set of fibers (intervals $[0_i, 1_i]$ ), each of which is a Boolean algebra.
- $\mathcal{P}_A$ consists of homomorphisms between fibers induced by the order.
  Unlike standard semilattice sums (e.g., Clifford semigroups), this decomposition is not generally a quotient of the algebra, distinguishing it from classical semilattice decomposition theorems.
Representation as Decorated Posets: The authors show that McCarthy algebras are fully determined by their sℓ-decorated posets. The operations (multiplication, involution) can be expressed using the partial order, existing suprema/infima, and a unary predicate identifying the semilattice skeleton. This leads to a characterization of isomorphism: two McCarthy algebras are isomorphic if and only if their sℓ-decorated posets are isomorphic.
Lattice of Subvarieties: The paper sketches the lower levels of the lattice of subvarieties of i-ubands. It identifies that McCarthy algebras form a subclassical variety (where the unit is not an involution fixed-point) and that $\mathcal{M}$ covers the variety of Boolean algebras ($BA$) in this lattice. It also identifies open problems regarding the finite axiomatization of the varieties generated by the Sugihara monoid reduct ( $C_3^s$ ) and its left/right variants ( $L_3^s, R_3^s$ ).

Significance
The paper provides the first comprehensive structural analysis of McCarthy algebras, moving beyond the identification of their equational basis to a deep understanding of their internal architecture. By introducing i-ubands, the authors unify the study of McCarthy logic with other non-classical logics, revealing McCarthy logic as the non-commutative companion to Kleene and Boolean logics. The decomposition theorem and the representation via decorated posets offer new tools for analyzing these algebras, potentially facilitating further research into their model theory and applications in computer science, particularly in the formal verification of processes involving error handling and lazy evaluation. The work also clarifies the precise position of McCarthy algebras within the broader landscape of algebraic logic, specifically their relationship to Boolean algebras and the lattice of subvarieties of i-ubands.