Documentation

Mathlib.Data.ENat.Basic

Definition and basic properties of extended natural numbers #

In this file we define ENat (notation: ℕ∞) to be WithTop ℕ and prove some basic lemmas about this type.

Implementation details #

There are two natural coercions from ℕ to WithTop ℕ = ENat: WithTop.some and Nat.cast. In Lean 3, this difference was hidden in typeclass instances. Since these instances were definitionally equal, we did not duplicate generic lemmas about WithTop α and WithTop.some coercion for ENat and Nat.cast coercion. If you need to apply a lemma about WithTop, you may either rewrite back and forth using ENat.some_eq_coe, or restate the lemma for ENat.

TODO #

Unify ENat.add_iSup/ENat.iSup_add with ENNReal.add_iSup/ENNReal.iSup_add. The key property of ENat and ENNReal we are using is that all a are either absorbing for addition (a + b = a for all b), or that it's order-cancellable (a + b ≤ a + c → b ≤ c for all b, c), and similarly for multiplication.

instance instENatZero :

Equations

instENatZero = WithTop.zero

instance instENatCanonicallyOrderedCommSemiring :

CanonicallyOrderedCommSemiring ℕ∞

Equations

instENatCanonicallyOrderedCommSemiring = WithTop.instCanonicallyOrderedCommSemiringOfNontrivial

instance instENatNontrivial :

Nontrivial ℕ∞

Equations

instENatNontrivial = ⋯

instance instENatLinearOrder :

LinearOrder ℕ∞

Equations

instENatLinearOrder = WithTop.linearOrder

instance instENatBot :

Equations

instENatBot = WithTop.instBot

instance instENatCanonicallyLinearOrderedAddCommMonoid :

CanonicallyLinearOrderedAddCommMonoid ℕ∞

Equations

instENatCanonicallyLinearOrderedAddCommMonoid = WithTop.instCanonicallyLinearOrderedAddCommMonoid

instance instENatSub :

Equations

instENatSub = WithTop.instSub

instance instENatLinearOrderedAddCommMonoidWithTop :

LinearOrderedAddCommMonoidWithTop ℕ∞

Equations

instENatLinearOrderedAddCommMonoidWithTop = WithTop.linearOrderedAddCommMonoidWithTop

instance instENatWellFoundedRelation :

WellFoundedRelation ℕ∞

Equations

instENatWellFoundedRelation = instWellFoundedRelationOfSizeOf

instance ENat.instOrderBot :

OrderBot ℕ∞

Equations

ENat.instOrderBot = WithTop.orderBot

instance ENat.instOrderTop :

OrderTop ℕ∞

Equations

ENat.instOrderTop = WithTop.orderTop

instance ENat.instOrderedSub :

OrderedSub ℕ∞

instance ENat.instSuccOrder :

SuccOrder ℕ∞

Equations

ENat.instSuccOrder = inferInstanceAs (SuccOrder (WithTop ℕ))

instance ENat.instWellFoundedLT :

WellFoundedLT ℕ∞

instance ENat.instCharZero :

CharZero ℕ∞

@[simp]

theorem ENat.some_eq_coe :

WithTop.some = Nat.cast

Lemmas about WithTop expect (and can output) WithTop.some but the normal form for coercion ℕ → ℕ∞ is Nat.cast.

theorem ENat.coe_inj {a b : ℕ} :

↑a = ↑b ↔ a = b

instance ENat.instSuccAddOrder :

SuccAddOrder ℕ∞

Equations

ENat.instSuccAddOrder = SuccAddOrder.mk ENat.instSuccAddOrder.proof_1

theorem ENat.coe_zero :

↑0 = 0

theorem ENat.coe_one :

↑1 = 1

theorem ENat.coe_add (m n : ℕ) :

↑(m + n) = ↑m + ↑n

@[simp]

theorem ENat.coe_sub (m n : ℕ) :

↑(m - n) = ↑m - ↑n

@[simp]

theorem ENat.coe_mul (m n : ℕ) :

↑(m * n) = ↑m * ↑n

@[simp]

theorem ENat.mul_top {m : ℕ∞} (hm : m ≠ 0) :

@[simp]

theorem ENat.top_mul {m : ℕ∞} (hm : m ≠ 0) :

theorem ENat.top_pow {n : ℕ} (n_pos : 0 < n) :

def ENat.lift (x : ℕ∞) (h : x < ⊤) :

Convert a ℕ∞ to a ℕ using a proof that it is not infinite.

Equations

x.lift h = WithTop.untop x ⋯

Instances For

@[simp]

theorem ENat.coe_lift (x : ℕ∞) (h : x < ⊤) :

↑(x.lift h) = x

@[simp]

theorem ENat.lift_coe (n : ℕ) :

(↑n).lift ⋯ = n

@[simp]

theorem ENat.lift_lt_iff {x : ℕ∞} {h : x < ⊤} {n : ℕ} :

x.lift h < n ↔ x < ↑n

@[simp]

theorem ENat.lift_le_iff {x : ℕ∞} {h : x < ⊤} {n : ℕ} :

x.lift h ≤ n ↔ x ≤ ↑n

@[simp]

theorem ENat.lt_lift_iff {x : ℕ} {n : ℕ∞} {h : n < ⊤} :

x < n.lift h ↔ ↑x < n

@[simp]

theorem ENat.le_lift_iff {x : ℕ} {n : ℕ∞} {h : n < ⊤} :

x ≤ n.lift h ↔ ↑x ≤ n

@[simp]

theorem ENat.lift_zero :

ENat.lift 0 ⋯ = 0

@[simp]

theorem ENat.lift_one :

ENat.lift 1 ⋯ = 1

@[simp]

theorem ENat.lift_ofNat (n : ℕ) [n.AtLeastTwo] :

(OfNat.ofNat n).lift ⋯ = OfNat.ofNat n

@[simp]

theorem ENat.add_lt_top {a b : ℕ∞} :

a + b < ⊤ ↔ a < ⊤ ∧ b < ⊤

@[simp]

theorem ENat.lift_add (a b : ℕ∞) (h : a + b < ⊤) :

(a + b).lift h = a.lift ⋯ + b.lift ⋯

instance ENat.canLift :

CanLift ℕ∞ ℕ Nat.cast fun (x : ℕ∞) => x ≠ ⊤

instance ENat.instWellFoundedRelation :

WellFoundedRelation ℕ∞

Equations

ENat.instWellFoundedRelation = { rel := fun (x1 x2 : ℕ∞) => x1 < x2, wf := ENat.instWellFoundedRelation.proof_1 }

def ENat.toNat :

Conversion of ℕ∞ to ℕ sending ∞ to 0.

Equations

ENat.toNat = WithTop.untop' 0

Instances For

def ENat.toNatHom :

ℕ∞ →*₀ ℕ

Homomorphism from ℕ∞ to ℕ sending ∞ to 0.

Equations

ENat.toNatHom = { toFun := ENat.toNat, map_zero' := ENat.toNatHom.proof_1, map_one' := ENat.toNatHom.proof_2, map_mul' := ENat.toNatHom.proof_3 }

Instances For

@[simp]

theorem ENat.coe_toNatHom :

⇑ENat.toNatHom = ENat.toNat

theorem ENat.toNatHom_apply (n : ℕ) :

ENat.toNatHom ↑n = (↑n).toNat

@[simp]

theorem ENat.toNat_coe (n : ℕ) :

(↑n).toNat = n

@[simp]

theorem ENat.toNat_zero :

ENat.toNat 0 = 0

@[simp]

theorem ENat.toNat_one :

ENat.toNat 1 = 1

@[simp]

theorem ENat.toNat_ofNat (n : ℕ) [n.AtLeastTwo] :

(OfNat.ofNat n).toNat = n

@[simp]

theorem ENat.toNat_top :

⊤.toNat = 0

@[simp]

theorem ENat.toNat_eq_zero {n : ℕ∞} :

n.toNat = 0 ↔ n = 0 ∨ n = ⊤

@[simp]

theorem ENat.recTopCoe_zero {C : ℕ∞ → Sort u_1} (d : C ⊤) (f : (a : ℕ) → C ↑a) :

ENat.recTopCoe d f 0 = f 0

@[simp]

theorem ENat.recTopCoe_one {C : ℕ∞ → Sort u_1} (d : C ⊤) (f : (a : ℕ) → C ↑a) :

ENat.recTopCoe d f 1 = f 1

@[simp]

theorem ENat.recTopCoe_ofNat {C : ℕ∞ → Sort u_1} (d : C ⊤) (f : (a : ℕ) → C ↑a) (x : ℕ) [x.AtLeastTwo] :

ENat.recTopCoe d f (OfNat.ofNat x) = f (OfNat.ofNat x)

@[simp]

theorem ENat.top_ne_coe (a : ℕ) :

⊤ ≠ ↑a

@[simp]

theorem ENat.top_ne_ofNat (a : ℕ) [a.AtLeastTwo] :

⊤ ≠ OfNat.ofNat a

@[simp]

theorem ENat.top_ne_zero :

@[simp]

theorem ENat.top_ne_one :

@[simp]

theorem ENat.coe_ne_top (a : ℕ) :

↑a ≠ ⊤

@[simp]

theorem ENat.ofNat_ne_top (a : ℕ) [a.AtLeastTwo] :

OfNat.ofNat a ≠ ⊤

@[simp]

theorem ENat.zero_ne_top :

@[simp]

theorem ENat.one_ne_top :

@[simp]

theorem ENat.top_sub_coe (a : ℕ) :

⊤ - ↑a = ⊤

@[simp]

theorem ENat.top_sub_one :

@[simp]

theorem ENat.top_sub_ofNat (a : ℕ) [a.AtLeastTwo] :

⊤ - OfNat.ofNat a = ⊤

@[simp]

theorem ENat.top_pos :

@[deprecated ENat.top_pos]

theorem ENat.zero_lt_top :

Alias of ENat.top_pos.

theorem ENat.sub_top (a : ℕ∞) :

a - ⊤ = 0

@[simp]

theorem ENat.coe_toNat_eq_self {n : ℕ∞} :

↑n.toNat = n ↔ n ≠ ⊤

theorem ENat.coe_toNat {n : ℕ∞} :

n ≠ ⊤ → ↑n.toNat = n

Alias of the reverse direction of ENat.coe_toNat_eq_self.

theorem ENat.coe_toNat_le_self (n : ℕ∞) :

↑n.toNat ≤ n

theorem ENat.toNat_add {m n : ℕ∞} (hm : m ≠ ⊤) (hn : n ≠ ⊤) :

(m + n).toNat = m.toNat + n.toNat

theorem ENat.toNat_sub {n : ℕ∞} (hn : n ≠ ⊤) (m : ℕ∞) :

(m - n).toNat = m.toNat - n.toNat

theorem ENat.toNat_eq_iff {m : ℕ∞} {n : ℕ} (hn : n ≠ 0) :

m.toNat = n ↔ m = ↑n

theorem ENat.toNat_le_of_le_coe {m : ℕ∞} {n : ℕ} (h : m ≤ ↑n) :

m.toNat ≤ n

theorem ENat.toNat_le_toNat {m n : ℕ∞} (h : m ≤ n) (hn : n ≠ ⊤) :

m.toNat ≤ n.toNat

@[simp]

theorem ENat.succ_def (m : ℕ∞) :

Order.succ m = m + 1

@[deprecated Order.add_one_le_of_lt]

theorem ENat.add_one_le_of_lt {m n : ℕ∞} (h : m < n) :

m + 1 ≤ n

theorem ENat.add_one_le_iff {m n : ℕ∞} (hm : m ≠ ⊤) :

m + 1 ≤ n ↔ m < n

@[deprecated Order.one_le_iff_pos]

theorem ENat.one_le_iff_pos {n : ℕ∞} :

1 ≤ n ↔ 0 < n

theorem ENat.one_le_iff_ne_zero {n : ℕ∞} :

1 ≤ n ↔ n ≠ 0

theorem ENat.lt_one_iff_eq_zero {n : ℕ∞} :

n < 1 ↔ n = 0

@[deprecated Order.le_of_lt_add_one]

theorem ENat.le_of_lt_add_one {m n : ℕ∞} (h : m < n + 1) :

m ≤ n

theorem ENat.lt_add_one_iff {m n : ℕ∞} (hm : n ≠ ⊤) :

m < n + 1 ↔ m ≤ n

theorem ENat.le_coe_iff {n : ℕ∞} {k : ℕ} :

n ≤ ↑k ↔ ∃ (n₀ : ℕ), n = ↑n₀ ∧ n₀ ≤ k

@[simp]

theorem ENat.not_lt_zero (n : ℕ∞) :

¬n < 0

@[simp]

theorem ENat.coe_lt_top (n : ℕ) :

↑n < ⊤

theorem ENat.coe_lt_coe {n m : ℕ} :

↑n < ↑m ↔ n < m

theorem ENat.coe_le_coe {n m : ℕ} :

↑n ≤ ↑m ↔ n ≤ m

theorem ENat.nat_induction {P : ℕ∞ → Prop} (a : ℕ∞) (h0 : P 0) (hsuc : ∀ (n : ℕ), P ↑n → P ↑n.succ) (htop : (∀ (n : ℕ), P ↑n) → P ⊤) :

P a

theorem ENat.add_one_pos {n : ℕ∞} :

0 < n + 1

theorem ENat.add_lt_add_iff_right {m n k : ℕ∞} (h : k ≠ ⊤) :

n + k < m + k ↔ n < m

theorem ENat.add_lt_add_iff_left {m n k : ℕ∞} (h : k ≠ ⊤) :

k + n < k + m ↔ n < m

theorem ENat.exists_nat_gt {n : ℕ∞} (hn : n ≠ ⊤) :

∃ (m : ℕ), n < ↑m

theorem ENat.ne_top_iff_exists {x : ℕ∞} :

x ≠ ⊤ ↔ ∃ (a : ℕ), ↑a = x

@[simp]

theorem ENat.sub_eq_top_iff {a b : ℕ∞} :

a - b = ⊤ ↔ a = ⊤ ∧ b ≠ ⊤

theorem ENat.sub_ne_top_iff {a b : ℕ∞} :

a - b ≠ ⊤ ↔ a ≠ ⊤ ∨ b = ⊤

theorem ENat.addLECancellable_of_ne_top {a : ℕ∞} :

a ≠ ⊤ → AddLECancellable a

theorem ENat.addLECancellable_of_lt_top {a : ℕ∞} :

a < ⊤ → AddLECancellable a

theorem ENat.le_sub_of_add_le_left {a b c : ℕ∞} (ha : a ≠ ⊤) :

a + b ≤ c → b ≤ c - a

theorem ENat.sub_sub_cancel {a b : ℕ∞} (h : a ≠ ⊤) (h2 : b ≤ a) :

a - (a - b) = b

theorem ENat.add_one_natCast_le_withTop_of_lt {m : ℕ} {n : WithTop ℕ∞} (h : ↑m < n) :

↑(m + 1) ≤ n

@[simp]

theorem ENat.coe_top_add_one :

↑⊤ + 1 = ↑⊤

@[simp]

theorem ENat.add_one_eq_coe_top_iff {n : WithTop ℕ∞} :

n + 1 = ↑⊤ ↔ n = ↑⊤

@[simp]

theorem ENat.natCast_ne_coe_top (n : ℕ) :

↑n ≠ ↑⊤

@[deprecated ENat.natCast_ne_coe_top]

theorem ENat.nat_ne_coe_top (n : ℕ) :

↑n ≠ ↑⊤

Alias of ENat.natCast_ne_coe_top.

theorem ENat.one_le_iff_ne_zero_withTop {n : WithTop ℕ∞} :

1 ≤ n ↔ n ≠ 0

theorem ENat.natCast_le_of_coe_top_le_withTop {N : WithTop ℕ∞} (hN : ↑⊤ ≤ N) (n : ℕ) :

↑n ≤ N

theorem ENat.natCast_lt_of_coe_top_le_withTop {N : WithTop ℕ∞} (hN : ↑⊤ ≤ N) (n : ℕ) :

↑n < N

def ENat.map {α : Type u_1} (f : ℕ → α) (k : ℕ∞) :

Specialization of WithTop.map to ENat.

Equations

ENat.map f k = WithTop.map f k

Instances For

@[simp]

theorem ENat.map_top {α : Type u_1} (f : ℕ → α) :

ENat.map f ⊤ = ⊤

@[simp]

theorem ENat.map_coe {α : Type u_1} (f : ℕ → α) (a : ℕ) :

ENat.map f ↑a = ↑(f a)

@[simp]

theorem ENat.map_zero {α : Type u_1} (f : ℕ → α) :

ENat.map f 0 = ↑(f 0)

@[simp]

theorem ENat.map_one {α : Type u_1} (f : ℕ → α) :

ENat.map f 1 = ↑(f 1)

@[simp]

theorem ENat.map_ofNat {α : Type u_1} (f : ℕ → α) (n : ℕ) [n.AtLeastTwo] :

ENat.map f (OfNat.ofNat n) = ↑(f n)

@[simp]

theorem ENat.map_eq_top_iff {n : ℕ∞} {α : Type u_1} {f : ℕ → α} :

ENat.map f n = ⊤ ↔ n = ⊤

@[simp]

theorem ENat.map_natCast_nonneg {n : ℕ∞} {α : Type u_1} [AddMonoidWithOne α] [PartialOrder α] [AddLeftMono α] [ZeroLEOneClass α] :

0 ≤ ENat.map Nat.cast n

@[simp]

theorem ENat.strictMono_map_iff {α : Type u_1} {f : ℕ → α} [Preorder α] :

StrictMono (ENat.map f) ↔ StrictMono f

@[simp]

theorem ENat.monotone_map_iff {α : Type u_1} {f : ℕ → α} [Preorder α] :

Monotone (ENat.map f) ↔ Monotone f

@[simp]

theorem ENat.map_add {β : Type u_2} {F : Type u_3} [Add β] [FunLike F ℕ β] [AddHomClass F ℕ β] (f : F) (a b : ℕ∞) :

ENat.map (⇑f) (a + b) = ENat.map (⇑f) a + ENat.map (⇑f) b

def OneHom.ENatMap {N : Type u_2} [One N] (f : OneHom ℕ N) :

OneHom ℕ∞ (WithTop N)

A version of ENat.map for OneHoms.

Equations

f.ENatMap = { toFun := ENat.map ⇑f, map_one' := ⋯ }

Instances For

def ZeroHom.ENatMap {N : Type u_2} [Zero N] (f : ZeroHom ℕ N) :

ZeroHom ℕ∞ (WithTop N)

A version of ENat.map for ZeroHoms.

Equations

f.ENatMap = { toFun := ENat.map ⇑f, map_zero' := ⋯ }

Instances For

def AddHom.ENatMap {N : Type u_2} [Add N] (f : ℕ →ₙ+ N) :

ℕ∞ →ₙ+ WithTop N

A version of WithTop.map for AddHoms.

Equations

f.ENatMap = { toFun := ENat.map ⇑f, map_add' := ⋯ }

Instances For

@[simp]

theorem AddHom.ENatMap_apply {N : Type u_2} [Add N] (f : ℕ →ₙ+ N) :

⇑f.ENatMap = ENat.map ⇑f

def AddMonoidHom.ENatMap {N : Type u_2} [AddZeroClass N] (f : ℕ →+ N) :

ℕ∞ →+ WithTop N

A version of WithTop.map for AddMonoidHoms.

Equations

f.ENatMap = { toFun := ENat.map ⇑f, map_zero' := ⋯, map_add' := ⋯ }

Instances For

@[simp]

theorem AddMonoidHom.ENatMap_apply {N : Type u_2} [AddZeroClass N] (f : ℕ →+ N) :

⇑f.ENatMap = ENat.map ⇑f

def MonoidWithZeroHom.ENatMap {S : Type u_2} [MulZeroOneClass S] [DecidableEq S] [Nontrivial S] (f : ℕ →*₀ S) (hf : Function.Injective ⇑f) :

ℕ∞ →*₀ WithTop S

A version of ENat.map for MonoidWithZeroHoms.

Equations

f.ENatMap hf = { toFun := ENat.map ⇑f, map_zero' := ⋯, map_one' := ⋯, map_mul' := ⋯ }

Instances For

@[simp]

theorem MonoidWithZeroHom.ENatMap_apply {S : Type u_2} [MulZeroOneClass S] [DecidableEq S] [Nontrivial S] (f : ℕ →*₀ S) (hf : Function.Injective ⇑f) :

⇑(f.ENatMap hf) = ENat.map ⇑f

def RingHom.ENatMap {S : Type u_2} [CanonicallyOrderedCommSemiring S] [DecidableEq S] [Nontrivial S] (f : ℕ →+* S) (hf : Function.Injective ⇑f) :

ℕ∞ →+* WithTop S

A version of ENat.map for RingHoms.

Equations

f.ENatMap hf = { toFun := (↑(f.toMonoidWithZeroHom.ENatMap hf)).toFun, map_one' := ⋯, map_mul' := ⋯, map_zero' := ⋯, map_add' := ⋯ }

Instances For

@[simp]

theorem RingHom.ENatMap_apply {S : Type u_2} [CanonicallyOrderedCommSemiring S] [DecidableEq S] [Nontrivial S] (f : ℕ →+* S) (hf : Function.Injective ⇑f) :

⇑(f.ENatMap hf) = (↑(f.toMonoidWithZeroHom.ENatMap hf)).toFun