Theorem: LO.FirstOrder.Arith.Model.PR.Construction.cseq_iff (Arithmetization/ISigmaOne/HFS/PRF.lean)

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
⊢ c.CSeq v s →
    Seq s ∧
      (∃ z < s, z = c.zero v ∧ ⟪0, z⟫ ∈ s) ∧
        ∀ i < 2 * s,
          (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
Tactic:
rintro ⟨Hs, hz, hs⟩
State after:
case intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
⊢ Seq s ∧
    (∃ z < s, z = c.zero v ∧ ⟪0, z⟫ ∈ s) ∧
      ∀ i < 2 * s,
        (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s

State before:
case intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
⊢ Seq s ∧
    (∃ z < s, z = c.zero v ∧ ⟪0, z⟫ ∈ s) ∧
      ∀ i < 2 * s,
        (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
Tactic:
exact ⟨Hs, ⟨c.zero v, lt_of_mem_rng hz, rfl, hz⟩, fun i _ hi z _ hiz ↦
⟨c.succ v i z, by
  have := hs i (by rcases hi with ⟨l, _, rfl, hl⟩; simp [lt_tsub_iff_right, hl]) z hiz
  exact ⟨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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
i : M
x✝¹ : i < 2 * s
hi : ∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l
z : M
x✝ : z < s
hiz : ⟪i, z⟫ ∈ s
⊢ c.succ v i z < s ∧ c.succ v i z = c.succ v i z ∧ ⟪i + 1, c.succ v i z⟫ ∈ s
Tactic:
have := hs i (by rcases hi with ⟨l, _, rfl, hl⟩; simp [lt_tsub_iff_right, hl]) z hiz
State after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
i : M
x✝¹ : i < 2 * s
hi : ∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l
z : M
x✝ : z < s
hiz : ⟪i, z⟫ ∈ s
this : ⟪i + 1, c.succ v i z⟫ ∈ s
⊢ c.succ v i z < s ∧ c.succ v i z = c.succ v i z ∧ ⟪i + 1, c.succ v i z⟫ ∈ s

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
i : M
x✝¹ : i < 2 * s
hi : ∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l
z : M
x✝ : z < s
hiz : ⟪i, z⟫ ∈ s
this : ⟪i + 1, c.succ v i z⟫ ∈ s
⊢ c.succ v i z < s ∧ c.succ v i z = c.succ v i z ∧ ⟪i + 1, c.succ v i z⟫ ∈ s
Tactic:
exact ⟨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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
i : M
x✝¹ : i < 2 * s
hi : ∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l
z : M
x✝ : z < s
hiz : ⟪i, z⟫ ∈ s
⊢ i < lh s - 1
Tactic:
rcases hi with ⟨l, _, rfl, hl⟩
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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
i : M
x✝¹ : i < 2 * s
z : M
x✝ : z < s
hiz : ⟪i, z⟫ ∈ s
left✝ : lh s ≤ 2 * s
hl : i + 1 < lh s
⊢ i < lh s - 1

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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
hz : ⟪0, c.zero v⟫ ∈ s
hs : ∀ i < lh s - 1, ∀ (z : M), ⟪i, z⟫ ∈ s → ⟪i + 1, c.succ v i z⟫ ∈ s
i : M
x✝¹ : i < 2 * s
z : M
x✝ : z < s
hiz : ⟪i, z⟫ ∈ s
left✝ : lh s ≤ 2 * s
hl : i + 1 < lh s
⊢ i < lh s - 1
Tactic:
simp [lt_tsub_iff_right, hl]
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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
⊢ (Seq s ∧
      (∃ z < s, z = c.zero v ∧ ⟪0, z⟫ ∈ s) ∧
        ∀ i < 2 * s,
          (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s) →
    c.CSeq v s
Tactic:
rintro ⟨Hs, ⟨z, _, rfl, hz⟩, h⟩
State after:
case intro.intro.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
⊢ c.CSeq v s

State before:
case intro.intro.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
⊢ c.CSeq v s
Tactic:
exact ⟨Hs, hz, fun i hi z hiz ↦ by
  rcases h i
    (lt_of_lt_of_le hi (by simp; exact le_trans (lh_bound _) (by simp)))
    ⟨lh s, by simp [lt_succ_iff_le], rfl, by simpa [lt_tsub_iff_right] using hi⟩ z (lt_of_mem_rng hiz) hiz 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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
⊢ ⟪i + 1, c.succ v i z⟫ ∈ s
Tactic:
rcases h i
  (lt_of_lt_of_le hi (by simp; exact le_trans (lh_bound _) (by simp)))
  ⟨lh s, by simp [lt_succ_iff_le], rfl, by simpa [lt_tsub_iff_right] using hi⟩ z (lt_of_mem_rng hiz) hiz 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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h✝ : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝¹ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
left✝ : c.succ v i z < s
h : ⟪i + 1, c.succ v i z⟫ ∈ s
⊢ ⟪i + 1, c.succ v i z⟫ ∈ s

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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h✝ : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝¹ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
left✝ : c.succ v i z < s
h : ⟪i + 1, c.succ v i z⟫ ∈ s
⊢ ⟪i + 1, c.succ v i z⟫ ∈ s
Tactic:
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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
⊢ lh s - 1 ≤ 2 * s
Tactic:
simp
State after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
⊢ lh s ≤ 2 * s + 1

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
⊢ lh s ≤ 2 * s + 1
Tactic:
exact le_trans (lh_bound _) (by simp)
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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
⊢ 2 * s ≤ 2 * s + 1
Tactic:
simp
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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
⊢ lh s ≤ 2 * s
Tactic:
simp [lt_succ_iff_le]
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 ⊧ₘ* 𝐈𝚺₁
k : ℕ
p : Formulae k
c : Construction M p
v : Fin k → M
s : M
Hs : Seq s
h : ∀ i < 2 * s, (∃ l ≤ 2 * s, l = lh s ∧ i + 1 < l) → ∀ z < s, ⟪i, z⟫ ∈ s → ∃ u < s, u = c.succ v i z ∧ ⟪i + 1, u⟫ ∈ s
left✝ : c.zero v < s
hz : ⟪0, c.zero v⟫ ∈ s
i : M
hi : i < lh s - 1
z : M
hiz : ⟪i, z⟫ ∈ s
⊢ i + 1 < lh s
Tactic:
simpa [lt_tsub_iff_right] using hi
State after:
no goals