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
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.
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
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.
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
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.
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.
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.
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( ).
| Mechanism | Kind | Without it |
|---|---|---|
notation("default", true) | notation | if(P -> true) written out |
abbreviation, multi-place ∀{x, y | …} | notation | the formula written out; nested one-place quantifiers |
decide | generates text | a 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 calls | search | explicit calls with all arguments, then plain <…<e>… |> steps |
obtain[| S], witness[t | L] | lemmas of the library | the 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) | axiom | axioms 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.
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.
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.