A pure type system is specified by a set of sorts, a relation assigning sorts to sorts, and a relation governing the formation of dependent products. A legal expression is the subject or expected type of a derivable typing judgment in a valid context. Full -reduction permits reduction inside type annotations. System-wide weak normalization means that every legal expression in every valid context has a normal form. System-wide strong normalization means that no legal expression in any valid context admits an infinite reduction sequence. The question is whether system-wide weak normalization implies system-wide strong normalization for arbitrary pure type systems.
Geuvers formulated the conjecture. Barthe, Hatcliff and Sørensen established the implication for a class of nondependent pure type systems.
The preprint proves that every weakly normalizing pure type system is strongly normalizing for full -reduction.
The Lean library TypeSystem takes system-wide weak normalization as the hypothesis of its main theorem. Lean has checked every result of the Lean library, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its Lean declaration. Where the preprint gives a different statement, its version is given beside the Lean library’s statement. The preprint serves only as a guide to the order and names of the results.
TypeSystem is a Lean library: 67 items, in ten groups. Each has a page written by OctoInform, listed below.
No item matches.