Theorem: Digraph.Walk.map_injective_of_injective (GraphProjects/DigraphConnectivity.lean)

State before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝ v✝ u' v' : V
p : Walk G u✝ v✝
f : G →g G'
hinj : Injective ↑f
u v : V
⊢ Injective (Walk.map f)
Tactic:
intro p p' h
State after:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝ v✝ u' v' : V
p✝ : Walk G u✝ v✝
f : G →g G'
hinj : Injective ↑f
u v : V
p p' : Walk G u v
h : Walk.map f p = Walk.map f p'
⊢ p = p'

State before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝ u' v' : V
p : Walk G u✝¹ v✝
f : G →g G'
hinj : Injective ↑f
u v u✝ : V
p' : Walk G u✝ u✝
h : Walk.map f nil = Walk.map f p'
⊢ nil = p'
Tactic:
cases p'
State after:
case nil.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝ u' v' : V
p : Walk G u✝¹ v✝
f : G →g G'
hinj : Injective ↑f
u v u✝ : V
h : Walk.map f nil = Walk.map f nil
⊢ nil = nil

case nil.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ u✝
h : Walk.map f nil = Walk.map f (cons h✝ p✝)
⊢ nil = cons h✝ p✝

State before:
case nil.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝ u' v' : V
p : Walk G u✝¹ v✝
f : G →g G'
hinj : Injective ↑f
u v u✝ : V
h : Walk.map f nil = Walk.map f nil
⊢ nil = nil
Tactic:
rfl
State after:
no goals

State before:
case nil.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ u✝
h : Walk.map f nil = Walk.map f (cons h✝ p✝)
⊢ nil = cons h✝ p✝
Tactic:
simp at h
State after:
no goals

State before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : ∀ ⦃p' : Walk G v✝ w✝⦄, Walk.map f p✝ = Walk.map f p' → p✝ = p'
p' : Walk G u✝ w✝
h : Walk.map f (cons h✝ p✝) = Walk.map f p'
⊢ cons h✝ p✝ = p'
Tactic:
cases p' with
| nil => simp at h
| cons _ _ =>
  simp only [map_cons, cons.injEq] at h
  cases hinj h.1
  simp only [cons.injEq, heq_iff_eq, true_and_iff]
  apply ih
  simpa using h.2
State after:
no goals

State before:
case cons.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ u✝
ih : ∀ ⦃p' : Walk G v✝ u✝⦄, Walk.map f p✝ = Walk.map f p' → p✝ = p'
h : Walk.map f (cons h✝ p✝) = Walk.map f nil
⊢ cons h✝ p✝ = nil
Tactic:
simp at h
State after:
no goals

State before:
case cons.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝² u' v' : V
p : Walk G u✝¹ v✝²
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝¹ w✝ : V
h✝¹ : G.Adj u✝ v✝¹
p✝¹ : Walk G v✝¹ w✝
ih : ∀ ⦃p' : Walk G v✝¹ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : Walk.map f (cons h✝¹ p✝¹) = Walk.map f (cons h✝ p✝)
⊢ cons h✝¹ p✝¹ = cons h✝ p✝
Tactic:
simp only [map_cons, cons.injEq] at h
State after:
case cons.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝² u' v' : V
p : Walk G u✝¹ v✝²
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝¹ w✝ : V
h✝¹ : G.Adj u✝ v✝¹
p✝¹ : Walk G v✝¹ w✝
ih : ∀ ⦃p' : Walk G v✝¹ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝¹ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ cons h✝¹ p✝¹ = cons h✝ p✝

State before:
case cons.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝² u' v' : V
p : Walk G u✝¹ v✝²
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝¹ w✝ : V
h✝¹ : G.Adj u✝ v✝¹
p✝¹ : Walk G v✝¹ w✝
ih : ∀ ⦃p' : Walk G v✝¹ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝¹ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ cons h✝¹ p✝¹ = cons h✝ p✝
Tactic:
cases hinj h.1
State after:
case cons.cons.refl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ ⦃p' : Walk G v✝ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ cons h✝¹ p✝¹ = cons h✝ p✝

State before:
case cons.cons.refl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ ⦃p' : Walk G v✝ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ cons h✝¹ p✝¹ = cons h✝ p✝
Tactic:
simp only [cons.injEq, heq_iff_eq, true_and_iff]
State after:
case cons.cons.refl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ ⦃p' : Walk G v✝ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ p✝¹ = p✝

State before:
case cons.cons.refl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ ⦃p' : Walk G v✝ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ p✝¹ = p✝
Tactic:
apply ih
State after:
case cons.cons.refl.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ ⦃p' : Walk G v✝ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ Walk.map f p✝¹ = Walk.map f p✝

State before:
case cons.cons.refl.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ ⦃p' : Walk G v✝ w✝⦄, Walk.map f p✝¹ = Walk.map f p' → p✝¹ = p'
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : ↑f v✝ = ↑f v✝ ∧ HEq (Walk.map f p✝¹) (Walk.map f p✝)
⊢ Walk.map f p✝¹ = Walk.map f p✝
Tactic:
simpa using h.2
State after:
no goals