Exercise 117.1.
Associativity and commutativity collect the four generators. Inflation gives 𝛼 ⊔𝛼+ ≡𝛼+ and 𝛽 ⊔𝛽+ ≡𝛽+, so (𝛼+⊔𝛽)⊔(𝛼⊔𝛽+)≡𝛼+⊔𝛽+. Writing the normal form as 𝑢, idempotence gives 𝑢 ⊔(𝛼+ ⊔𝛽+) ≡𝑢. This is the defining witness of 𝖡𝖾𝗅𝗈𝗐(𝑢,𝛼+ ⊔𝛽+).
Exercise 117.2.
One suitable term is 𝜆ℎ.(ℎ0ℕ0,ℎ0+U0ℕ,ℎ0+(𝖫𝗂𝖿𝗍0+ℕ)(𝗅𝗂𝖿𝗍0)), with type (Π𝑡:𝖫𝖾𝗏𝖾𝗅.Π𝐴:U𝑡.𝐴→𝐴)→ℕ×U0×𝖫𝗂𝖿𝗍0+ℕ. The three applications use respectively ℕ :U0, U0 :U0+, and 𝖫𝗂𝖿𝗍0+ℕ :U0⊔0+ ≡U0+. The higher-rank product Π𝑡 :𝖫𝖾𝗏𝖾𝗅.Π𝐴 :U𝑡.𝐴 →𝐴 is well formed but inhabits no single universe, because its codomain level depends on the bound term 𝑡.
Exercise 117.3.
For 𝑧 :𝖫𝗂𝖿𝗍𝑢(𝖫𝗂𝖿𝗍𝑣𝐴), define 𝐹(𝑧)=𝗅𝗂𝖿𝗍𝑢⊔𝑣(𝗅𝗈𝗐𝖾𝗋𝑣(𝗅𝗈𝗐𝖾𝗋𝑢𝑧)). For 𝑤 :𝖫𝗂𝖿𝗍𝑢⊔𝑣𝐴, define 𝐺(𝑤)=𝗅𝗂𝖿𝗍𝑢(𝗅𝗂𝖿𝗍𝑣(𝗅𝗈𝗐𝖾𝗋𝑢⊔𝑣𝑤)). Two uses of Lift-F place the source of 𝐹 in U𝑡⊔𝑣⊔𝑢; one use places its target in U𝑡⊔(𝑢⊔𝑣), and associativity converts the levels. The same calculation types 𝐺. 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 𝐹(𝐺(𝑤)) ≡𝑤 and 𝐺(𝐹(𝑧)) ≡𝑧. With syntactic level identity, the universe conversion between (𝑡 ⊔𝑣) ⊔𝑢 and 𝑡 ⊔(𝑢 ⊔𝑣) would fail; the decision procedure of corollary 117.10 supplies that equality.
Exercise 117.4.
The principal calculus has level terms 𝑡 ::=0 ∣𝑡+ ∣𝑡 ⊔𝑡, the typing judgment Γ ⊢𝑡 :𝖫𝖾𝗏𝖾𝗅, and universes U𝑡. 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 Γ ⊢𝑘 :𝖫𝖾𝗏𝖾𝗅<ℓ. 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 𝐻(Δ). Its core judgments include Γ ⊢𝐻(Δ)𝐴 𝗍𝗒𝗉𝖾ℓ and Γ ⊢𝐻(Δ)𝑒 :𝐴; 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 𝗍𝗐𝗂𝖼𝖾𝖫𝖾𝗏𝖾𝗅 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.