Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section 1: Equivalence of the two UIP formulations

Proved
HofmannStreicher1994.uip_formulations_iff

by kmehltretter82 · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

category-theorygroupoidsidentity-typestype-theory

For every expression AAA that is a well-formed type in the empty context, the following are equivalent in the specified object theory:

  1. There is a derivable term of IdIdA(x,x)(p,reflA(x))\mathrm{Id}_{\mathrm{Id}_A(x,x)}(p,\mathrm{refl}_A(x))IdIdA​(x,x)​(p,reflA​(x)) in context x:A,p,q:IdA(x,x)x:A,p,q:\mathrm{Id}_A(x,x)x:A,p,q:IdA​(x,x).
  2. There is a derivable term of IdIdA(x,y)(p,q)\mathrm{Id}_{\mathrm{Id}_A(x,y)}(p,q)IdIdA​(x,y)​(p,q) in context x,y:A,p,q:IdA(x,y)x,y:A,p,q:\mathrm{Id}_A(x,y)x,y:A,p,q:IdA​(x,y).

The source attributes this equivalence to the identity eliminator JJJ. The unused qqq in the first context is preserved. The theorem assumes only closed formation of AAA.

Preamble
import Definitions.Def_HofmannStreicher1994_Syntax
Formal statement
namespace HofmannStreicher1994

theorem uip_formulations_iff (A : Expr) (hA : TypeWf [] A) :
    (∃ t, TermWf (diagonalContext A) t (diagonalConclusion A)) ↔
      (∃ t, TermWf (uipContext A) t (uipConclusion A)) := by sorry

end HofmannStreicher1994
Source
Hofmann and Streicher, A Groupoid Model Refutes Uniqueness of Identity Proofs, author manuscript dated 21 March 1994, https://www.dcs.ed.ac.uk/home/mxh/SH.dvi.gz; LICS 1994, https://doi.org/10.1109/LICS.1994.316071. Section 1, manuscript p. 2, paragraph following Theorem 1.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex independent blind auditor)

For every raw syntactic expression AAA, and every derivation hAh_AhA​ that AAA is a well-formed type in the empty context, the following two assertions are equivalent: there exists a raw syntactic expression ddd for which the typing judgment x:A, p:Id⁡A(x,x), q:Id⁡A(x,x) ⊢d:Id⁡Id⁡A(x,x)(p,refl⁡A(x))x:A,\ p:\operatorname{Id}_A(x,x),\ q:\operatorname{Id}_A(x,x)\ \vdash d:\operatorname{Id}_{\operatorname{Id}_A(x,x)}(p,\operatorname{refl}_A(x))x:A, p:IdA​(x,x), q:IdA​(x,x) ⊢d:IdIdA​(x,x)​(p,reflA​(x)) is derivable; and there exists a raw syntactic expression uuu for which the typing judgment x:A, y:A, p:Id⁡A(x,y), q:Id⁡A(x,y) ⊢u:Id⁡Id⁡A(x,y)(p,q)x:A,\ y:A,\ p:\operatorname{Id}_A(x,y),\ q:\operatorname{Id}_A(x,y)\ \vdash u:\operatorname{Id}_{\operatorname{Id}_A(x,y)}(p,q)x:A, y:A, p:IdA​(x,y), q:IdA​(x,y) ⊢u:IdIdA​(x,y)​(p,q) is derivable. The two existential witnesses are separate and need not be the same expression. In the first assertion, the declaration of qqq is present even though qqq does not occur in the displayed conclusion; the witness ddd may use qqq. All displayed context entries are local syntactic variable declarations, written from oldest to newest, rather than quantification over elements of a semantic interpretation. The expression language consists of variables indexed by natural numbers; dependent function types, dependent pair types, identity types, natural numbers, a universe, and decoding a universe expression into a type; annotated lambda abstractions, function applications, pairs, dependent pair eliminators, reflexivity expressions, identity eliminators, zero, successors, and natural-number eliminators. Here Id⁡B(a,b)\operatorname{Id}_B(a,b)IdB​(a,b) denotes the raw identity-type constructor applied to the three expressions B,a,bB,a,bB,a,b, and refl⁡B(a)\operatorname{refl}_B(a)reflB​(a) denotes the raw reflexivity constructor. Contexts are lists of expressions with the newest declaration first in their actual representation; variable index 000 refers to the newest declaration. Thus, in the first displayed context, indices 0,1,20,1,20,1,2 refer respectively to q,p,xq,p,xq,p,x, while in the second they refer respectively to q,p,y,xq,p,y,xq,p,y,x at indices 0,1,2,30,1,2,30,1,2,3. Copies of AAA have their free indices shifted, with bound indices preserved: in the first context the types of ppp and qqq use shifts by 111 and 222, and its conclusion uses a shift by 333; in the second context the types of yyy, ppp, and qqq use shifts by 111, 222, and 333, and its conclusion uses a shift by 444. These shifts are part of the expressions in the statement, even though the named-variable notation suppresses them. Well-formedness and derivability here mean membership in the particular mutually inductively generated judgments for this syntax: the empty context is well formed, and a well-formed context can be extended by a type well formed in that context; dependent function and pair types are formed from a domain type and a codomain type in the extended context; an identity type is formed from a type and two terms of that type; natural numbers and the universe are types in any well-formed context; and an expression of universe type can be decoded into a type. Type well-formedness is also closed under a well-formed substitution and transport to an equal context. Term typing is generated by lookup of a declaration in a well-formed context, with its stored type shifted to the lookup context; dependent function abstraction and application; dependent pair introduction and elimination; reflexivity and identity elimination; zero, successor, and dependent natural-number elimination; conversion along the specified type-equality judgment; well-formed substitution; and transport to an equal context. Function application and the eliminators obtain their result types by capture-avoiding substitution into the codomain or motive. Pair elimination uses a motive over a pair and a branch over its two components; identity elimination uses a motive over two endpoints and their identity proof and a branch at equal endpoints with reflexivity; natural-number elimination uses a motive over a natural number, a branch at zero, and a branch over a natural number together with the preceding result. The type- and term-equality judgments supporting these rules are generated by typed reflexivity, symmetry, transitivity, and congruence: type congruence covers dependent function types, dependent pair types, identity types, and decoding; term congruence covers abstraction, application, pairs, pair elimination, reflexivity, identity elimination, successor, and natural-number elimination. Term equality also allows conversion along type equality. Its computation rules identify application of a lambda with substitution into its body, pair elimination on an introduced pair with substitution of its components into the branch, identity elimination at reflexivity with substitution of the endpoint into its branch, natural-number elimination at zero with its zero branch, and natural-number elimination at a successor with its successor branch instantiated by the predecessor and its recursively obtained result; it additionally identifies the function a↦f(a)a\mapsto f(a)a↦f(a) with fff. Both equality judgments are closed under well-formed substitution and transport to equal contexts; substituting equal substitutions into a well-formed type or a well-typed term also generates the corresponding equality judgment. A substitution from a source context to a target context is well formed when both contexts are well formed and, for every stored source declaration at index nnn, its image is a target-context term of the type obtained by first shifting that declaration's stored type by n+1n+1n+1 and then applying the substitution. Two substitutions are equal when each is well formed and their images at every source declaration are equal terms at the type obtained using the first substitution. Context equality is generated by equality of empty contexts and extension of equal context tails by types equal in the first tail. These are syntactic derivability assertions for each AAA satisfying the given empty-context well-formedness hypothesis; the conclusion asserts neither uniqueness of either syntactic witness nor an equality between the two witnesses.

Literal code issues. The theorem's supplied proof is the placeholder "by sorry". This read-back records its stated proposition, not a checked proof. Only the supplied declaration, its supplied syntax dependency, and the specified auditor instructions informed this read-back; no elaboration or build was run.

Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by kmehltretter82 · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me