Ld Nclusion - η-rules and codata
Long time no see! This is a continuation of the cold introduction series. I'm sorry for the moronic title -- it's actually the co- version of "cold introduction", I've first fliiped "introduction" to "conclusion", and have taken away the "co-" prefix of "cold" and "conclusion", so it becomes "ld nclusion".
Why do I use such title? Well, because this time I wanna talk about codata and coinduction. So, basic knowledge on copatterns and productivity checking (guardedness) and Agda coinduction will be assumed. Links are pointed to the version v2.6.1 of the documentation.
Recall the previous post, we have introduced the composition operation. It's complicated, right? ;-)
Fortunately, this time we won't need these complicated operations. We won't need any SVG pictures either, because you've got enough of them (and should be able to draw them by yourself), and I've got enough with inkscape's shitty display on hi-dpi screens!
So, recall the proof of function extensionality:
Why does this proof type-check? Well, during type-checking, Agda first obtain the expression
λ i a -> p a i, which is of a path type, and checks the following equalities:
So, to some extent, we're checking the convertibility between
λ a -> f a (and similarly for
g), and we accepted it by η-rule. To sum up, we can obtain some extensionality proof with path type simply by introducing new paths, and return something convertible to the LHS when applied
i0, and similarly for
i1. So, after introducing an interval pattern
i (the new path), we return a new lambda that satisfies the path constraints. Apart from that, we also need very minor η-rules.
So, what about other types, whose extensionality also don't hold definitionally in MLTT (we can't prove almost any extensionality in MLTT if they're not definitional)? Can we do them in CTT? Like, some coinductive types that doesn't have definitional η-rules? Like the
Since this post assumes background on coinductive types, I'd assume the understanding of the definition of
Stream as well. Question: can we do this (the
λ where is for introducing anonymous codata, and I prefer the postfix version of projection syntax because the scope checker works better with them than the prefix ones)?
So, the simplest proof
λ a -> refl won't type-check because
streamη is equivalent to the absent definitional η-rule of coinductive types. So, like
funExt that introduces the lambda after the interval pattern, we also introduce the copattern matching after the interval pattern.
So, Agda checks that the term after the interval pattern:
When unfolded by
.head, the both sides reduce to
When unfolded by
.tail, the both sides reduce to
And they hold, of course. We can obtain the extensionality of
Stream in a similar way:
By the similar technique, we can define a function taking the even-indexed elements and odd-indexed elements, and prove that merging these two streams gives you the same stream back:
We can finally have coinduction-proof-principle (CPP) in our type theory, proved as a theorem. The proof is here:
isoToPath, we can prove
Stream A ≡ (Nat -> A):
An early note on the syntax and semantics of
Stream and cubical agda can be found in this PDF.
Streams, we can also play with coinductive natural numbers, where you can define infinity:
The definition of
Conat is a bit weird because it's essentially a sum type, unlike most codata that are record types. When defining functions or proving theorems over
Conat, we need to do define a mutually-recursive pair of functions (or theorems), including a
Conat' version of it and a
We can prove the basic fact about infinity, where it's successor is equivalent to itself:
The type-checking of this definition is the same as of
Then, with a proper definition of
We can prove that for any conatural number
n, adding it to infinity gives you infinity as well:
This, includes infinity itself:
We can also prove
∞ + ∞ ≡ ∞ by a copattern matching directly:
More interesting properties can be found on github, where the bisimilarity is defined, CPP is proved, and the homotopy-level of
Conat was proved.
This and the original version of this blog are licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.