Playground Documentation Challenges Full Docs

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.