Documentation

Mathlib.Order.SupIndep

Supremum independence #

In this file, we define supremum independence of indexed sets. An indexed family f : ι → α→ α is sup-independent if, for all a, f a and the supremum of the rest are disjoint.

Main definitions #

Main statements #

Implementation notes #

For the finite version, we avoid the "obvious" definition ∀ i ∈ s, Disjoint (f i) ((s.erase i).sup f)∀ i ∈ s, Disjoint (f i) ((s.erase i).sup f)∈ s, Disjoint (f i) ((s.erase i).sup f) because erase would require decidable equality on ι.

On lattices with a bottom element, via Finset.sup #

def Finset.SupIndep {α : Type u_1} {ι : Type u_2} [inst : Lattice α] [inst : OrderBot α] (s : Finset ι) (f : ια) :

Supremum independence of finite sets. We avoid the "obvious" definition using s.erase i because erase would require decidable equality on ι.

Equations
instance Finset.instDecidableSupIndep {α : Type u_1} {ι : Type u_2} [inst : Lattice α] [inst : OrderBot α] {s : Finset ι} {f : ια} [inst : DecidableEq ι] [inst : DecidableEq α] :
Equations
  • Finset.instDecidableSupIndep = Finset.decidableForallOfDecidableSubsets
theorem Finset.SupIndep.subset {α : Type u_1} {ι : Type u_2} [inst : Lattice α] [inst : OrderBot α] {s : Finset ι} {t : Finset ι} {f : ια} (ht : Finset.SupIndep t f) (h : s t) :
theorem Finset.supIndep_empty {α : Type u_1} {ι : Type u_2} [inst : Lattice α] [inst : OrderBot α] (f : ια) :
theorem Finset.supIndep_singleton {α : Type u_1} {ι : Type u_2} [inst : Lattice α] [inst : OrderBot α] (i : ι) (f : ια) :
theorem Finset.SupIndep.pairwiseDisjoint {α : Type u_1} {ι : Type u_2} [inst : Lattice α] [inst : OrderBot α] {s : Finset ι} {f : ια} (hs : Finset.SupIndep s f) :
theorem Finset.supIndep_iff_disjoint_erase {α : Type u_2} {ι : Type u_1} [inst : Lattice α] [inst : OrderBot α] {s : Finset ι} {f : ια} [inst : DecidableEq ι] :
Finset.SupIndep s f ∀ (i : ι), i sDisjoint (f i) (Finset.sup (Finset.erase s i) f)

The RHS looks like the definition of CompleteLattice.Independent.

@[simp]
theorem Finset.supIndep_pair {α : Type u_2} {ι : Type u_1} [inst : Lattice α] [inst : OrderBot α] {f : ια} [inst : DecidableEq ι] {i : ι} {j : ι} (hij : i j) :
Finset.SupIndep {i, j} f Disjoint (f i) (f j)
theorem Finset.supIndep_univ_bool {α : Type u_1} [inst : Lattice α] [inst : OrderBot α] (f : Boolα) :
Finset.SupIndep Finset.univ f Disjoint (f false) (f true)
@[simp]
theorem Finset.supIndep_univ_fin_two {α : Type u_1} [inst : Lattice α] [inst : OrderBot α] (f : Fin 2α) :
Finset.SupIndep Finset.univ f Disjoint (f 0) (f 1)
theorem Finset.SupIndep.attach {α : Type u_1} {ι : Type u_2} [inst : Lattice α] [inst : OrderBot α] {s : Finset ι} {f : ια} (hs : Finset.SupIndep s f) :
Finset.SupIndep (Finset.attach s) (f Subtype.val)
theorem Finset.supIndep_iff_pairwiseDisjoint {α : Type u_1} {ι : Type u_2} [inst : DistribLattice α] [inst : OrderBot α] {s : Finset ι} {f : ια} :
theorem Set.PairwiseDisjoint.supIndep {α : Type u_1} {ι : Type u_2} [inst : DistribLattice α] [inst : OrderBot α] {s : Finset ι} {f : ια} :

Alias of the reverse direction of Finset.supIndep_iff_pairwiseDisjoint.

theorem Finset.sup_indep.pairwise_disjoint {α : Type u_1} {ι : Type u_2} [inst : DistribLattice α] [inst : OrderBot α] {s : Finset ι} {f : ια} :

Alias of the forward direction of Finset.supIndep_iff_pairwiseDisjoint.

theorem Finset.SupIndep.sup {α : Type u_3} {ι : Type u_1} {ι' : Type u_2} [inst : DistribLattice α] [inst : OrderBot α] [inst : DecidableEq ι] {s : Finset ι'} {g : ι'Finset ι} {f : ια} (hs : Finset.SupIndep s fun i => Finset.sup (g i) f) (hg : ∀ (i' : ι'), i' sFinset.SupIndep (g i') f) :

Bind operation for SupIndep.

theorem Finset.SupIndep.bunionᵢ {α : Type u_3} {ι : Type u_1} {ι' : Type u_2} [inst : DistribLattice α] [inst : OrderBot α] [inst : DecidableEq ι] {s : Finset ι'} {g : ι'Finset ι} {f : ια} (hs : Finset.SupIndep s fun i => Finset.sup (g i) f) (hg : ∀ (i' : ι'), i' sFinset.SupIndep (g i') f) :

Bind operation for SupIndep.

On complete lattices via supₛ #

def CompleteLattice.SetIndependent {α : Type u_1} [inst : CompleteLattice α] (s : Set α) :

An independent set of elements in a complete lattice is one in which every element is disjoint from the Sup of the rest.

Equations

If the elements of a set are independent, then any pair within that set is disjoint.

theorem CompleteLattice.setIndependent_pair {α : Type u_1} [inst : CompleteLattice α] {a : α} {b : α} (hab : a b) :
theorem CompleteLattice.SetIndependent.disjoint_supₛ {α : Type u_1} [inst : CompleteLattice α] {s : Set α} (hs : CompleteLattice.SetIndependent s) {x : α} {y : Set α} (hx : x s) (hy : y s) (hxy : ¬x y) :

If the elements of a set are independent, then any element is disjoint from the supₛ of some subset of the rest.

def CompleteLattice.Independent {ι : Sort u_1} {α : Type u_2} [inst : CompleteLattice α] (t : ια) :

An independent indexed family of elements in a complete lattice is one in which every element is disjoint from the supᵢ of the rest.

Example: an indexed family of non-zero elements in a vector space is linearly independent iff the indexed family of subspaces they generate is independent in this sense.

Example: an indexed family of submodules of a module is independent in this sense if and only the natural map from the direct sum of the submodules to the module is injective.

Equations
theorem CompleteLattice.independent_def {α : Type u_2} {ι : Type u_1} [inst : CompleteLattice α] {t : ια} :
CompleteLattice.Independent t ∀ (i : ι), Disjoint (t i) (j, _H, t j)
theorem CompleteLattice.independent_def' {α : Type u_2} {ι : Type u_1} [inst : CompleteLattice α] {t : ια} :
CompleteLattice.Independent t ∀ (i : ι), Disjoint (t i) (supₛ (t '' { j | j i }))
theorem CompleteLattice.independent_def'' {α : Type u_2} {ι : Type u_1} [inst : CompleteLattice α] {t : ια} :
CompleteLattice.Independent t ∀ (i : ι), Disjoint (t i) (supₛ { a | j x, t j = a })
theorem CompleteLattice.Independent.pairwiseDisjoint {α : Type u_2} {ι : Type u_1} [inst : CompleteLattice α] {t : ια} (ht : CompleteLattice.Independent t) :
Pairwise (Disjoint on t)

If the elements of a set are independent, then any pair within that set is disjoint.

theorem CompleteLattice.Independent.mono {α : Type u_2} {ι : Type u_1} [inst : CompleteLattice α] {s : ια} {t : ια} (hs : CompleteLattice.Independent s) (hst : t s) :
theorem CompleteLattice.Independent.comp {α : Type u_3} [inst : CompleteLattice α] {ι : Sort u_1} {ι' : Sort u_2} {t : ια} {f : ι'ι} (ht : CompleteLattice.Independent t) (hf : Function.Injective f) :

Composing an independent indexed family with an injective function on the index results in another indepedendent indexed family.

theorem CompleteLattice.Independent.comp' {α : Type u_3} [inst : CompleteLattice α] {ι : Sort u_1} {ι' : Sort u_2} {t : ια} {f : ι'ι} (ht : CompleteLattice.Independent (t f)) (hf : Function.Surjective f) :
theorem CompleteLattice.Independent.injective {α : Type u_2} {ι : Type u_1} [inst : CompleteLattice α] {t : ια} (ht : CompleteLattice.Independent t) (h_ne_bot : ∀ (i : ι), t i ) :
theorem CompleteLattice.independent_pair {α : Type u_2} {ι : Type u_1} [inst : CompleteLattice α] {t : ια} {i : ι} {j : ι} (hij : i j) (huniv : ∀ (k : ι), k = i k = j) :
theorem CompleteLattice.Independent.map_orderIso {ι : Sort u_1} {α : Type u_2} {β : Type u_3} [inst : CompleteLattice α] [inst : CompleteLattice β] (f : α ≃o β) {a : ια} (ha : CompleteLattice.Independent a) :

Composing an indepedent indexed family with an order isomorphism on the elements results in another indepedendent indexed family.

@[simp]
theorem CompleteLattice.independent_map_orderIso_iff {ι : Sort u_1} {α : Type u_2} {β : Type u_3} [inst : CompleteLattice α] [inst : CompleteLattice β] (f : α ≃o β) {a : ια} :
theorem CompleteLattice.Independent.disjoint_bsupᵢ {ι : Type u_1} {α : Type u_2} [inst : CompleteLattice α] {t : ια} (ht : CompleteLattice.Independent t) {x : ι} {y : Set ι} (hx : ¬x y) :
Disjoint (t x) (i, h, t i)

If the elements of a set are independent, then any element is disjoint from the supr of some subset of the rest.

theorem CompleteLattice.independent_iff_supIndep {α : Type u_1} {ι : Type u_2} [inst : CompleteLattice α] {s : Finset ι} {f : ια} :
theorem CompleteLattice.Independent.supIndep {α : Type u_1} {ι : Type u_2} [inst : CompleteLattice α] {s : Finset ι} {f : ια} :

Alias of the forward direction of CompleteLattice.independent_iff_supIndep.

theorem Finset.SupIndep.independent {α : Type u_1} {ι : Type u_2} [inst : CompleteLattice α] {s : Finset ι} {f : ια} :

Alias of the reverse direction of CompleteLattice.independent_iff_supIndep.

theorem CompleteLattice.Independent.sup_indep_univ {α : Type u_1} {ι : Type u_2} [inst : CompleteLattice α] [inst : Fintype ι] {f : ια} :

Alias of the forward direction of CompleteLattice.independent_iff_supIndep_univ.

theorem Finset.SupIndep.independent_of_univ {α : Type u_1} {ι : Type u_2} [inst : CompleteLattice α] [inst : Fintype ι] {f : ια} :

Alias of the reverse direction of CompleteLattice.independent_iff_supIndep_univ.

theorem CompleteLattice.independent_iff_pairwiseDisjoint {α : Type u_2} {ι : Type u_1} [inst : Order.Frame α] {f : ια} :