Definitions in the Kernel
What an explicit definition is for the certificate kernel, why it is conservative, and how other systems do it
Overview
An explicit definition define(g := {x: T | e}) introduces a constant together with its value. In the
language it means a new atom and two defining statements, g(x) -> e and
e -> g(x). The certificate kernel (the small independent checker of proofs, see
Steps as Theorems) knows definitions as one of its kinds of context: a
definition level that declares the constant with its value. This page shows the same definition
written with ordinary blocks, what the kernel checks, why nothing false can come from a definition, and how other
proof assistants treat definitions.
The same definition, written with blocks
Here is a definition and a step that uses it:
A definition
In the full code T, f and a are declared above.
For the steps of a proof the definition is the same as a new atom g with a lock whose axioms are the
two defining statements. The following code proves the same statement in the same way:
The same with a for block and a lock
The difference is what the axioms are. In the second program they are assumptions: any statement could
be written there, g(x) -> a as well, and every theorem below is proved only
for a g that satisfies them. In the first program they are true: g is
{x: T | f(x, a)}, and g(x) -> f(x, a) holds as
f(x, a) -> f(x, a). The definition level lets the kernel see this.
What the kernel checks
In the certificate the definition is a level {"define": [g, type, value]}, and each defining statement
is a level {"fact": [name, statement]}:
{"open": {"define": ["g", [[], ["fn", ["T"], "T"]],
[[], ["lam", ["T"], ["app", ["v", "f", []], [["b", 0], ["v", "a", []]]]]]]}}
{"open": {"fact": ["gDef", ["all", "x", [[], "T"],
["red", ["app", ["v", "g", []], [["v", "x", []]]],
["app", ["v", "f", []], [["v", "x", []], ["v", "a", []]]]]]]}}
- The value is checked where the definition stands, before the constant exists: its type must be the type of the constant, and it cannot mention the constant itself (a definition is not recursive).
- A fact must become true when the definition is unfolded: replace
gby its value, reduce, and both sides must be one term.g(x) -> f(x, a)becomesf(x, a) -> f(x, a);g(x) -> ais rejected. So the defining statements are not assumptions; a proof uses them like any hypothesis. - Closing the level. A result that mentions
gis closed as "g := {x | f(x, a)}in the result", and this means the result with the value in place ofg. A result withoutgleaves as it is. So the theorem above saysf(a, a) -> f(a, a)once the definition is closed. - References. A later step that refers to a theorem under the same definition (in the same block,
or in another file that imports the module where it is defined) keeps the constant:
g(a)staysg(a). Anywhere else the kernel unfolds it.
A result therefore leaves a definition by the rule of the definition itself; earlier the certificate builder had to write a call of the result with the body for the constant (Leaving a Block).
Why a definition is conservative
An extension is conservative if everything it proves about the old notions could be proved
without it. A definition is: take any proof that uses g and replace g by its value everywhere.
The facts of the definition turn into steps e -> e, which hold by
reflexivity. Every other step stays valid, because no rule of the kernel looks at what an atom is, only at the
shape of the terms (substituting a term for an atom keeps a proof a proof). What remains is a proof of the same
statement without the definition. This is the classical theorem on definitional extensions (J. Shoenfield,
Mathematical Logic, § 4.6), and it is exactly what the kernel does when it closes the level.
For the same reason a constant cannot be detached from its value. A definition made under for(x)
is about this x; outside the for block a theorem about it says something about the value:
A constant goes with its value
Applied to a, the theorem c -> x gives
a -> a, never c -> a for the old
constant. The language asks the call for the defining statement at the new value,
a -> a, as a statement proved here (Same: a call proves nothing
by itself); the kernel does not even need it, because it unfolds the definition. An early kernel rule for definitions
(of the first proof journal) treated the constant as a fresh atom with global axioms and could be tricked exactly here;
the regression tests tests/13_boundaries/36–41 keep this case closed.
define(f | T∃!), is not of this kind: it has no value, only a property that holds of exactly one thing. It stays a for block with a lock, and a result leaves it only with a function that satisfies the property (Leaving a Block). Leaving it without one would need a principle of description, like THE in Isabelle; that principle is not in the trusted base.How other systems do it
Almost every proof checker has definitions in its kernel. Definitions are the most common extension of a theory, and the kernel has to know that they cannot make a theory inconsistent; otherwise each definition would be one more axiom to trust.
| System | Definitions in the kernel |
|---|---|
| Lean 4 | def adds a constant with its value to the environment; the kernel unfolds it (δ-reduction) when it compares terms, so g f a a = f a a is proved by rfl. |
| Coq (Rocq) | Definition is a global constant unfolded by δ-reduction; a Let inside a Section is substituted when the section closes (ζ). This is the closest relative of our definition level. |
| Isabelle/HOL | definition adds the axiom g ≡ λx. f x a; the kernel accepts it only as a definition (a new constant, no cyclic dependencies) and gives the theorem g_def. |
| HOL Light | new_basic_definition is one of the few primitive rules of the kernel: from a closed term t it makes a constant c and the theorem ⊢ c = t. |
| Mizar | A definition comes with its correctness conditions (existence, uniqueness, coherence), which the checker verifies. |
| Metamath | The exception: definitions in set.mm are ordinary axioms (df-…); that they are conservative is checked by separate tools, not by the verifier. |
The Coq program below closes a section with a Let; the theorem it leaves is stated of the value, just as
a Formall theorem is when its definition closes:
Section Definitions. Variable T : Type. Variables (f : T -> T -> T) (a : T). Let g := fun x : T => f x a. Lemma L : g a = f a a. Proof. reflexivity. Qed. End Definitions. Check L. (* L : forall (T : Type) (f : T -> T -> T) (a : T), f a a = f a a *)
Why Formall builds it in
Formall's kernel is kept small: logic rules, equality, enumerations are schemas and lock axioms, not rules of the
kernel (Steps as Theorems). Definitions were treated the same way, as a
for block with a lock, and this was sound. But it had a price:
- the defining statements were assumptions of the certificate, and the kernel accepts an assumption of any formula; a separate tool had to check, against the source, that each one really was the definition;
- leaving a definition needed a step written by the certificate builder (a call with the body and reflexive realizations) instead of a rule of the block;
- every theorem stated after a definition carried its axioms as premises.
The definition level costs each of the two kernels (Python and C++) about a hundred and thirty lines with their comments: a context entry with a value, a check that a fact is true by unfolding, the binder that closing writes and the rule that keeps or unfolds it in a reference. In return the defining statements are proved, not assumed, and leaving a definition is the kernel's own rule. This is the choice made by Lean, Coq, Isabelle and HOL Light.