Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit (Arithmetization/ISigmaZero/Exponential/Pow2.lean)

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Tactic:
rcases show i < j ∨ i = j ∨ i > j from lt_trichotomy i j with (hij | rfl | hij)
State after:
case inl
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i < j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a

case inr.inl
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i : M
pi pj : Pow2 i
h : ¬LenBit i a
⊢ LenBit i (a + i) ↔ i = i ∨ LenBit i a

case inr.inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i > j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a

State before:
case inl
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i < j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Tactic:
simp [LenBit.add_pow2 pi pj hij, hij.ne]
State after:
no goals

State before:
case inr.inl
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i : M
pi pj : Pow2 i
h : ¬LenBit i a
⊢ LenBit i (a + i) ↔ i = i ∨ LenBit i a
Tactic:
simp [LenBit.add_self_of_not_lenbit pi.pos, h]
State after:
no goals

State before:
case inr.inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i > j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Tactic:
simp [ne_of_gt hij]
State after:
case inr.inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i > j
⊢ LenBit i (a + j) ↔ LenBit i a

State before:
case inr.inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i > j
⊢ LenBit i (a + j) ↔ LenBit i a
Tactic:
have : 2 * j ∣ i := Pow2.dvd_of_le (by simp [pj]) pi <| (pj.lt_iff_two_mul_le pi).mp hij
State after:
case inr.inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i > j
this : 2 * j ∣ i
⊢ LenBit i (a + j) ↔ LenBit i a

State before:
case inr.inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i > j
this : 2 * j ∣ i
⊢ LenBit i (a + j) ↔ LenBit i a
Tactic:
rcases this with ⟨i, rfl⟩
State after:
case inr.inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a j : M
pj : Pow2 j
h : ¬LenBit j a
i : M
pi : Pow2 (2 * j * i)
hij : 2 * j * i > j
⊢ LenBit (2 * j * i) (a + j) ↔ LenBit (2 * j * i) a

State before:
case inr.inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a j : M
pj : Pow2 j
h : ¬LenBit j a
i : M
pi : Pow2 (2 * j * i)
hij : 2 * j * i > j
⊢ LenBit (2 * j * i) (a + j) ↔ LenBit (2 * j * i) a
Tactic:
rcases (not_lenbit_iff_add_mul pj).mp h with ⟨a, r, hr, rfl⟩
State after:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
pi : Pow2 (2 * j * i)
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)

State before:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
pi : Pow2 (2 * j * i)
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)
Tactic:
simp at pi
State after:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)

State before:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)
Tactic:
have pi' : Pow2 i := pi.2
State after:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)

State before:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)
Tactic:
have pj' : Pow2 j := pi.1
State after:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
pj' : Pow2 j
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)

State before:
case inr.inr.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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
pj' : Pow2 j
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (2 * j * i) (a * (2 * j) + r)
Tactic:
calc
  LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (i * (2 * j)) (a * (2 * j) + (r + j)) := by
    simp [mul_comm (2 * j), add_assoc]
  _                                        ↔ LenBit i a                                   :=
    lenbit_mul_add pi' (by simpa using pj') (by simp [two_mul, hr])
  _                                        ↔ LenBit (i * (2 * j)) (a * (2 * j) + r)       :=
    Iff.symm <| lenbit_mul_add pi' (by simpa using pj') (lt_of_lt_of_le hr $ by simp)
  _                                        ↔ LenBit (2 * j * i) (a * (2 * j) + r)         := by
    simp [mul_comm]
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 ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : ¬LenBit j a
hij : i > j
⊢ Pow2 (2 * j)
Tactic:
simp [pj]
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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
pj' : Pow2 j
⊢ LenBit (2 * j * i) (a * (2 * j) + r + j) ↔ LenBit (i * (2 * j)) (a * (2 * j) + (r + j))
Tactic:
simp [mul_comm (2 * j), add_assoc]
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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
pj' : Pow2 j
⊢ Pow2 (2 * j)
Tactic:
simpa using pj'
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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
pj' : Pow2 j
⊢ r + j < 2 * j
Tactic:
simp [two_mul, hr]
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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
pj' : Pow2 j
⊢ j ≤ 2 * j
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 ⊧ₘ* 𝐈𝚫₀
j : M
pj : Pow2 j
i : M
hij : 2 * j * i > j
a r : M
hr : r < j
h : ¬LenBit j (a * (2 * j) + r)
pi : Pow2 j ∧ Pow2 i
pi' : Pow2 i
pj' : Pow2 j
⊢ LenBit (i * (2 * j)) (a * (2 * j) + r) ↔ LenBit (2 * j * i) (a * (2 * j) + r)
Tactic:
simp [mul_comm]
State after:
no goals