Documentation

Mathlib.Data.Set.Semiring

Sets as a semiring under union #

This file defines SetSemiring α, a one-field structure around Set α, which we endow with ∪ as addition and pointwise * as multiplication. If α is a (commutative) monoid, SetSemiring α is an idempotent (commutative) semiring.

structure SetSemiring (α : Type u_4) :
Type u_4

SetSemiring α is a one-field structure around Set α with a semiring structure given by ∪ as addition and pointwise multiplication * as multiplication.

  • ofSet :: (
    • toSet : Set α

      The underlying set

  • )
Instances For
    theorem SetSemiring.ext {α : Type u_4} {x y : SetSemiring α} (toSet : x.toSet = y.toSet) :
    x = y
    theorem SetSemiring.ext_iff {α : Type u_4} {x y : SetSemiring α} :
    x = y ↔ x.toSet = y.toSet
    @[instance_reducible]
    instance instInhabitedSetSemiring {a✝ : Type u_4} :
    Equations

    The natural equivalence between SetSemiring α and Set α.

    Equations
    Instances For
      @[simp]
      theorem SetSemiring.toSetEquiv_apply {α : Type u_1} (self : SetSemiring α) :
      toSetEquiv self = self.toSet
      @[simp]
      theorem SetSemiring.toSetEquiv_symm_apply_toSet {α : Type u_1} (toSet : Set α) :
      (toSetEquiv.symm toSet).toSet = toSet
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      @[simp]
      theorem SetSemiring.toSet_ofSet {α : Type u_1} (s : Set α) :
      { toSet := s }.toSet = s
      @[simp]
      theorem SetSemiring.ofSet_toSet {α : Type u_1} (s : SetSemiring α) :
      { toSet := s.toSet } = s
      @[simp]
      theorem SetSemiring.ofSet_le_ofSet {α : Type u_1} {s t : Set α} :
      { toSet := s } ≤ { toSet := t } ↔ s ⊆ t
      @[simp]
      theorem SetSemiring.ofSet_lt_ofSet {α : Type u_1} {s t : Set α} :
      { toSet := s } < { toSet := t } ↔ s ⊂ t
      @[simp]
      theorem SetSemiring.toSet_subset_toSet {α : Type u_1} {s t : SetSemiring α} :
      s.toSet ⊆ t.toSet ↔ s ≤ t
      @[simp]
      theorem SetSemiring.toSet_ssubset_toSet {α : Type u_1} {s t : SetSemiring α} :
      s.toSet ⊂ t.toSet ↔ s < t
      @[instance_reducible]
      Equations
      @[instance_reducible]
      Equations
      @[instance_reducible]
      instance SetSemiring.instInsert {α : Type u_1} :
      Equations
      @[simp]
      theorem SetSemiring.mem_toSet {α : Type u_1} {s : SetSemiring α} {a : α} :
      a ∈ s.toSet ↔ a ∈ s
      @[simp]
      theorem SetSemiring.mem_ofSet {α : Type u_1} {s : Set α} {a : α} :
      a ∈ { toSet := s } ↔ a ∈ s
      @[simp]
      theorem SetSemiring.mem_singleton_iff {α : Type u_1} {a b : α} :
      a ∈ {b} ↔ a = b
      @[simp]
      theorem SetSemiring.toSet_singleton {α : Type u_1} {a : α} :
      @[simp]
      theorem SetSemiring.ofSet_singleton {α : Type u_1} {a : α} :
      { toSet := {a} } = {a}
      @[simp]
      theorem SetSemiring.toSet_insert {α : Type u_1} {s : SetSemiring α} {a : α} :
      @[simp]
      theorem SetSemiring.ofSet_insert {α : Type u_1} {s : Set α} {a : α} :
      { toSet := insert a s } = insert a { toSet := s }
      @[instance_reducible]
      instance SetSemiring.instZero {α : Type u_1} :
      Equations
      @[instance_reducible]
      instance SetSemiring.instAdd {α : Type u_1} :
      Equations
      theorem SetSemiring.zero_def {α : Type u_1} :
      0 = { toSet := ∅ }
      @[simp]
      theorem SetSemiring.toSet_zero {α : Type u_1} :
      @[simp]
      theorem SetSemiring.ofSet_empty {α : Type u_1} :
      { toSet := ∅ } = 0
      theorem SetSemiring.add_def {α : Type u_1} (s t : SetSemiring α) :
      s + t = { toSet := s.toSet ∪ t.toSet }
      @[simp]
      theorem SetSemiring.toSet_add {α : Type u_1} (s t : SetSemiring α) :
      (s + t).toSet = s.toSet ∪ t.toSet
      @[simp]
      theorem SetSemiring.ofSet_union {α : Type u_1} (s t : Set α) :
      { toSet := s ∪ t } = { toSet := s } + { toSet := t }
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      @[instance_reducible]
      instance SetSemiring.instOne {α : Type u_1} [One α] :
      Equations
      theorem SetSemiring.one_def {α : Type u_1} [One α] :
      1 = { toSet := 1 }
      @[simp]
      theorem SetSemiring.toSet_one {α : Type u_1} [One α] :
      toSet 1 = 1
      @[simp]
      theorem SetSemiring.ofSet_one {α : Type u_1} [One α] :
      { toSet := 1 } = 1
      @[instance_reducible]
      instance SetSemiring.instMul {α : Type u_1} [Mul α] :
      Equations
      theorem SetSemiring.mul_def {α : Type u_1} [Mul α] (s t : SetSemiring α) :
      s * t = { toSet := s.toSet * t.toSet }
      @[simp]
      theorem SetSemiring.toSet_mul {α : Type u_1} [Mul α] (s t : SetSemiring α) :
      (s * t).toSet = s.toSet * t.toSet
      @[simp]
      theorem SetSemiring.ofSet_mul {α : Type u_1} [Mul α] (s t : Set α) :
      { toSet := s * t } = { toSet := s } * { toSet := t }
      @[instance_reducible]
      instance SetSemiring.instPowNat {α : Type u_1} [Mul α] [One α] :
      Equations
      theorem SetSemiring.pow_def {α : Type u_1} [Mul α] [One α] (s : SetSemiring α) (n : ℕ) :
      s ^ n = { toSet := s.toSet ^ n }
      @[simp]
      theorem SetSemiring.toSet_pow {α : Type u_1} [Mul α] [One α] (s : SetSemiring α) (n : ℕ) :
      (s ^ n).toSet = s.toSet ^ n
      @[simp]
      theorem SetSemiring.ofSet_pow {α : Type u_1} [Mul α] [One α] (s : Set α) (n : ℕ) :
      { toSet := s ^ n } = { toSet := s } ^ n
      @[instance_reducible]
      Equations
      @[instance_reducible]
      Equations
      @[instance_reducible]
      Equations
      @[instance_reducible]
      instance SetSemiring.instMonoid {α : Type u_1} [Monoid α] :
      Equations
      @[instance_reducible]
      Equations
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.

      If α is a monoid, the map that sends a : α to {a} is a monoid homomorphism.

      Equations
      Instances For
        def SetSemiring.imageHom {α : Type u_1} {β : Type u_2} [MulOneClass α] [MulOneClass β] (f : α →* β) :

        The image of a set under a multiplicative homomorphism is a ring homomorphism with respect to the pointwise operations on sets.

        Equations
        Instances For
          @[simp]
          theorem SetSemiring.imageHom_apply {α : Type u_1} {β : Type u_2} [MulOneClass α] [MulOneClass β] (f : α →* β) (s : SetSemiring α) :
          (imageHom f) s = { toSet := ⇑f '' s.toSet }
          theorem SetSemiring.imageHom_comp {α : Type u_1} {β : Type u_2} {γ : Type u_3} [MulOneClass α] [MulOneClass β] [MulOneClass γ] (f : α →* β) (g : β →* γ) :
          @[deprecated SetSemiring.ofSet (since := "2026-10-13")]
          def Set.up {α : Type u_4} (toSet : Set α) :

          Alias of SetSemiring.ofSet.


          Convert a Set α to a SetSemiring α.

          Equations
          Instances For
            @[reducible, deprecated SetSemiring.toSet (since := "2026-10-13")]
            def SetSemiring.down {α : Type u_4} (self : SetSemiring α) :
            Set α

            Alias of SetSemiring.toSet.


            The underlying set

            Equations
            Instances For
              @[deprecated SetSemiring.toSet_ofSet (since := "2026-10-13")]
              theorem SetSemiring.down_up {α : Type u_1} (s : Set α) :
              { toSet := s }.toSet = s

              Alias of SetSemiring.toSet_ofSet.

              @[deprecated SetSemiring.ofSet_toSet (since := "2026-10-13")]
              theorem SetSemiring.up_down {α : Type u_1} (s : SetSemiring α) :
              { toSet := s.toSet } = s

              Alias of SetSemiring.ofSet_toSet.

              @[deprecated SetSemiring.ofSet_le_ofSet (since := "2026-10-13")]
              theorem SetSemiring.up_le_up {α : Type u_1} {s t : Set α} :
              { toSet := s } ≤ { toSet := t } ↔ s ⊆ t

              Alias of SetSemiring.ofSet_le_ofSet.

              @[deprecated SetSemiring.ofSet_lt_ofSet (since := "2026-10-13")]
              theorem SetSemiring.up_lt_up {α : Type u_1} {s t : Set α} :
              { toSet := s } < { toSet := t } ↔ s ⊂ t

              Alias of SetSemiring.ofSet_lt_ofSet.

              @[deprecated SetSemiring.toSet_subset_toSet (since := "2026-10-13")]
              theorem SetSemiring.down_subset_down {α : Type u_1} {s t : SetSemiring α} :
              s.toSet ⊆ t.toSet ↔ s ≤ t

              Alias of SetSemiring.toSet_subset_toSet.

              @[deprecated SetSemiring.toSet_ssubset_toSet (since := "2026-10-13")]
              theorem SetSemiring.down_ssubset_down {α : Type u_1} {s t : SetSemiring α} :
              s.toSet ⊂ t.toSet ↔ s < t

              Alias of SetSemiring.toSet_ssubset_toSet.

              @[deprecated SetSemiring.toSet_zero (since := "2026-10-13")]
              theorem SetSemiring.down_zero {α : Type u_1} :

              Alias of SetSemiring.toSet_zero.

              @[deprecated SetSemiring.ofSet_empty (since := "2026-10-13")]
              theorem Set.up_empty {α : Type u_1} :
              { toSet := ∅ } = 0

              Alias of SetSemiring.ofSet_empty.

              @[deprecated SetSemiring.toSet_add (since := "2026-10-13")]
              theorem SetSemiring.down_add {α : Type u_1} (s t : SetSemiring α) :
              (s + t).toSet = s.toSet ∪ t.toSet

              Alias of SetSemiring.toSet_add.

              @[deprecated SetSemiring.ofSet_union (since := "2026-10-13")]
              theorem Set.up_union {α : Type u_1} (s t : Set α) :
              { toSet := s ∪ t } = { toSet := s } + { toSet := t }

              Alias of SetSemiring.ofSet_union.

              @[deprecated SetSemiring.toSet_mul (since := "2026-10-13")]
              theorem SetSemiring.down_mul {α : Type u_1} [Mul α] (s t : SetSemiring α) :
              (s * t).toSet = s.toSet * t.toSet

              Alias of SetSemiring.toSet_mul.

              @[deprecated SetSemiring.ofSet_mul (since := "2026-10-13")]
              theorem Set.up_mul {α : Type u_1} [Mul α] (s t : Set α) :
              { toSet := s * t } = { toSet := s } * { toSet := t }

              Alias of SetSemiring.ofSet_mul.

              @[deprecated SetSemiring.toSet_one (since := "2026-10-13")]
              theorem SetSemiring.down_one {α : Type u_1} [One α] :
              toSet 1 = 1

              Alias of SetSemiring.toSet_one.

              @[deprecated SetSemiring.ofSet_one (since := "2026-10-13")]
              theorem Set.up_one {α : Type u_1} [One α] :
              { toSet := 1 } = 1

              Alias of SetSemiring.ofSet_one.

              @[deprecated SetSemiring.imageHom_apply (since := "2026-10-13")]
              theorem SetSemiring.imageHom_def {α : Type u_1} {β : Type u_2} [MulOneClass α] [MulOneClass β] (f : α →* β) (s : SetSemiring α) :
              (imageHom f) s = { toSet := ⇑f '' s.toSet }

              Alias of SetSemiring.imageHom_apply.

              @[deprecated SetSemiring.imageHom_apply (since := "2026-10-13")]
              theorem SetSemiring.down_imageHom {α : Type u_1} {β : Type u_2} [MulOneClass α] [MulOneClass β] (f : α →* β) (s : SetSemiring α) :
              (imageHom f) s = { toSet := ⇑f '' s.toSet }

              Alias of SetSemiring.imageHom_apply.

              @[deprecated SetSemiring.imageHom_apply (since := "2026-10-13")]
              theorem Set.up_image {α : Type u_1} {β : Type u_2} [MulOneClass α] [MulOneClass β] (f : α →* β) (s : SetSemiring α) :
              (SetSemiring.imageHom f) s = { toSet := ⇑f '' s.toSet }

              Alias of SetSemiring.imageHom_apply.

              @[deprecated SetSemiring.ofSet_toSet "type changed" (since := "2026-11-09")]
              theorem SetSemiring.symm_toSet {α : Type u_1} (s : SetSemiring α) :
              { toSet := s.toSet } = s

              Alias of SetSemiring.ofSet_toSet.

              @[deprecated SetSemiring.toSet_ofSet "type changed" (since := "2026-11-09")]
              theorem SetSemiring.symm_ofSet {α : Type u_1} (s : Set α) :
              { toSet := s }.toSet = s

              Alias of SetSemiring.toSet_ofSet.