Henkin semantics for reasoning with natural language

Michael Hahn, Frank Richter

Abstract

This paper addresses the computational "logic gap" between expressive linguistic theories and practical automated reasoning. By translating higher-order logic (Type Theory) into first-order logic (FOL) via Henkin semantics, the authors provide a framework that preserves the nuances of human language—such as intensionality and generalized quantifiers—while leveraging the efficiency of standard first-order theorem provers. Experimental results demonstrate that this approach achieves high accuracy and computational speed on natural language inference tasks, suggesting a viable path for integrating formal semantics into scalable NLP systems.

Introduction

In formal semantics, researchers face a persistent trade-off between expressivity and tractability. Theoretically-oriented linguists typically employ higher-order logics, such as two-sorted Type Theory (Ty2), to capture complex linguistic phenomena like modality ("John believes..."), adjectives, and generalized quantifiers ("Most students..."). However, higher-order logic is notoriously difficult for automated reasoning; it is generally undecidable and lacks complete proof systems.

Conversely, computational linguistics relies heavily on first-order logic (FOL) because of its mature ecosystem of optimized theorem provers and model builders. The limitation is that many natural language features cannot be natively expressed in FOL without losing significant detail. This paper proposes a systematic bridge: using Henkin semantics to translate higher-order linguistic representations into a format that FOL tools can process effectively.

Methodology: Bridging the Logic Gap

The core of the proposed method is a translation from Ty2 into FOL, facilitated by the adoption of Henkin semantics.

Henkin Semantics

In standard higher-order semantics, the domain of functions must include every possible mapping between sets, which leads to the loss of completeness. Henkin semantics relaxes this requirement, only requiring that the model contains enough functions to interpret the specific terms present in the language. This shift allows higher-order logic to behave more like FOL, enabling the use of complete proof systems without sacrificing the structural richness of the original linguistic theory.

Translation and Axiomatization

The authors developed a formal translation function ($T$) to map Ty2 types, terms, and formulas into FOL equivalents. To manage the reasoning process, they explored two distinct axiomatization strategies:

  1. Strong Axiomatization: This provides the full theoretical power of Henkin semantics but risks overwhelming theorem provers with an excessive number of axioms.
  2. Weak Axiomatization: A leaner, more targeted set of axioms based on the specific terms appearing in a given problem. This version is designed to improve performance by narrowing the search space.

Additionally, the authors utilized "Meaning Postulates" to encode specific linguistic knowledge (e.g., the fact that "knowing $p$" implies $p$ is true) as axioms in Ty2, which are then translated into FOL alongside the target sentences.

Experimental Setup

The approach was evaluated using a custom test suite of 117 natural language inference (NLI) problems. This suite was designed to test semantic competence across several categories:

  • Composition: Modality, knowledge/belief, generalized quantifiers, and adjectives.
  • Benchmarks: 29 items were adapted from the FraCaS test suite, a standard benchmark for semantic reasoning.
  • Task: Each item consists of premises and a conjecture, with the system tasked to label the relationship as valid, contradictory, or contingent.

The reasoning pipeline utilized standard FOL tools, including theorem provers (Spass, Prover9, and E) and the model builder Mace4.

Key Results and Insights

The experimental results highlight the efficiency of the Henkin-based approach:

  • Overall Performance: The system correctly identified the logical status of 75.2% of the test items.
  • The Advantage of Weak Axiomatization: The "weak" translation strategy significantly outperformed the "strong" version on valid and contradictory items, achieving an 87.7% success rate compared to 50.8%. This confirms that managing axiom density is critical for practical automated reasoning.
  • Computational Efficiency: The system proved to be remarkably fast. 94.5% of successful proofs using the weak translation were completed in under 5 seconds, with nearly half taking less than 0.1 seconds.
  • Handling Complex Quantifiers: One of the most significant findings was the system's ability to handle quantifiers like "most." While "most" is mathematically undefinable in standard FOL, the use of Henkin semantics allowed the provers to correctly resolve inferences such as "Most women sing and dance ⊢ Most women dance."

Discussion and Future Work

While the results are promising, the study identified several areas for further development. Generalized quantifiers like "most" and "few" remain the most challenging category for the system. Furthermore, the current evaluation relies on a controlled grammar; future work aims to integrate this translation framework into wide-coverage semantic parsers like Boxer to handle real-world, unconstrained text.

There is also a noted trade-off regarding soundness. The "weak" translation is technically unsound relative to the full Henkin semantics. Although this did not result in errors within the current test suite, a more formal characterization of the conditions under which this weakness might lead to incorrect inferences is necessary. Finally, improving the human-readability of the models generated by Mace4 would assist linguists in debugging and refining their theories.

Conclusion

By applying Henkin semantics to the problem of natural language inference, this research demonstrates that the gap between expressive linguistic theory and computational efficiency can be bridged. The ability to use standard FOL tools to reason over higher-order structures opens new possibilities for deep semantic processing in NLP.

Summary updated

Abstract

The frequency of intensional and non-first-order definable operators in natural languages constitutes a challenge for automated reasoning with the kind of logical translations that are deemed adequate by formal semanticists. Whereas linguists employ expressive higher-order logics in their theories of meaning, the most successful logical reasoning strategies with natural language to date rely on sophisticated first-order theorem provers and model builders. In order to bridge the fundamental mathematical gap between linguistic theory and computational practice, we present a general translation from a higher-order logic frequently employed in the linguistics literature, two-sorted Type Theory, to first-order logic under Henkin semantics. We investigate alternative formulations of the translation, discuss their properties, and evaluate the availability of linguistically relevant inferences with standard theorem provers in a test suite of inference problems stated in English. The results of the experiment indicate that translation from higher-order logic to first-order logic under Henkin semantics is a promising strategy for automated reasoning with natural languages.The paper is accompanied by the source code (cf. SUPP. FILES) of the grammar and reasoning architecture described in the paper.
BibTeX
@article{hahn2015henkin,
  author = {Michael Hahn and Frank Richter},
  title = {{Henkin semantics for reasoning with natural language}},
  journal = {J. Lang. Model.},
  year = {2015},
  doi = {10.15398/jlm.v3i2.113},
}
Figure