algebra.pointwise

finset.mul_card_le

finset.mul_mem_mul

mem_inv_smul_set_iff

mem_smul_set_iff_inv_smul_mem

set.Union_add_left_image

set.Union_add_right_image

set.Union_mul_left_image

set.Union_mul_right_image

set.add_comm_monoid

set.add_image_prod

set.add_mem_add

set.add_semigroup

set.add_singleton

set.add_subset_add

set.comm_monoid

set.fintype_add

set.fintype_mul

set.has_scalar_set

set.image2_smul

set.image_add_left

set.image_add_left'

set.image_add_right

set.image_add_right'

set.image_mul_left

set.image_mul_left'

set.image_mul_prod

set.image_mul_right

set.image_mul_right'

set.image_smul_prod

set.inv_mem_inv

set.inv_preimage

set.inv_subset_inv

set.mem_smul_set

set.mul_action_set

set.mul_mem_mul

set.mul_singleton

set.mul_subset_mul

set.neg_mem_neg

set.neg_preimage

set.neg_subset_neg

set.nonempty.add

set.nonempty.mul

set.one_mem_one

set.one_nonempty

set.preimage_add_left_zero

set.preimage_add_left_zero'

set.preimage_add_preimage_subset

set.preimage_add_right_zero

set.preimage_add_right_zero'

set.preimage_mul_left_one

set.preimage_mul_left_one'

set.preimage_mul_preimage_subset

set.preimage_mul_right_one

set.preimage_mul_right_one'

set.range_smul_range

set.set_semiring

set.set_semiring.comm_semiring

set.set_semiring.down

set.set_semiring.inhabited

set.set_semiring.semiring

set.singleton.is_add_hom

set.singleton.is_mul_hom

set.singleton_add

set.singleton_add_hom

set.singleton_add_singleton

set.singleton_hom

set.singleton_mul

set.singleton_mul_singleton

set.singleton_one

set.singleton_smul

set.singleton_zero

set.smul_mem_smul_set

set.smul_set_empty

set.smul_set_mono

set.smul_set_union

set.univ_add_univ

set.univ_mul_univ

set.zero_mem_zero

set.zero_nonempty

set.zero_subset

Pointwise addition, multiplication, and scalar multiplication of sets.

This file defines pointwise algebraic operations on sets.

For a type α with multiplication, multiplication is defined on set α by taking s * t to be the set of all x * y where x ∈ s and y ∈ t. Similarly for addition.
For α a semigroup, set α is a semigroup.
If α is a (commutative) monoid, we define an alias set_semiring α for set α, which then becomes a (commutative) semiring with union as addition and pointwise multiplication as multiplication.
For a type β with scalar multiplication by another type α, this file defines a scalar multiplication of set β by set α and a separate scalar multiplication of set β by α.
We also define pointwise multiplication on finset.

Appropriate definitions and results are also transported to the additive theory via to_additive.

Implementation notes

The following expressions are considered in simp-normal form in a group: (λ h, h * g) ⁻¹' s, (λ h, g * h) ⁻¹' s, (λ h, h * g⁻¹) ⁻¹' s, (λ h, g⁻¹ * h) ⁻¹' s, s * t, s⁻¹, (1 : set _) (and similarly for additive variants). Expressions equal to one of these will be simplified.

Tags

set multiplication, set addition, pointwise addition, pointwise multiplication

Properties about 1

@[instance]

def set.has_zero {α : Type u_1} [has_zero α] :

has_zero (set α)

@[instance]

def set.has_one {α : Type u_1} [has_one α] :

has_one (set α)

Equations

set.has_one = {one := {1}}

@[simp]

theorem set.singleton_zero {α : Type u_1} [has_zero α] :

{0} = 0

@[simp]

theorem set.singleton_one {α : Type u_1} [has_one α] :

{1} = 1

@[simp]

theorem set.mem_one {α : Type u_1} {a : α} [has_one α] :

a ∈ 1 ↔ a = 1

@[simp]

theorem set.mem_zero {α : Type u_1} {a : α} [has_zero α] :

a ∈ 0 ↔ a = 0

theorem set.one_mem_one {α : Type u_1} [has_one α] :

1 ∈ 1

theorem set.zero_mem_zero {α : Type u_1} [has_zero α] :

0 ∈ 0

@[simp]

theorem set.one_subset {α : Type u_1} {s : set α} [has_one α] :

1 ⊆ s ↔ 1 ∈ s

@[simp]

theorem set.zero_subset {α : Type u_1} {s : set α} [has_zero α] :

0 ⊆ s ↔ 0 ∈ s

theorem set.one_nonempty {α : Type u_1} [has_one α] :

theorem set.zero_nonempty {α : Type u_1} [has_zero α] :

@[simp]

theorem set.image_one {α : Type u_1} {β : Type u_2} [has_one α] {f : α → β} :

f '' 1 = {f 1}

@[simp]

theorem set.image_zero {α : Type u_1} {β : Type u_2} [has_zero α] {f : α → β} :

f '' 0 = {f 0}

Properties about multiplication

@[instance]

def set.has_mul {α : Type u_1} [has_mul α] :

has_mul (set α)

Equations

set.has_mul = {mul := set.image2 has_mul.mul}

@[instance]

def set.has_add {α : Type u_1} [has_add α] :

has_add (set α)

@[simp]

theorem set.image2_mul {α : Type u_1} {s t : set α} [has_mul α] :

set.image2 has_mul.mul s t = s * t

@[simp]

theorem set.image2_add {α : Type u_1} {s t : set α} [has_add α] :

set.image2 has_add.add s t = s + t

theorem set.mem_mul {α : Type u_1} {s t : set α} {a : α} [has_mul α] :

a ∈ s * t ↔ ∃ (x y : α), x ∈ s ∧ y ∈ t ∧ x * y = a

theorem set.mem_add {α : Type u_1} {s t : set α} {a : α} [has_add α] :

a ∈ s + t ↔ ∃ (x y : α), x ∈ s ∧ y ∈ t ∧ x + y = a

theorem set.mul_mem_mul {α : Type u_1} {s t : set α} {a b : α} [has_mul α] :

a ∈ s → b ∈ t → a * b ∈ s * t

theorem set.add_mem_add {α : Type u_1} {s t : set α} {a b : α} [has_add α] :

a ∈ s → b ∈ t → a + b ∈ s + t

theorem set.add_image_prod {α : Type u_1} {s t : set α} [has_add α] :

(λ (x : α × α), x.fst + x.snd) '' s.prod t = s + t

theorem set.image_mul_prod {α : Type u_1} {s t : set α} [has_mul α] :

(λ (x : α × α), x.fst * x.snd) '' s.prod t = s * t

@[simp]

theorem set.image_add_left {α : Type u_1} {t : set α} {a : α} [add_group α] :

(λ (b : α), a + b) '' t = (λ (b : α), -a + b) ⁻¹' t

@[simp]

theorem set.image_mul_left {α : Type u_1} {t : set α} {a : α} [group α] :

(λ (b : α), a * b) '' t = (λ (b : α), a⁻¹ * b) ⁻¹' t

@[simp]

theorem set.image_mul_right {α : Type u_1} {t : set α} {b : α} [group α] :

(λ (a : α), a * b) '' t = (λ (a : α), a * b⁻¹) ⁻¹' t

@[simp]

theorem set.image_add_right {α : Type u_1} {t : set α} {b : α} [add_group α] :

(λ (a : α), a + b) '' t = (λ (a : α), a + -b) ⁻¹' t

theorem set.image_mul_left' {α : Type u_1} {t : set α} {a : α} [group α] :

(λ (b : α), a⁻¹ * b) '' t = (λ (b : α), a * b) ⁻¹' t

theorem set.image_add_left' {α : Type u_1} {t : set α} {a : α} [add_group α] :

(λ (b : α), -a + b) '' t = (λ (b : α), a + b) ⁻¹' t

theorem set.image_add_right' {α : Type u_1} {t : set α} {b : α} [add_group α] :

(λ (a : α), a + -b) '' t = (λ (a : α), a + b) ⁻¹' t

theorem set.image_mul_right' {α : Type u_1} {t : set α} {b : α} [group α] :

(λ (a : α), a * b⁻¹) '' t = (λ (a : α), a * b) ⁻¹' t

@[simp]

theorem set.preimage_mul_left_one {α : Type u_1} {a : α} [group α] :

(λ (b : α), a * b) ⁻¹' 1 = {a⁻¹}

@[simp]

theorem set.preimage_add_left_zero {α : Type u_1} {a : α} [add_group α] :

(λ (b : α), a + b) ⁻¹' 0 = {-a}

@[simp]

theorem set.preimage_mul_right_one {α : Type u_1} {b : α} [group α] :

(λ (a : α), a * b) ⁻¹' 1 = {b⁻¹}

@[simp]

theorem set.preimage_add_right_zero {α : Type u_1} {b : α} [add_group α] :

(λ (a : α), a + b) ⁻¹' 0 = {-b}

theorem set.preimage_mul_left_one' {α : Type u_1} {a : α} [group α] :

(λ (b : α), a⁻¹ * b) ⁻¹' 1 = {a}

theorem set.preimage_add_left_zero' {α : Type u_1} {a : α} [add_group α] :

(λ (b : α), -a + b) ⁻¹' 0 = {a}

theorem set.preimage_add_right_zero' {α : Type u_1} {b : α} [add_group α] :

(λ (a : α), a + -b) ⁻¹' 0 = {b}

theorem set.preimage_mul_right_one' {α : Type u_1} {b : α} [group α] :

(λ (a : α), a * b⁻¹) ⁻¹' 1 = {b}

@[simp]

theorem set.mul_singleton {α : Type u_1} {s : set α} {b : α} [has_mul α] :

s * {b} = (λ (a : α), a * b) '' s

@[simp]

theorem set.add_singleton {α : Type u_1} {s : set α} {b : α} [has_add α] :

s + {b} = (λ (a : α), a + b) '' s

@[simp]

theorem set.singleton_add {α : Type u_1} {t : set α} {a : α} [has_add α] :

{a} + t = (λ (b : α), a + b) '' t

@[simp]

theorem set.singleton_mul {α : Type u_1} {t : set α} {a : α} [has_mul α] :

{a} * t = (λ (b : α), a * b) '' t

@[simp]

theorem set.singleton_mul_singleton {α : Type u_1} {a b : α} [has_mul α] :

{a} * {b} = {a * b}

@[simp]

theorem set.singleton_add_singleton {α : Type u_1} {a b : α} [has_add α] :

{a} + {b} = {a + b}

@[instance]

def set.semigroup {α : Type u_1} [semigroup α] :

semigroup (set α)

Equations

set.semigroup = {mul := has_mul.mul set.has_mul, mul_assoc := _}

@[instance]

def set.add_semigroup {α : Type u_1} [add_semigroup α] :

add_semigroup (set α)

@[instance]

def set.add_monoid {α : Type u_1} [add_monoid α] :

add_monoid (set α)

@[instance]

def set.monoid {α : Type u_1} [monoid α] :

monoid (set α)

Equations

set.monoid = {mul := semigroup.mul set.semigroup, mul_assoc := _, one := 1, one_mul := _, mul_one := _}

theorem set.mul_comm {α : Type u_1} {s t : set α} [comm_semigroup α] :

s * t = t * s

theorem set.add_comm {α : Type u_1} {s t : set α} [add_comm_semigroup α] :

s + t = t + s

@[instance]

def set.add_comm_monoid {α : Type u_1} [add_comm_monoid α] :

add_comm_monoid (set α)

@[instance]

def set.comm_monoid {α : Type u_1} [comm_monoid α] :

comm_monoid (set α)

Equations

set.comm_monoid = {mul := monoid.mul set.monoid, mul_assoc := _, one := monoid.one set.monoid, one_mul := _, mul_one := _, mul_comm := _}

theorem set.singleton.is_mul_hom {α : Type u_1} [has_mul α] :

is_mul_hom has_singleton.singleton

theorem set.singleton.is_add_hom {α : Type u_1} [has_add α] :

is_add_hom has_singleton.singleton

@[simp]

theorem set.empty_mul {α : Type u_1} {s : set α} [has_mul α] :

@[simp]

theorem set.empty_add {α : Type u_1} {s : set α} [has_add α] :

@[simp]

theorem set.add_empty {α : Type u_1} {s : set α} [has_add α] :

@[simp]

theorem set.mul_empty {α : Type u_1} {s : set α} [has_mul α] :

theorem set.mul_subset_mul {α : Type u_1} {s₁ s₂ t₁ t₂ : set α} [has_mul α] :

s₁ ⊆ t₁ → s₂ ⊆ t₂ → s₁ * s₂ ⊆ t₁ * t₂

theorem set.add_subset_add {α : Type u_1} {s₁ s₂ t₁ t₂ : set α} [has_add α] :

s₁ ⊆ t₁ → s₂ ⊆ t₂ → s₁ + s₂ ⊆ t₁ + t₂

theorem set.union_add {α : Type u_1} {s t u : set α} [has_add α] :

s ∪ t + u = s + u ∪ (t + u)

theorem set.union_mul {α : Type u_1} {s t u : set α} [has_mul α] :

(s ∪ t) * u = s * u ∪ t * u

theorem set.add_union {α : Type u_1} {s t u : set α} [has_add α] :

s + (t ∪ u) = s + t ∪ (s + u)

theorem set.mul_union {α : Type u_1} {s t u : set α} [has_mul α] :

s * (t ∪ u) = s * t ∪ s * u

theorem set.Union_mul_left_image {α : Type u_1} {s t : set α} [has_mul α] :

(⋃ (a : α) (H : a ∈ s), (λ (x : α), a * x) '' t) = s * t

theorem set.Union_add_left_image {α : Type u_1} {s t : set α} [has_add α] :

(⋃ (a : α) (H : a ∈ s), (λ (x : α), a + x) '' t) = s + t

theorem set.Union_add_right_image {α : Type u_1} {s t : set α} [has_add α] :

(⋃ (a : α) (H : a ∈ t), (λ (x : α), x + a) '' s) = s + t

theorem set.Union_mul_right_image {α : Type u_1} {s t : set α} [has_mul α] :

(⋃ (a : α) (H : a ∈ t), (λ (x : α), x * a) '' s) = s * t

@[simp]

theorem set.univ_mul_univ {α : Type u_1} [monoid α] :

set.univ * set.univ = set.univ

@[simp]

theorem set.univ_add_univ {α : Type u_1} [add_monoid α] :

set.univ + set.univ = set.univ

def set.singleton_add_hom {α : Type u_1} [add_monoid α] :

α →+ set α

singleton is an add monoid hom

def set.singleton_hom {α : Type u_1} [monoid α] :

α →* set α

singleton is a monoid hom.

Equations

set.singleton_hom = {to_fun := has_singleton.singleton set.has_singleton, map_one' := _, map_mul' := _}

theorem set.nonempty.mul {α : Type u_1} {s t : set α} [has_mul α] :

s.nonempty → t.nonempty → (s * t).nonempty

theorem set.nonempty.add {α : Type u_1} {s t : set α} [has_add α] :

s.nonempty → t.nonempty → (s + t).nonempty

theorem set.finite.mul {α : Type u_1} {s t : set α} [has_mul α] :

s.finite → t.finite → (s * t).finite

theorem set.finite.add {α : Type u_1} {s t : set α} [has_add α] :

s.finite → t.finite → (s + t).finite

def set.fintype_add {α : Type u_1} [has_add α] [decidable_eq α] (s t : set α) [hs : fintype ↥s] [ht : fintype ↥t] :

fintype ↥(s + t)

addition preserves finiteness

def set.fintype_mul {α : Type u_1} [has_mul α] [decidable_eq α] (s t : set α) [hs : fintype ↥s] [ht : fintype ↥t] :

fintype ↥(s * t)

multiplication preserves finiteness

Equations

s.fintype_mul t = set.fintype_image2 (λ (a b : α), a * b) s t

Properties about inversion

@[instance]

def set.has_neg' {α : Type u_1} [has_neg α] :

has_neg (set α)

@[instance]

def set.has_inv {α : Type u_1} [has_inv α] :

has_inv (set α)

Equations

set.has_inv = {inv := set.preimage has_inv.inv}

@[simp]

theorem set.mem_neg {α : Type u_1} {s : set α} {a : α} [has_neg α] :

a ∈ -s ↔ -a ∈ s

@[simp]

theorem set.mem_inv {α : Type u_1} {s : set α} {a : α} [has_inv α] :

a ∈ s⁻¹ ↔ a⁻¹ ∈ s

theorem set.neg_mem_neg {α : Type u_1} {s : set α} {a : α} [add_group α] :

-a ∈ -s ↔ a ∈ s

theorem set.inv_mem_inv {α : Type u_1} {s : set α} {a : α} [group α] :

a⁻¹ ∈ s⁻¹ ↔ a ∈ s

@[simp]

theorem set.inv_preimage {α : Type u_1} {s : set α} [has_inv α] :

has_inv.inv ⁻¹' s = s⁻¹

@[simp]

theorem set.neg_preimage {α : Type u_1} {s : set α} [has_neg α] :

has_neg.neg ⁻¹' s = -s

@[simp]

theorem set.image_inv {α : Type u_1} {s : set α} [group α] :

has_inv.inv '' s = s⁻¹

@[simp]

theorem set.image_neg {α : Type u_1} {s : set α} [add_group α] :

has_neg.neg '' s = -s

@[simp]

theorem set.inter_neg {α : Type u_1} {s t : set α} [has_neg α] :

-(s ∩ t) = -s ∩ -t

@[simp]

theorem set.inter_inv {α : Type u_1} {s t : set α} [has_inv α] :

(s ∩ t)⁻¹ = s⁻¹ ∩ t⁻¹

@[simp]

theorem set.union_inv {α : Type u_1} {s t : set α} [has_inv α] :

(s ∪ t)⁻¹ = s⁻¹ ∪ t⁻¹

@[simp]

theorem set.union_neg {α : Type u_1} {s t : set α} [has_neg α] :

-(s ∪ t) = -s ∪ -t

@[simp]

theorem set.compl_neg {α : Type u_1} {s : set α} [has_neg α] :

-sᶜ = (-s)ᶜ

@[simp]

theorem set.compl_inv {α : Type u_1} {s : set α} [has_inv α] :

sᶜ ⁻¹ = s⁻¹ ᶜ

@[simp]

theorem set.inv_inv {α : Type u_1} {s : set α} [group α] :

s⁻¹ ⁻¹ = s

@[simp]

theorem set.neg_neg {α : Type u_1} {s : set α} [add_group α] :

--s = s

@[simp]

theorem set.univ_neg {α : Type u_1} [add_group α] :

-set.univ = set.univ

@[simp]

theorem set.univ_inv {α : Type u_1} [group α] :

set.univ ⁻¹ = set.univ

@[simp]

theorem set.inv_subset_inv {α : Type u_1} [group α] {s t : set α} :

s⁻¹ ⊆ t⁻¹ ↔ s ⊆ t

@[simp]

theorem set.neg_subset_neg {α : Type u_1} [add_group α] {s t : set α} :

-s ⊆ -t ↔ s ⊆ t

theorem set.inv_subset {α : Type u_1} [group α] {s t : set α} :

s⁻¹ ⊆ t ↔ s ⊆ t⁻¹

theorem set.neg_subset {α : Type u_1} [add_group α] {s t : set α} :

-s ⊆ t ↔ s ⊆ -t

Properties about scalar multiplication

@[instance]

def set.has_scalar_set {α : Type u_1} {β : Type u_2} [has_scalar α β] :

has_scalar α (set β)

Scaling a set: multiplying every element by a scalar.

Equations

set.has_scalar_set = {smul := λ (a : α), set.image (has_scalar.smul a)}

@[simp]

theorem set.image_smul {α : Type u_1} {β : Type u_2} {a : α} [has_scalar α β] {t : set β} :

(λ (x : β), a • x) '' t = a • t

theorem set.mem_smul_set {α : Type u_1} {β : Type u_2} {a : α} {x : β} [has_scalar α β] {t : set β} :

x ∈ a • t ↔ ∃ (y : β), y ∈ t ∧ a • y = x

theorem set.smul_mem_smul_set {α : Type u_1} {β : Type u_2} {a : α} {y : β} [has_scalar α β] {t : set β} :

y ∈ t → a • y ∈ a • t

theorem set.smul_set_union {α : Type u_1} {β : Type u_2} {a : α} [has_scalar α β] {s t : set β} :

a • (s ∪ t) = a • s ∪ a • t

@[simp]

theorem set.smul_set_empty {α : Type u_1} {β : Type u_2} [has_scalar α β] (a : α) :

a • ∅ = ∅

theorem set.smul_set_mono {α : Type u_1} {β : Type u_2} {a : α} [has_scalar α β] {s t : set β} :

s ⊆ t → a • s ⊆ a • t

@[instance]

def set.has_scalar {α : Type u_1} {β : Type u_2} [has_scalar α β] :

has_scalar (set α) (set β)

Pointwise scalar multiplication by a set of scalars.

Equations

set.has_scalar = {smul := set.image2 has_scalar.smul}

@[simp]

theorem set.image2_smul {α : Type u_1} {β : Type u_2} {s : set α} [has_scalar α β] {t : set β} :

set.image2 has_scalar.smul s t = s • t

theorem set.mem_smul {α : Type u_1} {β : Type u_2} {s : set α} {x : β} [has_scalar α β] {t : set β} :

x ∈ s • t ↔ ∃ (a : α) (y : β), a ∈ s ∧ y ∈ t ∧ a • y = x

theorem set.image_smul_prod {α : Type u_1} {β : Type u_2} {s : set α} [has_scalar α β] {t : set β} :

(λ (x : α × β), x.fst • x.snd) '' s.prod t = s • t

theorem set.range_smul_range {α : Type u_1} {β : Type u_2} [has_scalar α β] {ι : Type u_3} {κ : Type u_4} (b : ι → α) (c : κ → β) :

set.range b • set.range c = set.range (λ (p : ι × κ), b p.fst • c p.snd)

theorem set.singleton_smul {α : Type u_1} {β : Type u_2} {a : α} [has_scalar α β] {t : set β} :

{a} • t = a • t

set α as a (∪,*)-semiring

@[instance]

def set.set_semiring.inhabited (α : Type u_1) :

inhabited (set.set_semiring α)

def set.set_semiring :

Type u_1 → Type u_1

An alias for set α, which has a semiring structure given by ∪ as "addition" and pointwise multiplication * as "multiplication".

Equations

set.set_semiring α = set α

def set.up {α : Type u_1} :

set α → set.set_semiring α

The identitiy function set α → set_semiring α.

Equations

s.up = s

def set.set_semiring.down {α : Type u_1} :

set.set_semiring α → set α

The identitiy function set_semiring α → set α.

Equations

s.down = s

@[simp]

theorem set.down_up {α : Type u_1} {s : set α} :

@[simp]

theorem set.up_down {α : Type u_1} {s : set.set_semiring α} :

@[instance]

def set.set_semiring.semiring {α : Type u_1} [monoid α] :

semiring (set.set_semiring α)

Equations

set.set_semiring.semiring = {add := λ (s t : set.set_semiring α), s ∪ t, add_assoc := _, zero := ∅, zero_add := _, add_zero := _, add_comm := _, mul := monoid.mul set.monoid, mul_assoc := _, one := monoid.one set.monoid, one_mul := _, mul_one := _, zero_mul := _, mul_zero := _, left_distrib := _, right_distrib := _}

@[instance]

def set.set_semiring.comm_semiring {α : Type u_1} [comm_monoid α] :

comm_semiring (set.set_semiring α)

Equations

set.set_semiring.comm_semiring = {add := semiring.add set.set_semiring.semiring, add_assoc := _, zero := semiring.zero set.set_semiring.semiring, zero_add := _, add_zero := _, add_comm := _, mul := comm_monoid.mul set.comm_monoid, mul_assoc := _, one := comm_monoid.one set.comm_monoid, one_mul := _, mul_one := _, zero_mul := _, mul_zero := _, left_distrib := _, right_distrib := _, mul_comm := _}

@[instance]

def set.mul_action_set {α : Type u_1} {β : Type u_2} [monoid α] [mul_action α β] :

mul_action α (set β)

A multiplicative action of a monoid on a type β gives also a multiplicative action on the subsets of β.

Equations

set.mul_action_set = {to_has_scalar := {smul := has_scalar.smul set.has_scalar_set}, one_smul := _, mul_smul := _}

theorem set.image_mul {α : Type u_1} {β : Type u_2} {s t : set α} [has_mul α] [has_mul β] (m : α → β) [is_mul_hom m] :

m '' (s * t) = m '' s * m '' t

theorem set.image_add {α : Type u_1} {β : Type u_2} {s t : set α} [has_add α] [has_add β] (m : α → β) [is_add_hom m] :

m '' (s + t) = m '' s + m '' t

theorem set.preimage_add_preimage_subset {α : Type u_1} {β : Type u_2} [has_add α] [has_add β] (m : α → β) [is_add_hom m] {s t : set β} :

m ⁻¹' s + m ⁻¹' t ⊆ m ⁻¹' (s + t)

theorem set.preimage_mul_preimage_subset {α : Type u_1} {β : Type u_2} [has_mul α] [has_mul β] (m : α → β) [is_mul_hom m] {s t : set β} :

m ⁻¹' s * m ⁻¹' t ⊆ m ⁻¹' (s * t)

def set.image_hom {α : Type u_1} {β : Type u_2} [monoid α] [monoid β] :

(α →* β) → set.set_semiring α →+* set.set_semiring β

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

Equations

set.image_hom f = {to_fun := set.image ⇑f, map_one' := _, map_mul' := _, map_zero' := _, map_add' := _}

theorem zero_smul_set {α : Type u_1} {β : Type u_2} [semiring α] [add_comm_monoid β] [semimodule α β] {s : set β} :

s.nonempty → 0 • s = 0

A nonempty set in a semimodule is scaled by zero to the singleton containing 0 in the semimodule.

theorem mem_inv_smul_set_iff {α : Type u_1} {β : Type u_2} [field α] [mul_action α β] {a : α} (ha : a ≠ 0) (A : set β) (x : β) :

x ∈ a⁻¹ • A ↔ a • x ∈ A

theorem mem_smul_set_iff_inv_smul_mem {α : Type u_1} {β : Type u_2} [field α] [mul_action α β] {a : α} (ha : a ≠ 0) (A : set β) (x : β) :

x ∈ a • A ↔ a⁻¹ • x ∈ A

@[instance]

def finset.has_add {α : Type u_1} [decidable_eq α] [has_add α] :

has_add (finset α)

The pointwise sum of two finite sets s and t: s + t = { x + y | x ∈ s, y ∈ t }.

@[instance]

def finset.has_mul {α : Type u_1} [decidable_eq α] [has_mul α] :

has_mul (finset α)

The pointwise product of two finite sets s and t: st = s ⬝ t = s * t = { x * y | x ∈ s, y ∈ t }.

Equations

finset.has_mul = {mul := λ (s t : finset α), finset.image (λ (p : α × α), p.fst * p.snd) (s.product t)}

theorem finset.mul_def {α : Type u_1} [decidable_eq α] [has_mul α] {s t : finset α} :

s * t = finset.image (λ (p : α × α), p.fst * p.snd) (s.product t)

theorem finset.mem_mul {α : Type u_1} [decidable_eq α] [has_mul α] {s t : finset α} {x : α} :

x ∈ s * t ↔ ∃ (y z : α), y ∈ s ∧ z ∈ t ∧ y * z = x

theorem finset.coe_mul {α : Type u_1} [decidable_eq α] [has_mul α] {s t : finset α} :

↑(s * t) = ↑s * ↑t

theorem finset.mul_mem_mul {α : Type u_1} [decidable_eq α] [has_mul α] {s t : finset α} {x y : α} :

x ∈ s → y ∈ t → x * y ∈ s * t

theorem finset.mul_card_le {α : Type u_1} [decidable_eq α] [has_mul α] {s t : finset α} :

(s * t).card ≤ s.card * t.card

General documentation

Additional documentation

mathlib overview

well founded recursion

documentation style guide

naming conventions

Library

algebra

big_operators

basic

intervals

order

pi

ring

category

Algebra

basic

limits

CommRing

adjunctions

basic

colimits

limits

Group

Z_Module_equivalence

abelian

adjunctions

basic

biproducts

colimits

images

limits

preadditive

zero

Module

abelian

basic

kernels

limits

monoidal

Mon

basic

colimits

limits

continued_fractions

computation

approximations

basic

correctness_terminating

translations

basic

continuants_recurrence

convergents_equiv

terminated_stable

translations

group

basic

commute

conj

defs

hom

inj_surj

pi

prod

semiconj

to_additive

type_tags

ulift

units

units_hom

with_one

homology

chain_complex

exact

homology

image_to_kernel_map

module

basic

ordered

pi

prod

submodule

ulift

polynomial

big_operators

ring

basic

pi

prod

ulift

add_torsor

archimedean

associated

char_p

char_zero

classical_lie_algebras

direct_limit

direct_sum

divisibility

euclidean_domain

field

field_power

floor

free

free_monoid

gcd_monoid

geom_sum

group_action_hom

group_power

group_ring_action

group_with_zero

group_with_zero_power

invertible

iterate_hom

lie_algebra

linear_ordered_comm_group_with_zero

linear_recurrence

midpoint

opposites

order

order_functions

ordered_field

ordered_group

ordered_ring

pointwise

punit_instances

quadratic_discriminant

algebraic_geometry

presheafed_space

prime_spectrum

stalks

analysis

ODE

gronwall

analytic

basic

composition

calculus

darboux

deriv

extend_deriv

fderiv

implicit

inverse

iterated_deriv

lhopital

local_extr

mean_value

specific_functions

tangent_cone

times_cont_diff

complex

basic

polynomial

convex

basic

caratheodory

cone

extrema

specific_functions

topology

normed_space

add_torsor

banach

basic

bounded_linear_maps

complemented

dual

enorm

extend

finite_dimension

hahn_banach

indicator_function

mazur_ulam

multilinear

operator_norm

point_reflection

real_inner_product

riesz_lemma

units

special_functions

arsinh

exp_log

pow

trigonometric

asymptotics

hofer

mean_inequalities

specific_limits

category_theory

abelian

diagram_lemmas

four

basic

exact

non_preadditive

pseudoelements

adjunction

basic

fully_faithful

limits

opposites

category

Cat

Groupoid

Kleisli

Rel

default

closed

cartesian

monoidal

concrete_category

basic

bundled

bundled_hom

reflects_isomorphisms

unbundled_hom

limits

preserves

basic

shapes

shapes

constructions

over

connected

default

products

binary_products

equalizers

limits_of_products_and_equalizers

preserve_binary_products

pullbacks

binary_products

biproducts

concrete_category

equalizers

finite_limits

finite_products

images

kernels

products

pullbacks

regular_mono

strong_epi

terminal

types

wide_pullbacks

zero

concrete_category

cones

connected

creates

fubini

functor_category

lattice

limits

opposites

over

pi

punit

types

monad

adjunction

algebra

basic

bundled

equiv_mon

limits

types

monoidal

internal

functor_category

types

End

braided

category

functor

functor_category

functorial

internal

of_has_finite_products

types

unitors

pi

basic

preadditive

biproducts

default

schur

products

associator

basic

bifunctor

sums

associator

basic

action

arrow

comma

conj

connected

const

core

currying

differential_object

discrete_category

elements

endomorphism

epi_mono

eq_to_hom

equivalence

full_subcategory

fully_faithful

functor

functor_category

functorial

graded_object

groupoid

hom_functor

isomorphism

isomorphism_classes

natural_isomorphism

natural_transformation

opposites

over

pempty

punit

quotient

reflects_isomorphisms

shift

simple

single_obj

sparse

types

whiskering

yoneda

combinatorics

composition

simple_graph

computability

halting

partrec

partrec_code

primrec

reduce

tm_to_partrec

turing_machine

control

bitraversable

basic

instances

lemmas

equiv_functor

instances

functor

multivariate

monad

basic

cont

writer

traversable

basic

derive

equiv

instances

lemmas

applicative

basic

bifunctor

equiv_functor

fold

functor

uliftable

core

data

buffer

parser

bitvec

buffer

dlist

lazy_list

stream

vector

init

algebra

classes

functions

order

control

alternative

applicative

combinators

except

functor

id

lawful

lift

monad

monad_fail

option

reader

state

data

array

basic

slice

bool

basic

lemmas

char

basic

classes

lemmas

fin

basic

ops

int

basic

bitwise

comp_lemmas

order

list

basic

instances

lemmas

qsort

nat

basic

bitwise

div

gcd

lemmas

option

basic

instances

ordering

basic

lemmas

rbmap

basic

rbtree

basic

default

sigma

basic

lex

string

basic

ops

subtype

basic

instances

sum

basic

unsigned

basic

ops

prod

punit

quot

repr

set

setoid

to_string

meta

converter

conv

interactive

lean

parser

smt

congruence_closure

ematch

interactive

rsimp

smt_tactic

widget

basic

html_cmd

interactive_expr

replace_save_info

tactic_component

ac_tactics

async_tactic

attribute

backward

case_tag

comp_value_tactics

congr_lemma

congr_tactic

constructor_tactic

contradiction_tactic

declaration

derive

environment

exceptional

expr

expr_address

float

format

fun_info

has_reflect

hole_command

injection_tactic

interaction_monad

interactive

interactive_base

level

local_context

match_tactic

mk_dec_eq_instance

mk_has_reflect_instance

mk_has_sizeof_instance

mk_inhabited_instance

module_info

name

occurrences

options

pexpr

rb_map

rec_util

ref

relation_tactics

rewrite_tactic

set_get_option_tactics

simp_tactic

tactic

tagged_format

task

type_context

vm

well_founded_tactics

cc_lemmas

classical

coe

core

default

function

funext

ite_simp

logic

propext

util

version

wf

system

io

io_interface

random

data

analysis

filter

topology

array

lemmas

bitvec

basic

buffer

basic

complex

basic

exponential

module

dlist

basic

instances

equiv

encodable

basic

lattice

basic

denumerable

fin

functor

list

local_equiv

mul_add

nat

ring

transfer_instance

finset

basic

fold

intervals

lattice

nat_antidiagonal

order

pi

powerset

sort

finsupp

basic

lattice

pointwise

fintype

basic

card

intervals

sort

fp

basic

int

basic

cast

char_zero

gcd

modeq

parity

range

sqrt

list

alist

bag_inter

basic

chain

defs

erase_dup

forall2

func

indexes

intervals

min_max

nat_antidiagonal

nodup

of_fn

pairwise

palindrome

perm

range

rotate

sections

sigma

sort

tfae

zip

matrix

basic

notation

pequiv

multiset

antidiagonal

basic

erase_dup

finset_ops

fold

functor

intervals

lattice

nat_antidiagonal

nodup

pi

powerset

range

sections

sort

nat

basic

cast

choose

digits

dist

enat

fib

gcd

modeq

multiplicity

pairing

parity

prime

sqrt

totient

num

basic

bitwise

lemmas

prime

option

basic

defs

padics

hensel

padic_integers

padic_norm

padic_numbers

pfunctor

multivariate

M

W

basic

univariate

M

basic

pnat

basic

factors

intervals

xgcd

polynomial

degree

basic

algebra_map

basic

coeff

degree

derivative

div

eval

field_division

identities

induction

integral_normalization

monic

monomial

ring_division

qpf

multivariate

constructions

cofix

comp

const

fix

prj

quot

sigma

basic

univariate

basic

rat

basic

cast

denumerable

floor

meta_defs

order

sqrt

real

basic

cardinality

cau_seq

cau_seq_completion

conjugate_exponents

ennreal

ereal

golden_ratio

hyperreal

irrational

nnreal

pi

seq

computation

parallel

seq

wseq

set

intervals

basic

disjoint

image_preimage

ord_connected

unordered_interval

basic

countable

disjointed

enumerate

finite

function

lattice

setoid

basic

partition

sigma

basic

stream

basic

string

basic

defs

zmod

basic

zsqrtd

basic

gaussian_int

W

bool

char

dfinsupp

erased

fin

fin2

fin_enum

finmap

hash_map

holor

indicator_function

lazy_list2

mllist

monoid_algebra

mv_polynomial

opposite

pequiv

pfun

prod

quot

rel

semiquot

subtype

sum

support

sym

sym2

tree

typevec

ulift

vector2

deprecated

group

ring

subgroup

submonoid

dynamics

circle

rotation_number

translation_number

fixed_points

basic

topology

periodic_pts

field_theory

algebraic_closure

chevalley_warning

finite

fixed

minimal_polynomial

mv_polynomial

normal

perfect_closure

separable

splitting_field

subfield

tower

geometry

algebra

lie_group

euclidean

basic

circumcenter

monge_point

triangle

manifold

basic_smooth_bundle

charted_space

local_invariant_properties

mfderiv

real_instances

smooth_manifold_with_corners

times_cont_mdiff

group_theory

perm

cycles

sign

submonoid

basic

membership

operations

abelianization

congruence

coset

eckmann_hilton

free_abelian_group

free_group

group_action

monoid_localization

order_of_element

presented_group

quotient_group

semidirect_product

subgroup

sylow

linear_algebra

affine_space

basic

combination

finite_dimensional

independent

char_poly

coeff

direct_sum

finsupp

tensor_product

adic_completion

basic

basis

bilinear_form

char_poly

contraction

determinant

dimension

direct_sum_module

dual

finite_dimensional

finsupp

finsupp_vector_space

invariant_basis_number

lagrange

linear_action

linear_pmap

matrix

multilinear

nonsingular_inverse

projection

quadratic_form

sesquilinear_form

smodeq

special_linear_group

tensor_algebra

tensor_product

logic

function

basic

conjugate

iterate

basic

embedding

nontrivial

relation

relator

unique

measure_theory

category

Meas

ae_eq_fun

bochner_integration

borel_space

content

decomposition

giry_monad

group

haar_measure

integration

interval_integral

l1_space

lebesgue_measure

measurable_space

measure_space

outer_measure

probability_mass_function

set_integral

simple_func_dense

meta

coinductive_predicates

expr

expr_lens

rb_map

uchange

number_theory

basic

bernoulli

dioph

lucas_lehmer

pell

primorial

pythagorean_triples

quadratic_reciprocity

sum_four_squares

sum_two_squares

order

category

LinearOrder

NonemptyFinLinOrd

PartialOrder

Preorder

filter

at_top_bot

bases

basic

cofinite

countable_Inter

extr

filter_product

germ

indicator_function

interval

lift

partial

pointwise

ultrafilter

basic

boolean_algebra

bounded_lattice

bounds

complete_boolean_algebra

complete_lattice

conditionally_complete_lattice

copy

directed

fixed_points

galois_connection

ideal

iterate

lattice

lexicographic

liminf_limsup

ord_continuous

order_iso_nat

pilex

rel_classes

rel_iso

semiconj_Sup

zorn

representation_theory

maschke

ring_theory

ideal

basic

operations

over

polynomial

basic

homogeneous

rational_root

valuation

basic

adjoin

adjoin_root

algebra

algebra_operations

algebra_tower

algebraic

coprime

derivation

discrete_valuation_ring

eisenstein_criterion

euclidean_domain

fintype

fractional_ideal

free_comm_ring

free_ring

integral_closure

integral_domain

jacobson

jacobson_ideal

localization

maps

matrix_algebra

multiplicity

noetherian

polynomial_algebra

power_series

prime

principal_ideal_domain

subring

subsemiring

tensor_product

unique_factorization_domain

set_theory

game

domineering

impartial

nim

short

state

winner

cardinal

cardinal_ordinal

cofinality

game

lists

ordinal

ordinal_arithmetic

ordinal_notation

pgame

schroeder_bernstein

surreal

zfc

system

random

basic

tactic

converter

apply_congr

binders

interactive

old_conv

linarith

datatypes

elimination

frontend

lemmas

parsing

preprocessing

verification

lint

basic

default

frontend

misc

simp

type_classes

monotonicity

basic

interactive

lemmas

nth_rewrite

basic

congr

default

omega

int

dnf

form

main

preterm

nat

dnf

form

main

neg_elim

preterm

sub_elim

clause

coeffs

eq_elim

find_ees

find_scalars

lin_comb

main

misc

prove_unsats

term

rewrite_all

basic

abel

algebra

alias

apply

apply_fun

auto_cases

binder_matching

cache

cancel_denoms

chain

choose

clear

core

dec_trivial

delta_instance

derive_fintype

derive_inhabited

doc_commands

elide

equiv_rw

explode

ext

fin_cases

find

find_unused

finish

fix_reflect_string

generalize_proofs

generalizes

group

hint

interactive

interactive_expr

interval_cases

lift

local_cache

localized

mk_iff_of_inductive_prop

noncomm_ring

norm_cast

norm_num

obviously

pi_instances

protected

push_neg

rcases

reassoc_axiom

rename_var

replacer

restate_axiom

rewrite

ring

ring2

ring_exp

scc

show_term

simp_command

simp_result

simp_rw

simpa

simps

slice

solve_by_elim

split_ifs

squeeze

subtype_instance

suggest

tauto

tfae

tidy

transfer

transform_decl

transport

trunc_cases

unfold_cases

where

with_local_reducibility

wlog

zify

topology

algebra

affine

continuous_functions

group

group_completion

infinite_sum

module

monoid

multilinear

open_subgroup

ordered

polynomial

ring

uniform_group

uniform_ring

category

Top

adjunctions

basic

epi_mono

limits

open_nhds

opens

TopCommRing

UniformSpace

instances

complex

ennreal

nnreal

real

real_vector_space

metric_space

antilipschitz

baire

basic

cau_seq_filter

closeds

completion

contracting

emetric_space

gluing

gromov_hausdorff

gromov_hausdorff_realized

hausdorff_distance

isometry

lipschitz

pi_Lp

premetric_space

sheaves

presheaf

presheaf_of_functions

sheaf

sheaf_of_functions

stalks

uniform_space

absolute_value

abstract_completion

basic

cauchy

compact_separated

compare_reals

complete_separated

completion

pi

separation

uniform_convergence

uniform_embedding

bases

basic

bounded_continuous_function

compact_open

compacts

constructions

continuous_map

continuous_on

dense_embedding

extend_from_subset

homeomorph

list

local_extr

local_homeomorph

maps

opens

order

path_connected

separation

sequences

stone_cech

subset_properties

tactic

topological_fiber_bundle