TLDR: A new research paper extends Dependent Typed Higher-Order Logic (DHOL) with refinement and quotient types, making it more expressive for AI applications while maintaining automated theorem proving support through a sound translation to Higher-Order Logic (HOL).
The paper “Subtyping in DHOL – Extended preprint” introduces significant advancements in Dependent Typed Higher-Order Logic (DHOL), a powerful framework that balances expressiveness with automated reasoning capabilities. DHOL is a variant of Higher-Order Logic (HOL) that incorporates dependent types, allowing types to depend on values. This feature greatly enhances its expressiveness compared to standard HOL, even though it makes the type system undecidable. However, DHOL maintains strong support for automated theorem proving by translating its logic into HOL.
This research specifically focuses on extending DHOL with two crucial type constructs: refinement types and quotient types. These types are highly sought after by practitioners but are rarely supported by automated theorem provers because they inherently require undecidable typing, making them difficult to integrate into systems with decidable type systems. The existing design of DHOL, which already handles undecidable typing, provides an elegant and straightforward path for adding these features.
Refinement types allow you to define a “subtype” of an existing type by adding a condition or predicate that elements of the subtype must satisfy. For example, you could define a type for “lists of a specific length” as a refinement of the general “list” type. The paper highlights that their approach to refinement types avoids costly changes in how data is represented, meaning the conversion from a refined type to its original type is a simple, identity operation.
Quotient types, on the other hand, allow you to group elements of a type based on an equivalence relation, effectively treating equivalent elements as the same. A classic example is defining “sets” from “lists” where lists containing the same elements (regardless of order or duplicates) are considered equivalent. Similar to refinement types, this work ensures that the projection from the original type to its quotient type also avoids representation changes, aligning with mathematical practice where elements of a type are often directly used as elements of its quotient.
The core idea behind integrating these new types is through “subtyping,” where one type is considered a subtype of another if all terms of the first type can also be considered terms of the second. This extensional subtyping approach is crucial for combining rich typed representations with efficient reasoning.
A major achievement of this research is the development of a sound and complete translation of the extended DHOL into HOL. This translation is vital because it allows existing, highly optimized automated theorem provers for HOL to be used for DHOL, making practical tool support for this more expressive logic a reality. The paper details how this translation works, including how it handles the new refinement and quotient types.
The practical implications of this work are demonstrated through its application to typed set theory. The extensions enable a novel and elegant formalization of set theory, where routine set constructions can be directly lifted to their typed counterparts. This means that a significant portion of the proving workload in typed set theory can be offloaded to the type-checking process, making theorem proving much more efficient.
Also Read:
- Bridging the Understanding Gap: How Structured Context Boosts AI Reasoning in Theorem Proving
- Unlocking AI’s Black Box: A New Mathematical Framework for Understanding Supervised Learning
In conclusion, this paper significantly enhances DHOL by integrating refinement and quotient types, which are challenging to implement in logics with decidable type systems. By leveraging DHOL’s existing design, the authors provide a practical and elegant solution that maintains strong automated theorem proving support through a sound and complete translation to HOL. This work pushes the boundaries of what can be achieved in automated theorem proving for expressive logical systems. You can read the full paper here.
