Reference · Logic
rainbow.math.logic.proof-irrelevance
Proof irrelevance from propositional extensionality. `logic/proof-irrelevance-from-proposition-extensionality` has exactly the statement of the axiom `logic/proof-irrelevance` (rainbow.math.profile): forall {claim : Prop} (left right : claim), Eq.{0} claim left right and its kernel axiom closure is exactly #{logic/proposition-extensionality}. This is the CIC result that propositional extensionality implies proof irrelevance (Coq: Coq.Logic.ClassicalFacts, ext_prop_dep_proof_irrel_cic). It uses neither excluded middle, nor choice, nor proof irrelevance itself. Route: 1. `logic/PropUnit : Prop`, an inductive proposition with one constructor `logic/prop-unit` and no fields. Its generated recursor `logic/PropUnit.rec` takes a dependent motive `PropUnit -> Sort m`; every motive below is into Prop, so no large elimination is involved (and the kernel's large-elimination rule only restricts blocks with two or more constructors anyway). 2. `logic/prop-unit-eq-point`: every x : PropUnit equals prop-unit (recursor with motive fun z => Eq PropUnit z prop-unit, case reflexivity). 3. `logic/prop-unit-proofs-equal`: any two x y : PropUnit are equal (recursor on x, then on y; the last case is reflexivity). Axiom-free. 4. `logic/prop-unit-equals-inhabited`: an inhabited claim (p : claim) is equivalent to PropUnit (fun _ => p and fun _ => prop-unit), so by `logic/proposition-extensionality` Eq.{1} Prop PropUnit claim. 5. `logic/prop-unit-transport-proofs-equal`: Leibniz transport along Eq Prop PropUnit claim with motive fun Q => forall x y : Q, Eq Q x y turns step 3 into proof irrelevance for claim. Axiom-free. 6. The theorem: steps 4 and 5 at claim, using `left` itself as the inhabitant p. How the proofs were found (rainbow.core/prove and search/prove with a reuse/build-index index and the proving loop's candidate options): the search found steps 4 and 5 unaided once the earlier lemmas were indexed, and closed the reflexivity cases of steps 2 and 3 after an AI-proposed `intro`/`induction` decomposition (the search's native inductive cases cover only a fixed list of data types, so it never inducts on PropUnit itself). `logic/prop-unit-holds` and the final assembly (step 6) were hand-written: the search returned them as blockers, the first because no constructor of a new block is offered as an exact candidate, the second because applying a lemma with dependent binders fails with :tactic/dependent-apply-unsupported. Each value below is the kernel term the loop returned, written in surface syntax; the test checks the statement and the axiom closures.
logic/prop-unit-holds
logic/prop-unit-holds : logic/PropUnit
logic/prop-unit-eq-point
logic/prop-unit-eq-point : (x : logic/PropUnit) → x = logic/prop-unit
= = equality/Eq
logic/prop-unit-proofs-equal
logic/prop-unit-proofs-equal : (x y : logic/PropUnit) → x = y
= = equality/Eq
logic/prop-unit-equals-inhabited
logic/prop-unit-equals-inhabited : (claim : Prop) (evidence : claim) → logic/PropUnit = claim
= = equality/Eq
logic/prop-unit-transport-proofs-equal
logic/prop-unit-transport-proofs-equal : (claim : Prop) (same : logic/PropUnit = claim) (x y : claim) → x = y
= = equality/Eq
logic/proof-irrelevance-from-proposition-extensionality
logic/proof-irrelevance-from-proposition-extensionality : (claim : Prop) (left right : claim) → left = right
= = equality/Eq