HOL in HOL over a set-theoretic universe: consistency of NK with infinity and choice

Christoph Benzmüller 📧 and Daniel Kirchner 📧

September 10, 2026

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

This companion to the entry A deep embedding of HOL in HOL certifies the natural-deduction calculus NK of that entry consistent with a Dedekind-style axiom of infinity — an injective, non-surjective self-map of the individuals — and, because its standard model has full function spaces, with the relational axiom of choice as well. Such an axiom has no finite models, so the compactness argument of the main entry — which certifies the first-order sentences "there are at least n individuals" by arbitrarily large finite models — does not apply: an infinite model is required. We construct one over Paulson's ZFC_in_HOL: the individuals are interpreted as the finite ordinals ω, with full function spaces at every type, yielding a standard Σ-model of NK over the set-theoretic universe V. As this meta-theory is stronger and non-conservative, the guarantee is relative consistency at ZF strength; the machine-checked formalisation lives in Isabelle/HOL with Paulson's ZFC_in_HOL (the ZF reading is metatheoretic, made precise in the introduction). Because NK already provides extensionality and typed description (after Andrews), this certifies the consistency of full classical higher-order logic in Church's sense, choice included as a separate relational scheme.

The plain-HOL results — soundness, Henkin completeness, and finite-model consistency, including the compactness route to the first-order sentences of infinity — are proved in the main entry and imported here unchanged. What the present entry adds is completeness and model existence for the extension by infinity, still in plain HOL, and the set-theoretic route to its consistency, which this development obtains only there.

This contribution is part of the LogiKEy project.

License

BSD License

Note

Parts of this formalisation and its documentation were drafted interactively with a generative AI assistant (Anthropic's Claude), used under continuous human direction. All proofs are machine-checked by Isabelle; the entire development, including all comments and references, was subsequently reviewed, revised and simplified by the authors, who take full responsibility for its content.

History

November 8, 2026
Model existence for DInf from its consistency as an explicit hypothesis, non-smallness of the carrier; prose revised.

Topics

Related publications

  • Benzmüller, C., Brown, C. E., & Kohlhase, M. (2004). Higher-order semantics and extensionality. Journal of Symbolic Logic, 69(4), 1027–1088. https://doi.org/10.2178/jsl/1102022211
  • https://isa-afp.org/entries/HOL_in_HOL_Deep.html

Session HOL_in_HOL_Deep_Infinity_ZFC