Cubist

LANGUAGE REFERENCE · CHAPTER 4

Proof blocks

A proof block builds a term one statement at a time. Each statement extends the context, changes the goal, or closes it.

Goals and statements

A proof block is the body of a block declaration: def name(params) : T { … }. As in the first proofs, it starts with the goal T and a context holding the parameters. Each statement does one of three things:

  • it extends the context and continues with the same goal: let, obtain;
  • it changes the goal and continues with the new one: intro, rw, simp, ext;
  • it closes the goal and ends the block: exact, match, rfl, calc, simpa, over, hlevel.
def swap_product(A, B : U0) : (A and B) -> (B and A) {
  intro pair;            // goal: B and A
  obtain (a, b) := pair;  // context: a : A, b : B
  let saved := a;
  let result : B and A {
    exact (b, saved);
  }
  exact result;          // closes the goal
}

A block must end by closing its goal. A block that runs out of statements first is rejected:

def unfinished(A : U0) : A -> A {
  intro a;  // Error: Proof block has no conclusion.
}

Nothing may follow a closing statement in the same block:

def after_the_end(A : U0, a : A) : A {
  exact a;
  exact a;  // Error: Statements after exact are unreachable.
}

An unknown word where a statement belongs is a syntax error:

def not_a_statement(a : UNat) : UNat {
  return a;  // Error: Expected a proof statement; found 'return'.
}
StatementEffectDescribed in
intro x, y;Changes the goalintro
exact term;Closesexact
let name := term;, let name : T := term;, let name : T { … }Extends the contextlet
obtain (a, b) := pair;Extends the contextobtain
use m;Extends the contextselecting a model
match value { left(a) => { … } right(b) => { … } }Closestaking a sum apart
match n { zero => { … } succ(k) => { … } }Closesproofs by matching
rfl;Closesreflexivity
calc { … }Closeschains
rw [p];Changes the goalrewriting
simp;, simp only [rules];, simp [rules] at h as h2;Changes the goal, or adds a hypothesissimplification
simpa [rules] using proof;Closessimpa
ext x;Changes the goalfunction extensionality
hlevel;, hlevel with [h];Closesh-levels

intro

intro x; takes the next input of a function goal. For a goal forall x : A. B(x), it adds x : A to the context and leaves B(x). For an implication P -> Q, it adds a proof of P and leaves Q. intro x, y, h; is three introductions in a row; the inspector shows the context after each one.

def curry(A, B, C : U0) : ((A and B) -> C) -> A -> B -> C {
  intro f, a, b;
  exact f((a, b));
}

The goal’s type is computed first, so intro works on a named definition that unfolds to a function type:

def Endo(A : U0) := A -> A;

def compose_endo(A : U0, f, g : Endo(A)) : Endo(A) {
  intro a;
  exact f(g(a));
}

A goal that is not a function type has nothing to introduce. This includes asking for more names than the goal has inputs:

import unat;

def nothing_to_introduce : UNat {
  intro n;  // Error: intro requires a dependent function goal.
  exact n;
}
def one_input_only(A : U0) : A -> A {
  intro a, b;  // Error: intro requires a dependent function goal.
  exact a;
}

A function goal can also be closed without intro, by giving the function: exact fun (a : A) => a;.

The name after intro is picked by the author. Its spelling does not determine its type; the goal does. Here decided gets the type Decidable(P) because that is the next input of the goal, after Statement unfolds:

def Decidable(P : U0) := P or (P -> Void);

def Statement := forall P : U0. Decidable(P) -> Decidable(P);

def keep_decision : Statement {
  intro P;          // P : U0, from the forall
  intro decided;    // decided : Decidable(P), from the implication
  exact decided;
}

exact

exact term; checks the term against the goal and closes the block. The two types need only be equal by computation, as described in conversion:

import unat;
use unat;

def by_computation : 2 + 2 = 4 {
  exact refl(4);
}

def identity_function(A : U0) : A -> A {
  exact fun (a : A) => a;
}
def wrong_type(A, B : U0, a : A) : B {
  exact a;  // Error: Type mismatch: found A, expected B.
}

let

let names a term for the rest of the block, or proves a local claim. It has three forms:

FormUse
let name := term;Name a term. Its type is the one the elaborator infers.
let name : T := term;Check term against T. The name has type T as written. The := keeps an = inside T unambiguous.
let name : T { … }Prove T in a nested block. The block sees the surrounding context, but not name.
import unat;

def three_ways(n : UNat) : n = n {
  let p := refl(n);
  let q : n = n := p;
  let r : n = n {
    exact q;
  }
  exact r;
}

The name stands for the term itself, so the checker sees through it: refl(m) below proves succ(n) = succ(n) because m is succ(n). This holds for every form; a proof named by let stays visible to computation. With a stated type, the name's type is T as written, and that is what the goal display, rw and simp see.

import unat;

def see_through(n : UNat) : succ(n) = succ(n) {
  let m := succ(n);
  exact refl(m);
}

Without a type, let name := term; gives the term no expected type, so a pair is rejected. State the type instead:

import unat;

def untyped_pair(a, b : UNat) : UNat and UNat {
  let p := (a, b);  // Error: Pair requires an expected type.
  exact p;
}
import unat;

def stated_pair(a, b : UNat) : UNat and UNat {
  let p : UNat and UNat := (a, b);
  exact p;
}

let names one term. To take a pair apart, use obtain:

def pattern_in_let(p : UNat and UNat) : UNat {
  let (a, b) = p;  // Error: Use obtain to unpack a pair.
  exact a;
}

A let whose name nothing after it uses can be removed, and the checker warns about it:

import unat;

def leftover(n : UNat) : UNat {
  let doubled := succ(succ(n));  // Warning: doubled is never used after this let: remove it.
  let same : n = n := refl(n);  // Warning: same is never used after this let: remove it.
  exact n;
}

Local lemmas

let name : T { … } proves a claim in a nested block and names it for the rest of the proof. Use it to split a long argument into named steps. The nested block must close its own goal:

def from_context(A, B : U0, a : A, b : B) : A and B {
  let pair : A and B {
    exact (a, b);
  }
  exact pair;
}
import unat;

def empty_claim(a : UNat) : UNat {
  let b : UNat {  // Error: Proof block has no conclusion.
  }
  exact b;
}

Restating the goal

To work on the goal in another form, prove that form and close the goal with it. exact accepts it when the two are equal by computation, as described in conversion. Use this to unfold a definition in the goal, or to see a computed form of it:

import unat;
use unat;

def Endo(A : U0) := A -> A;

def identity_endo(A : U0) : Endo(A) {
  let restated : A -> A {
    intro a;
    exact a;
  }
  exact restated;
}

def first_of_pair(n : UNat) : typed(UNat and UNat, (n, 0)).1 = n {
  let restated : n = n {
    rfl;
  }
  exact restated;
}

A form that is only provably equal to the goal is not enough. n + 0 and n are equal by a proof, not by computation:

import unat;
use unat;

def plus_zero(n : UNat) : n + 0 = n {  // Error: Type mismatch: found n = n, expected n + 0 = n.
  let restated : n = n {
    rfl;
  }
  exact restated;
}

Reasoning backwards

To reduce the goal to a claim, prove the claim first and then the goal from it:

def contrapositive(A, B : U0, f : A -> B, not_b : B -> Void) : A -> Void {
  intro a;
  let b : B {
    exact f(a);
  }
  exact not_b(b);
}

In contrapositive, the goal after intro a is Void. The block proves b : B, and not_b(b) proves the goal from it.

have, show and suffices were removed on 2026-09-30, since let expresses each of them. Each is refused with the let form that replaces it:

def claim(A : U0, a : A) : A {
  have b : A := a;  // Error: have was removed: write let name : T := term; or prove the claim in a block, let name : T { … }.
  exact b;
}
def restate(A : U0, a : A) : A {
  show A;  // Error: show was removed: prove the restated goal in a block, let h : T { … }, then exact h;.
  exact a;
}
def backwards(A, B : U0, f : A -> B, a : A) : B {
  suffices x : A by f(x);  // Error: suffices was removed: prove the claim first, let h : T { … }, then prove the goal from h.
  exact a;
}

obtain

obtain (a, b) := pair; names the components of a pair or dependent pair. Patterns can be tuples and can nest, following the shape of the type.

import unat;

def witness_(t : exists n : UNat. (n = n) and Unit) : UNat {
  obtain (n, same, u) := t;
  exact n;
}

def inner_unit(t : (UNat and Unit) and UNat) : Unit {
  obtain ((a, u), b) := t;
  exact u;
}

Like let, obtain introduces no new variables. Each name stands for a component of the pair, so (n, q) is equal to p by computation. A goal that mentions the original pair therefore still works:

import unat;

def about_the_pair(P : (exists n : UNat. n = n) -> U0,
    h : forall n : UNat. forall q : n = n. P((n, q)), p : exists n : UNat. n = n) : P(p) {
  obtain (n, q) := p;
  exact h(n, q);
}

The pattern must match the type’s shape, and a pattern needs at least two components:

import unat;

def not_a_pair(n : UNat) : UNat {
  obtain (a, b) := n;  // Error: obtain requires a dependent pair matching its pattern.
  exact a;
}
import unat;

def too_many_components(p : UNat and UNat) : UNat {
  obtain (a, b, c) := p;  // Error: obtain requires a dependent pair matching its pattern.
  exact a;
}
def one_component(p : UNat and UNat) : UNat {
  obtain (a) := p;  // Error: A pair pattern needs at least two components.
  exact a;
}

obtain does not open a propositional truncation: a merely existing witness cannot be named.

Taking a sum apart

match value { left(a) => { … } right(b) => { … } } proves the goal once for each side of a sum. Each clause is a block with its side’s value in its context. The match closes the goal.

def swap_sum(A, B : U0, value : A or B) : B or A {
  match value {
    left(a) => { exact right(a); }
    right(b) => { exact left(b); }
  }
}

def reassociate(A, B, C : U0, value : A or (B or C)) : (A or B) or C {
  match value {
    left(a) => { exact left(left(a)); }
    right(rest) => {
      match rest {
        left(b) => { exact left(right(b)); }
        right(c) => { exact right(c); }
      }
    }
  }
}

Each clause proves the goal at its side. Where the goal mentions value, the left clause sees left(a) in its place and the right clause right(b), as a match on a declared type does; a hypothesis about value is taken at each side too, under its own name.

import unat;
use unat;

def Shape(value : Unit or Unit) := match value return U0 {
  left a => UNat;
  right b => Unit;
};

def default(value : Unit or Unit) : Shape(value) {
  match value {
    left(a) => { exact 0; }
    right(b) => { exact tt; }
  }
}

A sum has two clauses, one for each side, each naming its side’s value:

def one_side(A : U0, value : A or A) : A {
  match value {  // Error: The match on a sum needs a clause for right: right(a) => { … }.
    left(a) => { exact a; }
  }
}

The cases statement, which took a sum apart without changing the goal, was removed on 2026-10-04. It is refused with the match that replaces it, which also takes its clauses as cases wrote them, left a => { … }:

def swap_cases(A, B : U0, value : A or B) : B or A {
  cases value {  // Error: cases was removed: write match value { left(a) => { … } right(b) => { … } }.
    left a => { exact right(a); }
    right b => { exact left(b); }
  }
}

Changing the goal

rw, simp and ext replace the goal with a new one and continue. Each has its own chapter: rewriting and simplification for rw and simp, and function extensionality for ext. They share one pattern. rw and simp finish the block when the new goal holds by computation; otherwise, and always after ext, a following statement proves the new goal. Here unat_add_zero(n) is the library’s proof of n + 0 = n, and rw uses it to replace the first n + 0 in the goal by n:

import unat;
use unat;

def rewrite_then_finish(n : UNat) : (n + 0) + 0 = n {
  rw [unat_add_zero(n)];      // the goal is now n + 0 = n
  exact unat_add_zero(n);
}

The rewritten goal, n + 0 = n, does not hold by computation, so a statement must follow. Without one, rw reports the goal it left:

import unat;
use unat;

def rewrite_only(n : UNat) : (n + 0) + 0 = n {
  rw [unat_add_zero(n)];  // Error: rw left an unresolved equality goal; add a following proof statement.
}

Where blocks can appear

A block can appear as the body of a block declaration, of a let with a stated type, of each clause of a match, of a calc step, and of over. A block is not an expression: to use a proof inside a term, prove it first with let name : T { … }, or move it into its own declaration.

def block_as_term : UNat and UNat {
  exact ({ exact 0; }, 1);  // Error: Expected an expression, found '{'.
}