CS Paper Radar

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

Christoph Benzmüller, Daniel Kirchner

cs.LO math.LO ·submitted 2026-11-13 08:22 UTC · v1

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 $n$ 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_{ω+ω}$; with it, full classical higher-order logic with infinity and relational choice is consistent relative to set theory.

Comment
23 pages, 1 figure. Formal proof artifacts: Archive of Formal Proofs entries HOL_in_HOL_Deep and HOL_in_HOL_Deep_Infinity_ZFC (Isabelle2026). Submitted

Closest papers

Nearest neighbours by meaning across the whole index.

Formalization of Fragments of the Theory of Hereditarily Finite Sets

cs.LO ·2026-09-28 ·Zuzana Haniková, Štěpán Holub
published similarity 0.59
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

The axiomatization of the theory of hereditarily finite sets in first-order classical logic is systematically explored and formalized in Isabelle/HOL. The formalization uses a hierarchy of locales, each corresponding to a fragment of the theory given by a particular collection of axioms. An inductive definition of first-order definable predicates is introduced and used to formalize axiom schemata. Special attention is paid to several equivalent axioms of finiteness, as well as to several equivalent ways of expressing regularity. The work also formalizes several facts about the independence of an axiom from a system of axioms by defining appropriate models.

0.44

Higher Tripos Theory

cs.LO ·2026-10-19 ·Yoshihiro Maruyama
similarity 0.57
Abstract

Tripos theory constructs categorical models of higher-order logic from indexed logical data. We develop higher tripos theory and higher tripos-to-topos construction recovering the classical construction on zero-types through a covering criterion. The higher tripos-to-topos construction yields elementary $\infty$-toposes with closed bounded hierarchies of univalent universes, thus establishing a logical adjunction between $\infty$-triposes and elementary $\infty$-toposes with univalent universes. We also construct a logically conservative higher completion of regular $1$-categories with weak section families and a finite-limit-closed projective cover. This completion preserves original maps, predicates, and existing dependent products, and gives criteria for extending interpretations while preserving logical structure. With strongly inaccessible size bounds, Kleene assemblies instantiate the construction, producing a cumulative hierarchy of univalent universes that classifies every family in the completion and recovering the effective topos as the category of zero-types. We then establish an arithmetical completeness result: for a uniformly computably presented family, the numerical index set for identity with a fixed classifier code is $Π^0_2$-complete. We also construct two inequivalent univalent classifiers with the same global homotopy type: every internal map from one to the natural-number object is constant, whereas the other admits a nonconstant such map. These reconstruction, preservation, and computability results contribute to the higher effective-topos program of Awodey-Emmenegger and Anel-Awodey-Barton.

0.37

Aligning HOL-Light and Rocq libraries formally

cs.LO ·2026-09-21 ·Frédéric Blanqui, Antoine Gontard
top venue similarity 0.57
Abstract

We report on our efforts to translate HOL-Light theorems on HOL-Light types/functions into Rocq theorems on Rocq types/functions. To this end, we developed in Rocq tactics to automate the proofs required for replacing a HOL-Light inductive type or recursive function definition by an equivalent but more idiomatic one in Rocq. We also explain how we replaced the definition of real numbers, as well as a number of mathematical notions like Rn spaces and the definition of limit, hence providing to Rocq users many definitions and theorems in logic and analysis that had not been formalized in Rocq before.

0.60

Nonstandard Axiomatic Semantics

cs.LO ·2026-08-24 ·Patrick Cousot
similarity 0.56
Abstract · ICTAC 2026

Similar to Skolem's nonstandard models of Peano's naturals, we show that axiomatic semantics based on Hoare logic has nonstandard models and so does not specify a unique, well-defined, and formal operational semantics of programming languages. We propose to enrich axiomatic semantics with additional proof obligations to solve this ambiguity problem. These proof obligations are always satisfied for standard trace models so that Hoare logic proofs are unchanged for these standard models.

0.19

Strict Equality in Higher Identity Types: Axioms, Completeness, Decidability

cs.LO ·2026-10-20 ·Keri D'Angelo, Liron Cohen, Luke Serafin, Dexter Kozen
theory similarity 0.56
Abstract

Reasoning about higher identity types uses two equalities, strict equality and equivalence of cells witnessed by a path. Strict equality is a congruence for every operation on cells, but associativity and the identity laws fail for it. Equivalence of cells satisfies those two laws, but it is not a congruence. Representations of higher identity types often conflate equational properties that hold strictly with those that hold only up to a path. We separate the two and axiomatize the former, introducing SEq, an equational theory generated by eleven axioms for strict equality between cells. We prove soundness and completeness for homotopy models, and completeness already over finite CW-complexes. Nine of these axioms form a strongly normalizing rewrite system whose normal forms are unique up to picture equivalence, and the resulting word problem is decidable in exponential time. We also give presheaf models over a cubical base category in which composition arises from a pushout in the base category itself, without requiring Kan filling structure. The same pushout structure provides explicit higher-dimensional witnesses for associativity and the identity laws.

0.38

Proofs Without Nominals: Gödel's Ontological Argument, its Shallow Embedding, and the Open Questions of the Monatshefte Notes

cs.LO cs.AImath.LO ·2026-09-28 ·Christoph Benzmüller
theory similarity 0.56
Abstract · 51 pages. New in v5: the witness criterion and the whole-term condition come apart (a proof with the nominal in a context alone); three open…

The shallow embedding of higher-order modal logic in classical higher-order logic, used in Benzmüller and Scott's Notes on Gödel's and Scott's variants of the ontological argument, reaches beyond the modal object language: its quantifiers range over domains containing the nominals and satisfaction operators of hybrid logic. A proof using one proves a theorem of the embedding, not necessarily of the modal logic. Whether a result is one of the modal logic can be settled by replaying it in an explicit calculus, or, more cheaply and for all results at once, by analysing what the embedding's proofs substitute. Every statement the Notes prove has a proof in the embedding substituting nothing outside the object language, 294 of them explicit. The Notes' own proofs substitute none either; what it flags are terms a prover introduced. A soundness theorem over general models closed under the object language, and a sentence of that language the embedding proves but which fails in such a model, fix what the certificate says. The Notes' three open questions are settled too, without nominals, but by the empty instance of the conjunction axiom, too cheaply to convince. Generalised to Gödel's "any number of summands", the axiom covers the empty conjunction and the singleton. This article restricts it to at least two different conjuncts, a non-degenerate reading of Gödel's footnote, and settles them again without nominals. In effect only the empty conjunction is excluded; the singleton comes back with the other axioms. In one variant the restriction refutes the possible existence of a God-like being; the answers return, with no side condition, once the Notes' non-emptiness clause is confined to Gödel's essence. Every theorem here is verified in Isabelle/HOL and independently in Lean 4, the separating model in its propositional part; the countermodels are Nitpick's, checked by the build.

0.45

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.55
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.49

Compact Quantitative Equational Theories as Monad Restrictions

cs.LO ·2026-10-09 ·Matteo Mio, Colin Riba
published similarity 0.55
Abstract · Conference: MFPS 2026, Ljubljana 2026

Proofs in quantitative algebra are, generally, infinite objects due to the presence of infinitary rules in the deductive apparatus. A quantitative equational theory is called compact if all its consequences are derivable by means of finite proofs, that is, proofs not using any instances of the infinitary rules. This definition is purely logical. In this work we give an equivalent, but categorical, characterisation based on the notion of monad restriction.

0.38