Excluded middle and choice
Cubist’s own rules are constructive. A proof builds its evidence, so a proof of A or B says which side holds, and a closed term computes to a value. Two principles of classical mathematics cannot be built this way: excluded middle, that every statement is true or false, and the axiom of choice. The library’s classical_axioms module states each as an assumption: a name with a type and no computation rule. A definition whose value is axiom of a statement assumes it:
def LEM := axiom ExcludedMiddle;
| Assumption | Statement, at U0 |
|---|---|
LEM(U0, A, doubleNegation) | Excluded middle: if A cannot be refuted, doubleNegation : (A -> Void) -> Void, then A merely holds, Trunc(U0, A) |
Choice(U0, A, B, setA, setFibers, inhabited) | The axiom of choice, for a set A and a family of sets B over it: if every B(a) merely has an element, inhabited : forall a : A. Trunc(U0, B(a)), then there merely is a function giving one for each a, Trunc(U0, forall a : A. B(a)) |
Both conclude that something merely holds. Trunc(U0, A), the library’s propositional truncation, says that A has an element, without providing one. It is a declared type of the module h1_truncation, which classical_axioms imports, so importing classical_axioms brings Trunc into scope too. It is no assumption: its point merely(U0, A, a) computes, and mere_eliminate maps it into a proposition. The inspector lists every assumption a theorem uses, computed from its checked term, its type and the definitions they mention: these two as LEM and Choice, and any other axiom by its module and name. Every axiom of the library, as read from library/ with every module it imports, is listed by its bare name; a module of a library module’s name from elsewhere, or edited, or one that imports such a module, is listed as any other, as classical_axioms::LEM. The two are independent: excluded middle does not request choice. To reason under a hypothesis of your own, take it as a parameter. The result then holds for every value of the hypothesis, which stays visible in its type.
Every result is reported with the assumptions it relies on, a printed term too: this example’s status reads print inspect at line 3: LEM(U0), assumes LEM.
import classical_axioms;
print(inspect(LEM(U0))); // Output: LEM(U0)
Excluded middle
A proof of A or (A -> Void) decides which of the two holds, and for most statements no construction can. Excluded middle is assumed in the form a proof most often needs: if A cannot be refuted, then A holds. A refutation of A is a function A -> Void, so “cannot be refuted” is (A -> Void) -> Void, and any element of A gives one:
import classical_axioms;
def unrefuted(A : U0, a : A) : (A -> Void) -> Void {
intro refutation;
exact refutation(a);
}
def excluded_middle_here(A : U0, nn : (A -> Void) -> Void) : Trunc(U0, A) {
exact LEM(U0, A, nn);
}
The converse is excluded middle. Its conclusion is Trunc(U0, A), not A: it asserts that A has an element without naming one, since an assumption has no rule that could compute it. The truncation is also what keeps excluded middle consistent with univalence. A function that produced an element of every non-empty type would have to respect every equivalence of types, which is impossible (Homotopy Type Theory, Theorem 3.2.2).
For a proposition, a type whose elements are all equal, merely holding and holding are the same, so excluded middle gives the statement itself. The library’s h1_classical module proves both familiar forms, for a proposition P in any universe:
import h1_classical;
def not_not(P : U0, prop_ : IsProp(U0, P), nn : (P -> Void) -> Void) : P {
exact double_negation(U0, P, prop_, nn);
}
def decide(P : U0, prop_ : IsProp(U0, P)) : P or (P -> Void) {
exact decide_prop(U0, P, prop_);
}
IsProp(U0, P) is forall x, y : P. x = y, from the library’s hlevels. decide is excluded middle as it is usually stated: every proposition holds or fails. Both use LEM, and the inspector lists it.
The axiom of choice
If every B(a) has an element, there is a function picking one for each a. When the elements are actually given, as f : forall a : A. B(a), the function is f itself, and no assumption is needed. The axiom of choice covers the case where each B(a) only merely has an element: it concludes that such a function merely exists.
import classical_axioms;
def choose(A : U0, B : A -> U0, setA : IsSet(U0, A), setB : forall a : A. IsSet(U0, B(a)),
inhabited : forall a : A. Trunc(U0, B(a))) : Trunc(U0, forall a : A. B(a)) {
exact Choice(U0, A, B, setA, setB, inhabited);
}
A and every B(a) must be sets, types in which any two paths between the same elements are equal (propositions and sets); here IsSet(U0, A) comes from the library’s hlevels module, which classical_axioms imports too. Without these conditions the statement can fail: with univalence, there is a family of sets over a type that is not a set for which it is false (Homotopy Type Theory, Lemma 3.8.5). The library’s surjections module uses choice to show that every surjection between sets merely has a right inverse.
Truncation: Trunc
Both axioms conclude a truncation, Trunc(U, A), which is no assumption: the library declares it in h1_truncation as a proposition in A’s own universe (the library’s truncation). Its point point(a), also merely(U, A, a), computes, and its generated Trunc.squash identifies any two of its elements. A function out of it must respect Trunc.squash, so it can only prove a proposition, as mere_eliminate does: a merely existing element can be used in a proof whose result does not depend on which element it is. So the function that choice merely provides can be used to prove that a right inverse merely exists, but never to compute one.
The first library, in the archive, used an older truncation, Truncate(U0, A), which resized every truncation into U0, given by four builtin assumptions, Truncate, TruncateIntro, TruncateProp and TruncateElim, with an excluded middle and a choice of its own over it. The archive’s modules now use Trunc and the axioms of classical_axioms, with PropResizing where a result needs a resized proposition, and the legacy builtins are removed from the language: their names are unknown, as LEM and Choice are where nothing binds them. A module that uses LEM without importing classical_axioms meets that:
// Error: Untranslated name: LEM
def excluded(A : U0, nn : (A -> Void) -> Void) := LEM(U0, A, nn);
Universes
An axiom is generic over the universes below UU0, as its statement is, and its first argument selects the universe: LEM(U1, A, nn) is excluded middle for a type A : U1, and a universe variable works too. The universe and the later arguments can be supplied separately: Choice(U0) is the axiom of choice at U0, a function that can be named and passed on. Each assumption is one entry of the kernel’s context, and each use instantiates it at its universe. A declaration’s assumptions are therefore listed by name, once each, whatever universes they are used at: LEM, not LEM(U0). The inspector shows every use with its universe argument. An assumption holds only below UU0.
import classical_axioms;
def choice_at_zero := Choice(U0);
def excluded_middle_at(U < UU0, A : U, nn : (A -> Void) -> Void) : Trunc(U, A) := LEM(U, A, nn);
import classical_axioms;
// Error: A universe argument must lie below UU0: U0, U1, … or a universe variable.
def large(T : UU0, nn : (T -> Void) -> Void) := LEM(UU0, T, nn);
A truncation keeps its universe: Trunc(U1, U0) is a proposition in U1, and Trunc(U0, U0) is refused, because U0 is not a type in U0. Nothing resizes a truncation into a smaller universe; only the assumption PropResizing gives a proposition a copy in one.
import classical_axioms;
def truncated_types := Trunc(U1, U0);
import classical_axioms;
def too_large := Trunc(U0, U0); // Error: Type mismatch: found U1, expected U0.
The statements as types
The library module classical_axioms names the statements of the two classical assumptions, for every universe U < UU0: ExcludedMiddle(U) is the type of LEM(U), and AxiomOfChoice(U) is the type of Choice(U), since each axiom assumes its statement’s body over the statement’s universe. A result can take excluded middle as a parameter of that type, and the assumption is supplied only where the result is used:
import classical_axioms;
computable def merely_under(lem : ExcludedMiddle(U0), A : U0, nn : (A -> Void) -> Void) : Trunc(U0, A) {
exact lem(A, nn);
}
def merely_assumed(A : U0, nn : (A -> Void) -> Void) : Trunc(U0, A) {
exact merely_under(LEM(U0), A, nn);
}
Only merely_assumed uses LEM; merely_under uses no assumption, and is computable. A result can also state an equivalence with excluded middle: the library’s universe_automorphisms proves that ExcludedMiddle(U0) holds exactly when there merely is an automorphism of U0 sending Unit to Void.
Optional assumptions: the continuum hypotheses
The library’s continuum_hypothesis module states further principles as types, for every universe U < UU0, and assumes none of them: the continuum hypothesis ContinuumHypothesis(U), that no set lies strictly between Nat and its powerset in cardinality; its generalization GeneralizedContinuumHypothesis(U), the same for every set A into which Nat merely injects and the powerset of A; and the stronger DecidableContinuumHypothesis(U) and DecidableGeneralizedContinuumHypothesis(U), by which a set between the two is merely equinumerous with one of them. It proves the implications among them, each taking its premise as a parameter. The separate module continuum_axioms assumes these four as CH, GCH, DecidableCH and DecidableGCH:
def CH := axiom ContinuumHypothesis;
A module states that it may rely on them by importing continuum_axioms. One that imports only continuum_hypothesis has none of them in scope, and may as well assume the negation of the continuum hypothesis, or leave it open. With all four in scope, a result is still listed with exactly those it uses:
import continuum_axioms;
computable def ch_under(U < UU0, gch : DecidableGeneralizedContinuumHypothesis(U)) :
ContinuumHypothesis(U) := gch_implies_ch(U, decidable_gch_implies_gch(U, gch));
def ch_assumed : ContinuumHypothesis(U0) := ch_under(U0, DecidableGCH(U0));
ch_under uses no assumption, and is computable; ch_assumed uses DecidableGCH alone, and is not.
Propositional resizing
A proposition lives in a universe, as every type does: a proposition in U1, such as the truncation of a type in U1, is no type in U0. Propositional resizing assumes that each has a copy there. The library’s classical_axioms states it from U1 to U0, with IsProp from hlevels, and assumes it:
def PropResize(P : U1) := exists Q : U0. IsProp(U0, Q) and (P -> Q) and (Q -> P);
def PropositionalResizing := forall P : U1. IsProp(U1, P) -> PropResize(P);
def PropResizing := axiom PropositionalResizing;
For a proposition P : U1, with prop_ : IsProp(U1, P), PropResizing(P, prop_) gives a proposition Q : U0 and maps both ways between P and Q. It computes nothing, and it is listed as PropResizing with every result that uses it. Excluded middle implies it: the library’s h1_classical proves resize_prop(P, prop_) : PropResize(P), deciding P and answering Unit or Void, with LEM alone. The first library’s results that relied on its truncation’s resizing, such as the Bourbaki–Witt theorem, Zorn’s lemma and the basis theorem, use PropResizing.
Extensionality and univalence compute
Function extensionality and univalence are not assumptions. In cubical type theory both are constructions, and the checker builds them from the kernel’s own rules:
FunExt(U, A, B, f, g, pointwise)- For
B : A -> U, dependent functionsfandg, andpointwise : forall x : A. f(x) = g(x), the pathf = g. It builds the same term asext, which is usually shorter. ua(U, A, B, equivalence)- A path
A = Bfrom an equivalenceequivalence : Equiv(U, A, B), defined byimport paths_;. An equivalence is a function with an inverse, two homotopies and the triangle law; a pair of maps is not enough. UnivalenceBeta(U, A, B, equivalence, x)- Transport of
x : Aalongua(U, A, B, equivalence)equals the image ofxunder the equivalence.
All three need every argument; there is no separate univalence axiom. Because they use no assumption, results built on them can be marked computable, and transport along ua computes:
import paths_;
use unat;
def swap(p : Unit and UNat) := unpack p as (u, n) return UNat and Unit { typed(UNat and Unit, (n, u)); };
def swap_back(p : UNat and Unit) := unpack p as (n, u) return Unit and UNat { typed(Unit and UNat, (u, n)); };
computable def swap_equivalence : Equiv(U0, Unit and UNat, UNat and Unit) {
exact (swap, swap_back, fun (p : Unit and UNat) => refl(p), fun (q : UNat and Unit) => refl(q),
fun (p : Unit and UNat) => refl(refl(swap(p))));
}
computable def swapped : (Unit and UNat) = (UNat and Unit) {
exact ua(U0, Unit and UNat, UNat and Unit, swap_equivalence);
}
evaluate transport typed(Unit and UNat, (tt, 3)) along swapped in (fun (T : U0) => T)
expecting typed(UNat and Unit, (3, tt));
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);
}
One definition for every universe
Like the assumptions, ua, UnivalenceBeta and FunExt are each one definition, used at any universe below UU0 through their first argument, as a universe variable would be:
import paths_;
def small_path(A, B : U0, e : Equiv(U0, A, B)) : A = B := ua(U0, A, B, e);
def large_path(A, B : U1, e : Equiv(U1, A, B)) : A = B := ua(U1, A, B, e);
ua takes its four arguments and no more: the path it gives is no function to apply further.
import paths_;
// Error: Too many arguments to ua.
def extra_argument(A, B : U0, e : Equiv(U0, A, B), a : A) := ua(U0, A, B, e, a);
Equiv(U, A, B), like IsProp and IsSet, is a library definition, not a new sort or a keyword. hlevels defines the levels, IsProp(U, A) and IsSet(U, A), for a type in any universe below UU0, as Choice above uses them (propositions and sets).
In the library: univalence and propositional extensionality
The library proves univalence in Cubist, from Glue types (Glue types), for the equivalences of contractible_maps: a function whose fibers are all contractible, ContrEquiv(U, A, B). inverse_equiv makes one from a function with an inverse and both inverse laws. univalence's glue_path(U, A, B, e) is the path A = B an equivalence glues, and idtoequiv the equivalence a path gives; they are inverse, so univalence(U, A, B) is an equivalence between A = B and ContrEquiv(U, A, B).
propositions takes it to the propositions of a universe, Prop(U), a type one universe up: propositions that imply each other are equal (prop_ext), and equal as propositions (prop_path), and the propositions form a set (prop_type_is_set). The effectiveness of quotients rests on it. None of it uses an assumption, and transport along prop_ext is the map it was given:
import propositions;
computable def unit_to_unit_is_prop : IsProp(U0, Unit -> Unit) :=
pi_is_prop(U0, Unit, fun (u : Unit) => Unit, fun (u : Unit) => unit_is_prop);
computable def units : Unit = (Unit -> Unit) := prop_ext(
U0, Unit, Unit -> Unit, unit_is_prop, unit_to_unit_is_prop, fun (u : Unit) => fun (v : Unit) => v,
fun (f : Unit -> Unit) => tt
);
evaluate comp(fun (i : Interval) => units @ i, tt)(tt) expecting tt;
computable def props_form_a_set : IsSet(U1, Prop(U0)) := prop_type_is_set(U0);
Computability
A term that uses an assumption can stop computing. LEM(U0, A, doubleNegation) has type Trunc(U0, A), but it is not built from any element of A, so nothing can be computed from it. A term that uses no assumption is built from the kernel’s own rules only. The kernel is designed so that such a closed term reduces to a canonical value: a closed UNat reduces to a numeral. The test suite checks this on closed examples. The language lets a declaration require it, and lets a file test what a term computes to.
computable def
Writing computable before def requires the declaration to use no assumption. The checker collects the assumptions of the checked term, of its type and of every definition they mention; this is the same list that the inspector shows. If the list is not empty, the declaration is rejected. The error names every assumption, and one chain of definitions through which the first one enters. A rejected declaration is not added, so the declarations that use it are blocked too.
import unat;
use unat;
computable def double(n : UNat) := n + n;
computable def double_two : double(2) = 4 {
rfl;
}
A computable declaration may take parameters, like double. The requirement is about assumptions, not about closed terms: every application of double to a numeral computes. The library’s double_negation is proved with excluded middle, so a declaration that uses it cannot be computable:
import h1_classical;
computable def recover(P : U0, prop_ : IsProp(U0, P), nn : (P -> Void) -> Void) : P {
// Error: This computable declaration depends on non-computing assumptions: LEM.
// Path to LEM: double_negation (h1_classical) → LEM.
exact double_negation(U0, P, prop_, nn);
}
The error lists every assumption the proof uses, and the chain of definitions through which the first one enters: here the library’s double_negation. When the assumption is used directly, the chain is just its name:
import classical_axioms;
computable def lem_directly(A : U0, nn : (A -> Void) -> Void) : Trunc(U0, A) {
// Error: This computable declaration depends on non-computing assumptions: LEM.
// Path to LEM: LEM.
exact LEM(U0, A, nn);
}
Without the modifier, the same proofs are accepted and their assumptions are listed as usual. The modifier changes nothing else: a computable declaration is checked and unfolded like any other.
evaluate
evaluate term expecting value; is a top-level directive, placed between declarations. It checks both terms and requires term to use no assumption. It requires the two to have the same type, then compares their normal forms. It defines no name. A success is reported with the normal form. A failure is an error that makes the module incomplete, so every evaluation is rechecked with the rest of its module.
import unat;
use unat;
def double(n : UNat) := n + n;
evaluate double(3) expecting 6;
evaluate double(double(1)) expecting 2 + 2;
import unat;
use unat;
def double(n : UNat) := n + n;
evaluate double(3) expecting 7; // Error: The term evaluates to 6, not 7.
import classical_axioms;
// Error: The evaluated term depends on non-computing assumptions: LEM. Path to LEM: LEM.
evaluate LEM(U0, Unit, fun (k : Unit -> Void) => k(tt)) expecting merely(U0, Unit, tt);
The expected side is normalized too, so it may be any term of the same type. Writing a literal makes the directive state what the term computes to.
An expected value with a hole _ or a demand mark is a pattern, matched part by part, and each part of the term is computed only as far as the pattern observes it: a hole matches anything and computes nothing; a pair, left(p), right(p) or a constructor of the part's type applied to patterns computes the part's weak head and matches a value built so; and any other expression is elaborated at the part's type and compared with the part by their normal forms, in which a stuck definition stays named, by conversion. A part is read at its type, the field's type where it is a constructor's argument. A mismatch names the part that differs and shows the value as far as it was computed, with <unevaluated> for a part nothing computed. A hole stands only where such a part can be read, not inside another function's arguments.
import lists;
use unat;
def numbers : List(U0, UNat) := cons(1, cons(2, cons(3, nil)));
def tagged : List(U0, UNat) and (Unit or UNat) := (numbers, right(2 + 2));
evaluate numbers expecting cons(1, _);
evaluate tagged expecting (cons(_, cons(2, _)), right(4));
import lists;
use unat;
def numbers : List(U0, UNat) := cons(1, cons(2, cons(3, nil)));
evaluate numbers expecting cons(_, nil); // Error: The term evaluates to cons(<unevaluated>, cons(<unevaluated>, <unevaluated>)), which does not match cons(_, nil): cons(<unevaluated>, <unevaluated>) is not nil.
Three demand marks ask for more than a pattern observes, by analogy with Haskell's $! and $!!. !p computes the part's weak head, its outermost constructor, pair, injection, function or type, before matching p. !!p computes its normal form, in which data computes in full and a definition whose value is no data, such as a lemma applied to a variable under a proof's binder, stays as written, with its arguments normalized. !!!p computes its full normal form, which unfolds every definition. A mark applies to the whole part after it, and marks apart, ! !p, are refused, so that a space never weakens a mark. !_ thus checks that a part has a weak head without computing inside it, !!_ that it has a normal form, and !!!_ that it has a full normal form. Written right after evaluate, as in evaluate !!e expecting p;, a mark applies to the whole pattern. A bare evaluate e expecting _; would compute nothing, and is refused.
import unat;
use unat;
// 2 * 256 is a unary numeral too deep to build, but a pattern that does
// not observe it does not compute it.
def far : UNat and UNat := (1, 2 * 256);
evaluate far expecting (1, _);
evaluate far expecting (_, succ(_));
evaluate far expecting (_, !_);
import unat;
use unat;
def far : UNat and UNat := (1, 2 * 256);
evaluate far expecting !!_; // Error: Native prototype syntax depth exceeds 512.
import unat;
use unat;
def three : UNat := 3;
evaluate three expecting _; // Error: evaluate e expecting _; would compute nothing: write !_ to compute the value's weak head, !!_ for its normal form, or !!!_ for its full normal form.
A weak head is the kernel's weak-head normal form, which contracts a function by η: the weak head of fun (n : UNat) => succ(n) is the constructor succ, and that of fun (n : UNat) => n + n is the function itself. ! therefore says nothing about a proof that is a function, such as a certificate that a number is nonzero: its weak head is that function. !! computes the certificate's body as far as its own definitions are not stuck, and names those that are; only !!! unfolds them all.
> import rationals;
Imported rationals.
> use nat;
Selected nat.
> evaluate !!rat(int(2, 0), 2);
class((class((2, 0)), class((3, 0)), rat_succ_nonzero(2)))
The rational's data, two integers, is computed, and its certificate that the denominator is not zero is named. Under !!! that certificate unfolds into a normal form of more than 90,000 nodes.
Each computation a pattern asks for runs under the evaluation's step budget and time limit, and one that runs out, or builds syntax deeper than the kernel allows, fails the evaluation as it would anywhere, at the part of the pattern that asked for it. A part no pattern observes asks nothing, so it cannot fail. A mark that asks for nothing more is a warning: a mark under !! or !!! that asks for no more than it, and, where a hole keeps the expected value a pattern without the mark, ! before a pair, an injection, a constructor or an expression, which compute at least their part's weak head, and !! before an expression, which is compared by its normal form. A !!! inside a !! part asks for what that part's normal form does not hold, and is refused. A mark that alone makes the expected value a pattern is not reported: without it, the value would be compared whole instead.
import unat;
use unat;
def pairs : UNat and UNat := (3, 4);
evaluate pairs expecting !(3, _); // Warning: The ! before (3, _) asks for nothing more: a pair, an injection, a constructor or an expression computes its part's weak head itself.
evaluate pairs expecting (!!3, _); // Warning: The !! before 3 asks for nothing more: an expression is compared by its normal form.
evaluate pairs expecting !!(3, !_); // Warning: The ! before _ asks for nothing more: it is under !!, which normalizes its part.
import unat;
use unat;
def pairs : UNat and UNat := (3, 4);
evaluate pairs expecting !!(3, !!!_); // Error: A !!! inside a !! part asks for a full normal form, which the !! part's normal form does not hold: write !!! on the outer part.
A normal form, of an expression or under !!, unfolds the term asked for to its weak head, and inside it unfolds a definition only where its value is data, so a proof stays named where it is stuck: evaluate !!identity; shows the function, a fun, and where both is defined as (identity, tt), evaluate !!both; shows (identity, tt). It is compared with another by conversion; a full normal form, under !!!, unfolds every definition (normal form). Neither reads with unfolding hints.
evaluate nonempty P by proof; instead checks that the supplied evidence inhabits P and that neither the evidence nor its type depends on assumptions. The counterpart evaluate empty P by proof; checks evidence of P -> Void, under the same rules. Neither form searches for a proof or fully normalizes its body. This is useful for disequalities, whose proofs are functions into Void: different proofs need not have identical normal forms.
evaluate nonempty Unit by tt;
evaluate nonempty (Void -> Void) by fun (x : Void) => x;
evaluate nonempty (Void -> Void) by fun (x : Void) => absurd(x);
evaluate empty Void by fun (x : Void) => x;
Success is reported as nonempty P or empty P. The directive defines no name, and incorrect evidence makes the module incomplete. computable, evaluate, expecting, nonempty and empty are reserved keywords.
Without expecting, print(evaluate(term)); and the REPL's evaluate term; show the term's value form: its data computed and shown, and a marker such as <fun> where a function, a path or a type stops it. The runtime evaluator computes it where it can, and the kernel's queries otherwise; neither certifies it (printing). !, !! and !!! written before the term show its weak head, its normal form and its full normal form.
The command-line checker prints each success as evaluate at line N: value, the value as far as the directive computed it. After check, its evaluate EXPRESSION command shows an expression in the scope of the checked module, under the same rule and as the REPL does: its value form, or with !! before the expression its normal form, and with !!! its full normal form. inspect NAME lists the declaration’s assumptions, or none. See checking and inspection.