Documentation

Mathlib.Init.Data.Nat.Lemmas

addition

multiplication

theorem Nat.eq_zero_of_mul_eq_zero {n : ℕ} {m : ℕ} :

n * m = 0 → n = 0 ∨ m = 0

properties of inequality

instance Nat.instLinearOrder :

LinearOrder ℕ

Equations

Nat.instLinearOrder = LinearOrder.mk Nat.le_total inferInstance inferInstance inferInstance Nat.instLinearOrder.proof_1 Nat.instLinearOrder.proof_2 Nat.instLinearOrder.proof_3

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

C

Equations

Nat.ltGeByCases h₁ h₂ = Decidable.byCases h₁ fun (h : ¬a < b) => h₂ ⋯

Instances For

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

C

Equations

Nat.ltByCases h₁ h₂ h₃ = Nat.ltGeByCases h₁ fun (h₁ : b ≤ a) => Nat.ltGeByCases h₃ fun (h : a ≤ b) => h₂ ⋯

Instances For

bit0/bit1 properties

theorem Nat.bit1_eq_succ_bit0 (n : ℕ) :

bit1 n = Nat.succ (bit0 n)

theorem Nat.bit1_succ_eq (n : ℕ) :

bit1 (Nat.succ n) = Nat.succ (Nat.succ (bit1 n))

theorem Nat.bit1_ne_one {n : ℕ} :

n ≠ 0 → bit1 n ≠ 1

theorem Nat.bit0_ne_one (n : ℕ) :

theorem Nat.bit1_ne_bit0 (n : ℕ) (m : ℕ) :

bit1 n ≠ bit0 m

theorem Nat.bit0_ne_bit1 (n : ℕ) (m : ℕ) :

bit0 n ≠ bit1 m

theorem Nat.bit0_inj {n : ℕ} {m : ℕ} :

bit0 n = bit0 m → n = m

theorem Nat.bit1_inj {n : ℕ} {m : ℕ} :

bit1 n = bit1 m → n = m

theorem Nat.bit0_ne {n : ℕ} {m : ℕ} :

n ≠ m → bit0 n ≠ bit0 m

theorem Nat.bit1_ne {n : ℕ} {m : ℕ} :

n ≠ m → bit1 n ≠ bit1 m

theorem Nat.zero_ne_bit0 {n : ℕ} :

n ≠ 0 → 0 ≠ bit0 n

theorem Nat.zero_ne_bit1 (n : ℕ) :

theorem Nat.one_ne_bit0 (n : ℕ) :

theorem Nat.one_ne_bit1 {n : ℕ} :

n ≠ 0 → 1 ≠ bit1 n

theorem Nat.one_lt_bit1 {n : ℕ} :

n ≠ 0 → 1 < bit1 n

theorem Nat.one_lt_bit0 {n : ℕ} :

n ≠ 0 → 1 < 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 < m → bit1 n < bit0 m

theorem Nat.one_le_bit1 (n : ℕ) :

theorem Nat.one_le_bit0 (n : ℕ) :

n ≠ 0 → 1 ≤ bit0 n

successor and predecessor

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

B

Equations

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

Instances For

theorem Nat.one_eq_succ_zero :

subtraction

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

min

induction principles

def Nat.twoStepInduction {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.twoStepInduction H1 H2 H3 0 = H1
Nat.twoStepInduction H1 H2 H3 1 = H2
Nat.twoStepInduction H1 H2 H3 (Nat.succ (Nat.succ _n)) = H3 _n (Nat.twoStepInduction H1 H2 H3 _n) (Nat.twoStepInduction H1 H2 H3 (Nat.succ _n))

Instances For

def Nat.subInduction {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.subInduction H1 H2 H3 0 x = H1 x
Nat.subInduction H1 H2 H3 (Nat.succ _n) 0 = H2 _n
Nat.subInduction H1 H2 H3 (Nat.succ n) (Nat.succ m) = H3 n m (Nat.subInduction H1 H2 H3 n m)

Instances For

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

p n

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

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

dvd

find

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

{ n : ℕ // p n ∧ ∀ (m : ℕ), m < n → ¬p m }

Equations

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

Instances For

def Nat.find {p : ℕ → Prop} [DecidablePred 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.

Equations

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

Instances For

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

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

m < Nat.find H → ¬p m

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

Nat.find H ≤ m