🔢 mathematics

Univalence without function extensionality

This paper demonstrates that a weaker variant of the univalence axiom, termed "categorical univalence," does not imply function extensionality by analyzing Von Glehn's polynomial model construction, which yields models of Martin-Löf type theory that satisfy categorical univalence while refuting function extensionality.

Original authors: Evan Cavallo, Jonas Höfer

Published 2026-05-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Evan Cavallo, Jonas Höfer

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: The "Perfect Match" Rule

Imagine you are building a massive library of mathematical objects (called types). In this library, you have a special rule called Univalence.

Think of Univalence as a "Perfect Match" rule. It says: If two books in the library are "equivalent" (they contain the same information and can be transformed into each other), then they are actually the same book.

For a long time, mathematicians thought this rule was a package deal. They believed that to have the "Perfect Match" rule, you also needed a second rule called Function Extensionality.

Function Extensionality is like a rule for recipes. It says: If two recipes produce the exact same cake for every single ingredient you put in, then the two recipes are the same recipe, even if the steps to get there look different on paper.

The big question this paper asks is: Can you have the "Perfect Match" rule for the library without having the "Same Recipe" rule?

The Discovery: Breaking the Package Deal

The authors, Evan Cavallo and Jonas Höfer, say Yes, you can.

They found a way to build a mathematical universe where the "Perfect Match" rule works, but the "Same Recipe" rule fails. This means you can have a library where equivalent books are identical, but two different recipes that bake the same cake are still considered different.

To prove this, they didn't just argue with words; they built a specific "machine" (a mathematical model) that generates these weird universes. They used a construction called the Polynomial Model (invented by Von Glehn).

The Machine: The "Shape and Position" Factory

To understand how their machine works, imagine a factory that builds toys.

The Shape: Every toy has a main shape (like a cube, a sphere, or a star).
The Position: Inside the shape, there are little "slots" where you can put extra parts.

In this factory, two toys are considered identical only if:

Their Shapes are identical.
Their Positions (the slots) are identical.

The authors built a factory where they can tweak the "Positions" independently of the "Shapes."

The "Same Recipe" Failure (Function Extensionality): In this factory, you can have two machines (functions) that take a shape and produce a toy. Even if both machines produce the exact same toy for every input, the factory considers them different because the internal wiring (the positions) of the machines is slightly different. The factory refuses to say, "Oh, they do the same job, so they are the same machine."
The "Perfect Match" Success (Categorical Univalence): However, the factory does follow the "Perfect Match" rule for the library of toys. If two toys are equivalent (you can swap them back and forth without breaking anything), the factory agrees they are the same toy.

The "Wild Category" Concept

The paper introduces a concept called a "Wild Category."

Imagine a chaotic playground where kids (objects) run around.

In a normal, well-behaved playground, if two kids can swap places perfectly, they are considered the same.
In this Wild Category, the rules are a bit looser. The authors define a specific version of the "Perfect Match" rule called Categorical Univalence. This rule only cares about whether you can swap things back and forth using strict, rigid steps (like snapping Lego bricks together), not loose, wobbly steps.

They proved that you can have a playground where this "Categorical Univalence" rule holds true, even though the "Same Recipe" rule (Function Extensionality) is broken.

Why Does This Matter?

For years, mathematicians thought the "Perfect Match" rule (Univalence) was a giant, indivisible block. They thought you couldn't take it apart.

This paper is like a mechanic taking a complex engine apart to show that the "spark plugs" (Function Extensionality) and the "fuel pump" (Univalence) are actually separate parts. You can have a car that runs on the fuel pump without the spark plugs working the way we usually expect.

Key Takeaways from the Paper:

Univalence does not force Function Extensionality. You can have one without the other.
The "Package Deal" is broken. The authors showed that a weaker version of Univalence (called Categorical Univalence) is consistent with a world where Function Extensionality is false.
The Tool: They used a specific mathematical construction (the Polynomial Model) to prove this. This model acts like a filter that keeps the "Perfect Match" rule but scrubs out the "Same Recipe" rule.

What They Did Not Do

The paper is purely theoretical. It does not:

Apply this to computer software or AI.
Suggest how this changes how we write code today.
Claim that one version of the rule is "better" than the other for practical use.

It simply answers a deep philosophical question in mathematics: "Are these two rules inseparable?" The answer is No. They are distinct, and you can build a world where one exists without the other.

1. Problem Statement

The paper addresses a foundational question in Homotopy Type Theory (HoTT) regarding the logical relationship between Univalence (UA) and Function Extensionality (FE).

Background: It is a standard theorem (due to Voevodsky) that in any univalent universe, function extensionality holds. That is, if two functions are homotopic ( $f \sim g$ ), they are equal ( $f = g$ ).
The Question: Does the converse hold? Specifically, does a weaker form of univalence, which asserts that the universe forms a "univalent wild category" (where equality of types corresponds to the existence of strict inverses, i.e., categorical equivalences), imply function extensionality?
Context: François G. Dorais proposed a weakening called Categorical Univalence (CUA), where the map from type equality to categorical equivalence (maps with strict left and right inverses) is an equivalence. The authors investigate whether CUA implies FE.

2. Methodology

The authors employ Von Glehn's polynomial model construction ( $Poly(\mathcal{C})$ ) to construct a counterexample. This method is a known source of models for Martin-Löf Type Theory (ITT) that refute function extensionality.

Base Model ( $\mathcal{C}$ ): They start with a model $\mathcal{C}$ of ITT that satisfies Univalence and Function Extensionality (e.g., a cubical model) and possesses extensive finite coproducts satisfying strict $\eta$ -rules.
Polynomial Model Construction: They construct the polynomial model $Poly(\mathcal{C})$ $P o l y (C)$ . In this model:
- Types are pairs $(S, P)$ representing "shapes" and "positions."
- The construction is related to Gödel's Dialectica interpretation and the category of containers.
- Crucially, it is known that $Poly(\mathcal{C})$ always refutes FE.
Analysis of Isomorphisms: The core technical work involves analyzing the structure of isomorphisms (categorical equivalences) within the polynomial model. The authors decompose the type of isomorphisms between two types in the polynomial model into:
1. Isomorphisms between their "shape" components (in the base model $\mathcal{C}$ ).
2. Isomorphisms between their "position" components, conditioned on the shape isomorphism.

3. Key Definitions and Concepts

Wild Category: A structure capturing the $(\infty, 1)$ -categorical nature of types, where composition and identities satisfy coherence laws up to equality (not necessarily homotopy).
Categorical Equivalence ( $A \sim= B$ ): A map $f: A \to B$ equipped with strict left and right inverses ($sf = id, fs = id$). This differs from a homotopy equivalence ( $A \simeq B$ ), where inverses exist only up to homotopy.
Categorical Univalence (CUA): The principle that the map $(A = B) \to (A \sim= B)$ is an equivalence.
Familial Categorical Univalence (CUA $^\bullet$ ): A stronger variant asserting that for any index type $I$ , the category of $I$ -indexed families is univalent in the categorical sense.
Decomposition of Univalence: The paper establishes that standard Univalence (UA) is logically equivalent to the conjunction of Categorical Univalence (CUA) and Function Extensionality (FE).
$UA \iff (CUA \land FE)$

4. Key Contributions and Results

A. Independence of CUA and FE

The primary result is the proof that Familial Categorical Univalence does not imply Function Extensionality.

Theorem: $ITT + CUA^\bullet_U \nvdash FE_U$ .
Proof Strategy:
1. Take a base model $\mathcal{C}$ satisfying $UA + FE$.
2. Construct $Poly(\mathcal{C})$ .
3. Preservation of CUA: The authors prove (Theorem 4.17) that if the base model $\mathcal{C}$ satisfies Familial Categorical Univalence, then the polynomial model $Poly(\mathcal{C})$ also satisfies it. This relies on the fact that isomorphisms in the polynomial model are determined by isomorphisms in the base model (shapes) and specific conditions on positions that are contractible when the base model is univalent.
4. Refutation of FE: It is a known property of polynomial models (Proposition 5.3) that they refute Function Extensionality.
5. Conclusion: $Poly(\mathcal{C})$ is a model of $ITT + CUA^\bullet_U + \neg FE_U$ .

B. Hierarchy of Univalence Variants

The paper explores the landscape of weakened univalence axioms, showing they are not all equivalent:

CUA vs. CUA $^\bullet$ : The authors show that CUA (for a single universe) does not imply Familial Categorical Univalence (CUA $^\bullet$ ). They construct a slice model where CUA holds but CUA $^\bullet$ fails.
Categorical Categorical Univalence (CCUA): They define a variant where the map $(A=B) \to (A \sim= B)$ is a categorical equivalence rather than a homotopy equivalence. They show this is strictly stronger than CUA but still does not imply FE.
Approximate Univalence: They discuss Van den Berg's "approximate univalence" (existence of a path for every equivalence) and note that its relationship to FE remains an open question, though polynomial models refute a related "approximate equivalence improvement."

5. Significance

Decoupling Axioms: The paper demonstrates that the "univalence" property of a universe can be separated from the "function extensionality" property. This challenges the intuition that univalence is a monolithic axiom that forces all extensionality principles.
Structural Insight: By showing that Univalence factors into Categorical Univalence and Function Extensionality, the authors provide a clearer structural understanding of what makes the univalence axiom "tick." It suggests that functions are "privileged" in the standard statement of univalence specifically because of the interaction with FE.
Model Theory: The work validates the polynomial model construction as a powerful tool for separating subtle axioms in type theory, extending its utility beyond just refuting FE to analyzing the internal structure of univalence.
Foundational Implications: For constructivists and foundational researchers, this suggests that one can adopt a form of univalence (categorical univalence) that preserves the structural equivalence of types without committing to the stronger, historically difficult-to-integrate principle of function extensionality.

In summary, the paper resolves Dorais' question in the negative: Categorical Univalence is strictly weaker than full Univalence and does not imply Function Extensionality.