Theorem: LO.FirstOrder.Arith.Model.seqMap_graph (Arithmetization/ISigmaOne/HFS/Seq.lean)

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H : Seq s✝
t s : M
⊢ t = seqMap hf s →
    (Seq s →
        Seq t ∧ (∃ l ≤ 2 * s, l = lh s ∧ l = lh t) ∧ ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t) ∧
      (¬Seq s → t = 0)
Tactic:
rintro rfl
State after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H : Seq s✝
s : M
⊢ (Seq s →
      Seq (seqMap hf s) ∧
        (∃ l ≤ 2 * s, l = lh s ∧ l = lh (seqMap hf s)) ∧
          ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s) ∧
    (¬Seq s → seqMap hf s = 0)

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H : Seq s✝
s : M
⊢ (Seq s →
      Seq (seqMap hf s) ∧
        (∃ l ≤ 2 * s, l = lh s ∧ l = lh (seqMap hf s)) ∧
          ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s) ∧
    (¬Seq s → seqMap hf s = 0)
Tactic:
by_cases H : Seq s <;> simp only [H, Seq.seqMap, lt_succ_iff_le, Seq.seqMap_lh_eq, and_self,
  exists_eq_right, lh_bound, true_and, forall_true_left, not_true_eq_false, IsEmpty.forall_iff, and_true,
  not_false_eq_true, H, seqMap_spec_of_not_seq, forall_true_left]
State after:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
s : M
H : Seq s
⊢ ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s

State before:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
s : M
H : Seq s
⊢ ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s
Tactic:
intro i _ x _ hix
State after:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
s : M
H : Seq s
i : M
a✝¹ : i < s
x : M
a✝ : x < s
hix : ⟪i, x⟫ ∈ s
⊢ ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s

State before:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
s : M
H : Seq s
i : M
a✝¹ : i < s
x : M
a✝ : x < s
hix : ⟪i, x⟫ ∈ s
⊢ ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s
Tactic:
have : ⟪i, f x⟫ ∈ seqMap hf s := H.seqMap_spec hix
State after:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
s : M
H : Seq s
i : M
a✝¹ : i < s
x : M
a✝ : x < s
hix : ⟪i, x⟫ ∈ s
this : ⟪i, f x⟫ ∈ seqMap hf s
⊢ ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s

State before:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
s : M
H : Seq s
i : M
a✝¹ : i < s
x : M
a✝ : x < s
hix : ⟪i, x⟫ ∈ s
this : ⟪i, f x⟫ ∈ seqMap hf s
⊢ ∃ y < seqMap hf s, y = f x ∧ ⟪i, y⟫ ∈ seqMap hf s
Tactic:
exact ⟨f x, lt_of_mem_rng this, rfl, this⟩
State after:
no goals

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H : Seq s✝
t s : M
⊢ (Seq s → Seq t ∧ (∃ l ≤ 2 * s, l = lh s ∧ l = lh t) ∧ ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t) ∧
      (¬Seq s → t = 0) →
    t = seqMap hf s
Tactic:
by_cases H : Seq s <;>
  simp only [H, lt_succ_iff_le, exists_eq_right_right, forall_true_left,
    not_true_eq_false, IsEmpty.forall_iff, and_true, and_imp]
State after:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
⊢ Seq t → lh t ≤ 2 * s → lh t = lh s → (∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t) → t = seqMap hf s

case neg
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : ¬Seq s
⊢ (¬False → t = 0) → t = seqMap hf s

State before:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
⊢ Seq t → lh t ≤ 2 * s → lh t = lh s → (∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t) → t = seqMap hf s

case neg
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : ¬Seq s
⊢ (¬False → t = 0) → t = seqMap hf s
Tactic:
intro Ht _ hl h
State after:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
⊢ t = seqMap hf s

case neg
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : ¬Seq s
⊢ (¬False → t = 0) → t = seqMap hf s

State before:
case pos
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
⊢ t = seqMap hf s

case neg
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : ¬Seq s
⊢ (¬False → t = 0) → t = seqMap hf s
Tactic:
apply Classical.extendedChoose!_uniq
State after:
case pos.hpx
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
⊢ Seq s

case pos.hrx
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
⊢ Seq t ∧ lh t = lh s ∧ ∀ (i x : M), ⟪i, x⟫ ∈ s → ⟪i, f x⟫ ∈ t

case neg
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : ¬Seq s
⊢ (¬False → t = 0) → t = seqMap hf s

State before:
case pos.hpx
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
⊢ Seq s
Tactic:
exact H
State after:
no goals

State before:
case pos.hrx
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
⊢ Seq t ∧ lh t = lh s ∧ ∀ (i x : M), ⟪i, x⟫ ∈ s → ⟪i, f x⟫ ∈ t
Tactic:
exact ⟨Ht, hl, by intro i x hi; rcases h i (lt_of_mem_dom hi) x (lt_of_mem_rng hi) hi with ⟨_, _, rfl, h⟩; exact h⟩
State after:
no goals

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
⊢ ∀ (i x : M), ⟪i, x⟫ ∈ s → ⟪i, f x⟫ ∈ t
Tactic:
intro i x hi
State after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
i x : M
hi : ⟪i, x⟫ ∈ s
⊢ ⟪i, f x⟫ ∈ t

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
i x : M
hi : ⟪i, x⟫ ∈ s
⊢ ⟪i, f x⟫ ∈ t
Tactic:
rcases h i (lt_of_mem_dom hi) x (lt_of_mem_rng hi) hi with ⟨_, _, rfl, h⟩
State after:
case intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h✝ : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
i x : M
hi : ⟪i, x⟫ ∈ s
left✝ : f x < t
h : ⟪i, f x⟫ ∈ t
⊢ ⟪i, f x⟫ ∈ t

State before:
case intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : Seq s
Ht : Seq t
a✝ : lh t ≤ 2 * s
hl : lh t = lh s
h✝ : ∀ i < s, ∀ x < s, ⟪i, x⟫ ∈ s → ∃ y < t, y = f x ∧ ⟪i, y⟫ ∈ t
i x : M
hi : ⟪i, x⟫ ∈ s
left✝ : f x < t
h : ⟪i, f x⟫ ∈ t
⊢ ⟪i, f x⟫ ∈ t
Tactic:
exact h
State after:
no goals

State before:
case neg
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
f : M → M
hf : 𝚺₁-Function₁ f
s✝ : M
H✝ : Seq s✝
t s : M
H : ¬Seq s
⊢ (¬False → t = 0) → t = seqMap hf s
Tactic:
simp [H]
State after:
no goals