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. [copatterns]: https://agda.readthedocs.io/en/v2.6.1/language/copatterns.html [guardedness]: https://agda.readthedocs.io/en/v2.6.1/language/coinduction.html [streams-ctt]: https://saizan.github.io/streams-ctt.pdf 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!
{-# OPTIONS --cubical --guardedness --allow-unsolved-metas #-}
module 2020-9-11-Cutt4 where
open import Cubical.Core.Everything
open import Cubical.Foundations.Prelude
variable A B : Set
So, recall the proof of function extensionality:
functionExt : (f g : A -> B) (p : ∀ a -> f a ≡ g a) -> f ≡ g functionExt _ _ p i a = p a i
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:
- That the path’s LHS is convertible to
f- To check it, we apply
i0to the expression, and we getλ a -> p a i0, andp a : f a ≡ g awill reduce tof awhen applied byi0due to the property of the path type, so it reduces toλ a -> f a
- To check it, we apply
- That the path’s RHS is convertible to
g- To check it, we apply
i1to the expression, and we getλ a -> p a i1, which reduces toλ a -> g aSo, to some extent, we’re checking the convertibility betweenfandλ a -> f a(and similarly forg), 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 appliedi0, and similarly fori1. So, after introducing an interval patterni(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 theStreamtype?Streams
- To check it, we apply
open import Cubical.Codata.Stream open Stream -- click me to see definition of `Stream`
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)?
streamη : (a : Stream A) -> a ≡ λ where .head -> a .head .tail -> a .tail
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.
streamη a i .head = a .head streamη a i .tail = a .tail _ = Stream-η -- similar definition in the library
So, Agda checks that the term after the interval pattern:
- When unfolded by
.head, the both sides reduce toa .head- Which holds definitionally
- When unfolded by
.tail, the both sides reduce toa .tail- Ditto
And they hold, of course.
We can obtain the extensionality of
Streamin a similar way:
- Ditto
And they hold, of course.
We can obtain the extensionality of
streamExt : {a b : Stream A}
(x : a .head ≡ b .head)
(y : a .tail ≡ b .tail) -> a ≡ b
streamExt x _ i .head = x i
streamExt _ y i .tail = y i
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:
_ = mergeEvenOdd≡id
We can finally have coinduction-proof-principle (CPP) in our type theory, proved as a theorem. The proof is here:
_ = Equality≅Bisimulation.path≡bisim
Also, by isoToPath, we can prove Stream A ≡ (Nat -> A):
_ = Stream≅Nat→.Stream≡Nat→
An early note on the syntax and semantics of Stream and cubical agda
can be found in [this PDF][streams-ctt].
Conaturals
Apart from Streams, we can also play with coinductive natural numbers,
where you can define infinity:
open import Cubical.Codata.Conat.Base open Conat -- click to see the definition of `Conat` ∞ : Conat ∞ .force = suc ∞
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 Conat version.
We can prove the basic fact about infinity, where it’s successor is
equivalent to itself:
∞+1≡∞ : succ ∞ ≡ ∞ ∞+1≡∞ _ .force = suc ∞
The type-checking of this definition is the same as of streamη.
Then, with a proper definition of +,
_+_ : Conat -> Conat -> Conat _+′_ : Conat′ -> Conat -> Conat′ (x + y) .force = x .force +′ y zero +′ y = y .force suc x +′ y = suc (x + y)
We can prove that for any conatural number n,
adding it to infinity gives you infinity as well:
n+∞≡∞ : ∀ n -> n + ∞ ≡ ∞ n+′∞≡∞′ : ∀ n -> n +′ ∞ ≡ suc ∞ n+∞≡∞ n i .force = n+′∞≡∞′ (n .force) i n+′∞≡∞′ zero = refl n+′∞≡∞′ (suc n) i = suc (n+∞≡∞ n i)
This, includes infinity itself:
∞+∞≡∞′ : ∞ + ∞ ≡ ∞ ∞+∞≡∞′ = n+∞≡∞ ∞
We can also prove ∞ + ∞ ≡ ∞ by a copattern matching directly:
∞+∞≡∞ : ∞ + ∞ ≡ ∞ ∞+∞≡∞ i .force = suc (∞+∞≡∞ i)
More interesting properties can be found on
github,
where the bisimilarity is defined, CPP is proved, and the homotopy-level of Conat was proved.
