Cubist

LANGUAGE REFERENCE · CHAPTER 6

Universes

Types of types, universe variables, and declarations checked once for every universe.

Universes

U0 denotes U₀, the universe of small types such as UNat. U1, U2, U3 and so on denote the larger universes U₁, U₂, U₃. Each universe is a type in the next one, so U0 : U1. No universe contains itself: a type of all types, itself among them, would make the logic inconsistent (Girard’s paradox), so the universes form a tower instead.

A smaller type is also a type of every larger universe: it is lifted, never silently lowered. This is called cumulativity. A type built from others lives in the largest of their universes, so UNat -> U0, a function into U0, is in U1, and a forall over all of U0 is in U1 too, as chapter 1 showed.

import unat;

def large_identity(A : U1, x : A) := x;
def lifted_unit := typed(U1, Unit);
def small_in_large : U1 := U0;
def families : U1 := UNat -> U0;
def one_unit := large_identity(Unit, tt);

large_identity takes a type in U1, and Unit, a type in U0, is lifted to it. The other direction fails: a type in U1 is not a type in U0.

import unat;

def small_identity(A : U0, x : A) := x;
def lowered := small_identity(U0, UNat);
// Error: Type mismatch: found U1, expected U0.

Universe variables

A declaration with A : U0 works only for small types. To work at every universe, bind a universe variable with U < UU0, read “U is a universe below UU0”. Inside the declaration, U is a universe like U0, so A : U is a type of that universe. The declaration is checked once, for every universe at the same time.

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);
def universe_identity := identity(U2, U1, U0);

A use passes the universe explicitly as the first argument, as in identity(U0, UNat, 3). The compiler does not infer universe arguments. The argument must be a universe: U3, a universe variable in scope, or a universe expression. Several universe variables can share a bound: (U, V < UU0, A : U, B : V).

A universe variable can also be bound in a type or a function: forall U < UU0. B and fun (U < UU0) => t. In a proof block, intro introduces it like any other binder.

def endo : forall U < UU0. U -> U := fun (U < UU0, A : U) => A -> A;
def generic_identity : forall U < UU0. forall A : U. A -> A {
  intro U;
  intro A;
  intro a;
  exact a;
}
def swap(U < UU0, A, B : U, p : A and B) : B and A {
  exact (p.2, p.1);
}

A universe variable stands for an arbitrary universe, so it is not a type of any fixed universe. U itself lives in the next universe, next(U).

import unat;

def fixed(U < UU0, f : U2 -> UNat) : UNat := f(U);
// Error: Type mismatch: found next(U), expected U2.

The word Universe is gone. A parameter written U : Universe is now written U < UU0.

def old_identity(U : Universe, A : U, x : A) := x;
// Error: Universe was removed: bind a universe variable as U < UU0.

next and max

Two functions build universes from others. next(U) is the universe just above U, so U : next(U). max(U, V) is the larger of U and V. They apply to universes only: next(UNat) is an error.

def type_of(U < UU0) : next(U) := U;
def both(U, V < UU0, A : U, B : V) : max(U, V) := A and B;
def one_level_up(U < UU0, A : U) : next(U) := A;
import unat;

def not_a_universe(U < UU0) := next(UNat);
// Error: Expected a universe: U0, UU0, a universe variable, next(E) or max(E, F).

The checker compares universe expressions by value: max(U, U) is U, next(max(U, V)) is max(next(U), next(V)), and max(U, U0) is U.

UU0 and larger universes

UU0 is the universe above every U0, U1, U2, …. UU1, UU2 and so on follow it, each containing the previous one. They are ordinary types, and cumulativity crosses from one family to the other.

def every_small_universe : UU0 := U7;
def larger : UU1 := UU0;

The bound of a universe variable is always UU0. A universe argument must lie below UU0, so a generic declaration is used at U0, U1, …, or a universe variable, but not at UU0 itself.

def identity(U < UU0, A : U, x : A) : A := x;
def too_large(T : UU0, x : T) := identity(UU0, T, x);
// Error: A universe argument must lie below UU0
def wrong_bound(U < UU1, A : U) := A;
// Error: A universe variable's bound must be UU0, as in U < UU0.

Names made of Us followed by digits, such as U1 and UU2, are universes. They cannot name a variable or a declaration. A name such as UU or U_1 is an ordinary name.

def UU2 := UNat;  // Error: UU2 is a universe constant; pick another name.

Inspecting generic declarations

Universe variables work with every construct of the later chapters. Equalities between types use them (carriers), as do rewriting with generic lemmas and the univalence builtins and library assumptions, each of which is one definition for every universe.

The inspector shows a generic declaration as the kernel checked it. A universe binder is written Π (U < ω) in a type and λ (U < ω) in a term, where ω is the kernel’s name for UU0. A use shows its universe argument, as in identity(U0, UNat, 3). The statement summary lists U < UU0 with the other parameters.