¿Cuándo se puede usar la hipótesis de coinducción?

Question

Podemos usar la hipótesis de inducción cuando estamos demostrando una propiedad para una estructura que está bien ordenada. Soy consciente de que hay una prueba para esto.

Cuando se trata de coinducción, estoy confundido.

Una de las respuestas a otra pregunta " ¿Qué es la coinducción? " menciona que hay una noción de una definición correcursiva para estar bien formada.

Muchas cosas que (intento) leer relacionadas con la coinducción en su mayoría hablan sobre la bisimulación y la equivalencia. Pero a lo mejor de mi conocimiento, esos están tratando de probar alguna relación para dos estructuras de datos coinductivos. Por ejemplo, demuestran que dos corrientes son equivalentes. Y la hipótesis coinductiva se deriva de alguna manera de una de las hipótesis de la bisimulación. Aun así, creo que todavía estoy perdido en los requisitos de lo que constituye la bien formación en el mundo coinductivo.

Puedo ver que la hipótesis de coinducción funciona al probar aquellos tipos de proposiciones, pero todavía no estoy claro cuando se pueden usar para probar proposiciones más generales, como la mencionada en ¿Qué es la coinducción? . En ese enlace, la proposición afirma que "algo es infinito". Esto parece una forma más genérica de declaración que uno estaría interesado en demostrar.

Una pregunta posiblemente relacionada es si alguna proposición se puede convertir y volver a establecer como una propuesta de equivalencia o no.

¿Hay algún razonamiento informal simple que habla por qué la coinducción funciona para algún requisito de bien formación?

Espero una explicación como si fuera posible: https://math.stackexchange.com/questions/432293/well-ordering-and-mathematical-induction/432302#432302 .

Answer 1

Primero, permítame recordar los puntos fijos menos y los mejores fijos para $ \ subespeteq $ . Estamos trabajando en relación con un establecimiento $ u $ , el universo. En el caso de (CO) definiciones inductivas, $ u $ es el conjunto de todos los términos. Una función $ f: 2 ^ u \ to2 ^ u $ (de subconjuntos de $ u $ a subconjuntos de $ u $ ) es monotone , si $ a \ subestexq b $ Siempre implica $ f (a) \ subestesteq f (b) $ . Un punto fijo de $ f $ es un conjunto $ a $ tal que $ f (a)= A $ .

para monótono $ f $ siempre hay un punto menos fijo $ \ m mu f $ , a saber La intersección de todos los $ A \ Subesteq U $ de tal que $ f (a) \ subestesteq a $ . menos significa que para los puntos fijos arbitrarios $ f $ siempre tenemos $ \ m mu f \ subesteeteq F $ .

Para un ejemplo, deje que $ f _ {\ tt nat} $ se define por $ f _ {\ tt nat} (A)={0 \ \ \ CUP \ \ \ {N + 1 \ Mid N \ in A \} $ . La función $ f _ {\ tt nat} $ es la función de cierre de un paso debajo de los constructores $ 0 $ y $ + 1 $ . La condición $ f _ {\ tt nat} (a) \ subespeteq A $ significa que $ a $ es Cerrado bajo los constructores $ 0 $ y $ + 1 $ . La intersección significa que el $ \ m mu f _ {\ tt nat} $ contiene solo los elementos que se encuentran en cada conjunto cerrado debajo de los constructores. Estos son los números naturales. El ejemplo muestra cómo la definición inductiva de números naturales es el punto menos fijo de cierre bajo los constructores de los números naturales. En general, los conjuntos inductivamente definidos son los puntos menos fijos de cierre en constructores.

dualmente, para monótono $ f $ también hay un punto de referencia fijo más grande $ \ nu f $ , a saber, la Unión de todos los $ a \ subesteqq u $ , de modo que $ f (a) \ supseteq a $ . mayor significa que para puntos fijos arbitrarios $ f $ siempre tenemos $ \ nu f \ supseteq F $ . Para completar la dualidad, notemos que la intersección es la $ \ subesteteq $ -infimum and union the $ \ subespeteq $ -supremum y, por lo tanto, el $ \ supseteq $ -infimum. Entonces, de hecho, los mejores puntos fijos para $ \ subestesteq $ son solo puntos menos fijos para $ \ supseteq $ y viceversa. (Además, observe que el requisito de monotonicidad es el mismo para $ \ subestesteq $ como para $ \ supseteq $ .)

ahora, para técnicas de prueba. Comencemos con el ejemplo de la inducción en números naturales. Para mostrar que algunas propiedades $ P $ se mantienen para todos los números naturales, mostramos que $ P (0) $ y ese $ P (n) $ implica $ P (n + 1) $ . Viendo $ P $ como un subconjunto de $ u $ (el conjunto de todos los elementos donde sostiene la propiedad) La obligación de prueba para la inducción natural es que $ P $ está cerrado bajo $ f _ {\ tt nat} $ . La corrección de la técnica de prueba de la inducción natural se sigue a partir de la definición de punto menos fijo: si $ f _ {\ tt nat} (p) \ subespeteq p $ , luego < span class="Math-contenedor"> $ P $ es parte de la intersección que forma $ \ m mu f _ {\ tt nat} $ , por lo que el La propiedad se mantiene en todo el $ \ mu f _ {\ tt nat} $ , que es $ \ m mu f _ {\ tt nat} \ {\ tt nat} \ subespeteq p $ .

La inducción es solo la generalización del párrafo anterior al monótono arbitrario $ f $ en lugar de $ f _ {\ tt nat } $ . La coinducción es la doble de la inducción: la obligación de prueba es $ f (p) \ supseteq p $ . Esto significa que si $ p $ se mantiene en algún elemento $ x $ , luego

Clase="Math-contenedor"> $ x $ se construye utilizando solo elementos base en los que $ P $ también se mantiene. Entonces, en lugar de demostrar que la propiedad sobrevive a la aplicación de constructores, tenemos que demostrar que sobrevive a la deconstrucción. Una vez que se cumple la obvicitación de la prueba, obtenemos $ \ nu f \ supseteq p $ .

¿Qué bueno es la conclusión $ \ nu f \ supseteq p $ ? Permítanos reconsiderar $ p $ no como una propiedad, sino como un subconjunto de $ u $ . La conclusión de coinducción establece que todos los elementos de $ P $ son miembros bien formados del conjunto coinductivamente definido $ \ nu f $ . Esto es lo que sucede en el ejemplo en ¿Qué es la coinducción? Mostrando forall n, Infinite (from n). Aquí, $ f $ está cerrado bajo los constructores de Infinite (no de colist!) Y $ P $ es el conjunto de todos los términos del formulario from n para algún n.