The
binary operations of set union () and intersection () satisfy many identities. Several of these identities or "laws" have well established names.
Notation
Throughout this article, capital letters (such as and ) will denote sets. On the left hand side of an identity, typically,
will be the Left most set,
will be the M iddle set, and
will be the R ight most set.
This is to facilitate applying identities to expressions that are complicated or use the same symbols as the identity.[note 1]
For example, the identity
One set is said to intersect another set if Sets that do not intersect are said to be disjoint.
The
power set of is the set of all subsets of and will be denoted by
Universe set and complement notation
The notation
may be used if is a subset of some set that is understood (say from context, or because it is clearly stated what the superset is).
It is emphasized that the definition of depends on context. For instance, had been declared as a subset of with the sets and not necessarily related to each other in any way, then would likely mean instead of
If it is needed then unless indicated otherwise, it should be assumed that denotes the
universe set, which means that all sets that are used in the formula are subsets of
In particular, the
complement of a set will be denoted by where unless indicated otherwise, it should be assumed that denotes the complement of in (the universe)
In the left hand sides of the following identities, is the L eft most set and is the R ight most set.
Assume both are subsets of some universe set
Formulas for binary set operations ⋂, ⋃, \, and ∆
In the left hand sides of the following identities, is the L eft most set and is the R ight most set. Whenever necessary, both should be assumed to be subsets of some universe set so that
Set subtraction is not commutative. However, the commutativity of set subtraction can be characterized: from it follows that:
Said differently, if distinct symbols always represented distinct sets, then the only true formulas of the form that could be written would be those involving a single symbol; that is, those of the form:
But such formulas are necessarily true for every binary operation (because must hold by definition of
equality), and so in this sense, set subtraction is as diametrically opposite to being commutative as is possible for a binary operation.
Set subtraction is also neither
left alternative nor
right alternative; instead, if and only if if and only if
Set subtraction is
quasi-commutative and satisfies the
Jordan identity.
In
constructive mathematics, "not empty" and "inhabited" are not equivalent: every inhabited set is not empty but the converse is not always guaranteed; that is, in constructive mathematics, a set that is not empty (where by definition, " is empty" means that the statement is true) might not have an
inhabitant (which is an such that ).
The following proposition says that for any set the
power set of ordered by inclusion, is a
bounded lattice, and hence together with the distributive and complement laws above, show that it is a
Boolean algebra.
In the left hand sides of the following identities, is the L eft most set, is the M iddle set, and is the R ight most set.
Precedence rules
There is no universal agreement on the
order of precedence of the basic set operators.
Nevertheless, many authors use
precedence rules for set operators, although these rules vary with the author.
One common convention is to associate intersection with
logical conjunction (and) and associate union with
logical disjunction (or) and then transfer the
precedence of these logical operators (where has precedence over ) to these set operators, thereby giving precedence over
So for example, would mean since it would be associated with the logical statement and similarly, would mean since it would be associated with
Sometimes, set complement (subtraction) is also associated with
logical complement (not) in which case it will have the highest precedence.
More specifically, is rewritten so that for example, would mean since it would be rewritten as the logical statement which is equal to
For another example, because means which is equal to both and (where was rewritten as ), the formula would refer to the set
moreover, since this set is also equal to (other set identities can similarly be deduced from
propositional calculusidentities in this way).
However, because set subtraction is not associative a formula such as would be ambiguous; for this reason, among others, set subtraction is often not assigned any precedence at all.
Symmetric difference is sometimes associated with
exclusive or (xor) (also sometimes denoted by ), in which case if the order of precedence from highest to lowest is then the order of precedence (from highest to lowest) for the set operators would be
There is no universal agreement on the precedence of exclusive disjunction with respect to the other logical connectives, which is why symmetric difference is not often assigned a precedence.
For set subtraction, instead of associativity, only the following is always guaranteed:
where equality holds if and only if (this condition does not depend on ). Thus
if and only if
where the only difference between the left and right hand side set equalities is that the locations of have been swapped.
The operator distributes over if it both left distributes and right distributes over
In the definitions above, to transform one side to the other, the innermost operator (the operator inside the parentheses) becomes the outermost operator and the outermost operator becomes the innermost operator.
Intersection distributes over symmetric difference:
Union does not distribute over symmetric difference because only the following is guaranteed in general:
Symmetric difference does not distribute over itself:
and in general, for any sets (where represents ), might not be a subset, nor a superset, of (and the same is true for ).
Distributivity and set subtraction \
Failure of set subtraction to left distribute:
Set subtraction is right distributive over itself. However, set subtraction is not left distributive over itself because only the following is guaranteed in general:
where equality holds if and only if which happens if and only if
For symmetric difference, the sets and are always disjoint.
So these two sets are equal if and only if they are both equal to
Moreover, if and only if
To investigate the left distributivity of set subtraction over unions or intersections, consider how the sets involved in (both of) De Morgan's laws are all related:
always holds (the equalities on the left and right are De Morgan's laws) but equality is not guaranteed in general (that is, the containment might be strict).
Equality holds if and only if which happens if and only if
This observation about De Morgan's laws shows that is not left distributive over or because only the following are guaranteed in general:
where equality holds for one (or equivalently, for both) of the above two inclusion formulas if and only if
The following statements are equivalent:
that is, left distributes over for these three particular sets
that is, left distributes over for these three particular sets
Set subtraction complexity: To manage the many identities involving set subtraction, this section is divided based on where the set subtraction operation and parentheses are located on the left hand side of the identity. The great variety and (relative) complexity of formulas involving set subtraction (compared to those without it) is in part due to the fact that unlike and set subtraction is neither associative nor commutative and it also is not left distributive over or even over itself.
Two set subtractions
Set subtraction is not associative in general:
since only the following is always guaranteed:
(L\M)\R
L\(M\R)
If
with equality if and only if
One set subtraction
(L\M) ⁎ R
Set subtraction on the left, and parentheses on the left
if and only if for any belongs to at most two of the sets
Cartesian products ⨯ of finitely many sets
Binary ⋂ of finite ⨯
Binary ⋃ of finite ⨯
Difference \ of finite ⨯
and
Finite ⨯ of differences \
Symmetric difference ∆ and finite ⨯
In general, need not be a subset nor a superset of
Arbitrary families of sets
Let and be indexed
families of sets. Whenever the assumption is needed, then all
indexing sets, such as and are assumed to be non-empty.
Definitions
A family of sets or (more briefly) a family refers to a set whose elements are sets.
An indexed family of sets is a function from some set, called its indexing set, into some family of sets.
An indexed family of sets will be denoted by where this notation assigns the symbol for the indexing set and for every index assigns the symbol to the value of the function at
The function itself may then be denoted by the symbol which is obtained from the notation by replacing the index with a bullet symbol explicitly, is the function:
which may be summarized by writing
Any given indexed family of sets (which is a
function) can be canonically associated with its image/range (which is a family of sets).
Conversely, any given family of sets may be associated with the -indexed family of sets which is technically the
identity map
However, this is not a bijective correspondence because an indexed family of sets is not required to be injective (that is, there may exist distinct indices such as ), which in particular means that it is possible for distinct indexed families of sets (which are functions) to be associated with the same family of sets (by having the same image/range).
If is a non-empty family of sets then denotes the set:
Nullary intersections
If then
where every possible thing in the universe
vacuously satisfied the condition: "if then ". Consequently, consists of everything in the universe.
So if and:
if you are working in a
model in which there exists some
universe set then
otherwise, if you are working in a
model in which "the class of all things " is not a set (by far the most common situation) then is undefined because consists of everything, which makes a
proper class and not a set.
Assumption: Henceforth, whenever a formula requires some indexing set to be non-empty in order for an arbitrary intersection to be well-defined, then this will automatically be assumed without mention.
A consequence of this is the following assumption/definition:
A finite intersection of sets or an intersection of finitely many sets refers to the intersection of a finite collection of one or more sets.
Some authors adopt the so called nullary intersection convention, which is the convention that an empty intersection of sets is equal to some canonical set. In particular, if all sets are subsets of some set then some author may declare that the empty intersection of these sets be equal to However, the nullary intersection convention is not as commonly accepted as the nullary union convention and this article will not adopt it (this is due to the fact that unlike the empty union, the value of the empty intersection depends on so if there are multiple sets under consideration, which is commonly the case, then the value of the empty intersection risks becoming ambiguous).
If all are
pairwise disjoint and all are also pairwise disjoint, then so are all (that is, if then ).
Importantly, if then in general,
(an
example of this is given below). The single union on the right hand side must be over all pairs
The same is usually true for other similar non-trivial set equalities and relations that depend on two (potentially unrelated) indexing sets and (such as Eq. 4b or Eq. 7g[4]). Two exceptions are Eq. 2c (unions of unions) and Eq. 2d (intersections of intersections), but both of these are among the most trivial of set equalities (although even for these equalities there is still something that must be proven[note 2]).
Example where equality fails: Let and let Let and let Then
(an
example of this is given above). The single intersection on the right hand side must be over all pairs
Arbitrary ⋂'s and arbitrary ⋃'s
Incorrectly distributing by swapping ⋂ and ⋃
Naively swapping and may produce a different set
The following inclusion always holds:
(Inclusion 1 ∪∩ is a subset of ∩∪)
In general, equality need not hold and moreover, the right hand side depends on how for each fixed the sets are labelled; and analogously, the left hand side depends on how for each fixed the sets are labelled. An example demonstrating this is now given.
Example of dependence on labeling and failure of equality: To see why equality need not hold when and are swapped, let and let and Then
If and are swapped while and are unchanged, which gives rise to the sets and then
In particular, the left hand side is no longer which shows that the left hand side depends on how the sets are labelled.
If instead and are swapped while and are unchanged, which gives rise to the sets and then both the left hand side and right hand side are equal to which shows that the right hand side also depends on how the sets are labeled.
Equality in Inclusion 1 ∪∩ is a subset of ∩∪ can hold under certain circumstances, such as in 7e, which is the special case where is (that is, with the same indexing sets and ), or such as in 7f, which is the special case where is (that is, with the indexing sets and swapped).
For a correct formula that extends the distributive laws, an approach other than just switching and is needed.
Correct distributive laws
Suppose that for each is a non-empty index set and for each let be any set (for example, to apply this law to use for all and use for all and all ). Let
denote the
Cartesian product, which can be interpreted as the set of all functions such that for every Such a function may also be denoted using the tuple notation where for every and conversely, a tuple is just notation for the function with domain whose value at is both notations can be used to denote the elements of
Then
(Eq. 5 ∩∪ to ∪∩)
(Eq. 6 ∪∩ to ∩∪)
where
Applying the distributive laws
Example application: In the particular case where all are equal (that is, for all which is the case with the family for example), then letting denote this common set, the Cartesian product will be which is the
set of all functions of the form The above set equalities Eq. 5 ∩∪ to ∪∩ and Eq. 6 ∪∩ to ∩∪, respectively become:[3]
on the left hand side, the indices range over (so the subscripts of range over )
on the right hand side, the indices range over (so the subscripts of range over ).
Example application: To apply the general formula to the case of and use and let for all and let for all
Every map can be
bijectively identified with the pair (the inverse sends to the map defined by and this is technically just a change of notation). Recall that Eq. 5 ∩∪ to ∪∩ was
Expanding and simplifying the left hand side gives
and doing the same to the right hand side gives:
Thus the general identity Eq. 5 ∩∪ to ∪∩ reduces down to the previously given set equality Eq. 3b:
Moreover, a tuple belongs to the set in Eq. 8 above if and only if for all and all
In particular, if and are two families indexed by the same set then
So for instance,
and
Intersections of products indexed by different sets
Let and be two families indexed by different sets.
Technically, implies
However, sometimes these products are somehow identified as the same set through some
bijection or one of these products is identified as a subset of the other via some
injective map, in which case (by
abuse of notation) this intersection may be equal to some other (possibly non-empty) set.
For example, if and with all sets equal to then and where unless, for example, is identified as a subset of through some
injection, such as maybe for instance; however, in this particular case the product actually represents the -indexed product where
For another example, take and with and all equal to Then and which can both be identified as the same set via the bijection that sends to Under this identification,
Unions ⋃ of Π
For unions, only the following is guaranteed in general:
Let be any function, where we denote its domain by and denote its codomain by
Many of the identities below do not actually require that the sets be somehow related to 's domain or codomain (that is, to or ) so when some kind of relationship is necessary then it will be clearly indicated.
Because of this, in this article, if is declared to be "any set," and it is not indicated that must be somehow related to or (say for instance, that it be a subset or ) then it is meant that is truly arbitrary.[note 3]
This generality is useful in situations where is a map between two subsets and of some larger sets and and where the set might not be entirely contained in and/or (e.g. if all that is known about is that ); in such a situation it may be useful to know what can and cannot be said about and/or without having to introduce a (potentially unnecessary) intersection such as: and/or
Images and preimages of sets
If is any set then the image of under is defined to be the set:
A set is said to be -saturated or a saturated set if any of the following equivalent conditions are satisfied:[3]
There exists a set such that
Any such set necessarily contains as a subset.
Any set not entirely contained in the domain of cannot be -saturated.
and
The inclusion always holds, where if then this becomes
and if and satisfy then
Whenever a fiber of intersects then contains the entire fiber. In other words, contains every -fiber that intersects it.
Explicitly: whenever is such that then
In both this statement and the next, the set may be replaced with any superset of (such as ) and the resulting statement will still be equivalent to the rest.
The intersection of with a fiber of is equal to the empty set or to the fiber itself.
Explicitly: for every the intersection is equal to the
empty set or to (that is, or ).
Alternatively, where denotes the
inclusion map, which is defined by
(Pre)Images of arbitrary unions ⋃'s and intersections ⋂'s
If is a family of arbitrary sets indexed by then:[5]
So of these four identities, it is onlyimages of intersections that are not always preserved. Preimages preserve all basic set operations. Unions are preserved by both images and preimages.
If all are -saturated then be will be -saturated and equality will hold in the first relation above; explicitly, this means:
(Conditional Equality 10a)
If is a family of arbitrary subsets of which means that for all then Conditional Equality 10a becomes:
(Conditional Equality 10b)
(Pre)Images of binary set operations
Throughout, let and be any sets and let be any function.
Summary
As the table below shows, set equality is not guaranteed only for images of: intersections, set subtractions, and symmetric differences.
Preimages of sets are well-behaved with respect to all basic set operations:
In words, preimages
distribute over unions, intersections, set subtraction, and symmetric difference.
Images only preserve unions
Images of unions are well-behaved:
but images of the other basic set operations are not since only the following are guaranteed in general:
In words, images
distribute over unions but not necessarily over intersections, set subtraction, or symmetric difference. What these latter three operations have in common is set subtraction: they either areset subtraction or else they can naturally be defined as the set subtraction of two sets:
If then where as in the more general case, equality is not guaranteed. If is surjective then which can be rewritten as: if and
Counter-examples: images of operations not distributing
If is constant, and then all four of the set containments
are
strict/proper (that is, the sets are not equal) since one side is the empty set while the other is non-empty. Thus equality is not guaranteed for even the simplest of functions.
The example above is now generalized to show that these four set equalities can fail for any
constant function whose domain contains at least two (distinct) points.
Example: Let be any constant function with image and suppose that are non-empty disjoint subsets; that is, and which implies that all of the sets and are not empty and so consequently, their images under are all equal to
What the set operations in these four examples have in common is that they either areset subtraction (examples (1) and (2)) or else they can naturally be defined as the set subtraction of two sets (examples (3) and (4)).
Mnemonic: In fact, for each of the above four set formulas for which equality is not guaranteed, the direction of the containment (that is, whether to use ) can always be deduced by imagining the function as being constant and the two sets ( and ) as being non-empty disjoint subsets of its domain. This is because every equality fails for such a function and sets: one side will be always be and the other non-empty − from this fact, the correct choice of can be deduced by answering: "which side is empty?" For example, to decide if the in
should be pretend[note 5]
that is constant and that and are non-empty disjoint subsets of 's domain; then the left hand side would be empty (since ), which indicates that should be (the resulting statement is always guaranteed to be true) because this is the choice that will make
true.
Alternatively, the correct direction of containment can also be deduced by consideration of any constant with and
Furthermore, this mnemonic can also be used to correctly deduce whether or not a set operation always distribute over images or preimages; for example, to determine whether or not always equals or alternatively, whether or not always equals (although was used here, it can replaced by ). The answer to such a question can, as before, be deduced by consideration of this constant function: the answer for the general case (that is, for arbitrary and ) is always the same as the answer for this choice of (constant) function and disjoint non-empty sets.
Conditions guaranteeing that images distribute over set operations
Characterizations of when equality holds for all sets:
For any function the following statements are equivalent:
In particular, the statement that results from (d) gives a characterization of injectivity that explicitly involves only one point (rather than two): is injective if and only if
For statement (d), this is the same as: "for all singleton subsets" (because the definition of "
pairwise disjoint" is satisfies vacuously by any family that consists of exactly 1 set).
"for all disjoint subsets"
In particular, if a map is not known to be injective then barring additional information, there is no guarantee that any of the equalities in statements (b) - (e) hold.
An example above can be used to help prove this characterization. Indeed, comparison of that example with such a proof suggests that the example is representative of the fundamental reason why one of these four equalities in statements (b) - (e) might not hold (that is, representative of "what goes wrong" when a set equality does not hold).
Conditions for f(L⋂R) = f(L)⋂f(R)
Characterizations of equality: The following statements are equivalent:
The left hand side is always equal to (because always holds).
If satisfies then
If but then
Any of the above three conditions (i) - (k) but with the subset symbol replaced with an equals sign
Sufficient conditions for equality: Equality holds if any of the following are true:
where the set is equal to the image under of the largest -saturated subset of
In general, only always holds and equality is not guaranteed; but replacing "" with its subset "" results in a formula in which equality is always guaranteed:
A family of sets or simply a family is a set whose elements are sets.
A family over is a family of subsets of
The power set of a set is the set of all subsets of :
Notation for sequences of sets
Throughout, will be arbitrary sets and and will denote a
net or a
sequence of sets where if it is a sequence then this will be indicated by either of the notations
where denotes the
natural numbers.
A notation indicates that is a
netdirected by which (by definition) is a
sequence if the set which is called the net's
indexing set, is the natural numbers (that is, if ) and is the natural order on
Disjoint and monotone sequences of sets
If for all distinct indices then is called a pairwise disjoint or simply a disjoint.
A sequence or net of set is called increasing or non-decreasing if (resp. decreasing or non-increasing) if for all indices (resp. ).
A sequence or net of set is called strictly increasing (resp. strictly decreasing) if it is non-decreasing (resp. is non-increasing) and also for all distinct indices
It is called monotone if it is non-decreasing or non-increasing and it is called strictly monotone if it is strictly increasing or strictly decreasing.
A sequences or net is said to increase to denoted by [11] or if is increasing and the union of all is that is, if
It is said to decrease to denoted by [11] or if is increasing and the intersection of all is that is, if
Definitions of elementwise operations on families
If are families of sets and if is any set then define:[12]
which are respectively called elementwiseunion, elementwiseintersection, elementwise (set) difference, elementwisesymmetric difference, and the trace/restriction of to The regular union, intersection, and set difference are all defined as usual and are denoted with their usual notation: and respectively.
These elementwise operations on families of sets play an important role in, among other subjects, the theory of
filters and prefilters on sets.
Additionally, a semiring is a
π-system where every complement is equal to a finite
disjoint union of sets in
A semialgebra is a semiring where every complement is equal to a finite
disjoint union of sets in are arbitrary elements of and it is assumed that
A family is called isotone, ascending, or upward closed in if and [12]
A family is called downward closed if
A family is said to be:
closed under finite intersections (resp. closed under finite unions) if whenever then (respectively, ).
closed under
countable intersections (resp. closed under countable unions) if whenever are elements of then so is their intersections (resp. so is their union ).
closed under
complementation in (or with respect to) if whenever then
A family of sets is called a/an:
π−system if and is closed under finite-intersections.
Every non-empty family is contained in a unique smallest (with respect to ) π−system that is denoted by and called the π−system generated by
filter on if is a family of subsets of that is a π−system, is upward closed in and is also proper, which by definition means that it does not contain the empty set as an element.
prefilter or filter base if it is a non-empty family of subsets of some set whose upward closure in is a filter on
algebra on is a non-empty family of subsets of that contains the empty set, forms a π−system, and is also closed under complementation with respect to
σ-algebra on is an algebra on that is closed under countable unions (or equivalently, closed under countable intersections).
A
family of subsets of a set is said to be an algebra of sets if and for all all three of the sets and are elements of [13]
The
article on this topic lists set identities and other relationships these three operations.
Given any family of subsets of there is a unique smallest[note 7] algebra of sets in containing [13]
It is called the algebra generated by and it will be denote it by
This algebra can be constructed as follows:[13]
If then and we are done. Alternatively, if is empty then may be replaced with and continue with the construction.
Let be the family of all sets in together with their complements (taken in ).
Let be the family of all possible finite intersections of sets in [note 8]
Then the algebra generated by is the set consisting of all possible finite unions of sets in
Elementwise operations on families
Let and be families of sets over
On the left hand sides of the following identities, is the L eft most family, is in the M iddle, and is the R ight most set.
^
For example, the expression uses two of the same symbols ( and ) that appear in the identity
but they refer to different sets in each expression.
To apply this identity to substitute and (since these are the left, middle, and right sets in ) to obtain:
For a second example, this time applying the identity to is now given. The identity can be applied to by reading and as and and then substituting and to obtain:
^
abTo deduce Eq. 2c from Eq. 2a, it must still be shown that so Eq. 2c is not a completely immediate consequence of Eq. 2a. (Compare this to the commentary about Eq. 3b).
^So for instance, it's even possible that or that and (which happens, for instance, if ), etc.
^Whether or not it is even feasible for the function to be constant and the sets and to be non-empty and disjoint is irrelevant for reaching the correct conclusion about whether to use
^
abcdNote that this condition depends entirely on and not on
^Here "smallest" means relative to subset containment. So if is any algebra of sets containing then
^Since there is some such that its complement also belongs to The intersection of these two sets implies that The union of these two sets is equal to which implies that
Proofs
^
abcLet where because is also equal to As proved above, so that if and only if Since this happens if and only if Because are both subsets of the condition on the right hand side happens if and only if Because the equality holds if and only if If (such as when or ) then if and only if In particular, taking proves: if and only if where
^Let and let denote the set equality which will now be proven. If then so there exists some now implies so that To prove the reverse inclusion let so that there exists some such that Then so that and thus which proves that as desired. Defining the identity follows from and the inclusions
Köthe, Gottfried (1983) [1969]. Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. Vol. 159. Translated by Garling, D.J.H. New York: Springer Science & Business Media.
ISBN978-3-642-64988-2.
MR0248498.
OCLC840293704.
The
binary operations of set union () and intersection () satisfy many identities. Several of these identities or "laws" have well established names.
Notation
Throughout this article, capital letters (such as and ) will denote sets. On the left hand side of an identity, typically,
will be the Left most set,
will be the M iddle set, and
will be the R ight most set.
This is to facilitate applying identities to expressions that are complicated or use the same symbols as the identity.[note 1]
For example, the identity
One set is said to intersect another set if Sets that do not intersect are said to be disjoint.
The
power set of is the set of all subsets of and will be denoted by
Universe set and complement notation
The notation
may be used if is a subset of some set that is understood (say from context, or because it is clearly stated what the superset is).
It is emphasized that the definition of depends on context. For instance, had been declared as a subset of with the sets and not necessarily related to each other in any way, then would likely mean instead of
If it is needed then unless indicated otherwise, it should be assumed that denotes the
universe set, which means that all sets that are used in the formula are subsets of
In particular, the
complement of a set will be denoted by where unless indicated otherwise, it should be assumed that denotes the complement of in (the universe)
In the left hand sides of the following identities, is the L eft most set and is the R ight most set.
Assume both are subsets of some universe set
Formulas for binary set operations ⋂, ⋃, \, and ∆
In the left hand sides of the following identities, is the L eft most set and is the R ight most set. Whenever necessary, both should be assumed to be subsets of some universe set so that
Set subtraction is not commutative. However, the commutativity of set subtraction can be characterized: from it follows that:
Said differently, if distinct symbols always represented distinct sets, then the only true formulas of the form that could be written would be those involving a single symbol; that is, those of the form:
But such formulas are necessarily true for every binary operation (because must hold by definition of
equality), and so in this sense, set subtraction is as diametrically opposite to being commutative as is possible for a binary operation.
Set subtraction is also neither
left alternative nor
right alternative; instead, if and only if if and only if
Set subtraction is
quasi-commutative and satisfies the
Jordan identity.
In
constructive mathematics, "not empty" and "inhabited" are not equivalent: every inhabited set is not empty but the converse is not always guaranteed; that is, in constructive mathematics, a set that is not empty (where by definition, " is empty" means that the statement is true) might not have an
inhabitant (which is an such that ).
The following proposition says that for any set the
power set of ordered by inclusion, is a
bounded lattice, and hence together with the distributive and complement laws above, show that it is a
Boolean algebra.
In the left hand sides of the following identities, is the L eft most set, is the M iddle set, and is the R ight most set.
Precedence rules
There is no universal agreement on the
order of precedence of the basic set operators.
Nevertheless, many authors use
precedence rules for set operators, although these rules vary with the author.
One common convention is to associate intersection with
logical conjunction (and) and associate union with
logical disjunction (or) and then transfer the
precedence of these logical operators (where has precedence over ) to these set operators, thereby giving precedence over
So for example, would mean since it would be associated with the logical statement and similarly, would mean since it would be associated with
Sometimes, set complement (subtraction) is also associated with
logical complement (not) in which case it will have the highest precedence.
More specifically, is rewritten so that for example, would mean since it would be rewritten as the logical statement which is equal to
For another example, because means which is equal to both and (where was rewritten as ), the formula would refer to the set
moreover, since this set is also equal to (other set identities can similarly be deduced from
propositional calculusidentities in this way).
However, because set subtraction is not associative a formula such as would be ambiguous; for this reason, among others, set subtraction is often not assigned any precedence at all.
Symmetric difference is sometimes associated with
exclusive or (xor) (also sometimes denoted by ), in which case if the order of precedence from highest to lowest is then the order of precedence (from highest to lowest) for the set operators would be
There is no universal agreement on the precedence of exclusive disjunction with respect to the other logical connectives, which is why symmetric difference is not often assigned a precedence.
For set subtraction, instead of associativity, only the following is always guaranteed:
where equality holds if and only if (this condition does not depend on ). Thus
if and only if
where the only difference between the left and right hand side set equalities is that the locations of have been swapped.
The operator distributes over if it both left distributes and right distributes over
In the definitions above, to transform one side to the other, the innermost operator (the operator inside the parentheses) becomes the outermost operator and the outermost operator becomes the innermost operator.
Intersection distributes over symmetric difference:
Union does not distribute over symmetric difference because only the following is guaranteed in general:
Symmetric difference does not distribute over itself:
and in general, for any sets (where represents ), might not be a subset, nor a superset, of (and the same is true for ).
Distributivity and set subtraction \
Failure of set subtraction to left distribute:
Set subtraction is right distributive over itself. However, set subtraction is not left distributive over itself because only the following is guaranteed in general:
where equality holds if and only if which happens if and only if
For symmetric difference, the sets and are always disjoint.
So these two sets are equal if and only if they are both equal to
Moreover, if and only if
To investigate the left distributivity of set subtraction over unions or intersections, consider how the sets involved in (both of) De Morgan's laws are all related:
always holds (the equalities on the left and right are De Morgan's laws) but equality is not guaranteed in general (that is, the containment might be strict).
Equality holds if and only if which happens if and only if
This observation about De Morgan's laws shows that is not left distributive over or because only the following are guaranteed in general:
where equality holds for one (or equivalently, for both) of the above two inclusion formulas if and only if
The following statements are equivalent:
that is, left distributes over for these three particular sets
that is, left distributes over for these three particular sets
Set subtraction complexity: To manage the many identities involving set subtraction, this section is divided based on where the set subtraction operation and parentheses are located on the left hand side of the identity. The great variety and (relative) complexity of formulas involving set subtraction (compared to those without it) is in part due to the fact that unlike and set subtraction is neither associative nor commutative and it also is not left distributive over or even over itself.
Two set subtractions
Set subtraction is not associative in general:
since only the following is always guaranteed:
(L\M)\R
L\(M\R)
If
with equality if and only if
One set subtraction
(L\M) ⁎ R
Set subtraction on the left, and parentheses on the left
if and only if for any belongs to at most two of the sets
Cartesian products ⨯ of finitely many sets
Binary ⋂ of finite ⨯
Binary ⋃ of finite ⨯
Difference \ of finite ⨯
and
Finite ⨯ of differences \
Symmetric difference ∆ and finite ⨯
In general, need not be a subset nor a superset of
Arbitrary families of sets
Let and be indexed
families of sets. Whenever the assumption is needed, then all
indexing sets, such as and are assumed to be non-empty.
Definitions
A family of sets or (more briefly) a family refers to a set whose elements are sets.
An indexed family of sets is a function from some set, called its indexing set, into some family of sets.
An indexed family of sets will be denoted by where this notation assigns the symbol for the indexing set and for every index assigns the symbol to the value of the function at
The function itself may then be denoted by the symbol which is obtained from the notation by replacing the index with a bullet symbol explicitly, is the function:
which may be summarized by writing
Any given indexed family of sets (which is a
function) can be canonically associated with its image/range (which is a family of sets).
Conversely, any given family of sets may be associated with the -indexed family of sets which is technically the
identity map
However, this is not a bijective correspondence because an indexed family of sets is not required to be injective (that is, there may exist distinct indices such as ), which in particular means that it is possible for distinct indexed families of sets (which are functions) to be associated with the same family of sets (by having the same image/range).
If is a non-empty family of sets then denotes the set:
Nullary intersections
If then
where every possible thing in the universe
vacuously satisfied the condition: "if then ". Consequently, consists of everything in the universe.
So if and:
if you are working in a
model in which there exists some
universe set then
otherwise, if you are working in a
model in which "the class of all things " is not a set (by far the most common situation) then is undefined because consists of everything, which makes a
proper class and not a set.
Assumption: Henceforth, whenever a formula requires some indexing set to be non-empty in order for an arbitrary intersection to be well-defined, then this will automatically be assumed without mention.
A consequence of this is the following assumption/definition:
A finite intersection of sets or an intersection of finitely many sets refers to the intersection of a finite collection of one or more sets.
Some authors adopt the so called nullary intersection convention, which is the convention that an empty intersection of sets is equal to some canonical set. In particular, if all sets are subsets of some set then some author may declare that the empty intersection of these sets be equal to However, the nullary intersection convention is not as commonly accepted as the nullary union convention and this article will not adopt it (this is due to the fact that unlike the empty union, the value of the empty intersection depends on so if there are multiple sets under consideration, which is commonly the case, then the value of the empty intersection risks becoming ambiguous).
If all are
pairwise disjoint and all are also pairwise disjoint, then so are all (that is, if then ).
Importantly, if then in general,
(an
example of this is given below). The single union on the right hand side must be over all pairs
The same is usually true for other similar non-trivial set equalities and relations that depend on two (potentially unrelated) indexing sets and (such as Eq. 4b or Eq. 7g[4]). Two exceptions are Eq. 2c (unions of unions) and Eq. 2d (intersections of intersections), but both of these are among the most trivial of set equalities (although even for these equalities there is still something that must be proven[note 2]).
Example where equality fails: Let and let Let and let Then
(an
example of this is given above). The single intersection on the right hand side must be over all pairs
Arbitrary ⋂'s and arbitrary ⋃'s
Incorrectly distributing by swapping ⋂ and ⋃
Naively swapping and may produce a different set
The following inclusion always holds:
(Inclusion 1 ∪∩ is a subset of ∩∪)
In general, equality need not hold and moreover, the right hand side depends on how for each fixed the sets are labelled; and analogously, the left hand side depends on how for each fixed the sets are labelled. An example demonstrating this is now given.
Example of dependence on labeling and failure of equality: To see why equality need not hold when and are swapped, let and let and Then
If and are swapped while and are unchanged, which gives rise to the sets and then
In particular, the left hand side is no longer which shows that the left hand side depends on how the sets are labelled.
If instead and are swapped while and are unchanged, which gives rise to the sets and then both the left hand side and right hand side are equal to which shows that the right hand side also depends on how the sets are labeled.
Equality in Inclusion 1 ∪∩ is a subset of ∩∪ can hold under certain circumstances, such as in 7e, which is the special case where is (that is, with the same indexing sets and ), or such as in 7f, which is the special case where is (that is, with the indexing sets and swapped).
For a correct formula that extends the distributive laws, an approach other than just switching and is needed.
Correct distributive laws
Suppose that for each is a non-empty index set and for each let be any set (for example, to apply this law to use for all and use for all and all ). Let
denote the
Cartesian product, which can be interpreted as the set of all functions such that for every Such a function may also be denoted using the tuple notation where for every and conversely, a tuple is just notation for the function with domain whose value at is both notations can be used to denote the elements of
Then
(Eq. 5 ∩∪ to ∪∩)
(Eq. 6 ∪∩ to ∩∪)
where
Applying the distributive laws
Example application: In the particular case where all are equal (that is, for all which is the case with the family for example), then letting denote this common set, the Cartesian product will be which is the
set of all functions of the form The above set equalities Eq. 5 ∩∪ to ∪∩ and Eq. 6 ∪∩ to ∩∪, respectively become:[3]
on the left hand side, the indices range over (so the subscripts of range over )
on the right hand side, the indices range over (so the subscripts of range over ).
Example application: To apply the general formula to the case of and use and let for all and let for all
Every map can be
bijectively identified with the pair (the inverse sends to the map defined by and this is technically just a change of notation). Recall that Eq. 5 ∩∪ to ∪∩ was
Expanding and simplifying the left hand side gives
and doing the same to the right hand side gives:
Thus the general identity Eq. 5 ∩∪ to ∪∩ reduces down to the previously given set equality Eq. 3b:
Moreover, a tuple belongs to the set in Eq. 8 above if and only if for all and all
In particular, if and are two families indexed by the same set then
So for instance,
and
Intersections of products indexed by different sets
Let and be two families indexed by different sets.
Technically, implies
However, sometimes these products are somehow identified as the same set through some
bijection or one of these products is identified as a subset of the other via some
injective map, in which case (by
abuse of notation) this intersection may be equal to some other (possibly non-empty) set.
For example, if and with all sets equal to then and where unless, for example, is identified as a subset of through some
injection, such as maybe for instance; however, in this particular case the product actually represents the -indexed product where
For another example, take and with and all equal to Then and which can both be identified as the same set via the bijection that sends to Under this identification,
Unions ⋃ of Π
For unions, only the following is guaranteed in general:
Let be any function, where we denote its domain by and denote its codomain by
Many of the identities below do not actually require that the sets be somehow related to 's domain or codomain (that is, to or ) so when some kind of relationship is necessary then it will be clearly indicated.
Because of this, in this article, if is declared to be "any set," and it is not indicated that must be somehow related to or (say for instance, that it be a subset or ) then it is meant that is truly arbitrary.[note 3]
This generality is useful in situations where is a map between two subsets and of some larger sets and and where the set might not be entirely contained in and/or (e.g. if all that is known about is that ); in such a situation it may be useful to know what can and cannot be said about and/or without having to introduce a (potentially unnecessary) intersection such as: and/or
Images and preimages of sets
If is any set then the image of under is defined to be the set:
A set is said to be -saturated or a saturated set if any of the following equivalent conditions are satisfied:[3]
There exists a set such that
Any such set necessarily contains as a subset.
Any set not entirely contained in the domain of cannot be -saturated.
and
The inclusion always holds, where if then this becomes
and if and satisfy then
Whenever a fiber of intersects then contains the entire fiber. In other words, contains every -fiber that intersects it.
Explicitly: whenever is such that then
In both this statement and the next, the set may be replaced with any superset of (such as ) and the resulting statement will still be equivalent to the rest.
The intersection of with a fiber of is equal to the empty set or to the fiber itself.
Explicitly: for every the intersection is equal to the
empty set or to (that is, or ).
Alternatively, where denotes the
inclusion map, which is defined by
(Pre)Images of arbitrary unions ⋃'s and intersections ⋂'s
If is a family of arbitrary sets indexed by then:[5]
So of these four identities, it is onlyimages of intersections that are not always preserved. Preimages preserve all basic set operations. Unions are preserved by both images and preimages.
If all are -saturated then be will be -saturated and equality will hold in the first relation above; explicitly, this means:
(Conditional Equality 10a)
If is a family of arbitrary subsets of which means that for all then Conditional Equality 10a becomes:
(Conditional Equality 10b)
(Pre)Images of binary set operations
Throughout, let and be any sets and let be any function.
Summary
As the table below shows, set equality is not guaranteed only for images of: intersections, set subtractions, and symmetric differences.
Preimages of sets are well-behaved with respect to all basic set operations:
In words, preimages
distribute over unions, intersections, set subtraction, and symmetric difference.
Images only preserve unions
Images of unions are well-behaved:
but images of the other basic set operations are not since only the following are guaranteed in general:
In words, images
distribute over unions but not necessarily over intersections, set subtraction, or symmetric difference. What these latter three operations have in common is set subtraction: they either areset subtraction or else they can naturally be defined as the set subtraction of two sets:
If then where as in the more general case, equality is not guaranteed. If is surjective then which can be rewritten as: if and
Counter-examples: images of operations not distributing
If is constant, and then all four of the set containments
are
strict/proper (that is, the sets are not equal) since one side is the empty set while the other is non-empty. Thus equality is not guaranteed for even the simplest of functions.
The example above is now generalized to show that these four set equalities can fail for any
constant function whose domain contains at least two (distinct) points.
Example: Let be any constant function with image and suppose that are non-empty disjoint subsets; that is, and which implies that all of the sets and are not empty and so consequently, their images under are all equal to
What the set operations in these four examples have in common is that they either areset subtraction (examples (1) and (2)) or else they can naturally be defined as the set subtraction of two sets (examples (3) and (4)).
Mnemonic: In fact, for each of the above four set formulas for which equality is not guaranteed, the direction of the containment (that is, whether to use ) can always be deduced by imagining the function as being constant and the two sets ( and ) as being non-empty disjoint subsets of its domain. This is because every equality fails for such a function and sets: one side will be always be and the other non-empty − from this fact, the correct choice of can be deduced by answering: "which side is empty?" For example, to decide if the in
should be pretend[note 5]
that is constant and that and are non-empty disjoint subsets of 's domain; then the left hand side would be empty (since ), which indicates that should be (the resulting statement is always guaranteed to be true) because this is the choice that will make
true.
Alternatively, the correct direction of containment can also be deduced by consideration of any constant with and
Furthermore, this mnemonic can also be used to correctly deduce whether or not a set operation always distribute over images or preimages; for example, to determine whether or not always equals or alternatively, whether or not always equals (although was used here, it can replaced by ). The answer to such a question can, as before, be deduced by consideration of this constant function: the answer for the general case (that is, for arbitrary and ) is always the same as the answer for this choice of (constant) function and disjoint non-empty sets.
Conditions guaranteeing that images distribute over set operations
Characterizations of when equality holds for all sets:
For any function the following statements are equivalent:
In particular, the statement that results from (d) gives a characterization of injectivity that explicitly involves only one point (rather than two): is injective if and only if
For statement (d), this is the same as: "for all singleton subsets" (because the definition of "
pairwise disjoint" is satisfies vacuously by any family that consists of exactly 1 set).
"for all disjoint subsets"
In particular, if a map is not known to be injective then barring additional information, there is no guarantee that any of the equalities in statements (b) - (e) hold.
An example above can be used to help prove this characterization. Indeed, comparison of that example with such a proof suggests that the example is representative of the fundamental reason why one of these four equalities in statements (b) - (e) might not hold (that is, representative of "what goes wrong" when a set equality does not hold).
Conditions for f(L⋂R) = f(L)⋂f(R)
Characterizations of equality: The following statements are equivalent:
The left hand side is always equal to (because always holds).
If satisfies then
If but then
Any of the above three conditions (i) - (k) but with the subset symbol replaced with an equals sign
Sufficient conditions for equality: Equality holds if any of the following are true:
where the set is equal to the image under of the largest -saturated subset of
In general, only always holds and equality is not guaranteed; but replacing "" with its subset "" results in a formula in which equality is always guaranteed:
A family of sets or simply a family is a set whose elements are sets.
A family over is a family of subsets of
The power set of a set is the set of all subsets of :
Notation for sequences of sets
Throughout, will be arbitrary sets and and will denote a
net or a
sequence of sets where if it is a sequence then this will be indicated by either of the notations
where denotes the
natural numbers.
A notation indicates that is a
netdirected by which (by definition) is a
sequence if the set which is called the net's
indexing set, is the natural numbers (that is, if ) and is the natural order on
Disjoint and monotone sequences of sets
If for all distinct indices then is called a pairwise disjoint or simply a disjoint.
A sequence or net of set is called increasing or non-decreasing if (resp. decreasing or non-increasing) if for all indices (resp. ).
A sequence or net of set is called strictly increasing (resp. strictly decreasing) if it is non-decreasing (resp. is non-increasing) and also for all distinct indices
It is called monotone if it is non-decreasing or non-increasing and it is called strictly monotone if it is strictly increasing or strictly decreasing.
A sequences or net is said to increase to denoted by [11] or if is increasing and the union of all is that is, if
It is said to decrease to denoted by [11] or if is increasing and the intersection of all is that is, if
Definitions of elementwise operations on families
If are families of sets and if is any set then define:[12]
which are respectively called elementwiseunion, elementwiseintersection, elementwise (set) difference, elementwisesymmetric difference, and the trace/restriction of to The regular union, intersection, and set difference are all defined as usual and are denoted with their usual notation: and respectively.
These elementwise operations on families of sets play an important role in, among other subjects, the theory of
filters and prefilters on sets.
Additionally, a semiring is a
π-system where every complement is equal to a finite
disjoint union of sets in
A semialgebra is a semiring where every complement is equal to a finite
disjoint union of sets in are arbitrary elements of and it is assumed that
A family is called isotone, ascending, or upward closed in if and [12]
A family is called downward closed if
A family is said to be:
closed under finite intersections (resp. closed under finite unions) if whenever then (respectively, ).
closed under
countable intersections (resp. closed under countable unions) if whenever are elements of then so is their intersections (resp. so is their union ).
closed under
complementation in (or with respect to) if whenever then
A family of sets is called a/an:
π−system if and is closed under finite-intersections.
Every non-empty family is contained in a unique smallest (with respect to ) π−system that is denoted by and called the π−system generated by
filter on if is a family of subsets of that is a π−system, is upward closed in and is also proper, which by definition means that it does not contain the empty set as an element.
prefilter or filter base if it is a non-empty family of subsets of some set whose upward closure in is a filter on
algebra on is a non-empty family of subsets of that contains the empty set, forms a π−system, and is also closed under complementation with respect to
σ-algebra on is an algebra on that is closed under countable unions (or equivalently, closed under countable intersections).
A
family of subsets of a set is said to be an algebra of sets if and for all all three of the sets and are elements of [13]
The
article on this topic lists set identities and other relationships these three operations.
Given any family of subsets of there is a unique smallest[note 7] algebra of sets in containing [13]
It is called the algebra generated by and it will be denote it by
This algebra can be constructed as follows:[13]
If then and we are done. Alternatively, if is empty then may be replaced with and continue with the construction.
Let be the family of all sets in together with their complements (taken in ).
Let be the family of all possible finite intersections of sets in [note 8]
Then the algebra generated by is the set consisting of all possible finite unions of sets in
Elementwise operations on families
Let and be families of sets over
On the left hand sides of the following identities, is the L eft most family, is in the M iddle, and is the R ight most set.
^
For example, the expression uses two of the same symbols ( and ) that appear in the identity
but they refer to different sets in each expression.
To apply this identity to substitute and (since these are the left, middle, and right sets in ) to obtain:
For a second example, this time applying the identity to is now given. The identity can be applied to by reading and as and and then substituting and to obtain:
^
abTo deduce Eq. 2c from Eq. 2a, it must still be shown that so Eq. 2c is not a completely immediate consequence of Eq. 2a. (Compare this to the commentary about Eq. 3b).
^So for instance, it's even possible that or that and (which happens, for instance, if ), etc.
^Whether or not it is even feasible for the function to be constant and the sets and to be non-empty and disjoint is irrelevant for reaching the correct conclusion about whether to use
^
abcdNote that this condition depends entirely on and not on
^Here "smallest" means relative to subset containment. So if is any algebra of sets containing then
^Since there is some such that its complement also belongs to The intersection of these two sets implies that The union of these two sets is equal to which implies that
Proofs
^
abcLet where because is also equal to As proved above, so that if and only if Since this happens if and only if Because are both subsets of the condition on the right hand side happens if and only if Because the equality holds if and only if If (such as when or ) then if and only if In particular, taking proves: if and only if where
^Let and let denote the set equality which will now be proven. If then so there exists some now implies so that To prove the reverse inclusion let so that there exists some such that Then so that and thus which proves that as desired. Defining the identity follows from and the inclusions
Köthe, Gottfried (1983) [1969]. Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. Vol. 159. Translated by Garling, D.J.H. New York: Springer Science & Business Media.
ISBN978-3-642-64988-2.
MR0248498.
OCLC840293704.