Rewrite under exists

Question

Say I have the following relation:

Inductive my_relation: nat -> Prop :=
constr n: my_relation n.

and I want to prove the following:

Lemma example:
  (forall n, my_relation n -> my_relation (S n)) -> (exists n, my_relation n) -> exists n, my_relation (S n).
Proof.
  intros.

After introducing, I have the following environment:

1 subgoal
H : forall n : nat, my_relation n -> my_relation (S n)
H0 : exists n : nat, my_relation n
______________________________________(1/1)
exists n : nat, my_relation (S n)

My question is: is there a possibility to rewrite H under the exists quantifier ? If not, is there a strategy to solve this kind of problem (this particular one is not really relevant, but problems where you have to prove an exists using another exists, and where, informally, you can « deduce » a way to rewrite the exists in the hypothesis into the exists in the goal) ?

For instance, if I try rewrite H in H0. I have, an error (Error: Cannot find a relation to rewrite.).

Answer 1

The standard way to manipulate an existential quantification in an hypothesis is to get a witness of the property using inversion or, better and simpler, destruct.

You can give a name to the variable using one of the following syntaxes:

destruct H0 as (n, H0).
destruct H0 as [n H0].
destruct H0 as (n & H0).

Note that you can also destruct an hypothesis using intro-patterns.

intros H (n & H0).

And you can even directly apply H in H0.

intros H (n & H0%H). exists n. assumption.

Software Foundations explains this in a clear way.