Non-Derivability Results in Polymorphic Dependent Type Theory

This paper establishes that in pure polymorphic dependent type theory ($\lambda$P2), parametric quotient types and strong coinduction principles are not definable, and that function extensionality is strictly necessary to prove induction principles, by constructing specific models where these principles fail.

The Gist

Here is an explanation of the paper "Non-Derivability Results in Polymorphic Dependent Type Theory" by Herman Geuvers, translated into simple language with creative analogies.

The Big Picture: Building a Perfect Lego Castle

Imagine you are an architect trying to build a perfect Lego castle using a specific, very strict set of rules (a "Type Theory" called $\lambda P2$).

In this world, you can build amazing things:

• Data Types: You can build a "Natural Number" block or a "List" block.
• Functions: You can write instructions on how to use these blocks.
• Logic: You can write rules to prove things about your blocks (e.g., "This tower is stable").

The paper asks a very specific question: Can we build a "Perfect Castle" where the rules for how these blocks behave are automatically proven to be true just by the way we built them?

Specifically, the author is looking at two big problems:

1. Induction: The rule that says, "If I can build the first step, and I can build any step from the one before it, then I can build the whole infinite staircase."
2. Co-induction & Quotients: Rules for infinite streams (like a never-ending video feed) and rules for merging different blocks together (quotients).

The author's conclusion is: No, you cannot do this with the basic rules alone. You need to add extra "magic tools" (extensions) to make it work.

---

The Problem: The "Smart" Encoding Trap

In the world of $\lambda P2$, you can try to be "smart" and encode a number (like 5) not as a raw number, but as a complex instruction: "I am the thing that does this action 5 times."

This works great for simple math. But when you try to prove the Induction Principle (the rule that lets you do math on all numbers), the system fails. It's like trying to prove a bridge is safe just by looking at the blueprints, but the blueprints don't actually contain the physics of gravity. The system knows how to make the number, but it doesn't know how to reason about the whole sequence of numbers.

The Author's Discovery:
Even if you try every "smart" trick to redefine what a number is, the system cannot prove the induction principle. It's a fundamental limitation of the basic rules.

---

The Counter-Models: The "Hall of Mirrors"

How does the author prove this? He doesn't just say "it's hard." He builds a Counter-Model.

Imagine a "Hall of Mirrors" (a mathematical model) where the rules of the universe are slightly twisted.

• In our normal world, if two things look the same and act the same, they are the same.
• In this "Hall of Mirrors," you can have two things that look identical and act identical, but the mirror tells you they are different.

By building these specific "Hall of Mirrors" universes, the author shows:

1. For Streams (Infinite Videos): You can build a stream type, but you cannot prove that two streams are the same just because they produce the same output forever. In the mirror world, they are different objects.
2. For Quotients (Merging): You cannot create a rule that says "If two things are related, treat them as one." In the mirror world, the system refuses to merge them, even if you tell it to.

These "mirror worlds" act as proof that the basic rules of $\lambda P2$ are too weak to force these principles to work.

---

The Solution: What Tools Do We Need?

Since the basic rules fail, the paper looks at what happens when we add "Magic Tools" (Extensions) to our Lego set. Researchers had previously suggested adding four tools to fix the induction problem:

1. Identity Types: A way to say "A is the same as B."
2. UIP (Uniqueness of Identity Proofs): A rule saying "There is only one way to prove A is B."
3. $\Sigma$-Types: A way to bundle two things together tightly.
4. FunExt (Function Extensionality): A rule saying "If two functions give the same answer for every input, they are the same function."

The Big Surprise:
The author tests these tools one by one. He builds a new "Hall of Mirrors" where he has Identity Types, UIP, and $\Sigma$-types, but NO Function Extensionality.

In this world:

• The system is very powerful.
• It has all the fancy tools.
• BUT, it still cannot prove the induction principle for natural numbers.

The Verdict:
Function Extensionality (FunExt) is the missing key. Without it, the system is like a car with a great engine, a perfect steering wheel, and a GPS, but no wheels. It can't move. You must have the rule that "same behavior = same function" to make induction work.

---

Summary of the "Story"

1. The Goal: We want a logical system where we can define data (like numbers) and automatically prove that they behave correctly (Induction).
2. The Failure: In the basic system ($\lambda P2$), this is impossible. No matter how cleverly you define "numbers," the system can't prove the induction rule.
3. The Proof: The author builds "twisted universes" (counter-models) where the rules hold, but the induction principle fails. This proves the principle isn't hidden inside the basic rules.
4. The Fix: We need to add extra rules to the system.
5. The Crucial Ingredient: Among the proposed fixes, Function Extensionality is the most important. Without it, even with all other fancy tools, you still can't prove induction.

Why Should You Care?

This paper is like a mechanic telling you: "You can't drive this car without a transmission." It saves other researchers from wasting time trying to build induction into a system that fundamentally lacks the gears to make it happen. It tells us exactly which "gears" (like Function Extensionality) we need to add to make our logical systems powerful enough to handle real-world mathematics.

Technical Summary

Here is a detailed technical summary of the paper "Non-Derivability Results in Polymorphic Dependent Type Theory" by Herman Geuvers.

1. Problem Statement

The paper addresses fundamental limitations in $\lambda P2$ (second-order dependent type theory), a subsystem of the Calculus of Constructions (CC). While $\lambda P2$ allows for the impredicative encoding of inductive data types (like natural numbers, lists, and streams) and supports higher-order logic, it lacks the ability to prove essential reasoning principles for these types.

Specifically, the paper investigates the following open questions regarding the necessity of specific extensions to $\lambda P2$ to derive:

1. Induction Principles: Can the induction principle for natural numbers (or other inductive types) be proven in pure $\lambda P2$?
2. Coinduction Principles: Can the coinduction principle (specifically, that the definable stream type is a terminal co-algebra) be proven in pure $\lambda P2$?
3. Quotient Types: Can parametric quotient types (where the quotient operation is polymorphic) be defined in $\lambda P2$?
4. Necessity of Extensions: Recent work (e.g., Awodey, Frey, Speight [1]) showed that adding Identity Types, Uniqueness of Identity Proofs (UIP), Function Extensionality (FunExt), and $\Sigma$-types allows for these principles. The paper asks: Which of these extensions are strictly necessary? Is FunExt required? Are $\Sigma$-types required?

2. Methodology

The author employs syntactic analysis and the construction of counter-models to prove non-derivability.

• Model Framework: The paper utilizes Polyset Models based on Weakly Extensional Combinatory Algebras (WECA).
  • Unlike standard parametric models (where types are interpreted as sets of realizers satisfying parametricity), these models are based on untyped $\lambda$-calculus terms (modulo $\beta$ or $\beta\eta$ equality).
  • The models are "non-parametric," meaning they allow for terms that behave differently depending on the specific type instantiation, breaking the parametricity that usually forces induction/coinduction to hold in standard models.
• Counter-Model Construction: To prove a principle is not derivable, the author constructs a specific model where:
  1. The type theory rules are sound (the model is a valid interpretation of $\lambda P2$).
  2. The specific principle in question (e.g., the existence of a term of the induction type) is false (the type is empty or the required term does not exist in the model).
• Extension Analysis: The methodology is extended to models incorporating Identity Types and $\Sigma$-types to test the necessity of FunExt.

3. Key Contributions and Results

A. Non-Derivability of Coinduction for Streams

• Context: Streams are definable in $\lambda P2$ as existential types (e.g., $\exists \alpha. \alpha \times (\alpha \to \sigma) \times (\alpha \to \alpha)$).
• Result: The definable stream type is not a terminal co-algebra.
• Proof: The author constructs two streams, $s_1$ and $s_2$, that are bisimilar (they produce the same infinite sequence of observations) but are not equal in the model.
  • In the model based on untyped $\lambda$-terms modulo $\beta\eta$, $s_1$ and $s_2$ reduce to distinct normal forms.
  • Therefore, the type $\Pi s, t : \text{Stream}. s \sim t \to s = t$ is empty.
  • This implies the coinduction principle (uniqueness of the corecursor) fails.

B. Non-Derivability of Parametric Quotient Types

• Context: A parametric quotient type $\sigma/R$ requires a polymorphic class function $cls$ and a recursor $rec_q$ that respects the relation $R$.
• Result: Parametric quotient types (as defined in Definition 2.7) are not definable in $\lambda P2$.
• Proof: The author shows that in a model based on the WECA of untyped $\lambda$-terms, any term $cls$ satisfying the quotient properties must act as a constant function due to the nature of the model.
  • However, for a quotient to be useful, $cls$ must distinguish elements (e.g., $cls(\text{true}) \neq cls(\text{false})$ if the relation doesn't equate them).
  • The contradiction between the required non-constant behavior and the model's forcing of constant behavior proves non-derivability.

C. Necessity of Function Extensionality (FunExt)

• Context: Previous work established that adding Identity Types, UIP, and $\Sigma$-types allows for induction. The question remained: Is Function Extensionality (FunExt) strictly necessary?
• Result: Yes. Even with Identity Types, UIP, and $\Sigma$-types, induction for natural numbers is not provable without FunExt.
• Proof:
  • The author constructs a model based on $\Lambda_{id}$ (untyped $\lambda$-calculus extended with constants for Identity Types and $\Sigma$-projections).
  • In this model:
    • UIP holds: All proofs of equality are equal to refl.
    • $\Sigma$-types and Identity Types are sound.
    • FunExt fails: There exist functions $f, g$ such that $\forall x. f x = g x$ but $f \neq g$.
    • Induction fails: The type for the induction principle of natural numbers is empty.
  • This demonstrates that FunExt is the critical missing ingredient that enables the proof of induction in the extensions studied in [1].

4. Significance

1. Clarification of Type Theory Extensions: The paper provides a precise boundary for what can and cannot be achieved in polymorphic dependent type theory. It confirms that "smart" encodings of data types in pure $\lambda P2$ are insufficient for reasoning principles like induction and coinduction.
2. Role of Function Extensionality: The most significant finding is the isolation of Function Extensionality as the crucial axiom required to make induction provable for inductive types (like natural numbers) when combined with Identity Types and $\Sigma$-types. Without FunExt, even with UIP, the system remains too weak to support standard inductive reasoning.
3. Limitations of Impredicativity: The results reinforce that while impredicative encodings (Church encodings) are powerful for defining data, they lack the structural strength to support internal reasoning principles (like the initial algebra property) without additional axioms.
4. Methodological Contribution: The use of syntactic, non-parametric models based on WECA provides a robust tool for proving negative results in type theory, offering an alternative to realizability or PER models which often validate these principles by default.

Conclusion

Herman Geuvers concludes that to define data types with proper induction and coinduction principles (such as initial algebras and terminal co-algebras), one cannot rely solely on the pure Calculus of Constructions or $\lambda P2$. One must extend the system. Specifically, while Identity Types, UIP, and $\Sigma$-types are necessary, Function Extensionality is the decisive factor that enables the derivation of the induction principle. Without it, even the most sophisticated encodings of natural numbers fail to satisfy the induction principle.