🔢 mathematics

Doctrinal Semantics of Directed First-Order Logic

This paper introduces a directed first-order logic featuring asymmetric equality and a polarity-based syntactic system, providing a sound and complete categorical semantics via "directed doctrines" that characterize directed equality as a relative left adjoint and generalize Lawvere's classical equality.

Original authors: Andrea Laretto, Fosco Loregian, Niccolò Veltri

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrea Laretto, Fosco Loregian, Niccolò Veltri

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 you are trying to write a set of rules for a game where things can change, but the rules for "change" are different from the rules for "sameness."

In standard logic (the kind used in math and computer science), equality is like a mirror. If $A$ is equal to $B$ , then $B$ is automatically equal to $A$ . It's a two-way street. But in the real world, many things are directed. If you rewrite a document, you go from Version 1 to Version 2. You can't just magically go back to Version 1 without doing the work again. If you have a process that turns a raw egg into a cooked egg, that process doesn't work in reverse.

This paper introduces a new kind of logic called Directed First-Order Logic. Think of it as a rulebook for a world where "equality" is actually a one-way street, or a "rewrite."

Here is the breakdown of their ideas using simple analogies:

1. The Problem: The "Mirror" vs. The "Arrow"

In traditional logic, if you say "x equals y," you are saying they are interchangeable.

The Mirror: If I hold a mirror up to you, your reflection looks just like you. If I swap you with your reflection, nothing changes.
The Arrow: In this new logic, the relationship is an arrow ( $x \le y$ ). It means "x can become y" or "x rewrites to y." But you cannot necessarily go from $y$ back to $x$ .

The authors wanted to build a logic system that treats these arrows as the fundamental building blocks, rather than just adding them as an afterthought.

2. The Solution: "Polarity" (The Traffic Lights)

The biggest headache in creating this logic is keeping track of direction.
Imagine a traffic intersection.

Positive variables are cars driving forward.
Negative variables are cars driving backward (or looking at the road from the opposite direction).
Dinatural variables are cars that can drive in both directions, but only if they are careful.

In standard logic, you don't need to worry about which way a car is facing; it's just a car. In this new logic, the authors invented a system of Polarities. They split the "context" (the list of variables available to use) into three separate lanes:

The Negative Lane: Variables here can only be used in "backward" positions.
The Positive Lane: Variables here can only be used in "forward" positions.
The Dinatural Lane: Variables here are special; they can appear in both lanes, but they must be the same variable in both places (like a car that drives forward and backward simultaneously in a loop).

This system acts like a strict traffic cop. It prevents you from accidentally writing a rule that says "If A becomes B, then B becomes A" (which would break the one-way nature of the logic). It forces the logic to respect the direction of the arrow.

3. The "Magic Trick": Relative Adjunctions

The paper uses a fancy mathematical concept called an "adjunction" to explain how equality works.

Old Logic: Equality is like a machine that takes two variables and squashes them into one.
New Logic: Because the arrows are one-way, you can't just squash them. You need a machine that takes two variables (one facing forward, one facing backward) and squashes them into a single "loop" variable.

The authors prove that this "directed equality" is the best possible way to do this squashing, given the rules of the road (the polarities). They call this a "Relative Left Adjoint." In plain English: It's the most efficient way to combine a forward-moving thing and a backward-moving thing into a single unit, without breaking the rules of the system.

4. The "Doctrines" (The Rulebook)

To make sure their logic actually works, they built a "Doctrinal Semantics."
Think of a Doctrine as a dictionary that translates the abstract rules of the logic into a concrete world.

In their world, Types are Preorders.
- What is a Preorder? Imagine a list of items where some are "less than or equal to" others, but not everything is comparable. For example, in a video game, "Level 1" is less than "Level 2," but "Level 1" isn't necessarily less than "Level 3" in a direct line (you might skip it).
They proved that their logic is Sound and Complete.
- Sound: If you can prove something in their rulebook, it is true in the real world (the preorder world).
- Complete: If something is true in the real world, you can prove it using their rulebook.

5. Why This Matters (According to the Paper)

The authors show that this logic is perfect for describing things that happen in steps or processes, like:

Rewriting: Changing a sentence in a document.
Graph Rewriting: Changing the connections in a network (like a social network or a computer circuit).
Petri Nets: A way to model how resources move through a system (like customers in a bank or tokens in a game).

They specifically mention that this logic is proof-irrelevant. This means they don't care how you got from A to B (the specific path or proof), only that you can get from A to B. This is different from some advanced computer science theories that care about every single step of the journey.

Summary

The authors have built a new language for logic that treats "change" as a one-way street. To keep the traffic flowing correctly, they invented a system of "lanes" (polarities) to ensure variables don't get confused about which way they are facing. They proved that this system is mathematically solid and perfectly matches a world where things are ordered but not necessarily symmetric (like a to-do list or a game progression).

They didn't invent this to cure diseases or build new apps directly; they did it to fix a fundamental gap in how mathematicians and computer scientists understand the logic of "directed" change.

Technical Summary: Doctrinal Semantics of Directed First-Order Logic

1. Problem Statement

The paper addresses the challenge of formalizing directed equality within a logical framework. While Lawvere's categorical perspective successfully characterized classical equality as a left adjoint to contraction, this approach relies on symmetry. In directed type theory, where types are interpreted as categories (or preorders) rather than groupoids (or sets), equality becomes an asymmetric relation (e.g., a rewrite $a \to b$ or an order $a \le b$ ).

The core difficulty lies in handling variance (polarity). In a directed setting, a variable may appear in a "negative" position (contravariant, e.g., the source of a morphism) or a "positive" position (covariant, e.g., the target). Standard logical rules for equality (reflexivity and the J-rule/elimination) fail in this context because they implicitly assume symmetry or allow variables to appear in both polarities simultaneously in ways that would derive symmetry ( $a \le b \vdash b \le a$ ), which is invalid in directed logic. Previous attempts at directed type theory often struggle with these polarity constraints, particularly in the context of proof-irrelevant logic (where equality is a proposition, not a type with multiple inhabitants).

2. Methodology

The authors develop a directed first-order logic (dFOL) and its doctrinal semantics by generalizing Lawvere's framework of hyperdoctrines.

Syntax: Polarized Contexts

The syntax introduces a polarized context $[\Theta \mid \Delta \mid \Gamma]$ , partitioning variables into three sets based on their variance:

$\Theta$ (Negative): Variables appearing only in contravariant positions.
$\Gamma$ (Positive): Variables appearing only in covariant positions.
$\Delta$ (Dinatural): Variables appearing in both positions (or allowed to be treated as such).

Key syntactic features include:

Directed Equality ( $\le_A$ ): A primitive relation $s \le_A t$ where $s$ is typed in the negative context and $t$ in the positive context.
Polarized Implication: The implication $\psi \Rightarrow \phi$ swaps the polarity of the context for $\psi$ (moving it from the left to the right of the turnstile), reflecting the contravariance of the first argument.
Polarized Quantifiers: Quantifiers ( $\forall^p, \exists^p$ ) are indexed by polarity $p \in \{-, \Delta, +\}$ to track the variance of the bound variable.
Substitution Rules: A specialized substitution mechanism (Definition 2.7) handles the reindexing of terms across polarized contexts, ensuring that dinatural variables are substituted consistently.

Semantics: Directed Doctrines

The semantics is captured via directed doctrines, a generalization of Lawvere's doctrines.

Base Category: Instead of a standard category of types, the base is a polarization category $ndp(\mathcal{C})$ , whose objects are triples $(\Theta, \Delta, \Gamma)$ and morphisms respect the variance structure.
Fibered Structure: A functor $P: ndp(\mathcal{C})^{op} \to \mathbf{Pos}$ maps polarized contexts to posets of formulas.
Key Conditions:
- No-Dinatural-Variance (ndv): A condition ensuring that dinatural variables in predicates arise only from collapsing positive and negative variables, preventing "third" types of variance.
- Relative Adjunctions: Directed equality is characterized not as a standard left adjoint, but as a left relative adjoint to a contraction-like operation that collapses two variables of opposite polarity into a single dinatural variable. This captures the syntactic restriction that prevents deriving symmetry.
- Polarized Implication: Characterized as a relative coadjoint.

3. Key Contributions

Syntax of dFOL: A precise natural deduction system for first-order logic with directed equality, featuring a rigorous system of polarities inspired by dinaturality. This system explicitly forbids the derivation of symmetry for directed equality while maintaining standard logical connectives.
Characterization of Directed Equality: The paper generalizes Lawvere's "equality as left adjoint" to directed equality as a left relative adjoint. This provides a precise categorical universal property for directed equality that accounts for the asymmetry of the relation.
Directed Doctrines: The introduction of directed doctrines as a semantic framework. The authors prove that the syntax of dFOL is sound and complete with respect to this semantics.
Preorder Completeness: A specific completeness result is proven for the classical fragment of dFOL with respect to the standard model of preorders ( $\mathbf{Preord}$ ). This establishes that any entailment valid in all preorder models is derivable in the syntax.
Handling of Polarity: The paper demonstrates how to manage variance in a proof-irrelevant setting, distinguishing it from proof-relevant directed type theories (like those in $\mathbf{Cat}$ ) by using posetal fibrations and poset-valued fibers.

4. Results

Soundness and Completeness: The authors establish a bi-adjunction between the category of theories ( $\mathbf{Theory}$ ) and the 2-category of directed doctrines ( $\mathbf{DDoctrine}$ ). This implies that dFOL is the internal language of directed doctrines.
Completeness for Preorders: Using a Henkin-style construction adapted for polarized contexts, the paper proves that the classical fragment of dFOL is complete with respect to the model of preorders. The construction defines the domain of the model as the set of closed terms ordered by the derivability of directed equality ( $\le_A$ ).
Derived Rules: The system supports derived rules for transitivity, reflexivity, and congruence of directed equality, as well as interaction rules between polarized quantifiers and implication.
Counterexamples: The paper illustrates that symmetry ( $a \le b \vdash b \le a$ ) is not derivable, and the preorder model serves as a countermodel for such derivations.

5. Significance and Claims

The paper claims to advance the work of Lawvere on the role of variance and hom-functors in logic. Specifically:

It provides a precise syntactic and semantic characterization of directed equality in a proof-irrelevant setting, filling a gap between classical logic and directed type theory.
It generalizes the concept of equality as an adjoint to the directed case via relative adjunctions, offering a new categorical tool for understanding directed structures.
It demonstrates that directed logic can be treated with standard logical techniques (like Henkin completeness) by carefully managing polarities through polarized contexts, rather than requiring complex geometric or higher-categorical machinery.
The work is positioned as a foundational step for reasoning about rewriting systems and directed phenomena (processes, transitions) within a logical framework, distinct from the proof-relevant approaches of Homotopy Type Theory.

The authors explicitly state that their focus is on the proof-irrelevant case, justified by the nature of rewriting logic (where a rewrite either happens or it does not) and the use of posetal fibrations in categorical logic. They do not claim to solve the full complexity of dependent directed type theory but provide a robust foundation for the first-order, preorder-based case.