Theory Footprint_Checks
theory Footprint_Checks
imports Consistency
begin
section ‹Footprint of the consistency proof›
text ‹A footprint audit for the consistency result ‹nk_consistent›; nothing new is proved
here. The instances ‹consistency_bool_params› and ‹consistency_unit_params› instantiate
the parameter type ‹'p› (BKK's typed constants) --- not the individuals ‹ι›, which the
model makes a singleton --- with the finite types ‹bool› and ‹unit›; they would fail to
type-check if the proof required ‹'p :: infinite›, so no infinite supply of parameters is
needed.
The result is what the introduction calls an @{emph ‹outright›} consistency proof, relative
only to plain Isabelle/HOL: the meta-logic certifies the embedded object logic --- which
carries no axiom of infinity --- by a standard model with finite domains at every type,
using no set theory. The model construction uses no Hilbert choice: the definitions of
theory ‹Consistency› contain neither ‹SOME› nor ‹THE›, and its description
operator selects by definite description (‹THE›, locale @{locale lambda_universe} in
theory ‹Semantics›). The proofs around the model do not avoid choice: the only
explicit use of Isabelle's choice operator before the completeness proof names a canonical
assignment (‹xi0› in theory ‹Semantics›), but a dependency audit over the proof
terms of @{thm [source] nk_consistent} (via \<^ML>‹Thm_Deps.thm_deps›) finds the meta-logic's
choice principles entering through the datatype package, through lemmas about fresh
variable names in the syntax, through the evaluation of abstraction and quantification in
the semantics, and through the soundness proof. The footprint claim is therefore "no
choice in the model", not "no choice in the proof". Theory ‹Footprint_Deps› performs both
checks mechanically and fails the build if either is violated.
The type \<^typ>‹ival› that hosts the model is infinite, as every recursive HOL datatype is.
For the object logic this does not matter: its quantifiers range over the domains
‹cD 1 σ› of the size-one instance ‹k = 1› of the model family of ‹Consistency›, and
each of these is a finite set. The domain of individuals has a single element:
@{lemma ‹en 1 ι = [VI 0]› by (simp add: upt_rec)}. The model therefore refutes every
axiom of infinity, which by definition has no finite models; concretely, a Dedekind-style
axiom demands an injective, non-surjective self-map of the individuals, and a one-element
domain has none. Nor can the model keep two individual constants apart. This is why the
consistency proof needs neither an infinite model nor a stronger meta-theory.
Finally, the kind of statement this is. The meta-logic Isabelle/HOL has an axiom of
infinity; the object logic has none. The meta-level infinity is needed, as far as the
argument goes, only for the syntax, and there only in the form of the natural numbers: the term type, the names of free
variables and the inductively defined set of derivations are infinite, as they must be in
any meta-theory that speaks about derivations. The argument itself uses nothing beyond finite
objects: evaluation in a finite model is decidable, and soundness is an induction over
derivations (a metatheoretic remark, not formalised). Inside HOL there seems no lighter route:
the term type itself exists only by the axiom of infinity, and that axiom states exactly
that some type is Dedekind-infinite, which is all the natural numbers need. The datatype
\<^typ>‹ival› that hosts the model is infinite only because every HOL datatype is; its
domains are finite. So the consistency proof is carried out in a logic with an axiom of
infinity, about a logic without one; it is not a logic proving its own consistency.
G\"odel'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 embeddings of object logics
\<^cite>‹LogiKEy›, arithmetic at the object level is optional; the introduction's paragraph
on the two tiers of consistency says which core of the logic in use is the one certified
here.›
theorem : "¬ (⊢ (❙⊥ :: bool tm))"
by (rule nk_consistent)
theorem : "¬ (⊢ (❙⊥ :: unit tm))"
by (rule nk_consistent)
end