[Agda] Induction from Sigma?

Joey Eremondi joey.eremondi at gmail.com
Thu Apr 9 07:59:12 CEST 2020


I have an inductive type that looks something like this:

data Foo : Set where
  A : (Foo , Foo) -> Foo
  B : (Nat -> Foo) -> Foo
  C : Unit -> Foo

I'm trying to show that P holds for Foo, for some specific P : Set -> Set.
I currently have:

  (A B : Set) -> P A -> P B -> P (A , B)
  (A : Set) -> P A -> P (Nat -> A)
  P Unit
and importantly,
  (I : Set) -> (T : I -> Set) -> ( (i : I) -> P (T i) ) -> P (Sigma I T)
i.e. we can compose P for any n-ary sum type.

What I'm wondering is, is there any way I can combine these to get P Foo?

Some notes:
* I don't want to prove P Foo directly, because I want the ability to add
constructors and easily compose the proofs into a proof of Foo P.
* I'm open to other representations of Foo. The only reason I'm not having
it as a Sigma type is that that doesn't allow for self-reference.

My ideas:

* If I can show that P holds under isomorphism, then I can show that Foo is
isomorphic to (Foo \times Foo) + (Nat -> Foo) + Unit. But I'm not certain
that this will still be well-founded recursion.
* Maybe sized types can be used to make an explicit fixed-point operator,
so I can have a recursive sum?
* Could Containers, W-types, Descriptions, levitation, etc. be useful here?

Thanks!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20200408/6c3add90/attachment.html>


More information about the Agda mailing list