# Documentation

Mathlib.Init.Data.Nat.Lemmas

multiplication

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

properties of inequality

theorem Nat.lt_of_le_and_ne {m : } {n : } (h1 : m n) :
m nm < n
def Nat.ltGeByCases {a : } {b : } {C : Sort u} (h₁ : a < bC) (h₂ : b aC) :
C
Instances For
def Nat.ltByCases {a : } {b : } {C : Sort u} (h₁ : a < bC) (h₂ : a = bC) (h₃ : b < aC) :
C
Instances For

bit0/bit1 properties

theorem Nat.bit1_ne_one {n : } :
n 0bit1 n 1
theorem Nat.bit0_ne_one (n : ) :
bit0 n 1
theorem Nat.bit1_ne_bit0 (n : ) (m : ) :
theorem Nat.bit0_ne_bit1 (n : ) (m : ) :
theorem Nat.bit0_inj {n : } {m : } :
bit0 n = bit0 mn = m
theorem Nat.bit1_inj {n : } {m : } :
bit1 n = bit1 mn = m
theorem Nat.bit0_ne {n : } {m : } :
n mbit0 n bit0 m
theorem Nat.bit1_ne {n : } {m : } :
n mbit1 n bit1 m
theorem Nat.zero_ne_bit0 {n : } :
n 00 bit0 n
theorem Nat.zero_ne_bit1 (n : ) :
0 bit1 n
theorem Nat.one_ne_bit0 (n : ) :
1 bit0 n
theorem Nat.one_ne_bit1 {n : } :
n 01 bit1 n
theorem Nat.one_lt_bit1 {n : } :
n 01 < bit1 n
theorem Nat.one_lt_bit0 {n : } :
n 01 < bit0 n
theorem Nat.bit0_lt {n : } {m : } (h : n < m) :
bit0 n < bit0 m
theorem Nat.bit1_lt {n : } {m : } (h : n < m) :
bit1 n < bit1 m
theorem Nat.bit0_lt_bit1 {n : } {m : } (h : n m) :
bit0 n < bit1 m
theorem Nat.bit1_lt_bit0 {n : } {m : } :
n < mbit1 n < bit0 m
theorem Nat.one_le_bit1 (n : ) :
1 bit1 n
theorem Nat.one_le_bit0 (n : ) :
n 01 bit0 n

successor and predecessor

def Nat.discriminate {B : Sort u} {n : } (H1 : n = 0B) (H2 : (m : ) → n = B) :
B
Instances For

subtraction

Many lemmas are proven more generally in mathlib algebra/order/sub

theorem Nat.le_sub_iff_right {x : } {y : } {k : } (h : k y) :
x y - k x + k y
theorem Nat.sub.right_comm (m : ) (n : ) (k : ) :
m - n - k = m - k - n

min

induction principles

def Nat.twoStepInduction {P : Sort u} (H1 : P 0) (H2 : P 1) (H3 : (n : ) → P nP ()P (Nat.succ ())) (a : ) :
P a
Equations
Instances For
def Nat.subInduction {P : Sort u} (H1 : (m : ) → P 0 m) (H2 : (n : ) → P () 0) (H3 : (n m : ) → P n mP () ()) (n : ) (m : ) :
P n m
Equations
Instances For
theorem Nat.strong_induction_on {p : } (n : ) (h : (n : ) → ((m : ) → m < np m) → p n) :
p n
theorem Nat.case_strong_induction_on {p : } (a : ) (hz : p 0) (hi : (n : ) → ((m : ) → m np m) → p ()) :
p a

mod

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

div

theorem Nat.mul_div_mul {m : } (n : ) (k : ) (H : 0 < m) :
m * n / (m * k) = n / k

dvd

instance Nat.decidableDvd :
DecidableRel fun x x_1 => x x_1

find

def Nat.findX {p : } [] (H : n, p n) :
{ n // p n ∀ (m : ), m < n¬p m }
Instances For
def Nat.find {p : } [] (H : n, p n) :

If p is a (decidable) predicate on ℕ and hp : ∃ (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.
Instances For
theorem Nat.find_spec {p : } [] (H : n, p n) :
p ()
theorem Nat.find_min {p : } [] (H : n, p n) {m : } :
m < ¬p m
theorem Nat.find_min' {p : } [] (H : n, p n) {m : } (h : p m) :
m
theorem Nat.to_digits_core_lens_eq_aux (b : ) (f : ) (n : ) (l1 : ) (l2 : ) :
theorem Nat.to_digits_core_lens_eq (b : ) (f : ) (n : ) (c : Char) (tl : ) :
theorem Nat.nat_repr_len_aux (n : ) (b : ) (e : ) (h_b_pos : 0 < b) :
n < b ^ n / b < b ^ e
theorem Nat.to_digits_core_length (b : ) (h : 2 b) (f : ) (n : ) (e : ) (hlt : n < b ^ e) (h_e_pos : 0 < 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.

theorem Nat.repr_length (n : ) (e : ) :
0 < en < 10 ^ e 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.