Lectures onType Theory
ch:first-class-universe-levels: ch:first-class-universe-levels
appendix sectionsolutions

ch:first-class-universe-levels: ch:first-class-universe-levels

Exercise 117.1.

Associativity and commutativity collect the four generators. Inflation gives αα+α+ and ββ+β+, so (α+β)(αβ+)α+β+. Writing the normal form as u, idempotence gives u(α+β+)u. This is the defining witness of Below(u,α+β+).

Exercise 117.2.

One suitable term is λh.(h0N0,h0+U0N,h0+(Lift0+N)(lift0)), with type (Πt:Level.ΠA:Ut.AA)N×U0×Lift0+N. The three applications use respectively N:U0, U0:U0+, and Lift0+N:U00+U0+. The higher-rank product Πt:Level.ΠA:Ut.AA is well formed but inhabits no single universe, because its codomain level depends on the bound term t.

Exercise 117.3.

For z:Liftu(LiftvA), define F(z)=liftuv(lowerv(loweruz)). For w:LiftuvA, define G(w)=liftu(liftv(loweruvw)). Two uses of Lift-F place the source of F in Utvu; one use places its target in Ut(uv), and associativity converts the levels. The same calculation types G. Repeated Lift-β lowers both composites to the corresponding input after lowering. Applying Lift-η outward once on the single lift and twice on the nested lift gives F(G(w))w and G(F(z))z. With syntactic level identity, the universe conversion between (tv)u and t(uv) would fail; the decision procedure of corollary 117.10 supplies that equality.

Exercise 117.4.

The principal calculus has level terms t::=0t+tt, the typing judgment Γt:Level, and universes Ut. At that signature, Corollary 4.3 of Danielsson, Favier, and Kubánek gives decidable judgmental equality, as recorded in theorem 117.11.

The bounded calculus has level expressions generated by zero, successor, and join, but a level is typed by a bound-sensitive judgment Γk:Level<. At that signature Chan and Weirich prove subject reduction, type safety, consistency, and canonicity; normalization of open terms and decidable checking are not among the proved claims.

The displacement system takes external level expressions in a hierarchy H(Δ). Its core judgments include ΓH(Δ)Atype and ΓH(Δ)e:A; closed declarations may be acted on by a displacement. Theorem 3.10 of Hou, Angiuli, and Mullanix sends every hierarchy theory, under its stated smallness hypotheses, faithfully into a displacement algebra.

None of these results transfers by shared notation. Decidable equality for the principal calculus does not decide the bound-sensitive relation of the bounded calculus or the external order of an arbitrary displacement algebra. Subject reduction for bounded levels does not prove normalization of the principal or displacement systems. The displacement representation theorem does not type the higher-rank twiceLevel term and proves neither bounded-level canonicity nor the principal calculus’s erasure theorem. Each transfer would require a typed translation and preservation of the relevant conversion or reduction judgment.

Exercise 117.5.

The source ledger is

principal POPL 2026 calculus bounded calculus
normalization proved open for open terms
canonicity proved proved in Lean
subject reduction proved proved in Lean
decidable equality proved not supplied
decidable checking stated fragment open.

The first column is exactly the theorem package of theorem 117.11; the second is the bounded-system package recorded in its comparison card. Blank or open cells cannot be filled by transporting a result across the different level, lift, and bound rules.

Search the book

Type to search the local edition.