internlm/Lean-Github huggingface dataset:
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)
this : b * j + r < i * j
⊢ LenBit (i * j) ((a * (2 * i) + i + b) * j + r)
Tactic:
exact (lenbit_iff_add_mul (by simp [pi, pj])).mpr ⟨a, b * j + r, this, by simp [add_mul, add_assoc, mul_assoc]⟩
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 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)
⊢ Pow2 (i * j)
Tactic:
simp[pi, pj]
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 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
⊢ Pow2 (i * j)
Tactic:
simp [pi, pj]
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 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
⊢ (a * (2 * i) + i + b) * j + r = a * (2 * (i * j)) + i * j + (b * j + r)
Tactic:
simp [add_mul, add_assoc, mul_assoc]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_mul_add
Proof 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 ⊧ₘ* 𝐈𝚫₀
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 (not_lenbit_iff_add_mul pi).mp h with ⟨a, b, hb, rfl⟩
Proof state after:
case neg.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) + b)
⊢ ¬LenBit (i * j) ((a * (2 * i) + b) * j + r)
Theorem: LO.FirstOrder.Arith.Model.lenbit_mul_add
Proof state before:
case neg.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) + b)
⊢ ¬LenBit (i * j) ((a * (2 * 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 neg.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) + b)
this : b * j + r < i * j
⊢ ¬LenBit (i * j) ((a * (2 * i) + b) * j + r)
Theorem: LO.FirstOrder.Arith.Model.lenbit_mul_add
Proof state before:
case neg.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) + b)
this : b * j + r < i * j
⊢ ¬LenBit (i * j) ((a * (2 * i) + b) * j + r)
Tactic:
exact (not_lenbit_iff_add_mul (by simp [pi, pj])).mpr ⟨a, b * j + r, this, by simp [add_mul, add_assoc, mul_assoc]⟩
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 r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
a b : M
hb : b < i
h : ¬LenBit i (a * (2 * i) + b)
⊢ Pow2 (i * j)
Tactic:
simp[pi, pj]
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 r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
a b : M
hb : b < i
h : ¬LenBit i (a * (2 * i) + b)
this : b * j + r < i * j
⊢ Pow2 (i * j)
Tactic:
simp [pi, pj]
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 r : M
pi : Pow2 i
pj : Pow2 j
hr : r < j
a b : M
hb : b < i
h : ¬LenBit i (a * (2 * i) + b)
this : b * j + r < i * j
⊢ (a * (2 * i) + b) * j + r = a * (2 * (i * j)) + (b * j + r)
Tactic:
simp [add_mul, add_assoc, mul_assoc]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
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 : ¬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)
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 : ¬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
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
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 : ¬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]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
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 : ¬LenBit i a
⊢ LenBit i (a + i) ↔ i = i ∨ LenBit i a
Tactic:
simp [LenBit.add_self_of_not_lenbit pi.pos, h]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
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 : ¬LenBit j a
hij : i > j
⊢ LenBit i (a + j) ↔ i = j ∨ LenBit i a
Tactic:
simp [ne_of_gt 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 : ¬LenBit j a
hij : i > j
⊢ LenBit i (a + j) ↔ LenBit i a
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
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 : ¬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
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 : ¬LenBit j a
hij : i > j
this : 2 * j ∣ i
⊢ LenBit i (a + j) ↔ LenBit i a
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
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 : ¬LenBit j a
hij : i > j
this : 2 * j ∣ i
⊢ LenBit i (a + j) ↔ LenBit i a
Tactic:
rcases this with ⟨i, rfl⟩
Proof 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
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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⟩
Proof 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)
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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
Proof 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)
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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
Proof 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)
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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
Proof 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)
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
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 : ¬LenBit j a
hij : i > j
⊢ Pow2 (2 * j)
Tactic:
simp [pj]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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'
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_add_pow2_iff_of_not_lenbit
Proof 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]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : LenBit j a
⊢ LenBit i (a - j) ↔ i ≠ j ∧ LenBit i a
Tactic:
generalize ha' : a - j = 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 ⊧ₘ* 𝐈𝚫₀
a i j : M
pi : Pow2 i
pj : Pow2 j
h : LenBit j a
a' : M
ha' : a - j = a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i a
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : LenBit j a
a' : M
ha' : a - j = a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i a
Tactic:
have h' : ¬LenBit j a' := by simpa [←ha'] using LenBit.sub_self_of_lenbit pj.pos h
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 i j : M
pi : Pow2 i
pj : Pow2 j
h : LenBit j a
a' : M
ha' : a - j = a'
h' : ¬LenBit j a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i a
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : LenBit j a
a' : M
ha' : a - j = a'
h' : ¬LenBit j a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i a
Tactic:
have : a = a' + j := by simp [←ha', sub_add_self_of_le h.le]
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 i j : M
pi : Pow2 i
pj : Pow2 j
h : LenBit j a
a' : M
ha' : a - j = a'
h' : ¬LenBit j a'
this : a = a' + j
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i a
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : LenBit j a
a' : M
ha' : a - j = a'
h' : ¬LenBit j a'
this : a = a' + j
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i a
Tactic:
rcases this with rfl
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 j : M
pi : Pow2 i
pj : Pow2 j
a' : M
h' : ¬LenBit j a'
h : LenBit j (a' + j)
ha' : a' + j - j = a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i (a' + j)
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : M
pi : Pow2 i
pj : Pow2 j
a' : M
h' : ¬LenBit j a'
h : LenBit j (a' + j)
ha' : a' + j - j = a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i (a' + j)
Tactic:
have : LenBit i (a' + j) ↔ i = j ∨ LenBit i a' := lenbit_add_pow2_iff_of_not_lenbit pi pj h'
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 j : M
pi : Pow2 i
pj : Pow2 j
a' : M
h' : ¬LenBit j a'
h : LenBit j (a' + j)
ha' : a' + j - j = a'
this : LenBit i (a' + j) ↔ i = j ∨ LenBit i a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i (a' + j)
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : M
pi : Pow2 i
pj : Pow2 j
a' : M
h' : ¬LenBit j a'
h : LenBit j (a' + j)
ha' : a' + j - j = a'
this : LenBit i (a' + j) ↔ i = j ∨ LenBit i a'
⊢ LenBit i a' ↔ i ≠ j ∧ LenBit i (a' + j)
Tactic:
simp [this, and_or_left]
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 j : M
pi : Pow2 i
pj : Pow2 j
a' : M
h' : ¬LenBit j a'
h : LenBit j (a' + j)
ha' : a' + j - j = a'
this : LenBit i (a' + j) ↔ i = j ∨ LenBit i a'
⊢ LenBit i a' → ¬i = j
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : M
pi : Pow2 i
pj : Pow2 j
a' : M
h' : ¬LenBit j a'
h : LenBit j (a' + j)
ha' : a' + j - j = a'
this : LenBit i (a' + j) ↔ i = j ∨ LenBit i a'
⊢ LenBit i a' → ¬i = j
Tactic:
rintro _ rfl
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
pi : Pow2 i
a' : M
a✝ : LenBit i a'
pj : Pow2 i
h' : ¬LenBit i a'
h : LenBit i (a' + i)
ha' : a' + i - i = a'
this : LenBit i (a' + i) ↔ i = i ∨ LenBit i a'
⊢ False
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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
pi : Pow2 i
a' : M
a✝ : LenBit i a'
pj : Pow2 i
h' : ¬LenBit i a'
h : LenBit i (a' + i)
ha' : a' + i - i = a'
this : LenBit i (a' + i) ↔ i = i ∨ LenBit i a'
⊢ False
Tactic:
contradiction
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : LenBit j a
a' : M
ha' : a - j = a'
⊢ ¬LenBit j a'
Tactic:
simpa [←ha'] using LenBit.sub_self_of_lenbit pj.pos h
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.lenbit_sub_pow2_iff_of_lenbit
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 : LenBit j a
a' : M
ha' : a - j = a'
h' : ¬LenBit j a'
⊢ a = a' + j
Tactic:
simp [←ha', sub_add_self_of_le h.le]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Bounded.var
Proof state before:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
i : Fin k
⊢ ∀ (v : Fin k → M), v i ≤ Semiterm.valm M v id #i
Tactic:
intro _
Proof state after:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
i : Fin k
v✝ : Fin k → M
⊢ v✝ i ≤ Semiterm.valm M v✝ id #i
Theorem: LO.FirstOrder.Arith.Model.Bounded.var
Proof state before:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
i : Fin k
v✝ : Fin k → M
⊢ v✝ i ≤ Semiterm.valm M v✝ id #i
Tactic:
simp
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Bounded.const
Proof state before:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
c : M
⊢ ∀ (v : Fin k → M), c ≤ Semiterm.valm M v id &c
Tactic:
intro _
Proof state after:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
c : M
v✝ : Fin k → M
⊢ c ≤ Semiterm.valm M v✝ id &c
Theorem: LO.FirstOrder.Arith.Model.Bounded.const
Proof state before:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
c : M
v✝ : Fin k → M
⊢ c ≤ Semiterm.valm M v✝ id &c
Tactic:
simp
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.Bounded.term_retraction
Proof state before:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
t : Semiterm L M n
e : Fin n → Fin k
⊢ ∀ (v : Fin k → M), Semiterm.valm M (fun x => v (e x)) id t ≤ Semiterm.valm M v id ((Rew.substs fun x => #(e x)) t)
Tactic:
intro _
Proof state after:
L : Language
inst✝⁹ : L.ORing
ξ : Type u_1
n : ℕ
M : Type u_2
inst✝⁸ : Zero M
inst✝⁷ : One M
inst✝⁶ : Add M
inst✝⁵ : Mul M
inst✝⁴ : LT M
inst✝³ : M ⊧ₘ* 𝐏𝐀⁻
inst✝² : Structure L M
inst✝¹ : Structure.ORing L M
inst✝ : Structure.Monotone L M
Γ : HierarchySymbol
k : ℕ
t : Semiterm L M n
e : Fin n → Fin k
v✝ : Fin k → M
⊢ Semiterm.valm M (fun x => v✝ (e x)) id t ≤ Semiterm.valm M v✝ id ((Rew.substs fun x => #(e x)) t)