N-ary images of finsets #
This file defines Finset.image₂
, the binary image of finsets. This is the finset version of
Set.image2
. This is mostly useful to define pointwise operations.
Notes #
This file is very similar to Data.Set.NAry
, Order.Filter.NAry
and Data.Option.NAry
. Please
keep them in sync.
We do not define Finset.image₃
as its only purpose would be to prove properties of Finset.image₂
and Set.image2
already fulfills this task.
The image of a binary function f : α → β → γ
as a function Finset α → Finset β → Finset γ
.
Mathematically this should be thought of as the image of the corresponding function α × β → γ
.
Equations
- Finset.image₂ f s t = Finset.image (Function.uncurry f) (s ×ˢ t)
Instances For
A common special case of image₂_congr
Algebraic replacement rules #
A collection of lemmas to transfer associativity, commutativity, distributivity, ... of operations
to the associativity, commutativity, distributivity, ... of Finset.image₂
of those operations.
The proof pattern is image₂_lemma operation_lemma
. For example, image₂_comm mul_comm
proves that
image₂ (*) f g = image₂ (*) g f
in a CommSemigroup
.
Symmetric statement to Finset.image₂_image_left_comm
.
Symmetric statement to Finset.image_image₂_right_comm
.
Symmetric statement to Finset.image_image₂_distrib_left
.
Symmetric statement to Finset.image_image₂_distrib_right
.
The other direction does not hold because of the s
-s
cross terms on the RHS.
The other direction does not hold because of the u
-u
cross terms on the RHS.
Symmetric statement to Finset.image₂_image_left_anticomm
.
Symmetric statement to Finset.image_image₂_right_anticomm
.
Symmetric statement to Finset.image_image₂_antidistrib_left
.
Symmetric statement to Finset.image_image₂_antidistrib_right
.
If a
is a left identity for f : α → β → β
, then {a}
is a left identity for
Finset.image₂ f
.
If b
is a right identity for f : α → β → α
, then {b}
is a right identity for
Finset.image₂ f
.
If each partial application of f
is injective, and images of s
under those partial
applications are disjoint (but not necessarily distinct!), then the size of t
divides the size of
Finset.image₂ f s t
.
If each partial application of f
is injective, and images of t
under those partial
applications are disjoint (but not necessarily distinct!), then the size of s
divides the size of
Finset.image₂ f s t
.
If a Finset
is a subset of the image of two Set
s under a binary operation,
then it is a subset of the Finset.image₂
of two Finset
subsets of these Set
s.