>
\end{code}
Another example is the generalised IID of proofs that a natural numbers are
even given introduction rules
\begin{code}
evenZ : Even zero
evenSS : (n : Nat) -> Even n -> Even (suc (suc n))
\end{code}
The code for |Even| is
\begin{code}
gammaEven : OPg Nat
= sigma 2 (\ c. elim2 c (iota zero) (sigma Nat (\ n. delta 1 (\ x. n) (iota (suc (suc n))))))
\end{code}
Again an argument of type |2| is used to distinguish the two constructors. In
the |evenZ| case there are no arguments and the index is |zero|. In the
|evenSS| case there is one non-inductive argument |n| of type |Nat| and one
inductive argument with no assumptions and index |n|. The index of the result
is |suc (suc n)|.
The Paulin-Mohring intensional identity type also has a code. Given a set |A|
and an |x : A| code for the family |x == y| indexed by |y : A| is
\begin{code}
gammaId : OPg A = iota x
\end{code}
That is, there is a single constructor with no arguments, whose index is |x|.
This corresponds to the introduction rule
> refl : x == x
The elimination rule for this type is exactly the Paulin-Mohring elimination rule.
\section{Encoding generalised IID as restricted IID} \label{sec-Encoding}
In this section we show that generalised IID are expressible in the logical
framework extended with restricted IID and the intensional identity type. We do
this by defining the formation, introduction, and elimination rules of a
generalised IID and subsequently proving that the computation rules hold
intensionally.
\subsection{Formation rule}
We first show how to transform the code for a generalised IID into the code for
its encoding as a restricted IID. The basic idea, as we have seen, is to add a
proof that the index of the restricted IID is equal to the index computed for
the generalised IID. Concretely:
\begin{code}
eps_I : OPg I -> OPr I
eps (iota i) j = sigma (i == j) (\ p. iota star)
eps (sigma A gamma) j = sigma A (\ a. eps (gamma a) j)
eps (delta H i gamma) j = delta H i (eps gamma j)
\end{code}
Now a generalised IID for a code |gamma| can be defined as the restricted IID
of |eps gamma|.
\begin{code}
Ugg : I -> Set
Ugg i = Ureg i
\end{code}
For example, the generalised IID of the proofs that a number is even, given by
\begin{code}
Even : Nat -> Set
evenZ : Even zero
evenSS : (n : Nat) -> Even n -> Even (suc (suc n))
\end{code}
is encoded by the following restricted IID:
\begin{code}
Even' : Nat -> Set
evenZ' : (n : Nat) -> zero == n -> Even' n
evenSS' : (n : Nat)(m : Nat) -> Even' m -> suc (suc m) == n -> Even' n
\end{code}
\subsection{Introduction rule}
We need an introduction rule
\begin{code}
introgg : (a : Args gamma Ugg) -> Ugg (index gamma Ugg a)
\end{code}
and we have the introduction rule for the restricted IID:
\begin{code}
introreg i : Args (eps gamma i) Ureg -> Ureg i
= Args (eps gamma i) Ugg -> Ugg i
\end{code}
So, what we need is a function |grArgs| to convert a constructor argument for a
generalised IID, |a : Args gamma Ugg|, to a constructor argument for its
representation, |Args (eps gamma (index gamma Ugg a)) Ugg|. This function
simply adds a reflexivity proof to |a|:
\begin{code}
grArgs_I : (gamma : OPg I)(U : I -> Set)
(a : Args gamma U) -> Args (eps gamma (index gamma U a)) U
grArgs (iota e) U a = < refl, star >
grArgs (sigma A gamma) U < a, b > = < a, grArgs (gamma a) U b >
grArgs (delta H i gamma) U < g, b > = < g, grArgs gamma U b >
\end{code}
As usual we abstract over the type of inductive occurrences. Now the
introduction rule is simply defined by
\begin{code}
introgg a = introreg (index gamma Ugg a) (grArgs gamma Ugg a)
\end{code}
In our example:
\begin{code}
evenZ : Even' zero
evenZ = evenZ' refl
evenSS : (n : Nat) -> Even' n -> Even' (suc (suc n))
evenSS n e = evenSS' n e refl
\end{code}
\subsection{Elimination rule}
Now we turn our attention towards the elimination rule.
\begin{theorem}
The elimination rule for a generalised IID is provable for the representation
of generalised IID given above. More precisely, we can prove the following rule
in the logical framework with restricted IID and the identity type.
\begin{code}
elimUgg : (C : (i : I) -> Ugg i -> Set) ->
( (a : Args γ Ugg) -> IndHyp γ Ugg C a ->
C (index γ Ugg a) (introgg a)) ->
(i : I)(u : Ugg i) -> C i u
\end{code}
\end{theorem}
\begin{proof}
We can use the elimination for the restricted IID
\begin{code}
elimUreg : (C : (i : I) -> Ugg i -> Set) ->
( (i : I)(a : Args (eps gamma i) Ugg) ->
IndHyp (eps gamma i) Ugg C a -> C i (introreg i a)) ->
(i : I)(u : Ugg i) -> C i u
\end{code}
Now we face the opposite problem from what we encountered when defining the
introduction rule. In order to apply the induction step we have to convert a
constructor argument to the restricted IID to a generalised argument, and
likewise for the induction hypothesis. To convert a restricted constructor
argument we simply remove the equality proof.
\begin{code}
rgArgs_I : (gamma : OPg I)(U : I -> Set)
(i : I)(a : Args (eps gamma i) U) -> Args gamma U
rgArgs (iota i) U j _ = star
rgArgs (sigma A gamma) U j < a, b > = < a, rgArgs (gamma a) U j b >
rgArgs (delta H i gamma) U j < g, b > = < g, rgArgs gamma U j b >
\end{code}
Converting induction hypotheses requires a little more work. This work,
however, is pure book-keeping, as we will see. We have an induction hypothesis
for the restricted IID. Namely, for |a : Args (eps gamma i) Ugg| we have
\begin{code}
ih : IndHyp (eps gamma i) Ugg C a
= (v : IndArg (eps gamma i) U a -> C (indIndex (eps gamma i) U a v)
(ind (eps gamma i) U a v)
\end{code}
We need, for |a' = rgArgs gamma Ugg i a|
\begin{code}
ih : IndHyp gamma Ugg C a'
= (v : IndArg gamma U a') -> C (indIndex gamma U a' v) (ind gamma U a' v)
\end{code}
Our intuition is that |eps| does not change the inductive occurrences in any
way, and indeed we can prove the following lemma:
\begin{lemma} \label{lem-eps-ind}
For any closed |gamma|, and |a : Args (eps gamma i) U| and |v : IndArg (eps
gamma i) U a| the following equalities hold definitionally.
\begin{code}
IndArg gamma U (rgArgs gamma U i a) = IndArg (eps gamma i) U a
indIndex gamma U (rgArgs gamma U i a) v = indIndex (eps gamma i) U a v
ind gamma U (rgArgs gamma U i a) v = ind (eps gamma i) U a v
IndHyp gamma U C (rgArgs gamma U i a) = IndHyp (eps gamma i) U C a
indHyp gamma U C g (rgArgs gamma U i a) = indHyp (eps gamma i) U C g a
\end{code}
\end{lemma}
%format lem_epsInd = "\ref{lem-eps-ind}"
\begin{proof}
The first three are proven by induction on |gamma|. The last two follows from the first three.
\end{proof}
That is, we can use the induction hypothesis we have as it is. Let us now try
to define the elimination rule. We are given
\begin{code}
C : (i : I) -> Ugg i -> Set
step : (a : Args gamma Ugg) -> IndHyp gamma Ugg C a ->
C (index gamma Ugg a) (introgg a)
i : I
u : Ugg i
\end{code}
and we have to prove |C i u|. To apply the restricted elimination rule
(|elimUreg|) we need an induction step |stepr| of type
\begin{code}
(i : I)(a : Args (eps gamma i) Ugg) -> IndHyp (eps gamma i) Ugg C a -> C i (intror i a)
\end{code}
As we have observed the induction hypothesis already has the right type, so we attempt to
define
\begin{code}
stepr i a ih = step (rgArgs gamma Ugg i a) ih
\end{code}
The type of |stepr i a ih| is |C (index gamma U ar) (intror (grArgs gamma U
ar))|, where |ar = rgArgs gamma Ugg i a|. Here, we would like the conversion of
a constructor argument from the restricted representation to a generalised
argument and back to be the definitional identity. It is easy to see that
this is not the case. For instance, in our |Even| example the argument to the
|evenZ'| constructor is a proof |p : zero == zero|. Converting to a generalised
argument we throw away the proof, and converting back we add a proof by
reflexivity. But |p| and |refl| are not definitionally equal. Fortunately they
are provably equal, so we can define the following substitution function:
\begin{code}
rgArgssubst : (gamma : OPg I)(U : I -> Set)
(C : (i : I) -> rArgs (eps gamma) U i -> Set)
(i : I)(a : rArgs (eps gamma) U i) ->
(C (index gamma U (rgArgs gamma U i a))
(grArgs gamma U (rgArgs gamma U i a))
) -> C i a
rgArgssubst (iota i) U C j < p, star > m =
elimId i (\ k q. C k < q, star >) m j p
rgArgssubst (delta A gamma) U C j < a, b > m =
rgArgssubst (gamma a) U (\ i c. C i < a, c >) j b m
rgArgssubst (delta H i gamma) U C j < g, b > m =
rgArgssubst gamma U (\ i c. C i < g, c >) j b m
\end{code}
The interesting case is the |iota|-case where we have to prove |C j |
given |C i | and |p : i == j|. This is proven using the elimination
rule, |elimId|, for the identity type. Armed with this substitution rule we can
define the elimination rule for a generalised IID:
\begin{code}
elimUgg C step i u = elimUreg C stepr i u
where
stepr i a ih = rgArgssubst gamma Ugg (\ i a. C i (intror i a))
i a (step (rgArgs gamma Ugg i a) ih)
\end{code}
\end{proof}
In our example the definition of the elimination rule is
\begin{code}
elim_Even : (C : (n : Nat) -> Even n -> Set) ->
C zero evenZ ->
( (n : Nat)(e : Even n) -> C n e ->
C (suc (suc n)) (evenSS n e)) ->
(n : Nat)(e : Even n) -> C n e
elim_Even C cz css n (evenZ' p) =
elimId zero (\ m q. C m (evenZ' q)) cz n p
elim_Even C cz css n (evenSS' m e p) =
elimId (suc (suc m)) (\ z q. C z (evenSS' m e q))
(css m e (elim_Even C cz css m e)) n p
\end{code}
To improve readability we present the rule using pattern matching and explicit
recursion rather than calling |elim_Even'|. The call to |rgArgssubst| is has
been reduced to identity proof eliminations.
\subsection{Computation rule}
So far we have shown that we can represent generalised IID as a restricted IID
and that the elimination rule is still valid. The only thing remaining is to
show that the computation rule is also valid. That is, that we get the same
definitional equalities for our representation as we would if we extended our
system with generalised IID.
\begin{theorem}
For the representation of generalised IID given above, and the encoding of
the elimination rule |elimUgg| the following computation rule holds
definitionally for closed |gamma|:
\begin{code}
elimUgg C step (index γ Ugg a) (introgg a) =
step a (indHyp γ Ugg C (elimUgg C step) a)
\end{code}
\end{theorem}
\begin{proof}
The key insight here is that the computation rule does not talk about arbitrary
elements of |Ugg|, but only those that have been constructed using the
introduction rule. This means that we do not have to satisfy any definitional
equalities for elements where the equality proof is not definitionally equal to
|refl|. So, the main step in the proof is to prove that |rgArgssubst| is the
definitional identity when the equality proof is |refl|, i.e. when the argument
is build using the |grArgs| function.
\begin{lemma} \label{lem-rgArgsubst}
For all closed |gamma|, and all |U|, |C|, |a : Args gamma U|, and
\begin{code}
h : C (index gamma U arg) (grArgs gamma U arg)
\end{code}
where
\begin{code}
ar = grArgs gamma U a
i = index gamma U a
arg = rgArgs gamma U i ar
\end{code}
it holds definitionally that
\begin{code}
rgArgssubst gamma U C i ar h = h
\end{code}
\end{lemma}
%format lem_rgArgsubst = "\ref{lem-rgArgsubst}"
\begin{proof}
By induction on |gamma|. In the |iota|-case we have to prove that
\begin{code}
elimId i C' h i refl = h
\end{code}
which is exactly the computation rule for the identity type.
\end{proof}
The final lemma we need before proving the computation rule is that starting with
a generalised constructor argument, converting it to a restricted one, and then
back is the definitional identity. This amounts to adding a reflexivity proof
and then removing it, so it is easy to see that this should be true.
\begin{lemma} \label{lem-arg-is-a}
For all closed |gamma|, and all |a : Args gamma U| it holds definitionally that
> rgArgs gamma U (index gamma U a) (grArgs gamma U a) = a
\end{lemma}
%format lem_argIsa = "\ref{lem-arg-is-a}"
\begin{proof}
By induction on |gamma|.
\end{proof}
Now we are ready to prove the computation rule. Take |a : Args gamma Ugg| and let
\begin{code}
i = index gamma Ugg a
ar = grArgs gamma Ugg a
arg = rgArgs gamma Ugg i ar
\end{code}
we have
\begin{code}
elimUgg C step (index gamma Ugg a) (introgg a)
= elimUgg C step i (introgg a)
= {definition of_ elimUgg and introrg}
elimUreg C stepr i (introreg i ar)
= {computation rule for Ureg}
stepr i ar (indHyp (eps gamma i) Ugg C (elimUgg C step) ar)
= {definition of_ stepr}
rgArgssubst gamma Ugg (\ i a. C i (intror i ar)) i ar
(step arg (indHyp (eps gamma i) Ugg C (elimUgg C step) ar))
= {Lemma lem_rgArgsubst}
step arg (indHyp (eps gamma i) Ugg C (elimUgg C step) ar)
= {Lemma lem_epsInd}
step arg (indHyp gamma Ugg C (elimUgg C step) arg)
= {Lemma lem_argIsa}
step a (indHyp gamma Ugg C (elimUgg C step) a)
\end{code}
\end{proof}
In the example of |Even| the proofs of the computation rules are
\begin{code}
elim_Even C cz css zero evenZ
= elim_Even C cz css zero (evenZ' refl)
= elimId zero (\ m q. C m (evenZ' q)) cz zero refl
= cz
elim_Even C cz css (suc (suc m)) (evenSS m p)
= elim_Even C cz css (suc (suc m)) (evenSS' m p refl)
= elimId (suc (suc m)) (\ z q. C z (evenSS' m e q))
(css m e (elim_Even C cz css m e)) (suc (suc m)) refl
= css m e (elim_Even C cz css m e)
\end{code}
The important steps are the appeals to the computation rule for the identity
type.
This concludes the proof that we can faithfully represent generalised IID in
the theory of restricted IID and the intensional identity type.
\section{Notes on the formal proof} \label{sec-formal}
One approach to formalise our result would be to do a deep embedding,
formalising the logical framework and the theory of restricted IID in Agda, and
prove our theorems for this formalisation. This would be a big undertaking,
however, so we chose a more light-weight approach. In Agda we can define the
rules for restricted IID directly, that is, we can define restricted IID as a
datatype in Agda and get the introduction, elimination, and computation rules
for free. Using this definition of restricted IID we can then prove the
formation, introduction, and elimination rules for the representation of
generalised IID.
When we want to prove the computation rule, however, there is a problem. The
computation rule talks about definitional equality and in Agda we cannot reason
about the internal definitional equality. To solve this problem we axiomatised
the definitional equality of the logical framework. That is, for each |A, B :
Set| we introduce a constant
\begin{code}
! = ! : A -> B -> Set
\end{code}
and axioms corresponding to the conversion rules of the logical framework. For
instance, for all |f|, |g|, |x|, and |y|
\begin{code}
app : (f = g) -> (x = y) -> (f x = g y)
\end{code}
In this axiom, we can see why the definitional equality has type |A -> B ->
Set|: since |f| and |g| can be dependent functions, |f x| and |g y| can have
different types.
With this approach one has to be careful with induction. For instance, if one
proves by induction on |n| that |n + zero = n|, this only holds definitionally
for closed |n|. In our case the only induction is over codes |gamma| and we
always assume |gamma| to be closed. The formalisation can be downloaded from
the author's webpage~\cite{norell:iird-formal}.
\section{Conclusions} \label{sec-concl}
We have shown that the theory of generalised indexed inductive definitions can
be interpreted in the theory of restricted indexed inductive definitions
extended with an intensional identity type. The informal proof presented here
has been formalised in Agda using a light-weight approach where Agda is used
both for the object language and the meta language.
This result gives way of adding generalised IID to theories with only
restricted IID, such as Agda, without having to extend the meta-theory.
\bibliographystyle{abbrv}
\bibliography{../../../../bib/pmgrefs,iird}
\end{document}
% vim: et