Leaving a Block
How a result proved inside a block is carried out of it, and under which conditions
Overview
Every block of Formall is an assumption: for introduces arbitrary atoms, if assumes
statements, lock assumes axioms, type introduces a type parameter. A result proved inside
is a result under these assumptions. A block is useful only if such results can be carried out of it — and
only under conditions that keep them true. This page lists, for every block, how a result leaves it and what the
kernel checks. The sugar of the language (definitions, subtypes, enumerations) is a combination of these blocks,
so the same table says how to leave a definition or a subtype.
| Block | A result leaves by | Condition |
|---|---|---|
{ … }, import | nothing to do | no assumption: its statements hold in the enclosing block |
for(x) | generalize[| S] (∀-introduction) | the axiom of the quantifier; no assumption between the result and the for |
for(x) if(p(x)) | obtain[| S] (∃-elimination) | the result does not mention x; the fact ∃(p) is visible above |
if(H) | deduce[| S] (⇒-introduction), contradict[| S] | the theorem of the implication; a contradiction under H |
| any path of blocks | a call of the result as a theorem | every atom and type of the path substituted, every if met by a visible fact, every lock axiom realized |
define(f := {a | e}) | automatically, by a call that takes the blocks around it | none: a definition level of the kernel; a result with f is stated of the body (Definitions in the Kernel) |
define(f | T∃!) | a call with f := g, then ∃-elimination over g | a function g satisfying the definition exists: ∃{g | ∀a. φ(a, g(a))} is visible |
type(S) for(ι: [S -> T]) subtype(ι, φ, ∃, ⇒) | a call with a model S := M, ι := e | the model satisfies S1–S3 |
type(T = c1 | … | cn) of a theory | a call with an enumeration of the call site | the type and the values replaced together, value for value; its schemas of distinct values and of cases realized by the label (the package) of the call site's |
An explicit definition is a level of the kernel: the constant with its value (Definitions
in the Kernel). The last three rows are not rules of the kernel. A definition by unique existence is a for
block of the constant with a lock under it whose axiom is the definition; a subtype is a type parameter, a
for block of the embedding and a lock with S1–S3. Leaving them is an ordinary call: the constant is
substituted by something that satisfies its axioms. The condition is always the same — a witness: the
body of an explicit definition, a selector function for define!, a model type for a subtype. Without a witness the
assumptions of the block could be contradictory (no such function, no such type), so nothing may leave it, not even a
statement that does not mention the constant.
An explicit definition
The body is the witness, so the interpreter discharges the definition by itself. A result without the constant
leaves the definition's lock with the call that takes the blocks around it
(generalize[| R], deduce[| R]); in the
certificate it leaves the definition level as it is, by the kernel's own rule (Definitions
in the Kernel). A result that mentions the constant stays inside: outside the definition it would speak of
a constant without a meaning.
Leaving an explicit definition
The full code declares a polymorphic = with reflexivity and the quantifier ∀; in the library they come from logic/equality.fl and logic/quantifiers.fl.
Repository test: tests/13_boundaries/44_generalize_leaves_explicit_definition.fl (and 45 for
deduce).
A definition by unique existence
define(f | T) with T: ∃!{c | φ(a, c)} assumes that f picks the value for
every a. To leave the block, show that such a function exists — by a construction or by the principle of
unique choice, written as an explicit axiom (it is not part of the trusted kernel):
Leaving a definition by unique existence
In the full code: the quantifiers ∀, ∃, ∃! with their rules (the library's logic/uniqueness.fl), unique choice as an explicit axiom AUniqueChoice, and R with unique values (H).
Repository test: tests/08_corpus/experiments/reduction/define_unique_exit.fl.
A subtype
A result about T proved through the subtype S leaves with a model: a type M
and an embedding e for which S1–S3 hold. The subtype may be empty; then the model is an empty type as
well. Formall does not assume that every predicate has a model type (the typedef principle of HOL).
Leaving a subtype with a model
The full code proves Inside through the subtype S of {x: T | p(x)} and then leaves it with the model M, e; ⇒, =, ∀, ∃ are declared at the top (in the library — logic/).
Repository test: tests/08_corpus/experiments/reduction/subtype_exit.fl.
An enumeration, written out
An enumeration is a type, its values as atoms, and two kinds of axiom schemas: distinctness —
two different values of one expression give anything — and exhaustion — what follows from each
value of an expression follows. The refutations of an enumeration (if(X -> red) refute[| …], the lemma of
logic/equality.fl) and the value decide finds are calls of these schemas.
Three colors without the enumeration rules
Only type, for, lock, axiom, if, proofs and calls: the kernel needs no rule of its own for enumerations. The repository test experiments/reduction/enumeration_as_axioms.fl derives the same X -> blue with the built-in enumeration as well.
Why this matters
The kernel is trusted, so it must be small. The richer commands are trusted only through such reductions: each one is shown to be a combination of the core blocks, and each block is shown to be left only with a witness. Every example on this page is a test of the repository, checked by the interpreter and by the independent kernel.