Zulip Chat Archive
Stream: lean4
Topic: how to deal with "motive / result is not type correct"?
Jan-Mirko Otter (Oct 14 2022 at 14:19):
Hi,
I often find myself in the situation that many useful tactics fail to work if there are dependent types involved:
conv
refuses to select arguments if there are dependenciesrw
,generalize
,cases
... do not work either
I understand why; if I just naively replace some expressions with some equal (but not defeq) expressions, some types which depend on it may not be definitional equal to what they are suppossed to be. In many cases, I manage to use dependent elimination, but not always.
Consider the following simple example: I have a filtered list, and I want to prove that getting something out of the filtered list is the same as getting something (possible at a different index) from the original list:
theorem get_from_filtered {T : Type u} (l : List T) (pred : T -> Bool)
(idx : Fin (l.filter pred).length)
: ∃ idx' : Fin l.length, (l.filter pred).get idx = l.get idx' :=by
induction l
. have : idx.val < 0 :=idx.isLt
contradiction
. rename_i head tail IH
simp only [List.filter]
-- how to continue from here?
cases pred head -- does not work, result is not type correct
sorry
Intuitively, the rest of the proof is clear. For example, if pred head
is false and idx.val > 0
, I can use the induction hypothesis.
However, I fail to simplify List.filter pred (head :: tail)
given the value of pred head
.
Do you have any tips how to continue here?
Last updated: Dec 20 2023 at 11:08 UTC