Abstract
This paper addresses the challenge of automated reasoning in Higher Order Logic (HOL) by proposing a formal framework for translating HOL theorems into First Order Logic (FOL). By utilizing sorted logic, an "Apply" predicate, and quasi-homomorphisms, the author establishes a method that is sound and complete with respect to Henkin semantics. The approach is validated through a successful automated proof of Cantor's Theorem using the Markgraf Karl Refutation Procedure.
Introduction
In automated reasoning, a significant trade-off exists between the expressive power of a logic and the efficiency of its theorem provers. First Order Logic (FOL) is highly efficient, supported by optimized provers like the Markgraf Karl Refutation Procedure (MKRP). However, FOL lacks the ability to quantify over functions or predicates, making it difficult to express complex mathematical concepts naturally. Higher Order Logic (HOL) is the standard language for mathematics but historically suffers from less efficient automated reasoning tools. This paper explores whether HOL theorems can be "compiled" into FOL to leverage existing high-performance provers.
Methodology: Translating HOL to FOL
The author defines a systematic mapping of HOL constructs into a "sorted" First Order Logic—a variant of FOL that incorporates categories or types. This translation relies on several key technical innovations:
The "Apply" Predicate
To represent higher-order function applications such as $P(x)$ within the constraints of FOL, the framework introduces a special predicate. This effectively translates a function application into a term like $apply(P, x)$, allowing predicates and functions to be treated as objects that can be manipulated by the prover.
Logic Morphisms and Soundness
The translation is formalized through "quasi-homomorphisms," which map the structures of HOL to FOL. Kerber proves that if this mapping is injective, the translation is sound: any proof found by the FOL prover corresponds to a true statement in the original HOL context.
Completeness and Extensionality
To ensure completeness—the guarantee that a true HOL statement will have a corresponding FOL proof—the author incorporates specific axioms. The most notable is the Extensionality Axiom, which asserts that two functions are identical if they produce the same output for all possible inputs.
Results and Evaluation
The proposed framework was evaluated using Cantor’s Theorem, a fundamental result in set theory stating that the power set of a set has a strictly greater cardinality than the set itself. This theorem is inherently higher-order as it involves quantifying over sets of sets.
Using the $\Theta_n$ translation function, the author successfully generated a proof of Cantor's Theorem using the MKRP theorem prover. This demonstration confirmed that complex higher-order mathematics can be automated using first-order tools, provided the translation is handled with appropriate axioms. Figure 1 illustrates the concrete syntax of the axioms and theorems as they appear in the sorted logic during such a proof.
Key Insights
- Soundness vs. Completeness Trade-off: While completeness is theoretically desirable, adding all necessary axioms (like comprehension axioms) can lead to a "search space explosion," making the prover inefficient. In many practical cases, a sound but incomplete translation is more effective.
- Henkin Semantics: The translation targets Henkin's general model semantics. While standard HOL is incomplete due to Gödel's theorems, HOL under Henkin semantics can be fully captured by FOL, providing a solid theoretical foundation for this approach.
Conclusion and Future Work
The paper successfully bridges the gap between the expressivity of HOL and the power of FOL provers. Future work involves extending these methods to even more complex type systems, such as Higher Order Sorted Logic, which would require the target FOL to support more sophisticated sort structures.
Reference: Kerber, M. (1991). How to Prove Higher Order Theorems in First Order Logic. Fachbereich Informatik, Universität Kaiserslautern.
Summary updated