Zulip Chat Archive
Stream: lean4
Topic: trans in index bound proof
Jun Yoshida (Oct 20 2023 at 09:09):
When I index-access to List
/Array
, it is frustrating the following causes errors:
example (x : List Nat) (i : Nat) (hi : i < x.length) : Nat :=
-- Both arguments of `trans` cause errors.
x[i-1]'(trans i.pred_le hi)
I want to know why trans
doesn't work here.
From the error message above, it seems that trans
cannot infer its implicit arguments correctly.
So I next tried the following:
example (x : List Nat) (i : Nat) (hi : i < x.length) : Nat :=
-- Only `i.pred_le` causes an error.
x[i-1]'(trans (r:=LE.le) i.pred_le hi)
/-
The error message says
> application type mismatch
> trans (Nat.pred_le i)
> argument
> Nat.pred_le i
> has type
> Nat.pred i ≤ i : Prop
> but is expected to have type
> x ≤ ?m.2258 : Prop
-/
example (x : List Nat) (i : Nat) (hi : i < x.length) : Nat :=
-- The same errors as in the case without `s` specified.
x[i-1]'(trans (s:=LT.lt) i.pred_le hi)
example (x : List Nat) (i : Nat) (hi : i < x.length) : Nat :=
-- No error
x[i-1]'(trans (t:=LT.lt) i.pred_le hi)
Seeing the result, I completely got lost.
Why on earth does the elaborator think r:=LE.le (List Nat)
is the appropriate choice when r:=LE.le
is given?
I am not sure either why the last one compiles while it doesn't without t
specified; isn't the target binary relation t
of trans
determined by GetElem
instance of List
?
I am glad if you could give me a hint.
Eric Rodriguez (Oct 20 2023 at 09:28):
Note that hi
is not a le
statement, but a lt
statement. I think there is other issues in here, but this is one issue
Eric Rodriguez (Oct 20 2023 at 09:33):
Here's a way you could do it with mathlib:
import Mathlib.Init.Data.Nat.Lemmas
import Mathlib.Order.Basic
example (x : List Nat) (i : Nat) (hi : i < x.length) : Nat := x[i-1]'((i.pred_le).trans_lt hi)
but it does seem quite annoying to do in basic Lean
Jun Yoshida (Oct 20 2023 at 10:40):
Eric Rodriguez said:
Note that
hi
is not ale
statement, but alt
statement. I think there is other issues in here, but this is one issue
Thank you for commenting, but I can't see what you mean. Note that Trans
is a heterogeneous transitivity, and actually it can use docs#Nat.instTransNatLeInstLENatLtInstLTNat .
In fact, trans
uses it in my example if (t:=LT.lt)
is supplied. One of my questions is why we need to specify it.
Jun Yoshida (Oct 20 2023 at 10:44):
I mean, the following works:
example (x : List Nat) (i : Nat) (hi : i < x.length) : Nat :=
have : i-1 < x.length := trans i.pred_le hi
x[i-1]'this -- or just `x[i-1]`
Jun Yoshida (Oct 20 2023 at 11:09):
Oh, I was a bit surprised knowing the code just above works without type specification in have
-clause.
Jun Yoshida (Oct 20 2023 at 11:19):
Hmm, this even works:
example (x : List Nat) (i : Nat) (hi : i < x.length) : Nat :=
x[i-1]'(trans i.pred_le hi : _)
Eric Rodriguez (Oct 20 2023 at 11:28):
Oh I see! Apologies, this was based on old Lean3 knowledge, I didn't know that this worked automatically. It seems to be an expected type issue, I now agree this is bizarre!
Last updated: Dec 20 2023 at 11:08 UTC