Prouver avec les principes de co-induction

Question

Je passe par la «programmation certifiée d'Adam Chlipala avec des types dépendants» (disponible ici pour plus de commodité), et je suis un peu coincé à internaliser le principe d'introduction du co-induction pour le stream_eq prédicat dans le chapitre 5.

Premièrement, je suis habitué aux schémas d'induction définis pour les structures de données (stream Dans ce cas, s'il s'agissait de données et non de codata). Pourtant, le principe de co-induction introduit semble être défini pour le prédicat que nous essayons de faire ses preuves, et comment se connecte-t-il avec les éléments suivants (la nôtre cursive)?

Dument, un principe de co-induction devrait être paramétré sur un prédicat Caractérisant ce que nous voulons prouver, en fonction des arguments au prédicat co-indicatif que nous essayons de prouver.

Ou devrais-je analyser cela comme impliquant une paramétrisation sur le prédicat R : stream A -> stream A -> Prop, qui, pour moi, semble être une reformulation de stream_eq, tenir compte de l'hypothèse suivante?

Hypothesis Cons_case_hd : forall s1 s2, R s1 s2 -> hd s1 = hd s2.
Hypothesis Cons_case_tl : forall s1 s2, R s1 s2 -> R (tl s1) (tl s2).

Deuxièmement, compte tenu du texte cité à nouveau, nous essayons de prouver stream_eq. Quels seraient les arguments de ce prédicat ici? On dirait que ce devrait être les flux, mais l'hypothèse semble être beaucoup plus complexe que cela.

Enfin, tout ça stream_eq_coind me semble une façon quelque peu générique de faire le match Acrobatie sur les flux pour permettre au simplificateur de se dérouler (comme le fait Chlipala dans la version de la preuve précédant cette partie). Est-ce correct ou est-ce que je manque un sens plus profond?

Oh, et quelles seraient de bonnes sources à lire sur la co-induction? Quelques articles ou tutoriels que j'ai trouvés se réfèrent à une algèbre ou à une logique (c.-à-d. Les modèles Kripke) au-delà de mes connaissances actuelles.