internlm/Lean-Github huggingface dataset:
Theorem: LO.FirstOrder.Arith.Model.SPPow2.sq_le_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 ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
j : M
IH : ∀ y < j, ∀ i < y, Pow2 i → Pow2 y → LenBit i m → LenBit y m → i ^ 2 ≤ y
i : M
hij : i < j
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
jne2 : ¬j = 2
ine2 : ¬i = 2
this : √i < √j
⊢ i ≤ √j
Tactic:
simpa [hm.sq_sqrt_eq hi pi ine2] using
  IH (√j) (sqrt_lt_self_of_one_lt (hm.one_lt hj)) (√i) this
    (pi.sqrt (hm.sq_sqrt_eq hi pi ine2)) (pj.sqrt (hm.sq_sqrt_eq hj pj jne2)) (hm.sqrt hi pi ine2) (hm.sqrt hj pj jne2)
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
⊢ i = j
Tactic:
by_contra ne
Proof state after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
⊢ False
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
⊢ False
Tactic:
wlog hij : i < j
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 ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
this :
  ∀ {M : Type u_1} [inst : Zero M] [inst_1 : One M] [inst_2 : Add M] [inst_3 : Mul M] [inst_4 : LT M]
    [inst_5 : M ⊧ₘ* 𝐈𝚫₀] {m : M},
    SPPow2 m → ∀ {i j : M}, Pow2 i → Pow2 j → LenBit i m → LenBit j m → m < i ^ 2 → m < j ^ 2 → ¬i = j → i < j → False
hij : ¬i < j
⊢ False

M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
⊢ False
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
⊢ False
Tactic:
have : i^2 ≤ m := le_trans  (hm.sq_le_of_lt pi pj hi hj hij) hj.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✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this : i ^ 2 ≤ m
⊢ False
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this : i ^ 2 ≤ m
⊢ False
Tactic:
have ltsqi : 2 < i^2 := lt_of_le_of_ne (one_lt_iff_two_le.mp $ by simpa using hm.one_lt hi) (by simp)
Proof state after:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
⊢ False
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
⊢ False
Tactic:
have : LenBit (i^2) m ↔ LenBit i m := by simpa using hm.lenbit_iff this pi.sq ltsqi
Proof state after:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝ : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this : LenBit (i ^ 2) m ↔ LenBit i m
⊢ False
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝ : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this : LenBit (i ^ 2) m ↔ LenBit i m
⊢ False
Tactic:
have : LenBit (i^2) m := this.mpr hi
Proof state after:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝¹ : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this✝ : LenBit (i ^ 2) m ↔ LenBit i m
this : LenBit (i ^ 2) m
⊢ False
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝¹ : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this✝ : LenBit (i ^ 2) m ↔ LenBit i m
this : LenBit (i ^ 2) m
⊢ False
Tactic:
have : ¬m < i^2 := by simp; exact this.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✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝² : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this✝¹ : LenBit (i ^ 2) m ↔ LenBit i m
this✝ : LenBit (i ^ 2) m
this : ¬m < i ^ 2
⊢ False
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝² : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this✝¹ : LenBit (i ^ 2) m ↔ LenBit i m
this✝ : LenBit (i ^ 2) m
this : ¬m < i ^ 2
⊢ False
Tactic:
contradiction
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
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 ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
this :
  ∀ {M : Type u_1} [inst : Zero M] [inst_1 : One M] [inst_2 : Add M] [inst_3 : Mul M] [inst_4 : LT M]
    [inst_5 : M ⊧ₘ* 𝐈𝚫₀] {m : M},
    SPPow2 m → ∀ {i j : M}, Pow2 i → Pow2 j → LenBit i m → LenBit j m → m < i ^ 2 → m < j ^ 2 → ¬i = j → i < j → False
hij : ¬i < j
⊢ False
Tactic:
exact this hm pj pi hj hi hsqj hsqi (Ne.symm ne) (lt_of_le_of_ne (by simpa using hij) (Ne.symm ne))
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
this :
  ∀ {M : Type u_1} [inst : Zero M] [inst_1 : One M] [inst_2 : Add M] [inst_3 : Mul M] [inst_4 : LT M]
    [inst_5 : M ⊧ₘ* 𝐈𝚫₀] {m : M},
    SPPow2 m → ∀ {i j : M}, Pow2 i → Pow2 j → LenBit i m → LenBit j m → m < i ^ 2 → m < j ^ 2 → ¬i = j → i < j → False
hij : ¬i < j
⊢ j ≤ i
Tactic:
simpa using hij
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this : i ^ 2 ≤ m
⊢ 1 < i ^ 2
Tactic:
simpa using hm.one_lt hi
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this : i ^ 2 ≤ m
⊢ 2 ≠ i ^ 2
Tactic:
simp
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
⊢ LenBit (i ^ 2) m ↔ LenBit i m
Tactic:
simpa using hm.lenbit_iff this pi.sq ltsqi
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝¹ : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this✝ : LenBit (i ^ 2) m ↔ LenBit i m
this : LenBit (i ^ 2) m
⊢ ¬m < i ^ 2
Tactic:
simp
Proof state after:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝¹ : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this✝ : LenBit (i ^ 2) m ↔ LenBit i m
this : LenBit (i ^ 2) m
⊢ i ^ 2 ≤ m
Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq
Proof state before:
M✝ : Type u_1
inst✝¹¹ : Zero M✝
inst✝¹⁰ : One M✝
inst✝⁹ : Add M✝
inst✝⁸ : Mul M✝
inst✝⁷ : LT M✝
inst✝⁶ : M✝ ⊧ₘ* 𝐈𝚫₀
m✝ : M✝
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈𝚫₀
m : M
hm : SPPow2 m
i j : M
pi : Pow2 i
pj : Pow2 j
hi : LenBit i m
hj : LenBit j m
hsqi : m < i ^ 2
hsqj : m < j ^ 2
ne : ¬i = j
hij : i < j
this✝¹ : i ^ 2 ≤ m
ltsqi : 2 < i ^ 2
this✝ : LenBit (i ^ 2) m ↔ LenBit i m
this : LenBit (i ^ 2) m
⊢ i ^ 2 ≤ m
Tactic:
exact this.le
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.one_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 ⊧ₘ* 𝐈𝚫₀
i : M
ppi : PPow2 i
⊢ 1 < i
Tactic:
rcases ppi with ⟨_, m, _, sppm, lb⟩
Proof state after:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
left✝¹ : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
lb : LenBit i m
⊢ 1 < i
Theorem: LO.FirstOrder.Arith.Model.PPow2.one_lt
Proof state before:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
left✝¹ : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
lb : LenBit i m
⊢ 1 < i
Tactic:
exact sppm.one_lt lb
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sq_sqrt_eq
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
ppi : PPow2 i
ne2 : i ≠ 2
⊢ (√i) ^ 2 = i
Tactic:
rcases ppi with ⟨pi, m, _, sppm, lb⟩
Proof state after:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
lb : LenBit i m
⊢ (√i) ^ 2 = i
Theorem: LO.FirstOrder.Arith.Model.PPow2.sq_sqrt_eq
Proof state before:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
lb : LenBit i m
⊢ (√i) ^ 2 = i
Tactic:
exact ((sppm.lenbit_iff lb.le pi (lt_of_le_of_ne (one_lt_iff_two_le.mp $ sppm.one_lt lb) (Ne.symm ne2))).mp lb).1
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ppi : PPow2 i
ne2 : i ≠ 2
⊢ PPow2 (√i)
Tactic:
rcases ppi with ⟨pi, m, _, sppm, him⟩
Proof state after:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
⊢ PPow2 (√i)
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
Proof state before:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
⊢ PPow2 (√i)
Tactic:
have : LenBit i m ↔ (√i)^2 = i ∧ LenBit (√i) m :=
  sppm.lenbit_iff him.le pi (lt_of_le_of_ne (one_lt_iff_two_le.mp $ sppm.one_lt him) (Ne.symm ne2))
Proof state after:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
⊢ PPow2 (√i)
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
Proof state before:
case 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
⊢ PPow2 (√i)
Tactic:
rcases this.mp him with ⟨e, H⟩
Proof 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
⊢ PPow2 (√i)
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
Proof 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
⊢ PPow2 (√i)
Tactic:
have psqi : Pow2 (√i) := Pow2.sq_iff.mp (by simp [e, pi])
Proof 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
⊢ PPow2 (√i)
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
Proof 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
⊢ PPow2 (√i)
Tactic:
have one_lt_sqi : 1 < √i := one_lt_sq_iff.mp (by simpa [e] using sppm.one_lt him)
Proof 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
⊢ PPow2 (√i)
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
Proof 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 ⊧ₘ* 𝐈𝚫₀
i : M
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this✝ : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
this : SPPow2 (m % (2 * √i))
⊢ PPow2 (√i)
Tactic:
exact ⟨psqi, m % (2 * √i), mod_lt _ (by simp [psqi.pos]), this, by simp [H]⟩
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
⊢ Pow2 ((√i) ^ 2)
Tactic:
simp [e, pi]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
⊢ 1 < (√i) ^ 2
Tactic:
simpa [e] using sppm.one_lt him
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
⊢ ¬LenBit 1 (m % (2 * √i))
Tactic:
simpa [LenBit.mod] using sppm.not_lenbit_one
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
⊢ Pow2 2
Tactic:
simp
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
⊢ Pow2 (2 * √i)
Tactic:
simp [psqi]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
⊢ 2 < 2 * √i
Tactic:
simp [one_lt_sqi]
Proof state after:
no goals
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
⊢ ∀ i_1 ≤ m % (2 * √i),
    Pow2 i_1 → 2 < i_1 → (LenBit i_1 (m % (2 * √i)) ↔ (√i_1) ^ 2 = i_1 ∧ LenBit (√i_1) (m % (2 * √i)))
Tactic:
intro j hj pj lt2
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
j : M
hj : j ≤ m % (2 * √i)
pj : Pow2 j
lt2 : 2 < j
⊢ LenBit j (m % (2 * √i)) ↔ (√j) ^ 2 = j ∧ LenBit (√j) (m % (2 * √i))
Theorem: LO.FirstOrder.Arith.Model.PPow2.sqrt
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
j : M
hj : j ≤ m % (2 * √i)
pj : Pow2 j
lt2 : 2 < j
⊢ LenBit j (m % (2 * √i)) ↔ (√j) ^ 2 = j ∧ LenBit (√j) (m % (2 * √i))
Tactic:
have hjsi : j < 2 * √i := lt_of_le_of_lt hj (mod_lt _ (by simp [psqi.pos]))
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
ne2 : i ≠ 2
pi : Pow2 i
m : M
left✝ : m < 2 * i
sppm : SPPow2 m
him : LenBit i m
this : LenBit i m ↔ (√i) ^ 2 = i ∧ LenBit (√i) m
e : (√i) ^ 2 = i
H : LenBit (√i) m
psqi : Pow2 (√i)
one_lt_sqi : 1 < √i
j : M
hj : j ≤ m % (2 * √i)
pj : Pow2 j
lt2 : 2 < j
hjsi : j < 2 * √i
⊢ LenBit j (m % (2 * √i)) ↔ (√j) ^ 2 = j ∧ LenBit (√j) (m % (2 * √i))