# Re: [isabelle] Parameterized Types?

```Hi Robert,

On Tuesday 28 March 2006 14:28, Robert Lamar wrote:
> My only question for the moment arises from my attempt to prove a lemma,
> that the sum of two elements of a quotient is in the quotient.  I am unable
> to get past a certain step, which I isolate in the following lemma:
>
>   lemma "EX s. S = coset I s ==> EX s. S = {i + s | i. i \<in> I}"
>   proof -
>     assume "EX s. S = coset I s"
>     from this coset_def [of I s] show "EX s. S = {i + s | i. i \<in> I}"
>     by simp
>   qed
>
> I have defined
>
>   constdefs
>     coset ::  "[('a::ring) set, 'a] => 'a set"
>               "coset I a == {i + a | i. i \<in> I}"
>

The problem with this proof is caused by your usage of the "of" theorem
attribute. Specifically, coset_def [of I s] instantiates coset_def with the
free variables "I" and "s" (on my system Proof General renders these in
blue), where the term you want to replace uses "s" as a bound variable
(rendered in green). Replace this with coset_def [of I] and the proof works.

> and would like to think that it is a straightforward matter of
> substitution.  However, I know that section 5.11 of the tutorial makes it
> clear that reasoning about existential operators can be very tricky.  Am I
> missing something crucial?
>
> Robert Lamar

When you instantiate coset_def with free variables "I" and "s", you get an
assumption that is too weak, since it only asserts the equality for a single
value of "s". For simp to perform a substitution under a quantifier, on a
term containing bound variables, the equality needs to hold for all possible
values of the bound variables. Leaving a variable uninstantiated has the
effect of a universal quantification over that variable, and simp is able to
match it against a bound variable.

It appears that [of I] is still necessary to instantiate the free type
variable in coset_def. Apparently, leaving a type variable uninstantiated
does not have the same effect as an uninstantiated term variable, as far as
simp is concerned; simp cannot match the types and it fails.

As a simpler alternative, you can give coset_def as an argument to simp or
unfold, which avoids the problems with instantiating type variables:

lemma "EX s. S = coset I s ==> EX s. S = {i + s | i. i \<in> I}"
proof -
assume "EX s. S = coset I s"
then show "EX s. S = {i + s | i. i \<in> I}"
by (unfold coset_def)
qed

- Brian

```

This archive was generated by a fusion of Pipermail (Mailman edition) and MHonArc.