Playground Documentation Challenges Full Docs

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.

▶ Run

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

▶ Run

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 g by its value, reduce, and both sides must be one term. g(x) -> f(x, a) becomes f(x, a) -> f(x, a); g(x) -> a is rejected. So the defining statements are not assumptions; a proof uses them like any hypothesis.
  • Closing the level. A result that mentions g is closed as "g := {x | f(x, a)} in the result", and this means the result with the value in place of g. A result without g leaves as it is. So the theorem above says f(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) stays g(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

▶ Run

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.

ℹ
A definition by unique existence, 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.

SystemDefinitions in the kernel
Lean 4def 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/HOLdefinition 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 Lightnew_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.
MizarA definition comes with its correctness conditions (existence, uniqueness, coherence), which the checker verifies.
MetamathThe 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.