Theorem: LO.FirstOrder.Arith.Model.SPPow2.last_uniq (Arithmetization/ISigmaZero/Exponential/PPow2.lean)

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
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

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
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

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
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

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)
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

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
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

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
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

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
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

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
State after:
no goals

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))
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 ⊧ₘ* 𝐈𝚫₀
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
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✝ ⊧ₘ* 𝐈𝚫₀
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
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✝ ⊧ₘ* 𝐈𝚫₀
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
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✝ ⊧ₘ* 𝐈𝚫₀
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
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✝ ⊧ₘ* 𝐈𝚫₀
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
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

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
State after:
no goals