OctoInformBeta

Weak normalization implies strong normalization in pure type systems

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 β\beta-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 β\beta-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.

The Lean library: TypeSystem

TypeSystem is a Lean library: 67 items, in ten groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. Specification, expressions, typing, and normalization Typing and normalization in pure type systems. §1
  2. Theorem 1 Weakly normalizing pure type systems normalize strongly.
§2. Structural properties 12 items
  1. Lemma 2 Typing enforces context validity and scoping.
  2. Lemma 3 Typed renaming preserves dependent typing.
  3. Lemma 4 Typed substitution preserves typing in valid contexts.
  4. Lemma 5 Sorted head conversion preserves typing.
  5. Lemma 6 Typing generation recovers constructor premises.
  6. Lemma 7 Assigned types are sorts or have sorts.
  7. Lemma 8 Full β\beta reduction is confluent.
  8. Lemma 9 Full beta reduction preserves typing.
  9. Lemma 10 Neutral terms have unique types up to conversion.
  10. Lemma 11 Normal forms retain typing under weak normalization.
  11. Lemma 12 Localizing a failure of strong normalization.
  12. Lemma 13 Saturated towers supply arbitrarily late variables.
§3. Sort profiles and normalization candidates 9 items
  1. Profiles and the signed dependency graph Sort profiles and their signed dependencies. §3
  2. Lemma 14 Sort profiles obey shape and transport laws.
  3. Actual types, tested stacks, candidates, and the interface Candidates between normalization and stack tests. §3
  4. Lemma 16 Ground candidates refine typed strong normalization.
  5. Lemma 17 Sufficient conditions for strongly normalizing head expansions.
  6. Lemma 18 Constructing candidates by intersection and application.
  7. Lemma 19 Strong normalization yields substitution transport.
  8. Proposition 20 A component interpretation identifies two normalization candidates.
  9. Proposition 21 From component interfaces to strong normalization.
§4. Two component constructions 5 items
  1. Proposition 22 Primary components without odd closed walks admit interpretations.
  2. Lemma 23: dependence on support Signed support controls candidate comparison.
  3. Lemma 23: structural invariance Structural invariance of one-child candidate evaluation.
  4. Lemma 24 Compatible bits control substitution comparisons.
  5. Proposition 25 One-child candidates furnish component interpretations.
§5. Observation spaces and substitution-stable candidates 9 items
  1. Layers, spaces, environments, goodness, and the graph exclusion Observation layers and their candidate interpretation. §5
  2. Lemma 26 Plainness propagates backwards and free signs compose.
  3. Lemma 27 Graph exclusion permits recursive plain spaces.
  4. Lemma 28 Observation outputs under changes of typing data.
  5. Lemma 29 Conversion and renaming preserve structural goodness.
  6. Lemma 30 Substitution preserves good observations.
  7. Lemma 31 Full reduction transports good observations.
  8. Lemma 32 Normal evaluation forgets its typing tree choices.
  9. Proposition 33 Component laws for observation interpretations.
§6. A typed calculus for the forbidden configuration 5 items
  1. Modes, terminal converters, formulas, and data wrappers Modes and wrappers for a logical calculus. §6
  2. Lemma 34 Labelled typing supports reduction and erasure.
  3. Lemma 35 Terminal networks preserve converter contexts.
  4. Lemma 36 Boolean consequences yield labelled proof terms.
  5. Lemma 37 Fixed data wrappers admit typed cancellation.
§7. Typed data channels 7 items
  1. The forbidden configuration and two data channels Fixed data channels and quantifier routes. §7
  2. Lemma 38 Forbidden configurations determine channel paths.
  3. Lemma 39 Rounding preserves observations in formed channels.
  4. Lemma 40 Canonical embeddings retain their signed payloads.
  5. Lemma 41 Encoding distinguishes tags and preserves observations.
  6. Lemma 42 Tests of dummy and point observations.
  7. Lemma 43 Access laws for typed data bundles.
§8. Relational coding of the diagonal argument 9 items
  1. Admissibility, comparison, probes, and the chosen query parameter Relational codes and a chosen query parameter. §8
  2. Lemma 44 Observation laws relate inputs to channel rounding.
  3. Lemma 45 Class evaluations and congruence for constructed pairs.
  4. Lemma 46 Probe comparison is an equivalence relation.
  5. Lemma 47 Tagged observations separate the three copies.
  6. Lemma 48 An admissible parameter for structural queries.
  7. Lemma 49 The specialization recovers structural observations.
  8. Lemma 50 Class and edge rules from tagged witnesses.
  9. Lemma 51 Response pairing distinguishes left and right tags.
§9. The guarded diagonal argument 6 items
  1. Response predicates, shift, and induction Response predicates and a guarded induction object. §9
  2. Lemma 52 Guarded laws for the response predicate.
  3. Lemma 53 Diagonal shifting respects guarded comparison.
  4. Lemma 54 Pointwise comparison transports guarded induction.
  5. Lemma 55 Guarded induction at the well-foundedness object.
  6. Proposition 56 Formed specialized observations inhabit the logical terminal.
§10. Exclusion and completion of the proof 3 items
  1. Terminal targets and the proof context Normal targets and converter proof contexts. §10
  2. Lemma 57 Normal proof exclusion in converter contexts.
  3. Proposition 58 Finite weakly normalizing systems satisfy relational exclusion.

No item matches.