Playground Documentation Challenges Full Docs

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.

BlockA result leaves byCondition
{ … }, importnothing to dono 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 blocksa call of the result as a theoremevery 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 itnone: 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 ga 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, ι := ethe model satisfies S1–S3
type(T = c1 | … | cn) of a theorya call with an enumeration of the call sitethe 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.

▶ Run

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).

▶ Run

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/).

▶ Run

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.

▶ Run

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.