ink

theorem Nat.eq_zero_of_mul_eq_zero {n : ℕ} {m : ℕ} : n * m = 0 → n = 0 ∨ m = 0

ink

instance Nat.linearOrder : LinearOrder ℕ

Equations

• Nat.linearOrder = LinearOrder.mk Nat.le_total inferInstance inferInstance inferInstance

ink

def Nat.strong_rec_on {p : ℕ → Sort u} (n : ℕ) (H : (n : ℕ) → ((m : ℕ) → m < n → p m) → p n) : p n

Equations

• Nat.strong_rec_on n H = WellFounded.fix' (_ : WellFounded WellFoundedRelation.rel) H n

ink

theorem Nat.strong_induction_on {p : ℕ → Prop} (n : ℕ) (h : (n : ℕ) → ((m : ℕ) → m < n → p m) → p n) : p n

ink

theorem Nat.case_strong_induction_on {p : ℕ → Prop} (a : ℕ) (hz : p 0) (hi : (n : ℕ) → ((m : ℕ) → m ≤ n → p m) → p (Nat.succ n)) : p a

ink

def Nat.iterate {α : Sort u} (op : α → α) : ℕ → α → α

Equations

• (op^[0]) x = x
• (op^[Nat.succ k]) x = (op^[k]) (op x)

ink

def Nat.«term_^[_]» : Lean.TrailingParserDescr

Equations

• One or more equations did not get rendered due to their size.

bit0/bit1 properties

ink

theorem Nat.bit1_eq_succ_bit0 (n : ℕ) : bit1 n = Nat.succ (bit0 n)

ink

theorem Nat.bit1_succ_eq (n : ℕ) : bit1 (Nat.succ n) = Nat.succ (Nat.succ (bit1 n))

ink

theorem Nat.bit1_ne_one {n : ℕ} : n ≠ 0 → bit1 n ≠ 1

ink

theorem Nat.bit0_ne_one (n : ℕ) : bit0 n ≠ 1

ink

theorem Nat.bit1_ne_bit0 (n : ℕ) (m : ℕ) : bit1 n ≠ bit0 m

ink

theorem Nat.bit0_ne_bit1 (n : ℕ) (m : ℕ) : bit0 n ≠ bit1 m

ink

theorem Nat.bit0_inj {n : ℕ} {m : ℕ} : bit0 n = bit0 m → n = m

ink

theorem Nat.bit1_inj {n : ℕ} {m : ℕ} : bit1 n = bit1 m → n = m

ink

theorem Nat.bit0_ne {n : ℕ} {m : ℕ} : n ≠ m → bit0 n ≠ bit0 m

ink

theorem Nat.bit1_ne {n : ℕ} {m : ℕ} : n ≠ m → bit1 n ≠ bit1 m

ink

theorem Nat.zero_ne_bit0 {n : ℕ} : n ≠ 0 → 0 ≠ bit0 n

ink

theorem Nat.zero_ne_bit1 (n : ℕ) : 0 ≠ bit1 n

ink

theorem Nat.one_ne_bit0 (n : ℕ) : 1 ≠ bit0 n

ink

theorem Nat.one_ne_bit1 {n : ℕ} : n ≠ 0 → 1 ≠ bit1 n

ink

theorem Nat.one_lt_bit1 {n : ℕ} : n ≠ 0 → 1 < bit1 n

ink

theorem Nat.one_lt_bit0 {n : ℕ} : n ≠ 0 → 1 < bit0 n

ink

theorem Nat.bit0_lt {n : ℕ} {m : ℕ} (h : n < m) : bit0 n < bit0 m

ink

theorem Nat.bit1_lt {n : ℕ} {m : ℕ} (h : n < m) : bit1 n < bit1 m

ink

theorem Nat.bit0_lt_bit1 {n : ℕ} {m : ℕ} (h : n ≤ m) : bit0 n < bit1 m

ink

theorem Nat.bit1_lt_bit0 {n : ℕ} {m : ℕ} : n < m → bit1 n < bit0 m

ink

theorem Nat.one_le_bit1 (n : ℕ) : 1 ≤ bit1 n

ink

theorem Nat.one_le_bit0 (n : ℕ) : n ≠ 0 → 1 ≤ bit0 n

ink

def Nat.discriminate {n : ℕ} {α : Sort u_1} (H1 : n = 0 → α) (H2 : (m : ℕ) → n = Nat.succ m → α) : α

Equations

• Nat.discriminate H1 H2 = match n, H1, H2 with | 0, H1, H2 => H1 Nat.discriminate.proof_1 | Nat.succ m, H1, H2 => H2 m (_ : Nat.succ m = Nat.succ m)

ink

theorem Nat.one_eq_succ_zero : 1 = Nat.succ 0

ink

def Nat.two_step_induction {P : ℕ → Sort u} (H1 : P 0) (H2 : P 1) (H3 : (n : ℕ) → P n → P (Nat.succ n) → P (Nat.succ (Nat.succ n))) (a : ℕ) : P a

Equations

• Nat.two_step_induction H1 H2 H3 0 = H1
• Nat.two_step_induction H1 H2 H3 1 = H2
• Nat.two_step_induction H1 H2 H3 (Nat.succ (Nat.succ n)) = H3 n (Nat.two_step_induction H1 H2 H3 n) (Nat.two_step_induction H1 H2 H3 (Nat.succ n))

ink

def Nat.sub_induction {P : ℕ → ℕ → Sort u} (H1 : (m : ℕ) → P 0 m) (H2 : (n : ℕ) → P (Nat.succ n) 0) (H3 : (n m : ℕ) → P n m → P (Nat.succ n) (Nat.succ m)) (n : ℕ) (m : ℕ) : P n m

Equations

• Nat.sub_induction H1 H2 H3 0 x = H1 x
• Nat.sub_induction H1 H2 H3 (Nat.succ n) 0 = H2 n
• Nat.sub_induction H1 H2 H3 (Nat.succ n) (Nat.succ m) = H3 n m (Nat.sub_induction H1 H2 H3 n m)

ink

def Nat.lt_ge_by_cases {a : ℕ} {b : ℕ} {C : Sort u} (h₁ : a < b → C) (h₂ : b ≤ a → C) : C

Equations

• Nat.lt_ge_by_cases h₁ h₂ = if h : a < b then h₁ h else h₂ (_ : b ≤ a)

ink

def Nat.lt_by_cases {a : ℕ} {b : ℕ} {C : Sort u} (h₁ : a < b → C) (h₂ : a = b → C) (h₃ : b < a → C) : C

Equations

• Nat.lt_by_cases h₁ h₂ h₃ = Nat.lt_ge_by_cases h₁ fun h₁ => Nat.lt_ge_by_cases h₃ fun h => h₂ (_ : a = b)

ink

def Nat.findX {p : ℕ → Prop} [inst : DecidablePred p] (H : ∃ n, p n) : { n // p n ∧ ∀ (m : ℕ), m < n → ¬p m }

Used in the definition of Nat.find. Returns the smallest natural satisfying p

Equations

• One or more equations did not get rendered due to their size.

ink

def Nat.find {p : ℕ → Prop} [inst : DecidablePred p] (H : ∃ n, p n) : ℕ

If p is a (decidable) predicate on ℕ and hp : ∃ (n : ℕ), p n∃ (n : ℕ), p n is a proof that there exists some natural number satisfying p, then Nat.find hp is the smallest natural number satisfying p. Note that Nat.find is protected, meaning that you can't just write find, even if the Nat namespace is open.

The API for Nat.find is:

• Nat.find_spec is the proof that Nat.find hp satisfies p.
• Nat.find_min is the proof that if m < Nat.find hp then m does not satisfy p.
• Nat.find_min' is the proof that if m does satisfy p then Nat.find hp ≤ m≤ m.

Equations

• Nat.find H = (Nat.findX H).val

ink

theorem Nat.find_spec {p : ℕ → Prop} [inst : DecidablePred p] (H : ∃ n, p n) : p (Nat.find H)

ink

theorem Nat.find_min {p : ℕ → Prop} [inst : DecidablePred p] (H : ∃ n, p n) {m : ℕ} : m < Nat.find H → ¬p m

ink

theorem Nat.find_min' {p : ℕ → Prop} [inst : DecidablePred p] (H : ∃ n, p n) {m : ℕ} (h : p m) : Nat.find H ≤ m

ink

theorem Nat.cond_decide_mod_two (x : ℕ) [d : Decidable (x % 2 = 1)] : (bif decide (x % 2 = 1) then 1 else 0) = x % 2

ink

theorem Nat.to_digits_core_lens_eq_aux (b : ℕ) (f : ℕ) (n : ℕ) (l1 : List Char) (l2 : List Char) : List.length l1 = List.length l2 → List.length (Nat.toDigitsCore b f n l1) = List.length (Nat.toDigitsCore b f n l2)

ink

theorem Nat.to_digits_core_lens_eq (b : ℕ) (f : ℕ) (n : ℕ) (c : Char) (tl : List Char) : List.length (Nat.toDigitsCore b f n (c :: tl)) = List.length (Nat.toDigitsCore b f n tl) + 1

ink

theorem Nat.nat_repr_len_aux (n : ℕ) (b : ℕ) (e : ℕ) (h_b_pos : 0 < b) : n < b ^ Nat.succ e → n / b < b ^ e

ink

theorem Nat.to_digits_core_length (b : ℕ) (h : 2 ≤ b) (f : ℕ) (n : ℕ) (e : ℕ) (hlt : n < b ^ e) (h_e_pos : 0 < e) : List.length (Nat.toDigitsCore b f n []) ≤ e

The String representation produced by toDigitsCore has the proper length relative to the number of digits in n < e for some base b. Since this works with any base greater than one, it can be used for binary, decimal, and hex.

ink

theorem Nat.repr_length (n : ℕ) (e : ℕ) : 0 < e → n < 10 ^ e → String.length (Nat.repr n) ≤ e

The core implementation of Nat.repr returns a String with length less than or equal to the number of digits in the decimal number (represented by e). For example, the decimal string representation of any number less than 1000 (10 ^ 3) has a length less than or equal to 3.