Pointwise order on finitely supported functions

This file lifts order structures on α to ι →₀ α.

Main declarations

• Finsupp.orderEmbeddingToFun: The order embedding from finitely supported functions to functions.

Order structures

instance Finsupp.instLEFinsupp {ι : Type u_1} {α : Type u_2} [Zero α] [LE α] : LE (ι →₀ α)

Equations

• Finsupp.instLEFinsupp = { le := fun (f g : ι →₀ α) => ∀ (i : ι), f i ≤ g i }

theorem Finsupp.le_def {ι : Type u_1} {α : Type u_2} [Zero α] [LE α] {f : ι →₀ α} {g : ι →₀ α} : f ≤ g ↔ ∀ (i : ι), f i ≤ g i

@[simp]

theorem Finsupp.coe_le_coe {ι : Type u_1} {α : Type u_2} [Zero α] [LE α] {f : ι →₀ α} {g : ι →₀ α} : ⇑f ≤ ⇑g ↔ f ≤ g

def Finsupp.orderEmbeddingToFun {ι : Type u_1} {α : Type u_2} [Zero α] [LE α] : (ι →₀ α) ↪o (ι → α)

The order on Finsupps over a partial order embeds into the order on functions

Equations

• Finsupp.orderEmbeddingToFun = { toEmbedding := { toFun := fun (f : ι →₀ α) => ⇑f, inj' := ⋯ }, map_rel_iff' := ⋯ }

@[simp]

theorem Finsupp.orderEmbeddingToFun_apply {ι : Type u_1} {α : Type u_2} [Zero α] [LE α] {f : ι →₀ α} {i : ι} : Finsupp.orderEmbeddingToFun f i = f i

instance Finsupp.preorder {ι : Type u_1} {α : Type u_2} [Zero α] [Preorder α] : Preorder (ι →₀ α)

Equations

• Finsupp.preorder = let __src := Finsupp.instLEFinsupp; Preorder.mk ⋯ ⋯ ⋯

theorem Finsupp.lt_def {ι : Type u_1} {α : Type u_2} [Zero α] [Preorder α] {f : ι →₀ α} {g : ι →₀ α} : f < g ↔ f ≤ g ∧ ∃ (i : ι), f i < g i

@[simp]

theorem Finsupp.coe_lt_coe {ι : Type u_1} {α : Type u_2} [Zero α] [Preorder α] {f : ι →₀ α} {g : ι →₀ α} : ⇑f < ⇑g ↔ f < g

theorem Finsupp.coe_mono {ι : Type u_1} {α : Type u_2} [Zero α] [Preorder α] : Monotone Finsupp.toFun

theorem Finsupp.coe_strictMono {ι : Type u_1} {α : Type u_2} [Zero α] [Preorder α] : Monotone Finsupp.toFun

instance Finsupp.partialorder {ι : Type u_1} {α : Type u_2} [Zero α] [PartialOrder α] : PartialOrder (ι →₀ α)

Equations

• Finsupp.partialorder = let __src := Finsupp.preorder; PartialOrder.mk ⋯

instance Finsupp.semilatticeInf {ι : Type u_1} {α : Type u_2} [Zero α] [SemilatticeInf α] : SemilatticeInf (ι →₀ α)

Equations

• Finsupp.semilatticeInf = let __src := Finsupp.partialorder; SemilatticeInf.mk ⋯ ⋯ ⋯

@[simp]

theorem Finsupp.inf_apply {ι : Type u_1} {α : Type u_2} [Zero α] [SemilatticeInf α] {i : ι} {f : ι →₀ α} {g : ι →₀ α} : (f ⊓ g) i = f i ⊓ g i

instance Finsupp.semilatticeSup {ι : Type u_1} {α : Type u_2} [Zero α] [SemilatticeSup α] : SemilatticeSup (ι →₀ α)

Equations

• Finsupp.semilatticeSup = let __src := Finsupp.partialorder; SemilatticeSup.mk ⋯ ⋯ ⋯

@[simp]

theorem Finsupp.sup_apply {ι : Type u_1} {α : Type u_2} [Zero α] [SemilatticeSup α] {i : ι} {f : ι →₀ α} {g : ι →₀ α} : (f ⊔ g) i = f i ⊔ g i

instance Finsupp.lattice {ι : Type u_1} {α : Type u_2} [Zero α] [Lattice α] : Lattice (ι →₀ α)

Equations

• Finsupp.lattice = let __src := Finsupp.semilatticeInf; let __src_1 := Finsupp.semilatticeSup; Lattice.mk ⋯ ⋯ ⋯

theorem Finsupp.support_inf_union_support_sup {ι : Type u_1} {α : Type u_2} [Zero α] [DecidableEq ι] [Lattice α] (f : ι →₀ α) (g : ι →₀ α) : (f ⊓ g).support ∪ (f ⊔ g).support = f.support ∪ g.support

theorem Finsupp.support_sup_union_support_inf {ι : Type u_1} {α : Type u_2} [Zero α] [DecidableEq ι] [Lattice α] (f : ι →₀ α) (g : ι →₀ α) : (f ⊔ g).support ∪ (f ⊓ g).support = f.support ∪ g.support

Algebraic order structures

instance Finsupp.orderedAddCommMonoid {ι : Type u_1} {α : Type u_2} [OrderedAddCommMonoid α] : OrderedAddCommMonoid (ι →₀ α)

Equations

• Finsupp.orderedAddCommMonoid = let __src := Finsupp.instAddCommMonoid; let __src_1 := Finsupp.partialorder; OrderedAddCommMonoid.mk ⋯

instance Finsupp.orderedCancelAddCommMonoid {ι : Type u_1} {α : Type u_2} [OrderedCancelAddCommMonoid α] : OrderedCancelAddCommMonoid (ι →₀ α)

Equations

• Finsupp.orderedCancelAddCommMonoid = let __src := Finsupp.orderedAddCommMonoid; OrderedCancelAddCommMonoid.mk ⋯

instance Finsupp.contravariantClass {ι : Type u_1} {α : Type u_2} [OrderedAddCommMonoid α] [ContravariantClass α α (fun (x x_1 : α) => x + x_1) fun (x x_1 : α) => x ≤ x_1] : ContravariantClass (ι →₀ α) (ι →₀ α) (fun (x x_1 : ι →₀ α) => x + x_1) fun (x x_1 : ι →₀ α) => x ≤ x_1

Equations

• ⋯ = ⋯

instance Finsupp.instPosSMulMono {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Zero α] [Preorder α] [Zero β] [Preorder β] [SMulZeroClass α β] [PosSMulMono α β] : PosSMulMono α (ι →₀ β)

Equations

• ⋯ = ⋯

instance Finsupp.instSMulPosMono {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Preorder α] [Zero β] [Preorder β] [SMulZeroClass α β] [SMulPosMono α β] : SMulPosMono α (ι →₀ β)

Equations

• ⋯ = ⋯

instance Finsupp.instPosSMulReflectLE {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Zero α] [Preorder α] [Zero β] [Preorder β] [SMulZeroClass α β] [PosSMulReflectLE α β] : PosSMulReflectLE α (ι →₀ β)

Equations

• ⋯ = ⋯

instance Finsupp.instSMulPosReflectLE {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Preorder α] [Zero β] [Preorder β] [SMulZeroClass α β] [SMulPosReflectLE α β] : SMulPosReflectLE α (ι →₀ β)

Equations

• ⋯ = ⋯

instance Finsupp.instPosSMulStrictMono {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Zero α] [PartialOrder α] [Zero β] [PartialOrder β] [SMulWithZero α β] [PosSMulStrictMono α β] : PosSMulStrictMono α (ι →₀ β)

Equations

• ⋯ = ⋯

instance Finsupp.instSMulPosStrictMono {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Zero α] [PartialOrder α] [Zero β] [PartialOrder β] [SMulWithZero α β] [SMulPosStrictMono α β] : SMulPosStrictMono α (ι →₀ β)

Equations

• ⋯ = ⋯

instance Finsupp.instSMulPosReflectLT {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Zero α] [PartialOrder α] [Zero β] [PartialOrder β] [SMulWithZero α β] [SMulPosReflectLT α β] : SMulPosReflectLT α (ι →₀ β)

Equations

• ⋯ = ⋯

instance Finsupp.orderBot {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] : OrderBot (ι →₀ α)

Equations

• Finsupp.orderBot = OrderBot.mk ⋯

theorem Finsupp.bot_eq_zero {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] : ⊥ = 0

@[simp]

theorem Finsupp.add_eq_zero_iff {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] (f : ι →₀ α) (g : ι →₀ α) : f + g = 0 ↔ f = 0 ∧ g = 0

theorem Finsupp.le_iff' {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] (f : ι →₀ α) (g : ι →₀ α) {s : Finset ι} (hf : f.support ⊆ s) : f ≤ g ↔ ∀ i ∈ s, f i ≤ g i

theorem Finsupp.le_iff {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] (f : ι →₀ α) (g : ι →₀ α) : f ≤ g ↔ ∀ i ∈ f.support, f i ≤ g i

theorem Finsupp.support_monotone {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] : Monotone Finsupp.support

theorem Finsupp.support_mono {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] {f : ι →₀ α} {g : ι →₀ α} (hfg : f ≤ g) : f.support ⊆ g.support

instance Finsupp.decidableLE {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [DecidableRel LE.le] : DecidableRel LE.le

Equations

• Finsupp.decidableLE f g = decidable_of_iff (∀ i ∈ f.support, f i ≤ g i) ⋯

instance Finsupp.decidableLT {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [DecidableRel LE.le] : DecidableRel LT.lt

Equations

• Finsupp.decidableLT = decidableLTOfDecidableLE

@[simp]

theorem Finsupp.single_le_iff {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] {i : ι} {x : α} {f : ι →₀ α} : Finsupp.single i x ≤ f ↔ x ≤ f i

instance Finsupp.tsub {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] : Sub (ι →₀ α)

This is called tsub for truncated subtraction, to distinguish it with subtraction in an additive group.

Equations

• Finsupp.tsub = { sub := Finsupp.zipWith (fun (m n : α) => m - n) ⋯ }

instance Finsupp.orderedSub {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] : OrderedSub (ι →₀ α)

Equations

• ⋯ = ⋯

instance Finsupp.instCanonicallyOrderedAddCommMonoidFinsuppToZeroToAddMonoidToAddCommMonoidToOrderedAddCommMonoid {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] : CanonicallyOrderedAddCommMonoid (ι →₀ α)

Equations

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

@[simp]

theorem Finsupp.coe_tsub {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] (f : ι →₀ α) (g : ι →₀ α) : ⇑(f - g) = ⇑f - ⇑g

theorem Finsupp.tsub_apply {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] (f : ι →₀ α) (g : ι →₀ α) (a : ι) : (f - g) a = f a - g a

@[simp]

theorem Finsupp.single_tsub {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] {i : ι} {a : α} {b : α} : Finsupp.single i (a - b) = Finsupp.single i a - Finsupp.single i b

theorem Finsupp.support_tsub {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] {f1 : ι →₀ α} {f2 : ι →₀ α} : (f1 - f2).support ⊆ f1.support

theorem Finsupp.subset_support_tsub {ι : Type u_1} {α : Type u_2} [CanonicallyOrderedAddCommMonoid α] [Sub α] [OrderedSub α] [DecidableEq ι] {f1 : ι →₀ α} {f2 : ι →₀ α} : f1.support \ f2.support ⊆ (f1 - f2).support

@[simp]

theorem Finsupp.support_inf {ι : Type u_1} {α : Type u_2} [CanonicallyLinearOrderedAddCommMonoid α] [DecidableEq ι] (f : ι →₀ α) (g : ι →₀ α) : (f ⊓ g).support = f.support ∩ g.support

@[simp]

theorem Finsupp.support_sup {ι : Type u_1} {α : Type u_2} [CanonicallyLinearOrderedAddCommMonoid α] [DecidableEq ι] (f : ι →₀ α) (g : ι →₀ α) : (f ⊔ g).support = f.support ∪ g.support

theorem Finsupp.disjoint_iff {ι : Type u_1} {α : Type u_2} [CanonicallyLinearOrderedAddCommMonoid α] {f : ι →₀ α} {g : ι →₀ α} : Disjoint f g ↔ Disjoint f.support g.support

Some lemmas about ℕ

theorem Finsupp.sub_single_one_add {ι : Type u_1} {a : ι} {u : ι →₀ ℕ} {u' : ι →₀ ℕ} (h : u a ≠ 0) : u - Finsupp.single a 1 + u' = u + u' - Finsupp.single a 1

theorem Finsupp.add_sub_single_one {ι : Type u_1} {a : ι} {u : ι →₀ ℕ} {u' : ι →₀ ℕ} (h : u' a ≠ 0) : u + (u' - Finsupp.single a 1) = u + u' - Finsupp.single a 1