Introduction
Cubist is a language for writing mathematics that a computer checks. A Cubist file defines objects, states theorems about them, and proves each theorem. The checker accepts a declaration only when its proof really proves its statement.
Every value in Cubist has a type. A statement is a type too, and a proof of the statement is a value of that type: proving a statement means building a value of the right type. So the language starts with types and their values, and the next chapter writes a first proof with them.
This chapter introduces the basic types one at a time: natural numbers, Unit and Void, pairs, alternatives, functions, types themselves, equality, and forall and exists. Each section shows how to write the type, how to build its values, and what the checker says about a value of the wrong type. How to use a value, such as taking a pair apart or deciding which side of an alternative holds, comes in the next chapter, with the first proofs that need it.
Every example in this reference is checked. When the checker rejects an example, its error message appears as a // Error: comment on the line at fault. Click a name in an example to see the checked kernel term behind it, with its type and context. Open in workspace opens the example in the proof workspace, where you can edit and check it. To check files on your own computer, use the command-line checker.
Every value has a type
The default natural numbers are binary: import nat; use nat; supplies Nat, an alias of BNat, with decimal and 0b literals and direct binary arithmetic. Structural zero/successor examples use import unat; use unat; and UNat. For dependent numerical induction on binary Nat, use nat_peano or nat_strong_recursion.
import nat;
use nat;
def wide : 18446744073709551615 + 1 = 18446744073709551616 { rfl; }
A Cubist file is a list of declarations. The simplest names a value:
import unat;
use unat;
def seven := 7;
def seven := 7; names the value 7. The checker works out its type, UNat, the type of explicit unary natural numbers. Read x : T as “x has type T”: here seven : UNat.
Stating the type: exact
A declaration can also state its type, after a colon. The value then goes in a block between braces, and the statement exact value; gives it:
import unat;
use unat;
def seven_again : UNat {
exact 7;
}
A short value can also follow the type directly: def seven_again : UNat := 7; means the same. Throughout Cubist, := gives a name its value, and = always means equality. The checker accepts the declaration only when the value really has the stated type. exact is the simplest statement a block can hold. The following chapters use blocks to build proofs one step at a time, and the chapter on proof blocks lists every statement.
Natural numbers
The following structural examples use unary UNat for 0, 1, 2, …. Its values are built from 0 and succ, the successor: succ(n) is n + 1. Public Nat instead stores binary bits.
In unat notation, 3 is shorthand for succ(succ(succ(0))). The unary reader accepts numerals up to 256 to bound the size of these terms. The default nat notation reads decimal and 0b literals directly into BNat without that unary limit. BNat is described with the inductive types.
Addition + and multiplication * are defined in the arithmetic library, which a file loads with import unat; at its start; use unat; then selects its notation, in which numerals and + mean the naturals'. evaluate term expecting value; checks what a term computes to:
import unat;
use unat;
def three := succ(succ(succ(0)));
evaluate three expecting 3;
evaluate 2 + 3 expecting 5;
evaluate 2 * 3 expecting 6;
Without use unat;, neither the numerals nor + mean anything. A wrong expectation is reported with the actual value:
import unat;
def five := 2 + 3; // Error: x + y means what a selected notation binds + to: for natural numbers, use nat; or write nat.(x + y).
import unat;
use unat;
evaluate 2 + 2 expecting 5; // Error: The term evaluates to 4, not 5.
Unit
Unit is the type with exactly one value, tt. A value of Unit carries no information: there is only one thing it could be. Read as a statement, Unit is trivially true.
import unat;
def nothing_much : Unit {
exact tt;
}
def forget(n : UNat) : Unit {
exact tt;
}
If you know C, its void corresponds to Unit, not to Void: a C function returning void does return, just without information, like a Cubist function returning tt. A value of another type is not a Unit:
import unat;
use unat;
def not_unit : Unit {
exact 0; // Error: Type mismatch: found UNat, expected Unit.
}
Void
Void is the empty type. Like the empty set, it has no values, so no closed term of type Void can be written. Read as a statement, Void is falsehood. Since there is nothing to give, every attempt to produce a Void fails:
def something : Void {
exact tt; // Error: Type mismatch: found Unit, expected Void.
}
A value of Void can still be assumed, as a parameter. absurd(v) turns such a value into a value of any type: no case can arise, because no v exists. The chapter on terms uses this for negation, written A -> Void.
import unat;
def from_nothing(v : Void) : UNat {
exact absurd(v);
}
Pairs: and
A and B is the type of pairs (a, b) with a : A and b : B. Three or more components are written in one tuple, (1, 2, 3), with the type UNat and UNat and UNat.
A tuple is a pair whose second component holds the rest: (1, 2, 3) is (1, (2, 3)), and UNat and UNat and UNat is UNat and (UNat and UNat). So (1, (2, 3)) also checks as UNat and UNat and UNat, and it is the same value, as the section on equality checks. Nesting on the left, ((1, 2), 3), has a different type; see tuples.
import unat;
use unat;
def pair : UNat and Unit {
exact (3, tt);
}
def triple : UNat and UNat and UNat {
exact (1, 2, 3);
}
def nested : UNat and UNat and UNat {
exact (1, (2, 3));
}
A pair needs its type stated: the checker does not guess it.
def loose := (3, tt); // Error: Pair requires an expected type.
Alternatives: or
A or B is the type of values that are either a value of A, written left(a), or a value of B, written right(b). A value remembers which side it came from. Such a type is also called a sum. The chapter on terms shows how to take such a value apart.
import unat;
use unat;
def a_number : UNat or Unit {
exact left(3);
}
def no_number : UNat or Unit {
exact right(tt);
}
More than two alternatives
or groups to the right: Unit or Unit or UNat means Unit or (Unit or UNat). So left picks the first type, and right steps into the rest, where left and right pick again:
import unat;
use unat;
def first_of_three : Unit or Unit or UNat {
exact left(tt);
}
def second_of_three : Unit or Unit or UNat {
exact right(left(tt));
}
def third_of_three : Unit or Unit or UNat {
exact right(right(5));
}
Each right steps in once, so a value deeper in the list needs every step on the way:
import unat;
use unat;
def skipped_step : Unit or Unit or UNat {
exact right(5); // Error: Type mismatch: found UNat, expected Unit or UNat.
}
right(5) offers 5 as a value of the rest, Unit or UNat, which is itself an or. right(right(5)) is the value meant.
Parentheses make a different type. In (Unit or Unit) or UNat, left first picks between the two units:
import unat;
use unat;
def second_unit : (Unit or Unit) or UNat {
exact left(right(tt));
}
def the_number : (Unit or Unit) or UNat {
exact right(5);
}
Functions: ->
A -> B is the type of functions from A to B. fun (n : UNat) => n + n is the function that doubles a number, of type UNat -> UNat. A declaration can state its type before :=, as double_again does. A declaration with parameters defines a function in one step, and f(x) applies it:
import unat;
use unat;
def double(n : UNat) := n + n;
def double_again : UNat -> UNat := fun (n : UNat) => n + n;
evaluate double(4) expecting 8;
evaluate double_again(4) expecting 8;
import unat;
use unat;
def double(n : UNat) := n + n;
def wrong_argument := double(tt); // Error: Type mismatch: found Unit, expected UNat.
The argument tt has type Unit, but double takes a UNat.
Several parameters
A function can take several parameters, separated by commas, and f(a, b) applies it to all of them. Consecutive parameters of the same type can share it: (m, n : UNat) means (m : UNat, n : UNat). The same works in fun:
import unat;
use unat;
def sum(m : UNat, n : UNat) := m + n;
def sum_again(m, n : UNat) := m + n;
def sum_fun := fun (m, n : UNat) => m + n;
evaluate sum(3, 4) expecting 7;
evaluate sum_again(3, 4) expecting 7;
evaluate sum_fun(3, 4) expecting 7;
The comma between names is required:
def sum_spaced(m n : UNat) := m + n; // Error: Separate names with commas: (n, m : Nat)
A function of two numbers has type UNat -> UNat -> UNat: given m, it returns a function that waits for n. So arguments can be supplied a few at a time, and sum(3) is the function that adds 3:
import unat;
use unat;
def sum(m, n : UNat) := m + n;
def add_three := sum(3);
evaluate add_three(4) expecting 7;
Functions in a block: intro
A function can also be built in a block, like any other value. When the type to give is a function type A -> B, intro a; takes the input: it names it a, of type A, and what remains to give is a value of B, which can use a. With several names, separated by commas, intro takes several inputs at once:
import unat;
use unat;
def double : UNat -> UNat {
intro n; // n : UNat; what remains to give is a UNat
exact n + n;
}
def sum : UNat -> UNat -> UNat {
intro m, n; // m : UNat and n : UNat; what remains to give is a UNat
exact m + n;
}
evaluate double(4) expecting 8;
evaluate sum(3, 4) expecting 7;
This double is the same function as def double(n : UNat) := n + n;. The next chapter calls the type that remains to give the goal, and the names available the context. In the proof workspace, clicking a line number of a block shows both. A type that is not a function has no input to take:
import unat;
def seven : UNat {
intro n; // Error: intro requires a dependent function goal.
exact 7;
}
UNat is not a function type. The message’s dependent function types are the forall types below, and A -> B is one of them.
Types are values too
A type is itself a value, of a type called a universe. UNat, Unit and UNat and Unit have type U0, the universe of small types. U0 itself has type U1, the next universe. So types can be named, and functions can build them:
import unat;
use unat;
def Pair := UNat and Unit;
def p : Pair {
exact (1, tt);
}
def Twice(A : U0) := A and A;
def q : Twice(UNat) {
exact (1, 2);
}
def nat_is_a_type : U0 {
exact UNat;
}
A universe does not contain itself:
def too_big : U0 {
exact U0; // Error: Type mismatch: found U1, expected U0.
}
Equality: =
For two values x and y of the same type, x = y is a type: the statement that they are equal. Its values are evidence of that equality. refl(x), short for reflexivity (every value is equal to itself), is evidence that x = x, and the checker also accepts it as evidence of x = y whenever x and y compute to the same value:
import unat;
use unat;
def two_plus_two : 2 + 2 = 4 {
exact refl(4);
}
def seven_is_seven : 7 = 7 {
exact refl(7);
}
2 + 2 computes to 4, so refl(4) proves 2 + 2 = 4. In a block, rfl; says the same without repeating the value: it closes a goal x = y whose two sides compute to the same value. The tuple and the nested pair of the pairs section are equal this way:
import unat;
use unat;
def two_plus_two_again : 2 + 2 = 4 {
rfl;
}
def triple : UNat and UNat and UNat := (1, 2, 3);
def nested : UNat and UNat and UNat := (1, (2, 3));
def same_value : triple = nested {
rfl;
}
Values that are not equal have no such evidence:
import unat;
use unat;
def wrong_sum : 2 + 2 = 5 {
exact refl(4); // Error: Type mismatch: found 4 = 4, expected 2 + 2 = 5.
}
The message shows both types as they would be written in a file. An equality is a type like any other, so it can be a parameter, an assumption to reason from, or part of a larger type. Equalities that do not hold by computation, such as n + 0 = n for a variable n, need a proof. The chapter on computation says exactly which equalities hold by computation, and the chapter on equality and paths describes the tools for the others.
Dependent types: forall and exists
A function’s result type can depend on its argument. forall x : A. B is the type of functions that take any x : A and return a value of B, where B may mention x. A -> B is the special case where it does not: the two are the same type, as the chapter on equality checks. The dot ends the type of x, and the body follows it. Several names can share the type, as parameters do: forall x, y : A. B.
import unat;
use unat;
// `and` binds tighter than `->`, so `A -> A and A` means `A -> (A and A)`.
def duplicate : forall A : U0. A -> A and A {
exact fun (A : U0, a : A) => (a, a);
}
// The same function, built with intro.
def duplicate_again : forall A : U0. A -> A and A {
intro A, a; // A : U0 and a : A; what remains to give is A and A
exact (a, a);
}
def one_one := duplicate(UNat, 1);
duplicate takes a type A and then a value of that type; intro A, a; takes the two inputs of duplicate_again in the same order. Its result type, A and A, depends on which type it was given: duplicate(UNat, 1) is the pair (1, 1). The chapter on terms lists the full precedence of the operators. The result must fit the type given as the first argument:
import unat;
use unat;
def duplicate : forall A : U0. A -> A and A {
exact fun (A : U0, a : A) => (a, 0); // Error: Type mismatch: found UNat, expected A.
}
A comma cannot end the type. In a parameter list such as (P : UNat -> U0, f : forall n : UNat. P(n)), a comma separates parameters, so it would read as the start of the next one:
// Error: End forall's type with a dot: forall n : Nat. P(n)
def identity_on_nat : forall n : UNat, UNat := fun (n : UNat) => n;
A forall type is itself a value, like every type. Compare a function that builds a type with a single type that quantifies over all types:
def Twice(A : U0) := A and A;
def AlsoTwice : U1 {
exact forall A : U0. A and A;
}
Twice is a function from types to types: Twice(UNat) is UNat and UNat. AlsoTwice is one type: the type of functions that give a pair of values in every type. It quantifies over all of U0, so it lives in the next universe, U1. It has no values, because Void has no pair of values.
exists x : A. B is the type of pairs whose second component’s type depends on the first: a value x : A, together with a value of B for that x. When B does not mention x, nothing depends on the first component, and exists x : A. B is the same type as A and B, just as A -> B is forall x : A. B without the dependency. The chapter on equality checks this too.
import unat;
use unat;
def pointed : exists A : U0. A {
exact (UNat, 3);
}
def two_of_a_kind : exists A : U0. A and A {
exact (UNat, (1, 2));
}
The first component decides the type of the second:
import unat;
def pointed : exists A : U0. A {
exact (UNat, tt); // Error: Type mismatch: found Unit, expected UNat.
}
Read as statements, forall and exists are the quantifiers “for all” and “there exists”. A value of exists n : UNat. P(n) is a witness n together with evidence that P(n) holds. The next chapter starts with proofs about and and or, then proves a statement with both quantifiers: forall n : UNat. exists m : UNat. lt(n, m), every number has a greater one.