internlm/Lean-Github huggingface dataset:
Theorem: LO.FirstOrder.Arith.Model.Pow2.four_le
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
lt : 2 < i
A : ¬4 ≤ i
⊢ False
Tactic:
have : i ≤ 3 := by simpa [←three_add_one_eq_four, ←le_iff_lt_succ] using A
Proof state after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
lt : 2 < i
A : ¬4 ≤ i
this : i ≤ 3
⊢ False
Theorem: LO.FirstOrder.Arith.Model.Pow2.four_le
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
lt : 2 < i
A : ¬4 ≤ i
this : i ≤ 3
⊢ False
Tactic:
rcases le_three_iff_eq_zero_or_one_or_two_or_three.mp this with (rfl | rfl | rfl | rfl) <;> simp at lt hi
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.four_le
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
lt : 2 < i
A : ¬4 ≤ i
⊢ i ≤ 3
Tactic:
simpa [←three_add_one_eq_four, ←le_iff_lt_succ] using A
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p q : M
hp : Pow2 p
hq : Pow2 q
h : a * p < q
hb : b < p
hbq : b < q
⊢ a * p + b < q
Tactic:
rcases zero_le a with (rfl | pos)
Proof 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 ⊧ₘ* 𝐈𝚫₀
b p q : M
hp : Pow2 p
hq : Pow2 q
hb : b < p
hbq : b < q
h : 0 * p < q
⊢ 0 * p + b < q

case inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p q : M
hp : Pow2 p
hq : Pow2 q
h : a * p < q
hb : b < p
hbq : b < q
pos : 0 < a
⊢ a * p + b < q
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
case inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p q : M
hp : Pow2 p
hq : Pow2 q
h : a * p < q
hb : b < p
hbq : b < q
pos : 0 < a
⊢ a * p + b < q
Tactic:
have : p ∣ q :=
  dvd_of_le hp hq (le_of_lt $
    lt_of_mul_lt_of_one_le_of_nonneg_left (by simpa [mul_comm a p] using h) (pos_iff_one_le.mp pos) (by simp))
Proof state after:
case inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p q : M
hp : Pow2 p
hq : Pow2 q
h : a * p < q
hb : b < p
hbq : b < q
pos : 0 < a
this : p ∣ q
⊢ a * p + b < q
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
case inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p q : M
hp : Pow2 p
hq : Pow2 q
h : a * p < q
hb : b < p
hbq : b < q
pos : 0 < a
this : p ∣ q
⊢ a * p + b < q
Tactic:
rcases this with ⟨q, rfl⟩
Proof state after:
case inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
⊢ a * p + b < p * q
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
case inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
⊢ a * p + b < p * q
Tactic:
have : a < q := lt_of_mul_lt_mul_right (a := p) (by simpa [mul_comm] using h)
Proof state after:
case inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
this : a < q
⊢ a * p + b < p * q
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
case inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
this : a < q
⊢ a * p + b < p * q
Tactic:
calc
  a * p + b < (a + 1) * p := by simp [add_mul, hb]
  _         ≤ p * q       := by simp [mul_comm p q]; exact mul_le_mul_right (lt_iff_succ_le.mp this)
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof 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 ⊧ₘ* 𝐈𝚫₀
b p q : M
hp : Pow2 p
hq : Pow2 q
hb : b < p
hbq : b < q
h : 0 * p < q
⊢ 0 * p + b < q
Tactic:
simp [hbq]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p q : M
hp : Pow2 p
hq : Pow2 q
h : a * p < q
hb : b < p
hbq : b < q
pos : 0 < a
⊢ p * a < q
Tactic:
simpa [mul_comm a p] using h
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p q : M
hp : Pow2 p
hq : Pow2 q
h : a * p < q
hb : b < p
hbq : b < q
pos : 0 < a
⊢ 0 ≤ p
Tactic:
simp
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
⊢ a * p < q * p
Tactic:
simpa [mul_comm] using h
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
this : a < q
⊢ a * p + b < (a + 1) * p
Tactic:
simp [add_mul, hb]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
this : a < q
⊢ (a + 1) * p ≤ p * q
Tactic:
simp [mul_comm p q]
Proof state after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
this : a < q
⊢ (a + 1) * p ≤ q * p
Theorem: LO.FirstOrder.Arith.Model.Pow2.mul_add_lt_of_mul_lt_of_pos
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
a b p : M
hp : Pow2 p
hb : b < p
pos : 0 < a
q : M
hq : Pow2 (p * q)
h : a * p < p * q
hbq : b < p * q
this : a < q
⊢ (a + 1) * p ≤ q * p
Tactic:
exact mul_le_mul_right (lt_iff_succ_le.mp this)
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.LenBit.mod_pow2
Proof 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 : i < j
⊢ 2 * i ∣ j
Tactic:
rw [←Pow2.le_iff_dvd] <;> simp [pi, pj, ←Pow2.lt_iff_two_mul_le, h]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.LenBit.add_pow2
Proof 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 : i < j
⊢ 2 * i ∣ j
Tactic:
rw [←Pow2.le_iff_dvd] <;> simp [pi, pj, ←Pow2.lt_iff_two_mul_le, h]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.LenBit.add_pow2_iff_of_lt
Proof 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 : a < j
⊢ 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)
Proof 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 : a < j
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 : a < i
⊢ 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 : a < j
hij : i > j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Theorem: LO.FirstOrder.Arith.Model.LenBit.add_pow2_iff_of_lt
Proof 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 : a < j
hij : i < j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Tactic:
simp [LenBit.add_pow2 pi pj hij, hij.ne]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.LenBit.add_pow2_iff_of_lt
Proof 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 : a < i
⊢ LenBit i (a + i) ↔ i = i ∨ LenBit i a
Tactic:
simp [LenBit.add_self h]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.LenBit.add_pow2_iff_of_lt
Proof 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 : a < j
hij : i > j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Tactic:
have : a + j < i := calc
  a + j < 2 * j  := by simp[two_mul, h]
  _     ≤ i      := (pj.lt_iff_two_mul_le pi).mp hij
Proof 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 : a < j
hij : i > j
this : a + j < i
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Theorem: LO.FirstOrder.Arith.Model.LenBit.add_pow2_iff_of_lt
Proof 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 : a < j
hij : i > j
this : a + j < i
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Tactic:
simp [not_lenbit_of_lt this, not_lenbit_of_lt (show a < i from lt_trans _ _ _ h hij), hij.ne.symm]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.LenBit.add_pow2_iff_of_lt
Proof 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 : a < j
hij : i > j
⊢ a + j < 2 * j
Tactic:
simp[two_mul, h]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ LenBit i a ↔ ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Tactic:
constructor
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ LenBit i a → ∃ k, ∃ r < i, a = k * (2 * i) + i + r

case mpr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ (∃ k, ∃ r < i, a = k * (2 * i) + i + r) → LenBit i a
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ LenBit i a → ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Tactic:
intro h
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Tactic:
have : 2 * ((a / i) / 2) + 1 = a / i := by simpa [LenBit.iff_rem.mp h] using div_add_mod (a / i) 2
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
this : 2 * (a / i / 2) + 1 = a / i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
this : 2 * (a / i / 2) + 1 = a / i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Tactic:
have : a = ((a / i) / 2) * (2 * i) + i + (a % i) := calc
  a = i * (a / i) + (a % i)                  := Eq.symm <| div_add_mod a i
  _ = i * (2 * ((a / i) / 2) + 1) + (a % i) := by simp [this]
  _ = ((a / i) / 2) * (2 * i) + i + (a % i) := by simp [mul_add, ←mul_assoc, mul_comm i 2, mul_comm (2 * i)]
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
this✝ : 2 * (a / i / 2) + 1 = a / i
this : a = a / i / 2 * (2 * i) + i + a % i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
this✝ : 2 * (a / i / 2) + 1 = a / i
this : a = a / i / 2 * (2 * i) + i + a % i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + i + r
Tactic:
exact ⟨(a / i) / 2, a % i, by simp [hi.pos], this⟩
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
⊢ 2 * (a / i / 2) + 1 = a / i
Tactic:
simpa [LenBit.iff_rem.mp h] using div_add_mod (a / i) 2
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
this : 2 * (a / i / 2) + 1 = a / i
⊢ i * (a / i) + a % i = i * (2 * (a / i / 2) + 1) + a % i
Tactic:
simp [this]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
this : 2 * (a / i / 2) + 1 = a / i
⊢ i * (2 * (a / i / 2) + 1) + a % i = a / i / 2 * (2 * i) + i + a % i
Tactic:
simp [mul_add, ←mul_assoc, mul_comm i 2, mul_comm (2 * i)]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : LenBit i a
this✝ : 2 * (a / i / 2) + 1 = a / i
this : a = a / i / 2 * (2 * i) + i + a % i
⊢ a % i < i
Tactic:
simp [hi.pos]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
case mpr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ (∃ k, ∃ r < i, a = k * (2 * i) + i + r) → LenBit i a
Tactic:
rintro ⟨k, r, h, rfl⟩
Proof state after:
case mpr.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
k r : M
h : r < i
⊢ LenBit i (k * (2 * i) + i + r)
Theorem: LO.FirstOrder.Arith.Model.lenbit_iff_add_mul
Proof state before:
case mpr.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
k r : M
h : r < i
⊢ LenBit i (k * (2 * i) + i + r)
Tactic:
simp [LenBit.iff_rem, ←mul_assoc, add_assoc, div_mul_add_self, hi.pos, h, one_lt_two]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ ¬LenBit i a ↔ ∃ k, ∃ r < i, a = k * (2 * i) + r
Tactic:
constructor
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ ¬LenBit i a → ∃ k, ∃ r < i, a = k * (2 * i) + r

case mpr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ (∃ k, ∃ r < i, a = k * (2 * i) + r) → ¬LenBit i a
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ ¬LenBit i a → ∃ k, ∃ r < i, a = k * (2 * i) + r
Tactic:
intro h
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + r
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + r
Tactic:
have : 2 * ((a / i) / 2) = a / i := by simpa [not_lenbit_iff_rem.mp h] using div_add_mod (a / i) 2
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
this : 2 * (a / i / 2) = a / i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + r
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
this : 2 * (a / i / 2) = a / i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + r
Tactic:
have : a = ((a / i) / 2) * (2 * i) + (a % i) := calc
  a = i * (a / i) + (a % i)              := Eq.symm <| div_add_mod a i
  _ = i * (2 * ((a / i) / 2)) + (a % i) := by simp [this]
  _ = ((a / i) / 2) * (2 * i) + (a % i) := by simp [mul_add, ←mul_assoc, mul_comm i 2, mul_comm (2 * i)]
Proof state after:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
this✝ : 2 * (a / i / 2) = a / i
this : a = a / i / 2 * (2 * i) + a % i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + r
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
case mp
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
this✝ : 2 * (a / i / 2) = a / i
this : a = a / i / 2 * (2 * i) + a % i
⊢ ∃ k, ∃ r < i, a = k * (2 * i) + r
Tactic:
exact ⟨(a / i) / 2, a % i, by simp [hi.pos], this⟩
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
⊢ 2 * (a / i / 2) = a / i
Tactic:
simpa [not_lenbit_iff_rem.mp h] using div_add_mod (a / i) 2
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
this : 2 * (a / i / 2) = a / i
⊢ i * (a / i) + a % i = i * (2 * (a / i / 2)) + a % i
Tactic:
simp [this]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
this : 2 * (a / i / 2) = a / i
⊢ i * (2 * (a / i / 2)) + a % i = a / i / 2 * (2 * i) + a % i
Tactic:
simp [mul_add, ←mul_assoc, mul_comm i 2, mul_comm (2 * i)]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
h : ¬LenBit i a
this✝ : 2 * (a / i / 2) = a / i
this : a = a / i / 2 * (2 * i) + a % i
⊢ a % i < i
Tactic:
simp [hi.pos]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
case mpr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i a : M
hi : Pow2 i
⊢ (∃ k, ∃ r < i, a = k * (2 * i) + r) → ¬LenBit i a
Tactic:
rintro ⟨k, r, h, rfl⟩
Proof state after:
case mpr.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
k r : M
h : r < i
⊢ ¬LenBit i (k * (2 * i) + r)
Theorem: LO.FirstOrder.Arith.Model.not_lenbit_iff_add_mul
Proof state before:
case mpr.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i : M
hi : Pow2 i
k r : M
h : r < i
⊢ ¬LenBit i (k * (2 * i) + r)
Tactic:
simp [not_lenbit_iff_rem, ←mul_assoc, add_assoc, div_mul_add_self, hi.pos, h]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_mul_add
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i j a r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
⊢ LenBit (i * j) (a * j + r) ↔ LenBit i a
Tactic:
by_cases h : LenBit i a <;> simp [h]
Proof 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 ⊧ₘ* 𝐈𝚫₀
i j a r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
h : LenBit i a
⊢ LenBit (i * j) (a * j + r)

case neg
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i j a r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
h : ¬LenBit i a
⊢ ¬LenBit (i * j) (a * j + r)
Theorem: LO.FirstOrder.Arith.Model.lenbit_mul_add
Proof 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 ⊧ₘ* 𝐈𝚫₀
i j a r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
h : LenBit i a
⊢ LenBit (i * j) (a * j + r)
Tactic:
rcases (lenbit_iff_add_mul pi).mp h with ⟨a, b, hb, rfl⟩
Proof state after:
case pos.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i j r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
a b : M
hb : b < i
h : LenBit i (a * (2 * i) + i + b)
⊢ LenBit (i * j) ((a * (2 * i) + i + b) * j + r)
Theorem: LO.FirstOrder.Arith.Model.lenbit_mul_add
Proof state before:
case pos.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i j r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
a b : M
hb : b < i
h : LenBit i (a * (2 * i) + i + b)
⊢ LenBit (i * j) ((a * (2 * i) + i + b) * j + r)
Tactic:
have : b * j + r < i * j :=
  pj.mul_add_lt_of_mul_lt_of_pos (by simp[pi, pj]) ((mul_lt_mul_right pj.pos).mpr hb)  hr (lt_of_lt_of_le hr $ le_mul_of_pos_left $ pi.pos)
Proof state after:
case pos.intro.intro.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
i j r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
a b : M
hb : b < i
h : LenBit i (a * (2 * i) + i + b)
this : b * j + r < i * j
⊢ LenBit (i * j) ((a * (2 * i) + i + b) * j + r)