Theorem: List.all_in_map_fst_groupByKey_of_sublist (Table/BuiltinExtensions.lean)

State before:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ map Prod.fst (groupByKey ((k, v) :: xs))
⊢ x ∈ map Prod.fst (groupByKey ((k, v) :: ys))
Tactic:
simp only [groupByKey]
State after:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ map Prod.fst (groupByKey ((k, v) :: xs))
⊢ x ∈ map Prod.fst ((k, v :: (matchKey ys k).fst) :: groupByKey (matchKey ys k).snd)

State before:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ map Prod.fst (groupByKey ((k, v) :: xs))
⊢ x ∈ map Prod.fst ((k, v :: (matchKey ys k).fst) :: groupByKey (matchKey ys k).snd)
Tactic:
simp only [map]
State after:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ map Prod.fst (groupByKey ((k, v) :: xs))
⊢ x ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)

State before:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ map Prod.fst (groupByKey ((k, v) :: xs))
⊢ x ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)
Tactic:
simp only [groupByKey] at hx
State after:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ map Prod.fst ((k, v :: (matchKey xs k).fst) :: groupByKey (matchKey xs k).snd)
⊢ x ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)

State before:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ map Prod.fst ((k, v :: (matchKey xs k).fst) :: groupByKey (matchKey xs k).snd)
⊢ x ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)
Tactic:
simp only [map] at hx
State after:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ k :: map Prod.fst (groupByKey (matchKey xs k).snd)
⊢ x ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)

State before:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
hx : x ∈ k :: map Prod.fst (groupByKey (matchKey xs k).snd)
⊢ x ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)
Tactic:
cases hx with
| head => constructor
| tail _ htail =>
  apply Mem.tail
  have : (matchKey xs k).snd <+ (matchKey ys k).snd :=
    matchKey_snd_sublist_of_sublist _ _ _ hsubl
  have hterm := matchKey_length_lt k ys
  apply all_in_map_fst_groupByKey_of_sublist this
  assumption
State after:
no goals

State before:
case head
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
⊢ k ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)
Tactic:
constructor
State after:
no goals

State before:
case tail
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
⊢ x ∈ k :: map Prod.fst (groupByKey (matchKey ys k).snd)
Tactic:
apply Mem.tail
State after:
case tail.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
⊢ Mem x (map Prod.fst (groupByKey (matchKey ys k).snd))

State before:
case tail.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
⊢ Mem x (map Prod.fst (groupByKey (matchKey ys k).snd))
Tactic:
have : (matchKey xs k).snd <+ (matchKey ys k).snd :=
  matchKey_snd_sublist_of_sublist _ _ _ hsubl
State after:
case tail.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
this : (matchKey xs k).snd <+ (matchKey ys k).snd
⊢ Mem x (map Prod.fst (groupByKey (matchKey ys k).snd))

State before:
case tail.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
this : (matchKey xs k).snd <+ (matchKey ys k).snd
⊢ Mem x (map Prod.fst (groupByKey (matchKey ys k).snd))
Tactic:
have hterm := matchKey_length_lt k ys
State after:
case tail.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
this : (matchKey xs k).snd <+ (matchKey ys k).snd
hterm : length (matchKey ys k).snd < Nat.succ (length ys)
⊢ Mem x (map Prod.fst (groupByKey (matchKey ys k).snd))

State before:
case tail.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
this : (matchKey xs k).snd <+ (matchKey ys k).snd
hterm : length (matchKey ys k).snd < Nat.succ (length ys)
⊢ Mem x (map Prod.fst (groupByKey (matchKey ys k).snd))
Tactic:
apply all_in_map_fst_groupByKey_of_sublist this
State after:
case tail.a.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
this : (matchKey xs k).snd <+ (matchKey ys k).snd
hterm : length (matchKey ys k).snd < Nat.succ (length ys)
⊢ x ∈ map Prod.fst (groupByKey (matchKey xs k).snd)

State before:
case tail.a.a
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
xs✝ ys✝ xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x : κ
htail : Mem x (map Prod.fst (groupByKey (matchKey xs k).snd))
this : (matchKey xs k).snd <+ (matchKey ys k).snd
hterm : length (matchKey ys k).snd < Nat.succ (length ys)
⊢ x ∈ map Prod.fst (groupByKey (matchKey xs k).snd)
Tactic:
assumption
State after:
no goals

State before:
κ : Type u_1
ν : Type u_2
inst✝ : DecidableEq κ
_x✝ : (xs : List (κ × ν)) ×' (ys : List (κ × ν)) ×' (_ : xs <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs)
a✝⁵ :
  ∀ (y : (xs : List (κ × ν)) ×' (ys : List (κ × ν)) ×' (_ : xs <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs)),
    (invImage
            (fun a =>
              PSigma.casesOn a fun xs snd =>
                PSigma.casesOn snd fun ys snd =>
                  PSigma.casesOn snd fun hsubl snd => PSigma.casesOn snd fun x snd => length ys)
            instWellFoundedRelation).1
        y _x✝ →
      y.2.2.2.1 ∈ map Prod.fst (groupByKey y.2.1)
xs✝ : List (κ × ν)
ys✝¹ : (ys : List (κ × ν)) ×' (_ : xs✝ <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs✝)
a✝⁴ :
  ∀ (y : (xs : List (κ × ν)) ×' (ys : List (κ × ν)) ×' (_ : xs <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs)),
    (invImage
            (fun a =>
              PSigma.casesOn a fun xs snd =>
                PSigma.casesOn snd fun ys snd =>
                  PSigma.casesOn snd fun hsubl snd => PSigma.casesOn snd fun x snd => length ys)
            instWellFoundedRelation).1
        y { fst := xs✝, snd := ys✝¹ } →
      y.2.2.2.1 ∈ map Prod.fst (groupByKey y.2.1)
ys✝ : List (κ × ν)
x✝⁶ : (_ : xs✝ <+ ys✝) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs✝)
a✝³ :
  ∀ (y : (xs : List (κ × ν)) ×' (ys : List (κ × ν)) ×' (_ : xs <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs)),
    (invImage
            (fun a =>
              PSigma.casesOn a fun xs snd =>
                PSigma.casesOn snd fun ys snd =>
                  PSigma.casesOn snd fun hsubl snd => PSigma.casesOn snd fun x snd => length ys)
            instWellFoundedRelation).1
        y { fst := xs✝, snd := { fst := ys✝, snd := x✝⁶ } } →
      y.2.2.2.1 ∈ map Prod.fst (groupByKey y.2.1)
x✝⁵ : xs✝ <+ ys✝
x✝⁴ : (x : κ) ×' x ∈ map Prod.fst (groupByKey xs✝)
a✝² :
  ∀ (y : (xs : List (κ × ν)) ×' (ys : List (κ × ν)) ×' (_ : xs <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs)),
    (invImage
            (fun a =>
              PSigma.casesOn a fun xs snd =>
                PSigma.casesOn snd fun ys snd =>
                  PSigma.casesOn snd fun hsubl snd => PSigma.casesOn snd fun x snd => length ys)
            instWellFoundedRelation).1
        y { fst := xs✝, snd := { fst := ys✝, snd := { fst := x✝⁵, snd := x✝⁴ } } } →
      y.2.2.2.1 ∈ map Prod.fst (groupByKey y.2.1)
x✝³ : κ
x✝² : x✝³ ∈ map Prod.fst (groupByKey xs✝)
a✝¹ :
  ∀ (y : (xs : List (κ × ν)) ×' (ys : List (κ × ν)) ×' (_ : xs <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs)),
    (invImage
            (fun a =>
              PSigma.casesOn a fun xs snd =>
                PSigma.casesOn snd fun ys snd =>
                  PSigma.casesOn snd fun hsubl snd => PSigma.casesOn snd fun x snd => length ys)
            instWellFoundedRelation).1
        y { fst := xs✝, snd := { fst := ys✝, snd := { fst := x✝⁵, snd := { fst := x✝³, snd := x✝² } } } } →
      y.2.2.2.1 ∈ map Prod.fst (groupByKey y.2.1)
xs ys : List (κ × ν)
k : κ
v : ν
hsubl : xs <+ ys
x✝¹ : κ
hx : x✝¹ ∈ map Prod.fst (groupByKey ((k, v) :: xs))
x✝ :
  ∀ (y : (xs : List (κ × ν)) ×' (ys : List (κ × ν)) ×' (_ : xs <+ ys) ×' (x : κ) ×' x ∈ map Prod.fst (groupByKey xs)),
    (invImage
            (fun a =>
              PSigma.casesOn a fun xs snd =>
                PSigma.casesOn snd fun ys snd =>
                  PSigma.casesOn snd fun hsubl snd => PSigma.casesOn snd fun x snd => length ys)
            instWellFoundedRelation).1
        y
        { fst := (k, v) :: xs,
          snd :=
            { fst := (k, v) :: ys,
              snd := { fst := (_ : (k, v) :: xs <+ (k, v) :: ys), snd := { fst := x✝¹, snd := hx } } } } →
      y.2.2.2.1 ∈ map Prod.fst (groupByKey y.2.1)
b✝ : κ
as✝ : List κ
htail✝ : Mem x✝¹ as✝
h✝¹ : k :: map Prod.fst (groupByKey (matchKey xs k).snd) = b✝ :: as✝
head_eq✝ : k = b✝
tail_eq✝ : map Prod.fst (groupByKey (matchKey xs k).snd) = as✝
htail : Mem x✝¹ (map Prod.fst (groupByKey (matchKey xs k).snd))
h✝ :
  HEq
    (_ :
      x✝¹ ∈
        map Prod.fst
          (let_fun h_help := (_ : length (matchKey xs k).snd < Nat.succ (length xs));
          let fms := matchKey xs k;
          (k, v :: fms.fst) :: groupByKey fms.snd))
    (_ : Mem x✝¹ (k :: map Prod.fst (groupByKey (matchKey xs k).snd)))
this : (matchKey xs k).snd <+ (matchKey ys k).snd
hterm : length (matchKey ys k).snd < Nat.succ (length ys)
x : κ
a✝ : x ∈ map Prod.fst (groupByKey (matchKey xs k).snd)
⊢ (invImage
        (fun a =>
          PSigma.casesOn a fun xs snd =>
            PSigma.casesOn snd fun ys snd =>
              PSigma.casesOn snd fun hsubl snd => PSigma.casesOn snd fun x snd => length ys)
        instWellFoundedRelation).1
    { fst := (matchKey xs k).snd,
      snd := { fst := (matchKey ys k).snd, snd := { fst := this, snd := { fst := x, snd := a✝ } } } }
    { fst := (k, v) :: xs,
      snd :=
        { fst := (k, v) :: ys,
          snd := { fst := (_ : (k, v) :: xs <+ (k, v) :: ys), snd := { fst := x✝¹, snd := hx } } } }
Tactic:
assumption
State after:
no goals