¿Son necesarias las pruebas coinductive?

Question

He estado explorando corecursion en Coq (específicamente, infinitas secuencias de números naturales) y últimamente hasta ahora cualquier coinductive predicado he construido y su coinductive prueba puede ser transformado en un predicado inductivo y el inductivo prueba con una prueba de que cualquiera de los estilos de prueba puede ser construido a partir de la otra. Sin duda el coinductive versión es a menudo más fácil de escribir, pero hay algo que puede ser probado con coinduction que no puede ser con la inducción? Tal vez es el caso de los infinitos arroyos, pero hay otros infinitos objetos en los que esto no es cierto?

Como ejemplo tengo el coinductive predicado

$\operatorname{increasing} : \forall s\,n,\; n < \operatorname{head} s \implies \operatorname{increasing} s \implies \operatorname{increasing} (n \operatorname{cons} s)$

y el predicado inductivo

$\operatorname{increasing'} : \forall s,\; (\forall n,\; s[n] < s[n+1]) \implies \operatorname{increasing'} s$

y una prueba de que

$\forall s,\; \operatorname{increasing} s \iff \operatorname{increasing'} s$

Intuitivamente parece que el coinductive principio dice algo así como "nunca se puede ver una falsificación del predicado" que puede girar en torno a un argumento inductivo en el número de observaciones o, equivalentemente, cuánto del objeto infinito fuerza.

Si desea ver el Coq desarrollo para el aumento de predicado es en https://gist.github.com/3953040

Answer 1

Inductivo pruebas sólo se puede probar directamente las propiedades del conjunto de finito inicial subsecuencias de los arroyos - que directamente no se puede probar nada acerca del infinito arroyos. Esto es debido a la inducción sólo "llega" bien fundado de los elementos del tipo constructor, mientras que coinductive pruebas de llegar a todos estos elementos y el mal fundada como los elementos de la secuencia infinita 1,2,3,...

Dicho esto, mediante la apelación a la toma lema (dos arroyos que están de acuerdo en todos los iniciales de subsecuencias de una longitud dada son el mismo), puede utilizar inductivo pruebas de la razón sobre todas las corrientes. Pero usted no puede probar que el tomar lema inductiva.