Search code examples
coqcoq-tactic

Rewriting at the type level


I have the following proof state:

1 subgoals
U : Type
X : Ensemble U
Y : Ensemble U
f : U -> U
g : U -> U
pF : proof_dom_cod U X Y f
pG : proof_dom_cod U X Y g
fg : f = g
H : proof_dom_cod U X Y g = proof_dom_cod U X Y f
______________________________________(1/1)
createarrow U X Y f pF = createarrow U X Y g pG

So I want to

assert (pF = pG)

and then use proof irrelevance to prove that. Unfortunately, pF = pG is not valid because they have different types, even though I know the types to be the same because H. saying rewrite H or rewrite H in pF leads to a match failure, I assume because in pF refers to the value not the type.

Is there an equivalent to rewrite for types?

Here's the theorem I'm trying to complete (with all necessary definitions).

Require Import Coq.Logic.FunctionalExtensionality.
Require Import Coq.Sets.Ensembles.
Require Import Coq.Logic.Classical_Prop.


Definition proof_dom_cod 
(U : Type) (X Y : Ensemble U) (f : U -> U) : Prop
    := forall x : U, In U X x -> In U Y (f x).

Inductive setarrow (U : Type) (X Y : Ensemble U) : Type
        :=
    | createarrow (f : U -> U) (proof : proof_dom_cod U X Y f).

Lemma eq_setarrow
    (U : Type) (X Y : Ensemble U) (f g : U -> U) (pF : proof_dom_cod U X Y f) (pG : proof_dom_cod U X Y g)
        : (f = g -> (createarrow U X Y f pF = createarrow U X Y g pG)).
    intros fg.
    assert (proof_dom_cod U X Y g = proof_dom_cod U X Y f).
        rewrite fg.
        trivial.
Qed.

Solution

  • This is not an answer to the general question, but here subst does the work. The proof can be finished as follows:

    subst f.
    apply f_equal. apply proof_irrelevance.