Playground Documentation Challenges Full Docs

Full Documentation

All documentation on a single page for easy searching (Ctrl+F), printing to PDF, or pasting into AI assistants.

Getting Started

↗

Formall Documentation

A formal logic programming language for constructing and verifying mathematical proofs

What is Formall?

Formall is a language for writing and verifying formal mathematical proofs. You define your axioms, declare types and symbols, and build proofs step by step — Formall checks every step mechanically.

Unlike most proof assistants, Formall has no hidden automation and no tactics engine. Every step is written in the text; the one command that writes steps for you (decide) is named in the proof and expand into ordinary commands. Every run can also write a journal of all steps, which an independent checker verifies with four rules — hypotheses, axioms, rewriting and applying a theorem (a call T[…]): contradiction, generalization, calls on quantified facts, implication, equality and enumerations all come down to calls of theorems and axioms the files write (Command Reducibility). What you see is exactly what is verified.

Despite this minimalism, Formall is expressive enough for serious mathematics:

  • Second-order logic — quantify over predicates and functions, not just values
  • Any axiom system — Peano arithmetic, ZFC set theory, or your own foundations
  • Type polymorphism — prove a theorem once for a type parameter, instantiate it with any concrete type by a call T[…]
  • Parametric theorems — the lock/axiom/call mechanism lets theorems accept proof arguments, analogous to how higher-order functions accept function arguments
  • Full reuse — every proved theorem becomes a lemma applicable anywhere by a call

The included library covers propositional logic, quantifiers and equality; Peano arithmetic up to the fundamental theorem of arithmetic; set theory from axioms (the Russell paradox, Kuratowski pairs, and the integers, positive rationals and reals built from sets); ordered fields and completeness, limits and continuity; Hilbert's geometry (incidence and order, synthetically and in coordinates); groups and commutative rings; Cantor's diagonal argument and logic puzzles. Each theory is a module that can be imported or interpreted in another model.

ℹ
Formall verifies proofs, it doesn't find them automatically. You write the proof, Formall checks it. This means every proof is fully transparent — there is no step you did not reason about yourself.

Quick Start

Here's a minimal Formall program that proves a simple logical identity:

Your First Proof

This program defines boolean logic and demonstrates proof by contradiction.

▶ Run

Core Concepts

Types and Atoms

Formall is strongly typed. You declare types with type(...) and atoms (values/functions) with for:

Type declarations

▶ Run

Statements and Proofs

A statement in Formall has the form expression -> expression. The if command introduces assumptions, and a proof <…> derives new statements:

Making statements

▶ Run

Labels for Reuse

Labels let you name and reuse proven statements:

Using labels

▶ Run

Documentation Structure


Basics

↗

Types

Declaring and using types in Formall

Overview

Formall is a strongly-typed language. Every expression has a type, and type mismatches are caught at parse time. Types are declared using the type(...) command.

type(typeName1, typeName2, ...)
typeName1, …
Names of new primary types; the other forms of type (enumerations, subtypes, type variables) are on the type page.

Basic examples

Primary Types

Primary types are the basic building blocks. They represent sets of values (like booleans, natural numbers, or sets):

Declaring primary types

▶ Run
💡
Type names can use Unicode characters like ℕ, 𝕊, 𝔹. This allows mathematical notation in your code.

Function Types

Functions are typed using the arrow notation [Args -> Result]:

for(f: [A -> B]) // Function from A to Bfor(g: [A, B -> C]) // Function taking A and B, returning Cfor(h: [A, [B -> C] -> D]) // Higher-order function taking A and [B -> C] (function taking B, returning C), returning D

Declarations of functional type atoms

▶ Run

Type Scoping

Types are scoped — they are visible inside the type() scope:

Type scoping

▶ Run

Type Polymorphism

Formall supports type polymorphism in two ways. A type parameter of a theorem: declare type(T) inside the theorem, prove it, and instantiate it with a concrete type by a call (see Calls — Type Parameters). And a type variable: a type whose name starts with an apostrophe, type('α). An atom whose type contains 'α is polymorphic — one atom for all types, its type is inferred at every application (as in HOL and Lean). A statement with 'α in the types of its bound atoms is a schema — true for every type: calls and the search for conditions instantiate 'α by matching.

A polymorphic quantifier and an axiom schema

Atoms in Formall are variables (for means «for any»), so a polymorphic atom does not claim that a type is inhabited: empty types stay sound.

▶ Run

Why Types Matter

Types in Formall serve several purposes:

  • Safety — prevent meaningless expressions like applying a boolean function to a natural number
  • Clarity — make the domain of discourse explicit
  • Verification — enable automatic checking of proof steps
  • Quantification — for and constructors quantify over specific types
ℹ
Unlike some proof assistants, Formall doesn't have a built-in type hierarchy. All types are independent unless you define relationships between them.

↗

Atoms

Values, functions, and named entities

Overview

Atoms are the named entities in Formall — constants, variables, and functions. They are declared using the for command and always have an associated type.

for(atomName: type)for(atomName1, atomName2: type)for(atomName1: type1; atomName2: type2)for(atomName: [argumentTypes -> resultType])
atomName
The name of the atom: letters, digits, any non-ASCII symbols (∀, ➕, 𝔹) and _ ! $ % & ' = ? @ ` ~ + ^ - (not before >) and *; not spaces or the characters of the syntax ( ) [ ] { } < > , : ; | ". . is reserved for namespaces.
type
A declared type, or a function type [argumentType1, argumentType2 -> resultType].

Basic examples

Simple Atoms

Simple atoms represent values of a given type:

Declaring simple atoms

▶ Run

More compact declaration

▶ Run

Function Atoms

Functions are atoms with function types. They can take arguments and return values:

Function declarations

▶ Run

Calling Functions

Functions are called with parentheses. Constructors create anonymous functions using {varName: Type | expression}:

Function application and constructors

▶ Run

Atom Naming

Atom names can include letters (including Unicode: Greek, Cyrillic, mathematical symbols like ×, =, ∈, ➕), digits (in any position), and underscores. However, the symbols +, -, *, ^ are reserved for label operations and cannot be used in atom names.

Naming examples

▶ Run

Scoping Rules

Atoms are scoped to their declaration for command. Inner for can shadow outer atoms:

Atom scoping

▶ Run
⚠
When an atom is shadowed, the outer atom is completely inaccessible in the inner scope. Choose unique names when you need both.

Atoms vs Labels

Don't confuse atoms with labels:

  • Atoms — declared with for, have types, appear in expressions
  • Labels — declared with +, store statements, used in proof commands

Atoms vs Labels

▶ Run

↗

Expressions

Building complex terms from atoms

Overview

Expressions in Formall are built from atoms through function application. Every expression has a type, determined by its structure.

Basic examples

Atomic Expressions

The simplest expressions are just atoms:

Atomic expressions

▶ Run

Function Application

Apply a function to arguments with parentheses:

Function application

▶ Run

Constructors

Create anonymous functions (predicates) with constructor syntax {varName: Type | expression}:

{boundAtomName: type | expression}

A function applied to a single constructor needs no parentheses: ∀{x: ℕ | p(x)} is ∀({x: ℕ | p(x)}). Quantifiers are written this way: the braces show where the quantified formula ends, so no precedence rule is needed for it. Nested one-place quantifiers are printed together: ∀{x, y: ℕ | P}. The interpreter prints this form too (with --prefix — the form with parentheses).

This is only a way of writing: ∀ still takes one argument, a function of one variable, and ∀{x, y: ℕ | P} is ∀{x: ℕ | ∀{y: ℕ | P}} — the parser builds the nested form and L[a, b] removes the quantifiers one at a time. Nothing has to be declared for it: the shorthand applies to any atom f: [[T -> R] -> R] whose argument is a function into the same type R as its result (so f{y | P} can be the body of another f): ∀, ∃, ∃!, a sum ∑: [[ℕ -> ℝ] -> ℝ]. It does not apply to sup: [[ℝ -> 𝔹] -> ℝ] or to a function of two arguments, where {x, y | e} is a function of two variables (define(f := {a, b: T | e})).

⚠
Nesting is what the shorthand means for every such atom, including ∃!: ∃!{x, y: T | P} is ∃!{x: T | ∃!{y: T | P}} («exactly one x for which there is exactly one y»), which is not the same as «exactly one pair (x, y)».

Constructor syntax

▶ Run

Lexical Rules

  • A name (atom, type, label, command) is a run of letters, digits, _!$%&'.=?@\`~ and any non-ASCII characters: ➕, ∀𝔹, L➕1, =Color are single names. In expressions — the terms of commands, calls and proofs — an atom name may also contain + * ^ - (a-b is one name, a - b an operator): - before > is the arrow ->, * right after | is the hint |*.
  • Reserved in expressions: ( ) , ; { } | [ ] : < >, spaces, " and comment starts //, /*.
  • Spaces and comments (// … to the end of the line, /* … */) separate tokens; they cannot occur inside a name. Comments are allowed inside expressions too.
  • In an expression a space is kept only between two name characters, where it separates names: a ∘ b is three names, a∘b is one. Elsewhere spaces are insignificant: ∀{x: T | p(x)} and ∀ { x : T | p ( x ) } are the same.
  • Unicode spaces (no-break space U+00A0, thin space U+2009, ideographic space U+3000 …) count as ordinary spaces, so text pasted from a word processor reads as it looks. Invisible characters — zero-width space U+200B, joiners, soft hyphen, bidirectional controls U+202A–U+202E, U+2066–U+2069, line separators U+2028/U+2029 — are an error anywhere: otherwise a​b and ab would be different names that look the same.
  • Positions in messages are line:column, the column counted in Unicode characters.

Proofs

A proof is an expression in angle brackets; the inner brackets mark the places to rewrite:

<expression>

Inside <...>, the system searches for matching statements and substitutes their right-hand side:

Prove syntax

▶ Run

Label Hints in Prove

Use <expr | Label> to specify which statement to use for a substitution when there are multiple matching ones:

Label hints

Outer angle brackets are not needed — ➕ is not being substituted.

▶ Run

Expression Equality

Two expressions are considered equal in Formall if they are the same atom, function applications with equal functions and equal arguments, or constructors with alpha-equivalent bodies (same structure up to variable renaming).

Alpha-equivalence of constructors

▶ Run
❗
Formall expressions are purely syntactic — there's no evaluation or simplification. ➕(1, 1) and 2 are different expressions unless you prove they're equal.

↗

Functions and λ

Lambda terms, α, β, η, currying, binder notation and Miller patterns — what Formall does and does not do

Overview

Formall terms are the terms of the simply typed λ-calculus: atoms, applications f(a, b) and anonymous functions {x: T | e} (written λx. e elsewhere). The theory of λ-calculus names several ways in which two terms can be «the same»; each is called a reduction or an equivalence and has a Greek letter. This page explains each one on the smallest examples and says whether Formall does it automatically, does it on request, or not at all.

NameWhat it saysIn Formall
α{x | p(x)} is {y | p(y)}: bound names do not matteralways, in every comparison
β{x | e}(a) is e with a in place of xalways, when a term is built
η{x | f(x)} is fno; a fact or the extensionality axiom gives it
δa defined name is its definitionon request: define gives a statement, a hint unfolds it
curryingf(a, b) is f(a)(b)no: [A, B -> C] and [A -> [B -> C]] are different types

α: names of bound variables

In all{x: T | p(x)} the name x is only a place holder. Renaming it gives the same expression, so a fact written with x is found for a formula written with y.

α-equivalence

▶ Run

When a substitution would put a free name under a binder with the same name, the bound name is changed in print (n′, 𝓋1), so that the meaning stays the same. This is called capture-avoiding substitution.

β: applying a function

A λ applied to an argument is replaced by its body with the argument substituted. Formall does it at once, every time a term is built (after parsing, substitution in a call, a hint): you never see a term like {x | e}(a) in statements.

β-reduction when a term is built

▶ Run

The same happens when a definition is unfolded: the hint <double> replaces the atom by its λ, and the application is reduced.

Unfolding a definition (δ) followed by β

▶ Run

η: a function is the λ of its values

η says that {x: T | q(x)} and q are the same function. Lean, Coq and Agda build this into comparison; Isabelle keeps terms η-short. Formall does not: the two are different expressions, and a fact about one is not found for the other.

No η: this fails

▶ Run

Expected error: No matching statement found for expression substitution

Two ways around it. Write the same form that the facts use (most library code does so). Or obtain the η statement as a fact: it follows from function extensionality (logic/extensionality.fl, «functions with equal values are equal»), and then it rewrites like any statement:

η from a fact

▶ Run

Formall never identifies the two forms by itself: a call infers a predicate η-reduced (∀(p) from generalize[| S] under for(x) with p(x) -> ✔), and where ∀{x | p(x)} is wanted, the predicate is written: generalize[{x: T | p(x)} | S].

Currying

A function of two arguments can be a function of a pair ([A, B -> C]) or a function returning a function ([A -> [B -> C]], «curried»). Formall has both types and keeps them apart: there is no partial application f(a) of a two-place f.

Two kinds of two-argument functions

▶ Run

No partial application: this fails

▶ Run

Expected error: Too few arguments

Write the one-argument function as a λ instead:

A λ in place of f(a)

▶ Run

Why functions are not curried

HOL, Lean and Coq identify the two types: there every function takes one argument, and f(a) of a two-place f is simply a function. Nothing in the logic forbids that. Formall keeps the number of arguments in the type on purpose:

  • A forgotten argument is an error where it is forgotten. With currying, f(a) where f(a, b) was meant is not wrong — it is a function. The mistake surfaces later and elsewhere, as a type mismatch far from the place, or not at all: in the failing example above, h(f(a)) would be accepted and mean something the author did not write.
  • Every subterm is a term someone wrote. In a curried f(a, b) the piece f(a) is a subterm too. A hint, a chain step or argument inference that rewrites functions would also find these partial applications: more places to rewrite, more ambiguous hints, and the pattern p(x, y) of inference would have to be matched one argument at a time.
  • Operations and tables stay whole. a + b is one application of + to two arguments; the truth tables of decide (∧(✔, ❌) -> ❌) list whole applications. Curried, each would be a chain of one-argument applications that printing has to fold back.
  • Nothing is lost. A partial application is one λ: {y: T | f(a, y)} says exactly which argument is left open, and it is also the only way to leave open the first argument ({x: T | f(x, b)}), which currying does not give either.

Calls of proofs, on the other hand, are curried: there a partial call is useful and cannot be confused with anything. The parameters of a theorem are a list — its for atoms, then the quantifiers of its conclusion — and a call may give them all at once or a few at a time: T[b][a] is a call on the result of T[b], and states the same as T[b, a]. Nothing makes it so on purpose: the result of a call is again a statement that can be called. Partial application of a proof is how a theorem becomes a fact of the place: T[b] can be named once and its quantifiers given later (see Calls).

Curried calls: T[a][b] is T[a, b]

▶ Run

Binder notation f{x, y | P}

A function applied to one λ needs no parentheses: ∀{x: T | p(x)} is ∀({x: T | p(x)}). Several variables are a shorthand for nested binders: ∀{x: A; y: B | r(x, y)} is ∀{x: A | ∀{y: B | r(x, y)}}. It applies to any atom f: [[T -> R] -> R] whose argument returns the same type R as f itself (so that f{y | P} can be the body of another f): ∀, ∃, ∃!, a sum ∑. With a polymorphic quantifier (∀: [['α -> 𝔹] -> 𝔹]) the variables may have different types; each nested ∀ gets its own. It does not apply to sup: [[ℝ -> 𝔹] -> ℝ], and for a function of two arguments {x, y | e} is one λ of two variables. See Expressions.

Higher-order matching and Miller patterns

To infer the arguments of a theorem, a call matches its conditions with visible facts. When the unknown is a function, matching is «higher-order», and in general it has many solutions. A Miller pattern is the good case: an unknown function applied to distinct bound variables, like P(x) under {x | …}. Then there is exactly one solution: P is the λ over those variables of whatever stands in their place.

A Miller pattern: P is inferred as a λ

▶ Run

An unknown applied to an ordinary term, like P(a), is not a pattern: against p(c) both P := p, a := c and P := {y | p(c)} fit. Formall then matches first-order, by the head:

Not a pattern: matched by the head

▶ Run

A third case is an unknown applied to a term built from bound variables, like P(ι(n)) under ∀{n | …}: every occurrence of that term becomes the variable, again the only solution. When inference is not unique, the call asks for the argument (P := …) or a fact label. Inference only chooses; the conditions are checked afterwards as usual (calls). Hints of proofs (<e | T>) match first-order only, without Miller patterns.


↗

Statements

The fundamental unit of proof

Overview

A statement in Formall has the form expression -> expression. It asserts that within the current context, the left expression can be replaced by the right expression.

leftExpression -> rightExpression
leftExpression
What may be replaced.
rightExpression
What replaces it: wherever leftExpression occurs, it can be rewritten to rightExpression. A truth is a statement with a true value on the right: P -> ✔.

Basic examples

With if

Introduce statements as assumptions:

if statements

▶ Run

With prove

Derive statements by substitution:

prove statements

Note: outer angle brackets around f are NOT needed since f itself is not being substituted.

▶ Run

Statement Semantics

A statement A -> B means: in the current proof context, A can be replaced with B. This is not logical implication — it's closer to "evaluates to" or "equals". To express logical implication, use a function:

Equality vs Implication

▶ Run

Statement Sources

Statements can come from: if (assumptions), proofs <…> (derived by rewriting), calls T[…] (theorems and quantified facts applied to values; taking their blocks — lifted to universals, flipped assumptions), and axiom (conditional axioms).

Statement Visibility

Statements are visible inside the scope where they were created. When that scope closes, they are no longer accessible:

Statement scope

▶ Run

Chained Substitutions

With nested angle brackets, prove chains substitutions:

Chains

▶ Run
ℹ
Formall statements are one-directional. A -> B does not imply B -> A. To express bidirectional equality, you typically prove both directions separately.

↗

Scopes

Scope structure, braces, chaining, and bare blocks

Overview

Formall code is organized into nested scopes. Five commands create scopes: type, for, if, lock, and rule. Every declaration and proof result is scoped to the scope where it was delivered.

Braces Are Optional

A scope-creating command always creates a scope, whether or not you use curly braces { }. Braces are just syntax for grouping multiple commands into one scope. Without braces, the scope contains only the next command (and its scope). These two forms are equivalent:

With and without braces

Both forms produce exactly the same scope tree. Braces simply let you put more commands inside a scope.

▶ Run
ℹ
This is the same rule as in C-like languages: if(x) if(y) f(); is equivalent to if(x) { if(y) { f(); } }.

Chaining

Without braces, scope-creating commands naturally chain — each one wraps around what follows. The chain ends when something that opens no scope — a proof, a call — is done, or when a semicolon ; is encountered:

Chaining

▶ Run

As in C, a semicolon after a statement ends the whole chain: in for(…) if(…) <…>; the ; closes the proof, and with it the if and the for.

Declarations

A chain that consists only of scope commands (type, for, if, lock, rule, import) and ends with ; is a declaration. It lasts until the end of the enclosing block or file, like int x; in C: later semicolons end only their own statements. A chain left open at the end of a file is a declaration as well.

Declarations

▶ Run

A declaration made inside a block ends with the block. This is how a file declares its language once and then states its theorems at the top level — and how import works.

Labels before a chained command apply to that command:

Labels on chained commands

▶ Run

Comma-separated Commands

Non-scope commands can be separated by commas within the same scope. Each command executes independently:

Comma-separated commands

▶ Run
⚠
Scope-creating commands (type, for, if, lock, rule) cannot be comma-separated. They must be chained or placed in their own scopes.

Bare Blocks

Curly braces can be used without any command, creating an anonymous scope. Anything declared inside is not visible outside:

Bare block

▶ Run

Scope Hierarchy

Scopes form a tree. Each scope may contain child scopes. This tree determines:

  • Visibility — atoms, labels, and rules are visible in their declaring scope and all descendants
  • Statement access — statements are accessible from the scope where they were delivered and from nested scopes
  • Label scope visibility — when reading a label, only statements on the path from the current scope up to the label's declaration are included (see Labels)
  • Boundary rules — a call that takes the blocks its proof stands in takes for and if only, never a type, lock or rule

↗

Shadowing

The later and the inner hide the earlier and the outer

One rule

When Formall has to choose among several visible things that fit, it takes the nearest: a later one hides an earlier one in the same block, and one in an inner block hides one in an outer block. It is the rule of local variables in programming languages, and it is the same for names, for the facts a proof substitutes, and for the facts a call finds for the conditions of a theorem.

The order of the search is fixed: the current block from its end, then the enclosing block from its end, and so on outward to the top level of the file and the modules it imports. A label given explicitly comes before all of them.

ℹ
Shadowing only chooses. Whatever is chosen is then checked as if written by hand, so soundness never depends on the choice; a label or an argument always reaches a fact that is hidden.

Names

An inner for hides an atom of the same name declared outside (Atoms):

An inner atom hides an outer one

▶ Run

Facts in prove

Without a label, <e> takes the first statement with left side e in the search order. Other statements about e are not an error: in a proof by contradiction the hypothesis X -> false of the inner if stands beside the outer fact X -> true, and the hypothesis is the one meant.

The nearest fact

In the full code the outer if carries the label X1.

▶ Run

Conditions of a call

A theorem's if conditions are patterns; a call matches them against the visible statements to infer the arguments not given (calls). When the conditions can be met in several ways, each way uses one statement per condition, and one way shadows another when each of its statements is the same or nearer, at least one nearer. The ways nobody shadows must give the same result. Two conditions may take the same statement, and the names of the theorem's parameters play no part:

Each condition takes its nearest fact

Unique is an axiom of a lock here only to keep the example short; a uniqueness theorem is applied the same way.

▶ Run

When neither way shadows the other — one is nearer in one condition and farther in another — the call stops and shows both. Here P := A uses the earlier ⇔(A, B) -> ✔ and the later A -> ✔; P := C the other way round:

Neither choice shadows the other

A fact label or an argument such as P := A settles it.

▶ Run

Expected error: Ambiguous arguments of the call

In other systems

Lean's assumption takes the latest matching hypothesis of the local context, and Isabelle's assumption tries the premises in turn; for one condition this is the same rule. Formall extends it to several conditions at once without preferring any of them, so an ambiguity that depends on the order of conditions is reported instead of being decided silently.


↗

Labels

Naming and managing collections of statements

Overview

Labels in Formall serve as named references to collections of statements. They are used to store proof results and pass them on: to calls T[a | L], as hints of proofs <e | L>, to commands like generalize and contradict.

Declaration and Definition

Combined Declaration and Definition

Use +Name: before a command to both declare and define in one step:

Declaration + definition

▶ Run

Module-level declaration: T::

The most common case — a theorem proved deep inside for and if blocks, whose label must live at the top of the file — has its own form. T:: declares the label at the top level of the current file (exactly where +T; would stand before the statement that contains the definition) and defines it here, like theorem in Lean. All for and if between the top level and the definition become the theorem's parameters and conditions. T:: on a label that is already declared is an error (define it with T:), and an undeclared T: is still an error, so a typo never creates a new theorem silently. +T; stays for other levels — for example, a label declared inside a hypothesis block.

Module-level declaration

▶ Run

Forward Declaration

Declare a label with +Name; before defining it later. Use Name: (without +) to add statements to an already declared label. This is useful when the definition happens inside a nested scope but the label must be accessible outside it:

Forward declaration

▶ Run

Delivery Scope

A label placed on a command captures the result at the delivery scope of that command. For most non-scope commands, delivery is the current scope. A call that takes the blocks its proof stands in is special: contradict[| S] delivers above the if it closes, generalize[| S] above the for it takes. Scope commands (if, rule) deliver into themselves.

CommandDelivery scopeBoundaries
forN/A (no label allowed)—
ifInto itself—
type, lock, ruleInto itself (scope marker)—
proofs <…>, calls T[…], axiom, +-*^Current scope—
contradict[| S], a call taking an ifParent of the if takenfor, type, lock, rule
generalize[| S], a call taking a forParent of the for takenif, type, lock, rule
ℹ
The scope of a label is determined by where its command delivers its result, not by where the +Label: syntax physically appears. For example, +L: contradict[| …] places the label in the parent of the if the call closes.

Since such calls deliver to a different scope, labels on them capture results at those delivery scopes:

Labels at different delivery levels

▶ Run

Since generalize[| …] delivers to the parent of the for it takes, you can pass a proof directly to avoid needing a separate label inside the loop:

generalize delivers above for

▶ Run

Scope Visibility

Labels follow scoping: a label is accessible in the scope where it was declared (and in all nested scopes). When that scope closes, the label is no longer accessible.

Whenever a label's statements are read — by a call, a proof hint, label commands, or any other operation — statements are filtered by scope visibility. Only statements whose definition scope lies on the path from the current scope up to the label's declaration scope are included. Statements from sibling branches of the scope tree are foreign and are excluded (with a warning).

Scope filtering

Collected holds statements from two sibling if branches. Inside the second if, only its own branch's statements are visible.

▶ Run

Using Labels with prove

Inside a proof, you can specify which label to use for a particular substitution using the <expr | Label> syntax:

Labels in prove

▶ Run

Lock Labels

When a label is placed on lock(), it can be used as the first argument of axiom. See lock() and axiom for details. Here is a complete example:

Lock label with axiom

▶ Run

Undeclaration and Undefinition

Two operations for removing label data:

  • -Name; (undeclaration) — removes the label entirely; any subsequent use causes an error. The label is searched upward through all parent scopes, so you can undeclare a label from inside a nested block.
  • Name-; (undefinition) — clears the label's statements but keeps it declared for later reuse

Undefinition and undeclaration

▶ Run

Since undeclaration searches upward, it can be used to remove visibility of labels declared in outer scopes. A common use case is sealing a lock() after all axioms have been defined:

Sealing a lock via undeclaration

After -𝒜;, no new axioms can be added to this lock, but existing axioms and theorems still work.

▶ Run

Augmentation

By default, redefining a label (L: cmd) clears all its statements in the current scope and replaces them. With an augmentation postfix, you control how new statements combine with existing ones:

  • L+: cmd — union: adds new, skipping duplicates
  • L-: cmd — subtract: removes matching statements
  • L*: cmd — intersect: keeps only statements present in both
  • L^: cmd — symmetric difference: XOR of the two sets
⚠
Augmentation is not allowed during initial declaration (+L+: cmd is an error). Declare and define first, then augment.

All four augmentation operations

▶ Run

Accumulating across scope branches

The L+: postfix is especially useful for collecting results from different scope branches. Plain L: cmd would fail because it tries to clear statements from foreign scopes:

Accumulating with Label+: across scope branches

▶ Run

Duplicate Statements

Statement equality in labels considers both content and scope. Two statements with identical expressions are equal only if they were defined in the same scope. This affects all set operations and augmentation.

Defining a Label with Another Label

A label name is a proof — after | of a call, of a proof hint or of a command — and so it is where a statement stands: C: H; defines C with the statements of H visible here, as C: +(H); does. As every reading of a label, it keeps only the statements on the path to here (see Scope Visibility).

A copy stands where C is declared. That decides which atoms are parameters of its statements — the atoms of the blocks between a statement and the declaration of its label. A theorem declared at the top of a file takes the for atoms of its blocks as parameters; its copy declared inside those blocks takes none of them: it is the statement as a fact of this place.

A copy of a label is a fact of its place

▶ Run

A proof gives its statements to whoever takes it: written as a statement, to the block; as an argument, to the command that takes it; in a hint, to the hint. A label name alone (H;) is +(H); written as a statement: it gives the block the statements of H visible here — they are its facts already, so nothing is added, and the interpreter warns. See Label Commands for +, -, *, ^.


↗

Proofs <…>

Deriving a statement by rewriting marked places

Overview

A proof is an expression in angle brackets: <and(<P>, <Q>)>. Inner brackets mark the places to rewrite; each is replaced by the right side of a visible statement whose left side it is. The result is a new statement: its left side is the expression as written, without the brackets, its right side — the expression after all rewrites (and(P, Q) -> true).

<expressionWithMarks><expressionWithMarks |> // the top is not rewritten<…<subexpression>…> // a rewrite point: any visible statement whose left side is the subexpression<…<subexpression | hint1, hint2>…> // only these hints<…<subexpression |* hint1, …>…> // rewrite inside repeatedly while a hint applies<term0 -> term1 | hint1 -> term2 | hint2> // a chain: every term written
expressionWithMarks
The expression to start from, with the places to rewrite marked by < >; it becomes the left side of the proved statement, and the result of all rewrites — the right side. Several proofs under one label: +(<a>, <b>).
subexpression
The part of the expression to replace; brackets nest, the innermost is rewritten first.
hint1, …
What may justify the rewrite — any proof, as after the bar of a call (below): a label with statements (a fact a -> b, an equality =(a, b) -> ✔ in either direction, a quantified fact — instantiated by matching), a theorem (its parameters inferred from the subexpression: <∈(t, ∪(a, b)) | L∈∪>), a call T[a], a proof <…>, a command: decide() — the value of the place by truth tables.
term0 -> term1 …
A chain: each term is written out, the step from the previous term is justified by the hint after it; the interpreter finds where the rewrite happens. The chain proves only the rewrite term0 -> termN; when the equality of its ends is needed, the lemma L=ByRewrite of logic/equality.fl states it: L=ByRewrite[| <term0 -> … -> termN>].

Properties

Produces
A statement: the expression as written -> the expression after the rewrites
Delivery & Label
Into the current scope. A label on the proof (L: <…>) holds the derived statement at this scope.
Creates scope
No.
Mechanism
Reads the expression, finds for each marked place a statement whose left side it is (the hint labels first, then the current block from its end, then the enclosing blocks — shadowing), and replaces the place with the right side, innermost places first. The brackets are then removed: the expression as written becomes the left side of the new statement, the fully rewritten one its right side. In the journal of the interpreter and in the source map of the certificate the step is named proof.

Basic examples

Inside <…>, Formall searches for a statement whose left side is the marked expression and puts its right side in place:

A first proof

▶ Run

Details

After a bar come the labels allowed to justify a rewrite: <x | H>. A bar with nothing after it, <t |>, rewrites only the marked places inside t and leaves its top as it is.

A proof is not a command but a form, like a label: it stands wherever a statement may come from — alone (<…>;), under a label (L: <…>), as a fact passed to a call (T[| <…>]), as the proof of a call that takes its blocks (contradict[| <…>]). It never assumes anything: every rewrite is justified by a statement already proved or assumed in this place.

How Substitution Works

  1. Find a statement X -> Y whose left side X is the expression in <…>
  2. Replace <X> with Y
  3. Process nested <…> from the inside out
  4. Create a new statement: original expression -> final result

Substitution steps

▶ Run

Label Hints

Use <expr | Label> to specify which statement to use when multiple match:

Label hints

Outer angle brackets are not needed around ➕ because it is not being substituted.

▶ Run

Without hints, Formall searches all visible statements starting from the innermost scope.

Nested Substitution

Angle brackets can be nested for complex chained substitutions:

Nested substitution

▶ Run

Chained Substitutions

Chained substitution

▶ Run

Several proofs together

Each proof derives one statement. Several proofs are collected by the label command + — under a label, or as one fact passed to a call:

Two proofs at once

The same as two proofs written one after the other; +(…) only lets them stand where one fact is expected.

▶ Run

A proof as an argument

A proof can be stored in a label or written directly where a command expects a statement:

A proof inside contradict

▶ Run

Rewriting with a theorem

A label hint may name a theorem — a label whose statements were proven for arbitrary atoms. A theorem hint is a call of the theorem at this place: the left side of the theorem statement is matched against the expression, and the atoms (and types) found are its arguments; the call does the rest — infers an atom that does not occur in the left side from the conditions (if on its path), over all conditions together, checks that they hold here, and asks for the axioms of a lock on the path to be assumed here. This is rw of Lean: one step instead of a call T[…] followed by a proof. The parameters of a theorem are its for atoms, then the quantifiers of its conclusion (calls), so a theorem whose conclusion is ∀{x: N | =(⊕(x, c), x)} -> ✔ rewrites ⊕(a, z) to a: c := z and x := a are both found in the term, as by T[z, a].

A theorem as a rewriting rule

A hint passes no realizations: a theorem with a lock on its path is used this way only inside that lock, where its axioms are assumed; elsewhere call it, T[… | R], with a realization R.

▶ Run

Hints are proofs

After the bar of a proof stands what stands after the bar of a call: proofs. A label is the simplest one; a call T[a], another proof <…> or a command may stand there too, and the statements it gives justify the rewrite. A hint is a value: it is proved where the bracket stands, and what it gives is not delivered into the block — only the outermost bracket delivers its statement.

A command whose expression is not written takes the place of the hint, as a call T[] infers what is not written: <e | decide()> decides e by the truth tables of its connectives, <e | decide(| H)> from the facts of H first (<e | decide(| H;)> — only them). In a chain the place of a step is found only after the hint, so there the expression is written: <t0 -> t1 | decide(t0 | H)>.

Hints that are proofs

▶ Run

Rewriting with a quantified fact

A hint may also name a fact with a quantifier, ∀{x: nat | P} -> true, when a notation("apply" | …) for the quantifier is visible. The expression is matched against the body P with x as an unknown, and is rewritten to the rule's value: no separate call H[t] is needed before the proof. Nested quantifiers are removed one by one. This is simp [h] in Lean for h : ∀ x, P x; the typical use is reflexivity — <=(t, t) | Reflexive>.

A quantified fact as a hint

▶ Run

Chains of rewritings

A bracket may hold a chain: <t0 -> t1 | H1 -> t2 | H2 -> … -> tn>. Every next term is written out, and the hint after it justifies the step. The interpreter finds the place where t1 differs from t0 and checks that a single rewriting of that subexpression by H1 gives exactly t1; the value of the bracket is the last term. A step without a hint is justified by any visible statement. This is calc in Lean and also … finally in Isabelle: the reader sees every intermediate term, and the writer does not mark the rewritten subterm with its own brackets.

Because the result of each step is written, it also decides what a hint alone could not: the direction of a rule kept in both directions under one label, the place among several occurrences, and parameters that occur only on the right side of a theorem (x -> plus(x, zero) rewrites a with x := a, found from the next term).

A chain of rewritings

In library/algebra/group.fl of the repository every group identity is one chain: <=(<∘(a, ⁻¹(a)) -> ∘(e, ∘(a, ⁻¹(a))) | LeftId -> … -> e | LeftInv>, e) | A=Reflexive>.

▶ Run
ℹ
Every statement of a hint label is tried at e — a fact as it stands, an instance of a quantified fact, an equality either way, a theorem. A single hint <e | H> must rewrite e in one way: statements giving the same result are fine, different results are an error (Ambiguous hint). In a chain the next term is written, so a label with several matching rules is fine there.

A step up to associativity and commutativity

Moving terms around a sum — a + b + (c + d) to d + (c + a) + b — is many steps by associativity and commutativity, each written out. A step with an asterisk, -> t′ |* A, C, says «t′ is the previous term rearranged by the laws of these labels». The interpreter reads the laws from the labels — f(f(a, b), c) = f(a, f(b, c)) makes f associative, f(a, b) = f(b, a) commutative (as facts under ∀ or as theorems) — checks that both terms have the same normal form, and goes from one to the other by single steps of these laws, each checked like a written step. So nothing new is trusted: the log shows the single steps, and the kernel checks them. This is abel / ring_nf in Lean and ac_simps in Isabelle, limited to rearranging.

Rearranging a sum

With an associative but not commutative operation (a group) |* Assoc only moves brackets; with several operations each one obeys only the laws given for it: x × (y + z) -> (z + y) × x |* MulComm, AddComm. In the limits of sequences of the repository (library/analysis/sequences.fl) this replaced 11-step chains by one line each.

▶ Run

Normalizing both terms

The labels of a |* step may also contain other rules. Labels that state no associativity or commutativity law then rewrite both terms everywhere, left to right, as <e |* L> does (when several rules apply to a subexpression, the first one in label order is taken). A law f(a, g(a)) = e together with f(a, e) = a cancels an operand a against g(a′) when a′ equals a up to the A/C laws, and drops operands e. Finally the two normal forms are compared up to associativity and commutativity. The path between the terms again consists of single steps by the same labels, so the kernel sees ordinary rewrites. This proves polynomial identities without copying expanded forms: it is close to simp only [...]; ac_rfl in Lean, though not a full ring (no numerals, no collecting a + a into 2 × a). If the normal forms differ, the error shows both.

A difference of squares

In the repository the Binet–Cauchy identity (A × B) • (C × D) = (A • C)(B • D) − (A • D)(B • C) of library/geometry/coordinates/vectors.fl is one such step after unfolding the vector operations into coordinates.

▶ Run

Several labels and rewriting everywhere

A hint may name several labels: <e | A, B> uses the one that rewrites e (different results are an error). With an asterisk, <e |* A, B> rewrites subexpressions of e by the labels again and again while something applies — from the inside out, left to right — like simp only [A, B] in Lean. Rules are used left to right only, and a subexpression is never folded back into one that was already unfolded, so a label may hold both sides of a definition. The typical use is unfolding nested definitions at once.

Unfolding everywhere

The lattice identities of the repository (library/sets/lattice.fl) are each one line: <⇔(<∈(t, ∩(a, ∪(b, c))) |* L∈∩, L∈∪>, <∈(t, ∪(∩(a, b), ∩(a, c))) |* L∈∪, L∈∩>) | decide()> — both sides unfolded, the Boolean identity checked by decide().

▶ Run

Definitions

A definition is a statement that rewrites a new atom into a lambda: if(double -> {x: nat | plus(x, x)}). Marking the atom in front of its arguments, <double>(a), rewrites it and applies the lambda (β-reduction): the result is double(a) -> plus(a, a). Since the atom is new, such a definition adds nothing that could not be written without it — it only names a term.

Unfolding a definition

In the set theory of the repository, operations are defined this way after their unique existence is proven: ∪ -> {a, b: 𝕊 | ι{c: 𝕊 | ∀{t: 𝕊 | ⇔(∈(t, c), ∨(∈(t, a), ∈(t, b)))}}}, where ι is the definite description (∃!(p) implies p(ι(p))).

▶ Run
⚠
A proof fails if no visible statement has a marked expression as its left side. The error names the place; show() there lists what is visible.

↗

Calls T[…]

Applying a theorem or a fact to concrete values

Overview

A call T[a, b | J] applies a proved statement where it is needed. Before the bar come the values of its parameters, after it the proofs it rests on — facts for its conditions and realizations of its lock axioms. T is a label, the result of a command (decide(X)[n]), a proof (<…>[x]) or another call (T[b][a]). The result is the instance of each statement of T, delivered into the current scope.

theoremLabel[]theoremLabel[| factLabel1, factLabel2, …]theoremLabel[argumentExpression1, argumentExpression2, … | factLabel1, …]theoremLabel[parameterName := argumentExpression, … | factLabel1, …]theoremLabel[argumentExpression1, …; | factLabel1, …;]
theoremLabel
The theorem: a label whose statements are its conclusions. Everything between a statement and the place where the label is declared is the theorem's contract: for atoms and type parameters to substitute, if conditions to meet, locks whose axioms need realizations — among them the schemas of the rules the theorem was proved under (below). Also the result of a command, a proof or a call.
factLabel1, …
Optional: facts for the theorem's if conditions and realizations of its lock axioms — labels, or what gives statements in place: a proof T[| <… |>], a command, a call. Each must be used by some condition or axiom. Conditions not given are met by visible facts; ; at the end — only these.
argumentExpression1, …
Optional: values of the theorem's parameters in their order — its for atoms from the first (_ skips an atom, which is then inferred), then the quantifiers of its conclusion. Positional values take the parameters not given by name.
parameterName := …
Optional, mixed with positional values in any order: values by name — an atom of the theorem's for (x := S(0)) or a type parameter (D := nat). Every atom not given is inferred from the conditions and facts (an atom that is itself in scope at the call stays itself, implicit); ; after the values — all are given, none is inferred.

Properties

Produces
Statements (the theorem instantiated with concrete values)
Delivery & Label
Into the current scope. A label on the call (R: T[a]) holds the instantiated statements at this scope.
Creates scope
No.
Mechanism
Walks the path from each theorem statement's definition scope up to the label's declaration scope. Along this path:
• for nodes: collects declared atoms; these are substituted with the given expressions (by name or by position, types must agree). Atoms not given are inferred from the theorem's if conditions, facts and realizations; an atom that is itself in scope at the call is implicit — it stays itself; another atom of the same name is never taken
• if nodes: checks that each assumption (with atoms substituted) holds as a statement in the current scope
• type() nodes: collects declared type parameters; they are given by name (D := nat) or inferred from the types of the atom arguments
• rule nodes: a rule is its schemas, axioms of its lock (Apply, Distinct, …); they are realized like the axioms of any lock, by labels passed to the call — the label of the declaration holds its schemas (Rules on the theorem's path)
• lock() nodes: for each axiom registered in the lock, finds a realization among the labels passed to the call by comparing signatures — the lists of for, if and rule conditions surrounding the axiom in the theorem and the realization, respectively. See Lock axioms: signature matching below.
Every label passed must be used: one of its statements satisfies a condition or realizes an axiom. In the journal of the interpreter and in the source map of the certificate the step is named call.

Basic examples

Call a theorem with values for the atoms of its for:

Applying a theorem

▶ Run

Details

The parameters of a statement are what lies between it and the declaration of its label: the atoms of for and the types of type() to substitute, the conditions of if to meet, the locks whose axioms need realizations — then the quantifiers of its conclusion. A theorem proved inside for(x: T) is called on values of x; a quantified fact ∀{x: T | P} -> true has no for of its own and is called on values of its quantifier (calls on facts). It is the one way to use what was proved: from the call of a lemma to the instance of an axiom of a theory at another structure.

Locks make a call more than substitution: a theorem proved under axioms can only be applied where those axioms are honestly supplied. The bulk of this page, from Lock axioms: signature matching onward, explains exactly how realizations are checked.

Arguments inferred from conditions and facts

Most arguments would only repeat formulas already written in the statements the theorem needs, so they are inferred. Each if condition of the theorem becomes a pattern whose unknowns are the atoms not given, and it is matched against the statements visible at the call. Matching is first-order with two higher-order cases: an atom-function applied to bound variables, like p(x) inside {x: nat | …}, receives a lambda (a Miller pattern); an atom-function applied to a term with bound variables, like P(ι(n)) inside ∀{n: ℕℝ | …}, receives the lambda in which every occurrence of that term is replaced by its variable — the only solution, since P cannot see n (if n remains elsewhere, there is none); otherwise p(a, b) against h(c, d) takes p := h. The instantiation is printed in the log (// Arguments: P := A (inferred), Q := B) and then checked as usual.

When the conditions can be satisfied in several ways that give different results, shadowing decides, as in a proof: the later and the inner hide the earlier and the outer. A fact of a label passed to the call comes first, then the statements of the current block from its end, then the enclosing blocks outward. One instantiation shadows another when each of its conditions is met by the same or a nearer statement, and at least one by a nearer one; so closed facts at the top level of an imported module, or of the model in an interpretation, do not disturb inference inside a proof. If the instantiations no one shadows give different results — each is nearer in one condition and farther in another — the call stops with an error showing two of them. The names of the theorem's parameters play no part: with if(P(A)) if(P(B)) at the call, both conditions P(A), P(B) of a uniqueness theorem take the nearer P(B), and the visible A, B are passed as arguments. A label passed to the call is used first — a condition that one of its statements fits is matched only against the label, and every solution must use every label. A condition whose left side is a bare atom (P -> true) fits almost any statement; a fact label or P := … settles it. Inference only chooses the instantiation; soundness does not depend on it, because all conditions, rules and lock axioms are checked afterwards.

Inferred arguments and a fact label

▶ Run

Implicit atoms and type inference

A theorem whose label is declared above a type() and its for atoms is generic: it can be applied to any type. Its outer atoms work like the variables of a Lean section: inside the theory they are the very atoms in scope and stay themselves; elsewhere they are inferred from the conditions, the facts and the realizations given, or written (f := g, or in order), and the types are inferred by matching. An atom of the call site is never taken for a parameter because it has the same name: the names of a lemma's own parameters (P, Q, a) are short and common, and a Q: 𝕊 in scope is not the Q: 𝔹 of the lemma. What the conditions do not determine is written. All conditions of the theorem are checked as usual.

Implicit atoms and inferred type

The full forms Twice[f, zero] and Twice[f := f, x := zero, D := nat] mean the same.

▶ Run

An atom of the same name is not taken

The last call has no condition to infer a and b from, and the atoms a, b of its for are other atoms than the theorem's: they are written, Swap[a, b].

▶ Run

Expected error: Cannot infer argument 'a: nat

Closing a side with ;

Both sides of a call follow one rule: what is written is taken, and whatever the theorem still needs is found by itself — the values of its atoms from its conditions, the facts for its conditions among the visible statements. A ; at the end of a side says «that is all»: nothing on that side is found, and what is missing is an error, not a search.

  • T[a, b; | …] — every for atom of the theorem is given, by position or by name; none is inferred or taken by name from the call site. Types still follow from the values. The constants of a definition move with their definition and are not given.
  • T[… | H, G;] — the conditions of the theorem are met only by the facts of H and G; a visible fact that would meet one is named in the error. Lock axioms are realized only by the proofs written in any case; a lock already in force at the call site, with its axioms unchanged, is the context, not a fact.

Closing never changes what is proved: it only narrows where the call looks. A call that passes closed passes open with the same result. Use it where the visible facts are many or contradict each other, and where a reader should see every premise in the text. The same ; closes decide, and a hint by a theorem closes inside its call: <e | T[| H;]>. Inference and what it chose are printed in the log either way.

Closed sides of a call

The last call is closed by ;: its condition P -> true at P := A is visible, but not given.

▶ Run

Expected error: The proofs of the call are closed by ';', and none of them meets the condition

Strictness for a whole file: --explicit

A project that wants every premise in its text runs the interpreter with --explicit. Then every call is checked as if both its sides ended with ;, every decide takes only the facts written after |, and every rewrite of a proof names its hint (<e | H>, a hint by a theorem as a call with its values and proofs). The errors name the visible fact that was found and the label to write for it. The option only forbids: a text it accepts means the same without it, because a call that gets everything written finds nothing else — the proofs written come first, and the values written are not inferred. So a strict file needs no ; anywhere, and it reads the same in any project. The option checks the text of the file itself, not the text that commands write (the proofs of decide, the schemas of rules) and not its modules.

Theorem with Conditions

When the theorem lies under an if, the call checks that the condition, with the values substituted, holds in the current scope:

Theorem with conditions

▶ Run

A call without arguments

If the theorem has no for atoms of its own, the call has no values: T[]. The theorem's if conditions are still checked in the current scope. (T[] is not T: the bare label stands for its statements as they are, where they were proved.)

This means you can prove something once and reuse it in any scope where the same condition holds — regardless of how you arrived there:

A call without arguments

The theorem AndImpliesOr is proved once. Then AndImpliesOr[] is called in two different scopes — each arrives at and(P, Q) -> true by a different route, but the theorem applies in both without repeating the proof. With for atoms the same call instantiates the theorem at any concrete values too.

▶ Run

A label of several theorems

A label may hold several theorems. A call applies each of them that the arguments and the labels fit here, and skips the others — the log says why each was skipped. At least one must apply; otherwise the error lists the reason for each theorem. The same rule holds for every place that takes a label: a hint tries all statements of its label and takes their result, if they agree.

Only the fitting theorems apply

▶ Run

Arguments for the quantifiers of the conclusion

The parameters of a theorem are its for atoms, then the quantifiers of its conclusion — those the theorem of a visible notation("apply" | …) removes. Values after the for atoms go to the quantifiers, outermost first: T[f, n] for a theorem T over f whose conclusion is ∀{n: ℕ | …} -> true states the instance at n at once (the chain T[f][n] — a call on the result of a call — gives the same: calls are curried), and delivers only that statement. A fact is a statement without for atoms, so H[a] on a quantified fact H is its instance at a (below). A quantifier always takes its value explicitly and by position: the name of a bound variable belongs to the formula, not to the call.

A theorem applied at the quantifiers of its conclusion

▶ Run

Calls on facts

A fact ∀{x: ℕ | P(x)} -> ✔ has no for atoms of its own, so its parameters are the quantifiers of its conclusion: H[c] is its instance P(c) -> ✔. The quantifier is removed by a visible rule("apply", ∀, ✔, ✔) — the rule says which atom is a quantifier and that its value ✔ carries over to the instance. The values go to the bound atoms in their order: as many as the quantifier binds at once, or more for nested quantifiers over one atom each — H[a, b] on ∀{x | ∀{y | P}} removes both. Their types fix the type variables of a polymorphic statement. A quantified fact can also be used without a call, as a hint of a proof.

A call on an axiom

▶ Run

Two quantified atoms

▶ Run

A value may be any expression of the bound atom's type, a lambda among them:

A lambda as the value

▶ Run

A call on a fact removes the quantifier through the theorem named by notation("apply" | A∀Apply) visible at the call: the nearest declaration for the quantifier and value is taken.

Realizations: labels for lock axioms

When a theorem uses lock() with axioms, the caller must supply a realization of each axiom — a proof that the axiom's conclusion holds in the current context. The label holding that proof is passed after the theorem, like a fact.

The realization lives outside the lock, in the calling scope, and is passed after the bar by name.

A realization passed to a call

AxiomAB is the realization: it proves that A -> false leads to B -> true in this specific context. Passing AxiomAB after the bar tells the call to use it as the realization for axiom AxiomPQ inside the lock. The same theorem FastOr can be applied with a different realization label in a different context.

▶ Run

A realization also tells the values of the parameters, as a fact tells them through a condition. The axiom is a pattern: its own for atoms are matched, in order, with the realization's own atoms as bound variables, and its own if conditions with the realization's, so a parameter applied to them is a Miller pattern — an axiom P(S(n)) -> true against a step proved for c gives P the lambda over c. A value is taken only when every match that gives it agrees. A lambda that only applies an atom to its own variables is that atom: {x, y: T | q(x, y)} gives q. The realization is then checked as before.

Values from the realization

▶ Run

A block of proof in an argument

After | a proof may be a block: headers for(…), if(…), type(…) and one statement, T[| for (y: T) S]. It proves what a label declared before the call and defined inside the block would hold — +B; for (y: T) B: S; — a theorem over y, or under the condition of the if. Nothing it proves enters the block of the call. So a lemma whose lock axiom has its own for or if is a command of its own: the block is its argument, and the result stands where the call is, outside the block's headers — as generalize stands outside its for and contradict outside its if.

A command of one's own with blocks as arguments

The values Q := a, P := a ∨ ¬a are inferred from the realizations: the blocks are theorems under a and under a -> ❌.

▶ Run

A call that leaves its blocks

The library names such lemmas by the step they make, in lowercase: contradict, generalize, deduce, obtain, witness, refute. A command is word(…), a theorem word[…]; the call reads as the step.

A lock axiom asks for a proof with blocks of its own: generalize asks for p(x) -> ✔ under for (x), deduce for Q -> ✔ under if (P), the library's obtain for a statement under for (x) if (p(x)). A proof written at a point inside such blocks — a label declared where it is defined, or a proof written in the call — is taken with the blocks it stands in, as many as the axiom asks for, and the call then stands above them: its result lies outside the for or if, which the step discharged. This is how the library introduces a quantifier (generalize[| H]), an implication (deduce[| H]) or eliminates an existential (obtain[| H]) — the commands generalize, deduce and obtain are these calls (step 189б). A label declared outside the block it is defined in holds that block (labels): the blocks it holds count too, and the call stands at the label's place.

Quantifier and implication introduced by calls

The reading with the blocks comes first: the call stands as high as it can. When the axiom's obligations cannot be met that way, the call is read as written, in its own block. Without a proof given (contradict[] inside if (Q)), the call takes the blocks it stands in itself and looks for the obligations among the facts there.

▶ Run

Three rules shape the result:

  • Where the result stands. At the exit, above the blocks taken — when the call is written inside them. A call written beside them, in a block of its own under the exit (if (q -> ❌) F: obtain[…, q | G] beside the for that G leaves), keeps its result at its own place, where contradict can then close that if.
  • Which blocks are taken. As many as the axiom's own shape asks for, counted from the proof outwards: for atoms and if hypotheses, never a lock, type or rule. Several atoms of one for at once: the library's generalize2 … generalize8 (logic/quantifiers.fl), the quantifiers nested in the order of the atoms, each with a type of its own.
  • Names of the variables. A quantifier variable the theorem applies the predicate to takes the predicate's own name: generalize2[| S] under for (a, b) states ∀{a, b | …}, not the lemma's ∀{x1, x2 | …}; a name already used elsewhere in the statement is not taken, and a variable the inference invented for a term that is no atom gives no name.

Rules on the theorem's path

A theorem proved inside an enumeration type(T = a | b) or rule("bijective", f) rests on their schemas — Distinct, Cases, Injective, Column: the declaration generates them as axioms of a lock (enumerated types, rule("bijective")). Outside, they are realized like any lock axioms: the call is given the labels that realize them. Usually these are the schemas of the same kind of declaration at the call site; any statement of the same form will do — an axiom of the caller's lock, a proved theorem. A call never takes a schema by itself. The same holds for an enumeration replaced by an enumeration of the call site: its schemas of distinct values and of cases are given by a label.

The schemas have no names of their own: the language names nothing. A label on the declaration holds all the schemas it generates — a package, +ColorSchemas: type(Color = red | green) or +ABijective: rule("bijective", color) — and the call takes from a given package the schema each axiom needs. Two schemas of a package that both fit would be an error, as two fitting facts are; the schemas of one declaration never do. The axioms of a quantifier are ordinary axioms of a lock the file writes (A∀Apply, generalize of logic/quantifiers.fl): a theorem proved under them is called under the same lock, or realizes them like any lock axioms.

A rule's schema realized by the call site's rule

R is the call H[x] on a quantified fact, so it rests on the Apply schema of the rule for Q. The call site declares the same rule for G; the label GSchemas on it holds its schemas and is passed to the call like any realization. Without it the call stops with “Axiom realization not found”.

▶ Run

…or by any statement of the same form

No rule at the call site: the axiom GApply of the caller's own lock states the schema for G, for every predicate p, and realizes it. An axiom about one predicate only would not: the schema is about all of them.

▶ Run

Lock axioms: signature matching

The simple case shown above — one axiom realized by one search label — hides what a call actually checks when locks are involved. This section spells out the rule precisely. It matters when realizations contain if, for, nested locks, or when the theorem's lock axioms have their own surrounding conditions.

Which locks require realizations

Only locks that lie on the theorem's path — the parent chain from the theorem statement's definition point up to the scope where the theorem label was declared — oblige the caller. Each axiom of each such lock needs a realization. Locks that merely exist nearby — siblings of the theorem statement, locks in other branches of the tree — do not participate: the theorem was not proved under their axioms, so the call ignores them.

Sibling lock off the path

The lock L sits next to the theorem statement, not above it. The path of T runs from its axiom command through for(a, c) up to the scope where T is declared, inside Scope - it crosses neither L nor Scope, so the call needs no realization at all. A realization label passed here would be an error: every label given to a call must be used.

▶ Run

The signature of a path

Every statement in Formall — a theorem statement, a lock axiom, a realization — sits at some place in the tree, and has a path from that place up to where its label was declared. Along this path, three kinds of blocks add to the local world:

  • for blocks introduce atoms;
  • if blocks introduce conditions;
  • type blocks introduce types; rule blocks (define, bijective) introduce rules.

The signature of a path is the multiset of these contributions across the path, organized by category. The order in which if and rule commands appear inside a single category does not matter — they are conjunctive — and neither does the relative order of for blocks of different types. What does matter is the order of for-atoms of the same type (used positionally) and the total number of contributions in each category.

What a call compares

For each axiom inside a lock on the theorem's path, the call finds its full path — from where the axiom is declared up to the theorem label's declaration scope. The same is done for the candidate realization — from where its statement is assigned up to where the realization label is declared. The call then matches these two signatures by the following rule of contraction:

The realization's signature must be no wider than the theorem's. Concretely:

  • for: per type, the realization must have at most as many atoms as the theorem, and atoms are matched positionally (the realization's first atom of a type pairs with the theorem's first atom of that type, etc.). The realization may declare fewer atoms; trailing theorem atoms simply go unused.
  • if: every if-condition in the realization's signature must appear in the theorem's signature. The realization may use fewer.
  • rule: every rule in the realization must appear in the theorem. type declarations are bounded the same way — the realization may not introduce more of them than the theorem's path carries (they are compared by count: type-parameter names are placeholders bound positionally by the call, so the names themselves never matter).

The axiom statement itself is matched after the for-atom mapping is built. Nothing in the realization beyond what the theorem already assumed may appear.

The intent is single and simple: the realization must not give itself more power than the theorem allowed. If it did — by adding an extra if, an extra atom, an extra rule — it could prove things the theorem never could, and the result of the call would be unsound.

Realizations may contain locks

A realization is allowed to cross lock() nodes on its path. Each lock contributes its axioms to the realization's signature, and each such axiom must, in turn, correspond to an axiom of some lock on the theorem's path (the inner match uses equality of signatures, since lock axioms are what the realization provides — they must be exactly as strong as the theorem expects, neither more nor less).

Lock in the realization, matched by signature

The theorem's axiom c -> false is registered in lock L, with a sub-lock Inner contributing a -> true. The realization is the plain label R: its proof sits inside lock RInner, so the realization's signature includes a nested-lock axiom not(y) -> true. After substitution a -> not(y), c -> not(not(y)), the realization's nested axiom matches Inner's axiom exactly. Sound and accepted.

▶ Run

How the realization's locks are nested or grouped does not matter — only the multiset of axioms across all of them does. The realization may split one theorem-lock into several, merge several into one, reorder them, or change the surrounding ifs — as long as the resulting signature stays inside what the theorem allows.

Shared context between the axiom and the theorem

The lock determines which parameters belong to an axiom schema. Values declared above the lock are replaced by the theorem arguments. Parameters declared inside the lock remain universally bound in the axiom, even when the result was proved under the same for block.

Place instance parameters and conditions above the lock when the intended contract depends on those particular values. The following realization supplies the complete schema below L.

Parameters above and below the lock

The parameters a,c and the condition c -> true are above L. The call substitutes them and checks the condition. The parameters m,n and condition a -> true are inside L and remain part of its complete axiom schema.

▶ Run
ℹ
A pointwise fact cannot implement a universally quantified axiom. Sharing a for-block with the theorem result does not remove that quantifier from the lock contract.

Permutations and grouping

Because signatures are compared as multisets per category, the textual layout of the proof is free in every way that does not change the multiset:

  • for of different types may be reordered. A template path for(m: bool) for(p: nat) is matched by a realization path for(N: nat) for(M: bool) — grouping by type happens before comparison. Only the order of atoms within one type is positional.
  • if blocks may be reordered and regrouped — two nested ifs, one if with two conditions, or any permutation thereof contribute the same set of conditions.
  • Locks may be split or merged. Two sibling locks with one axiom each, or one lock with two axioms, contribute the same multiset of lock axioms. The realization need not mirror the theorem's lock structure — only its total contract.
  • Multi-statement axioms are flattened. axiom(s1; s2 | L) registers two independent axioms, exactly as two separate axiom(s1 | L); axiom(s2 | L) commands would. A template written one way is matched by a realization written the other way.

Reordered for-types in a nested lock axiom

The template's nested axiom carries for(m: bool) then for(p: nat); the realization's mirror carries for(N: nat) then for(M: bool). Grouped by type, both are one bool-atom plus one nat-atom — the signatures agree.

▶ Run

Why this is sound

The whole construction rests on a single guarantee: a call delivers a theorem's conclusion only when the realization honestly supplies every premise the theorem was proved under, up to the call's substitution. Nothing weaker is accepted, and nothing the theorem did not assume can sneak in. Three facts together close the loop:

  • Requirements may only shrink. An if-condition, a for-atom, or a rule rule on the realization's path is something the realization demands of its context. Demanding less means the realization proved its statement under stricter circumstances — always safe. Demanding more is rejected, because the theorem never sanctioned that extra leverage.
  • Provided facts match pairwise-exactly, and never exceed the template. A nested lock axiom is something the realization hands back as established. The realization's set of nested axioms must be a subset of the template's — relying on fewer local assumptions is a stronger proof and is accepted (this weakening is what makes derived theorems possible); an extra nested axiom the theorem never sanctioned is rejected. Each nested axiom that is present must match a template one exactly — statement, for-atoms, if-conditions, rule rules and the count of rule type parameters on its own chain: handing back a stronger or weaker variant of an expected assumption would silently change what the theorem relied on.
  • Shared premises are never skipped. The theorem's conditions are checked against the calling scope. Conditions inside an axiom's lock also remain in that axiom's schema. A theorem with an unmet shared if is refused outright, even if the realization itself looks fine.

An axiom holds under its own lock. It can supply a realization there because the result stays under that lock. Outside a closed lock, its axiom remains an assumption of the realization's contract and cannot be discarded. A theorem may cross a lock only when its full contract matches the required scheme; an unconditional conclusion requires a proof of every premise.

Type Parameters

Types in Formall form their own small language, separate from expressions. A type is either a declared primary type (like bool, or a parameter introduced by type()) or a function type built from types, like [bool -> bool]. There are no operations on types — they are never computed, compared by value, or produced by expressions; the only things that ever happen to a type are declaration, substitution, and structural equality checking. A type parameter is an atomic placeholder name: it has no content of its own, so a parameter is given by its name among the values (U := bool) or, usually, inferred from the types of the atom arguments. A type argument may be a full type tree, not just primary names — [bool -> bool] is a valid instantiation of U, and the substitution rewrites every occurrence inside atom types structurally, so [U -> bool] becomes [[bool -> bool] -> bool].

When a theorem uses type() to declare a type parameter, the concrete type is inferred from the arguments, or given by name (T := ℕ):

Type parameters

The type parameter T is matched to ℕ. All atoms declared with type T (like =, x, y) are substituted with atoms of the matching concrete type.

▶ Run
💡
A call is the primary way to build complex proofs from simpler lemmas. Well-designed theorem libraries make proofs shorter and clearer.

Type parameters and lock axioms together

Type substitution composes with signature matching. If a lock axiom's own path declares for-atoms whose types mention a type parameter, those types are substituted by the call's types (inferred or named) before the for-categories are compared. A realization written directly in the concrete type matches a template written in the parameter:

Type parameter in a lock axiom

The template axiom f(u) -> true is parameterized over U both in the function type [U -> bool] and in the atom type of u. The call substitutes U -> bool, f -> not, u -> y; the expected realization becomes not(y) -> true, which the lock-label RL provides. Atom types on the axiom's own path are compared after the same substitution, so a realization declared over the concrete type lines up with a template declared over the parameter.

▶ Run

A theory as a block

A theory is a block whose parameters are its signature and whose assumptions are its axioms: type(M) for(op: [M, M -> M]; e: M) if(…) if(…) { … }. A theorem labelled T:: inside the block is declared outside it, so the type, the atoms and the axioms are its parameters and conditions. Inside the block the theorems serve as hints as usual (the parameters are the atoms in scope); outside, a call applies a theorem to another structure: the axioms of that structure, passed as labels, determine the type and the operations. This is a locale in Isabelle or a structure with an instance in Lean; in the repository, library/algebra/group.fl is the group theory written this way and z2.fl applies it to the integers modulo 2.

A theory and its instance

▶ Run

Commands

↗

Command Groups

All commands of the language, grouped by what they do with scopes and statements

Overview

Every Formall command does one of a few things with the scope tree: it opens a scope (a context the statements inside depend on), passes through without creating a context, adds statements to the current scope, moves a result above an enclosing scope, generates ordinary commands for you, or works with labels. Commands of one group share their boundary and label behaviour, so learning one of them explains the others.

Reading signatures. Each command page starts with its signatures and, under them, what to pass as each parameter of that command. The names in signatures are placeholders, not names to declare: a name ending in Label is a label (a command that returns statements can usually stand there too), …Atom / …AtomName — an atom or its name, …Expression — an expression, …Type — a type. Arguments come in two sides: first the expressions — terms and statements left -> right, written as they are, without quotation marks — then, after a bar |, the proofs: labels, proofs <…>, calls and commands that give statements (axiom(P | L)). Quotation marks are left only for texts that are not terms: file paths and the kinds of rule("…") and notation("…").

Two forms of the language are not commands at all, though they derive statements as commands do: a proof <…> and a call T[…]. They are described with the basics and listed below among the inference steps.

GroupCommandsWhat they share
Context type, for, if, lock, axiom, rule Open a scope; what is proved inside depends on it. Boundaries for closing commands.
Transparent headers import, notation Stand in a header chain or end with ;, but are not a context: commands pass through them.
Inference steps <…>, T[…], define Add new statements to the current scope.
Calls that leave their blocks contradict[| S], generalize[| S], deduce[| S], obtain[| S] A call whose lock axiom asks for a proof under for or if takes those blocks and delivers the result above them, removing the assumption or the variable.
Generators decide Writes ordinary if / call / <…> text for you; the checker sees only that text.
Tools show Print what is visible at the place (scope, facts, labels) or search for text; produce nothing.
Labels + - * ^, expect( ) Combine and compare collections of statements; no logical content.

A second way to look at the same commands is the trusted base: the axioms, the locks, the enumerations and the two rules — define (from ∃!) and bijective. The steps of a proof rest on theorems the file writes and names: a call on a quantified fact removes its quantifier through notation("apply" | A∀Apply), rewriting by equality in proofs through notation("hint" | …), and the introduction of a quantifier or an implication, the elimination of an existential, the closing of an assumption are calls of theorems (generalize, deduce, obtain, contradict of the library). tools/trust.py lists what each theorem relies on.

Context

Context commands are block commands: they open a scope that lasts until } (or until the end of the enclosing block). A statement proved inside the scope depends on the scope's header, and outside of it the statement becomes a theorem with that header turned into parameters and conditions, which a call T[…] fills in again:

  • type(T) and for(x: T) introduce parameters — types and atoms (⋀ in Isabelle/Pure). type(T = a | b) also declares an enumeration.
  • if(A -> B) introduces assumptions (⟹). lock() is an assumption block whose assumptions are added later, from inside, by axiom(… | L); a theorem proved with them receives them as parameters that a call realizes.
  • rule("…", …) introduces rules of the logic; a theorem proved under a rule needs that rule wherever it is applied.

All of them are boundaries: closing commands stop at them, and a label on type, lock or rule names the scope instead of capturing statements.

Transparent headers

import("file.fl") and notation("kind", …) may stand in a header chain (for(∘, e) notation("infixl", ∘, 70) if(…) { … }) or end with ;, but they are not a context: closing commands pass through them, and theorems get no parameters or conditions from them.

They are not one command, because they do different things. notation changes only how text is read and printed: if all operators were written in prefix form and abbreviations expanded by hand, the proof would stay the same. import brings atoms, axioms, rules and theorems of another file into scope; without it the proof does not check. It also has its own permissions (--import-root, formall.project).

Inference steps

These forms and commands add statements to the scope they are written in; a label on them captures those statements there.

  • <…> — rewriting: angle brackets, hints <e | L>, chains <t0 -> t1 | H -> t2>.
  • T[…] — applying a theorem: parameters are instantiated, conditions are discharged by facts, lock axioms are realized; on a quantified fact, L[a], — removing its quantifier (∀-elimination).
  • witness[t | L] — a call of the library's theorem: replacing a term in a fact by a quantified variable (∃-introduction).
  • define(f := …) — a new atom with its defining theorem.

Calls that leave their blocks

A step that takes statements proved inside a scope and delivers the result above it, removing what the scope assumed, is a call of a theorem whose lock axiom asks for a proof of that shape; the library proves the theorems once:

CallTakesResult above the blocks
contradict[| S]if(A -> B)The assumption is false: the contradiction flips it (A -> ❌ for A -> ✔)
deduce[| S]if(P)P ⇒ Q for the Q proved inside
generalize[| S]for(x)∀{x | …}
obtain[| S]for(x) if(p(x))The statement itself, when it does not mention x (∃-elimination)

They share all of their mechanics:

  • the proof after the bar is a label, a proof or a nested call; a nested call delivers above its own blocks first, and the outer call stands where that result stands, so the calls compose from the inside out: generalize[| deduce[| contradict[| …]]];
  • a label on such a call captures the result at the delivery scope, not where the call is written;
  • context commands a call does not take (type, lock, rule) are boundaries: the result cannot be carried across them.

contradict and deduce close the same if; which one to use is the author's decision, so each step names what it does.

Generators

decide(X) computes the value of X from facts by the tables of the functions over finite types. It produces ordinary if / call / <…> text that is parsed and checked like hand-written code; it adds nothing to the trusted base. The hints <e | decide()> and <e |* A, B> inside proofs work the same way. A case split by hand is a branch if (P -> ❌) S and the same step S after it (decide).

Tools

show() prints the context of its place into the log: the enclosing for / if (which one a closing command will close), the nearby facts and the labels of the file; show("text") searches visible facts and labels, imported ones included. It produces no statements — the proof is the same with or without it.

Labels

Label commands treat a label as a collection of statements: + union, - difference, * intersection, ^ symmetric difference. expect( ) checks that collections are equal and reports the difference otherwise; the commonly used check “these statements were proved” is expect(a -> b; … | L). Declaring, defining and extending labels (+L;, L:, L::, L+:) is described in Labels.


Context

↗

type

Declaring new types

Overview

The type(...) command declares new primary types. Types are the foundation of Formall's type system.

type(typeName)type(typeName1, typeName2, typeName3)type(enumTypeName = valueAtomName1 | valueAtomName2 | valueAtomName3) // enumerated typetype("'typeVariableName") // a type variable: atoms with it in their type are polymorphic
typeName1, …
Names of new types. Inside a theorem (a block whose statements are called elsewhere) a declared type is a parameter: a call substitutes another type for it.
enumTypeName = value1 | …
An enumeration: the type and its values (atoms of that type), every two different, every element one of them. The declaration generates the axiom schemes of distinct values and of cases that decide, cases and the lemma contradict of the library rest on; a label on the declaration holds them (+ColorSchemas: type(Color = red | green)), to pass to a call.
"'typeVariableName"
A type variable (a name starting with '): an atom whose type contains it is polymorphic, a statement with it is a schema; each use instantiates it.

Command Properties

Group
Context
Produces
Nothing for a plain type; an enumeration generates the axiom schemes of distinct values and of cases
Delivery & Label
A label on type holds the schemes of an enumeration (+ColorSchemas: type(Color = red | green)), to pass to a call.
Creates scope
Yes.
Mechanism
Declares the types in its scope; inside a theorem a declared type is a parameter that a call substitutes. An enumeration also declares its values as atoms of the type.

Basic examples

Type names can use mathematical Unicode symbols:

Declaring types

▶ Run

Enumerated types

type(T = c1 | c2 | … | cn) declares the type T and its values: atoms c1 … cn of type T. They are constants, not parameters of theorems. Two rules come with the declaration:

  • distinct values — two values of one expression give anything: from X -> ci and X -> cj follows every a -> b (Distinct);
  • exhaustion — the type has no other elements: what follows from each value of X follows (Cases).

For a function between two enumerated types that takes every value once (a grid puzzle), see rule("bijective"). In Lean this is inductive Color | red | yellow | green, in Isabelle datatype.

What the declaration writes

The rules are not built into the interpreter. The declaration writes them as text of the language: a lock under the declaring block, one axiom per rule, and the code after the declaration lies inside that lock. For +Abool: type(bool = false | true) the text is this (names with a dot are internal, '𝓐 is the type of «anything»):

for (𝓨: bool; 𝓪, 𝓫: '𝓐) {
	// Distinct: two values of one 𝓨 give anything
	+𝓟: lock() { axiom(𝓨 -> false; 𝓨 -> true | 𝓟); bool.Distinct.false.true: axiom(𝓪 -> 𝓫 | bool.Enumeration); }
	// Cases: what follows from each value follows
	+𝓒: lock() {
		if (𝓨 -> false) axiom(𝓪 -> 𝓫 | 𝓒);
		if (𝓨 -> true) axiom(𝓪 -> 𝓫 | 𝓒);
		bool.Cases: axiom(𝓪 -> 𝓫 | bool.Enumeration);
	}
}
// Flip, for two values only: a lemma, not an axiom. If 𝓨 -> true follows from 𝓨 -> false, then 𝓨 -> true.
// Proved by Cases: the case false is the premise, the case true is its own hypothesis.
for (𝓨: bool) +𝓟: lock() { +𝓡0, +𝓡1; if (𝓨 -> false) 𝓡0: axiom(𝓨 -> true | 𝓟); 𝓡1: if (𝓨 -> true) {} bool.Flip.false.true: bool.Cases[𝓨 := 𝓨, 𝓪 := 𝓨, 𝓫 := true | 𝓡0, 𝓡1]; }
for (𝓨: bool) +𝓟: lock() { +𝓡0, +𝓡1; 𝓡0: if (𝓨 -> false) {} if (𝓨 -> true) 𝓡1: axiom(𝓨 -> false | 𝓟); bool.Flip.true.false: bool.Cases[𝓨 := 𝓨, 𝓪 := 𝓨, 𝓫 := false | 𝓡0, 𝓡1]; }

With three values there are three Distinct axioms (one per pair), a Cases axiom with three branches, and no Flip. The label on the declaration (Abool) holds all of them. A call Abool[…] tries each one; the ones whose conditions and lock do not fit are skipped (the log says which), the one that fits is applied. The kernel sees only these axioms: it has no rule for enumerations.

Why contradict works

The library proves the contradiction lemma from these axioms in one line (logic/bool.fl, here with false/true for ❌/✔):

+L: lock() if (P -> true) { +AX: axiom(X -> false; X -> true | L); contradict: Abool[| Abool[_, P, false | AX]]; }

Read it from the inside out:

  1. Abool[_, P, false | AX] — the values are 𝓪 := P, 𝓫 := false; 𝓨 is left to the realization. AX holds X -> false and X -> true: exactly the two axioms of the lock 𝓟 of Distinct, so 𝓨 := X. Of the four schemas only Distinct fits. Result: P -> false — inside if (P -> true), from the contradiction (ex falso).
  2. Abool[| …] — no values written; the proof after the bar is P -> false under if (P -> true). Flip.true.false has exactly this lock axiom: if (𝓨 -> true) 𝓨 -> false. The call takes the if block as its realization, with 𝓨 := P, and stands above it: P -> false outside the if, inside the lock L.
  3. The label contradict catches it there. The lemma says: for any P, X, if under if (P -> true) both X -> false and X -> true hold, then P -> false. The two axioms of L are what a user must show.

So if (Q -> true) contradict[| )>] works like this: the proof after the bar gives not(Q) -> false, the fact not(Q) -> true is visible, together they realize the lock of contradict with X := not(Q); the call takes the if and delivers Q -> false above it. The second half of the lemma (contradict+, under if (P -> false)) gives P -> true the same way through Flip.false.true.

The schemas by hand, and contradict from them

The same text as the declaration writes, with readable names and without the second Flip. The three lines of contradict are the three steps above. A three-colour version is in Leaving a Block.

▶ Run

Working with the values

The booleans are the case of two values: refuting one value gives the other, so a case split is a branch if (P -> false) and the same step after it (decide). refute of logic/equality.fl turns x = c -> false into a refutation of x -> c the same way. Two values of an expression of any type contradict too, without an enumeration: the fact a = b -> false says they differ, and distinct[_, a, b | A, B] of the same file closes the assumption (A, B hold X -> a and X -> b). Over more values decide finds the value of an expression from the facts and the tables of the functions; its lemma is a call of Cases with a refutation by Distinct in each branch.

Exhaustion by elimination

decide tries the three values: stop(red) -> true and stop(yellow) -> true contradict the fact, so the signal is green.

▶ Run

Subtypes

A subtype makes a new type out of a part of an old one: the type and its embedding are declared as usual, and subtype states that the embedding is a one-to-one map onto the elements with the property:

type(ℝ⁺) for(ι: [ℝ⁺ -> ℝ]) +Sub: subtype(ι, {x: ℝ | 0 < x}, ∃, ⇒);

The elements of ℝ⁺ are then exactly the positive reals, through ι. This is typedef in Isabelle/HOL and Subtype in Lean. A subtype is how a structure built inside another one — positive reals inside ℝ, natural numbers inside ℝ, real numbers as sets — becomes a type to which a theory can be applied with import with substitution.

What «true» means here. subtype(ι, φ, ∃, ⇒) takes an embedding ι: [S -> T] declared before it, a property φ: [T -> 𝔹] — a name or a set {x: T | …} — and the existential quantifier and the implication its premises are written with. The property is an expression of the truth type (𝔹), and the subtype does not evaluate it: «y has the property» is a statement φ[y] -> ✔ to be proved like any other. The value of truth and the other notions come from the theorems named at the command: ∀ from notation("apply" | A∀Apply), = and ✔ from notation("hint" | A=Rewrite, …); the quantifiers and the equality must be polymorphic ('α, as in the library), so that they speak about the new type too. The set may be empty. The command introduces no names; it writes three premises, and a label on it receives them:

StatementMeaning
S1∀{u: S | φ[ι(u)]} -> ✔the embedding lands in the set
S2∀{u, w: S | ι(u) = ι(w) ⇒ u = w} -> ✔the embedding is injective
S3∀{y: T | φ[y] ⇒ ∃{u: S | ι(u) = y}} -> ✔every element of the set is an image

So a property is proved for an element of the subtype by S1, an element of the subtype is obtained from an element with the property by S3, and equality in the subtype is decided by its images in T (S2). Applied to a label with the three statements, a call uses those that fit its arguments: Sub[a] with a: S gives S1 and S2, Sub[y] with y: T gives S3. Operations on the subtype are defined with define from unique existence (the value of a ⊙ b is the element whose image is ι(a) × ι(b)).

Nothing is trusted here. subtype is a generator, like decide: it writes what could be written by hand. S is a type parameter of the type block, the embedding a parameter of the for block, and S1–S3 are the axioms of a lock under the command; the code after it continues inside the lock. The embedding is an ordinary atom of for: a constant defined under it takes it as an argument, as it takes the other atoms of the block. A theorem proved there holds for every type and embedding satisfying S1–S3, so nothing new follows about the old notions. An interpretation of a theory with a subtype realizes S1–S3 by the subtype of its own copy.

A subtype may be empty

No proof of nonemptiness is needed: any Formall type may be empty. A variable introduced by for is hypothetical, so a contradiction under it cannot be moved outside its scope (a contradiction closes the assumption it stands under, not a for), and S1–S3 are hypotheses of the subtype's lock. If no element satisfies φ, the subtype is an empty type: an element u of it would give φ[ι(u)] and a contradiction, but only for that u, so nothing new follows about T. Nonemptiness is assumed or proved exactly where a proof needs an element.

A result about T proved through a subtype leaves the subtype's block with a model of it (a type and an embedding satisfying S1–S3): Leaving a Block.

The embeddings of nested subtypes compose to give an embedding of the inner type into the original one; they do not automatically supply operations or prove the axioms of a mathematical theory.

A function with a restricted domain does not always need a subtype. A predicate D: [T -> 𝔹] can restrict statements to arguments satisfying D(x), including an empty domain. If a separate domain type is useful, declare the subtype. A limit at a point needs a stronger condition for uniqueness: every punctured neighborhood of that point must contain a domain element.

Even numbers as a type

The subtype declaration supplies an embedding into the original type, membership in the defining set, injectivity of that embedding, and a preimage for every element of the set.

▶ Run

Scoping

Types are scoped to the block of their type command:

Type scoping

▶ Run
ℹ
Unlike dependent type systems, Formall types are simple — no type constructors or type families. For complex structures, use predicates.

↗

for

Declaring variables and universal quantification

Overview

The for command declares atoms (variables and functions) and introduces universal quantification scope. It's one of the most fundamental commands in Formall.

for(atomName: type)for(atomName1, atomName2: type)for(atomName: [argumentType -> resultType])for(atomName: type) { ... }
atomName: type
The atoms to declare and their type; several of one type share it (for(x, y: ℕ)), groups are separated by ; (for(x: ℕ; p: [ℕ -> 𝔹])), as in Pascal. A function type is [argumentTypes -> resultType]. Inside the block the atoms are arbitrary: what is proved about them holds for every value (generalize, and a call substitutes them).
{ … }
The scope of the atoms. Without braces for(…) is a header of the next command, or with ; a declaration to the end of the enclosing block or file.

Command Properties

Group
Context
Produces
Nothing — for declares atoms but does not produce statements
Delivery & Label
N/A. Labels are not allowed on for.
Creates scope
Yes.
Mechanism
Introduces atoms (variables, functions) into scope with specified types.

Basic examples

Simple Values

Declaring values

▶ Run

Functions

Declaring functions

▶ Run

Multi-line Declarations

A single for can declare atoms of different types by separating type groups with commas after their type:

Multi-type declaration

▶ Run

Universal Quantification

A for command introduces a scope where statements proven inside hold "for all" values of the declared variables. Combine with generalize[| …] (a call that takes the for) to lift results out:

Universal proof with generalization

▶ Run

For without Braces

Without braces, for still creates a scope — it just contains only the next command (and its scope). This naturally supports chaining:

Declaration only

▶ Run

Scoping Rules

  • Atoms are visible inside the for scope and cease to exist when it closes
  • Inner for can shadow outer declarations
ℹ
Unlike programming languages, for doesn't iterate. It introduces a variable that represents "any" value of its type.

See Also


↗

if

Introducing assumptions and conditional reasoning

Overview

The if command introduces assumptions (hypotheses) that hold within its scope. It's the primary way to work with conditional statements in Formall.

if(expression -> expression) { ... }if(leftExpression1 -> rightExpression1; leftExpression2 -> rightExpression2; ...) { ... }+hypothesisLabel: if(expression -> expression) { ... }if(expression) // with notation("default", ✔): if(expression -> ✔)
leftExpression -> rightExpression, …
The assumptions: statements that hold inside the block. Without -> (when notation("default", …) is declared) the statement gets the default value of its type: if(P) is if(P -> ✔).
hypothesisLabel
Optional: a label on if holds the assumptions themselves — to name them in hints and as facts of calls.
{ … }
The block where the assumptions hold. Without braces if(…) is a header of the next command, or with ; a declaration to the end of the enclosing block.

Command Properties

Group
Context
Produces
Statements (assumptions)
Delivery & Label
Into itself — the if command IS the scope where its statements live. A label on if captures its assumptions and is scoped to the if scope.
Creates scope
Yes.
Mechanism
Parses the argument string as a list of statements separated by ;. Each entry follows the format expression -> expression. Left-hand sides that share the right-hand side are separated by commas: if(P, Q -> true; R -> false) is equivalent to if(P -> true; Q -> true; R -> false). All resulting statements are introduced as assumptions inside the if scope.

Basic examples

Inside an if scope, the assumed statements are available:

Basic if usage

▶ Run

Details

With notation("default", "true") in scope, a statement without -> means -> true: if(p) is if(p -> true).

Multiple Statements

You can introduce multiple statements at once, separated by ;; a comma joins left-hand sides that share the right-hand side (if(P, Q -> true; R -> false)):

Multiple assumptions

▶ Run

Proof by Contradiction

The most common pattern: assume the opposite, derive a contradiction, and call contradict (the lemma of the library, logic/bool.fl) to flip the assumption:

Proof by contradiction

▶ Run

Case Analysis

Use nested if commands for case analysis (proof by cases):

Case analysis

▶ Run

If without Block

Without braces, if still creates a scope — it just contains only the next command (and its scope):

Chained if

contradict[] only closes the nearest (inner) if. The outer if then simply completes.

▶ Run

Labels and Scope: if Delivers into Itself

Since if delivers its statements into its own scope, a label placed on if captures those assumptions. This label can then be used inside the scope — or passed out to commands that operate at other levels:

Labels on if: scoping and usage

Label A is declared at the if level and captures its assumption. It is accessible inside the block and in nested blocks.

▶ Run

How contradict works with if

contradict[| S] is a call that takes the if it stands in: its lock axiom asks for two values of one expression under the assumption. When it succeeds inside an if scope:

  1. The assumed statement's value is flipped (by the schemas of the enumeration type(bool = false | true), from which the lemma is proved)
  2. The flipped statement becomes proven in the outer scope
  3. The if scope typically immediately closes (as continuing within a contradictory scope is pointless — from a contradiction, anything can be proven)
⚠
The if command must have exactly one statement for contradict to flip it: the axiom of the lemma asks for an if of one condition. Multiple statements in one if cannot be flipped at once.

↗

lock

Creating axiom scopes for theorems

Overview

The lock() command creates a scope for axioms. Axioms defined within a lock act as parameters that must be "realized" when the theorem is called (T[… | R]).

+lockLabel: lock() { ... }+lockLabel: lock(); // a declaration to the end of the enclosing block
lockLabel
The label axiom(| lockLabel, …) adds axioms through. The lock takes no arguments.
{ … }
Where the axioms hold: everything proved inside is a theorem under them, and a call applies it elsewhere only with a realization of each axiom.

Command Properties

Group
Context
Produces
Nothing itself — axiom adds statements to it
Delivery & Label
A label is required (+𝒜: lock()): axiom(… | 𝒜) names the lock by it.
Creates scope
Yes.
Mechanism
Opens a scope whose axioms are parameters of everything proved inside: a call of such a theorem from outside the lock needs a realization of each axiom it rests on — a proved statement of the same form — after |. Inside the lock the axioms are visible facts.

Basic examples

Lock with axioms

▶ Run

Why Lock?

A lock is a scope whose internal rules are defined by its axioms. Each axiom command registers a statement in the lock's axiom list — a record of all conditions that must be satisfied when the theorem is applied. You cannot create statements "from thin air"; every axiom belongs to a specific lock.

When someone calls a theorem, the interpreter inspects each lock's axiom list and requires a realization for every axiom written before the theorem — a proof in the current context that the axiom's statement holds. The realization is checked by signature: it may rely on the same conditions the axiom did, or on fewer (a realization proved under fewer premises is still sound), but never on more. If any axiom cannot be realized this way, the call fails. This is what makes theorems trustworthy: they cannot be applied in contexts that don't satisfy their premises. See signature matching for the precise rule.

ℹ
See axiom for how axioms are declared, and do for how realizations are matched.

Axioms hold within their lock. Closing the lock does not make them facts outside it. A realization used outside a lock keeps that lock's full contract; every premise must match the required scheme. An unconditional result needs a proof of its premises. For assumptions used throughout a file, keep their lock open to the end of the file.

The axiom Command

Inside a lock, use axiom to declare conditional axioms:

axiom(expression -> expression | lockLabel)

The lock label must be passed as the first argument. Axiom statements follow the same syntax as if statements.

Axiom requires lock label

▶ Run

Using Theorems with do

When you call a theorem proved in a lock, the interpreter checks that all axioms can be realized from the current proof context. See calls and Peano Arithmetic for full examples.

Nested Locks

A lock can contain another lock. This is a common technique for creating theorems that require axiom realizations containing their own inner axioms:

Nested locks

An inner lock inside an outer lock is a valid pattern for creating theorem templates.

▶ Run
ℹ
An axiom realization (the code that provides the axiom when calling the theorem) may itself cross lock() nodes. The interpreter will verify, by comparing signatures, that every axiom of every lock on the realization's path is matched by a corresponding lock axiom on the theorem's side. See Lock axioms: signature matching for details.

Sealing a Lock

After all axioms have been defined, you can undeclare the lock label to prevent any further axioms from being added. Existing axioms and theorems built on them remain fully functional — only the ability to call axiom with this label is removed.

Sealing a lock with undeclaration

After -𝒜;, the lock is sealed — no new axioms can reference it.

▶ Run

Boundary Rules

Locks act as boundaries for calls that take the blocks their proof stands in: such a call takes for and if blocks only, never a lock (or a type / rule) — a result proved under a lock leaves it only as a theorem whose axioms a call realizes.


↗

axiom

Declaring conditional axioms in locked scopes

Overview

The axiom command declares statements inside a lock() scope. These axioms act as parameters — when the theorem is called, T[… | R], the axioms must be realized by the current proof context.

axiom(statement1; statement2; … | lockLabel)
lockLabel
The label of the lock() the axioms belong to; the axiom command is inside that lock (possibly under for, if and other locks — they become the axiom's own context).
statement1; …
The axioms, written as statements left -> right (or without -> with notation("default", …)). A theorem proved under the lock needs a realization of each of them wherever it is called.

Command Properties

Group
Context
Produces
Statements (axiom declarations within a lock scope)
Delivery & Label
Into the current scope. Additionally registers each axiom in the lock's axiom list (for later matching by calls). A label on axiom captures the declared axiom statements at this scope.
Creates scope
No.
Mechanism
Reads the statements, creates them, delivers them to the current scope, and registers each in the lock label's axiom list. If the axiom is inside if command (between the current scope and the lock), those conditions become part of the axiom's requirements when matched by a call.

Basic examples

Axioms are always declared inside a lock and reference the lock's label:

Basic axioms

▶ Run

Details

Axioms hold within their lock. Closing the lock does not make them facts outside it. A realization used outside a lock keeps that lock's full contract; every premise must match the required scheme. An unconditional result needs a proof of its premises. For assumptions used throughout a file, keep their lock open to the end of the file.

Conditional Axioms

When an axiom is inside an if command, it only takes effect when that condition holds. This is how you create theorems with preconditions:

Conditional axiom

▶ Run

Axiom Label Requirement

The first argument must be a label declared on a lock(). This ensures axioms are properly scoped:

Label requirement

The lock label must be the first argument to axiom

▶ Run
ℹ
Axioms are the mechanism for creating parameterized theorems. Without axiom and lock(), all statements would be unconditional.

Why Axioms Need a Lock

Every axiom must reference a lock label. This is not a technicality — it reflects a fundamental design principle. A lock is a scope whose internal rules are defined by its axioms. You cannot create a statement "from thin air" with axiom; you must specify which lock this axiom belongs to.

Each axiom is registered in its lock's axiom list. This list is what a call inspects when applying a theorem: for every axiom that stood in the lock when the theorem was proved (an axiom written later is no obligation of it), the call must find a matching realization — a proof in the current context that satisfies the axiom's statement (and its if-conditions). If any axiom cannot be realized, the call fails.

Think of it this way: a lock says "these are the rules of my world", and each axiom adds a rule. When someone calls the theorem, they must prove that every rule holds in their world. This is what makes theorems trustworthy — they cannot be applied in contexts that don't satisfy their axioms.

💡
Once all axioms are defined, you can seal the lock by undeclaring its label (-𝒜;). This prevents any further axiom calls while keeping existing axioms intact. See Sealing a Lock.
ℹ
See lock() for more on lock semantics, and do for how axiom realizations are matched.

↗

rule

Rules of the logic: definitions by unique existence, bijections

Overview

The rule command declares the two rules of the logic that generate axiom schemes: rule("define", ∃!, ✔) says which atom means «there exists a unique», so that define(f | T) may define an operation from a proved unique existence; rule("bijective", f) says that a function between two enumerated types takes every value once (rule("bijective")). Each is part of what you trust. Everything else that shapes a step is written in the file as theorems and named: an enumeration type(𝔹 = ❌ | ✔) carries the schemas of distinct values and of cases, and the library proves from them the lemma contradict that closes an assumption by a contradiction (logic/bool.fl); the axioms of a quantifier or an implication are ordinary axioms of a lock (A∀Apply, generalize in logic/quantifiers.fl), and the steps are calls of them — generalize[| H], deduce[| H], obtain[| H]; the theorem a call on a quantified fact or a hint uses is named by notation("apply" | A∀Apply) and notation("hint" | …), which generate nothing.

rule("define", quantifierExpression1, …; truthExpression)rule("bijective", functionAtom1, …)
quantifierExpression1, …
define: the quantifiers «there exists a unique» — atoms of type [[T -> V] -> V] (∃!).
truthExpression
The value of a true statement of the quantifier's type (true, ✔).
functionAtom1, …
bijective: functions f: [D -> C] between enumerated types of one size, each declared a bijection.

Command Properties

Group
Context
Produces
Nothing — rule configures the proof system but does not produce statements
Delivery & Label
Into itself. A label on rule holds the schemas the declaration generates (a package to pass to a call); only +Label: syntax is allowed (declaration), Label: (definition without +) is an error.
Creates scope
Yes.
Mechanism
Parses the first string argument as the rule name, checks the types of the atoms given, and generates the axiom schemes of the rule in a lock of its own.

Basic examples

A bijection between enumerations

The rule says that color is a bijection: no two houses have one colour, and every colour is in some house. decide finds the values from the facts by the schemas of the enumerations and of the rule.

▶ Run

Details

Rules are part of what you trust — a false rule is as dangerous as a false axiom, and tools/trust.py lists the rules every theorem relies on. Everything that only changes how text is read (operators, abbreviations, default values, the theorems of steps) is notation, not a rule. Types and locks used to be rules too; they are now separate commands — type() and lock() — and they share the label and boundary behaviour described below.

Available Rules

RulePurposeDetails
define Quantifiers «there exists a unique» that allow define(f | T) rule("define")
bijective Functions between enumerated types that take every value once rule("bijective")

Before step 189в the rules contradict, apply, generalize, deduce, obtain, witness and equality generated the axiom schemes of the steps of a proof. Now these axioms are written in the file, where a reader sees them (Command Reducibility), and the steps are calls; nothing is generated and nothing is hidden.

Labels on rule, type and lock

A label on rule (and likewise on type and lock) does not capture any statements proved under it. A label on a rule or an enumeration holds the schemas the declaration generates — a package, +ABijective: rule("bijective", color), +AColor: type(Color = red | green) — and a call takes from a given package the schema each lock axiom of the theorem needs (Rules on the theorem's path): contradict of the library is proved by A𝔹[| A𝔹[_, P, ❌ | AX]], the schemas of cases and of distinct values of +A𝔹: type(𝔹 = ❌ | ✔).

As a lock label for axiom

When a label is placed on lock(), it can be used as the first argument of axiom to register axioms within that lock. This is the only way to create axioms:

Label on lock for axiom

▶ Run
⚠
Only +Label: (declaration) is allowed on rule, type and lock. Using Label: (definition without +) is an error, because these commands produce nothing to define with.

Boundary Role

Any rule, type or lock command acts as a boundary: a call that takes the blocks its proof stands in takes for and if blocks only, never one of these — a result proved under a rule or a lock rests on its schemas or axioms, and leaves it only as a theorem whose axioms a call realizes.


Transparent headers

↗

import

Using another file as a context

Overview

The import command makes the contents of another .fl file a context for the code that follows — exactly like for or if make their atoms or assumptions a context. Types, atoms, assumptions, rules, locks and labels of the imported file are visible inside the import, and nowhere else.

import("filePath");import("filePath") { ... }import("filePath1") import("filePath2");import("theoryFilePath", typeParameterName := argumentType, parameterAtomName := functionExpression, otherParameterAtomName := argumentExpression); // interpretationimport(namespaceName := "theoryFilePath"); // namespace: namespaceName.memberNameimport(namespaceName := "theoryFilePath", typeParameterName := argumentType, …); // interpretation in a namespace
"filePath"
The file to import, relative to the importing file; by default only inside its directory, the project root (formall.project) and --import-root directories. Its theorems and declarations become visible here; it is checked once, as a module.
typeParameterName := argumentType, …
An interpretation: the theory's type parameters, atoms and axioms are given values here (G := ℤ, ∘ := +, e := 0); its axioms must then be facts here, and its theorems hold for these values.
namespaceName := …
Optional: everything the import brings is visible as namespaceName.name (an operation as a namespaceName.+ b), so two imports of one theory do not clash.
{ … }
Optional: the imported content is visible only in the block. Without it, the code after import is at the top level of the file.

Command Properties

Produces
Nothing by itself — the imported file's commands produce their statements as usual
Delivery & Label
No label is allowed on import.
Creates scope
Yes. import("f.fl"); is a declaration: it lasts until the end of the enclosing block or file. import("f.fl") { ... } limits it to the braces.
Mechanism
The module's checked result — its block tree with statements, labels and rules — is loaded from its object as children of the import node (the file is checked first if needed). Whatever is open at the end of the file — its declarations — stays open: the code after import continues at the top level of the imported file.

Basic examples

A file is a context

Suppose bool.fl declares a type and two atoms:

bool.fl

▶ Run

Then importing it gives the same context as writing its text in place:

Two equivalent programs

The full code is the second program: the text of bool.fl in place of the import.

▶ Run

Details

An imported file is a module: it is checked on its own, as a main file, and sees only what it imports itself — not the file that imports it. Each module is checked once; its result is kept as a module object and loaded by later runs.

Modules

A module declares what it needs (usually by importing other modules) and then states its theorems at its top level. Everything the module declares at the top level — atoms, assumptions, locks, labels — is visible to the importer. The proofs themselves stay in their blocks; their results are reached through labels, as usual:

theory.fl

The full code inlines bool.fl.

▶ Run

Using the module

The full code inlines theory.fl (and bool.fl through it).

▶ Run

Projects of several files

Each module imports what it needs: a module cannot use a name of the file that imports it. If a file is already imported in an enclosing context (on the same path of the scope tree), a repeated import is skipped with a notice and its names are shared — so "diamond" dependencies work naturally. An import cycle is an error.

main.fl

The repository contains a library built this way (tests/08_corpus/library): common logic, set theory, Peano arithmetic and the Einstein puzzle; the set theory produces exactly the same statements as the single-file version.

Module objects and the cache

There is no separate build step: run formall main.fl. For every imported module the interpreter finds its object in the cache and checks that it is current: the module's text, the files it read and the objects of its own imports are unchanged, and so is the interpreter. A module that is not current is checked again — in a child run, as a main file — and only such modules: after an edit of one file, the files that import it are checked again, the rest of the project is loaded. The results are the same as without the cache; reports (--log, --statements, --certificate-journal …) describe the main file, while --trust covers the theorems of all modules.

  • Where. In a project — a directory with a formall.project file — the cache is the directory .formall next to it. Paths inside are relative to the project, so the project can be moved or copied together with its cache. Without a project the cache is ~/.cache/formall ($XDG_CACHE_HOME/formall); --cache DIR or $FORMALL_CACHE choose another directory. The cache can be deleted at any time. Stale modules are compiled in parallel (-j N; by default as many as there are processors).
  • Errors. An error in a module is reported with its file and position, followed by the place of each import that led to it.
  • Interpretations are instances of the theory's object (below): an interpretation of a large theory costs about as much as loading it.

Interpretation: a theory in another model

A theory proved once can be used for every structure that satisfies its axioms. The second argument of import is a substitution: import("group.fl", G := Z2, ∘ := ⊕, e := 0, ⁻¹ := −) reads the theory of groups with its parameters replaced by the model — this is interpretation in Isabelle and an instance in Lean.

  • Parameters. A type of the theory named in the substitution becomes the model's type — a named type or a compound one: Point := [Axis -> ℝ] makes the points of a theory functions from axes to numbers (library/geometry/real_space.fl); an atom becomes the model's expression of the same type — an atom (⊕), a constant (0) or a λ (⁻¹ := {x: Z2 | x}). The theory's operator notation stays with the theory's text (a⁻¹ is read as −(a)), the model keeps its own.
  • Axioms are obligations. A top-level if of the theory's files that speaks about the substituted parameters and about nothing new of the theory must already be a fact of the model, the same statement after the substitution; it is not assumed again, and the theory's label of the axiom points to the model's fact. A missing axiom is an error. The kernel checks the same where the import is written: the file's certificate applies the theory's axiom to the model's values with the model's fact for it, so that the fact is the axiom after the substitution, whether or not a theorem of the instance is used later. An assumption that mentions something the theory itself introduces stays an assumption, as with an ordinary import: the condition of a theorem about its own atoms (for(a, b) if(a + b = 0) T:: …), the definition of a new constant (for(2) if(2 = S(1))), an axiom of a new notion (the order of the indices of sequences). A top-level if closed by a call that takes it (contradict, deduce, obtain) is a step of a proof.
  • The theory is checked once. The theory is a module: its proofs were checked for arbitrary parameters when its object was built. The interpretation is an instance of that object (as an instance in Lean): every statement, definition, abbreviation and rule of the theory and of the modules it imports that declare a parameter is copied with the parameters replaced by the model's values — proofs are not checked again, and a new constant of the theory (define) gets a copy of its own. The theory's theorems become available for the model: InvMul[] now gives − b ⊕ − a = −(a ⊕ b).
  • The names of the parameters (G, ∘, e) are not declared by the instance; they do not hide the model's names.
  • Axioms of a lock are not obligations. A theory written without if, with its axioms as axiom(L, …) in a lock (the style of reducibility), is imported as well, but the import checks nothing against the model: the theorems stay inside the lock, and every call realizes its axioms with the model's facts — RightInv[| ZA, ZI, ZV], as with an ordinary import of such a theory. This is sound, only the check «the model satisfies the axioms» moves from the import to each use.

An optional condition of a theorem can mention only the model parameters, without mentioning that theorem's own arguments. Put such a condition inside the theorem's explicit body. A file-level header chain treats a condition about substituted parameters as an obligation of the interpretation. For example, the convergence library puts nonemptiness of base sets inside its uniqueness proofs; its sum proof and the import itself do not require that extra condition.

type(Z2 = 0 | 1);
for(⊕: [Z2, Z2 -> Z2]; −: [Z2 -> Z2]); …
// the axioms of a group for Z2 — proved by cases: ∀{a, b, c: Z2 | a ⊕ b ⊕ c = a ⊕ (b ⊕ c)}, …
import("algebra/group.fl", G := Z2, ∘ := ⊕, e := 0, ⁻¹ := −);
for(a, b: Z2) InvMul[];   // − b ⊕ − a -> −(a ⊕ b)

The library uses the same mechanism in library/analysis/real_sequences.fl: natural indices inside ℝ supply the index type and order required by library/analysis/sequences.fl. The obligations are proved before the theory is imported. To interpret a theory twice in one file, or next to its ordinary import, give each interpretation a namespace; otherwise its theorem labels clash.

What a transferred theorem proves

Interpreting theory A in theory B proves the translated theorems of A inside B. The proof must establish the required axioms of A for the chosen type and operations. The resulting theorems retain the assumptions used to establish those facts. Changing names does not remove assumptions.

For example, library/reals/naturals.fl constructs natural numbers inside ℝ, and library/reals/peano.fl interprets the Peano theory on that type. It also proves that the imported addition and multiplication agree with the operations inherited from ℝ. These operation identities let an arithmetic theorem be written in either representation.

The reverse question has two parts. A proved correspondence between two number representations can translate a statement back to the original representation. To obtain a proof from Peano assumptions alone, the proof must also avoid extra real-number assumptions, or those assumptions must themselves be justified in the target theory. An embedding, even an isomorphism, does not by itself establish this independence.

In practice, write a reusable theorem with the weakest assumptions its proof needs, then prove those assumptions in each model. Use a proved correspondence to translate operations and predicates when the models have different representations. A subtype supplies membership and an injective embedding; it does not supply a general reverse transfer procedure. tools/trust.py helps inspect the assumptions of a particular theorem, while show displays its contract.

The Peano module uses induction quantified over predicates of type [ℕ -> 𝔹]. Its axioms should not be silently identified with the first-order induction schema of textbook PA when discussing logical strength or independence.

Namespaces

The last argument of import may be a prefix: import(R := "reals/main.fl"). Everything the import brings — types, atoms, values of enumerations, operators, abbreviations, labels — is visible after it only with the prefix: R.ℝ, R.sup(X), R.TArchimedes[]. An operator keeps its notation and is written with the prefix too: n N.+ N.1. Inside the theory's own files the names are plain. Without a prefix, import works as before.

import("logic/uniqueness.fl");             // shared logic: ∀, =, ∃! — one for both theories
import(N := "peano/main.fl");              // N.ℕ, N.S, N.+, N.T➕Associative, …
import("reals/main.fl");                   // ℝ, +, ×, 0, 1 — without a prefix
for(x: ℝ) L0Add[x];                // 0 + x = x
for(m, k: N.ℕ) N.T➕Associative[m, k, m];   // m N.+ (k N.+ m) = m N.+ k N.+ m
  • Why. Both Peano arithmetic and the reals declare +, ×, 1, <. Without a prefix the later import hides the earlier names: the theorems of Peano stay true (their atoms are different), calls still apply them, but the sum of two natural numbers can no longer be written. With interpretations, a prefix lets one theory be read for two models (import(A := "group.fl", G := Z2, …) and "B"), or for a model next to the ordinary import of the same theory (the reals and their copy C: C.TWeierstrass).
  • The prefix covers everything the import brings, including the files it imports — unless they are already imported outside: a shared file (logic/…) is imported once, before the prefixed imports, and stays shared. A file imported only under a prefix has prefixed names everywhere: N.=, not =. An error on an undeclared name says when it is visible with a prefix.
  • Inside an interpretation, a file of the theory that is also imported ordinarily outside (it declares the parameters, like reals/language.fl) is read again for the model, not shared.
  • The same import with the same prefix again is skipped; an ordinary import after a prefixed one is a separate copy. A prefixed import without a substitution of a file already imported without a prefix is an error: it would be the same theory under other names.
  • Namespaces nest: a theory that imports another one with the prefix M, imported itself with O, gives O.M.name.
  • . is reserved for namespaces: it cannot appear in declared names of atoms, types, values and labels, nor in the prefix itself.

Rules

  • Paths are relative to the importing file (absolute paths are allowed too); spaces in paths are not supported. Only .fl files can be imported.
  • An imported file must be complete: balanced braces, closed comments, no unfinished command, label definition or trailing comma, and no trailing statement chain without ;. A trailing chain of scope commands is a declaration.
  • Files are walls in both directions: ; and } inside an imported file never close the importer's chain, and the importer's ; never closes the declarations of the imported file — they end together with the import.
  • import("f.fl") <…>; — an import followed by a statement in the same chain ends with that statement.
  • import cannot be an argument of another command and cannot carry a label.
  • Messages and statements from imported files show their position as file.fl:line:column.

Security

By default the interpreter imports only files inside the directory of the main file and inside the project root — the nearest parent directory containing a formall.project file (paths are compared after resolving .. and symbolic links). Command-line flags widen this: --import-root DIR adds an allowed directory, --allow-any-import lifts the restriction for trusted local use.

Running a project

The interpreter always gets one file; its imports are resolved and checked recursively. Any module of a project can also be checked on its own — it imports its dependencies itself, and the end of a file closes its declarations. The same file imported twice on one path of the scope tree (also via .., an absolute path or a symbolic link) is used once.


↗

notation

How text is read and printed: operators, abbreviations, default values, steps read through theorems

Overview

notation("kind", …) collects everything that changes only how the text is read: writing atoms as operators, names for formulas, the default right-hand side of a statement, and which theorems a step of a proof — a call that removes a quantifier, generalize, deduce, witness, obtain, a hint by a fact of a relation — is read as calling. A notation never makes anything true.

notation("infixl" | "infixr" | "infix" | "prefix" | "postfix", operatorAtomNames, precedenceInteger)notation("abbreviation", abbreviationName := expression)notation("default", defaultExpressions)notation("alias", shortName := Namespace.Prefix)notation("apply" | applyTheorem) notation("generalize" | generalizeTheorem)notation("deduce" | deduceTheorem) notation("witness" | witnessTheorem) notation("obtain" | obtainTheorem1, …)notation("hint" | rewriteTheorem, rewriteBackTheorem, reflexiveTheorem)
kind
What the notation is: an operator (infixl, infixr, infix, prefix, postfix), a name for a formula (abbreviation), the default right side of statements (default), a short name for a namespace (alias).
operatorAtomNames
Atoms (comma-separated) to write as operators — two-argument for infix kinds, one-argument for prefix and postfix. Infix operators need spaces around them: a ∘ b.
precedenceInteger
The binding strength, as in Lean: a higher number binds tighter (+ 65, × 70, = 50, ¬ 40, postfix 1024).
abbreviationName, expression
The name and the formula it stands for; a function is written as a constructor {x: T | e}. See below.
defaultExpressions
Values, at most one per type: a statement without -> in if/axiom gets the value of its type. See below.
shortName, Namespace.Prefix
Write shortName.x for Namespace.Prefix.x. See below.
| theorems
For a step: the labels of the theorems the step calls. The quantifier, implication or relation and its values are read from their forms. See below.

Command Properties

Produces
Nothing; no label can be put on it
Creates scope
Operators — wherever the atom is visible, from this point on; abbreviations and default values — in the enclosing block after the command
Mechanism
A transparent header: it can stand in a chain (for(∘: [G, G -> G]) notation("infixl", ∘, 70) if(…) { … }) or end with ;

Basic examples

Any visible atom of two arguments can be written between its arguments, and an atom of one argument before or after it. notation("infixl", ∘, 70) makes a ∘ b ∘ c mean ∘(∘(a, b), c); statements are then also printed this way, with parentheses only where they are needed. The notation is pure syntax: the parser turns a ∘ b into ∘(a, b), so proofs, the journal and the independent checker do not change. The prefix form ∘(a, b) stays valid, and an operator can still be passed as an argument: f(=, x).

notation("infixl", ∘, 70) // left-associative: a ∘ b ∘ c = (a ∘ b) ∘ cnotation("infixr", ⇒, 25) // right-associative: a ⇒ b ⇒ c = a ⇒ (b ⇒ c)notation("infix", =, 50) // non-associative: a = b = c is an errornotation("prefix", ¬, 40) // ¬ anotation("postfix", ⁻¹, 1024) // a⁻¹notation("infixl", ∪, ➕, 65) // several operatorAtomNames with the same fixity

Command Properties

Produces
Nothing; the atoms are written as operators wherever they are visible, from this point on
Mechanism
The expression parser reads operators by precedence (Pratt parsing) and passes the prefix form to the core parser.

Spaces

An operator is separated by spaces, as in Agda: a ∘ b is three names, a∘b is a single name. This keeps names like L➕1 or ∀𝔹 intact and lets an editor split the text into tokens without knowing the declarations. Parentheses need no spaces: (a ∘ b) ∘ c, ¬(a ∧ b).

Prefix and postfix operators may be glued to their operand: a⁻¹, ¬¬p, −a!, f(x)⁻¹⁻¹. A name that is not a visible atom is split into prefixes, a core and postfixes; the core is a visible atom without notation or a bound variable, and the result is parsed by precedence as if spaces were there. The split happens only where the name would otherwise be unknown: a declared atom a⁻¹ stays one name. If a name splits in more than one way (postfixes ! and !!, text a!!!) it is an error, and spaces decide. Infix operators are never split. The interpreter prints a prefix or postfix glued — a⁻¹, −ε, n!, (a ∘ b)⁻¹, ¬¬p — when the glued text reads back the same: the operand has no spaces outside parentheses (otherwise ¬ ι(p) ≤ x would look like (¬ι(p)) ≤ x), the glued piece is not a visible atom, it splits in exactly one way, and the junction does not spell another operator of the same kind (with an atom c! and postfixes !, !! the term c! ! is not printed c!!). Otherwise it keeps the space: a !!. Infix operators are always printed with spaces.

Precedence

The precedence is an integer 0–1024; the greater binds tighter. The scale is the one of Lean 4 and Isabelle, so that the same numbers can be used: ⇔ 20, ⇒ 25, ∨ 30, ∧ 35, ¬ 40, = ∈ ⊂ 50, ∪ + 65, ∩ * 70, ^ 75, ⁻¹ 1024. Application f(x) binds tighter than any operator. A prefix operator takes as its operand everything that binds at least as tight as itself: with ¬ 40, ¬ a ∧ b is (¬ a) ∧ b and ¬ a = b is ¬ (a = b), as in Lean.

Example

A group in operator notation

The library of the repository (tests/08_corpus/library) is written this way: in its expressions there are 2.5 times fewer parentheses than in the prefix form, and the proved statements are exactly the same.

▶ Run
💡
An atom gets a notation once; it is a property of the atom, visible together with it (also from imported files). The same names cannot be used for both a prefix and an infix operator.

Details

None of it is logic — the core, the journal and the independent checker never see it. That is why notation is transparent: it may stand in a chain of headers or end with ;, but unlike rule, type, lock, for and if it is not a context — calls pass through it, and theorems get no parameters or conditions from it. Rules of logic, which generate axiom schemes and are part of what you trust, are declared separately with rule.

Steps read through theorems: notation("apply" | …), notation("hint" | …)

A call on a fact H[a] removes a quantifier, a fact a = b rewrites a to b. Neither step is built into the language: each is a call of a theorem, and the file says which. notation("apply" | A∀Apply) reads «a call removes ∀ through A∀Apply»; the quantifier ∀ and the values come from the form of the theorem, not from arguments. The declaration states nothing, so it is a notation, not a rule: a theorem of another form is an error that names it. The other steps name their theorem themselves: the introduction of a quantifier or an implication, the elimination of an existential and the closing of an assumption are calls that take the blocks their proof stands in — generalize[| H], deduce[| H], obtain[| H], witness[t | L], contradict[| H] (logic/quantifiers.fl, logic/propositional.fl, logic/bool.fl); nothing is generated (Command Reducibility).

NotationThe theoremThe step it reads
notation("apply" | Apply)p(x…) -> c under if(Q(p) -> d), over p, x…H[a] on a fact Q(p) -> d: p(a) -> c; a hint <e | H> by such a fact
notation("hint" | Rewrite, RewriteBack, Reflexive)a -> b and b -> a under if(R(a, b) -> v); R(x, x) -> va fact R(l, r) -> v as a hint (notation("hint"))

The steps of a theory named by its own theorems

The library (logic/quantifiers.fl, logic/propositional.fl, logic/equality.fl) is written this way: notation("apply" | A∀Apply), notation("hint" | A=Rewrite, L=RewriteBack, A=Reflexive), and the calls generalize[| H], deduce[| H], obtain[| H], witness[t | L]. Its only rules are rule("define", ∃!, ✔) and rule("bijective", …).

▶ Run

A theorem of the wrong form

Without the condition ∀(p) -> true the axiom would say p(x) -> true for every p, much more than Apply, so the notation refuses it.

▶ Run

Expected error: notation("apply"): the theorem 'Wrong' must lie under one if(Q(p) -> d), Q a quantifier

Abbreviations: notation("abbreviation")

Long formulas often repeat: "t is empty" is ∀{z: set | not(in(z, t))}, written a hundred times in a proof. notation("abbreviation", empty := {t: set | ∀{z: set | not(in(z, t))}}) gives it a name. Wherever empty(x) is written afterwards, the parser puts the expression in its place (the lambda is applied to the arguments, with fresh bound variables). No atom and no axiom appear: statements are exactly the same as with the formula written out, so nothing has to be unfolded in proofs. This is abbreviation in Isabelle and notation in Lean. Unlike define, which introduces a new atom with a defining theorem, an abbreviation is pure syntax.

notation("abbreviation", abbreviationName := {boundAtomName: type | expression});notation("abbreviation", abbreviationName := expression);
abbreviationName
The new name: name(a) (or just name for a term) is replaced by the formula while the text is read.
{boundAtomName: type | expression}
A formula with arguments: the bound atoms are its parameters, the expression its body. A formula without arguments is written as an expression.

Command Properties

Produces
Nothing; the name is visible in the enclosing block after the command, like an atom declared by for
Mechanism
Expanded by the expression parser: name(a) becomes the lambda applied to a and is β-reduced. Statements are printed expanded.

Example

Naming a formula

In library/sets/pairs.fl of the repository two abbreviations replaced 169 occurrences of these formulas: the file became a quarter shorter, and its statements did not change.

▶ Run

Printing folds abbreviations back. The checker sees only the expanded formula, but statements, messages and show print it with the name: an expression that matches the body of a visible abbreviation is printed as name(arguments), as Isabelle prints abbreviations. A parameter-function applied to bound variables is matched as a Miller pattern: with notation("abbreviation", everywhere := {f: [T -> T] | ∀{i: T | p(f(i))}}) the formula ∀{i: T | p(g(i))} prints as everywhere(g) and ∀{i: T | p(g(s(i)))} as everywhere{i: T | g(s(i))}. An abbreviation declared in a block folds only inside that block. The interpreter flag --no-fold prints everything expanded.

💡
Choose bound variable names in an abbreviation that do not occur as atoms where it is used: the meaning is always right (atoms are distinct internally), but the printed statement is easier to read.

An abbreviation written as an operator

An abbreviation of one or two arguments can be given an operator notation like an atom. Strict order defined through ≤ is the typical case: a < b is then literally ¬ b ≤ a, so decide and the rules see through it, and no lemmas «from < to ¬ ≤ and back» are needed. With define instead, a < b would be a new atom and every passage between the two forms a rewriting by the definition.

Strict order as an abbreviation

Statements are printed with the abbreviation expanded: ¬ z ≤ x -> true. In the real numbers and limits of the repository (library/reals/, library/analysis/) this replaced two lemmas and 25 of their uses.

▶ Run

Default values: notation("default")

Most assumptions and axioms say that something is true: if(x ∘ y = e -> true). notation("default", true) lets you write just if(x ∘ y = e): in if and axiom a statement without -> gets the default value of its own type as the right-hand side.

notation("default", defaultExpression1, defaultExpression2, …)
defaultExpression1, …
One value per type (✔; true, ∅): the right side given to a statement of that type written without ->.
  • Each value is the default of its type, at most one per type in one block: notation("default", true, ∅) makes if(p) mean p -> true for p: bool and if(a ∪ b) mean a ∪ b -> ∅ for sets.
  • It acts in the enclosing block after the command; the nearest declaration with a value of the type wins.
  • It is notation only: the statement is P -> true, and it is printed that way.
  • The arrow is searched up to the end of its group, so lists keep their meaning: if(p, q -> r) is still p -> r and q -> r, while if(p -> r; q) is p -> r and q -> true.
  • Without a default value of the type a statement without -> is an error.

In the repository library the rule stands next to the booleans, in logic/bool.fl: notation("default", ✔).

Example

Assumptions without -> true

Commands that check statements, such as expect(), are not affected: there a string without an arrow already means «the statement with this left-hand side».

▶ Run

Short names for namespaces: notation("alias")

Nested namespaces make long names: a construction imported as Reals that itself imports pairs as PairClasses and classes as Classes gives the type Reals.PairClasses.Classes.Class. notation("alias", R := Reals.PairClasses.Classes) lets the file write R.Class, R.classEmbed, R.SomeTheorem instead — for types, atoms and labels, in code and inside strings — like import … as R in Python.

notation("alias", shortName := Namespace.Prefix)
shortName
The short prefix to write (R).
Namespace.Prefix
The long prefix it stands for — a namespace of an import, possibly nested (Reals.PairClasses.Classes).
  • The alias is expanded while the text is read: R.x is the name Reals.PairClasses.Classes.x. Statements, the journal and the output show the full names.
  • It belongs to this file: imported files and files importing this one do not see it. Inside the file it acts in the enclosing block after the command, like an abbreviation.
  • The prefix must have visible names, and the short name must not already be a visible namespace.
  • The first argument of import, the file path, is left as written; the substitution string of an interpretation may use the alias.
import("real_numbers.fl");
notation("alias", R := Reals.PairClasses.Classes);
import(RealSpace := "../../geometry/coordinates/space.fl", Number := R.Class, + := Reals.⊕, …);
for(a: R.Class) { … }

In the repository library: sets/numbers/real_numbers.fl, sets/constructions/*.fl (C for PairClasses.Classes). A block that opens a namespace, so that its names need no prefix at all, is not part of the language.


Inference steps

↗

define

Naming a term, or an operation whose result is unique

Overview

define introduces a new atom together with what defines it. There are two forms, and both are conservative: nothing new can be proven about the old atoms, so a definition can never make a theory inconsistent.

+definitionLabel: define(atomName := expression)+definitionLabel: define(atomName | theoremLabel)
atomName
The name of the new constant.
expression
Its definition: a term (S(S(0))) or a function written as a constructor ({a, b: ℕ | e}). The defining statements say the constant equals it — in both directions.
theoremLabel
A proved unique existence ∃!{c: R | φ(c)} -> ✔ (with rule("define", ∃!, ✔)); the constant is that unique element, and the definition is φ of it. Under for atoms the theorem gives a function of them.
definitionLabel
Receives the defining statements, to use as hints and facts.

Command Properties

Produces
The defining statements (a theorem over the atoms of the definition)
Delivery & Label
The new atom is declared in the current scope (until the end of the block or file). The label receives the defining statements.
Creates scope
No.
Mechanism
Explicit form: the atom gets the type of the expression; for a function {a, b: T | e} the label holds the theorem name(a, b) -> e and e -> name(a, b) over a, b — call it or use it as a hint of a proof to unfold or fold. Unique-existence form: see below.

Basic examples

Explicit definition

An atom equal to a term can always be eliminated by substituting the term, which is why this is conservative.

Unfold and fold a definition

▶ Run

Definition by unique existence

An operation like the union of two sets is defined after it is proven that for any arguments the result exists and is unique. The language does not know which atom means «there exists a unique» — the theory declares it, as it declares the rules of its quantifiers:

Union of two sets

In the repository the set theory is built this way: define(∪ | T∪), define(∩ | T∩), define({} | T{}) for unordered pairs, and the Kuratowski pair as an explicit definition define(⟨⟩ := {a, b: 𝕊 | {}({}(a, a), {}(a, b))}).

▶ Run

The theorem must have the form Q{c: R | φ} -> v for a quantifier Q and value v declared by rule("define", …). Its for atoms become the arguments of the new operation, and its conditions stay: the defining statement can be used only where unique existence was proven. This is the theorem on functional extensions (J. Shoenfield, Mathematical Logic, § 4.6), the same principle as func … means … existence uniqueness in Mizar.

What the kernel sees

For the steps of a proof, define(f := …) is a for(f) block with a lock under it whose axioms are the definition: f(a) -> e and e -> f(a) for an explicit definition, φ(a, f(a)) -> ✔ (under the conditions of the theorem) for unique existence. Both blocks are declarations: the code after the command continues inside the lock until the end of the enclosing block. Inside the lock, a call finds the lock already assumed. Outside it, or when a call substitutes an atom that the definition mentions, an explicit definition is replaced by its body and its axioms become e -> e, given as statements proved there; an interpretation realizes them by the definition in its own copy. So a constant can never be detached from its definition: a definition made under for(x) does not survive a call with another value of x, and a call taking the blocks around a proof that mentions the constant cannot cross the lock.

The certificate kernel knows an explicit definition as a definition level: the constant with its value, and the defining statements as facts it checks to be true by unfolding the value. A result leaves the definition by the level's own rule, stated of the value. This is how Lean, Coq, Isabelle and HOL Light treat definitions; why it is conservative and how it compares is on Definitions in the Kernel. A definition by unique existence has no value: for the kernel it stays a for block with a lock, and how to leave it — with a function that satisfies it — is shown on Leaving a Block. The research behind the design is in docs/design/constants.md of the repository; subtypes work the same way (type).

Definitions and their requirements

A mathematical definition and a theorem can have different requirements. Include the requirements of a public notion in its defining predicate. For example, library/analysis/domains.fl defines functionLimitOnDomain(f,D,a,L) as both an accumulation-point condition on a and the epsilon-delta condition. The weaker helper satisfiesEpsilonDeltaConditionOnDomain names only the latter condition, which can hold vacuously. A fact about the public limit already supplies the accumulation-point requirement; its uniqueness theorem does not ask the caller to supply it again.

Extra assumptions needed by a particular theorem belong in that theorem's conditions. Requirements for an operation defined from unique existence remain on its defining equation: being able to write a well-typed expression does not establish those requirements. Check the exported contract with show, and document these distinctions beside the mathematical definition.

⚠
rule("define", …) is a statement of the theory: it says that the atom means «there exists a unique». Declare it only for such a quantifier.

Generators

↗

decide

Evaluation over finite types

Overview

Many steps of a proof are pure propositional logic: from iff(P, Q) -> true and P -> true follows Q -> true; from P -> true follows or(P, Q) -> true. Each such step can be a lemma applied by a call, but then every pattern needs its own lemma and its own name. decide(X) finds the value of X from the facts by the tables of its functions and writes the proof as ordinary commands. The same works over any enumerated type: a value of Color = red | green | blue left when the others are refuted, a law of a group of two elements checked for every value of its variables, the house left for a value in a puzzle.

decide(expression);decide(expression, otherExpression, …); // the same as decide(expression); decide(otherExpression); …decide(expression | factLabel1, factLabel2, …);decide(expression | factLabel1, factLabel2, …;); // only these factscontradict[| decide(expression)] theoremLabel[| decide(expression)] // as a proof in an argument<functionAtom(<expression | decide()>) |> // as a hint: decides its place<functionAtom(<expression | decide(| factLabel1, …)>) |> // its place, from these facts first
expression
The expression whose value to compute — of an enumerated type: 𝔹, or any type(T = c1 | … | cn) (X, not X -> ✔). Several, comma-separated, are decided in order; each sees the previous results.
factLabel1, …
Optional: the facts to use first — labels or commands that return statements. What they leave undetermined is found among the visible facts sharing atoms with the expression, as a call finds the conditions its proofs do not meet; ; at the end — only these. Each must be needed. Facts about the expression itself are never used.

Command Properties

Produces
X -> v, where v is the value X takes under every assignment of its atoms consistent with the facts
Delivery & Label
Like a proof: into the current block, a label before decide catches the result, and as a proof in an argument of a call its statement is that proof. Facts about X itself are not used, so contradict[| decide(X)] refutes an assumption about X.
Mechanism
Functions with tables are atoms of type [T1, …, Tk -> T] over enumerated types whose rows are visible as statements (or(false, true) -> true, next(red) -> green); = of a hint on two values of an enumeration is a table too (c = c is true, c = d false). Atoms of the problem are maximal subexpressions that are no such function — P, p(x), ∀{x | …}, k: Color; each has an enumerated type. A cell f(h) of a bijection is an atom bound to the other cells: two cells take no value together, every value stands in a cell. Facts are statements F -> c with a value on the right: from the labels if given, otherwise the visible ones that share atoms with X (transitively, up to 10 atoms; the cells of one bijection share). The interpreter checks all assignments and then writes the proof as ordinary commands, parsed inside the decide node (as import parses a file inside its node): a case analysis by the schemas of the enumeration, every branch closed by a fact refuted or by the value computed (below). The result is checked like a hand-written proof by cases, and the kernel does not grow.

Basic examples

Values from facts

The atoms may be any expressions of the type: decide(or(not(p(x)), p(x))), decide(∀{x: nat | q(x)}) from iff(∀{x: nat | q(x)}, R) -> true and R -> true.

▶ Run

Several expressions

A list of expressions is decided in order, exactly as separate commands decide(P); decide(Q);: each expression sees the results of the previous ones, and a label before decide catches all of them. This is how the parts of an assumption are taken out: for(p) if(prime(p) ∧ p ∣ d) decide(prime(p), p ∣ d). Nothing appears by itself: every result is written in the command.

▶ Run

Over an enumeration

The atoms, the functions and X itself may be of any enumerated type. A function over enumerated types with visible rows is evaluated by them, like a connective by its truth table; an atom of three values is split three ways. The cells of a bijection color: [House -> Color] (rule("bijective", color)) are evaluated together: the value left for a house, the house left for a value.

Three colours and three houses

The library proves the group laws of Z2 so: for(a, b, c: Z2) decide(a ⊕ b ⊕ c = a ⊕ (b ⊕ c)) with the table of ⊕ (algebra/z2.fl), and solves the Einstein puzzle from the refutations of values (puzzles/einstein_enum.fl).

▶ Run

Equality of values

An equality is the relation of a hint (notation("hint" | Rewrite, Reflexive); the library declares = so in logic/equality.fl): c = c is true by its Reflexive, c = d of two values false by their distinctness. A refuted value is such a fact: k = red -> false above an assumption if(k -> red) that led to a contradiction is what refute of the library delivers (contradict).

▶ Run

What decide is — and what it is not

decide is not a rule of the logic. It is a proof generator: it searches, writes text with if, calls of the schemas of the enumeration and proofs, and that text is checked by the kernel like any hand-written proof. So a mistake in decide can only make it refuse — it can never make a false statement pass. For the same reason a generator may in principle be as clever as one likes (up to a neural network that finds proofs by itself): only its output is trusted, after checking.

Today decide is a small and weak piece of automation. It is a brute-force search over the assignments of a finite abstraction of the formula: every maximal subexpression that is not a function with a table — P, p(x), a = b over an infinite type, ∀{x | …} — is an opaque atom with no meaning but its enumerated type. It is complete only in this narrow sense: if the selected facts determine X when the atoms are treated as independent variables over their types, decide finds the value. It is far from a general prover: Lean's decide and tauto cover the same ground, Isabelle's blast and auto go far beyond it.

Limits

  • Enumerated types only: X and every atom are of a type(T = c1 | … | cn) (𝔹 among them). At most 16 atoms, and at most 216 assignments of their values in the search.
  • Functions with tables are atoms of type [T1, …, Tk -> T] over enumerated types, with at most 8 arguments and at least one row visible as a statement (and(false, true) -> false). An application is evaluated by a row when one applies; when the rows are incomplete and none applies, the application is an opaque atom. An atom with no visible row is an ordinary function, and its applications are atoms. = is a table on two values of an enumeration only when a hint with a Reflexive theorem is declared for it.
  • Atoms are opaque and compared syntactically (up to renaming bound variables). No equality reasoning between atoms: p(c) and p(d) are unrelated even if c = d is a fact. No quantifiers: ∀{x | p(x)} and p(c) are unrelated. No arithmetic.
  • Facts are statements F -> c with a value c of F's type on the right: those of the labels if labels are given and, if they do not determine X and the list is not closed by ;, the visible ones that share atoms with X, transitively, while the total stays within 10 atoms — a needed fact beyond that is not taken, and the answer is «not determined». Rewritings a -> b whose right side is not a value are not facts. Facts about X itself are skipped on purpose (so that contradict[| decide(X)] refutes an assumption about X).
  • Closed formulas (only values and known functions) are evaluated with one empty assignment, using the same checked proof generator.
  • On failure it reports what it saw: assignments with different values of X, or the list of contradictory facts. Closing the labels with ; makes the search exact; when the closed facts do not determine X but the visible ones would, the error names those visible facts.
  • Every label passed must be needed: the proof keeps only the facts X needs, preferring the labelled ones, and a label none of whose facts is kept is an error, as in a call.

A case split by hand

A case split needs no command. Under P -> false write the step; after the branch closes, P -> true holds and the same step is written once more:

if (P -> false) contradict[| <…>];   // the branch P -> false: closed, so P -> true above it
contradict[| <…>];                   // now with P -> true

With a block, the block stands in the branch and again after it. For two atoms, the branch holds the split on the second one. When the branches only check the tables, one line does the same: contradict[| decide(G)] proves G by the tables and the split on its atoms, and the value found against the assumption on G closes it (logic/propositional.fl, puzzles/knights.fl). decide builds the tree itself: it chooses the atoms and their order, closes a branch as soon as a fact is determined by the atoms already split — P ∧ Q is false once P is false — and makes the determined parts facts from the bottom up, each by one row of its function's table, so taking one conjunct out of a conjunction of twelve needs a few branches, not 211. A branch that needs more than the tables (a call, a rewriting by a fact) is written by hand.

The tree is written once for the shape of the step, not for its atoms. The atoms become variables, the facts the step needs become conditions, and the tree proves a lemma: P(u) from P(u) ∧ Q(u) is the lemma «𝓅1 from 𝓅1 ∧ 𝓅2», proved where the enumerations, the functions and their tables are visible and applied by a call with 𝓅1 := P(u), 𝓅2 := Q(u). Another decide of the same shape — Q(w) from Q(w) ∧ P(v) in another theorem — applies the same lemma; so does one in a file that imports it. One row of a table with an unknown argument («𝓆1 -> false gives 𝓆1 ∧ 𝓆2 -> false») is a lemma of its own, shared the same way, and so is c = d -> false of two values. The cells of a bijection stay themselves in the lemma. The log says for each step whether its lemma is new or applied again. These lemmas have internal names: a program does not see them.

How automation is added to Formall

  • The machine reasons only in a generator command that you write for a goal you name (decide(X)). Other commands and calls never reason silently: no facts appear by themselves, no condition is accepted without a fact.
  • A generator's scope is a whole theory that can be stated in one phrase («tables over finite types»), not a list of cases that happened to be needed. Inside the scope it searches exhaustively or refuses with a clear message.
  • Stronger automation — equality reasoning (congruence closure), linear arithmetic, rings, propositional logic modulo such a theory — will come as separate commands with their theories stated, not as one more special case inside decide.

What decide writes

decide is not a new rule of the logic. It finds the value by trying all assignments, and then writes a proof by cases with the commands you already know; that text is parsed inside the decide node and checked like any other code. The proof always has the same shape:

  1. Split an atom by the values of its enumeration: a branch if(A -> c) B1: … per value, each proving the goal X -> v under its hypothesis, and the cases schema of the enumeration (type generates it) combines the branches: Bool[A, X, v | B1, B2] through the label of the type. A value of a bijection is split by the cells it may stand in, with the column schema of the bijection. Atoms that have a fact of their own (P -> true) have their value from the start and are never split.
  2. Close every branch as soon as the values chosen so far make a fact or X itself computable: <F(<A>, <B>)> rewrites each atom to its value in the branch and the functions by their tables. A fact refuted so gives the goal by ex falso — the distinctness schema of two values (Bool[F(A, B), X, v | <F(<A>, <B>)>], the fact F(A, B) -> w found at the point), or the injectivity schema of two cells with one value; X computed is the goal itself; a branch whose hypothesis is the goal is that hypothesis (B2: if(X -> v) {}).
  3. The branch labels and the lemma's own label are internal names (𝓑1, decide.…); below they are written as a program could, through the label Bool of the type.

For the first example above, if(iff(P, Q) -> true; P -> true) decide(Q) writes:

What decide(Q) writes

The same text as if(iff(P, Q) -> true, P -> true) decide(Q) generates, the schemas of the enumeration named through the label Bool of the type; the full code declares the connectives by their truth tables. P has a fact of its own, so only Q is split.

▶ Run

Modus tollens, if(imp(P, Q) -> true) if(Q -> false) decide(P):

What decide(P) writes for modus tollens

The text if(imp(P, Q) -> true) if(Q -> false) decide(P) generates.

▶ Run

A tautology with three atoms has no facts, so every branch is closed by X itself: eight branches, each <imp(<and(<imp(<P>, <Q>)>, …)>, …)> computing true, combined by the cases of the three atoms. The log shows the size of the generated proof: [ decide ] … // 0 facts, 3 atoms, 8 branches.

Because the result goes through if, the schemas of the enumeration and proofs, the kernel does not grow: the certificate of such a proof uses only the kernel's ordinary rules.

Labels first, then the visible facts; ; — only these

After | come the facts decide takes first. What they leave open is found among the visible facts, like the conditions of a call that its proofs do not meet: one rule for every |. A ; at the end of the list says «only these». It is needed where the visible facts must not be used — in a block whose assumptions contradict each other on purpose, or where a reader should see everything the result rests on.

Labels first, then the visible facts

The second decide is closed by ;: the error names the visible fact Q -> true that would decide it.

▶ Run

Expected error: with these visible facts it would be true (pass their labels or remove ';')

decide as a hint

In a proof, <e | decide()> rewrites e to its value decided from the visible facts — the propositional counterpart of a theorem hint. A hint is a proof, and a command whose expression is not written takes the place of the hint, as a call T[] infers what is not written; <e | decide(| H)> decides the place from the facts of H first, <e | decide(| H;)> from them alone (Hints are proofs). Standing alone, decide() has no place and is an error.

A hint and an argument

▶ Run
ℹ
If the facts do not determine the value, decide reports assignments that give different values; if the facts contradict each other, it lists them. Pass the facts as labels and close the list with ; to make the search exact.

Labels

↗

Label Commands (+, -, *, ^, expect)

Set operations on label collections and the check expect

Overview

Labels in Formall hold collections (packages) of statements. The standalone label commands +, -, *, ^ perform set-like operations on these collections. They take one or more arguments and produce a new collection of statements that can be captured by a label.

+(statementSource1, statementSource2, ...)-(statementSource1, statementSource2, ...)*(statementSource1, statementSource2, ...)^(statementSource1, statementSource2, ...)expect(left -> right; … | statementSource1, ...)expect(left -> right; …)
statementSource
A statement label or a nested command returning statements.
left -> right, …
expect only, at most one: the expected set, read as the statements of if (without -> — the value of notation("default")). Alone, it names visible statements: an error if one is not visible here, otherwise they are returned as a label.
+ − * ^ expect
Union, difference, intersection, symmetric difference of the sets of statements; expect checks that all sources are equal sets (an error shows the difference) and returns that set. Inclusion is written by composition: expect(| *(A, B), A).

Command Properties

Group
Labels
Produces
Statements (result of set operations on statement collections)
Delivery & Label
Into the current scope. A label on a label command captures the resulting statement collection at this scope.
Creates scope
No.
Mechanism
Processes arguments left to right. The first argument initializes the result (copied in full). Each remaining argument is combined using the set operation (+ union, - subtract, * intersect, ^ symmetric difference). Arguments are labels or commands returning statements.

Basic examples

Union: +(first, second, ...)

Initializes the result with the first argument, then for each remaining argument adds its statements to the result, skipping those already present:

Union of two labels

▶ Run

Subtract: -(first, second, ...)

Initializes the result with the first argument, then for each remaining argument removes from the result any statements that match:

Subtraction of labels

▶ Run

Intersect: *(first, second, ...)

Initializes the result with the first argument, then for each remaining argument keeps in the result only those statements that also appear in that argument:

Intersection of labels

▶ Run

Symmetric Difference: ^(first, second, ...)

Initializes the result with the first argument, then for each remaining argument performs a symmetric difference (XOR) with the accumulated result. For each statement in the current argument:

  1. If the statement exists in the result (as it was before processing this argument), it is removed.
  2. If the statement did not exist in the result, it is added.

After processing an argument, the result contains only statements that were in exactly one of the two sets. When there are more than two arguments, this process repeats — the next argument is XORed with the accumulated result, and so on.

Symmetric difference of labels

▶ Run

How It Works

Label commands process arguments left to right. The first argument initializes the result collection (copied in full, unaffected by the command symbol). Then each remaining argument is combined with the accumulated result using the set operation indicated by the command symbol.

With a single argument, all four commands produce the same result — a copy of that argument's statements. With multiple arguments, each one is folded into the result in order.

💡
The result of a label command is itself a statement collection that can be captured by a label: +L: +(A, B) declares L and fills it with the union of A and B.

Arguments

Each argument is a source of statements:

  • Label — a label name; uses the statements accessible from that label (filtered by scope visibility, so only statements reachable from the current scope are included)
  • Anything that gives statements in place — a proof <…>, a call T[…], a command (decide(X), expect(…), another label command)
  • The statements of expect — before the bar expect takes one set of statements, read as in if: expect(P -> true; Q -> false | L) checks that L holds exactly these; alone, expect(P -> true) checks that each is visible here

At least one argument is required. If no arguments are provided, the interpreter reports an error.

Statements Named in Place

Label commands work on proofs: labels and commands. To use a visible statement that no label holds, name it whole with expect: it checks that the statement is visible here and returns it as a label.

Statements named in place

▶ Run

Multiple Arguments

When more than two arguments are provided, the operation is applied sequentially — each argument is combined with the accumulated result from all previous steps:

Multiple arguments

▶ Run

Nested Label Commands

Label commands can be nested. The result of one command can serve as an argument to another, allowing complex set expressions in a single statement:

Nested label commands

▶ Run

Checking: expect

expect(A, B, ...) checks that all its arguments contain the same set of statements (brought to the current scope, ignoring order and duplicates). If they differ, it is an error that lists what is only in one side and only in the other. If they are equal, it returns that set, so it can be labeled and passed on like any label command.

Use it to state important facts explicitly instead of writing them in comments: a comment can silently become wrong, a check cannot.

What expect states, the independent kernel checks too: a statement of another file it names here (a fact of an imported module, a theorem of an interpretation at the model) is proved at this place in the file's certificate, by that statement's own proof applied here.

Explicit checks

▶ Run

A statements string in expect is the expected set — with labels beside it, it does not have to exist in the scope; there is one such string at most. Inclusion is expressed by combining expect with intersection: expect(*(A, B), A) means A ⊆ B.

Inclusion through intersection

▶ Run

Statement Equality

All set operations rely on statement equality to determine matches. Two label statements are considered equal when both conditions hold:

  • Their expression content is identical (same left-hand and right-hand sides)
  • They were defined in the same scope

This means two statements with identical text but originating from different scopes are treated as distinct entries. Union will not deduplicate them, subtract will not match them, and so on. This scope-awareness ensures that statements retain their provenance through set operations.

⚠
The symbols +, -, *, ^ are reserved in Formall and cannot be used in atom names.

Scope Visibility Filtering

When a label is passed as an argument to a label command, its statements are filtered by scope visibility. A statement visible here is a fact of this scope. A statement standing in a closed block inside the label's declaration scope is a theorem of that label (see Theorems keep their place) and is kept with its place. The receiving label holds it only when declared in a scope that encloses that place; otherwise the statement is considered foreign to it and is excluded (with a warning).

Scope filtering in action

Statements from sibling scopes are invisible. +(Collected) inside the second if can only see statements defined in its own scope branch.

▶ Run

This is why L:OtherLabel; (defining a label directly with another label) is not allowed — the filtering would happen implicitly, and the user might expect all of OtherLabel's statements to be copied. Using a label command makes the filtering explicit:

resultLabel: +(sourceLabel); // explicit: copy accessible statements from sourceLabel into resultLabel

Theorems keep their place

A statement proved inside for and if blocks and delivered to a label declared outside them is a theorem: its contract — parameters, conditions, lock axioms — is the path from its place to the label's declaration (as with T::). Label commands keep that place: +(T, S) holds both theorems with their own contracts, and a call applies each with its own conditions. Two theorems that look the same but rest on different conditions stay different statements, so -, *, ^ tell them apart. String arguments still find visible facts only: a theorem is given by its label.

Label commands with theorems

Both theorems have the same form, but different conditions: OnlyT needs not(y) -> false, the symmetric difference — y -> true.

▶ Run

A label on type or rule holds what the declaration generates — its schemas, each with its place (a package to pass to a call).

Augmentation vs. Label Commands

Label commands (+(A, B)) and augmentation postfixes (L+: cmd) use the same underlying set operations, but differ in how they are applied:

  • Label commands create a new collection from existing labels and statements. They are standalone commands that produce a result to be captured.
  • Augmentation postfixes modify an existing label in place by combining its current contents with the result of a command. They are part of the label definition syntax.

See Labels for details on augmentation postfixes.


Tools

↗

show

What is visible here: the scope, nearby facts, labels — and a search

Overview

show() prints into the log what one needs to know at this place: the enclosing for and if, the facts already there and what the labels hold. show("text") searches the visible facts and labels for a piece of text. Nothing is produced.

show()show("searchText")show(| theoremLabel)show("check", leftExpression -> rightExpression; …)show("facts", expression1, expression2, …)show("type", expression1, expression2, …)
()
The context here: visible atoms, types, assumptions, labels, rules.
"searchText"
Visible facts and labels whose text contains it.
theoremLabel
The contract of each conclusion of the theorem — what a call would require — without applying it.
"check", statements
For each statement: is it already a visible fact?
"facts", expressions
The visible facts with this left side.
"type", expressions
The types of the expressions.

Command Properties

Group
Tools
Produces
Nothing: no statements, no label (a label on show is an error). The command is a tool; the journal and the checker do not see it.
Delivery & Label
—
Mechanism
show(): the enclosing scopes of this file, inner first — the nearest if is marked «a call taking this if closes it» (contradict[| …], deduce[| …]), the nearest for «a call taking this for delivers above it» (generalize[| …], obtain[| …]); then the facts of this file, nearest first (at most 40), and the labels declared in this file. A label statement is printed as a theorem: the for and if between the place it was delivered to and the label declaration are its parameters and conditions. show("text"): every visible fact and label whose printed form (or name) contains the text, from all files. The search is literal: bound variables keep the names they were printed with (1 + x, not 1 + y).

Basic examples

Context and search

▶ Run

Contract and exact queries

▶ Run
ℹ
show prints into the log only. Remove it when the proof is done: it changes nothing, but the log of a finished file stays shorter.

Details

A Formall proof goes forward, so there is no «goal» as in tactic provers. What one needs to know before the next command is the place itself: which for and if enclose it (what a call that takes its blocks — contradict, deduce, generalize, obtain — will close or lift over), which facts are already there and which labels hold what. show() prints exactly this into the log, like the infoview of Lean. show("text") searches the visible facts and labels, including those of imported files — a quick way to find the name of a lemma.

Exact queries

show("check", P -> true) reports FOUND with the source statement or NOT FOUND. It uses the visible-statement lookup used by calls, including type-polymorphic statements. It does not rewrite, apply a theorem or infer a value: NOT FOUND means that the requested fact is not already available, not that it cannot be proved. The same statement-list syntax and default right-hand values as in if are accepted.

show("facts", P) lists visible statements whose left side is exactly P (up to bound-variable renaming and type-scheme matching), nearest first, with a count and at most 40 entries per expression. Unlike text search, it does not find occurrences of P inside other expressions. show("type", P, f) prints the type of each expression; neither query evaluates it.

show(theoremLabel) prints every conclusion and its own contract: atom and type parameters, assumptions, rules and lock obligations. Assumptions are checked as written against the current facts. This is a template inspection, without argument substitution, inference or checking lock realizations; it is not a verdict that theoremLabel[] will succeed or fail. Different conclusions may have different contracts.


Rules

Quantifiers

↗

rule("define")

Declaring unique existence: definitions of operations

Overview

define has two forms. An explicit definition define(f := {a: T | e}) needs no rule: the new atom is just a name for a term. A definition from a theorem define(f | T) introduces an operation whose value is described by a property, and this is allowed only for the quantifier «there exists a unique» declared by rule("define").

rule("define", quantifierExpression1, quantifierExpression2, …; truthExpression)
quantifierExpression1, …
The quantifier of unique existence ∃!: an atom of type [[T -> V] -> V], possibly polymorphic.
truthExpression
The value v of a true statement. Then define(c | T) with T: ∃!{x | φ(x)} -> v introduces c with φ(c).

Basic examples

An operation from unique existence

▶ Run

In the library the rule stands in logic/uniqueness.fl next to the general ∃!, so the set theory (∪, ∩, {}, 𝒫, A × B) and the reals (sup) define their operations the same way.

⚠
rule("define", …) is a statement of the theory: declaring it for ∃ (plain existence) would allow choosing a value that does not exist uniquely, and the theory could become inconsistent.

What the rule states

If for all ā under conditions H(ā) a theorem gives ∃!{c | φ(ā, c)} -> v, then a new operation f may be added with the theorem φ(ā, f(ā)) -> v under the same conditions. This is the theorem on functional extensions (Shoenfield, Mathematical Logic, § 4.6) and func … means … existence uniqueness in Mizar: the extension is conservative, so the rule is safe exactly when the declared atom really means unique existence.


Equality & functions

↗

notation("hint")

Facts of a relation as hints, through named theorems

Overview

notation("hint" | Rewrite, RewriteBack, Reflexive) lets a fact R(a, b) -> v of a relation R be a hint: a proof rewrites a to b by it, as if it called Rewrite[| F]. The relation and its value are read from the theorems themselves. Like every notation it states nothing: every step it allows is a call of one of the theorems it names, and the certificate says so. The other steps of a proof are named the same way — notation("apply" | A∀Apply), notation("generalize" | generalize), notation("deduce" | deduce), notation("witness" | witness), notation("obtain" | obtain, …) — see steps read through theorems.

notation("hint" | rewriteLabel)notation("hint" | rewriteLabel, rewriteBackLabel, reflexiveLabel)
rewriteLabel
Required: a -> b under one if(R(a, b) -> v), over the atoms a, b only. A fact R(l, r) -> v then rewrites l to r.
rewriteBackLabel
Optional: b -> a under the same condition. Without it a fact rewrites one way only.
reflexiveLabel
Optional: R(x, x) -> v over one atom. With it R(t, t) reduces to v by itself.

Basic examples

A relation of its own

▶ Run

Details

The three theorems are the axioms Reflexive, Rewrite and the lemma RewriteBack a file writes for its equality (Command Reducibility); here they are named: a fact, a quantified fact and a theorem whose conclusion is R(l, r) -> v rewrite by Rewrite and RewriteBack, a bracket without a hint uses the visible facts of the relation, R(t, t) is Reflexive. The library declares its equality this way: notation("hint" | A=Rewrite, L=RewriteBack, A=Reflexive) in logic/equality.fl, and equivalence the same way: notation("hint" | L⇔Rewrite, L⇔Back, L⇔Reflexive) in logic/propositional.fl, so a fact P ⇔ Q -> ✔ rewrites P to Q and back. Nothing about = or ⇔ is built into the language beyond what the theorems say.

Each theorem must hold one statement and be proved without locks or rules of its own, over atoms of one type; the theorems must be about one relation and one value. A theorem of another form is an error that names it.

One way only

Without RewriteBack the fact rewrites left to right only.

▶ Run

Expected error: No matching statement found for expression substitution


↗

rule("bijective")

Functions between enumerated types that take every value once

Overview

In grid puzzles every house has one colour and every colour is in one house. With enumerated types the first half is already there: color(2) -> red and color(2) -> blue contradict each other, and refuting all colours but one of house 2 gives the last one. rule("bijective", f) adds the second half for a function f: [D -> C] between enumerated types of the same size.

rule("bijective", functionAtom1, functionAtom2, …)
functionAtom1, …
Functions f: [D -> C] between enumerated types of the same size, each declared a bijection.

Basic examples

Row and column

The Einstein puzzle in the repository (library/puzzles/einstein_enum.fl) is solved this way in about a hundred lines of code: properties are functions color: [House -> Color], clues are conditional axioms, and the solution is a sequence of refutations.

▶ Run

Details

  • Injectivity. f(a) -> c and f(b) -> c with different values a, b of D contradict each other.
  • Exhaustion by column. When f(h) -> c is refuted (or h already has another value) for every h but one, f(k) -> c follows. By row, the values already taken by other houses are excluded too.

Both are schemas of the declaration — Injective and Column, axioms of a lock of its own — and decide works with them: the value of a cell is found from the facts about the other cells of its row and column, by the tables of the functions applied to it. A label on the declaration holds the schemas, to pass to a call of a theorem proved under another bijection. Like every rule, the declaration is an axiom of the theory: the function is a bijection.


Examples

↗

Boolean Logic

Propositional logic fundamentals

Overview

This example shows how to set up boolean logic in Formall and prove basic theorems like the law of excluded middle, De Morgan's laws, and double negation.

Basic Setup

Boolean setup

Complete boolean logic foundation

▶ Run

Law of Excluded Middle

For any proposition P, either P is true or not(P) is true:

Excluded middle

Proof that P ∨ ¬P is always true

▶ Run

Double Negation

not(not(P)) = P for any proposition:

Double negation

Proof that ¬¬P ↔ P

▶ Run

De Morgan's Laws

not(and(P, Q)) = or(not(P), not(Q)):

De Morgan

Proof of ¬(P ∧ Q) ↔ (¬P ∨ ¬Q) by case analysis

▶ Run

Tips for Boolean Proofs

  • Case analysis — use nested if to cover all combinations
  • Contradiction — assume the opposite and derive false and true for the same expression
  • Substitution — proofs with nested angle brackets chain substitutions
ℹ
For boolean types with only two values, proofs often reduce to checking all 2ⁿ cases.

↗

Peano Arithmetic

Formalizing natural numbers and proving 2+2=4

Overview

This example shows how to formalize Peano arithmetic in Formall — defining natural numbers, equality, addition, and proving 2+2=4.

Complete Proof

Full 2+2=4 Proof

Complete working proof that can be executed in the interpreter.

▶ Run

Step-by-Step Explanation

1. Equality Setup

We establish reflexivity (x = x), substitution (if x = y, we can replace x with y), and symmetry (if x = y then y = x) — all inside a lock scope so they work as reusable axioms.

2. Number Definitions

Each number is defined as the successor of the previous: 2 = S(1), 3 = S(2), 4 = S(3).

3. Addition Axioms

A➕1: adding 1 is successor (x + 1 = S(x)). A➕2: recursive step (x + S(y) = S(x + y)).

4. The Calculation

2 + 2
= 2 + S(1) // by definition of 2
= S(2 + 1) // by A➕2
= S(S(2)) // by A➕1
= S(3) // by definition of 3
= 4 // by definition of 4

Key Techniques Used

  • T=S[a, b] — Apply symmetry: if =(a,b) proven, get =(b,a)
  • A=I[a, b] — Apply substitution: if =(a,b) proven, enable a -> b replacement
  • A➕1[2] — Instantiate addition axiom with specific value
  • <...> — Chain substitutions together
ℹ
This proof uses lock() with axiom to create reusable equality theorems. The lock ensures axioms are verified when applied via do.

↗

Steps as Theorems

Contradiction, generalization, calls on facts and if, written as axioms and theorems of a file

Overview

Formall's core is four commands — type, for, lock, axiom — and two forms: proofs <…> and calls T[…]. The steps of a proof — contradiction, generalization, calls on quantified facts, and even if — are theorems about these primitives, not commands. This page shows each step twice: first with the theorem of the library, then with axiom-based theorems written in the file itself (and, in the final example, without if either).

The page was written when these steps were commands of the interpreter (contradict, generalize, apply) and showed that each is reducible to the core. Since step 189в the language is exactly this. There are no commands contradict, generalize, deduce, obtain, witness and no rules generating their schemes: an enumeration type(bool = false | true) writes the schemas of distinct values and of cases as axioms of a lock, the library proves contradict from them (logic/bool.fl), the axioms of the quantifiers and of the implication are written in logic/quantifiers.fl and logic/propositional.fl, and every step is a call — contradict[| H], generalize[| H], deduce[| H], obtain[| H]; a call on a quantified fact removes its quantifier through the theorem named by notation("apply" | A∀Apply). The independent kernel checks proofs with three rules — axioms, rewriting and applying a theorem (a call). The examples below keep the shape of the reductions as they were found: the «built-in» step is the library's theorem, written in the file.

Contradiction: contradict

Let's start with the most interesting case. We'll prove that if an implication is false, its consequent must be false: implies(P, Q) -> false implies Q -> false.

Using contradict

Contradiction with the library theorem

▶ Run

Using axiom-based contradiction theorems

To replace contradict, we define four theorem variants — one for each combination of assumption direction and contradiction direction. Each theorem encodes the logical conclusion directly as an axiom:

Axiom-based contradict — same proof without contradict

Each contradict is replaced by a call of the appropriate theorem. The realization label after the bar (e.g. A) provides the axiom realization: a label whose statements prove the contradictory statement under the given assumption.

▶ Run

Generalization: generalize

Let's prove that equivalent(x, x) -> true for all x, and lift it to forall_b{x | equivalent(x, x)} -> true.

Using the axiom of the quantifier

Built-in generalize

▶ Run

Using an axiom-based generalization

The axiom-based version declares two axioms inside a lock: one per-element (p(x) -> true) and one quantified (forall_b(...) -> true):

Axiom-based generalize

The realization label ReflProof provides the per-element proof. The call verifies that equivalent(x, x) -> true holds for each x and produces the quantified statement.

▶ Run

Calls on facts: notation("apply")

Continuing from the previous example, we now instantiate the universal statement for a concrete value.

Using notation("apply")

Built-in apply

▶ Run

Using an axiom-based instantiation

Axiom-based apply

G[true] becomes AppTheorem[predicate, true]. The if-condition forall_b(p) -> true is satisfied by the generalized statement.

▶ Run

if as a lock

So far we've reduced contradiction, generalization and calls on facts down to axiom-based theorems with if-conditions. But if itself can be reduced too: an if-block is essentially a lock with a single axiom — a hypothesis under which the body is proved. Lifting an assumption out of if and into a lock-axiom is a routine restructuring.

The example below is a direct restatement of FlipTrueIfTrue from the contradict reduction above, but written without using if for the hypothesis: each if-condition becomes a lock-axiom, and the realization mirrors that structure.

if reduced to lock

Each if becomes an axiom of its own lock, and the theorem is registered inside the innermost lock so that every supporting lock lies on its path. The axiom c -> false (carried by proof) gets a realization; the deeper axiom a -> true (in L2) becomes a nested lock axiom that the realization must match exactly. The caller mirrors the structure: ExL1 realizes c -> true, and Exproof realizes c -> false while crossing ExL2, whose axiom not(y) -> true matches L2's a -> true after substitution. Remove either realizer and the call fails — both axioms are genuinely on the path. This is the general pattern: any if-block rewrites to a single-axiom lock, and any proof using that if rewrites to a realization crossing the equivalent lock.

▶ Run

This is what unifies the language: if, for, type, lock, and rule are not separate features each requiring its own treatment in calls — they are all elements of the same signature. When a call walks the path from a theorem statement back to its label declaration, it sees the conditions imposed by these constructs and checks them against the realization's path uniformly. Whether an assumption was written as if(P -> false) or as axiom(P -> false | L) inside a lock, a call compares it the same way.

Everything at once: the full reduction

Each section above removed one step. The natural stress-test is to remove all four at once: a complete file that proves the same chain — hypothetical reasoning, contradiction, generalization, application — using only axiom, calls, lock(), proofs and for. The full code below contains not a single if, contradict, generalize or call on a quantified fact.

It goes one step further. Of the six Flip schemas, only four remain postulates: the two unary ones (FlipIfFalse, FlipIfTrue — Clavius laws, the only mechanisms that carry a result out of a hypothesis lock) and two binary ones (FlipTrueIfFalse, FlipTrueIfTrue — ex falso engines, one per conclusion polarity). The other two binary schemas are derived, not postulated — their labels are defined by the result of a call carrying the very same lock contract:

The four commands, fully eliminated

The derivation pattern, twice: inside a hypothesis lock the two axioms c -> true and c -> false contradict; a binary Flip of the needed polarity turns the contradiction into ex falso (its realization uses fewer nested assumptions than the template — weakening, allowed by the subset rule); the matching Clavius law then carries the result out of the hypothesis. The label FlipFalseIfFalse is defined by the result of a call, yet exposes exactly the same lock contract as the removed postulate — every later FlipFalseIfFalse[| HIPQ, A, ...] works unchanged. Mutation-checked: breaking the ex-falso polarity, the Clavius step, or any realizer fails the file.

▶ Run

Two things are worth noting. First, the derived theorems demonstrate that a theorem in Formall need not be an axiom registration: a label marked on the result of a call, positioned inside the right locks, carries a full lock contract and is applied like any other theorem. Second, the four remaining postulates are genuinely minimal for a language without a negation function: deriving a binary schema with a -> false conclusion requires an ex-falso schema of that same polarity, which is circular.

The other mechanisms

The other mechanisms of the language — notations, generated text, search, declarations — enlarge the core no further: the minimal set is still type, for, lock, axiom, proofs and calls. The table below groups these mechanisms by how they reduce. To check a reduction, compare the statements proved with and without the mechanism using expect( ).

MechanismKindWithout it
notation("default", true)notationif(P -> true) written out
abbreviation, multi-place ∀{x, y | …}notationthe formula written out; nested one-place quantifiers
decidegenerates texta lemma over the schemas of cases of the enumeration with the tables of the functions as conditions, applied by a call at the place
hints <e | L>, <e |* L>, chains, implicit arguments of callssearchexplicit calls with all arguments, then plain <…<e>… |> steps
obtain[| S], witness[t | L]lemmas of the librarythe same calls with p, q written out — or of an axiom scheme in a lock (below)
type(T = a | b)declaration (axiom schemes)type(T) for(a, b: T) and the schemas Distinct and Cases as axioms of a lock (an enumeration, written out)
notation("hint" | Rewrite, RewriteBack, Reflexive)two axioms and a lemma written in the file (no kernel rule since step 96)=(x, x) -> true and, under if(=(a, b) -> true), the rewriting a -> b; a rewrite by an equality is a call of the second one (below)
define(f := {a | e}), define(f | T∃!)definitional extension (no kernel rule since step 93)for(f) and a lock under it with the defining axioms (f(a) -> e, e -> f(a); or φ(a, f(a)) under the theorem's conditions); the code goes on inside the lock, and a call realizes the axioms outside it — an explicit definition by its body
subtype(ι, φ, ∃, ⇒)subtype premises about a declared ι: [S -> T] (no kernel rule since step 93)a lock with S1–S3 as axioms; no nonemptiness is needed by the kernel
rule("bijective", f)axiomaxioms of injectivity and exhaustion for f
contradict[| S], generalize[| S], H[a] on a quantified fact, deduce[| S]theorems and axioms written in the files (step 189в; no kernel rule since steps 95–97)Distinct: Y -> c1 and Y -> c2 give anything, Cases: what follows from each value follows — the lemma contradict; Generalize: p(x) -> c for an arbitrary x gives Q(p) -> d; Apply: under Q(p) -> d, p(x) -> c; ⇒(P, Q) -> true from Q -> true under if(P) in a lock

So the independent kernel checks every proof of the corpus with three rules — axioms, rewriting and applying a theorem — plus two shortcuts for modules (import, instance) that its strict mode does without.

How a result proved inside each of these blocks — a definition, a subtype, an enumeration — is carried out of it, and under which condition, is the subject of Leaving a Block.

equality as two axiom schemes

A statement a -> b already says that b may replace a anywhere. An equality fact =(a, b) -> true is only a fact until something turns it into such a rewriting. A file does it with two axioms of a lock, named by notation("hint" | Rewrite, RewriteBack, Reflexive): Reflexive =(x, x) -> true and Rewrite: under if(=(a, b) -> true), the rewriting a -> b. Rewriting right to left, the equality of a chain's ends and symmetry are proved from them. In the journal every step by an equality is a call of Rewrite (or of the proved RewriteBack), with the equality fact as its condition, and --trust lists the two schemes as axioms. Here they are written out without the rule:

Equality as two axioms

Under a binder the interpreter writes the same call of Rewrite at the bound variable: the condition is then met by the quantified fact instantiated right in the step (a premise written inline), since a statement about a bound variable cannot stand on its own.

▶ Run

obtain as an axiom scheme

Like FlipTrueIfTrue above, ∃-elimination is a theorem whose premise is a lock: «if ∃(p), and from p(x) for an arbitrary x follows q, then q». obtain[| S] is this call, with p and q found from the proof and the blocks it stands in:

obtain and the ∃-elimination scheme

In the library the scheme is not an axiom but a lemma (obtain), proved from the definition of ∃ through ∀; the call obtain[| S] takes the for and the if its proof stands in.

▶ Run

Summary

Once the axiom-based theorems are defined, using them takes roughly the same number of lines as the library's theorems. The real difference is that a call taking the blocks its proof stands in needs no extra labels: it expresses «flip the assumption» or «generalize over x» as one call, and the theorem it calls says exactly what the step is.


↗

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.


↗

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.


↗

Locks and Realizations

How do compares signatures, and what locks in realizations mean

Overview

When a call applies a theorem proved in a lock(), you supply realizations — search labels whose statements implement the lock's axioms in the calling context. The interpreter does not require these realizations to be plain unconditional proofs: each may itself sit inside if, for, or rule blocks, and may even cross other locks. What is required is that the realization's surrounding context — its signature — is no wider than the signature of the axiom it implements.

This page is an extended worked discussion of that rule. It builds up gradually, from the simplest case to nested locks and shared paths. The compact specification is on the do page.

The basic match: realization beside the call

The simplest case: the theorem uses one lock with one axiom; the caller proves the axiom's conclusion in plain scope, labels the result, and passes the label to the call. The realization's path is just ifs — no for, no lock.

Plain realization

The theorem's axiom AxiomPQ is registered inside L under if(P -> false). The realization AxiomAB sits under if(A -> false) in the caller. The substitution P -> A, Q -> B makes the two signatures match: same if, no extra for, no extra rules.

▶ Run

Realization may use less than the theorem allows

The realization's signature may be narrower than what the theorem assumed — fewer ifs, fewer for-atoms, fewer rules. This means the realization proved its conclusion under stricter conditions than necessary, which is always sound.

Realization narrower than theorem

The theorem assumed the axiom under if(P -> false), but the caller proves B -> true outright. This is fine: the realization is strictly stronger than the theorem required.

▶ Run

Realization may not exceed the theorem

What is not allowed is the realization adding anything to its signature that the theorem did not have. An extra if, an extra for-atom of some type, or an extra rule — any of these would let the realization invoke assumptions the theorem never sanctioned. The call rejects such cases.

Realization with an extra if - rejected

The call reports that the realization's extra if-condition B -> false is not in the theorem's signature for this axiom. The realization could be reading any kind of falsehood out of that assumption - that is not something the theorem ever agreed to.

▶ Run

Expected error: Axiom realization not found

Locks in the realization

A realization's path may cross lock() nodes. Each such lock contributes its own axioms to the realization's signature, and each of those axioms must be matched by an axiom of some lock on the theorem's path. The match for nested lock axioms is by equality of signature, not by containment — a lock axiom is what the realization provides, so it must be exactly as strong as the theorem expects, neither weaker nor stronger.

The grouping of locks does not matter. The realization may split one theorem lock into several locks of its own, or merge several into one — as long as the resulting multiset of nested lock axioms is contained in the theorem's.

Nested locks: signatures match

The theorem's two locks together carry two supporting axioms. The realization carries both in a single outer lock. Because a call matches by multiset of nested-lock axioms (not by lock-by-lock isomorphism), the regrouping is accepted.

▶ Run

Parameters above and below the lock

An axiom keeps the entire schema declared inside its lock. Its own parameters are universally bound; a theorem argument cannot specialize them. Parameters declared above the lock are instance parameters and receive the theorem substitution.

Parameters above and below the lock

The realization supplies the full schema inside L. The parameters a,c and condition c -> true are above L and are handled by the theorem application.

▶ Run

The position of the lock determines the contract; the common ancestor of the axiom and the proof result does not remove schema parameters.

Multiple axioms in one lock

If a lock has several axioms, a call requires a realization for each one written before the theorem — whether or not the theorem actually uses it. The lock is a contract: every axiom standing in the lock when the theorem was proved is a hypothesis under which it was proved, and every one must be discharged. Realizations may be supplied in any order; the call matches them by signature, not by position.

All axioms must be realized

A lock is a contract: every axiom standing in it when the theorem was proved must be discharged. Order does not matter.

▶ Run

An axiom written after the theorem

The text is read in order, and a theorem is proved under the conditions that stand when it is written. An axiom added to the lock after the theorem could not take part in its proof, so it is no obligation of the theorem: a call asks for no realization of it. Here T1 is proved before Ax is added to A, and is applied outside A without one.

An axiom written after the theorem is not required

T1 rests only on what stood in A when it was proved. Written before T1, Ax would have to be realized (it cannot be here).

▶ Run

do inside a realization

A realization may freely call other theorems. The result of a call is a plain statement delivered into the current scope; whatever locks lived inside the theorem applied by that nested call stay there, never appearing on the outer realization's path.

A call inside a realization

A call gives a regular statement; the theorem applied by the inner call does not affect the outer realization's signature.

▶ Run

Summary

A call checks realizations by comparing signatures. A signature is a structured account of everything between a statement's definition and where its label was declared: the multiset of for-atoms (per type), the multiset of if-conditions, the multiset of rule rules.

For each axiom the theorem requires:

  • The realization's signature must be contained in the axiom's signature — fewer or equal for-atoms per type (positional, prefix-matched), fewer or equal ifs, fewer or equal rules.
  • Parameters above the axiom's lock receive the theorem substitution. Its own parameters inside the lock remain part of the complete schema.
  • Nested locks on either side contribute their axioms; these are matched by equality of signature, in any grouping.

The single underlying principle: the realization must not be allowed to use anything the theorem did not. Everything else — order, grouping, narrowing — is just freedom to write the proof naturally.


↗

Formall vs. Other Proof Assistants

A structured comparison with Lean 4, Coq, Agda, Isabelle/HOL, and Metamath

Overview

Formall sits at a different point in the proof assistant design space than Lean 4, Coq, Agda, Isabelle/HOL, and Metamath. This page puts them side by side on the same concrete theorems, then summarises the conceptual differences. The goal is not a ranking but a clear picture of what each system optimises for.

  • Lean 4 — dependent types, tactic and term mode, Mathlib standard library. Proofs and programs unified via Curry–Howard.
  • Coq / Rocq — dependent types, tactic-based, constructive by default. Classical axioms are an explicit import.
  • Agda — dependent types, no tactics, proof terms written directly. Constructive (intuitionistic) only.
  • Isabelle/HOL — higher-order logic, structured Isar proof language, classical by default. Powerful automation via sledgehammer.
  • Metamath — no built-in logic: axioms are declared as $a statements, proofs are chains of substitutions written in reverse Polish notation. Its main database set.mm builds ZFC set theory from scratch (about 48,000 theorems); there are many small independent verifiers. The closest relative of Formall — see below.
  • Formall — typed atoms with HOL-style type variables (not dependent types, see below), scope-tree proofs, a small core of commands. No built-in logic — you define it from axioms.

Example 1: double negation elimination — ¬¬x → x

Prove: if ¬¬x holds, then x holds. Constructive systems (Agda, base Coq, base Lean) cannot prove this without a classical axiom.

Lean 4 — term mode with Classical

-- Classical is a built-in namespace; no external file needed
open Classical

-- em p : p ∨ ¬p  (excluded middle, from Classical)
-- Or.elim splits the disjunction into two cases:
--   · left  branch (hp  : p)  → return hp directly
--   · right branch (hnp : ¬p) → absurd : ¬p → ¬¬p → False → p
-- Result type: p
theorem dne {p : Prop} (h : ¬¬p) : p :=
  Or.elim (em p)
    (fun hp  : p  => hp)            -- case p holds: done
    (fun hnp : ¬p => absurd hnp h)  -- case ¬p: contradicts h : ¬¬p

Coq (tactic mode) — with full manual classical setup

(* Coq is constructive by default.
   We can either import Classical or declare the axiom ourselves. *)

(* Rule A: import the library *)
Require Import Classical.
(* This gives us: NNPP : forall P : Prop, ~~P -> P *)

Theorem dne_library : forall P : Prop, ~~P -> P.
Proof.
  intros P H.  (* H : ~~P, goal : P *)
  apply NNPP.  (* NNPP reduces ~~P → P to showing ~~P *)
  exact H.     (* H : ~~P. QED, result: P *)
Qed.

(* Rule B: declare classical axiom manually, no imports *)
Axiom excluded_middle : forall P : Prop, P \/ ~P.

Theorem dne_manual : forall P : Prop, ~~P -> P.
Proof.
  intros P H.
  destruct (excluded_middle P) as [hp | hnp].
  - exact hp.          (* case P holds: done, result P *)
  - exfalso.           (* goal becomes False *)
    apply H. exact hnp. (* H : ~~P, hnp : ~P, so H hnp : False *)
Qed.

Agda — constructive only; DNE requires a postulate

-- Agda's logic is intuitionistic: ¬¬A → A is not provable.
-- We can postulate excluded middle as an axiom:

open import Data.Empty using (⊥; ⊥-elim)  -- ⊥ = False
open import Data.Sum   using (_⊎_; inj₁; inj₂)

-- ¬ A is defined as A → ⊥
¬_ : Set → Set
¬ A = A → ⊥

-- Postulate excluded middle (not provable constructively)
postulate
  em : (A : Set) → A ⊎ ¬ A

-- Double negation elimination using the postulate
dne : {A : Set} → ¬ ¬ A → A
dne {A} h with em A
... | inj₁ a  = a         -- case A holds: return a directly
... | inj₂ ¬a = ⊥-elim (h ¬a)
-- case ¬A: h : ¬¬A, ¬a : ¬A, so h ¬a : ⊥, ⊥-elim gives A

Isabelle/HOL — classical by default, Isar proof language

(* Isabelle/HOL is classical; no imports needed. *)
(* 'classical' is a built-in rule: (¬P ⟹ P) ⟹ P *)

theory DNE imports Main begin

theorem dne: "¬¬P ⟹ P"
proof (rule classical)        (* apply classical: assume ¬P, prove P *)
  assume "¬P" "¬¬P"           (* both assumptions now in context *)
  then show P by contradiction  (* ¬P and ¬¬P directly contradict *)
qed
(* Result: ¬¬P ⟹ P *)

end

Metamath (set.mm)

$( Metamath has no built-in logic either: set.mm declares its axioms
   (ax-mp, ax-1, ax-2, ax-3, ...) as $a statements, and a proof is a
   list of labels in reverse Polish notation.  The verifier only checks
   that every step is a correct substitution instance. $)
$[ set.mm $]

$( Double negation elimination from Clavius' law
     pm2.18 : |- ( ( -. ph -> ph ) -> ph )
   jarli turns |- ( ( ph -> ps ) -> ch ) into |- ( -. ph -> ch ). $)
dne $p |- ( -. -. ph -> ph ) $=
  wph wn wph wph wph pm2.18 jarli $.
$( wph wn      : build the wff -. ph  (substituted for ph in jarli)
   wph wph     : ps := ph, ch := ph
   wph pm2.18  : jarli's hypothesis, an instance of Clavius' law
   Result: |- ( -. -. ph -> ph ) $)

Formall: double negation elimination

No imports. The logic rules — which truth values contradict each other, how not behaves — are declared explicitly at the top. The proof assumes x -> false, derives not(not(x)) -> false by a proof, then contradict closes the assumption. Result: x -> true inside the outer if block.

▶ Run

Example 2: reusing a theorem — ¬¬¬x → ¬x

Apply the double negation theorem to ¬x instead of x.

Lean 4

open Classical

-- Lean's type system unfolds ¬¬¬p as ¬¬(¬p) automatically.
-- dne is applied with implicit argument ¬p inferred from context.
theorem triple_neg {p : Prop} (h : ¬¬¬p) : ¬p :=
  dne h
-- Result: ¬p  (Lean infers the substitution from the type)

Coq (tactic mode)

Axiom excluded_middle : forall P : Prop, P \/ ~P.
Theorem dne_manual : forall P : Prop, ~~P -> P.
Proof.
  intros P H. destruct (excluded_middle P) as [hp | hnp].
  - exact hp. - exfalso. apply H. exact hnp.
Qed.

Theorem triple_neg : forall P : Prop, ~~~P -> ~P.
Proof.
  intros P H.            (* H : ~~~P, goal : ~P i.e. P → False *)
  apply dne_manual.      (* reduce goal to ~~(~P) = ~~~P *)
  exact H.               (* H : ~~~P matches. Result: ¬P *)
Qed.

Agda

-- Using dne from Example 1 (with em postulate)
triple-neg : {A : Set} → ¬ ¬ ¬ A → ¬ A
triple-neg h = dne h
-- Agda unifies ¬¬¬A with ¬¬(¬A); dne applied with A := ¬A.
-- Result: ¬A

Isabelle/HOL

theory TripleNeg imports DNE begin

(* Use dne lemma from Example 1 *)
theorem triple_neg: "¬¬¬P ⟹ ¬P"
  using dne by blast
(* blast: automated reasoner closes the goal instantly. *)
(* Result: ¬P *)

end

Metamath (set.mm)

$( Reuse dne from Example 1.  The verifier computes the substitution
   ph := -. ph itself; the proof only builds the wff -. ph (wph wn). $)
triple-neg $p |- ( -. -. -. ph -> -. ph ) $=
  wph wn dne $.
$( Result: |- ( -. -. -. ph -> -. ph ) $)

Formall: reuse by a call

MyDNE[not(y)] substitutes not(y) for x in the theorem. The substitution is explicit — passed as a string. Lean and Agda infer it from types; Coq infers it from the goal. Result: not(y) -> true inside not(not(not(y))) -> true.

▶ Run

Example 3: symmetry of equality — x = y → y = x

Lean 4

-- Equality (=) is built into Lean's type theory (reflexivity, congruence).
-- h ▸ rfl: rewrite the goal "b = a" using h : a = b, giving "a = a",
--           then close with rfl (reflexivity). Result: b = a
theorem eq_symm {α : Type} {a b : α} (h : a = b) : b = a :=
  h ▸ rfl

Coq (tactic mode)

Theorem eq_symm : forall (A : Type) (a b : A), a = b -> b = a.
Proof.
  intros A a b H.  (* H : a = b, goal : b = a *)
  rewrite H.        (* rewrite a → b in goal via H, goal becomes b = b *)
  reflexivity.      (* close b = b. Result: b = a *)
Qed.

Agda

-- Equality is defined inductively (refl : a ≡ a)
-- Pattern matching on refl forces a = b, unifying a and b.
open import Relation.Binary.PropositionalEquality using (_≡_; refl)

sym : {A : Set} {a b : A} → a ≡ b → b ≡ a
sym refl = refl
-- When h : a ≡ b is matched as refl, a and b become equal by definition.
-- refl then proves b ≡ a trivially. Result: b ≡ a

Isabelle/HOL

theory EqSym imports Main begin

(* sym is already in Main; shown here for comparison *)
theorem eq_sym_manual: "a = b ⟹ b = a"
proof -
  assume h: "a = b"   (* h : a = b in context *)
  from h show "b = a" by (rule sym)  (* sym : a = b ⟹ b = a *)
qed
(* Result: b = a *)

end

Metamath (set.mm)

$( Class equality is defined in set.mm (df-cleq), and eqcom is a theorem:
     eqcom : |- ( A = B <-> B = A )
     mpbi  : from |- ph and |- ( ph <-> ps ) conclude |- ps
   A ${ ... $} block scopes the hypothesis eqsym.1 to this theorem. $)
${
  eqsym.1 $e |- A = B $.
  eqsym $p |- B = A $=
    cA cB wceq cB cA wceq eqsym.1 cA cB eqcom mpbi $.
$}
$( Result: from |- A = B infer |- B = A $)

Formall: symmetry of equality

Formall has no built-in equality. Reflexivity is an explicit axiom; rewriting is the substitution syntax <=(y, <x>)>; indiscernibility is a lock axiom. More code than other systems — but every rule that equality follows is visible and auditable. Result: L=Sym — =(y, x) -> ✔ whenever =(x, y) -> ✔.

▶ Run

Conceptual differences

Metamath: the closest relative

Of all the systems on this page, Metamath shares Formall's core philosophy most closely: the verifier knows no logic. In Metamath, ax-mp, the propositional axioms and ZFC are ordinary $a declarations in a text file; the verifier checks only that every proof step is a correct substitution instance of an earlier statement. The whole language is a handful of keywords ($c $v $f $e $d $a $p), and set.mm — about 48,000 theorems of ZFC — is verified by the reference program in roughly four seconds. Even the route to double negation is the same: set.mm derives it from Clavius' law ((¬φ → φ) → φ), which is exactly what Formall's contradict does when it flips an assumption.

The differences are in what the core takes care of:

  • Binders and variables. Metamath is pure string substitution; bound variables are managed by explicit distinct-variable conditions ($d) and substitution lemmas. Formall has typed terms and constructors {x: T | …} with α-equivalence built in, so bound variables need no bookkeeping.
  • Contexts. Metamath is Hilbert-style: there are no local assumptions, so set.mm writes most theorems in deduction form ph -> … and carries the context by hand. Formall's scope tree (if, for, rule) gives natural-deduction-style contexts directly.
  • Proof text. A Metamath proof is a list of labels in reverse Polish notation (including the steps that merely build formulas); it is compact and machine-checkable but unreadable without a tool that displays it. A Formall proof is a sequence of commands, each producing a visible statement.
  • Instantiation. Metamath's verifier computes substitutions by unification — wph wn dne is enough to use dne at ¬φ. A Formall call T[a] takes the substitution as written values, or infers them from the conditions of the theorem.
  • Hypothetical theorems. Metamath's essential hypotheses ($e) turn a theorem into an inference rule whose premises must be proved before use. Formall's lock() / axiom / call plays the same role, but a realization may itself be proved under local for/if assumptions and is matched by signature.
  • Ecosystem. Metamath has a large library, a detailed specification and several independent verifiers written in different languages. Formall has one interpreter and a growing corpus.

In short: Metamath minimises the trusted kernel; Formall trades a somewhat larger kernel (types, binders, scopes, contradiction) for proofs that read as structured text.

Logic system: axiom-defined vs. built-in

Lean, Coq, and Agda have a fixed constructive core — intuitionistic type theory. Classical axioms exist but must be added deliberately. Isabelle/HOL is classical but still has a fixed higher-order logic built in.

Formall, like Metamath, has no built-in logic at all. type(bool = false | true) declares the truth values, every two different; if axioms declare how connectives behave; lock() introduces any further axioms. You can define classical boolean logic (as above), a three-valued logic, or a custom axiom system — Formall treats them identically. There is no constructive/classical split to manage, because the distinction is itself defined by your axioms.

Types: three designs

A frequent question: how do you state one equality = that works for numbers, sets and functions alike? The three families of systems answer it differently.

Metamath: one universe, no types

set.mm has no types of mathematical objects. Everything — the number 2, a real number, a function, ℝ itself — is a set (a class). So there is a single = between classes, and no =ℕ, =ℝ copies; ℕ ⊆ ℝ is ordinary inclusion. "x is a real number" is a hypothesis A ∈ ℝ, not a type. Metamath has only syntactic sorts (wff, setvar, class) that keep formulas well-formed. A theorem is a scheme over metavariables, and applying it is textual substitution.

HOL (Isabelle/HOL, HOL Light) and Formall: type variables outside the statement

Formall follows this design. A type variable 'α makes an atom polymorphic and every statement about it a scheme; a call substitutes a concrete type. This is how library/logic/equality.fl declares equality once for every type:

Formall (actual library code)

type("'α");
for("=: ['α, 'α -> 𝔹]"); notation("infix", "=", "50");

for ("x: 'α") A=Reflexive: axiom(𝒜, "x = x");
for ("a, b: 'α") if ("a = b") A=Rewrite: axiom(𝒜, "a -> b");

'α stays outside the statement: one cannot write a single statement that says "for every type". Structures such as groups are theory blocks type(G) for(∘, e) if(axioms) { … } applied by calls — the same idea as Isabelle's locales. The kernel needs no computation, and equality of types is plain syntactic equality.

Inside a block a premise over 'α can be used at another type: a proof about ℕ rewrites with A=Rewrite at ℕ. The certificate kernel (Reducibility) states such a premise as the schema it is, "for every type A, A=Rewrite at A", and each use is the schema taken at a type, which the kernel checks like any other step. The certificate has a quantifier over types for this; the language does not need one, because 'α already says it. Other systems differ here. HOL instantiates a whole theorem at a type together with its hypotheses (INST_TYPE), so the hypothesis at the other type becomes one more hypothesis of the theorem. Isabelle keeps 'a fixed inside a locale, and the locale's assumptions cannot be used at another type there. In Lean and Coq a hypothesis "for every type" is an ordinary formula ∀ α, P α.

Lean, Coq, Agda: types are values (dependent types)

The code below is hypothetical — Formall does not support it. It shows what Formall would look like on the dependent-type route.

1. A type of types 𝕋 (Lean's Type) lets a statement quantify over types inside the formula:

Hypothetical Formall

for("=: ∀{T: 𝕋 | [T, T -> 𝔹]}")              // one constant with a type argument
axiom(𝒜, "∀{T: 𝕋 | ∀{x: T | =(T, x, x)}} -> ✔")
if("∀{T: 𝕋 | ∃{x: T | ✔}} -> ✔")              // "every type is inhabited" as a hypothesis

2. A structure is a value, and its carrier is a type computed from that value:

Hypothetical Formall

define("Group", "{ G: 𝕋, ∘: [G, G -> G], e: G, assoc: …, … }")
for("H: Group")
for("a, b: H.G")                               // the type depends on the value H
"∀{H: Group | ∀{a: H.G | a H.∘ H.e = a}}"      // an ordinary statement about all groups

This allows lists of groups, a function "group ↦ its centre (a group)", the type of elements of a subgroup.

3. A type depending on a number — and the price:

Hypothetical Formall

for("Vec: [ℕ -> 𝕋]")
for("append: ∀{n, m: ℕ | [Vec(n), Vec(m) -> Vec(n + m)]}")
for("n: ℕ") for("v: Vec(n), w: Vec(0)")
"=(append(v, w), v)"      // TYPE ERROR unless the kernel computes Vec(n + 0) to Vec(n)
  • The kernel must compute. To see that Vec(n + 0) and Vec(n) are the same type it has to reduce n + 0 — a small evaluator inside the trusted kernel.
  • Theorems do not help type checking. If addition recurses on the second argument, 0 + n does not reduce to n; 0 + n = n is only a theorem, so one needs an explicit cast ("transport"). Fighting such casts is a known cost in Mathlib.
  • Equality depends on typing. x = y is well-formed only when the types coincide, and that coincidence is a computation, not a statement.

On the HOL route one writes v: 𝕊 with a hypothesis length(v) = n instead: coarser, but the kernel needs no evaluator.

Which is better?

There is no consensus; it is a trade-off. Dependent types are more expressive, and Lean has the largest library of formal mathematics (Mathlib). HOL has a much smaller logic and kernel (HOL Light's is a few hundred lines), strong automation (Sledgehammer) and large verification projects (seL4, CakeML); it is argued (e.g. by Paulson) that HOL with locales suffices for most ordinary mathematics. Formall takes the HOL route: its goal is a small, reliable, checkable kernel — rank-one polymorphic constants plus schematic theorems, with "for every structure" expressed by theory blocks and calls.

Proof structure: tactics vs. scope tree

Coq and Lean build proofs interactively by transforming goals. You see the current goal state, apply a tactic, and get subgoals. Lean 4 has simp, omega, decide, and grind — tactics that solve whole classes of goals in one step. Isabelle's sledgehammer calls external theorem provers automatically.

Formall builds proofs as a static nested-block tree. There are no goals, no subgoal queue, no tactic state. Each if block introduces an assumption; each for introduces variables; each lock introduces local axioms. The structure of the code is the structure of the proof. Every step is an explicit command with a precisely defined effect. Formall proofs are longer, but fully readable as text without a running proof assistant.

Standard library vs. blank slate

Lean's Mathlib, Coq's standard library, and Isabelle's Archive of Formal Proofs each contain tens of thousands of theorems. Agda's standard library is similarly substantial. Working in these systems, you build on a large existing body of mathematics.

Formall starts from axioms. The library modules (library/logic/uniqueness.fl, library/sets/main.fl, library/peano/main.fl) build logic, arithmetic, and set operations from explicit axioms — including the Russell paradox, ordered pairs by Kuratowski, and existence of unions. This is slower to use but makes the foundations completely explicit and auditable.

A small core

Lean, Coq, and Isabelle have large trusted kernels and many derived rules. The kernel correctness is what you ultimately trust. Metamath sits at the other extreme: its whole verification rule is "check the substitution", and independent verifiers fit in a few hundred lines.

Formall's trusted core is a handful of commands — type, for, if, lock, rule, axiom — and two forms: proofs <…> and calls T[…]. The steps of a proof — contradiction, generalization, calls on quantified facts — and even if are expressed through lock, axiom and calls, as shown on the Command Reducibility page. If you understand what the core commands do, you understand everything the interpreter can verify.

ℹ
This comparison is a starting point. Good future additions: an induction example comparing Lean's induction tactic with Formall's Peano axiom approach; a set theory example; and the Curry–Howard correspondence — how proofs-as-programs applies (or does not) to Formall.

API

↗

API

Submit Formall source code and receive interpreted output files.

Upload & Run

Upload a .fl file or paste source code directly to interpret:

📁 Choose a .fl file or drag & drop it here

Endpoints

POST /api/run

Submit source code for interpretation. Accepts either a file upload or raw source text.

POST /api/run

Request (file upload)

Content-Type: multipart/form-data

ParameterTypeDescription
filefileFormall source file (.fl). Max 2 MB.

Request (source text)

Content-Type: multipart/form-data or application/x-www-form-urlencoded

ParameterTypeDescription
sourcestringFormall source code as plain text. Max 2 MB.

Response

200 OK
{
  "success": true,
  "token": "aBcDeFgHiJkLmNoPqRsTuVxYz012345",
  "status_url": "/api/status?token=aBcDeFgHiJkLmNoPqRsTuVxYz012345",
  "files": {
    "source":     "/files/TOKEN/source.fl",
    "output":     "/files/TOKEN/output.txt",
    "result":     "/files/TOKEN/result.txt",
    "statements": "/files/TOKEN/statements.txt",
    "log":        "/files/TOKEN/log.txt",
    "messages":   "/files/TOKEN/messages.txt",
    "tree":       "/files/TOKEN/tree.txt",
    "links":      "/files/TOKEN/links.txt",
    "labels":     "/files/TOKEN/labels.txt"
  }
}
ℹ
Interpretation runs asynchronously. Use the status_url to poll for results.

GET /api/status

Check whether the interpretation has finished. Once ready is true, download result files via the URLs returned by /api/run.

GET /api/status?token=TOKEN
ParameterTypeDescription
tokenstring32-character alphanumeric session token returned by /api/run.

Response (processing)

200 OK
{ "ready": false }

Response (ready)

200 OK
{ "ready": true, "ok": true, "exit_code": 0 }

ok is true when the code is checked without errors (exit code 0); exit code 1 means an error in the code, other codes a failure of the interpreter.

GET /files/{token}/{filename}

Download individual result files directly once interpretation is complete.

Available files (the interpreter runs as formall source.fl -o DIR, see the command line):

  • source.fl — the source
  • output.txt — what the interpreter printed: the error, warnings and notices about the source, and the result line OK <seconds> or ERROR <seconds>
  • result.txt — the result line alone, written last
  • statements.txt — every statement with its position
  • log.txt — every command with the statements it gives and all messages
  • messages.txt — all errors, warnings, notices and remarks, also about imported files
  • labels.txt — labels and their statements
  • links.txt — the premises of every statement
  • tree.txt — the block tree (for debugging the interpreter)

Runs made before 2026-10-11 keep their old file names (out.fl, log.fl, log.messages.fl, …).

Command line

The same interpreter runs locally:

formall FILE.fl [options]

  -o, --out DIR        all reports with standard names in DIR (created if missing); result.txt last
  --log FILE           every command with the statements it gives and all messages
  --statements FILE    every statement with its position
  --messages FILE      all errors, warnings, notices and remarks, also about imported files
  --links FILE, --labels FILE, --tree FILE, --result FILE
  --certificate-journal FILE  a certificate of every statement (JSON lines), checked by the independent kernel
  --trust FILE         the axioms, definitions, rules and conditions of every theorem T::
  --profile FILE       where the time went
  --cache DIR          where module objects are kept (default: .formall next to formall.project, else ~/.cache/formall)
  -j, --jobs N         modules compiled in parallel
  --import-root DIR    also allow import() from DIR;  --allow-any-import
  --explicit           every value and fact is written (calls)
  --prefix, --no-fold  printing;  -q, --quiet  only the error on stderr;  -h, --help

Imported files are modules: each is checked once and kept as an object in the cache; only what changed is checked again (import).

The last line on stdout is OK <seconds> or ERROR <seconds>; the exit code is 0 (OK), 1 (an error in the file) or 2 (a wrong command line, a file that cannot be read or written). The error, and the warnings and notices about the file itself (not about imported files, not about text generated by decide), go to stderr.

Errors

Error responses use standard HTTP status codes:

CodeMeaning
400No input provided
405Method not allowed (use POST for /api/run)
413File or source too large
500Internal server error

Examples

cURL — file upload

Shell
curl -X POST -F "file=@example.fl" https://formall.mooo.com/api/run

cURL — source text

Shell
curl -X POST -d "source=for x (do)" https://formall.mooo.com/api/run

cURL — check status

Shell
curl https://formall.mooo.com/api/status?token=YOUR_TOKEN

JavaScript (fetch)

ℹ
This example is for browser environments. Paste it into the browser console (F12) on any webpage.
JavaScript
// Create file input element
const fileInput = document.createElement('input');
fileInput.type = 'file';
document.body.appendChild(fileInput);

// Handle file selection
fileInput.onchange = async () => {
    try {
        // Prepare form data with selected file
        const form = new FormData();
        form.append('file', fileInput.files[0]);

        // Upload file
        const res = await fetch('https://formall.mooo.com/api/run', {
            method: 'POST',
            body: form
        });
        const data = await res.json();

        // Poll for completion
        const poll = async (token) => {
            const r = await fetch(`https://formall.mooo.com/api/status?token=${token}`);
            const s = await r.json();
            if (s.ready) return s;
            await new Promise(r => setTimeout(r, 1000));
            return poll(token);
        };

        await poll(data.token);

        // Download output file
        const output = await fetch(`https://formall.mooo.com${data.files.output}`)
            .then(r => r.text());
        console.log(output);

    } catch (error) {
        console.error('Error:', error);
    }
};

// Open file picker
fileInput.click();

Python (requests)

Python
import requests, time

# Upload file
r = requests.post('https://formall.mooo.com/api/run',
                   files={'file': open('example.fl', 'rb')})
data = r.json()
token = data['token']

# Poll for results
while True:
    s = requests.get(f'https://formall.mooo.com/api/status?token={token}').json()
    if s['ready']:
        break
    time.sleep(1)

# Download output
output = requests.get(f'https://formall.mooo.com{data["files"]["output"]}').text
print(output)