betaFeedback

WorksMathematics

HOL in HOL: mechanized soundness, completeness and consistency, with and without infinity

Abstract

What can a logic certify about a copy of itself? For Church's simple theory of types, formalized as a deep embedding in Isabelle/HOL with Henkin semantics and a natural-deduction calculus, the answer has two tiers. On the first tier, plain Isabelle/HOL certifies the logic without an axiom of infinity, by a standard model with one individual. On the second tier, the logic with a Dedekind-style axiom of infinity is certified only in Isabelle/HOL extended by a large enough set-theoretic universe. Both tiers appear in Harrison's self-verification of HOL Light. What the present formalization adds is Henkin completeness, and with it a semantics that matches the calculus exactly, compactness and model existence on the first tier, and the boundary between the tiers. Comparing two ways of adding infinity to the object logic shows where the boundary lies. One is an infinite domain of individuals, expressed by the first-order sentences "there are at least nn individuals", each of which has a finite model; the other is the Dedekind axiom, a single sentence with no finite model, and there the first tier ends. In the calculus the axiom is strictly stronger than the sentences together: it derives each of them, but they do not derive it. The witness is a countable Henkin model in which every sentence holds and the axiom fails, because its function domain is too sparse for an injective, non-surjective self-map. On the second tier, the universe serves one purpose only: to prove the Dedekind axiom consistent. Everything that follows, completeness and even the countable Henkin model of the axiom, is obtained in plain Isabelle/HOL. The universe axiom is Harrison-style, realized in Paulson's ZFC_in_HOL with the domain of every type in Vω+ωV_{ω+ω}; with it, full classical higher-order logic with infinity and relational choice is consistent relative to set theory.

Introduction

A theory that interprets arithmetic cannot prove its own consistency; this is Gödel’s second incompleteness theorem. Yet proof assistants are routinely trusted with the verification of their own logical cores. Harrison proved the kernel of HOL Light sound and consistent twice: for the kernel without its axiom of infinity inside full HOL Light, and for the kernel with it inside HOL Light extended by one axiom postulating a large universe [19]. Kumar, Arthan, Myreen and Owens, and later the Candle project, extended the soundness result to HOL’s definitional mechanisms, with the set-theoretic universe as an explicit assumption of the soundness theorem rather than an axiom [25, 1]. Between Gödel’s limit and these results lies a question that this paper answers by machine-checked theorems, for Church’s simple theory of types [14]: what exactly can a copy of the logic certify about the logic, and at what point does the certifying side have to become stronger than the certified one? Harrison’s two results fix the two tiers of the answer for standard semantics and soundness. This paper transfers his division to a deep embedding with Henkin semantics, where a completeness theorem is available, and completeness has three consequences here. First, the calculus acquires a semantics that matches it exactly: NK proves exactly what holds in all Henkin models, so every statement about derivability below is also a statement about all Henkin models. Second, compactness and model existence belong to the first tier: both are theorems of plain Isabelle/HOL, and even the countable Henkin model of the Dedekind axiom of infinity is built there, from its consistency alone. Third, both sides of the boundary become visible: finite models show where the first tier ends, and the Henkin model built by the completeness proof shows that the two familiar ways of adding infinity, an infinite domain of individuals and a Dedekind-style axiom, differ there.

The setting is a deep embedding: Church’s type theory, the logic underlying Isabelle/HOL [29], HOL4 [39], HOL Light [20] and the automated provers of the TPTP library’s higher-order format THF [40, 8], is the object logic, formalized as mathematical data inside Isabelle/HOL, the meta-logic. Its syntax is represented by a datatype, and the Henkin-style semantics [22, 5] and the natural-deduction calculus NK of Benzmüller, Brown and Kohlhase (BKK) [5] are defined over that datatype; object and meta-logic are kept strictly apart. What is formalized is the monomorphic core common to these systems: primitive equality and typed description, no polymorphism, no choice operator, and no axiom of infinity unless one is added explicitly. The calculus is proved sound and Henkin-complete (§ 2) and consistent (§ 3). The two tiers are distinguished by the meta-theory required. A statement is on the first tier if plain Isabelle/HOL proves it, be it a consistency, completeness or model existence statement, and on the second tier if it is proved only with a large enough set-theoretic universe as an additional type (§ 7 and § 8).

Tier one: consistency without infinity

Without an object-level axiom of infinity, NK is consistent by a standard model with finite domains: a single individual suffices, the signature may be finite, and the model is defined without a choice operator (§ 3). No set theory is involved, and Gödel’s second incompleteness theorem does not apply, since the object logic interprets no arithmetic; the meta-level infinity of Isabelle/HOL enters only through the syntax and the datatype inside which the finite models are built (§ 3). For many uses of higher-order logic that assume no object-level axiom of infinity, as in the LogiKEy methodology of semantic embeddings [9], this first tier already certifies the logic in use.

Tier two: consistency with infinity

A Dedekind-style axiom of infinity DInf (some self-map of the individuals is injective but not surjective) has no finite models, so the first tier cannot certify its consistency. § 4 argues that plain Isabelle/HOL cannot prove the extension by infinity and choice consistent. The two ways it offers fail: a standard model needs a carrier type of cardinality at least ℵω\aleph_\omega, and plain Isabelle/HOL proves no type that large; a Henkin model is built by the completeness proof only from the very consistency to be shown. By Gödel’s second incompleteness theorem no other way succeeds, since NK with infinity and choice interprets the monomorphic core of the meta-logic (this is a classical argument, not formalized here). So the meta-theory has to be strengthened, and the strengthening we need is small: a Harrison-style universe axiom, formalized as the locale harrison_universe. From it we construct an abstract universe interface, the locale hol_universe, and we realize both in the set-theoretic universe VV of Paulson’s ZFC_in_HOL [32]. The result is a machine-checked consistency theorem for full classical higher-order logic in Church’s sense, extensionality, typed description, the Dedekind axiom and a relational axiom of choice, relative to set theory (§ 7 and § 8; the construction chain is Figure 1(b)). Choice adds no further requirement: the relational choice scheme holds in every standard model, whose full function spaces contain the choice function that the meta-logic’s own choice provides (§ 7.1). A rank analysis shows the domain of every type in the concrete model to be an element of Vω+ωV_{\omega+\omega}, that is, to lie within finitely many power-set steps above the natural numbers (§ 9). This is the part of the set-theoretic universe that Zermelo set theory, ZF without replacement, already provides; that the construction needs no replacement is an interpretation of the rank bound, not a formalized reduction to Zermelo set theory.

The two senses of infinity and the construction chain behind the tier-two consistency theorem

Figure 1. (a) The two senses of infinity of § 5: the first-order sentences ∃≥n\exists_{\ge n} (“at least nn individuals”) and the Dedekind axiom DInf. Arrows denote derivability in NK (Convention 2.1); the lower arrow is a non-derivability result, witnessed by a Henkin model of all the sentences (Theorem 5.5). (b) The construction chain behind the tier-two consistency theorem (Theorems 8.1, 8.2 and 7.2). ACrel\mathrm{AC}^{\mathrm{rel}} is the relational choice scheme of § 7; the boxed nodes are the two interfaces of A2A_2, Isabelle locales, that is, named bundles of parameters and assumptions; the universe VV appears only as one instance of the topmost one.

The boundary, and what stays below it

Where exactly does the first tier end? § 5 compares the two senses of adding infinity of Figure 1(a): infinity as a semantic property of the individual domain, axiomatized by the first-order sentences “there are at least nn individuals”, and infinity as the single syntactic axiom DInf. The sentences are on the first tier: NK is consistent with all of them by compactness over arbitrarily large finite models, without ever constructing an infinite model. DInf derives every one of them, but they do not derive DInf: a Henkin model of all of them refutes it, because a sparse function domain need not contain the witnessing self-map. In Henkin semantics the Dedekind axiom is therefore strictly stronger than an infinite individual domain, while at standard models the two coincide. The first tier holds more than the consistency of the first-order sentences. Completeness of NK with DInf as a hypothesis is a theorem of plain Isabelle/HOL, and so is model existence: every consistent sentence over a countable signature, an axiom of infinity included, has a Henkin model with countable total domain (§ 6). Only the consistency of the extension requires the stronger meta-theory, and nothing else is taken from it: the countable Henkin model of DInf is built in plain Isabelle/HOL from that consistency alone.

Contributions

The contribution of this paper is a precise answer to the opening question: what higher-order logic can certify about a copy of itself, where the boundary between the two tiers runs, and how little has to be added to reach the second tier. Every theorem, proposition and corollary of this paper is a machine-checked theorem, and the machine-checking has made the answer more precise: every hypothesis is explicit, and several of the distinctions below (the two senses of infinity, the per-type rank bound, the exact role of choice) emerged where a plausible stronger claim could not be proved. The theorems are contained in two entries of the Archive of Formal Proofs (AFP): HOL_in_HOL_Deep [6], extended for this paper and called A1A_1 below, and its companion HOL_in_HOL_Deep_Infinity_ZFC [7], called A2A_2. The metatheoretic steps that are not formalized (§ 4, Table 1, Remark 8.4) are marked as such wherever they occur. In detail, we provide:

Henkin models (Mβfb\mathcal{M}_{\beta f b})standard models
completeness of NKholds (Theorem 2.3)fails classically: standard validity is not recursively enumerable (not formalized)
compactnessholds (Corollary 2.4)fails: {∃≥n∣n}∪{¬DInf}\{\exists_{\ge n}\mid n\}\cup\{\neg\mathrm{DInf}\} has no standard model, though every finite part does
DInf versus infinite DιD_{\iota}strictly stronger: DInf forces DιD_{\iota} infinite, yet can fail with DιD_{\iota} infinite (Theorem 5.5, Remark 5.6)equivalent to Dedekind infinitude of DιD_{\iota} (Proposition 5.2)
ACrel\mathrm{AC}^{\mathrm{rel}}not guaranteed: a sparse domain may omit the choice functionholds always (Proposition 7.1)

Table 1. Henkin versus standard semantics for the embedded logic. The entries name the results of this paper. The two failures at standard semantics are classical readings (of Propositions 5.2 and 4.1, and of Gödel’s first incompleteness theorem), not formalized theorems; the compactness failure uses the classical step that an infinite set admits an injective non-surjective self-map, which needs choice and is not formalized. ACrel\mathrm{AC}^{\mathrm{rel}} is the relational choice scheme of § 7.

  1. consistency of NK without infinity, by a finite standard model, with a footprint audit: no object-level infinity, no set theory, no choice operator in the definition of the model, and a possibly finite signature (§ 3);

  2. the plain-HOL results: soundness, Henkin completeness relative to hypotheses at every infinite signature, semantic compactness, and model existence with a countable witness (§ 2 and § 6);

  3. the boundary, measured by two senses of infinity: consistency of the first-order sentences “there are at least nn individuals” by compactness over finite models; their derivability from DInf; non-derivability of DInf from them, with a Henkin countermodel satisfying all of them; and the characterization of satisfaction of DInf in any Henkin model (§ 5);

(4) an abstract universe interface with a carrier-generic consistency theorem for the extension by infinity and choice (§ 7);

(5) a Harrison-style interface from which the universe interface is constructed, and its realization in ZFC_in_HOL, yielding the consistency of full classical HOL in Church’s sense (§ 7 and § 8);

(6) a type-by-type rank bound: every domain of the concrete model is an element of Vω+ωV_{\omega+\omega} (§ 9).

Items (1), (4), (5) refine Harrison’s two tiers; (2), (3), (6) have no counterpart there.

The underlying deep embedding

We recall from A1A_1 [6] what the later sections use; for the full development see the entry itself. The object logic has base types ι\iota (individuals) and oo (truth values) and function types σ⇒τ\sigma\Rightarrow\tau.

The syntax, after BKK [5], is formalized in a locally nameless representation [13]: a bound variable is not a name but a number, counting the binders between its occurrence and the binder that captures it, while a free variable is a named atom; terms that differ only in the names of bound variables are therefore identical. The signature is a set of typed constants (parameters) drawn from a meta-level type pp;1 BKK’s identification of α\alpha-equivalent terms thereby becomes a literal equality. Concretely, a term is a value of the datatype tm, with constructors for bound variables (de Bruijn indices), free variables (a name and a type), parameters (a signature constant and a type), the logical constants ¬\neg, ∨\lor, Πσ\Pi_\sigma, ισ\iota_\sigma and =σ=_{\sigma}, application, and abstraction with an annotated domain type. Well-formedness at a type σ\sigma is an inductive predicate. The binder notation of the displayed formulas, ∀Xσ.A\forall X_{\sigma}. A and ∃Xσ.A\exists X_{\sigma}. A, is defined in the usual way by abstracting a named free variable, so that every displayed formula is literally a value of tm (Remark 2.2). The signature includes primitive equality and, following Andrews [2] and going beyond BKK, typed description operators. The calculus is BKK’s NKβfb\mathrm{NK}_{\beta fb} (their Definition 7.1 and Figures 6, 7 and 9), fifteen rules: hypothesis, β\beta-conversion, introduction and elimination for ¬\neg, ∨\lor and Π\Pi, classical contradiction, functional and Boolean extensionality, two rules for primitive equality, and, after Andrews but at every type, one rule for description. The semantics is rendered abstractly, for the class Mβfb\mathcal{M}_{\beta fb} of Σ\Sigma-Henkin models (“Σ\Sigma” is BKK’s name for the signature, our pp) over an arbitrary value carrier uu, the meta-level type inside which all domains live. A model is a frame of typed domains Dσ\mathcal{D}_\sigma with application, in which every well-formed term denotes and the logical constants behave as expected; standard models are the special case in which every function domain Dσ⇒τ\mathcal{D}_{\sigma\Rightarrow\tau} is the full function space.

The results of this paper are stated with three consequence relations, two syntactic and one semantic, fixed in the following convention.

Convention 2.1. For a set Φ\Phi of object formulas and a formula AA:

  • Φ⊢A\Phi\vdash A denotes derivability in NK from the whole context Φ\Phi (Isabelle: bprov, theory Calculus of A₁);

  • Φ⊩A\Phi\Vdash A denotes the finitary consequence in the style of Andrews: some finite Φ0⊆Φ\Phi_0 \subseteq\Phi satisfies Φ0⊢A\Phi_0 \vdash A (Isabelle: fprov, theory Calculus of A1\mathcal{A}_1);

  • Φ⊩uA\Phi\Vdash_u A denotes semantic consequence over all models of Mβfb\mathcal{M}_{\beta fb} with value carrier uu (Isabelle: bkk_consequence, theory Semantics of A1\mathcal{A}_1).

con Φ abbreviates Φ⊬⊥\Phi\nvdash\bot. Over infinite signatures, ⊩\Vdash and ⊢\vdash provably coincide on finite contexts and on pure contexts, those whose formulas contain no parameters (Isabelle: fprov_eq_bprov, theory Calculus of A1\mathcal{A}_1).

Remark 2.2 (How to read the formal statements). Every displayed object formula is, in the artifact, literally a value of an Isabelle datatype: the type tm of locally nameless terms over the signature type pp (theory Syntax). The axiom DInf of § 4, for instance, is the Isabelle definition DInf, a term of type tm written with the binder notation in the form displayed there. That this term is a closed, well-formed formula is not stipulated, as it would be on paper, but proved (cwff_DInf, theory NK_Infinity). On the semantic side, “AA is satisfied in MM under assignment ξ\xi” means that the denotation of AA under ξ\xi in MM is the distinguished truth value, in the artifact the equation den A ξ = Tv. An assignment is always type-respecting: each variable of type σ\sigma receives a value in DσD_\sigma (asg; both in theory Semantics). Each principal statement below is a natural-language reading of a formal statement in the artifact, with every hypothesis shown, and carries a pointer of the form “(Isabelle: name, theory TT of Ai\mathcal{A}_i)” to it.

The main theorem of A1\mathcal{A}_1 states soundness and completeness under two hypotheses, an infinite signature and a value carrier into which the signature embeds; every later section uses it in this form.

Theorem 2.3 (Soundness and completeness, hypothesis-relative). Let Φ\Phi be any set of well-formed object formulas over an infinite signature pp and AA well-formed, and let the value carrier uu admit an injection p↪up \hookrightarrow u. Then

Φ⊩A⟺Φ⊩uA.\Phi\Vdash A \quad\Longleftrightarrow\quad\Phi\Vdash_u A.

*No purity, finiteness, countability, or closedness condition is required of Φ\Phi or A.∗(Isabelle:‘soundandcompletehyps‘,theory‘MainResults‘ofA.* (Isabelle: `sound_and_complete_hyps`, theory `Main_Results` of\mathcal{A}_1`)

Corollary 2.4 (Semantic compactness). Let Φ\Phi, AA and uu be as in Theorem 2.3. If Φ⊩uA\Phi\Vdash_u A then, for every value carrier vv, some finite Φ0⊆Φ\Phi_0 \subseteq\Phi satisfies Φ0⊩vA\Phi_0 \Vdash_v A. (Isabelle: NK_consequence_compact, theory Main_Results of $\mathcal{A}_1`)

The proof uses no ultraproducts. Completeness turns Φ⊩uA\Phi\Vdash_u A into a derivation of AA from some finite Φ0⊆Φ\Phi_0 \subseteq\Phi, and soundness, which holds over every carrier, turns that derivation into Φ0⊩vA\Phi_0 \Vdash_v A for every vv.2 The same Φ0\Phi_0 thus serves all carriers. The formal corollary cannot say so, because Isabelle/HOL quantifies over types only at the outermost level: vv is a schematic type variable, and no quantifier over it can follow the existential over Φ0\Phi_0. The corollary is therefore one theorem per carrier vv; the uniformity is recorded by the syntactic statement Φ⊩A\Phi\Vdash A of Theorem 2.3, whose witness Φ0\Phi_0 mentions no carrier.

Tier one: consistency without infinity

The first consistency theorem of the development needs nothing beyond plain Isabelle/HOL.

Theorem 3.1 (Consistency of NK). ⊬⊥\nvdash\bot, at every signature pp; consequently no formula is derivable together with its negation. (Isabelle: consistency, theory Main_Results of A1\mathcal{A}_1), (Isabelle: no_contradiction, theory Main_Results of A1\mathcal{A}_1)

The proof exhibits a model and appeals to soundness: whatever is derivable is true in the model, and ⊥\bot is not. The model is standard and finite: one individual, two truth values, and every function domain the full function space, finite because its argument and result domains are, represented by finite graphs. This is Andrews’ consistency argument for Q0Q_0 (Theorem 5403 of [3]). The logical constants are not defined individually: the frame is an instance of an abstract interface (lambda_universe) over which negation, disjunction, quantification, equality and description are constructed (Isabelle: concrete_lambda_universe, theory Consistency of A1\mathcal{A}_1); the description operator is interpreted by Isabelle’s own definite description THE. The artifact builds such a model for any number k>0k > 0 of individuals; the larger instances serve the finite-model arguments of § 5, and their parameter interpretation can distinguish any prescribed finite family of constants. The one-element model refutes every sentence without a finite model, such as an axiom of infinity. The first tier asserts the consistency of no such sentence, which is why it needs neither an infinite model nor a stronger meta-theory.

What the proof does not use is recorded by a footprint audit (theory Footprint_Checks), which instantiates the consistency theorem at the finite parameter types bool and unit (Isabelle: consistency_bool_params, theory Footprint_Checks of A1\mathcal{A}_1). The object logic may have a finite signature, the model has finite domains at every type, and no set theory is involved.

No choice operator occurs in the model itself, while the proofs about it inherit choice as a dependency on the meta-logic. The defining equations of the model, for its domains, application, abstraction, parameter interpretation and assignment, contain neither SOME nor THE; the description operator comes from the interface, where it is Isabelle’s definite description THE, not a choice operator. Theory Footprint_Deps checks the first claim mechanically. The same theory audits the proof terms of the consistency theorem and finds the meta-logic’s choice principles in four places: the datatype package, the lemmas about fresh variable names in the syntax, the evaluation of abstraction and quantification in the semantics, and the canonical assignment of the soundness proof. The footprint claim is therefore “no choice in the model”, not “no choice in the proof” (Remark 8.4).

The kind of statement obtained deserves to be made precise. The meta-logic Isabelle/HOL has an axiom of infinity; the object logic has none. The meta-level infinity is used in two places. The syntax uses it: the term type and the inductively defined set of derivations are infinite, as they must be in any meta-theory that speaks about derivations of arbitrary length. The models use it too, as formalized: their value carrier uu is one datatype ival, a recursive type and hence infinite, inside which every finite model is built, and the proofs about the models use the natural numbers freely. The content of each instance, by contrast, uses nothing beyond finite objects: a single model with finite domains, in which evaluation is decidable, and a soundness proof by induction over derivations. A finite fragment of ival would suffice for any single derivation, which mentions finitely many types; this is a metatheoretic remark (not formalized here): the model for all types is infinite as a whole, and the formalization does not isolate such fragments. So the consistency proof is carried out in a logic with an axiom of infinity, about a logic without one. No logic proves its own consistency here, and Gödel’s second incompleteness theorem does not apply to the object logic: a theory with a standard model all of whose domains are finite, one individual and full function spaces above it, interprets no arithmetic.

For many applications this is no restriction. Where HOL serves as a representation language—as in the LogiKEy methodology of semantic embeddings [9], whose embedded object logics assume no object-level axiom of infinity—the monomorphic core of the logic employed (TH0, the monomorphic dialect of the TPTP THF family [40], without its choice operator) is the one certified here. The certificate makes no claim about Isabelle/HOL’s polymorphic definitional superstructure, whose consistency is established separately [26].

The boundary: infinity on the object side

The Dedekind-style axiom of infinity [15] is the single closed, pure object formula

DInf=∃Fι⇒ι.(∀X Y. FX=FY⊃X=Y)∧(∃C. ∀Z. ¬(FZ=C))\mathrm{DInf} = \exists F_{\iota\Rightarrow\iota}.\left(\forall X\ Y.\ F X = F Y \mathbin{\supset} X = Y\right) \land\left(\exists C.\ \forall Z.\ \neg\left(F Z = C\right)\right)

(Isabelle: DInf, theory NK_Infinity of A1A_1), asserting the existence of an injective, non-surjective self-map of the individuals. It mentions no parameters at all. Up to notation and elementary logical equivalence, DInf is the axiom of infinity of HOL Light (INFINITY_AX [19]): HOL Light and HOL4 postulate this sentence, and Isabelle/HOL an equivalent skolemized form.

Proposition 4.1 (Finite refutation). Every Henkin model with a finite individual domain refutes DInf, under every type-respecting assignment.

(Isabelle: DInf_refuted_finite, theory NK_Infinity of A1A_1)

Proposition 4.1 is the pigeonhole principle in semantic form: an injective self-map of a finite set is surjective. In particular, the finite models of § 3 refute DInf, so the argument of the first tier does not extend to con⁡{DInf}\operatorname{con}\{\mathrm{DInf}\}.

Could an infinite model be built in plain Isabelle/HOL instead? Plain Isabelle/HOL has infinite types, and every level N\mathbb{N}, N⇒bool\mathbb{N} \Rightarrow\mathsf{bool}, … of the full function-space tower exists as a type. What it cannot prove is that one type carries the whole tower at once. The obstruction is stated in four steps: three observations, on the shape of a formalized model (1), on standard models (2) and on Henkin models (3), and one argument that carries the conclusion (4): (1) In the deep embedding the object types are values of a datatype, not types of the meta-logic. A formalized model is therefore one evaluation function, taking terms of all object types to values of one meta-level type uu, the value carrier, inside which all domains live (ivalival for the finite models of § 3, Paulson’s VV for the model of § 8). The codomain cannot vary with the object type, because the simple types of the meta-logic do not depend on values. The single carrier is thus not part of BKK’s notion of model, where “standard” means only that the function domains are full; it is imposed by the formalization in simply-typed HOL.

(2) Over an infinite individual domain with full function spaces, the carrier must have cardinality at least ℶω\beth_{\omega}, the supremum of the cardinalities of the levels of the tower. Plain Isabelle/HOL cannot prove any of its types to be that large. For a type τ\tau to carry the tower, each level N\mathbb{N}, N⇒bool\mathbb{N} \Rightarrow\mathrm{bool}, …\ldots must inject into τ\tau. In the standard set-theoretic semantics of HOL, with a countable type ind\mathrm{ind}, every type has cardinality below ℶω\beth_{\omega}, because each type is built from ind\mathrm{ind} by finitely many function-space and definitional steps. So for every τ\tau one of these injections fails in that semantics and is therefore, by soundness, not a theorem.

(3) Henkin models avoid the cardinality obstruction, but they need not satisfy DInf (Remark 5.6). The canonical way of building one that does, the term-model construction of § 6, takes con⁡{DInf}\operatorname{con}\{\mathrm{DInf}\} as its premise.

(4) That no other way succeeds either is Gödel’s second incompleteness theorem. NK with infinity and choice is Church’s type theory with infinity and choice, and this theory interprets the monomorphic core of the meta-logic: the meta-level type of individuals by the object individuals, infinite by DInf, and function types by function types. A consistency proof of NK with infinity and choice in plain Isabelle/HOL would therefore yield a consistency proof of Isabelle/HOL’s own core, which Gödel’s theorem excludes.3 The two theories are in fact of the same strength: by the classical analysis both are equiconsistent with Mac Lane set theory, a subsystem of Zermelo set theory (Mathias [28]), a standard account we rely on and do not formalize; the consistency of type theory with infinity in Zermelo set theory goes back to Kemeny [23]. For the extension by infinity alone we make no such claim: the argument would need in addition that adjoining the choice scheme does not raise consistency strength, probably in the theory itself, a classical fact whose proof without replacement is delicate [28] (Remark 8.4).

Steps (1) and (3) appear in the formalization; step (2) is a cardinality argument about the standard semantics of HOL, carried out at the meta-level; step (4) is a metatheoretic observation the artifacts discuss but do not formalize.

The conclusion is that the meta-theory has to be strengthened, and the obstacle is a familiar one: Harrison’s self-verification of HOL Light removes it by a universe axiom [19]; its successors add no axiom but state soundness under an explicit assumption, a type with a membership relation satisfying the axioms of set theory [25, 1]. § 7 to § 9 show how little strength beyond plain Isabelle/HOL the second tier needs, through two small interfaces. In the terms of a hierarchy of infinity axioms, write HOL0\mathrm{HOL}_0 and HOL1\mathrm{HOL}_1 for higher-order logic without and with an axiom of infinity. The metalogic Isabelle/HOL is HOL1\mathrm{HOL}_1: its own axiom of infinity is DInf on the type ind with the witnesses named—theory Nat postulates constants Zero_Rep and Suc_Rep with Suc_Rep injective and never Zero_Rep, the skolemized form mentioned above, interderivable with DInf by naming the witnesses and by ∃\exists-introduction (not formalized). Tier one is HOL1⊢con⁡(HOL0)\mathrm{HOL}_1 \vdash\operatorname{con}(\mathrm{HOL}_0), while HOL1⊢con⁡(HOL1)\mathrm{HOL}_1 \vdash\operatorname{con}(\mathrm{HOL}_1) is not available. Tier two, as formalized, is HOL1+ZFC_in_HOL⊢con⁡(HOL1)\mathrm{HOL}_1 + \mathrm{ZFC\_in\_HOL} \vdash\operatorname{con}(\mathrm{HOL}_1). Its proof depends on Paulson’s universe only through the seven assumptions of the Harrison-style interface (§ 8). This bounds what the proof uses, not the consistency strength it needs: that every interpretation of the interface yields con⁡(HOL1)\operatorname{con}(\mathrm{HOL}_1) is a theorem of the artifact, but the only interpretation it provides is Paulson’s universe VV, and no weaker one, such as a single strong-limit type above ind, is shown to exist. The reading “HOL1\mathrm{HOL}_1 plus one strong-limit type”, suggested by Harrison’s axiom II, therefore describes the interface informally; it is not a theorem of the artifact. § 5 and § 6 measure where the boundary between the tiers runs; § 7 to § 9 then build the second tier.

Measuring the boundary: two senses of infinity

The first-order sentences

The axiomatization of “the domain is infinite” in the language of pure equality [17 III.6.3] consists of the constant-free sentences

∃≥n=∃x1…∃xn. ⋀i<j¬(xi=xj),n∈N,\exists_{\geq n} = \exists x_1 \ldots\exists x_n.\ \bigwedge_{i<j} \neg(x_i = x_j), \qquad n \in\mathbb{N},

one for each nn (Isabelle: ExDistinct, theory NK_Infinity of A1A_1). Each has a finite model, while the set of all of them has none (in general, the class of infinite structures is Δ\Delta-elementary, that of finite structures is not [17 VI.3.4]). This, and not the order of the language, is what separates the sentences from DInf.4 The boundary between the tiers thus runs between sentences that have finite models and sentences that have none. Inside NK, DInf derives every one of the sentences:

Theorem 5.1 (DInf derives every finite cardinality). Over an infinite signature pp, for every nn: {DInf}⊢∃≥n\{\mathrm{DInf}\} \vdash\exists_{\ge n}. (Isabelle: axiom_derives_every_finite_cardinality, theory Main_Results of A1\mathcal{A}_1)

The derivation is built by meta-level recursion on nn, one NK-derivation for each nn: two parameters serve as eigenvariables for the self-map FF and the point CC outside its range, the witnesses are CC, FCF C, F(FC)F(F C), …\ldots, and their pairwise distinctness follows from injectivity.

The semantic bridge

Proposition 5.2 (Satisfaction of DInf). In every Henkin model and under every type-respecting assignment, DInf is satisfied if and only if some element dd of the function domain Dι→ι\mathcal{D}_{\iota\to\iota} is injective on Dι\mathcal{D}_{\iota} and omits a point of Dι\mathcal{D}_{\iota}. In a standard model, where that domain is full, this holds if and only if Dι\mathcal{D}_{\iota} is Dedekind-infinite as a set, that is, admits an injective self-map that is not surjective. (Isabelle: DInf_sat_iff, theory NK_Infinity of A1),(Isabelle:‘DInfsatiffDedekind‘,theoryNK_Infinityof\mathcal{A}_1), (Isabelle: `DInf_sat_iff_Dedekind`, theory NK\_Infinity of\mathcal{A}_1)

The first-order sentences are consistent

Theorem 5.3 (Consistency of the first-order sentences). At every signature pp, finite or infinite: ¬({∃≥n∣n}⊩⊥)\neg(\{\exists_{\ge n}\mid n\}\Vdash\bot). (Isabelle: finite_cardinalities_consistent, theory Main_Results of A1\mathcal{A}_1)

The proof constructs no infinite model: a finite part of the sentences mentions a largest nn, and the finite standard model of § 3 with at least nn individuals satisfies it, so no finite part derives falsity, which is the statement. This is the textbook compactness argument that a theory with arbitrarily large finite models has an infinite model, carried out with the very same sentences [17 VI.2.2]—except that no infinite model is ever formed. The sentences mention no constants, which is why the signature may be finite; over an infinite signature the context, being pure, has ⊩\Vdash and ⊢\vdash agree (Isabelle: fprov_eq_bprov, theory Calculus of A1\mathcal{A}_1), and the theorem may there equally be read as con⁡{∃≥n∣n}\operatorname{con}\{\exists_{\ge n}\mid n\}.

The artifact also carries out the finite-model argument in the classical form of the compactness argument by expansion with new constants [38, 27, 21, 34], applied in type theory in Theorem 5506 of Andrews’ §55 [3]. For an injective family f:N→pf:\mathbb{N}\to p of parameters over an infinite signature, the scheme Ineqf={¬(fi=ιfj)∣i≠j}\mathrm{Ineq}_f=\{\neg(f_i =_{\iota} f_j)\mid i\ne j\} is consistent by the same finite models (Isabelle: con_Ineq_fprov, theory NK_Infinity of A1\mathcal{A}_1); it derives every ∃≥n\exists_{\ge n} (Isabelle: Ineq_derives_distinct_n, theory NK_Infinity of A1\mathcal{A}_1); and a cut reduces every finitary consequence of the sentences to one of the scheme (Isabelle: distinct_scheme_fprov_Ineq, theory NK_Infinity of A1\mathcal{A}_1).

The first-order sentences do not derive DInf

Theorem 5.4 (The first-order sentences do not derive DInf). At every signature pp, finite or infinite: ¬({∃≥n∣n}⊢DInf)\neg(\{\exists_{\ge n}\mid n\}\vdash\mathrm{DInf}). (Isabelle: finite_cardinalities_do_not_derive_axiom, theory Main_Results of A1\mathcal{A}_1)

Again a finite-model argument: finitely many of the sentences hold in a finite standard model, which refutes DInf (Proposition 4.1), so by soundness they do not derive it. With Theorem 5.1, the first-order axiomatization of “the domain is infinite” is thus strictly weaker in NK than DInf. Theorem 5.4 separates DInf only from finite parts of the set, and no standard model separates it from the whole set (Remark 5.6); the separating model is a Henkin model, supplied by the completeness proof:

Theorem 5.5 (Henkin countermodel). Over every infinite signature pp there is a Σ\Sigma-Henkin model whose total domain embeds into the term type, that satisfies every sentence ∃≥n\exists_{\ge n} and refutes DInf. (Isabelle: henkin_scheme_refutes_DInf, theory NK_Infinity of $\mathcal{A}_1`)

The model is the term model that the completeness proof builds to refute a non-derivable formula; over a countable signature the term type is countable, and so is the model. The construction needs a reserve of unused parameters as large as the signature, yet the theorem carries no such hypothesis, because the reserve is created inside the signature. The signature is mapped injectively into a part of itself whose complement has the signature’s cardinality; the model is built there for the renamed sentences and pulled back along the renaming, which fixes DInf and every ∃≥n\exists_{\ge n}, both being pure. (The formal statement takes an injective family ff of parameters, available over any infinite signature, and records that the model also satisfies the scheme Ineq⁡f\operatorname{Ineq}_f.)

Remark 5.6 (Semantic infinitude does not force DInf). The individual domain of the model of Theorem 5.5 is infinite, since every ∃≥n\exists_{\ge n} holds in it. Yet DInf is false there: in a Henkin model the function domain Dι→ι\mathcal{D}_{\iota\to\iota} may be too sparse to contain any injective non-surjective self-map, and in this one it is. Conversely, in any Henkin model satisfying DInf, the witnessing function, sparse domains or not, acts injectively and non-surjectively on Dι\mathcal{D}_{\iota}, so the individual domain is Dedekind-infinite (Isabelle: DInf_sat_Dedekind_infinite, theory NK_Infinity of $\mathcal{A}_1). In Henkin semantics, then, the object-level axiom is strictly stronger than infinitude of the domain; at standard models DInf coincides with Dedekind infinitude of the domain (Proposition 5.2). Table 1 summarizes the comparison.

Completeness and model existence remain in plain Isabelle/HOL

Completeness for the extension by DInf needs nothing beyond plain Isabelle/HOL, neither the universe interfaces of § 7 and § 8 nor their realization in Paulson’s set-theoretic universe:

Theorem 6.1 (Completeness of the DInf extension, in plain Isabelle/HOL). For every infinite signature pp and every infinite value carrier uu: if AA is well-formed and {DInf}⊨uA\{\mathrm{DInf}\}\models_u A, then {DInf}⊢A\{\mathrm{DInf}\}\vdash A. (Isabelle: NK_completeness_DInf, theory HOL_Universe of A2\mathcal{A}_2)

The theorem is an instance of the hypothesis-relative completeness of A1\mathcal{A}_1 (Theorem 2.3; the context {DInf}\{\mathrm{DInf}\} is finite and pure, and for finite contexts the injection hypothesis of that theorem can be dropped—infinitude of signature and carrier suffices), and the theory proving it imports no set theory.5

Completeness says nothing about the consistency of DInf: were DInf inconsistent, both sides of the theorem would hold vacuously, since a hypothesis without models has every formula as a semantic consequence, and an inconsistent hypothesis derives every formula.

Model existence for the extension is likewise available in plain Isabelle/HOL, conditional on its consistency. Over a countably infinite signature, con {DInf} as an explicit hypothesis yields a countable Henkin model of DInf (Isabelle: countable_henkin_model_DInf_of_con, theory HOL_Universe of A2A_2); what plain Isabelle/HOL does not supply is the hypothesis itself (§ 4), which this development obtains only in the stronger meta-theory. Once the hypothesis is discharged there (§ 8.2), the model is obtained outright, still constructed in plain Isabelle/HOL (Isabelle: countable_henkin_model_DInf, theory HOL_in_HOL_Deep_Infinity_ZFC of A2A_2).

Standard models: consistency and choice

Choice in full standard semantics

Choice in full standard semantics. Let ACrel\mathrm{AC}^{\mathrm{rel}} denote the relational choice scheme: for each pair of types σ,τ\sigma,\tau, the closed object formula

ACστrel=∀Rσ⇒τ⇒o. (∀Xσ. ∃Yτ. R X Y)⊃(∃Fσ⇒τ. ∀Xσ. R X (F X))\mathrm{AC}^{\mathrm{rel}}_{\sigma\tau} = \forall R_{\sigma\Rightarrow\tau\Rightarrow o}.\,(\forall X_{\sigma}.\,\exists Y_{\tau}.\,R\,X\,Y)\supset(\exists F_{\sigma\Rightarrow\tau}.\,\forall X_{\sigma}.\,R\,X\,(F\,X))

(Isabelle: ACrel, theory HOL_Universe of A2\mathcal{A}_2), asserting that every left-total relation, one relating each XX to at least one YY, has a choice function FF.

Proposition 7.1 (Choice holds in every standard model). Every instance ACστrel\mathrm{AC}^{\mathrm{rel}}_{\sigma\tau} of the relational choice scheme is satisfied in every standard model, under every type-respecting assignment. (Isabelle: ACrel_sat, theory HOL_Universe of A2\mathcal{A}_2)

The witnessing function is the semantic λ\lambda-abstraction of a meta-level Hilbert choice of related targets, which lies in the function domain because that domain is full. This is a theorem about standard models: in Henkin models, whose sparse function domains need not contain the choice function, the scheme need not hold (Table 1).

Consistency from an abstract universe

The consistency argument of the second tier is stated first for an arbitrary value carrier, with no set theory involved; a concrete carrier is constructed only in § 8.2.

Theorem 7.2 (Abstract consistency of full HOL). Suppose some standard model, over an arbitrary value carrier, has a function domain Dι⇒ιD_{\iota\Rightarrow\iota} containing an element that is injective and not surjective on the individual domain DιD_\iota. Then

con⁡({DInf}∪{ACστrel∣σ,τ types}).\operatorname{con}\left(\{D\mathrm{Inf}\}\cup\{\mathrm{AC}^{\mathrm{rel}}_{\sigma\tau}\mid\sigma,\tau\ \text{types}\}\right).

(Isabelle: con_full_HOL_rel, theory HOL_Universe of A2\mathcal{A}_2)

The proof combines the satisfaction of DInf in such a model (Proposition 5.2), the satisfaction of the choice scheme (Proposition 7.1) and soundness. Since NK already carries Boolean and functional extensionality and typed description, the theory whose consistency is certified is full classical higher-order logic in Church’s sense [14, 4]: NK extended by Dedekind infinity and relational choice. Here “full” means that all of Church’s postulates are present, the basic logical postulates, extensionality, description, infinity and choice, though not always in Church’s formulation: Dedekind’s axiom stands in place of his Axioms 7 and 8, a relational choice scheme in place of his selection operator, and Boolean extensionality, which Church mentions but does not postulate, is included.

The model required by the theorem can be obtained from a sufficiently large universe type; § 8 makes precise how large, and how much set theory is needed to construct it. As an intermediate step, the interface hol_universe fixes a carrier with domains, application and abstraction satisfying the frame conditions (full function spaces, truth values, extensionality, a domain-respecting parameter interpretation) together with Dedekind-infinite individuals. Nothing is assumed about the logical constants: the interface extends lambda_universe of § 3, which supplies them. Any interpretation of hol_universe, a carrier type with domains, application and abstraction satisfying its assumptions, yields a model as required by Theorem 7.2, and thereby the consistency (Isabelle: con_full_HOL_universe, theory HOL_Universe of A2\mathcal{A}_2).

A Harrison-style interface and its set-theoretic realization

The interface

To construct an interpretation of hol_universe, which still speaks of types, domains, application and abstraction, we follow Harrison. His self-verification of HOL Light [19] adds to HOL Light one axiom II: a type II of cardinality strictly above that of the individuals, such that every set of cardinality below II has its power set of cardinality below II. In cardinal terms this is a strong limit ι>ℵ0\iota> \aleph_0, for which Harrison notes the cardinality of Vω+ωV_{\omega+\omega} as a realization. Our rendering is the interface harrison_universe, which replaces cardinal comparison by a smallness predicate closed under encoded power collections. It fixes only four constants on a carrier: an injective pairing prpr, an injective encoding encenc of the small collections, a smallness predicate SmSm, and a small Dedekind-infinite collection D0D_0 of individuals. These are subject to seven assumptions: injectivity of pairing and encoding, downward closure of smallness, closure under products, closure under encoded power collections (the collection of encodings of small subcollections of a small collection is small), smallness of D0D_0, and Dedekind infinitude of D0D_0. It mentions neither types nor domains nor application. Since the interface is the development’s most reusable component, we reproduce it in full:

locale harrison_universe =
  fixes pr :: "'u ⇒ 'u ⇒ 'u" and enc :: "('u ⇒ bool) ⇒ 'u"
    and Sm :: "('u ⇒ bool) ⇒ bool" and D0 :: "'u ⇒ bool"
  assumes pr_inj: "pr a b = pr c d ⟹ a = c ∧ b = d"
    and enc_inj: "⟦Sm X; Sm Y; enc X = enc Y⟧ ⟹ X = Y"
    and Sm_sub: "⟦Sm X; Y ≤ X⟧ ⟹ Sm Y"
    and Sm_prod: "⟦Sm X; Sm Y⟧ ⟹ Sm (λz. ∃a b. X a ∧ Y b ∧ z = pr a b)"
    and Sm_pow: "Sm X ⟹ Sm (λz. ∃Y. Y ≤ X ∧ Sm Y ∧ z = enc Y)"
    and Sm_D0: "Sm D0"
    and D0_inf: "∃f c. (∀a. D0 a ⟶ D0 (f a))
      ∧ (∀a b. D0 a ⟶ D0 b ⟶ f a = f b ⟶ a = b)
      ∧ D0 c ∧ (∀a. D0 a ⟶ f a ≠ c)"

Theorem 8.1 (The Harrison-style interface suffices). From every interpretation of harrison_universe an interpretation of hol_universe is constructed: domains are collections of encoded functional graphs, abstraction is encoding, application is decoding. Consequently the consistency of Theorem 7.2 follows from the Harrison-style assumptions alone. (Isabelle: harrison_hol_universe, theory HOL_Universe of A₂)

In effect, the Harrison-style interface postulates one carrier type in which every domain of the ι,o\iota,o-type hierarchy can be placed. It is closed under the operations that building each single type requires, pairing and encoded power collections of small collections, but not under its own full function space, which by Cantor’s theorem would be strictly larger; the carrier as a whole is accordingly not small (Isabelle: not_Sm_UNIV, theory HOL_Universe of A₂). This restricted closure is a comparably weak assumption: neither replacement nor union is demanded. Which cardinal hypothesis the seven assumptions correspond to exactly is left open here. Note that we deliberately call the interface Harrison-style and sufficient: no minimality claim is made or formalized, and no formal equivalence with Harrison’s axiom II is asserted; Sm_pow is the counterpart of his power-set clause and Sm_D0 that of his clause on the individuals. The interface serves two purposes. It isolates the strong-limit core of Harrison’s universe axiom II, the encoded power collections of Sm_pow, as the assumption that carries the additional strength of our construction. And, mentioning neither types nor domains nor application, it is reusable verbatim: any consistency argument for an embedded logic that requires full function spaces over an infinite domain of individuals can instantiate it, with Theorem 8.1 supplying the model construction.

The set-theoretic realization

Paulson’s ZFC_in_HOL [32] axiomatizes a Zermelo–Fraenkel universe with choice as an Isabelle/HOL type VV. Over it, the domains of the intended standard model are defined by three equations:

D_{\\iota} = \\omega,\\qquad D_o = \\{0,1\\},\\qquad D_{\\sigma\\Rightarrow\\tau} = \\prod_{x\\in D_\\sigma} D_\\tau\\quad\\text{(the full }V\\text{-function space).}

Application is the set-theoretic application of a function to an argument, λ\lambda-abstraction the formation of a function’s graph over the domain, and the parameter interpretation assigns to every parameter of a type one fixed element of that type’s domain (Isabelle: VJv_param_independent, theory HOL_in_HOL_Deep_Infinity_ZFC of A2). Interpreting all parameters alike is a simplification, not a necessity: the consistency theorems below hold for any domain-respecting parameter interpretation.

Theorem 8.2 (Realization). The VV-structure satisfies the assumptions of harrison_universe, with Sm as Paulson’s smallness, encoding as set comprehension and D0=ωD_0 = \omega, and, directly, those of hol_universe, with the successor function on ω\omega witnessing Dedekind infinitude. (Isabelle: V_harrison_universe, theory HOL_in_HOL_Deep_Infinity_ZFC of A2), (Isabelle: V_hol_universe, theory HOL_in_HOL_Deep_Infinity_ZFC of A2)

Theorem 8.3 (Consistency of full classical HOL). con⁡({DInf}∪{ACστrel∣σ,τ})\operatorname{con}(\{DInf\} \cup\{AC^{\mathrm{rel}}_{\sigma\tau}\mid\sigma,\tau\}), at every signature. (Isabelle: con_full_HOL, theory HOL_in_HOL_Deep_Infinity_ZFC of A2)

Theorem 8.3 is Theorem 8.1 applied to the instance of Theorem 8.2; it depends on the VV-structure only through the seven assumptions of the Harrison-style interface. In particular con⁡({DInf})\operatorname{con}(\{DInf\}) holds at every signature (Isabelle: con_DInf, theory HOL_in_HOL_Deep_Infinity_ZFC of A2), and this is exactly the premise of the conditional model existence of § 6. Combining the two yields a countable Henkin model of DInf whose construction never mentions VV; the set-theoretic universe serves only to discharge the premise.

Remark 8.4 (Readings at lower strength). Theorem 8.3 is a theorem of Isabelle/HOL extended by ZFC_in_HOL; it is therefore a consistency result relative to that theory. Two readings at lower strength are metatheoretic, made precise in the documentation of A2 and not themselves formalized theorems. First, choice can be dropped: Gödel’s constructible universe interprets ZFC in ZF, so the result holds relative to ZF. Second, the construction uses no replacement, so it can be carried out in Zermelo set theory with choice; whether choice can be dropped there as well is delicate [28]. The

rank analysis of the next section, which places every domain in Vω+ωV_{\omega+\omega}, is the formal basis of both readings.

Rank analysis

We now bound how much of the set-theoretic universe the model of the previous section occupies. Recall that the von Neumann universe is built in stages, V0=∅V_0=\varnothing, Vα+1=P(Vα)V_{\alpha+1}=\mathcal{P}(V_\alpha) and Vλ=⋃α<λVαV_\lambda=\bigcup_{\alpha<\lambda}V_\alpha at limits λ\lambda, and that the rank of a set is the first stage at which it appears as a subset. VωV_\omega is the union of the finite stages, and Vω+ωV_{\omega+\omega} the union of the stages Vω+nV_{\omega+n} obtained from VωV_\omega by finitely many power-set steps; these are the sets Zermelo set theory provides.

Theorem 9.1 (Rank bound, type by type). In the concrete model, rank⁡(Dι)=ω\operatorname{rank}(D_\iota)=\omega, and for every type σ\sigma:

rank⁡(Dσ)<ω+ω,henceDσ∈Vω+ω.\operatorname{rank}(D_\sigma)<\omega+\omega,\qquad\text{hence}\qquad D_\sigma\in V_{\omega+\omega}.

(Isabelle: rank_D_iota, theory HOL_in_HOL_Deep_Infinity_ZFC of A2A_2), (Isabelle: rank_D_lt, theory HOL_in_HOL_Deep_Infinity_ZFC of A2A_2), (Isabelle: D_in_Vset_ww, theory HOL_in_HOL_Deep_Infinity_ZFC of A2A_2)

Each function-space layer is contained in a triple power set of the union of its argument and result domains, so it raises the rank by at most three power-set steps above those domains; the limit ordinal ω+ω\omega+\omega absorbs these finite increments. The statement is one theorem, quantified over the object-level type σ\sigma, a value of the datatype of types. The set of all domains, {Dσ∣σ a type}\{D_\sigma\mid\sigma\ \text{a type}\} taken as one object, has rank ω+ω\omega+\omega, since the domains’ ranks grow unboundedly below ω+ω\omega+\omega, and is therefore not an element of Vω+ωV_{\omega+\omega} (not formalized). The bound substantiates the readings of the previous section: a single derivation mentions finitely many types, so its refutation uses only sets of bounded rank, finitely many power-set steps above ω\omega.

:::

Lessons from the formalization

Two tiers, one boundary

Two tiers, one boundary. Soundness alone shows where the first tier ends: finite models satisfy the first-order sentences and refute DInf, so finite-model arguments certify the sentences but not the axiom. Soundness alone does not show that the two senses of infinity differ: at standard models they coincide (Proposition 5.2), and separating them needs a model of all the sentences that refutes DInf. Such a model exists only in Henkin semantics, where function domains may be sparse, and it is the completeness proof that builds it (Theorem 5.5, Remark 5.6).

Eigenparameters and finitary consequence

Eigenparameters and finitary consequence. Over a fixed signature, an infinite context may use every parameter there is. The quantifier rule NK(ΠI\Pi_I) then cannot be applied, because its eigenparameter, the parameter standing for an arbitrary element of its type, must be fresh for the context. Andrews-style finitary consequence H\mathsf{H}, where some finite part of the context derives the conclusion, avoids the restriction as well: a finite context leaves fresh parameters over an infinite signature, so no purity condition is needed.6

Abstract interfaces before concrete models

Interposing hol_universe and harrison_universe between the consistency theorem and VV separates what the proof needs from where it is realized: Theorem 8.1 depends on seven assumptions about four constants, and VV satisfies these assumptions but is itself not part of the proof. The interfaces also make dependencies visible in what they do not mention: two properties stem from the meta-logic rather than from the interfaces. The object-level description operator is interpreted by Isabelle’s definite description THE, and the relational choice scheme holds in every standard model because the meta-logic’s own choice supplies the witness (§ 7.1).

Another design decision is the locally nameless syntax of A1\mathcal{A}_1: no proof in the development ever renames a bound variable, in exchange for a thin layer of named binders in which the axiom DInf of § 4 is written.

Related work

This paper describes two AFP entries: A1\mathcal{A}_1 [6], which formalizes BKK’s syntax, Henkin semantics and calculus [5] with Andrews-style description [2] and was extended for this paper, and its companion A2\mathcal{A}_2 [7], which adds the second tier. Closest in method, a deep embedding of a Church-style type theory with machine-checked metatheory, is the work on Andrews’ Q0Q_0. Díaz [16] machine-checks its soundness and, by Andrews’ one-element standard model (Theorem 5403 of [3]), its consistency; Schlichtkrull’s entry [37], developed independently in the same month, formalizes soundness as well. Building on Díaz’s entry, Boserup, Huerta y Munive and Schlichtkrull add Henkin completeness [10] by an abstract consistency property, using a locale framework for such properties [18]; see also Koch and Kirst’s analysis of second-order logic in Coq [24]. The Q0Q_0 line develops its semantics over ZFC_in_HOL throughout, the one-element model included; the present embedding admits set theory only on the second tier, so that tier one, the same classical argument for NK, is a theorem of plain Isabelle/HOL with an audited footprint. Closest in question is Harrison’s self-verification of HOL Light [19]: machine-checked consistency of HOL with infinity and choice is not new, nor is the division into two tiers. Harrison proves soundness and consistency of HOL Light’s core twice, without its axiom of infinity inside HOL Light and with it inside HOL Light plus a strong-limit universe axiom, and already notes Vω+ωV_{\omega+\omega} as a realization. Its successors by Kumar, Arthan, Myreen and Owens [25] and the verified implementation Candle [1] extend the soundness result to HOL’s definitional mechanisms, taking the existence of a set-theoretic universe as an assumption of the soundness theorem. All of these work with standard semantics and prove soundness; none has a completeness theorem. Harrison’s object logic has polymorphism and the choice operator ε\varepsilon, ours has primitive equality and typed description, so neither consistency result subsumes the other. Beyond completeness itself, the following are, to our knowledge, new. On the Henkin side: conditional model existence on the first tier, in hypothesis-relative form (§ 2 and § 6); the characterization of satisfaction of DInf in Henkin models and the measurement of the boundary between the two senses of infinity by NK-derivations and a Henkin countourmodel (§ 5); the countable Henkin model of DInf for which the universe discharges only the premise con {DInf} (§ 8.2). On the standard side: the per-type rank bound as a theorem (§ 9). Refinements of Harrison’s two tiers are, on the first, a possibly finite signature, no choice operator in the definition of the model and a mechanical footprint audit (§ 3), and, on the second, the factorization of the argument through two reusable locales, one of which isolates a version of Harrison’s axiom (§ 7 and § 8).

The object logic is also the base of dependently typed HOL (DHOL) [35, 36], which translates into HOL by erasing the dependencies, soundly and completely for provability [35], so that the consistency results of this paper transfer to it. Rabe’s lax models for DHOL [33], a Henkin-style generalization of standard models, come with soundness and completeness theorems, so the boundary drawn here can be drawn for DHOL as well (see the conclusion). For Lean’s theory, by contrast, Carneiro gives a set-theoretic model and thereby consistency relative to ZFC with countably many inaccessible cardinals [11], each universe level modelling the theory with one level fewer; the metatheory of its definitional equality is still being settled [12]. Every level contains the natural numbers, so it contains no infinity-free tier with finite models, and there is no completeness theorem that ties provability to a class of models.

Nipkow and Roßkopf formalize Isabelle’s own metalogic with a verified proof checker [30], the same programme for the logical framework beneath Isabelle/HOL.

Conclusion

What a copy of higher-order logic can certify about itself has two tiers, measured by the strength the certifying copy needs, and both correspond to the two results of Harrison’s self-verification of HOL Light. On the first tier, plain Isabelle/HOL certifies Church’s type theory without an axiom of infinity, by a standard model with one individual. On the second, a Harrison-style universe axiom realized in ZFC_in_HOL suffices for full classical higher-order logic with infinity and relational choice, with the domain of every type of rank below ω+ω\omega+ \omega. What the present formalization adds is Henkin completeness, and with it a semantics that matches the calculus exactly and, on the first tier, compactness and model existence conditional on consistency alone. Even the countable Henkin model of the Dedekind axiom of infinity is therefore built in plain Isabelle/HOL. The boundary between the tiers runs between sentences that have finite models and sentences that have none; the two senses of infinity are separated by a countable Henkin model that satisfies every sentence “there are at least nn individuals” and refutes the axiom. Every theorem, proposition and corollary stated above is a machine-checked theorem of the two AFP entries A1\mathcal{A}_1 and A2\mathcal{A}_2; the metatheoretic readings are marked as not formalized.

Three directions remain open. Whether the Harrison-style interface is minimal, in particular whether the encoded-power assumption Sm_pow is necessary for full function spaces, is not settled here. The equiconsistency of Isabelle/HOL’s monomorphic core with NK plus infinity and choice is a candidate for formalization in its own right; on that basis, step (4) of the argument in § 4, the appeal to Gödel’s second incompleteness theorem, could be formalized as well. It would require interpreting enough arithmetic inside NK + DInf, with Paulson’s mechanized incompleteness theorems [31] as the model to follow; the natural first step, Dedekind’s own theorem that the axiom yields a model of the Peano axioms, would itself be a worthwhile derivation inside NK.

Finally, the two interfaces of § 7 and § 8 invite reuse beyond this paper. The natural first candidate is dependently typed HOL (§ 11): connecting a formalization of Rabe’s DHOL semantics [33] to the interfaces of this paper would test them on a logic properly beyond Church’s.

Artifacts

Both artifacts are entries of the Archive of Formal Proofs, released with Isabelle2026 in October 2026, and both build with Isabelle2026. A1A_1 is HOL_in_HOL_Deep [6] (https://isa-afp.org/entries/HOL_in_HOL_Deep.html), first published in August 2026 and extended in September 2026 for this paper. A2A_2 is its companion HOL_in_HOL_Deep_Infinity_ZFC [7] (https://isa-afp.org/entries/HOL_in_HOL_Deep_Infinity_ZFC.html), which also uses the AFP entry ZFC_in_HOL. The versions this paper describes extend the released entries by a few facts cited above (DInf_sat_iff_Dedekind, not_Sm_UNIV, countable_henkin_model_DInf_of_con, and the direct finite-model proofs of § 5, which drop the infinite-signature hypothesis from Theorems 5.3 and 5.4) and by the theory Footprint_Deps of § 3. The complete sources in the versions described here accompany the arXiv version as ancillary files, and every artifact pointer in this paper resolves in them. The same extensions are part of the Archive’s development version since November 2026 (https://devel.isa-afp.org/entries/HOL_in_HOL_Deep.html, https://devel.isa-afp.org/entries/HOL_in_HOL_Deep_Infinity_ZFC.html) and will be in its next release. The theory Main_Results of A1A_1 restates the principal results with minimal hypotheses and without internal notation and is the intended entry point; A2A_2 is read in order, HOL_Universe (the two interfaces) followed by the VV-instantiation. Table 2 indexes the principal results against their formal counterparts. A1A_1 comprises eleven theories, about 7,500 lines and 462 named facts, and imports only the Isabelle distribution; A2A_2 comprises two theories, about 950 lines and 69 named facts, and imports A1A_1 and ZFC_in_HOL. Every proof in both artifacts, including the 23 in A1A_1 that call the smt method, is replayed through Isabelle’s kernel. Software Heritage identifiers follow with the final version, as the journal’s artifact policy asks.

Table 2. Index of the principal results; Infinity_ZFC abbreviates the theory HOL_in_HOL_Deep_Infinity_ZFC of A2\mathcal{A}_2.

resultIsabelle facttheory
Thm 2.3soundness and completenesssound_and_complete_hypsMain_Results (A1\mathcal{A}_1)
Cor 2.4semantic compactnessNK_consequence_compactMain_Results (A1\mathcal{A}_1)
Thm 3.1consistency without infinityconsistencyMain_Results (A1\mathcal{A}_1)
Prop 4.1finite refutationDInf_refuted_finiteNK_Infinity (A1\mathcal{A}_1)
Thm 5.1axiom ⊢\vdash every ∃≥n\exists_{\geq n}axiom_derives_every_finite_cardinalityMain_Results (A1\mathcal{A}_1)
Prop 5.2satisfaction of DInfDInf_sat_iff, DInf_sat_iff_DedekindNK_Infinity (A1\mathcal{A}_1)
Thm 5.3the sentences are consistentfinite_cardinalities_consistentMain_Results (A1\mathcal{A}_1)
Thm 5.4{∃≥n}n⊬\{\exists_{\geq n}\}_{n} \nvdash axiomfinite_cardinalities_do_not_derive_axiomMain_Results (A1\mathcal{A}_1)
Thm 5.5Henkin countermodelhenkin_scheme_refutes_DInfNK_Infinity (A1\mathcal{A}_1)
Thm 6.1completeness of the extensionNK_completeness_DInfHOL_Universe (A2\mathcal{A}_2)
Thm 7.2abstract consistencycon_full_HOL_relHOL_Universe (A2\mathcal{A}_2)
Prop 7.1choice at standard modelsACrel_satHOL_Universe (A2\mathcal{A}_2)
Thm 8.1Harrison-style interface sufficesharrison_hol_universeHOL_Universe (A2\mathcal{A}_2)
Thm 8.2VV-realizationV_harrison_universeInfinity_ZFC (A2\mathcal{A}_2)
Thm 8.3consistency of full HOLcon_full_HOLInfinity_ZFC (A2\mathcal{A}_2)
Thm 9.1type-by-type rank boundrank_D_lt, D_in_Vset_wwInfinity_ZFC (A2\mathcal{A}_2)

Table 2.

Disclosure

The argument, structure and final text of this manuscript are the authors’ own. A generative AI assistant (Anthropic’s Claude) was used, under continuous human direction, for three kinds of tasks: drafting Isabelle proof scripts and their documentation, all of which the authors reviewed, revised and simplified; editorial revision of passages of this manuscript according to the authors’ annotations; and checking the correspondence between the informal statements and the Isabelle statements, as well as bibliographic data. All proofs are machine-checked by Isabelle, and the authors take full responsibility for the content. This work received no external funding, including no subsidized access to tools or software.

References

Otto-Friedrich-Universität Bamberg and Freie Universität Berlin, Germany Email address: [email protected]

Otto-Friedrich-Universität Bamberg, Germany Email address: [email protected]

References

  1. [1]Oskar Abrahamsson, Magnus O. Myreen, Ramana Kumar, and Thomas Sewell, Candle: A verified implementation of HOL Light, 13th International Conference on Interactive Theorem Proving (ITP 2022), LIPIcs, vol. 237, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, https://doi.org/10.4230/LIPIcs.ITP.2022.3, pp. 3:1–3:17.
  2. [2]Peter B. Andrews, General models, descriptions, and choice in type theory, Journal of Symbolic Logic 37 (1972), no. 2, 385–394, https://doi.org/10.2307/2272981.
  3. [3]———, An introduction to mathematical logic and type theory: To truth through proof, 2nd ed., Applied Logic Series, vol. 27, Kluwer Academic Publishers, 2002, https://doi.org/10.1007/978-94-015-9934-4.
  4. [4]Christoph Benzmüller and Peter Andrews, Church’s type theory, The Stanford Encyclopedia of Philosophy (Edward N. Zalta and Uri Nodelman, eds.), Metaphysics Research Lab, Stanford University, 2024, Summer 2024 Edition, https://plato.stanford.edu/archives/sum2024/entries/type-theory-church/
  5. [5]Christoph Benzmüller, Chad E. Brown, and Michael Kohlhase, Higher-order semantics and extensionality, Journal of Symbolic Logic 69 (2004), no. 4, 1027–1088, https://doi.org/10.2178/jsl/1102022211.
  6. [6]Christoph Benzmüller and Daniel Kirchner, A deep embedding of HOL in HOL: Soundness, completeness, consistency, Archive of Formal Proofs (2026), https://isa-afp.org/entries/HOL_in_HOL_Deep.html, Formal proof development.
  7. [7]———, HOL in HOL over a set-theoretic universe: Consistency of NK with infinity and choice, Archive of Formal Proofs (2026), https://isa-afp.org/entries/HOL_in_HOL_Deep_Infinity_ZFC.html, Formal proof development.
  8. [8]Christoph Benzmüller and Dale Miller, Automation of higher-order logic, Handbook of the History of Logic, Volume 9: Computational Logic (Dov M. Gabbay, Jörg H. Siekmann, and John Woods, eds.), North Holland, Elsevier, 2014, https://doi.org/10.1016/B978-0-444-51624-4.50005-8, pp. 215–254.
  9. [9]Christoph Benzmüller, Xavier Parent, and Leender t van der Torre, Designing normative theories for ethical and legal reasoning: LogiKEy framework, methodology, and tool support, Artificial Intelligence 287 (2020), 103348, https://doi.org/10.1016/j.artint.2020.103348.
  10. [10]Asta Halkjær Boserup, Jonathan Julian Huerta y Munive, and Anders Schlichtkrull, Completeness of the Q₀ higher-order logic, Archive of Formal Proofs (2026), https://isa-afp.org/entries/Q0_Completeness.html, Formal proof development.
  11. [11]Mario Carneiro, The type theory of Lean, Master’s thesis, Carnegie Mellon University, 2019, https://github.com/digama0/lean-type-theory/releases.
  12. [12]______, Lean4Lean: Verifying a typechecker for Lean, in Lean, arXiv:2403.14064, 2024, https://doi.org/10.48550/arXiv.2403.14064.
  13. [13]Arthur Charguéraud, The locally nameless representation, Journal of Automated Reasoning 49 (2012), no. 3, 363–408, https://doi.org/10.1007/s10817-011-9225-2.
  14. [14]Alonzo Church, A formulation of the simple theory of types, Journal of Symbolic Logic 5 (1940), no. 2, 56–68, https://doi.org/10.2307/2266170.
  15. [15]Richard Dedekind, Was sind und was sollen die Zahlen?, Vieweg, Braunschweig, 1888.
  16. [16]Javier Díaz, Metatheory of Q₀, Archive of Formal Proofs (2023), https://isa-afp.org/entries/Q0_Metatheory.html, Formal proof development.
  17. [17]Heinz-Dieter Ebbinghaus, Jörg Flum, and Wolfgang Thomas, Mathematical logic, 3 ed., Graduate Texts in Mathematics, vol. 291, Springer, 2021, https://doi.org/10.1007/978-3-030-78339-6.
  18. [18]Asta Halkjær Boserup and Anders Schlichtkrull, Abstract, compositional consistency: Isabelle/HOL locales for completeness à la Fitting, 16th International Conference on Interactive Theorem Proving (ITP 2025), LIPIcs, vol. 352, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, https://doi.org/10.4230/LIPIcs.ITP.2025.8, pp. 8:1–8:20.
  19. [19]John Harrison, Towards self-verification of HOL Light, Automated Reasoning (IJCAR 2006), Lecture Notes in Computer Science, vol. 4130, Springer, 2006, https://doi.org/10.1007/11814771_17, pp. 177–191.
  20. [20]______, HOL Light: An overview, Theorem Proving in Higher Order Logics (TPHOLs 2009), Lecture Notes in Computer Science, vol. 5674, Springer, 2009, https://doi.org/10.1007/978-3-642-03359-9_4, pp. 60–66.
  21. [21]Leon Henkin, The completeness of the first-order functional calculus, Journal of Symbolic Logic 14 (1949), no. 3, 159–166, https://doi.org/10.2307/2267044.
  22. [22]______, Completeness in the theory of types, Journal of Symbolic Logic 15 (1950), no. 2, 81–91, https://doi.org/10.2307/2266967.
  23. [23]John G. Kemeny, Type-theory vs. set-theory, Ph.D. thesis, Princeton University, 1949.
  24. [24]Mark Koch and Dominik Kirst, Undecidability, incompleteness, and completeness of second-order logic in Coq, Proceedings of the 11th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2022), ACM, 2022, https://doi.org/10.1145/3497775.3503684, pp. 274–290.
  25. [25]Ramana Kumar, Rob Arthan, Magnus O. Myreen, and Scott Owens, Self-formalisation of higher-order logic: Semantics, soundness, and a verified implementation, Journal of Automated Reasoning 56 (2016), no. 3, 221–259, https://doi.org/10.1007/s10817-015-9357-x.
  26. [26]Ondřej Kunčar and Andrei Popescu, A consistent foundation for Isabelle/HOL, Journal of Automated Reasoning 62 (2019), no. 4, 531–555, https://doi.org/10.1007/s10817-018-9454-8.
  27. [27]Anatoly I. Mal’cev, Untersuchungen aus dem Gebiete der mathematischen Logik, Matematicheskii Sbornik 1(43) (1936), no. 3, 323–336.
  28. [28]A. R. D. Mathias, The strength of Mac Lane set theory, Annals of Pure and Applied Logic 110 (2001), no. 1–3, 107–234, https://doi.org/10.1016/S0168-0072(00)00031-2.
  29. [29]Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel, Isabelle/HOL: A proof assistant for higher-order logic, Lecture Notes in Computer Science, vol. 2283, Springer, 2002, https://doi.org/10.1007/3-540-45949-9.
  30. [30]Tobias Nipkow and Simon Roßkopf, Isabelle’s metalogic: Formalization and proof checker, Automated Deduction – CADE 28, Lecture Notes in Computer Science, vol. 12699, Springer, 2021, https://doi.org/10.1007/978-3-030-79876-5_6, pp. 93–110.
  31. [31]Lawrence C. Paulson, A mechanised proof of Gödel’s incompleteness theorems using nominal Isabelle, Journal of Automated Reasoning 55 (2015), no. 1, 1–37, https://doi.org/10.1007/s10817-015-9322-8.
  32. [32]———, Zermelo Fraenkel set theory in higher-order logic, Archive of Formal Proofs (2019), https://isa-afp.org/entries/ZFC_in_HOL.html, Formal proof development.
  33. [33]Florian Rabe, Semantics for dependently-typed HOL, Automated Reasoning (IJCAR 2026), Lecture Notes in Computer Science, vol. 16689, Springer, 2026, https://doi.org/10.1007/978-3-032-32592-1_9, pp. 143–160.
  34. [34]Abraham Robinson, Introduction to model theory and to the metamathematics of algebra, Studies in Logic and the Foundations of Mathematics, North-Holland, 1963.
  35. [35]Colin Rothgang, Florian Rabe, and Christoph Benzmüller, Theorem proving in dependently-typed higher-order logic, Automated Deduction – CADE 29, Lecture Notes in Computer Science, vol. 14132, Springer, 2023, https://doi.org/10.1007/978-3-031-38499-8_25, pp. 438–455.
  36. [36]———, Dependently typed higher-order logic, ACM Transactions on Computational Logic 27 (2026), no. 1, 1–54, https://doi.org/10.1145/3771725.
  37. [37]Anders Schlichtkrull, Soundness of the Q₀ proof system for higher-order logic, Archive of Formal Proofs (2023), https://isa-afp.org/entries/Q0_Soundness.html, Formal proof development.
  38. [38]Thoralf Skolem, Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschließlich Zahlenvariablen, Fundamenta Mathematicae 23 (1934), 150–161, https://doi.org/10.4064/fm-23-1-150-161.
  39. [39]Konrad Slind and Michael Norrish, A brief overview of HOL4, Theorem Proving in Higher Order Logics (TPHOLs 2008), Lecture Notes in Computer Science, vol. 5170, Springer, 2008, https://doi.org/10.1007/978-3-540-71067-7_6, pp. 28–32.
  40. [40]Geoff Sutcliffe and Christoph Benzmüller, Automated reasoning in higher-order logic using the TPTP THF infrastructure, Journal of Formalized Reasoning 3 (2010), no. 1, 1–27, https://doi.org/10.6092/issn.1972-5787/1710.

Paper details

vlnc:W_f3v9kba7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents