[Agda] Self-containing inductive-recursive definitions
Dan Doel
dan.doel at gmail.com
Fri Jun 11 17:02:33 CEST 2010
Greetings,
I was reading the recent Forsberg and Setzer paper* on inductive-inductive
definitions, and they made a note that you could write definitions of that
form in Agda which contain codes for the type being defined. However, this is
currently no different than Agda's implementation of induction-recursion:
mutual
data U : Set where
u : U
x : (s : U) -> T s -> U
T : U -> Set
T u = U
T (x s y) = Σ (T s) (\z -> z == y)
Conor McBride confirmed for me that this definition would not be expressible
in the more formal treatments of induction-recursion (by Dybjer and Setzer*,
say). The positivity checker rules out some obviously bad variations of the
above, like if we try to add pi types to the universe:
pi : (s : U) -> (T s -> U) -> U
we could obtain:
pi u : (U -> U) -> U
which is correctly rejected. However, informally, even the first definition
above is bad, because the mutual definition plays on T being able to be
defined for 'the elements of U constructed thus far', while U as a whole is
not defined within the definition. More formally (Conor again informs me), the
problem is that the functor for the above definition refers to its own initial
algebra.
I don't have an example where this sort of thing leads to a proof of false; at
a guess, you probably can't do anything really terrible unless the positivity
checker is off. But, is this cause for concern anyhow? Should it be
disallowed? I'm not sure if this warrants filing an issue in the bug tracker,
so I thought I'd ask for opinions here first.
Cheers,
-- Dan
[1] http://cs.swan.ac.uk/~csfnf/papers/indind_csl2010.pdf
[2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.2863
More information about the Agda
mailing list