READ THE ARGUMENT. INSPECT THE EVIDENCE.
Infinitely many primes
Write mathematics, follow definitions, and check every inference with the C kernel.
These proofs belong to the archived first library, kept checked while a rebuilt library replaces it. See the results it established.
This module is a Cubist test: cases the test suite checks, kept
in cubist-tests/ so that each can be checked and its
derivation inspected here.
Real-number development in progress: the shared interface and preliminary construction lemmas are checked. The three complete ordered field instances are not yet proved. Scope and assumptions.
Checked homotopy model: loop generation, winding numbers, and the additive period formula. The comparison with continuous paths in the punctured plane and the residue theorem remain to be proved. Proofs and assumptions.
Checked prerequisites: complex arithmetic, continuous straight segments, finite contour sums, dyadic integral limits under explicit field hypotheses, and abstract winding obstructions. Concrete complete real and complex fields, general contour integration, the residue theorem, algebraic closure, and Great Picard remain to be proved. Results and remaining work.
Proof source
The source as loaded. When the check finishes, each name links to its checked type, context, and definition.
0 kernel steps · 0 definitions checked · Loading proof…
Contextual console
Console
Open the REPL page
The names checked in this file are loaded. typeof NAME; shows a type,
evaluate TERM; computes a value, and let x := TERM; adds a
name. /help lists every command, and /modules the modules import can load.
Quick reference
One checked example for each construct, linked to its chapter of the language reference. Each example is checked when it scrolls into view. Click a name in it to inspect its kernel term, or open it in the workspace.
Declarations and files
def
def name(params) := term; infers the type; def name(params) : T := term; states it; def name(params) : T { … } proves T in a block. Use def for constructions and proofs alike.
A first proof and files →
import unat;
use unat;
def four : UNat := 4;
def add_two(n : UNat) := succ(succ(n));
def add_two_to_two : add_two(2) = four {
exact refl(4);
}
Parameters and application
Every parameter has a type, and consecutive ones may share it, as in (A, B : U0, x, y : A). f(a, b) means f(a)(b), so supplying some arguments gives a function of the rest.
A first proof and files →
import unat;
use unat;
def pick_second(A, B : U0, x, y : A, b : B) := y;
def picked := pick_second(UNat, Unit, 1, 2, tt);
def from_one := pick_second(UNat, Unit, 1);
Imports and descriptions
Imports come first. Comments start with //; those directly above a declaration become its description in the inspector, and an empty // line separates paragraphs.
A first proof and files →
import unat;
use unat;
// Seven, as a sum.
//
// The inspector shows this description.
def seven := 3 + 4;
Types and terms
Functions: fun
fun (x : A) => body constructs a function, and fun (x, y : A) => body takes several arguments. fun x => body reads the domain from an expected function type.
Functions, pairs and sums →
import unat;
def twice(A : U0, f : A -> A) := fun (x : A) => f(f(x));
def add_two := twice(UNat, fun n => succ(n));
Dependent functions: forall
forall x : A. B is a dependent function type (Π): its result type may mention the input. A -> B is the case where it does not.
Functions, pairs and sums →
import unat;
use unat;
def apply_at_zero(P : UNat -> U0, f : forall n : UNat. P(n)) : P(0) {
exact f(0);
}
Holes and named arguments: _, x := e
A hole _ is an argument the other arguments' types or the expected type determine. x := e gives the parameter x; the parameters before it that nothing gives are holes. Click a hole to see its value.
Functions, pairs and sums →
import unat;
def concat(U < UU0, A : U, x, y, z : A, p : x = y, q : y = z) : x = z := trans(p, q);
def joined(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat(U0, _, _, _, _, p, q);
def named(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat(U0, p := p, q := q);
Implicit parameters: def f{{A : U}}(…)
Parameters in double braces before the parameter list are implicit: a call reads them off its other arguments, universes included. To give them, write them in double braces after the name, in order or by name: concat{{U0, UNat}}(p, q), concat{{A := UNat}}(p, q).
Functions, pairs and sums →
import unat;
def concat{{U < UU0, A : U, x, y, z : A}}(p : x = y, q : y = z) : x = z := trans(p, q);
def joined(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat(p, q);
def given(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat{{U0, UNat}}(p, q);
Pairs, tuples and exists
A and B is a product and exists x : A. B a dependent pair (Σ) with an actual witness. (a, b, c) abbreviates (a, (b, c)); hover the parentheses to see the expansion.
Functions, pairs and sums →
import unat;
use unat;
def triple : UNat and Unit and UNat {
exact (1, tt, 2);
}
def two_exists : exists n : UNat. n = 2 {
exact (2, refl(2));
}
Using a pair: unpack
unpack p as (a, b) return T { … } takes a pair apart in a term. For a result that depends on the whole pair, use pair_induction.
Functions, pairs and sums →
import unat;
def first_number(pair : UNat and UNat) :=
unpack pair as (a, b) return UNat { a; };
Sums: or, left, right
A or B is a disjoint sum, shown as A + B in kernel notation. left(a) and right(b) inject into it.
Functions, pairs and sums →
import unat;
use unat;
def on_the_left := typed(Unit or UNat, left(tt));
def on_the_right : Unit or UNat {
exact right(3);
}
Case analysis: match
match value return T { left a => …; right b => …; } computes by cases on a sum. With as z, the result type may depend on the value.
Functions, pairs and sums →
import unat;
use unat;
def to_number(value : Unit or UNat) := match value return UNat {
left u => 0;
right n => n;
};
Unit and Void
tt : Unit is the one value of Unit. Void has none, and absurd(v) turns an impossible v : Void into any type.
Functions, pairs and sums →
def from_void(A : U0, impossible : Void) : A {
exact absurd(impossible);
}
def unit_is_tt(u : Unit) : u = tt {
exact unit_induction(fun (v : Unit) => v = tt, refl(tt), u);
}
Numbers
Default Nat literals are binary; select nat for them. The structural examples here use explicit unary UNat. With import unat; and use unat;, numerals, +, *, < and <= are the naturals' and compute.
Functions, pairs and sums →
import unat;
use unat;
def two_times_three : 2 * 3 = 6 {
exact refl(6);
}
def two_below_three : 2 < 3 {
exact tt;
}
Stating a type: typed
typed(T, term) supplies an expected type, for pairs, injections and functions whose domain is not written.
Functions, pairs and sums →
import unat;
def successor := typed(UNat -> UNat, fun n => succ(n));
Proof blocks
intro
Introduces the next input of a forall goal, or the assumption of an implication; intro x, y, h; introduces several. Click a line number in the workspace to see the goal.
Proof blocks →
def curry(A, B, C : U0) : ((A and B) -> C) -> A -> B -> C {
intro f, a, b;
exact f((a, b));
}
exact
Supplies a term of the goal's type and finishes the block. Like match, rfl, calc and simpa, nothing follows it in its block.
Proof blocks →
def identity_function(A : U0) : A -> A {
exact fun (a : A) => a;
}
let
let x := term; names a term, let x : T := term; checks it against T, and let x : T { … } proves T in a block. The checker sees through every form.
Proof blocks →
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;
}
obtain
Unpacks a pair or an existential into its parts, with the same tuple shape as (a, b, c).
Proof blocks →
import unat;
def witness_(t : exists n : UNat. (n = n) and Unit) : UNat {
obtain (n, same, u) := t;
exact n;
}
match on a sum
Splits a sum into one block per side, each proving the goal at its side. Proof blocks →
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); }
}
}
Computation and conversion
Equal by computation
Two terms are definitionally equal when they compute to the same normal form: functions apply, definitions unfold, and eliminators compute on constructors. refl and rfl prove exactly these equalities; n + 0 = n for a variable n is not one of them. Older proofs’ with unfolding [name] { expression } is still accepted, and changes nothing.
Computation and conversion →
import unat;
use unat;
def double(n : UNat) := n + n;
def double_two : double(2) = 4 {
rfl;
}
def applied : (fun (n : UNat) => succ(n))(0) = 1 {
rfl;
}
Universes
Universe constants
U0 : U1 : U2 and so on; each universe also lives in every larger one. UU0 lies above all of them, and UU1 above that.
Universes →
def large_identity(A : U1, x : A) := x;
def small_in_large : U1 := U0;
def every_small_universe : UU0 := U7;
Universe variables: U < UU0
A parameter U < UU0 ranges over the universes below UU0. The definition is checked once, for all of them, and a use such as identity(U0, …) instantiates it.
Universes →
import unat;
use unat;
def identity(U < UU0, A : U, x : A) : A := x;
def three := identity(U0, UNat, 3);
def small_identity := identity(U0);
next and max
next(U) is the universe above U, and max(U, V) the larger of two.
Universes →
def type_of(U < UU0) : next(U) := U;
def both(U, V < UU0, A : U, B : V) : max(U, V) := A and B;
Equality and paths
Equality and refl
x =[T] y is equality in T, and x = y infers the carrier. refl(x) proves x = x, and any equality whose sides compute to the same value.
Equality and paths →
import unat;
use unat;
def explicit_carrier(A : U0, x : A) : x =[A] x {
exact refl(x);
}
def by_computation : succ(succ(0)) = 2 {
exact refl(2);
}
sym, trans and cong
sym(p) reverses a path, trans(p, q) joins two, and cong(f, p) maps one through f. They are checked constructions, not axioms.
Equality and paths →
def join_and_map(A, B : U0, f : A -> B, x, y, z : A, p : x = y, q : y = z) : f(z) = f(x) {
exact sym(cong(f, trans(p, q)));
}
transport
transport v along p in C moves v : C(x) along p : x = y into C(y), with the endpoints read from p. The explicit call transport(C, x, y, p, v) is also available.
Equality and paths →
def move(A : U0, C : A -> U0, x, y : A, p : x = y, v : C(x)) : C(y) {
exact transport v along p in C;
}
Path induction
path_induction proves a statement about every path from the case of refl.
Equality and paths →
def symmetric(A : U0, x, y : A, p : x = y) : y = x {
exact path_induction(A, fun (a, b : A, q : a = b) => b = a,
fun (a : A) => refl(a), x, y, p);
}
Propositions, sets and hlevel
import hlevels; defines IsContr, IsProp, IsSet and HasLevel(U, n, A), and hlevel; proves them from evidence and the type's shape.
Equality and paths →
import hlevels;
def functions_into_nat(A : U0) : IsSet(U0, A -> UNat) {
hlevel;
}
Natural numbers and inductive types
inductive
inductive Name(params) : U0 { c; d(x : A, rest : Name(params)); } declares a type by its constructors. A constructor takes only its declared arguments; the type's parameters come from the expected type.
Natural numbers and inductive types →
import unat;
use unat;
inductive List(U < UU0, A : U) : U {
nil;
cons(head : A, tail : List(U, A));
}
def numbers : List(U0, UNat) := cons(2, cons(3, nil));
match and structural recursion
match n { zero => …; succ(k) => …; } gives one branch per constructor. A definition whose body is the match can call itself on a child such as k. In a proof block, match n { zero => { … } succ(k) => { … } } proves the goal for each constructor. A match can take apart several values, match m, n { … }, with nested patterns, variables and _; the first clause that fits a case takes it.
Natural numbers and inductive types →
import unat;
use unat;
def double(n : UNat) : UNat := match n {
zero => 0;
succ(k) => succ(succ(double(k)));
};
def double_three : double(3) = 6 { rfl; }
induction
induction v [as z] return C { c(xs) with hs => …; } on any declared type: each clause names the constructor’s fields in parentheses, then one induction hypothesis per recursive field after with. Omit with to leave all hypotheses unnamed. In a proof block, induction v { c(xs) with hs => { … } } takes its motive from the goal. Natural numbers also have zero => …; succ h => …;.
Natural numbers and inductive types →
import unat;
use unat;
inductive List(U < UU0, A : U) : U {
nil;
cons(head : A, tail : List(U, A));
}
def length(xs : List(U0, UNat)) : UNat := induction xs return UNat {
nil => 0;
cons(head, tail) with ih => succ(ih);
};
Binary literals
Where nat's notation is selected, 0b110 is six in Nat, the library's binary naturals: its literal rule reads the digits and computes one constructor per bit, and reads a decimal literal such as 6 into the same bits. unat keeps the structural unary reader.
Natural numbers and inductive types →
import nat;
use nat;
def six : Nat := 0b110;
Equational reasoning and simplification
rfl
Closes an equality whose two sides compute to the same value. Equational reasoning →
import unat;
use unat;
def successor_first(n, m : UNat) : succ(n) + m = succ(n + m) {
rfl;
}
calc
Chains equalities; _ is the previous right side. A step is proved by a term or a nested block.
Equational reasoning →
import unat;
use unat;
def through(a, b : UNat, p : a = b) : a + 0 = b {
calc {
a + 0 = a by unat_add_zero(a);
_ = b by p;
}
}
rw
Rewrites the goal with instantiated equalities, in order; <- rewrites right to left, and at lhs occurrence 2 picks one place. A goal that then holds by computation is closed.
Equational reasoning →
import unat;
use unat;
def rewrite_then_finish(n, m : UNat, h : n = m) : n + 0 = m {
rw [unat_add_zero(n)]; // goal: n = m
exact h;
}
simp only
Rewrites with the listed rules everywhere, repeatedly, finding their arguments by matching. Click a simp in the workspace to see its trace.
Equational reasoning →
import unat;
use unat;
def add_zero_twice(n : UNat) : (n + 0) + 0 = n {
simp only [unat_add_zero];
}
simpa
Simplifies both the goal and the type of a hypothesis, then uses the hypothesis. Equational reasoning →
import unat;
use unat;
def simpa_example(n, m : UNat, h : n + 0 = m) : n = m + 0 {
simpa only [unat_add_zero] using h;
}
simp_rule and simp_set
simp_rule registers a default rule and simp_set names a set; both carry through imports. Then simp; uses the defaults, and simp [set] at h as h2; adds a simplified copy of h.
Equational reasoning →
import unat;
use unat;
simp_rule unat_add_zero priority 10;
simp_set units := [unat_add_zero];
def by_default(n : UNat) : (n + 0) + 0 = n {
simp;
}
def simplified_copy(n, m : UNat, h : n + 0 = m) : n = m {
simp [units] at h as h2; // h2 : n = m
exact h2;
}
Conditional rules
A rule with a premise fires when simp with [h]; supplies it.
Equational reasoning →
import unat;
use unat;
def zero_if(n : UNat, h : n = 0) : n + 0 = 0 {
calc {
n + 0 = n by unat_add_zero(n);
_ = 0 by h;
}
}
simp_rule zero_if priority 20;
def conditional(n : UNat, h : n = 0) : n + 0 = 0 {
simp with [h];
}
Theories and models
theory
theory T(U < UU0) { M : set U; mul(x, y : M) : M notation x * y; law … ; } declares a kind of structure. T(U) is the type of its models, T.make(…) builds one field by field, and m.f reads a field. theory T(U < UU0) extends P, label : Q(f := g) { … } takes its parents' fields, renamed; m.label is the parent's model.
Theories and models →
import unat;
import hlevels;
use unat;
theory Pointed(U < UU0) {
M : set U;
point : M;
}
def zero_pointed : Pointed(U0) := Pointed.make(M := UNat, M_is_set := unat_is_set, point := 0);
def zero_point : zero_pointed.point = 0 { rfl; }
use
use m; puts the model m's fields in scope by their names for the rest of the block, or of the file at its top level, and its theory's notations mean its operations; m.(e) does so for one expression, and a m.(*) b qualifies one operator.
Theories and models →
import hlevels;
theory Magma(U < UU0) {
M : set U;
mul(x, y : M) : M notation x * y;
}
def cube(G : Magma(U0), x : G.M) : G.M {
use G;
exact x * x * x;
}
The library's algebra
import algebra; gives the lattice from Magma through Quasigroup, Loop, AssociativeQuasigroup, UnitalMagma, Semigroup and Monoid to Group, plus CommMonoid, AbelianGroup, Ring, CommRing and Field, and lemmas that take a model first, as mul_zero(A, x). integers is a commutative ring and rationals a field. import ordered_algebra; adds OrderedRing, OrderedCommRing and OrderedField.
Theories and models →
import rationals;
def times_zero(x : Q) : rationals.mul(x, rationals.zero) = rationals.zero := mul_zero(rationals.comm_ring, x);
section
section {{U < UU0}}(G : Monoid(U)) { def …; } gives each definition in it the section's parameters first, opens each model among them, and applies the section's earlier definitions to them.
Theories and models →
import unat;
use unat;
section (n : UNat) {
def twice := n + n;
def twice_unfolds : twice = n + n {
rfl;
}
}
def six : twice(3) = 6 {
rfl;
}
Cubical paths and higher inductive types
path i => and p @ i
A path is a function of an interval coordinate. Where a path type is expected, path i => body builds one, and p @ i evaluates p at i.
Cubical paths →
def reverse(A : U0, x, y : A, p : x = y) : y = x {
exact path i => p @ flip(i);
}
def at_the_start(A : U0, x, y : A, p : x = y) : p @ 0 = x {
exact refl(x);
}
ext
Reduces f = g to f(x) = g(x), without an axiom.
Cubical paths →
def pointwise_path(A, B : U0, f, g : A -> B, h : (forall x : A. f(x) = g(x))) : f = g {
ext x;
exact h(x);
}
Dependent paths: PathP and apd_path
PathP(family, a, b) is a path over a family of types. apd_path(f, p) is the dependent path of a dependent function over p, and lift q along p in C constructs one from an equality q after transport, using the expected path type for its endpoints.
Cubical paths →
def section_path(A : U0, C : A -> U0, f : (forall a : A. C(a)), x, y : A, p : x = y) :
PathP(fun (i : Interval) => C(p @ i), f(x), f(y)) {
exact apd_path(f, p);
}
Composition: comp
comp(family, base, walls…) fills from coordinate 0 to 1, starting at the base. A wall face(i, 0, …) fixes the side where another coordinate is 0. With no walls, comp is transport.
Cubical paths →
def join_(A : U0, x, y, z : A, p : x = y, q : y = z) : x = z {
exact path i => comp(fun (j : Interval) => A, p @ i,
face(i, 0, fun (j : Interval) => x),
face(i, 1, fun (j : Interval) => q @ j));
}
Path constructors
An inductive declaration can have constructors that build paths, written with their endpoint equality as the result type. A match clause loop @ i => … gives the result along the path, and must agree with the point clauses at its ends.
Cubical paths →
inductive Circle : U0 {
base;
loop : base = base;
}
def reverse(c : Circle) : Circle := match c {
base => base;
loop @ i => loop @ ~i;
};
Coherence obligations: obligations
Separates path and squash clauses from the computational point clauses of a match: write named clauses in obligations { c(xs) @ i => … }, or prove omitted declared path clauses with obligations by rfl, obligations by { … } or obligations by term. The squash clause of a truncated type is synthesized from h-level evidence, with hints from obligations by hlevel with [h].
Cubical paths →
import unat;
use unat;
inductive Circle : U0 {
base;
loop : base = base;
}
def flatten(c : Circle) : UNat := match c {
base => 0;
} obligations {
loop @ i => 0;
};
Set quotients
import quotients; gives Quotient(U, A, R), with a class for each element and a path between related classes. A map into a set that respects the relation descends to it (descend, descend2), and for an equivalence relation valued in propositions, equal classes have related elements (quotient_effective).
Cubical paths and higher inductive types →
import quotients;
// UNat with every two numbers related: one class.
def Everything(m, n : UNat) : U0 := Unit;
def Collapsed : U0 := Quotient(U0, UNat, Everything);
def one_class(m, n : UNat) : typed(Collapsed, class(m)) = typed(Collapsed, class(n)) :=
class_path(U0, UNat, Everything, m, n, tt);
Pushouts
import pushout; declares Pushout(U, V, W, C, A, B, f, g), which glues A and B along the two maps from C: the path constructor push(c) joins inl(f(c)) to inr(g(c)).
Cubical paths →
import unat;
import pushout;
def TwoPoints : U0 := Pushout(U0, U0, U0, UNat, Unit, Unit, fun (n : UNat) => tt, fun (n : UNat) => tt);
def west : TwoPoints := inl(tt);
def east : TwoPoints := inr(tt);
def bridge(n : UNat) : west = east {
exact push(n);
}
Suspensions
Suspension, north, south and meridian are ordinary definitions from import suspension_types;, built as pushouts.
Cubical paths →
import suspension_types;
def pole_path(A : U0, a : A) : north(A) = south(A) {
exact meridian(A, a);
}
Excluded middle, choice and computability
Excluded middle and choice
The library’s classical_axioms states LEM and Choice, the two classical assumptions, as axioms: definitions whose value is axiom of a statement, as in def LEM := axiom ExcludedMiddle;, each a name with a type and no computation rule. Their conclusions are truncations, Trunc, which is no assumption. Each is generic over the universes below UU0. The library’s continuum_axioms assumes the continuum hypotheses so too, as optional assumptions: CH, GCH, DecidableCH and DecidableGCH. A module states an axiom of its own the same way.
Excluded middle, choice and computability →
import classical_axioms;
def excluded_middle(A : U0, nn : (A -> Void) -> Void) : Trunc(U0, A) {
exact LEM(U0, A, nn);
}
computable def inhabited(A : U0, a : A) : Trunc(U0, A) {
exact merely(U0, A, a);
}
Function extensionality and univalence
FunExt, ua and UnivalenceBeta are constructions that compute, not assumptions.
Excluded middle, choice and computability →
computable def extensional(A : U0, B : A -> U0, f, g : forall a : A. B(a),
h : forall a : A. f(a) = g(a)) : f = g {
exact FunExt(U0, A, B, f, g, h);
}
computable def
Rejects the declaration if it uses an assumption, directly or through a definition. Excluded middle, choice and computability →
import unat;
use unat;
computable def double(n : UNat) := n + n;
evaluate
evaluate term expecting value; checks what a closed term computes to. The term may use no assumption. A value with holes, as (7, _), is a pattern that computes only what it observes, !!_ asks for the normal form, and !!!_ for the full normal form.
Excluded middle, choice and computability →
import unat;
use unat;
def double(n : UNat) := n + n;
evaluate double(3) expecting 6;