Cubist

LANGUAGE REFERENCE · CHAPTER 10

Theories and models

Theories of algebraic structures: carriers, operations with notation and laws, their models, extension and use.

Declaring a theory

A theory describes a kind of structure: the types it has, its operations and the laws they satisfy. A monoid, for instance, has one type, an associative multiplication and a unit:

import hlevels;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  law mul_assoc(x, y, z : M) : (x * y) * z = x * (y * z);
  one : M;
  law one_mul(x : M) : one * x = x;
  law mul_one(x : M) : x * one = x;
}

The header, theory Monoid(U < UU0), names the universe of the structure's types, so that a field can mention it. A theory's body lists its fields, in order:

  • a carrier, M : set U; or P : prop U;, is a type of the structure, a set or a proposition. Its evidence of being one is a field too, M_is_set : IsSet(U, M) or P_is_prop : IsProp(U, P), so a module that declares carriers imports hlevels. A carrier M : U; has no h-level: its equations are not propositions, so no law can state one, and its models have no homomorphisms;
  • an operation, mul(x, y : M) : M, or a constant, one : M, may have a notation: one of the operators x + y, x * y, x < y and x <= y, written with the operation's two arguments in order;
  • a law, law name(binders) : statement;, states a property of the earlier fields. A law must be a proposition: an equation between elements of a carrier that is a set or a proposition, Void, or forall, -> and and over those, such as zero = one -> Void. A law holds no data, so law point : M; is refused: declare it as a constant.

Each field is in scope by its name after it is declared, and inside the theory a notation means its operation: x * y there is mul(x, y). The words law, notation, set and prop are reserved keywords: they cannot name fields or binders.

Models

A model of a theory is a structure of its kind: a value for each field. Its type is the theory's name, Monoid(U), for models whose carriers are in the universe U, and Monoid.make builds one, field by field. The natural numbers with addition are a monoid:

import unat;
import hlevels;
use unat;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  law mul_assoc(x, y, z : M) : (x * y) * z = x * (y * z);
  one : M;
  law one_mul(x : M) : one * x = x;
  law mul_one(x : M) : x * one = x;
}

def additive_ : Monoid(U0) := Monoid.make(
  M := UNat, M_is_set := unat_is_set, mul := add, mul_assoc := unat_add_assoc, one := 0,
  one_mul := unat_zero_add, mul_one := unat_add_zero
);

def two_plus_three : additive_.mul(2, 3) = 5 {
  rfl;
}

A carrier's setness field can be left out where hlevel proves it, as for UNat, a type built from sets, or a type with a registered hlevel_rule: Monoid.make(M := UNat, mul := add, …) gives M_is_set the evidence it finds.

For a model m, m.f is its field f: additive_.M is UNat and additive_.mul(2, 3) computes to 5. A field's type is written through the earlier fields of the same model, so m.one_mul has type forall x : m.M. m.mul(m.one, x) = x, and goals and messages show fields this way. m.f is the projection Monoid.f(m), a definition like any other. A binding of m hides the declarations named m.…: in def f(Monoid : Monoid(U0)), Monoid.one is the parameter's field, and beside a theory B, a model bound as B reads its own B.one.

A parameter whose type is a theory's models makes a statement about every structure of that kind, in a universe of your choice:

import hlevels;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  one : M;
  law one_mul(x : M) : one * x = x;
}

def one_one(U < UU0, G : Monoid(U)) : G.mul(G.one, G.one) = G.one {
  exact G.one_mul(G.one);
}

Families and relations

A carrier may have indices: a family, one type for each index. F(A : set U) : set U is a set for each set A, as a monad on sets has. An index (A : set U) holds A and its evidence A_is_set : IsSet(U, A); inside the theory, F(A) passes that evidence along, and outside it is written, as in m.F(UNat, unat_is_set). An equation between members of a family of sets is a proposition, so the monad laws are laws, and the identity monad is a model:

import unat;
import hlevels;
use unat;

theory Monad(U < UU0) {
  F(A : set U) : set U;
  pure(A : set U, a : A) : F(A);
  bind(A, B : set U, m : F(A), k : A -> F(B)) : F(B);
  law left_unit(A, B : set U, a : A, k : A -> F(B)) : bind(A, B, pure(A, a), k) = k(a);
  law right_unit(A : set U, m : F(A)) : bind(A, A, m, fun (a : A) => pure(A, a)) = m;
}

def identity : Monad(U0) := Monad.make(
  F := fun (A : U0, h : IsSet(U0, A)) => A,
  F_is_set := fun (A : U0, h : IsSet(U0, A)) => h,
  pure := fun (A : U0, h : IsSet(U0, A), a : A) => a,
  bind := fun (A : U0, h : IsSet(U0, A), B : U0, k : IsSet(U0, B), m : A, f : A -> B) => f(m),
  left_unit := fun (A : U0, h : IsSet(U0, A), B : U0, k : IsSet(U0, B), a : A, f : A -> B) => refl(f(a)),
  right_unit := fun (A : U0, h : IsSet(U0, A), m : A) => refl(m)
);

def three : identity.bind(UNat, unat_is_set, UNat, unat_is_set, identity.pure(UNat, unat_is_set, 2), succ) = 3 {
  rfl;
}

A relation is a family of propositions indexed by carriers, and may have a notation. Its members are propositions, so x <= x is a law. A homomorphism maps a family at each index, pushing an index that is an element of a carrier, so the homomorphisms of preorders are the monotone maps, map_le : A.le(x, y) -> B.le(map(x), map(y)), with nothing to write:

import hlevels;

theory Preorder(U < UU0) {
  M : set U;
  le(x, y : M) : prop U notation x <= y;
  law le_refl(x : M) : x <= x;
  law le_trans(x, y, z : M) : x <= y -> y <= z -> x <= z;
}

def monotone(A, B : Preorder(U0), f : Preorder.Hom(A, B), x, y : A.M, p : A.le(x, y)) :
  B.le(f.map_M(x), f.map_M(y)) := f.map_le(x, y, p);

An isomorphism has round trips on each carrier and on each family of sets at each index; a family of propositions needs none. A family of sets indexed by a carrier, Fiber(x : M) : set U, has homomorphisms but no isomorphisms: its round trip would need a transport along the carrier's.

Selecting a model: use

use m; is a proof statement. For the rest of its block, each field of the model m is in scope by its name, and each notation of its theory means m's operation:

import hlevels;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  one : M;
  law one_mul(x : M) : one * x = x;
}

def square(G : Monoid(U0), x : G.M) : G.M {
  use G;
  exact x * x;
}

def square_one(G : Monoid(U0)) : square(G, G.one) = G.one {
  use G;
  exact one_mul(one);
}

A name that use binds shadows the one it had, as let does, until the block ends, and a later use shadows an earlier one: it switches the selection. At a file's top level, use m; selects m for every definition after it, statements included, until a later use switches it. m.(e) selects m for one expression, and an operator can be qualified by its model, with its usual precedence, a m.(*) b; alone, m.(*) is the operation itself. A parent's operator is reached through its label, x R.additive_.(*) y:

import unat;
import hlevels;
import algebra;
use unat;

def additive_ : Monoid(U0) := nat_additive.monoid;

def multiplicative : Monoid(U0) := nat_multiplicative.monoid;

def mixed : additive_.M := 2 multiplicative.(*) 3 additive_.(*) 1;

def product : multiplicative.(unat.(2) * unat.(3) * unat.(4)) = 24 {
  rfl;
}

def doubled(R : CommRing(U0), x : R.R) : R.R := x R.additive_.(*) x;

use multiplicative;

def squared(x : UNat) : UNat := x * x;

Elsewhere, + and * mean add and mul in scope, as for UNat. An operator means one thing in a scope, chosen by use or a qualifier, never by the types of its operands. open m;, the earlier spelling of use m;, is refused with a message naming it.

Named notations

notation v { x + y := add(x, y); … } declares a named notation: a rule for each operator it binds, written as the notation is used. A rule's right side is read where the notation is declared, so a later binding of add changes nothing. use v;, v.(e) and a v.(+) b select it as they select a model. The library's unat module declares unat, whose +, *, < and <= are add, mul, isLt and le:

import unat;
use unat;

notation times {
  x + y := mul(x, y);
  numeral(n : UNat) := n;
}

def fourteen : unat.(2 + 3 * 4) = 14 {
  rfl;
}

def twelve : times.(3 + 4) = 12 {
  rfl;
}

A selection is complete: an operator the selected notation or model does not bind is an error, never an outer selection's or a function named add in scope. A selection inside another wins for its expression, so multiplicative.(x * unat.(x + 1)) reads the inner + as the naturals'. Outside any selection, +, *, < and <= still mean add, mul, isLt and le in scope, until the name-based reading is retired.

A notation binds +, -, *, /, ^, <, <= and unary -x; x > y is y < x and x >= y is y <= x, so no notation declares them. From loosest: + -, then * /, then unary -, then right-associative ^, so -x^2 is -(x^2); the cubical @, ~, & and | bind tighter still. An operand that is no carrier's element names the notation it is read in, x ^ unat.(n), so x ^ (n + 1) adds in unat. A theory may define an operation over its fields, def sub(x, y : R) : R := x + -y notation x - y;, which every model has without giving it, and which homomorphisms ignore:

import unat;
import hlevels;
use unat;

theory Ring(U < UU0) {
  R : set U;
  add(x, y : R) : R notation x + y;
  neg(x : R) : R notation -x;
  mul(x, y : R) : R notation x * y;
  pow(x : R, n : UNat) : R notation x ^ unat.(n);
  def sub(x, y : R) : R := x + -y notation x - y;
  law pow_succ(x : R, n : UNat) : x ^ (n + 1) = x * x ^ n;
}

def grouped(A : Ring(U0), x, y : A.R) : A.(-x^2 * y) = A.mul(A.neg(A.pow(x, 2)), y) {
  rfl;
}

def subtracted(A : Ring(U0), x, y : A.R) : A.(x - y) = A.sub(x, y) {
  rfl;
}

Literals are read by the selected notation. A plain numeral goes to its numeral(n : UNat) := e rule, and any numeric token, 1/2, 2.3, 1_000 or 5i, to its literal(s : Lexeme) := e rule, a parser over the token's characters from the library's lexemes module, which also reads plain numerals when present; a notation with neither reads none, and unat.(2) gives a natural number inside it. A theory's derived operation marked notation numeral reads numerals in its models, as the library's rings' of_nat does. Its natural number is unary, UNat, or binary, BNat; a binary one is built from the numeral's bits, so of_nat reads a large numeral by doubling without a unary natural number. A numeral rule declared over BNat, numeral(n : BNat) := e, reads the bits too, as the import-free bnat module's bnat_numerals does. A generic numeral prints as A.(2), or bare where that model's notation is selected, only where the text reads back as the same term: where the model's module added a rule of its own, or a named notation takes the model's name, it prints as the call. The module that declares a model may add a numeral or a literal rule to its notation, as notation rationals { literal(s : Lexeme) := rat_literal(s); } does. A literal's parser is evaluated as the source is checked, and a refusal names the character, as for rationals.(1/0); the term holds the literal's characters and the evidence that its parse succeeded, which the kernel checks by evaluating the parse:

import rationals;
use nat;

def half : Q := rationals.(1/2);

def three_halves : Q := rationals.(1/2 + 1);

def two : integers.(2) = int(2, 0) {
  rfl;
}

Sections

A section gives a group of definitions the same first parameters. Each parameter that is a model is opened for each definition's statement and proof, and inside the section a definition of the section is already applied to the section's parameters:

import unat;
import hlevels;
use unat;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  one : M;
  law one_mul(x : M) : one * x = x;
}

section {{U < UU0}}(G : Monoid(U)) {
  def square(x : M) : M := x * x;

  def square_one : square(one) = one {
    exact one_mul(one);
  }
}

def additive_ : Monoid(U0) := Monoid.make(
  M := UNat, M_is_set := unat_is_set, mul := add, one := 0, one_mul := unat_zero_add
);

def four : square(additive_, 2) = 4 {
  rfl;
}

Inside the section, square(one) is square{{U}}(G, G.one); outside, square takes G first, and U in braces, and square_one states forall U < UU0. forall G : Monoid(U). square{{U}}(G, G.one) = G.one. A recursive call passes the section's parameters unchanged too: in a section over G, power(x, k) inside power's own definition is power{{U}}(G, x, k). A section's parameters, in braces or not, come before each definition's own, so a definition in a section has no implicit parameters of its own, and no parameter of a section's name. A section holds definitions only, and sections do not nest.

Extension: extends

A theory can extend others. It has its parents' fields, in order, and then its own:

import hlevels;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  one : M;
  law one_mul(x : M) : one * x = x;
}

theory Group(U < UU0) extends Monoid {
  inv(x : M) : M;
  law inv_mul(x : M) : inv(x) * x = one;
}

theory CommMonoid(U < UU0) extends Monoid {
  law mul_comm(x, y : M) : x * y = y * x;
}

theory CommGroup(U < UU0) extends Group, CommMonoid {}

def forget(G : CommGroup(U0)) : Monoid(U0) := G.group.monoid;

def same(G : CommGroup(U0), x, y : G.M) : G.group.monoid.mul(x, y) = G.mul(x, y) {
  rfl;
}

A theory may extend several parents. An ancestor that two parents reach, as Monoid through Group and CommMonoid above, contributes its fields once, when it arrives with the same fields under the same names. A model of a theory has a model of each parent, by the parent's label: G.group, and then G.group.monoid. An unlabelled parent's label is its name in snake case: comm_monoid for CommMonoid. Each computes to the model built from the child's fields.

A child can implement an inherited operation or law with a def of the same name and parameter/result types. The constructor then takes only the remaining fields. The parents receive the checked definition, so their laws still apply. For example, one step operation supplies a parent's double step:

import unat;
import hlevels;
use unat;

theory Unary(U < UU0) {
  M : set U;
  op(x : M) : M;
  law self(x : M) : op(x) = op(x);
}

theory Twice(U < UU0) extends Unary {
  step(x : M) : M;
  def op(x : M) : M := step(step(x));
  def self(x : M) : op(x) = op(x) := refl(op(x));
}

def twice_nat : Twice(U0) := Twice.make(M := UNat, M_is_set := unat_is_set, step := succ);

def inherited(n : UNat) : twice_nat.unary.op(n) = succ(succ(n)) {
  rfl;
}

Implementations may use earlier fields of the child; remaining constructor fields are ordered by their dependencies. They cannot replace carriers, change an inherited signature, or form recursive cycles. When two inheritance paths reach one member, a definition also satisfies the abstract path; conflicting definitions are refused. Derived members can be renamed in extends. Homomorphisms still require preservation of implemented parent operations, so every parent homomorphism remains available; implemented laws need no extra evidence. The equational initial/free strategy currently refuses these theories because folds for implemented members are not generated (E881).

A parent can be labelled and its fields renamed, with a new notation for an operation. A semiring has two monoids on one carrier, the additive one written with +:

import hlevels;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  one : M;
  law one_mul(x : M) : one * x = x;
}

theory Semiring(U < UU0) extends
    additive_ : Monoid(M := R, mul := add notation x + y, one := zero, one_mul := zero_add),
    multiplicative : Monoid(M := R) {
  law mul_add(x, y, z : R) : x * (y + z) = x * y + x * z;
}

def twice_plus(R : Semiring(U0), x : R.R) : R.R {
  use R;
  exact x * x + x;
}

Renaming a carrier to one name in two parents, as M := R twice above, makes it one carrier of the child; its evidence follows it, as R_is_set. An ancestor that arrives renamed is another copy: here each monoid has its own unit, zero and one, and its own law.

Two independent theories, written without knowing of each other, combine without changing either. A carrier both give under one name, with one kind and type, is one carrier of the child. Any other field of one name from both, or an operator both bind, stays each parent's: the name is ambiguous in the child and refused where it is used, with the qualified forms in the message, and each is reached through its parent's label, G.magma.mul or, inside the theory, magma.mul. A homomorphism's fields name them by label too, map_left_point. Renaming one in extends gives it a name or a notation of its own:

import unat;
import hlevels;

theory Magma(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
}

theory Action(U < UU0) {
  M : set U;
  act(x, y : M) : M notation x * y;
  law act_idem(x : M) : x * x = x;
}

theory Both(U < UU0) extends Magma, Action {
  law mixed(x : M) : magma.mul(x, x) = action.act(x, x);
}

theory Renamed(U < UU0) extends Magma, Action(act := act notation x + y) {
  law both(x : M) : x * x = x + x;
}

def first_of(G : Both(U0), x, y : G.M) : G.M := G.magma.mul(x, y);

Carriers of one name and different kinds, a set in one parent and a proposition in the other, are refused; so is a name that is a carrier in one parent and another field in the other.

Homomorphisms and isomorphisms

A homomorphism between two models of a theory, Monoid.Hom(A, B), is a map of their carrier, map : A.M -> B.M, with, for each operation and constant, a proof that the map preserves it: map_mul and map_one. With several sorts there is a map for each, map_M, map_N. Laws need no field: they are propositions about sets. Monoid.Hom.make builds one, and f.map and the rest read it:

import unat;
import hlevels;
use unat;

theory Monoid(U < UU0) {
  M : set U;
  mul(x, y : M) : M notation x * y;
  one : M;
  law one_mul(x : M) : one * x = x;
}

def additive_ : Monoid(U0) := Monoid.make(
  M := UNat, M_is_set := unat_is_set, mul := add, one := 0, one_mul := unat_zero_add
);

def trivial : Monoid(U0) := Monoid.make(
  M := Unit, M_is_set := prop_is_set(U0, Unit, unit_is_prop), mul := fun (x, y : Unit) => tt,
  one := tt, one_mul := fun (x : Unit) => unit_is_prop(tt, x)
);

def collapse : Monoid.Hom(additive_, trivial) := Monoid.Hom.make(
  additive_, trivial, map := fun (n : UNat) => tt, map_mul := fun (x, y : UNat) => refl(tt), map_one := refl(tt)
);

def unit_into(B : Monoid(U0)) : Monoid.Hom(trivial, B) := Monoid.Hom.make(
  trivial, B, map := fun (x : Unit) => B.one, map_mul := fun (x, y : Unit) => sym(B.one_mul(B.one)),
  map_one := refl(B.one)
);

def round : Monoid.Hom(additive_, additive_) := Monoid.Hom.compose(unit_into(additive_), collapse);

evaluate round.map(7) expecting 0;

Monoid.Hom.id(A) is the identity and Monoid.Hom.compose(g, f) is g after f; on closed models both compute. A child theory's homomorphisms preserve its parents' operations too, and f.monoid is the homomorphism of the parent's models.

An isomorphism, Monoid.Iso(A, B), is a homomorphism each way, to and from, with the round trips on each carrier: from_to : forall x : A.M. from.map(to.map(x)) = x and to_from. Monoid.Iso.id(A), Monoid.Iso.compose(g, f) and Monoid.Iso.inverse(f) are isomorphisms too. A field of a value that is not a name is read the same way: Monoid.Iso.inverse(f).to.map(x).

An operation's arguments need not be carriers. A homomorphism's preservation field relates the arguments in A to those in B by where the carriers sit in each argument's type. An argument with no carrier, as n : UNat or a parameter's element, is the same value on both sides. A covariant argument, with carriers right of every arrow, as s : UNat -> M, is pushed forward along the maps. A contravariant one, with carriers left of an arrow, as k : X -> UNat, is pulled back: B's function composed with the map. A result is pushed forward. For a measure, preservation says that the map preserves the integral:

import unat;
import hlevels;

theory Measure(U < UU0) {
  X : set U;
  integrate(k : X -> UNat) : UNat;
}

def preserves(A, B : Measure(U0), f : Measure.Hom(A, B), k : B.X -> UNat) :
  A.integrate(fun (x : A.X) => k(f.map(x))) = B.integrate(k) := f.map_integrate(k);

Pushing and pulling follow the arrows and pairs of the type, so along a composite they are the two maps in turn, and T.Hom.id and T.Hom.compose are generated for every such theory. An argument that mentions a carrier on both sides of an arrow, as g : M -> M, could only be related by a hypothesis, and such homomorphisms need not compose, so the theory has none. A carrier with no h-level leaves a theory without homomorphisms too:

import unat;
import hlevels;

theory Iterate(U < UU0) {
  M : set U;
  iterate(g : M -> M, x : M) : M;
}

def no_homs(A, B : Iterate(U0)) := Iterate.Hom(A, B);  // Error: Iterate's models have no homomorphisms: its iterate's argument g mentions a carrier on both sides of an arrow, and such homomorphisms need not compose.

Initial and free models: construction prototype

This is the retained construction-and-fold prototype for L2.6's second slice. It registers no initial or free capability. The planned interface requires the theory to request deriving (morphisms, initial) or deriving (morphisms, free); that opt-in, uniqueness and the universal-property proofs are not implemented yet. The prototype declarations below remain available as checked construction evidence.

initial N : T(…); builds a declared type N with a constructor for each operation, such as N.mul and N.one, a path constructor for each equational law, and the squash of the carrier's level. It also defines N.model : T(…), the recursion N.fold_map, and N.fold(M) : T.Hom(N.model, M), whose map computes on constructors. free W(A : U0) : T(…) on A; adds W.gen(a), and its fold takes the generators' images, W.fold(A, M, g). Explicit universe parameters are supported, as in free W(V < UU0, A : V) : Monoid(V) on A;; implicit parameters are not.

The equational strategy currently supports one carrier that is a set or a proposition, named operation arguments that are either the carrier or types independent of it, carrier-valued operations, and equational laws. Arguments must also be independent of the theory's law proofs and carrier evidence; law equations cannot refer to those proofs. Universe arguments belong in the theory's header, not in its operations or laws. A generator type must be independent of the newly declared model, and the model's name must not hide a declaration its expansion uses. Generated interface names such as model, fold, fold_map, squash and gen are reserved by the language at every naming site.

import unat;
import hlevels;
import algebra;
use unat;

free W(A : U0) : Monoid(U0) on A;

// A word's length: each generator is 1 in UNat's additive monoid.
def length{{A : U0}}(w : W(A)) : UNat := W.fold(A, nat_additive.monoid, fun (a : A) => 1).map(w);

// Output: 3
print(evaluate(length{{Unit}}(W.mul(W.gen(tt), W.mul(W.gen(tt), W.gen(tt))))));

def unit_left{{A : U0}}(x : W(A)) : W.mul(W.one, x) = x := W.one_mul(x);

The library's Group, AbelianGroup, Ring, CommRing and their extensions currently refuse initial/free with E881: their inherited division implementations need fold preservation proofs that the strategy does not yet generate. This temporarily removes support for earlier group and commutative-ring presentations. The monoid examples above remain supported.

The strategy refuses Field first because it inherits the additive group's implemented divisions and division laws, whose fold proofs are not generated yet (E881). It also has laws outside the equational fragment. This is a limitation of the strategy, not a proof that an initial model does not exist. Untruncated carriers are also unsupported; the circle remains an ordinary inductive declaration.

The generator type must fit the carrier's universe. E870 marks the expression after on when it does not: choose a larger carrier universe or a smaller generator type.

import hlevels;
import algebra;

free FG(A : U0) : Group(U0) on A;  // Error: The equational strategy does not yet generate folds for Group's implemented inherited members.
initial F : Field(U0);  // Error: The equational strategy does not yet generate folds for Field's implemented inherited members.

// A truncated law also fails without any implemented members.
theory Inhabited(U < UU0) {
  M : set U;
  law inhabited : Trunc(U, M);
}
initial I : Inhabited(U0);  // Error: The law inhabited is not an equation between operation terms: the equational strategy does not support this law.

The library's algebra

import algebra; declares the usual hierarchy as theories, each on one set, with its models, homomorphisms and isomorphisms:

TheoryExtendsAdds
MagmaM : set U, mul written x * y
UnitalMagmaMagmaone, one_mul, mul_one
SemigroupMagmamul_assoc
QuasigroupMagmaleft_div and right_div, with both cancellation laws for each
LoopQuasigroup, UnitalMagmaNothing: division and a unit on the shared magma
AssociativeQuasigroupQuasigroup, SemigroupNothing: division and associativity on the shared magma
MonoidSemigroup, UnitalMagmaNothing: associativity and a unit on the shared magma
CommMonoidMonoidmul_comm
GroupMonoid, Loop, AssociativeQuasigroupinv, inv_mul, mul_inv; implements both divisions and their laws
AbelianGroupGroup, CommMonoidNothing: the two parents share their monoid
Ringadditive_ : AbelianGroup, renamed for addition on R; multiplicative : Monoid on the same carriermul_add and distrib_right, the two distributive laws; derived subtraction and natural numerals
CommRingRing and multiplicative : CommMonoid, with the shared additive group also accessible as additive_Commutativity of multiplication; implements right distributivity from it and mul_add
FieldCommRinginverses, Trunc(U, exists y : R. x * y = one) for x other than zero, and zero_ne_one: laws, so being a field is a property of a ring, and a field's homomorphisms are its ring's

Group.make takes one inverse operation and its left and right inverse laws. Checked definitions implement left_div(x, y) = inv(x) * y, right_div(x, y) = x * inv(y), and all four division laws. Models supply no separate division operations or proofs. Every path through the lattice shares these definitions, the multiplication and the unit. group_from_associative_loop constructs a group from a loop and associativity; inv_as_left_div and inv_as_right_div identify its inverse with division of the unit.

The additive ring fields are add, add_assoc, zero, zero_add, add_zero, neg, neg_add, add_neg and add_comm. Inherited add_left_div(x, y) computes to -x + y, and add_right_div(x, y) to x + -y, also named sub(x, y). Their equations are add_neg_cancel_left, neg_add_cancel_left, neg_add_cancel_right and add_neg_cancel_right. The division operations and equations are derived, so model constructors do not request them. Homomorphism constructors still request preservation proofs: map_left_div and map_right_div for groups, and map_add_left_div and map_add_right_div for rings. This slice does not automatically derive these proofs from multiplication and inverse preservation.

ordered_algebra adds OrderedRing over Ring, OrderedCommRing over both OrderedRing and CommRing, and OrderedField over OrderedCommRing. Their proposition-valued strict order is cotransitive and tight, preserves addition and positive products, and reflects a positive product to each factor being apart from zero. Non-strict order negates the reverse strict inequality. These interfaces assume neither decidable trichotomy nor completeness. OrderedField.inverses requires apartness from zero, Trunc(U, (zero < x) or (x < zero)); ordered_inv extracts the unique inverse and ordered_mul_inv proves its product law. Mere inequality with zero need not supply apartness constructively, so this interface does not inherit Field's stronger inverse law. OrderedCommRing derives right-factor apartness from the left-factor law by commutativity.

A field's inverse is partial: inv(F, x, nonzero) takes evidence that x is not zero, with mul_inv(F, x, nonzero) : x * inv(F, x, nonzero) = one. It is derived by unique choice: in a commutative ring an element has at most one inverse (inverse_unique), so having one is a proposition (inverse_is_prop), into which the truncated law eliminates. A model that supplies the law as merely of an inverse, as the rationals do, computes its inverse. The module's sections prove general lemmas, which take a model first:

  • in any quasigroup, quasigroup_left_cancel and quasigroup_right_cancel;
  • in any commutative monoid, mul_left_comm, mul_right_comm and mul_interchange, (w * x) * (y * z) = (w * y) * (x * z);
  • in any group, left_cancel, right_cancel, inv_unique, inv_inv and inv_one;
  • in any commutative ring, mul_zero, zero_mul, add_mul and neg_mul, neg(x) * y = neg(x * y), and inverse_unique and inverse_is_prop;
  • in any field, inverse, inv and mul_inv.

A ring's parts are models too, so a monoid's or a group's lemma applies to them: mul_interchange(A.multiplicative, …), right_cancel(A.additive_.group, …). The natural numbers are a commutative monoid twice, nat_additive and nat_multiplicative. The library's integers are a commutative ring, integers, and its rationals a field, rationals, both quotients over binary natural numbers. fractions builds the field of fractions once, in a section over any commutative ring with decidable equality, no zero divisors and zero not one (fraction_field), and rationals takes it at the integers. rat(a, k) is a / (k + 1), and the field's arithmetic, the inverse included, computes:

import rationals;
use nat;

def equal_or_not(x, y : Q) : Nat := match rat_decide(x, y) return Nat {
  left same => 1;
  right different => 0;
};

// The inverse takes evidence that its argument is not zero; the rationals decide it.
def inverse_or_zero(x : Q) : Q := match rat_decide(x, rationals.zero) return Q {
  left same => rationals.zero;
  right different => inv(rationals, x, different);
};

// 1/2 + 1/3 = 5/6, and -2/3 times its inverse is one.
evaluate equal_or_not(rationals.add(rat(int(1, 0), 1), rat(int(1, 0), 2)), rat(int(5, 0), 5)) expecting 1;
evaluate equal_or_not(rationals.mul(rat(int(0, 2), 2), inverse_or_zero(rat(int(0, 2), 2))), rationals.one) expecting 1;

// A commutative ring's lemma, at the integers and at the rationals' ring.
def int_times_zero(x : Z) : int_mul(x, int_zero) = int_zero := mul_zero(integers, x);
def rat_times_zero(x : Q) : rationals.mul(x, rationals.zero) = rationals.zero := mul_zero(rationals.comm_ring, x);

A homomorphism between the library's models is built field by field, as any other. Powers of two carry the naturals' addition to their multiplication:

import algebra;
use unat;

def two_to(n : UNat) : UNat := match n {
  zero => 1;
  succ(k) => 2 * two_to(k);
};

def two_to_add(x, y : UNat) : two_to(x + y) = two_to(x) * two_to(y) {
  match x {
    zero => {
      exact sym(unat_one_mul(two_to(y)));
    }
    succ(k) => {
      calc {
        2 * two_to(k + y) = 2 * (two_to(k) * two_to(y)) by cong(fun (m : UNat) => 2 * m, two_to_add(k, y));
        _ = (2 * two_to(k)) * two_to(y) by sym(unat_mul_assoc(2, two_to(k), two_to(y)));
      }
    }
  }
}

def powers_of_two : CommMonoid.Hom(nat_additive, nat_multiplicative) := CommMonoid.Hom.make(
  nat_additive, nat_multiplicative, map := two_to, map_mul := two_to_add, map_one := refl(1)
);

evaluate powers_of_two.map(4) expecting 16;

What a theory declares

A theory is checked as ordinary definitions, which it declares in its module, in this order. Each is inspectable by name, uses no assumption, and computes:

DefinitionWhat it is
T(U < UU0) : next(U)The type of models whose carriers are in U: the type of pairs of the fields, in order
T.make{{U < UU0}}(…)The model with the given fields, one parameter for each, so that named arguments build a model field by field
T.f{{U < UU0}}(m : T(U))For each field f, its projection, written m.f
T.p{{U < UU0}}(m : T(U))For each parent labelled p, the model of the parent, written m.p
T.Hom(A, B), T.Hom.make, f.map …, T.Hom.id, T.Hom.compose, f.pHomomorphisms, when every carrier is a set or a proposition and no operation's argument mentions a carrier on both sides of an arrow
T.Iso(A, B), T.Iso.make, f.to …, T.Iso.id, T.Iso.compose, T.Iso.inverseIsomorphisms

The theory's name is the type of its models, T(U). The universes of a homomorphism's models, and the models themselves, are implicit in its operations: f.map and Monoid.Hom.compose(g, f) read them from the types of f and g.

What is refused

A field's name, and an operator's meaning, are each one thing:

import hlevels;

theory Twice(U < UU0) {  // Error: Twice has two fields named one: give each its own name.
  M : set U;
  one : M;
  one : M;
}

Two parents may give a carrier of one name only with one kind and type:

import hlevels;

theory Pointed(U < UU0) {
  M : set U;
  point : M;
}

theory Truth(U < UU0) {
  M : prop U;
}

theory Clash(U < UU0) extends Pointed, Truth {  // Error: Clash gets the carrier M from Pointed and Truth with different kinds or indices: rename one, as in Truth(M := …).
}

use takes a model, and m.f a field the theory has:

import unat;

def use_a_number(n : UNat) : UNat {
  use n;  // Error: use selects a model of a theory, such as m : Group(U0); this is a value of type UNat.
  exact n;
}