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 writtenexpressionWithMarks- 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 callT[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 lemmaL=ByRewriteoflogic/equality.flstates 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
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
- Find a statement
X -> Ywhose left sideXis the expression in<…> - Replace
<X>withY - Process nested
<…>from the inside out - Create a new statement:
original expression -> final result
Substitution steps
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.
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
Chained Substitutions
Chained substitution
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.
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
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.
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
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
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>.
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.
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.
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().
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))).
show() there lists what is visible.