CODEWITHSUNDEEP
isabelle
Denis
Denis

Reputation: 1271

How to replace existentially quantified variable?

Here is a simple type system:

datatype type =
  VoidType
| IntegerType
| RealType
| StringType

datatype val =
  VoidVal
| IntegerVal int
| RealVal real
| StringVal string

fun type_of :: "val ⇒ type" where
  "type_of (VoidVal) = VoidType"
| "type_of (IntegerVal _) = IntegerType"
| "type_of (RealVal _) = RealType"
| "type_of (StringVal _) = StringType"

with type conformance relation:

inductive less_type :: "type ⇒ type ⇒ bool" (infix "<" 65) where
  "IntegerType < RealType"

Integer values can be casted to corresponding real values:

inductive cast :: "val ⇒ val ⇒ bool" where
  "cast (IntegerVal x) (RealVal x)"

I'm trying to prove the following lemma. If type of a variable x conforms to RealType, then there exists a value y with type RealType and x can be casted to y.

lemma is_castable_to_real:
  "type_of x < RealType ⟹ ∃y. type_of y = RealType ∧ cast x y"
  apply (rule exI[of _ "RealVal v"])

I can prove the generic lemma using cases tactics:

lemma is_castable:
  "type_of x < τ ⟹ ∃y. type_of y = τ ∧ cast x y"
  by (cases x; cases τ; auto simp add: less_type.simps cast.simps)

But I'm trying to understand how to treat existential quantifiers in lemmas. So I'm trying to provide a concrete example RealVal v for y:

type_of x < RealType ⟹ ∃v. type_of (RealVal v) = RealType ∧ cast x (RealVal v)

The problem is that I get the following proposition instead:

 type_of x < RealType ⟹ type_of (RealVal v) = RealType ∧ cast x (RealVal v)

What is the kind of variable v? Is it universally quantified variable? How to make it existentially quantified one?

Upvotes: 0

Views: 85

Answers (1)

Peter Zeller
Peter Zeller

Reputation: 2296

To prove an existential, you can give a concrete example. In your case, this example can be derived from the assumption of the lemma.

lemma is_castable_to_real:
assumes subtype_of_real: "type_of x < RealType"
shows "∃y. type_of y = RealType ∧ cast x y"
proof -
  have "type_of x = IntegerType"
    using subtype_of_real less_type.cases by blast

  from this obtain i where x_def: "x = IntegerVal i"
    by (cases x, auto)

  (* prove it for concrete example (RealVal i) *)
  have "type_of (RealVal i) = RealType ∧ cast x (RealVal i)"
    by (auto simp add: x_def cast.intros)

  (* From the concrete example, the existential statement follows: *)
  thus "∃y. type_of y = RealType ∧ cast x y" ..
qed

If you just use v before obtaining or defining it somehow, the value will be similar to undefined. It has the correct type, but you do not know anything about it.

If you start the proof without the dash (-) Isabelle will use the default tactic and you would get the subgoal type_of ?y = RealType ∧ cast x ?y. Here ?y is a schematic variable and you can later provide any value that was already available before starting the proof. Maybe this is the kind of variable you get for v, but it is still not clear how you got to the last line in your question.

Upvotes: 1

Related Questions