List of set identities and relations explained

This article lists mathematical properties and laws of sets, involving the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures for evaluating expressions, and performing calculations, involving these operations and relations.

The binary operations of set union (

\cup ) and intersection (\cap ) satisfy many identities. Several of these identities or "laws" have well established names.

Notation

Throughout this article, capital letters (such as

A, B, C, L, M, R, S, and X ) will denote sets. On the left hand side of an identity, typically,L will be the eft most set, M will be the iddle set, and R will be the ight most set.This is to facilitate applying identities to expressions that are complicated or use the same symbols as the identity.^[1] For example, the identity $$(L\; \backslash ,\backslash setminus\backslash ,\; M)\; \backslash ,\backslash setminus\backslash ,\; R\; ~=~\; (L\; \backslash ,\backslash setminus\backslash ,\; R)\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash setminus\backslash ,\; R)$$may be read as:$$(\backslash text\; \backslash ,\backslash setminus\backslash ,\; \backslash text)\; \backslash ,\backslash setminus\backslash ,\; \backslash text\; ~=~\; (\backslash text\; \backslash ,\backslash setminus\backslash ,\; \backslash text)\; \backslash ,\backslash setminus\backslash ,\; (\backslash text\; \backslash ,\backslash setminus\backslash ,\; \backslash text).$$

Elementary set operations

For sets

L and R, define:and$$L\; \backslash triangle\; R\; ~\backslash stackrel~\; \backslash$$where the L \triangle R is sometimes denoted by L \ominus R and equals:^{[2] [3]}

One set

L is said to another set R if L \cap R ≠ \varnothing. Sets that do not intersect are said to be .

The power set of

X is the set of all subsets of X and will be denoted by$$\backslash wp(X)\; ~\backslash stackrel~\; \backslash .$$

Universe set and complement notation

The notation $$L^\backslash complement\; ~\backslash stackrel~\; X\; \backslash setminus\; L.$$may be used if

L is a subset of some set X that is understood (say from context, or because it is clearly stated what the superset X is). It is emphasized that the definition of L ^{\complement} depends on context. For instance, had L been declared as a subset of Y, with the sets Y and X not necessarily related to each other in any way, then L ^{\complement} would likely mean Y \setminus L instead of X \setminus L.

If it is needed then unless indicated otherwise, it should be assumed that

X denotes the universe set, which means that all sets that are used in the formula are subsets of X. In particular, the complement of a set L will be denoted by L ^{\complement} where unless indicated otherwise, it should be assumed that L ^{\complement} denotes the complement of L in (the universe) X.

One subset involved

Assume

L \subseteq X.

Identity

Definition:

e is called a left identity element of a binary operator \ast if e \ast R = R for all R and it is called a right identity element of \ast if L \ast e = L for all L. A left identity element that is also a right identity element if called an identity element.

The empty set

\varnothing is an identity element of binary union \cup and symmetric difference \triangle, and it is also a right identity element of set subtraction \setminus:

but

\varnothing is not a left identity element of \setminus since$$\backslash varnothing\; \backslash setminus\; L\; =\; \backslash varnothing$$ so $\backslash varnothing\; \backslash setminus\; L\; =\; L$ if and only if L = \varnothing.

Idempotence

L \ast L = L and Nilpotence L \ast L = \varnothing :

Domination/Absorbing element:

Definition:

z is called a left absorbing element of a binary operator \ast if z \ast R = z for all R and it is called a right absorbing element of \ast if L \ast z = z for all L. A left absorbing element that is also a right absorbing element if called an absorbing element. Absorbing elements are also sometime called annihilating elements or zero elements.

A universe set is an absorbing element of binary union

\cup. The empty set \varnothing is an absorbing element of binary intersection \cap and binary Cartesian product x , and it is also a left absorbing element of set subtraction \setminus:

but

\varnothing is not a right absorbing element of set subtraction since$$L\; \backslash setminus\; \backslash varnothing\; =\; L$$ where $L\; \backslash setminus\; \backslash varnothing\; =\; \backslash varnothing$ if and only if $L\; =\; \backslash varnothing.$

Double complement or involution law:

$$L\; \backslash setminus\; \backslash varnothing\; =\; L$$

$$L^\backslash complement\; =\; X\; \backslash setminus\; L\; \backslash quad\; \backslash text$$

L \,\triangle (X \setminus L)&= X&&\qquad\text\quad&&L \,\triangle L^\complement = X&&\quad&&\text L \subseteq X\\[1.4ex]

L \,\cap (X \setminus L)&= \varnothing&&\qquad\text\quad&&L \cap L^\complement = \varnothing&&\quad&&\\[1.4ex]\end

X \setminus X&= \varnothing&&\qquad\text\quad&&X^\complement = \varnothing&&\quad&&\text\\[1.4ex]\end

Two sets involved

In the left hand sides of the following identities,

L is the eft most set and R is the ight most set. Assume both L and R are subsets of some universe set X.

Formulas for binary set operations ⋂, ⋃, \, and ∆

In the left hand sides of the following identities,

L is the eft most set and R is the ight most set. Whenever necessary, both L and R should be assumed to be subsets of some universe set X, so that L ^{\complement} : = X \setminus L and R ^{\complement} : = X \setminus R.

De Morgan's laws

De Morgan's laws state that for

L, R \subseteq X:

X \setminus (L \cup R)&= (X \setminus L) \cap (X \setminus R)&&\qquad\text\quad&&(L \cup R)^\complement = L^\complement \cap R^\complement&&\quad&&\text\\[1.4ex]\end

Commutativity

Unions, intersection, and symmetric difference are commutative operations:

Set subtraction is not commutative. However, the commutativity of set subtraction can be characterized: from

(L \setminus R) \cap (R \setminus L) = \varnothing it follows that:$$L\; \backslash ,\backslash setminus\backslash ,\; R\; =\; R\; \backslash ,\backslash setminus\backslash ,\; L\; \backslash quad\; \backslash text\; \backslash quad\; L\; =\; R.$$ Said differently, if distinct symbols always represented distinct sets, then the true formulas of the form ⋅ \setminus ⋅ = ⋅ \setminus ⋅ that could be written would be those involving a single symbol; that is, those of the form: S \setminus S = S \setminus S. But such formulas are necessarily true for binary operation \ast (because x \ast x = x \ast x 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, (L \setminus L) \setminus R = L \setminus (L \setminus R) if and only if L \cap R = \varnothing if and only if (R \setminus L) \setminus L = R \setminus (L \setminus L). Set subtraction is quasi-commutative and satisfies the Jordan identity.

Other identities involving two sets

Absorption laws:

Other properties

X \setminus (L \setminus R)&= (X \setminus L) \cup R&&\qquad\text\quad&&(L \setminus R)^\complement = L^\complement \cup R&&\quad&&\text R \subseteq X\\[1.4ex]

L \setminus R&= (X \setminus R) \setminus (X \setminus L)&&\qquad\text\quad&&L \setminus R = R^\complement \setminus L^\complement&&\quad&&\text L, R \subseteq X\\[1.4ex]\end

Intervals:

$$(a,\; b)\; \backslash cap\; (c,\; d)\; =\; (\backslash max\backslash ,\; \backslash min\backslash )$$

l \in L then l \in R

L \cap R = L

L \cup R = R

L \triangle R = R \setminus L

L \triangle R \subseteq R \setminus L

L \setminus R = \varnothing

L and X \setminus R are disjoint (that is, L \cap (X \setminus R) = \varnothing )

X \setminus R \subseteq X \setminus L (that is, R ^{\complement} \subseteq L ^{\complement} )

The following statements are equivalent for any

L, R \subseteq X:

1. L \not\subseteq R
2. There exists some l \in L \setminus R.

Set equality

See also: Extensionality.

The following statements are equivalent:

1. L = R
2. L \triangle R = \varnothing
3. L \setminus R = R \setminus L

• If
  L \cap R = \varnothing then L = R if and only if L = \varnothing = R.
• Uniqueness of complements: If $L\; \backslash cup\; R\; =\; X\; \backslash text\; L\; \backslash cap\; R\; =\; \backslash varnothing$ then R = X \setminus L

Empty set

A set

L is empty if the sentence \forall x (x \not\in L) is true, where the notation x \not\in L is shorthand for ln ot (x \in L).

If

L is any set then the following are equivalent:

1. L is not empty, meaning that the sentence ln ot [\forall x (x \not\in L)] is true (literally, the logical negation of "L is empty" holds true).
2. (In classical mathematics) L is inhabited, meaning: \exists x (x \in L)
   • 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
   L that is not empty (where by definition, "L is empty" means that the statement \forall x (x \not\in L) is true) might not have an inhabitant (which is an x such that x \in L ).
3. L \not\subseteq R for some set R

If

L is any set then the following are equivalent:

1. L is empty (L = \varnothing ), meaning: \forall x (x \not\in L)
2. L \cup R \subseteq R for every set R
3. L \subseteq R for every set R
4. L \subseteq R \setminus L for some/every set R
5. \varnothing / L = L

Given any

x, the following are equivalent:

1. $x\; \backslash not\backslash in\; L\; \backslash setminus\; R$
2. $x\; \backslash in\; L\; \backslash cap\; R\; \backslash ;\; \backslash text\; \backslash ;\; x\; \backslash not\backslash in\; L.$
3. $x\; \backslash in\; R\; \backslash ;\; \backslash text\; \backslash ;\; x\; \backslash not\backslash in\; L.$

Moreover,$$(L\; \backslash setminus\; R)\; \backslash cap\; R\; =\; \backslash varnothing\; \backslash qquad\; \backslash text.$$

Meets, Joins, and lattice properties

\subseteq, which is a binary operation, has the following three properties:

• Reflexivity: $L\; \backslash subseteq\; L$
• Antisymmetry: $(L\; \backslash subseteq\; R\; \backslash text\; R\; \backslash subseteq\; L)\; \backslash text\; L\; =\; R$
• Transitivity: $\backslash textL\; \backslash subseteq\; M\; \backslash text\; M\; \backslash subseteq\; R\; \backslash text\; L\; \backslash subseteq\; R$

The following proposition says that for any set

S, the power set of S, ordered by inclusion, is a bounded lattice, and hence together with the distributive and complement laws above, show that it is a Boolean algebra.

Existence of a least element and a greatest element: $$\backslash varnothing\; \backslash subseteq\; L\; \backslash subseteq\; X$$

Joins/supremums exist: $$L\; \backslash subseteq\; L\; \backslash cup\; R$$

The union

L \cup R is the join/supremum of L and R with respect to \subseteq because:

1. L \subseteq L \cup R and R \subseteq L \cup R, and
2. if Z is a set such that L \subseteq Z and R \subseteq Z then L \cup R \subseteq Z.

The intersection

L \cap R is the join/supremum of L and R with respect to \supseteq.

Meets/infimums exist: $$L\; \backslash cap\; R\; \backslash subseteq\; L$$

The intersection

L \cap R is the meet/infimum of L and R with respect to \subseteq because:

1. if L \cap R \subseteq L and L \cap R \subseteq R, and
2. if Z is a set such that Z \subseteq L and Z \subseteq R then Z \subseteq L \cap R.

The union

L \cup R is the meet/infimum of L and R with respect to \supseteq.

Other inclusion properties:

$$L\; \backslash setminus\; R\; \backslash subseteq\; L$$$$(L\; \backslash setminus\; R)\; \backslash cap\; L\; =\; L\; \backslash setminus\; R$$

• If
  L \subseteq R then L \triangle R = R \setminus L.
• If L \subseteq X and R \subseteq Y then L x R \subseteq X x Y

Three sets involved

In the left hand sides of the following identities,

L is the eft most set, M is the iddle set, and R is the 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

L \cap R = \{x : (x \in L) \land (x \in R)\} with logical conjunction (and) L \land R and associate union L \cup R = \{x : (x \in L) \lor (x \in R)\} with logical disjunction (or) L \lor R, and then transfer the precedence of these logical operators (where \land has precedence over \lor ) to these set operators, thereby giving \cap precedence over \cup. So for example, L \cup M \cap R would mean L \cup (M \cap R) since it would be associated with the logical statement L \lor M \land R ~ = ~ L \lor (M \land R) and similarly, L \cup M \cap R \cup Z would mean L \cup (M \cap R) \cup Z since it would be associated with L \lor M \land R \lor Z ~ = ~ L \lor (M \land R) \lor Z.

Sometimes, set complement (subtraction)

\setminus is also associated with logical complement (not) ln ot, in which case it will have the highest precedence. More specifically, L \setminus R = \{x : (x \in L) \land ln ot (x \in R)\} is rewritten L \land ln ot R so that for example, L \cup M \setminus R would mean L \cup (M \setminus R) since it would be rewritten as the logical statement L \lor M \land ln ot R which is equal to L \lor (M \land ln ot R). For another example, because L \land ln ot M \land R means L \land ( ln ot M) \land R, which is equal to both (L \land ( ln ot M)) \land R and L \land (( ln ot M) \land R) ~ = ~ L \land (R \land ( ln ot M)) (where ( ln ot M) \land R was rewritten as R \land ( ln ot M) ), the formula L \setminus M \cap R would refer to the set (L \setminus M) \cap R = L \cap (R \setminus M); moreover, since L \land ( ln ot M) \land R = (L \land R) \land ln ot M, this set is also equal to (L \cap R) \setminus M (other set identities can similarly be deduced from propositional calculus identities in this way).However, because set subtraction is not associative (L \setminus M) \setminus R ≠ L \setminus (M \setminus R), a formula such as L \setminus M \setminus R would be ambiguous; for this reason, among others, set subtraction is often not assigned any precedence at all. L \triangle R = \{x : (x \in L) ⊕ (x \in R)\} is sometimes associated with exclusive or (xor) L ⊕ R (also sometimes denoted by \veebar ), in which case if the order of precedence from highest to lowest is ln ot, ⊕ , \land, \lor then the order of precedence (from highest to lowest) for the set operators would be \setminus, \triangle, \cap, \cup. There is no universal agreement on the precedence of exclusive disjunction ⊕ with respect to the other logical connectives, which is why symmetric difference \triangle is not often assigned a precedence.

Associativity

\ast is called associative if (L \ast M) \ast R = L \ast (M \ast R) always holds.

The following set operators are associative:

For set subtraction, instead of associativity, only the following is always guaranteed:$$(L\; \backslash ,\backslash setminus\backslash ,\; M)\; \backslash ,\backslash setminus\backslash ,\; R\; \backslash ;~~~~\backslash ;\; L\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash setminus\backslash ,\; R)$$where equality holds if and only if

L \cap R = \varnothing (this condition does not depend on M ). Thus $\backslash ;\; (L\; \backslash setminus\; M)\; \backslash setminus\; R\; =\; L\; \backslash setminus\; (M\; \backslash setminus\; R)\; \backslash ;$ if and only if (R \setminus M) \setminus L = R \setminus (M \setminus L), where the only difference between the left and right hand side set equalities is that the locations of L and R have been swapped.

Distributivity

Definition: If

\ast and \bullet are binary operators then if $$L\; \backslash ,\backslash ast\backslash ,\; (M\; \backslash ,\backslash bullet\backslash ,\; R)\; ~=~\; (L\; \backslash ,\backslash ast\backslash ,\; M)\; \backslash ,\backslash bullet\backslash ,\; (L\; \backslash ,\backslash ast\backslash ,R)\; \backslash qquad\backslash qquad\; \backslash text\; L,\; M,\; R$$while if $$(L\; \backslash ,\backslash bullet\backslash ,\; M)\; \backslash ,\backslash ast\backslash ,\; R\; ~=~\; (L\; \backslash ,\backslash ast\backslash ,\; R)\; \backslash ,\backslash bullet\backslash ,\; (M\; \backslash ,\backslash ast\backslash ,R)\; \backslash qquad\backslash qquad\; \backslash text\; L,\; M,\; R.$$ The operator if it both left distributes and right distributes over \bullet. 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.

Right distributivity

Left distributivity

Distributivity and symmetric difference ∆

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:$$L\; \backslash ,\backslash triangle\backslash ,\; (M\; \backslash ,\backslash triangle\backslash ,\; R)\; ~~~~\; \backslash color\; (L\; \backslash ,\backslash triangle\backslash ,\; M)\; \backslash ,\backslash triangle\backslash ,\; (L\; \backslash ,\backslash triangle\backslash ,\; R)\; ~=~\; M\; \backslash ,\backslash triangle\backslash ,\; R$$and in general, for any sets

L and A (where A represents M \triangle R ), L \triangle A might not be a subset, nor a superset, of L (and the same is true for A ).

Distributivity and set subtraction \

Failure of set subtraction to left distribute:

Set subtraction is distributive over itself. However, set subtraction is left distributive over itself because only the following is guaranteed in general:where equality holds if and only if

L \setminus M = L \cap R, which happens if and only if L \cap M \cap R = \varnothing and L \setminus M \subseteq R.

For symmetric difference, the sets

L \setminus (M \triangle R) and (L \setminus M) \triangle (L \setminus R) = L \cap (M \triangle R) are always disjoint. So these two sets are equal if and only if they are both equal to \varnothing. Moreover, L \setminus (M \triangle R) = \varnothing if and only if L \cap M \cap R = \varnothing and L \subseteq M \cup R.

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

{\color{red}{\subseteq}} might be strict). Equality holds if and only if L \setminus (M \cap R) \subseteq L \setminus (M \cup R), which happens if and only if L \cap M = L \cap R.

This observation about De Morgan's laws shows that

\setminus is left distributive over \cup or \cap 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 L \cap M = L \cap R.

The following statements are equivalent:

1. L \cap M = L \cap R
2. L \setminus M = L \setminus R
3. L \setminus (M \cap R) = (L \setminus M) \cap (L \setminus R); that is, \setminus left distributes over \cap for these three particular sets
4. L \setminus (M \cup R) = (L \setminus M) \cup (L \setminus R); that is, \setminus left distributes over \cup for these three particular sets
5. L \setminus (M \cap R) = L \setminus (M \cup R)
6. L \cap (M \cup R) = L \cap M \cap R
7. L \cap (M \cup R) ~\subseteq~ M \cap R
8. L \cap R ~\subseteq~ M and L \cap M ~\subseteq~ R
9. L \setminus (M \setminus R) = L \setminus (R \setminus M)
10. L \setminus (M \setminus R) = L \setminus (R \setminus M) = L

Quasi-commutativity

$$(L\; \backslash setminus\; M)\; \backslash setminus\; R\; ~=~\; (L\; \backslash setminus\; R)\; \backslash setminus\; M\; \backslash qquad\; \backslash text$$always holds but in general, $$L\; \backslash setminus\; (M\; \backslash setminus\; R)\; ~~~~\; L\; \backslash setminus\; (R\; \backslash setminus\; M).$$However,

L \setminus (M \setminus R) ~\subseteq~ L \setminus (R \setminus M) if and only if L \cap R ~\subseteq~ M if and only if L \setminus (R \setminus M) ~ = ~ L.

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

\cup, \cap, and \triangle, set subtraction is neither associative nor commutative and it also is not left distributive over \cup, \cap, \triangle, or even over itself.

Two set subtractions

Set subtraction is associative in general: $$(L\; \backslash ,\backslash setminus\backslash ,\; M)\; \backslash ,\backslash setminus\backslash ,\; R\; \backslash ;~~~~\backslash ;\; L\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash setminus\backslash ,\; R)$$since only the following is always guaranteed:$$(L\; \backslash ,\backslash setminus\backslash ,\; M)\; \backslash ,\backslash setminus\backslash ,\; R\; \backslash ;~~~~\backslash ;\; L\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash setminus\backslash ,\; R).$$

(L\M)\R

L\(M\R)

• If

L \subseteq M then L \setminus (M \setminus R) = L \cap R

• $L\; \backslash setminus\; (M\; \backslash setminus\; R)\; \backslash subseteq\; (L\; \backslash setminus\; M)\; \backslash cup\; R$ with equality if and only if

R \subseteq L.

One set subtraction

(L\M) ⁎ R

Set subtraction on the left, and parentheses on the

\begin{alignat}{ 4 } (L \setminus M) \cap R & = (&&L \cap R) \setminus (M \cap R) ~~~ (Distributivelawof \cap over \setminus ) \\ & = (&&L \cap R) \setminus M \\ & = &&L \cap (R \setminus M) \\ \end{alignat}

$$(L\; \backslash ,\backslash setminus\; M)\; \backslash times\; R\; =\; (L\; \backslash times\; R)\; \backslash ,\backslash setminus\; (M\; \backslash times\; R)\; ~~~~~\backslash text$$

L\(M ⁎ R)

Set subtraction on the left, and parentheses on the

where the above two sets that are the subjects of De Morgan's laws always satisfy

L \setminus (M \cup R) ~~{\color{red}{\subseteq}}~~ \color{black}{} L \setminus (M \cap R).

(L ⁎ M)\R

Set subtraction on the right, and parentheses on the

L ⁎ (M\R)

Set subtraction on the right, and parentheses on the

\begin{alignat}{ 4 } L \cap (M \setminus R) & = (&&L \cap M) &&\setminus (L \cap R) ~~~ (Distributivelawof \cap over \setminus ) \\ & = (&&L \cap M) &&\setminus R \\ & = &&M &&\cap (L \setminus R) \\ & = (&&L \setminus R) &&\cap (M \setminus R) \\ \end{alignat}

$$L\; \backslash times\; (M\; \backslash ,\backslash setminus\; R)\; =\; (L\; \backslash times\; M)\; \backslash ,\backslash setminus\; (L\; \backslash times\; R)\; ~~~~~\backslash text$$

Three operations on three sets

(L • M) ⁎ (M • R)

Operations of the form

(L \bullet M) \ast (M \bullet R) :

(L • M) ⁎ (R\M)

Operations of the form

(L \bullet M) \ast (R \setminus M) :

(L\M) ⁎ (L\R)

Operations of the form

(L \setminus M) \ast (L \setminus R) :

Other simplifications

Other properties:

$$L\; \backslash cap\; M\; =\; R\; \backslash ;\backslash text\backslash ;\; L\; \backslash cap\; R\; =\; M\; \backslash qquad\; \backslash text\; \backslash qquad\; M\; =\; R\; \backslash subseteq\; L.$$

• If
  L \subseteq M then L \setminus R = L \cap (M \setminus R).
• L x (M \setminus R) = (L x M) \setminus (L x R)
• If L \subseteq R then M \setminus R \subseteq M \setminus L.
• L \cap M \cap R = \varnothing if and only if for any x \in L \cup M \cup R, x belongs to of the sets L, M, and R.

Symmetric difference ∆ of finitely many sets

Given finitely many sets

L _{1,} \ldots, L _{n,} something belongs to their symmetric difference if and only if it belongs to an odd number of these sets. Explicitly, for any x, x \in L _{1} \triangle … \triangle L _{n} if and only if the cardinality \left|\left\{i : x \in L _{i\right\}\right|} is odd. (Recall that symmetric difference is associative so parentheses are not needed for the set L _{1} \triangle … \triangle L _{n} ).

Consequently, the symmetric difference of three sets satisfies:

Cartesian products ⨯ of finitely many sets

Binary ⨯ distributes over ⋃ and ⋂ and \ and ∆

The binary Cartesian product ⨯ distributes over unions, intersections, set subtraction, and symmetric difference:

But in general, ⨯ does not distribute over itself:$$L\; \backslash times\; (M\; \backslash times\; R)\; ~\backslash color\backslash color~\; (L\; \backslash times\; M)\; \backslash times\; (L\; \backslash times\; R)$$$$(L\; \backslash times\; M)\; \backslash times\; R\; ~\backslash color\backslash color~\; (L\; \backslash times\; R)\; \backslash times\; (M\; \backslash times\; R).$$

Binary ⋂ of finite ⨯

$$(L\; \backslash times\; R)\; \backslash cap\; \backslash left(L\_2\; \backslash times\; R\_2\backslash right)\; ~=~\; \backslash left(L\; \backslash cap\; L\_2\backslash right)\; \backslash times\; \backslash left(R\; \backslash cap\; R\_2\backslash right)$$$$(L\; \backslash times\; M\; \backslash times\; R)\; \backslash cap\; \backslash left(L\_2\; \backslash times\; M\_2\; \backslash times\; R\_2\backslash right)\; ~=~\; \backslash left(L\; \backslash cap\; L\_2\backslash right)\; \backslash times\; \backslash left(M\; \backslash cap\; M\_2\backslash right)\; \backslash times\; \backslash left(R\; \backslash cap\; R\_2\backslash right)$$

Binary ⋃ of finite ⨯

Difference \ of finite ⨯

and $$(L\; \backslash times\; M\; \backslash times\; R)\; ~\backslash setminus~\; \backslash left(L\_2\; \backslash times\; M\_2\; \backslash times\; R\_2\backslash right)\; ~=~\; \backslash left[\backslash left(L\; \backslash ,\backslash setminus\backslash ,\; L\_2\backslash right)\; \backslash times\; M\; \backslash times\; R\backslash right]\; ~\backslash cup~\; \backslash left[L\; \backslash times\; \backslash left(M\; \backslash ,\backslash setminus\backslash ,\; M\_2\backslash right)\; \backslash times\; R\backslash right]\; ~\backslash cup~\; \backslash left[L\; \backslash times\; M\; \backslash times\; \backslash left(R\; \backslash ,\backslash setminus\backslash ,\; R\_2\backslash right)\backslash right]$$

Finite ⨯ of differences \

$$\backslash left(L\; \backslash ,\backslash setminus\backslash ,\; L\_2\backslash right)\; \backslash times\; \backslash left(R\; \backslash ,\backslash setminus\backslash ,\; R\_2\backslash right)\; ~=~\; \backslash left(L\; \backslash times\; R\backslash right)\; \backslash ,\backslash setminus\backslash ,\; \backslash left[\backslash left(L\_2\; \backslash times\; R\backslash right)\; \backslash cup\; \backslash left(L\; \backslash times\; R\_2\backslash right)\backslash right]$$

$$\backslash left(L\; \backslash ,\backslash setminus\backslash ,\; L\_2\backslash right)\; \backslash times\; \backslash left(M\; \backslash ,\backslash setminus\backslash ,\; M\_2\backslash right)\; \backslash times\; \backslash left(R\; \backslash ,\backslash setminus\backslash ,\; R\_2\backslash right)\; ~=~\; \backslash left(L\; \backslash times\; M\; \backslash times\; R\backslash right)\; \backslash ,\backslash setminus\backslash ,\; \backslash left[\backslash left(L\_2\; \backslash times\; M\; \backslash times\; R\backslash right)\; \backslash cup\; \backslash left(L\; \backslash times\; M\_2\; \backslash times\; R\backslash right)\; \backslash cup\; \backslash left(L\; \backslash times\; M\; \backslash times\; R\_2\backslash right)\backslash right]$$

Symmetric difference ∆ and finite ⨯

$$L\; \backslash times\; \backslash left(R\; \backslash ,\backslash triangle\backslash ,\; R\_2\backslash right)\; ~=~\; \backslash left[L\; \backslash times\; \backslash left(R\; \backslash ,\backslash setminus\backslash ,\; R\_2\backslash right)\backslash right]\; \backslash ,\backslash cup\backslash ,\; \backslash left[L\; \backslash times\; \backslash left(R\_2\; \backslash ,\backslash setminus\backslash ,\; R\backslash right)\backslash right]$$$$\backslash left(L\; \backslash ,\backslash triangle\backslash ,\; L\_2\backslash right)\; \backslash times\; R\; ~=~\; \backslash left[\backslash left(L\; \backslash ,\backslash setminus\backslash ,\; L\_2\backslash right)\; \backslash times\; R\backslash right]\; \backslash ,\backslash cup\backslash ,\; \backslash left[\backslash left(L\_2\; \backslash ,\backslash setminus\backslash ,\; L\backslash right)\; \backslash times\; R\backslash right]$$

In general,

\left(L \triangle L _{2\right)} x \left(R \triangle R _{2\right)} need not be a subset nor a superset of \left(L x R\right) \triangle \left(L _{2} x R _{2\right).}

Arbitrary families of sets

Let

\left(L _{i\right)} _{i} , \left(R _{j\right)} _{j} , and \left(S _{i,j} \right) _{(i,} be indexed families of sets. Whenever the assumption is needed, then all indexing sets, such as I and J, are assumed to be non-empty.

Definitions

A or (more briefly) a refers to a set whose elements are sets.

An is a function from some set, called its, into some family of sets. An indexed family of sets will be denoted by

\left(L _{i\right)} _{i} , where this notation assigns the symbol I for the indexing set and for every index i \in I, assigns the symbol L _{i} to the value of the function at i. The function itself may then be denoted by the symbol L _{\bull,} which is obtained from the notation \left(L _{i\right)} _{i} by replacing the index i with a bullet symbol \bullet; explicitly, L _{\bull} is the function:which may be summarized by writing L _{\bull} = \left(L _{i\right)} _{i} .

Any given indexed family of sets

L _{\bull} = \left(L _{i\right)} _{i} (which is a function) can be canonically associated with its image/range \operatorname{Im} L _{\bull} ~\stackrel{\scriptscriptstyle def }~ \left\ (which is a family of sets). Conversely, any given family of sets l{B} may be associated with the l{B} -indexed family of sets (B) _{B} }, which is technically the identity map l{B} \to l{B}. However, this is a bijective correspondence because an indexed family of sets L _{\bull} = \left(L _{i\right)} _{i} is required to be injective (that is, there may exist distinct indices i ≠ j such as L _{i} = L _{j} ), 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).

Arbitrary unions defined

If

I = \varnothing then c up _{i} L _{i} = \{x ~:~ thereexists i \in \varnothing suchthat x \in L _{i\}} = \varnothing, which is somethings called the (despite being called a convention, this equality follows from the definition).

If

l{B} is a family of sets then \cup l{B} denotes the set: $$\backslash bigcup\; \backslash mathcal\; ~~\backslash stackrel~\; \backslash bigcup\_\; B\; ~~\backslash stackrel~\; \backslash .$$

Arbitrary intersections defined

If

I ≠ \varnothing then

If

l{B} ≠ \varnothing is a family of sets then \cap l{B} denotes the set: $$\backslash bigcap\; \backslash mathcal\; ~~\backslash stackrel~\; \backslash bigcap\_\; B\; ~~\backslash stackrel~\; \backslash \; ~=~\; \backslash .$$

Nullary intersections

If

I = \varnothing then$$\backslash bigcap\_\; L\_i\; =\; \backslash$$where every possible thing x in the universe vacuously satisfied the condition: "if i \in \varnothing then x \in L _{i} ". Consequently, { style c ap\limits _{i} } L_i = \ consists of in the universe.

So if

I = \varnothing and:X then { style c ap\limits _{i} } L_i = \ ~=~ X.

1. otherwise, if you are working in a model in which "the class of all things

x " is not a set (by far the most common situation) then { style c ap\limits _{i} } L_i is because { style c ap\limits _{i} } L_i consists of, which makes { style c ap\limits _{i} } L_i a proper class and 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 of sets or an refers to the intersection of a finite collection of sets.

Some authors adopt the so called , 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

X then some author may declare that the empty intersection of these sets be equal to X. 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 X so if there are multiple sets under consideration, which is commonly the case, then the value of the empty intersection risks becoming ambiguous).

Multiple index sets$$\backslash bigcup\_\; S\_\; ~~\backslash stackrel~\; \backslash bigcup\_\; S\_$$$$\backslash bigcap\_\; S\_\; ~~\backslash stackrel~\; \backslash bigcap\_\; S\_$$

Distributing unions and intersections

Binary ⋂ of arbitrary ⋃'s

and

• If all

\left(L _{i\right)} _{i} are pairwise disjoint and all \left(R _{j\right)} _{j} are also pairwise disjoint, then so are all \left(L _{i} \cap R _{j\right)} _{(i,} (that is, if (i, j) ≠ \left(i _{2,} j _{2\right)} then \left(L _{i} \cap R _{j\right)} \cap \left(L _{i _{2}} \cap R _{j _{2}} \right) = \varnothing ).

• Importantly, if

I = J then in general, $$~\backslash left(\backslash bigcup\_\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcup\_\; R\_i\backslash right)\; ~~\backslash color\backslash color~~\; \backslash bigcup\_\; \backslash left(L\_i\; \backslash cap\; R\_i\backslash right)~$$ (an example of this is given below). The single union on the right hand side be over all pairs (i, j) \in I x I: $$~\backslash left(\backslash bigcup\_\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcup\_\; R\_i\backslash right)\; ~~=~~\; \backslash bigcup\_\; \backslash left(L\_i\; \backslash cap\; R\_j\backslash right).~$$ The same is usually true for other similar non-trivial set equalities and relations that depend on two (potentially unrelated) indexing sets I and J (such as or). Two exceptions are (unions of unions) and (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).

• : Let

X ≠ \varnothing and let I = \{ 1 , 2 \}. Let L _{1} \colon = R _{2} \colon = X and let L _{2} \colon = R _{1} \colon = \varnothing. Then $$X\; =\; X\; \backslash cap\; X\; =\; \backslash left(L\_1\; \backslash cup\; L\_2\backslash right)\; \backslash cap\; \backslash left(R\_2\; \backslash cup\; R\_2\backslash right)\; =\; \backslash left(\backslash bigcup\_\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcup\_\; R\_i\backslash right)\; ~\backslash neq~\; \backslash bigcup\_\; \backslash left(L\_i\; \backslash cap\; R\_i\backslash right)\; =\; \backslash left(L\_1\; \backslash cap\; R\_1\backslash right)\; \backslash cup\; \backslash left(L\_2\; \backslash cap\; R\_2\backslash right)\; =\; \backslash varnothing\; \backslash cup\; \backslash varnothing\; =\; \backslash varnothing.$$ Furthermore, $$\backslash varnothing\; =\; \backslash varnothing\; \backslash cup\; \backslash varnothing\; =\; \backslash left(L\_1\; \backslash cap\; L\_2\backslash right)\; \backslash cup\; \backslash left(R\_2\; \backslash cap\; R\_2\backslash right)\; =\; \backslash left(\backslash bigcap\_\; L\_i\backslash right)\; \backslash cup\; \backslash left(\backslash bigcap\_\; R\_i\backslash right)\; ~\backslash neq~\; \backslash bigcap\_\; \backslash left(L\_i\; \backslash cup\; R\_i\backslash right)\; =\; \backslash left(L\_1\; \backslash cup\; R\_1\backslash right)\; \backslash cap\; \backslash left(L\_2\; \backslash cup\; R\_2\backslash right)\; =\; X\; \backslash cap\; X\; =\; X.$$

Binary ⋃ of arbitrary ⋂'s

and

• Importantly, if

I = J then in general, $$~\backslash left(\backslash bigcap\_\; L\_i\backslash right)\; \backslash cup\; \backslash left(\backslash bigcap\_\; R\_i\backslash right)\; ~~\backslash color\backslash color~~\; \backslash bigcap\_\; \backslash left(L\_i\; \backslash cup\; R\_i\backslash right)~$$ (an example of this is given above). The single intersection on the right hand side be over all pairs (i, j) \in I x I: $$~\backslash left(\backslash bigcap\_\; L\_i\backslash right)\; \backslash cup\; \backslash left(\backslash bigcap\_\; R\_i\backslash right)\; ~~=~~\; \backslash bigcap\_\; \backslash left(L\_i\; \backslash cup\; R\_j\backslash right).~$$

Arbitrary ⋂'s and arbitrary ⋃'s

Incorrectly distributing by swapping ⋂ and ⋃

Naively swapping

{ style c up\limits _{i} }\; and { style c ap\limits _{j} }\; may produce a different set

The following inclusion always holds:

In general, equality need not hold and moreover, the right hand side depends on how for each fixed

i \in I, the sets \left(S _{i,j} \right) _{j} are labelled; and analogously, the left hand side depends on how for each fixed j \in J, the sets \left(S _{i,j} \right) _{i} 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
  \cup and \cap are swapped, let I \colon = J \colon = \{ 1 , 2 \}, and let S _{11} = \{ 1 , 2 \},~S _{12} = \{ 1 , 3 \},~S _{21} = \{ 3 , 4 \}, and S _{22} = \{ 2 , 4 \}. Then $$\backslash \; =\; \backslash \; \backslash cup\; \backslash \; =\; \backslash left(S\_\; \backslash cap\; S\_\backslash right)\; \backslash cup\; \backslash left(S\_\; \backslash cap\; S\_\backslash right)\; =\; \backslash bigcup\_\; \backslash left(\backslash bigcap\_\; S\_\backslash right)\; ~\backslash neq~\; \backslash bigcap\_\; \backslash left(\backslash bigcup\_\; S\_\backslash right)\; =\; \backslash left(S\_\; \backslash cup\; S\_\backslash right)\; \backslash cap\; \backslash left(S\_\; \backslash cup\; S\_\backslash right)\; =\; \backslash .$$ If S _{11} and S _{21} are swapped while S _{12} and S _{22} are unchanged, which gives rise to the sets \hat{S} _{11} \colon = \{ 3 , 4 \},~\hat{S} _{12} \colon = \{ 1 , 3 \},~\hat{S} _{21} \colon = \{ 1 , 2 \}, and \hat{S} _{22} \colon = \{ 2 , 4 \}, then $$\backslash \; =\; \backslash \; \backslash cup\; \backslash \; =\; \backslash left(\backslash hat\_\; \backslash cap\; \backslash hat\_\backslash right)\; \backslash cup\; \backslash left(\backslash hat\_\; \backslash cap\; \backslash hat\_\backslash right)\; =\; \backslash bigcup\_\; \backslash left(\backslash bigcap\_\; \backslash hat\_\backslash right)\; ~\backslash neq~\; \backslash bigcap\_\; \backslash left(\backslash bigcup\_\; \backslash hat\_\backslash right)\; =\; \backslash left(\backslash hat\_\; \backslash cup\; \backslash hat\_\backslash right)\; \backslash cap\; \backslash left(\backslash hat\_\; \backslash cup\; \backslash hat\_\backslash right)\; =\; \backslash .$$ In particular, the left hand side is no longer \{ 1 , 4 \}, which shows that the left hand side { style c up\limits _{i} } \; S_ depends on how the sets are labelled. If instead S _{11} and S _{12} are swapped while S _{21} and S _{22} are unchanged, which gives rise to the sets \overline{S} _{11} \colon = \{ 1 , 3 \},~ \overline{S} _{12} \colon = \{ 1 , 2 \},~ \overline{S} _{21} \colon = \{ 3 , 4 \}, and \overline{S} _{22} \colon = \{ 2 , 4 \}, then both the left hand side and right hand side are equal to \{ 1 , 4 \}, which shows that the right hand side also depends on how the sets are labeled.

Equality in can hold under certain circumstances, such as in, which is the special case where

\left(S _{i,j} \right) _{(i,j)} is \left(L _{i} \setminus R _{j\right)} _{(i,j)} (that is, S _{i,j} \colon = L _{i} \setminus R _{j} with the same indexing sets I and J ), or such as in, which is the special case where \left(S _{i,j} \right) _{(i,j)} is \left(L _{i} \setminus R _{j\right)} _{(j,} (that is, \hat{S} _{j,i} \colon = L _{i} \setminus R _{j} with the indexing sets I and J swapped).For a correct formula that extends the distributive laws, an approach other than just switching \cup and \cap is needed.

Correct distributive laws

Suppose that for each

i \in I, J _{i} is a non-empty index set and for each j \in J _{i,} let T _{i,j} be any set (for example, to apply this law to \left(S _{i,j} \right) _{(i,} , use J _{i} \colon = J for all i \in I and use T _{i,j} \colon = S _{i,j} for all i \in I and all j \in J _{i} = J ). Let$$J\_\; ~\backslash stackrel~\; \backslash prod\_\; J\_i$$ denote the Cartesian product, which can be interpreted as the set of all functions f ~:~ I ~\to~ { style c up\limits _{i} } J_i such that f(i) \in J _{i} for every i \in I. Such a function may also be denoted using the tuple notation \left(f _{i\right)} _{i} where f _{i} ~\stackrel{\scriptscriptstyle def }~ f(i) for every i \in I and conversely, a tuple \left(f _{i\right)} _{i} is just notation for the function with domain I whose value at i \in I is f _{i;} both notations can be used to denote the elements of { style \prod} J _{\bull} . Then

where

{ style \prod} J _{\bull} ~\stackrel{\scriptscriptstyle def }~ J_i.

Applying the distributive laws

In the particular case where all

J _{i} are equal (that is, J _{i} = J _{i _{2}} for all i, i _{2} \in I, which is the case with the family \left(S _{i,j} \right) _{(i,} , for example), then letting J denote this common set, the Cartesian product will be { style \prod} J _{\bull} ~\stackrel{\scriptscriptstyle def }~ J_i = J = J^I, which is the set of all functions of the form f ~:~ I ~\to~ J. The above set equalities and, respectively become:$$\backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; S\_\; =\; \backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; S\_$$$$\backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; S\_\; =\; \backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; S\_$$

which when combined with implies: $$\backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; S\_~=~\; \backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; S\_~~\backslash color\backslash color~~\; \backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; S\_~=~\; \backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; S\_$$where

• on the left hand side, the indices

f and i range over f \in J ^{I} and i \in I (so the subscripts of S _{i,f(i)} range over i \in I and f(i) \in f(I) \subseteq J )

• on the right hand side, the indices

g and j range over g \in I ^{J} and j \in J (so the subscripts of S _{g(j),j} range over j \in J and g(j) \in g(J) \subseteq I ).

To apply the general formula to the case of

\left(C _{k\right)} _{k} and \left(D _{l} \right) _{l} , use I \colon = \{ 1 , 2 \}, J _{1} \colon = K, J _{2} \colon = L, and let T _{1,k} \colon = C _{k} for all k \in J _{1} and let T _{2,l} \colon = D _{l} for all l \in J _{2.} Every map f \in { style \prod} J _{\bull} ~\stackrel{\scriptscriptstyle def }~ J_i = J_1 \times J_2 = K \times L can be bijectively identified with the pair \left(f( 1 ), f( 2 )\right) \in K x L (the inverse sends (k,l) \in K x L to the map f _{(k,l)} \in { style \prod} J _{\bull} defined by 1 \mapsto k and 2 \mapsto l; this is technically just a change of notation). Recall that was $$~\backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; T\_\; =\; \backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; T\_.~$$ Expanding and simplifying the left hand side gives$$\backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; T\_=\; \backslash left(\backslash bigcup\_\; T\_\backslash right)\; \backslash cap\; \backslash left(\backslash ;\backslash bigcup\_\; T\_\backslash right)\; =\; \backslash left(\backslash bigcup\_\; T\_\backslash right)\; \backslash cap\; \backslash left(\backslash ;\backslash bigcup\_\; T\_\backslash right)\; =\; \backslash left(\backslash bigcup\_\; C\_k\backslash right)\; \backslash cap\; \backslash left(\backslash ;\backslash bigcup\_\; D\_l\backslash right)$$and doing the same to the right hand side gives:$$\backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; T\_=\; \backslash bigcup\_\; \backslash left(T\_\; \backslash cap\; T\_\backslash right)\; =\; \backslash bigcup\_\; \backslash left(C\_\; \backslash cap\; D\_\backslash right)\; =\; \backslash bigcup\_\; \backslash left(C\_k\; \backslash cap\; D\_l\backslash right)\; =\; \backslash bigcup\_\; \backslash left(C\_k\; \backslash cap\; D\_l\backslash right).$$

Thus the general identity reduces down to the previously given set equality : $$\backslash left(\backslash bigcup\_\; C\_k\backslash right)\; \backslash cap\; \backslash ;\backslash bigcup\_\; D\_l\; =\; \backslash bigcup\_\; \backslash left(C\_k\; \backslash cap\; D\_l\backslash right).$$

Distributing subtraction over ⋃ and ⋂

The next identities are known as De Morgan's laws.

The following four set equalities can be deduced from the equalities - above.

In general, naively swapping

\cup and \cap may produce a different set (see this note for more details). The equalities $$\backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; \backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)\; ~=~\; \backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; \backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)\backslash quad\; \backslash text\; \backslash quad\; \backslash bigcup\_\; \backslash ;\; \backslash bigcap\_\; \backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)\; ~=~\; \backslash bigcap\_\; \backslash ;\; \backslash bigcup\_\; \backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)$$ found in and are thus unusual in that they state exactly that swapping \cup and \cap will change the resulting set.

Commutativity and associativity of ⋃ and ⋂

Commutativity:

$$\backslash bigcup\_\; S\_\; ~~\backslash stackrel~\; \backslash bigcup\_\; S\_\; ~=~\; \backslash bigcup\_\; \backslash left(\backslash bigcup\_\; S\_\backslash right)\; ~=~\; \backslash bigcup\_\; \backslash left(\backslash bigcup\_\; S\_\backslash right)$$

$$\backslash bigcap\_\; S\_\; ~~\backslash stackrel~\; \backslash bigcap\_\; S\_\; ~=~\; \backslash bigcap\_\; \backslash left(\backslash bigcap\_\; S\_\backslash right)\; ~=~\; \backslash bigcap\_\; \backslash left(\backslash bigcap\_\; S\_\backslash right)$$

Unions of unions and intersections of intersections:

$$\backslash left(\backslash bigcup\_\; L\_i\backslash right)\; \backslash cup\; R\; ~=~\; \backslash bigcup\_\; \backslash left(L\_i\; \backslash cup\; R\backslash right)$$$$\backslash left(\backslash bigcap\_\; L\_i\backslash right)\; \backslash cap\; R\; ~=~\; \backslash bigcap\_\; \backslash left(L\_i\; \backslash cap\; R\backslash right)$$and

and if

I = J then also:^[4]

Cartesian products Π of arbitrarily many sets

Intersections ⋂ of Π

If

\left(S _{i,j} \right) _{(i,j)} is a family of sets then

• Moreover, a tuple

\left(x _{i\right)} _{i} belongs to the set in above if and only if x _{i} \in S _{i,j} for all i \in I and all j \in J.

In particular, if

\left(L _{i\right)} _{i} and \left(R _{i\right)} _{i} are two families indexed by the same set then $$\backslash left(\backslash prod\_\; L\_i\backslash right)\; \backslash cap\; \backslash prod\_\; R\_i\; ~=~\; \backslash prod\_\; \backslash left(L\_i\; \backslash cap\; R\_i\backslash right)$$So for instance, $$(L\; \backslash times\; R)\; \backslash cap\; \backslash left(L\_2\; \backslash times\; R\_2\backslash right)\; ~=~\; \backslash left(L\; \backslash cap\; L\_2\backslash right)\; \backslash times\; \backslash left(R\; \backslash cap\; R\_2\backslash right)$$$$(L\; \backslash times\; R)\; \backslash cap\; \backslash left(L\_2\; \backslash times\; R\_2\backslash right)\; \backslash cap\; \backslash left(L\_3\; \backslash times\; R\_3\backslash right)\; ~=~\; \backslash left(L\; \backslash cap\; L\_2\; \backslash cap\; L\_3\backslash right)\; \backslash times\; \backslash left(R\; \backslash cap\; R\_2\; \backslash cap\; R\_3\backslash right)$$ and $$(L\; \backslash times\; M\; \backslash times\; R)\; \backslash cap\; \backslash left(L\_2\; \backslash times\; M\_2\; \backslash times\; R\_2\backslash right)\; ~=~\; \backslash left(L\; \backslash cap\; L\_2\backslash right)\; \backslash times\; \backslash left(M\; \backslash cap\; M\_2\backslash right)\; \backslash times\; \backslash left(R\; \backslash cap\; R\_2\backslash right)$$

Intersections of products indexed by different sets

Let

\left(L _{i\right)} _{i} and \left(R _{j\right)} _{j} be two families indexed by different sets.

Technically,

I ≠ J implies \left({ style\prod\limits _{i} } L_i\right) \cap R_j = \varnothing. 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

I : = \{ 1 , 2 \} and J : = \{ 1 , 2 , 3 \} with all sets equal to \R then { style\prod\limits _{i} } L_i = \R = \R^2 and { style\prod\limits _{j} } R_j = \R = \R^3 where \R ^{2} \cap \R ^{3} = \varnothing , for example, { style\prod\limits _{i} }} \R = \R^2 is identified as a subset of { style\prod\limits _{j} }} \R = \R^3 through some injection, such as maybe (x, y) \mapsto (x, y, 0 ) for instance; however, in this particular case the product { style\prod\limits _{i} }} L_i actually represents the J -indexed product { style\prod\limits _{j} }} L_i where L _{3} : = \{ 0 \}.

• For another example, take

I : = \{ 1 , 2 \} and J : = \{ 1 , 2 , 3 \} with L _{1} : = \R ^{2} and L _{2,} R _{1,} R _{2,} and R _{3} all equal to \R. Then { style\prod\limits _{i} }L_i = \R^2 \times \R and { style\prod\limits _{j} } R_j = \R \times \R \times \R, which can both be identified as the same set via the bijection that sends ((x, y), z) \in \R ^{2} x \R to (x, y, z) \in \R x \R x \R. Under this identification, \left({ style\prod\limits _{i} } L_i\right) \cap \, R_j ~=~ \R^3.

Binary ⨯ distributes over arbitrary ⋃ and ⋂

The binary Cartesian product ⨯ distributes over arbitrary intersections (when the indexing set is not empty) and over arbitrary unions:

Distributing arbitrary Π over arbitrary ⋃

Suppose that for each

i \in I, J _{i} is a non-empty index set and for each j \in J _{i,} let T _{i,j} be any set (for example, to apply this law to \left(S _{i,j} \right) _{(i,} , use J _{i} \colon = J for all i \in I and use T _{i,j} \colon = S _{i,j} for all i \in I and all j \in J _{i} = J ). Let$$J\_\; ~\backslash stackrel~\; \backslash prod\_\; J\_i$$ denote the Cartesian product, which (as mentioned above) can be interpreted as the set of all functions f ~:~ I ~\to~ { style c up\limits _{i} } J_i such that f(i) \in J _{i} for every i \in I .Then

where

{ style \prod} J _{\bull} ~\stackrel{\scriptscriptstyle def }~ J_i.

Unions ⋃ of Π

For unions, only the following is guaranteed in general:$$\backslash bigcup\_\; \backslash ;\; \backslash prod\_\; S\_\; ~~\backslash color\backslash color~~\; \backslash prod\_\; \backslash ;\; \backslash bigcup\_\; S\_\; \backslash qquad\; \backslash text\; \backslash qquad\; \backslash bigcup\_\; \backslash ;\; \backslash prod\_\; S\_\; ~~\backslash color\backslash color~~\; \backslash prod\_\; \backslash ;\; \backslash bigcup\_\; S\_$$where

\left(S _{i,j} \right) _{(i,j)} is a family of sets.

• Example where equality fails: Let

I = J = \{ 1 , 2 \}, let S _{1,1} = S _{2,2} = \varnothing, let X ≠ \varnothing, and let S _{1,2} = S _{2,1} = X. Then $$\backslash varnothing\; =\; \backslash varnothing\; \backslash cup\; \backslash varnothing\; =\; \backslash left(\backslash prod\_\; S\_\backslash right)\; \backslash cup\; \backslash left(\backslash prod\_\; S\_\backslash right)\; =\; \backslash bigcup\_\; \backslash ;\; \backslash prod\_\; S\_\; ~~\backslash color\backslash color~~\; \backslash prod\_\; \backslash ;\; \backslash bigcup\_\; S\_\; =\; \backslash left(\backslash bigcup\_\; S\_\backslash right)\; \backslash times\; \backslash left(\backslash bigcup\_\; S\_\backslash right)\; =\; X\; \backslash times\; X.$$ More generally, $\backslash varnothing\; =\; \backslash bigcup\_\; \backslash ;\; \backslash prod\_\; S\_$ if and only if for each j \in J, at least one of the sets in the I -indexed collections of sets S _{\bullet,j} = \left(S _{i,j} \right) _{i\in} is empty, while $\backslash prod\_\; \backslash ;\; \backslash bigcup\_\; S\_\; \backslash neq\; \backslash varnothing$ if and only if for each i \in I, at least one of the sets in the J -indexed collections of sets S _{i,\bullet} = \left(S _{i,j} \right) _{j\in} is not empty.

However,

Difference \ of Π

If

\left(L _{i\right)} _{i} and \left(R _{i\right)} _{i} are two families of sets then:so for instance,and $$(L\; \backslash times\; M\; \backslash times\; R)\; ~\backslash setminus~\; \backslash left(L\_2\; \backslash times\; M\_2\; \backslash times\; R\_2\backslash right)\; ~=~\; \backslash left[\backslash left(L\; \backslash ,\backslash setminus\backslash ,\; L\_2\backslash right)\; \backslash times\; M\; \backslash times\; R\backslash right]\; ~\backslash cup~\; \backslash left[L\; \backslash times\; \backslash left(M\; \backslash ,\backslash setminus\backslash ,\; M\_2\backslash right)\; \backslash times\; R\backslash right]\; ~\backslash cup~\; \backslash left[L\; \backslash times\; M\; \backslash times\; \backslash left(R\; \backslash ,\backslash setminus\backslash ,\; R\_2\backslash right)\backslash right]$$

Symmetric difference ∆ of Π

Functions and sets

Let

f : X \to Y be any function.

Let

L and R be completely arbitrary sets. Assume A \subseteq X and C \subseteq Y.

Definitions

Let

f : X \to Y be any function, where we denote its X by \operatorname{domain} f and denote its Y by \operatorname{codomain} f.

Many of the identities below do not actually require that the sets be somehow related to

f 's domain or codomain (that is, to X or Y ) so when some kind of relationship is necessary then it will be clearly indicated. Because of this, in this article, if L is declared to be "," and it is not indicated that L must be somehow related to X or Y (say for instance, that it be a subset X or Y ) then it is meant that L is truly arbitrary.^[5] This generality is useful in situations where f : X \to Y is a map between two subsets X \subseteq U and Y \subseteq V of some larger sets U and V, and where the set L might not be entirely contained in X = \operatorname{domain} f and/or Y = \operatorname{codomain} f (e.g. if all that is known about L is that L \subseteq U ); in such a situation it may be useful to know what can and cannot be said about f(L) and/or f ^{-1} (L) without having to introduce a (potentially unnecessary) intersection such as: f(L \cap X) and/or f ^{-1} (L \cap Y).

Images and preimages of sets

If

L is set then the is defined to be the set: $$f(L)\; ~\backslash stackrel~\; \backslash$$while the is: $$f^(L)\; ~\backslash stackrel~\; \backslash$$where if L = \{s\} is a singleton set then the or is$$f^(s)\; ~\backslash stackrel~\; f^(\backslash )\; ~=~\; \backslash .$$

Denote by

\operatorname{Im} f or \operatorname{image} f the or of f : X \to Y, which is the set: $$\backslash operatorname\; f\; ~\backslash stackrel~\; f(X)\; ~\backslash stackrel~\; f(\backslash operatorname\; f)\; ~=~\; \backslash .$$

Saturated sets

See main article: Saturated set.

A set

A is said to be or a if any of the following equivalent conditions are satisfied:

1. There exists a set R such that A = f ^{-1} (R).
   • Any such set
   R necessarily contains f(A) as a subset.
   • Any set not entirely contained in the domain of
   f cannot be f -saturated.
2. A = f ^{-1} (f(A)).
3. A \supseteq f ^{-1} (f(A)) and A \subseteq \operatorname{domain} f.
   • The inclusion
   L \cap \operatorname{domain} f \subseteq f ^{-1} (f(L)) always holds, where if A \subseteq \operatorname{domain} f then this becomes A \subseteq f ^{-1} (f(A)).
4. A \subseteq \operatorname{domain} f and if a \in A and x \in \operatorname{domain} f satisfy f(x) = f(a), then x \in A.
5. Whenever a fiber of f intersects A, then A contains the entire fiber. In other words, A contains every f -fiber that intersects it.
• Explicitly: whenever
y \in \operatorname{Im} f is such that A \cap f ^{-1} (y) ≠ \varnothing, then f ^{-1} (y) s\subseteq A.
• In both this statement and the next, the set
\operatorname{Im} f may be replaced with any superset of \operatorname{Im} f (such as \operatorname{codomain} f ) and the resulting statement will still be equivalent to the rest.
6. The intersection of A with a fiber of f is equal to the empty set or to the fiber itself.
   • Explicitly: for every
   y \in \operatorname{Im} f, the intersection A \cap f ^{-1} (y) is equal to the empty set \varnothing or to f ^{-1} (y) (that is, A \cap f ^{-1} (y) = \varnothing or A \cap f ^{-1} (y) = f ^{-1} (y) ).

For a set A to be f -saturated, it is necessary that A \subseteq \operatorname{domain} f.

Compositions and restrictions of functions

If

f and g are maps then g \circ f denotes the map $$g\; \backslash circ\; f\; ~:~\; \backslash \; ~\backslash to~\; \backslash operatorname\; g$$with domain and codomain defined by$$(g\; \backslash circ\; f)(x)\; ~\backslash stackrel~\; g(f(x)).$$

The denoted by

f \ vert _{L,} is the map $$f\backslash big\backslash vert\_L\; ~:~\; L\; \backslash cap\; \backslash operatorname\; f\; ~\backslash to~\; Y$$with \operatorname{domain} f \ vert _{L} ~ = ~ L \cap \operatorname{domain} f defined by sending x \in L \cap \operatorname{domain} f to f(x); that is, $$f\backslash big\backslash vert\_L(x)\; ~\backslash stackrel~\; f\; (x).$$ Alternatively, ~f \ vert _{L} ~ = ~ f \circ \operatorname{In}~ where ~\operatorname{In} ~:~ L \cap X \to X~ denotes the inclusion map, which is defined by \operatorname{In}(s) ~\stackrel{\scriptscriptstyle def }~ s.

(Pre)Images of arbitrary unions ⋃'s and intersections ⋂'s

If

\left(L _{i\right)} _{i} is a family of arbitrary sets indexed by I ≠ \varnothing then:

So of these four identities, it is that are not always preserved. Preimages preserve all basic set operations. Unions are preserved by both images and preimages.

If all

L _{i} are f -saturated then c ap _{i} L _{i} be will be f -saturated and equality will hold in the first relation above; explicitly, this means:

If

\left(A _{i\right)} _{i} is a family of arbitrary subsets of X = \operatorname{domain} f, which means that A _{i} \subseteq X for all i, then becomes:

(Pre)Images of binary set operations

Throughout, let

L and R be any sets and let f : X \to Y be any function.

Summary

As the table below shows, set equality is guaranteed for of: intersections, set subtractions, and symmetric differences.

Image	Preimage
~~~~f(L \cup R) ~ = ~ f(L) \cup f(R)	f ^{-1} (L \cup R) ~ = ~ f ^{-1} (L) \cup f ^{-1} (R)	None
$$f(L\; \backslash cap\; R)\; ~\backslash subseteq~\; f(L)\; \backslash cap\; f(R)$$	f ^{-1} (L \cap R) ~ = ~ f ^{-1} (L) \cap f ^{-1} (R)	None
$$f(L\; \backslash setminus\; R)\; ~\backslash supseteq~\; f(L)\; \backslash setminus\; f(R)$$	\begin{alignat}{ 4 } f ^{-1} (L) \setminus f ^{-1} (R) & = f ^{-1} &&( &&L &&\setminus &&R) \\ & = f ^{-1} &&( &&L &&\setminus [&&R \cap \operatorname{Im} f]) \\ & = f ^{-1} &&([&&L \cap \operatorname{Im} f] &&\setminus &&R) \\ & = f ^{-1} &&([&&L \cap \operatorname{Im} f] &&\setminus [&&R \cap \operatorname{Im} f]) \end{alignat}	None
$$f(X\; \backslash setminus\; R)\; ~\backslash supseteq~\; f(X)\; \backslash setminus\; f(R)$$	\begin{alignat}{ 4 } X \setminus f ^{-1} (R) & = f ^{-1} (&&Y &&\setminus &&R) \\ & = f ^{-1} (&&Y &&\setminus [&&R \cap \operatorname{Im} f]) \\ & = f ^{-1} (&&\operatorname{Im} f &&\setminus &&R) \\ & = f ^{-1} (&&\operatorname{Im} f &&\setminus [&&R \cap \operatorname{Im} f]) \end{alignat} ^[6]	None
$$f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; ~\backslash supseteq~\; f(L)\; ~\backslash triangle~\; f(R)$$	f ^{-1} \left(L ~\triangle~ R\right) ~ = ~ f ^{-1} (L) ~\triangle~ f ^{-1} (R)	None

Preimages preserve set operations

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 preserve unions

Images of unions are well-behaved:

but images of the other basic set operations are since only the following are guaranteed in general:

L \setminus R or else they can naturally as the set subtraction of two sets: $$L\; \backslash cap\; R\; =\; L\; \backslash setminus\; (L\; \backslash setminus\; R)\; \backslash quad\; \backslash text\; \backslash quad\; L\; \backslash triangle\; R\; =\; (L\; \backslash cup\; R)\; \backslash setminus\; (L\; \backslash cap\; R).$$

If

L = X then f(X \setminus R) \supseteq f(X) \setminus f(R) where as in the more general case, equality is not guaranteed. If f is surjective then f(X \setminus R) ~\supseteq~ Y \setminus f(R), which can be rewritten as: f\left(R ^{\complement\right)} ~\supseteq~ f(R) ^{\complement} if R ^{\complement} ~\stackrel{\scriptscriptstyle def }~ X \setminus R and f(R) ^{\complement} ~\stackrel{\scriptscriptstyle def }~ Y \setminus f(R).

Counter-examples: images of operations not distributing

If

f : \{ 1 , 2 \} \to Y is constant, L = \{ 1 \}, and R = \{ 2 \} then all four of the set containmentsare 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.

Let

f : X \to Y be any constant function with image f(X) = \{y\} and suppose that L, R \subseteq X are non-empty disjoint subsets; that is, L ≠ \varnothing, R ≠ \varnothing, and L \cap R = \varnothing, which implies that all of the sets L ~\triangle~ R = L \cup R, L \setminus R = L, and X \setminus R \supseteq L \setminus R are not empty and so consequently, their images under f are all equal to \{y\}.

1. The containment
   ~f(L \setminus R) ~\supsetneq~ f(L) \setminus f(R)~ is strict: $$\backslash \; ~=~\; f(L\; \backslash setminus\; R)\; ~\backslash neq~\; f(L)\; \backslash setminus\; f(R)\; ~=~\; \backslash \; \backslash setminus\; \backslash \; ~=~\; \backslash varnothing$$In words: functions might not distribute over set subtraction \setminus
2. The containment ~f(X \setminus R) ~\supsetneq~ f(X) \setminus f(R)~ is strict: $$\backslash \; ~=~\; f(X\; \backslash setminus\; R)\; ~\backslash neq~\; f(X)\; \backslash setminus\; f(R)\; ~=~\; \backslash \; \backslash setminus\; \backslash \; ~=~\; \backslash varnothing.$$
3. The containment ~f(L ~\triangle~ R) ~\supsetneq~ f(L) ~\triangle~ f(R)~ is strict: $$\backslash \; ~=~\; f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; ~\backslash neq~\; f(L)\; ~\backslash triangle~\; f(R)\; ~=~\; \backslash \; \backslash triangle\; \backslash \; ~=~\; \backslash varnothing$$In words: functions might not distribute over symmetric difference \triangle (which can be defined as the set subtraction of two sets: L \triangle R = (L \cup R) \setminus (L \cap R) ).
4. The containment ~f(L \cap R) ~\subsetneq~ f(L) \cap f(R)~ is strict: $$\backslash varnothing\; ~=~\; f(\backslash varnothing)\; ~=~\; f(L\; \backslash cap\; R)\; ~\backslash neq~\; f(L)\; \backslash cap\; f(R)\; ~=~\; \backslash \; \backslash cap\; \backslash \; ~=~\; \backslash$$In words: functions might not distribute over set intersection \cap (which can be defined as the set subtraction of two sets: L \cap R = L \setminus (L \setminus R) ).

\setminus (examples (1) and (2)) or else they can naturally 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

\subseteq or \supseteq ) can always be deduced by imagining the function f as being and the two sets (L and R ) as being non-empty disjoint subsets of its domain. This is because equality fails for such a function and sets: one side will be always be \varnothing and the other non-empty − from this fact, the correct choice of \subseteq or \supseteq can be deduced by answering: "which side is empty?" For example, to decide if the ? in $$f(L\; \backslash triangle\; R)\; \backslash setminus\; f(R)\; ~\backslash ;~?~\backslash ;~\; f((L\; \backslash triangle\; R)\; \backslash setminus\; R)$$should be \subseteq or \supseteq, pretend^[7] that f is constant and that L \triangle R and R are non-empty disjoint subsets of f 's domain; then the hand side would be empty (since f(L \triangle R) \setminus f(R) = \{f 'ssinglevalue \} \setminus \{f 'ssinglevalue \} = \varnothing ), which indicates that ? should be \subseteq (the resulting statement is always guaranteed to be true) because this is the choice that will make$$\backslash varnothing\; =\; \backslash text\; ~\backslash ;~?~\backslash ;~\; \backslash text$$true. Alternatively, the correct direction of containment can also be deduced by consideration of any constant f : \{ 1 , 2 \} \to Y with L = \{ 1 \} and R = \{ 2 \}.

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

f(L \cap R) always equals f(L) \cap f(R), or alternatively, whether or not f ^{-1} (L \cap R) always equals f ^{-1} (L) \cap f ^{-1} (R) (although \cap was used here, it can replaced by \cup, \setminus, or \triangle ). 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 f, L, and R ) 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 sets:

For any function

f : X \to Y, the following statements are equivalent:

1. f : X \to Y is injective.
   • This means:
   f(x) ≠ f(y) for all distinct x, y \in X.
2. f(L \cap R) = f(L) \cap f(R) forall L, R \subseteq X. (The equals sign = can be replaced with \supseteq ).
3. f(L \setminus R) = f(L) \setminus f(R) forall L, R \subseteq X. (The equals sign = can be replaced with \subseteq ).
4. f(X \setminus R) = f(X) \setminus f(R) forall ~~~~~R \subseteq X. (The equals sign = can be replaced with \subseteq ).
5. f(L \triangle R) = f(L) \triangle f(R) forall L, R \subseteq X. (The equals sign = can be replaced with \subseteq ).
6. Any one of the four statements (b) - (e) but with the words "for all" replaced with any one of the following:
   1. "for all singleton subsets"
      • In particular, the statement that results from (d) gives a characterization of injectivity that explicitly involves only one point (rather than two):
      f is injective if and only if f(x) \not\in f(X \setminus \{x\}) forevery x \in X.
   2. "for all disjoint singleton subsets"
      • 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).

   3. "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)

$$f(L\; \backslash cap\; R)\; ~\backslash subseteq~\; f(L)\; \backslash cap\; f(R)\; \backslash qquad\backslash qquad\; \backslash text$$

Characterizations of equality: The following statements are equivalent:

1. f(L \cap R) ~ = ~ f(L) \cap f(R)
2. f(L \cap R) ~\supseteq~ f(L) \cap f(R)
3. L \cap f ^{-1} (f(R)) ~\subseteq~ f ^{-1} (f(L \cap R))
   • The left hand side
   L \cap f ^{-1} (f(R)) is always equal to L \cap f ^{-1} (f(L) \cap f(R)) (because L \cap f ^{-1} (f(R)) ~\subseteq~ f ^{-1} (f(L)) always holds).
4. R \cap f ^{-1} (f(L)) ~\subseteq~ f ^{-1} (f(L \cap R))
5. L \cap f ^{-1} (f(R)) ~ = ~ f ^{-1} (f(L \cap R)) \cap L
6. R \cap f ^{-1} (f(L)) ~ = ~ f ^{-1} (f(L \cap R)) \cap R
7. If l \in L satisfies f(l) \in f(R) then f(l) \in f(L \cap R).
8. If y \in f(L) but y \notin f(L \cap R) then y \notin f(R).
9. f(L) \setminus f(L \cap R) ~\subseteq~ f(L) \setminus f(R)
10. f(R) \setminus f(L \cap R) ~\subseteq~ f(R) \setminus f(L)
11. f(L \cup R) \setminus f(L \cap R) ~\subseteq~ f(L) \triangle f(R)
12. Any of the above three conditions (i) - (k) but with the subset symbol \subseteq replaced with an equals sign = .

Sufficient conditions for equality: Equality holds if any of the following are true:

1. f is injective.^[8]
2. The restriction f \ vert _{L} is injective.
3. f ^{-1} (f(R)) ~\subseteq~ R
4. f ^{-1} (f(L)) ~\subseteq~ L
5. R is f -saturated; that is, f ^{-1} (f(R)) = R
6. L is f -saturated; that is, f ^{-1} (f(L)) = L
7. f(L) ~\subseteq~ f(L \cap R)
8. f(R) ~\subseteq~ f(L \cap R)
9. f(L \setminus R) ~\subseteq~ f(L) \setminus f(R) or equivalently, f(L \setminus R) ~ = ~ f(L) \setminus f(R)
10. f(R \setminus L) ~\subseteq~ f(R) \setminus f(L) or equivalently, f(R \setminus L) ~ = ~ f(R) \setminus f(L)
11. f\left(L ~\triangle~ R\right) \subseteq f(L) ~\triangle~ f(R) or equivalently, f\left(L ~\triangle~ R\right) = f(L) ~\triangle~ f(R)
12. R \cap \operatorname{domain} f \subseteq L
13. L \cap \operatorname{domain} f \subseteq R
14. R \subseteq L
15. L \subseteq R

In addition, the following always hold:$$f\backslash left(f^(L)\; \backslash cap\; R\backslash right)\; ~=~\; L\; \backslash cap\; f(R)$$$$f\backslash left(f^(L)\; \backslash cup\; R\backslash right)\; ~=~\; (L\; \backslash cap\; \backslash operatorname\; f)\; \backslash cup\; f(R)$$

Conditions for f(L\R) = f(L)\f(R)

$$f(L\; \backslash setminus\; R)\; ~\backslash supseteq~\; f(L)\; \backslash setminus\; f(R)\; \backslash qquad\backslash qquad\; \backslash text$$

Characterizations of equality: The following statements are equivalent:

1. f(L \setminus R) ~ = ~ f(L) \setminus f(R)
2. f(L \setminus R) ~\subseteq~ f(L) \setminus f(R)
3. L \cap f ^{-1} (f(R)) ~\subseteq~ R
4. L \cap f ^{-1} (f(R)) ~ = ~ L \cap R \cap \operatorname{domain} f
5. Whenever y \in f(L) \cap f(R) then L \cap f ^{-1} (y) \subseteq R.
6. $f(L)\; \backslash cap\; f(R)\; ~\backslash subseteq~\; \backslash left\backslash$
   • The set on the right hand side is always equal to
   \left\{y \in f(L \cap R) : L \cap f ^{-1} (y) \subseteq R\right\}.
7. $f(L)\; \backslash cap\; f(R)\; ~=~\; \backslash left\backslash$
   • This is the above condition (f) but with the subset symbol
   \subseteq replaced with an equals sign = .

Necessary conditions for equality (excluding characterizations): If equality holds then the following are necessarily true:

1. f(L \cap R) = f(L) \cap f(R), or equivalently f(L \cap R) \supseteq f(L) \cap f(R).
2. L \cap f ^{-1} (f(R)) ~ = ~ L \cap f ^{-1} (f(L \cap R)) or equivalently, L \cap f ^{-1} (f(R)) ~\subseteq~ f ^{-1} (f(L \cap R))
3. R \cap f ^{-1} (f(L)) ~ = ~ R \cap f ^{-1} (f(L \cap R))

Sufficient conditions for equality: Equality holds if any of the following are true:

1. f is injective.
2. The restriction f \ vert _{L} is injective.
3. f ^{-1} (f(R)) ~\subseteq~ R ^[9] or equivalently, R \cap \operatorname{domain} f ~ = ~ f ^{-1} (f(R))
4. R is f -saturated; that is, R = f ^{-1} (f(R)). ^[9]
5. f\left(L ~\triangle~ R\right) \subseteq f(L) ~\triangle~ f(R) or equivalently, f\left(L ~\triangle~ R\right) = f(L) ~\triangle~ f(R)

Conditions for f(X\R) = f(X)\f(R)

$$f(X\; \backslash setminus\; R)\; ~\backslash supseteq~\; f(X)\; \backslash setminus\; f(R)\; \backslash qquad\backslash qquad\; \backslash text\; f\; :\; X\; \backslash to\; Y$$

Characterizations of equality: The following statements are equivalent:

1. f(X \setminus R) ~ = ~ f(X) \setminus f(R)
2. f(X \setminus R) ~\subseteq~ f(X) \setminus f(R)
3. f ^{-1} (f(R)) \subseteq R
4. f ^{-1} (f(R)) = R \cap \operatorname{domain} f
5. R \cap \operatorname{domain} f is f -saturated.
6. Whenever y \in f(R) then f ^{-1} (y) \subseteq R.
7. $f(R)\; ~\backslash subseteq~\; \backslash left\backslash$
8. $f(R)\; ~=~\; \backslash left\backslash$

   where if R \subseteq \operatorname{domain} f then this list can be extended to include:

9. R is f -saturated; that is, R = f ^{-1} (f(R)).

Sufficient conditions for equality: Equality holds if any of the following are true:

1. f is injective.
2. R is f -saturated; that is, R = f ^{-1} (f(R)).

Conditions for f(L∆R) = f(L)∆f(R)

$$f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; ~\backslash supseteq~\; f(L)\; ~\backslash triangle~\; f(R)\; \backslash qquad\backslash qquad\; \backslash text$$

Characterizations of equality: The following statements are equivalent:

1. f\left(L ~\triangle~ R\right) = f(L) ~\triangle~ f(R)
2. f\left(L ~\triangle~ R\right) \subseteq f(L) ~\triangle~ f(R)
3. f(L \setminus R) = f(L) \setminus f(R)  and  f(R \setminus L) = f(R) \setminus f(L)
4. f(L \setminus R) \subseteq f(L) \setminus f(R)  and  f(R \setminus L) \subseteq f(R) \setminus f(L)
5. L \cap f ^{-1} (f(R)) ~\subseteq~ R  and  R \cap f ^{-1} (f(L)) ~\subseteq~ L
   • The inclusions
   L \cap f ^{-1} (f(R)) ~\subseteq~ f ^{-1} (f(L)) and R \cap f ^{-1} (f(L)) ~\subseteq~ f ^{-1} (f(R)) always hold.
6. L \cap f ^{-1} (f(R)) ~ = ~ R \cap f ^{-1} (f(L))
   • If this above set equality holds, then this set will also be equal to both
   L \cap R \cap \operatorname{domain} f and L \cap R \cap f ^{-1} (f(L \cap R)).
7. L \cap f ^{-1} (f(L \cap R)) ~ = ~ R \cap f ^{-1} (f(L \cap R))  and  f(L \cap R) ~\supseteq~ f(L) \cap f(R).

Necessary conditions for equality (excluding characterizations): If equality holds then the following are necessarily true:

1. f(L \cap R) = f(L) \cap f(R), or equivalently f(L \cap R) \supseteq f(L) \cap f(R).
2. L \cap f ^{-1} (f(L \cap R)) ~ = ~ R \cap f ^{-1} (f(L \cap R))

Sufficient conditions for equality: Equality holds if any of the following are true:

1. f is injective.
2. The restriction f \ vert _{L} is injective.

Exact formulas/equalities for images of set operations

Formulas for f(L\R) =

For any function

f : X \to Y and any sets L and R, ^[10]

Formulas for f(X\R) =

Taking

L : = X = \operatorname{domain} f in the above formulas gives:where the set \left\{ y \in f(R) : f ^{-1} (y) \subseteq R \right\} is equal to the image under f of the largest f -saturated subset of R.

• In general, only f(X \setminus R) \supseteq f(X) \setminus f(R) always holds and equality is not guaranteed; but replacing "f(R) " with its subset "\left\{ y \in f(R) : f ^{-1} (y) \subseteq R \right\} " results in a formula in which equality is guaranteed: $$f(X\; \backslash setminus\; R)\; \backslash ,=\backslash ,\; f(X)\; \backslash setminus\; \backslash left\backslash .$$ From this it follows that:^[11] $$f(X\; \backslash setminus\; R)\; =\; f(X)\; \backslash setminus\; f(R)\; \backslash quad\; \backslash text\; \backslash quad\; f(R)\; =\; \backslash left\backslash \; \backslash quad\; \backslash text\; \backslash quad\; f^(f(R))\; \backslash subseteq\; R.$$
• If f _{R} : = \left\{y \in f(X) : f ^{-1} (y) \subseteq R\right\} then f(X \setminus R) = f(X) \setminus f _{R,} which can be written more symmetrically as f(X \setminus R) = f _{X} \setminus f _{R} (since f _{X} = f(X) ).

Formulas for f(L∆R) =

It follows from

L \triangle R = (L \cup R) \setminus (L \cap R) and the above formulas for the image of a set subtraction that for any function f : X \to Y and any sets L and R,

Formulas for f(L) =

It follows from the above formulas for the image of a set subtraction that for any function

f : X \to Y and any set L,

This is more easily seen as being a consequence of the fact that for any

y \in Y, f ^{-1} (y) \cap L = \varnothing if and only if y \not\in f(L).

Formulas for f(L⋂R) =

It follows from the above formulas for the image of a set that for any function

f : X \to Y and any sets L and R, where moreover, for any y \in Y, L \cap f ^{-1} (y) \subseteq L \setminus R~ if and only if ~L \cap R \cap f ^{-1} (y) = \varnothing~ if and only if ~R \cap f ^{-1} (y) \subseteq R \setminus L~ if and only if ~y \not\in f(L \cap R). The sets U and V mentioned above could, in particular, be any of the sets f(L \cup R), \operatorname{Im} f, or Y, for example.

(Pre)Images of set operations on (pre)images

Let

L and R be arbitrary sets, f : X \to Y be any map, and let A \subseteq X and C \subseteq Y.

Image of preimage	Preimage of image	Additional assumptions on sets
f\left(f ^{-1} (L) \cap R\right) = L \cap f(R)	f ^{-1} (f(L) \cap R) ~\supseteq~ L \cap f ^{-1} (R)	None
f\left(f ^{-1} (L) \cup R\right) ~ = ~ (L \cap \operatorname{Im} f) \cup f(R) ~\subseteq~ L \cup f(R)	f ^{-1} (f(A) \cup R) ~\supseteq~ A \cup f ^{-1} (R) ^[12] Equality holds if any of the following are true: f(A) \subseteq R. A \subseteq f ^{-1} (R).	A \subseteq X

(Pre)Images of operations on images

Since

f(L) \setminus f(L \setminus R) ~ = ~ \left\{y \in f(L \cap R) ~:~ L \cap f ^{-1} (y) \subseteq R\right\},

Since

f(X) \setminus f(L \setminus R) ~ = ~ \left\{y \in f(X) ~:~ L \cap f ^{-1} (y) \subseteq R\right\},

Using

L : = X, this becomes ~f(X) \setminus f(X \setminus R) ~ = ~ \left\{y \in f(R) ~:~ f ^{-1} (y) \subseteq R\right\}~ andand so

(Pre)Images and Cartesian products Π

Let

\prod Y _{\bull} ~\stackrel{\scriptscriptstyle def }~ \prod_ Y_j and for every k \in J, let $$\backslash pi\_k\; ~:~\; \backslash prod\_\; Y\_j\; ~\backslash to~\; Y\_k$$ denote the canonical projection onto Y _{k.}

Definitions

Given a collection of maps

F _{j} : X \to Y _{j} indexed by j \in J, define the mapwhich is also denoted by F _{\bull} = \left(F _{j\right)} _{j} . This is the unique map satisfying $$\backslash pi\_j\; \backslash circ\; F\_\; =\; F\_j\; \backslash quad\; \backslash text\; j\; \backslash in\; J.$$

Conversely, if given a map $$F\; ~:~\; X\; ~\backslash to~\; \backslash prod\_\; Y\_j$$ then

F = \left(\pi _{j} \circ F\right) _{j} . Explicitly, what this means is that if $$F\_k\; ~\backslash stackrel~\; \backslash pi\_k\; \backslash circ\; F\; ~:~\; X\; ~\backslash to~\; Y\_k$$ is defined for every k \in J, then F the unique map satisfying: \pi _{j} \circ F = F _{j} for all j \in J; or said more briefly, F = \left(F _{j\right)} _{j} .

The map

F _{\bull} = \left(F _{j\right)} _{j} ~:~ X ~\to~ \prod _{j} Y _{j} should not be confused with the Cartesian product \prod _{j} F _{j} of these maps, which is by definition is the map with domain \prod _{j} X = X ^{J} rather than X.

Preimage and images of a Cartesian product

Suppose

F _{\bull} = \left(F _{j\right)} _{j} ~:~ X ~\to~ \prod _{j} Y _{j.}

If

A ~\subseteq~ X then$$F\_(A)\; ~~\backslash ;\backslash color\backslash color\backslash ;~~\; \backslash prod\_\; F\_j(A).$$

If

B ~\subseteq~ \prod _{j} Y _{j} then $$F\_^(B)\; ~~\backslash ;\backslash color\backslash color\backslash ;~~\; \backslash bigcap\_\; F\_j^\backslash left(\backslash pi\_j(B)\backslash right)$$ where equality will hold if B = \prod _{j} \pi _{j(B),} in which case $F\_^(B)\; =\; \backslash displaystyle\backslash bigcap\_\; F\_j^\backslash left(\backslash pi\_j(B)\backslash right)$ and

For equality to hold, it suffices for there to exist a family

\left(B _{j\right)} _{j} of subsets B _{j} \subseteq Y _{j} such that B = \prod _{j} B _{j,} in which case: and \pi _{j(B)} = B _{j} for all j \in J.

(Pre)Image of a single set

Image	Preimage	Additional assumptions
\begin{alignat}{ 4 } f(L) & = f(L \cap \operatorname{domain} f) \\ & = f(L \cap X) \\ & = Y ~~~~ \setminus \left\{ y \in Y ~~~~ : f ^{-1} (y) \subseteq X \setminus L \right\} \\ & = \operatorname{Im} f \setminus \left\{ y \in \operatorname{Im} f : f ^{-1} (y) \subseteq X \setminus L \right\} \\ \end{alignat}	\begin{alignat}{ 4 } f ^{-1} (L) & = f ^{-1} (L \cap \operatorname{Im} f) \\ & = f ^{-1} (L \cap Y) \end{alignat}	None
f(X) = \operatorname{Im} f \subseteq Y	\begin{alignat}{ 4 } f ^{-1} (Y) & = X \\ f ^{-1} (\operatorname{Im} f) & = X \end{alignat}	None
\begin{alignat}{ 4 } f(L) & = f(L \cap R ~&&\cup~ &&(&&L \setminus R)) \\ & = f(L \cap R) ~&&\cup~ f&&(&&L \setminus R) \end{alignat}	\begin{alignat}{ 4 } f ^{-1} (L) & = f ^{-1} (L \cap R &&\cup &&( &&L &&\setminus &&R)) \\ & = f ^{-1} (L \cap R) &&\cup f ^{-1} &&( &&L &&\setminus &&R) \\ & = f ^{-1} (L \cap R) &&\cup f ^{-1} &&( &&L &&\setminus [&&R \cap \operatorname{Im} f]) \\ & = f ^{-1} (L \cap R) &&\cup f ^{-1} &&([&&L \cap \operatorname{Im} f] &&\setminus &&R) \\ & = f ^{-1} (L \cap R) &&\cup f ^{-1} &&([&&L \cap \operatorname{Im} f] &&\setminus [&&R \cap \operatorname{Im} f]) \end{alignat}	None
\operatorname{Im} f = f(X) ~ = ~ f(L) \cup f(X \setminus L)	\begin{alignat}{ 4 } X & = f ^{-1} (L) \cup f ^{-1} (Y &&\setminus L) \\ & = f ^{-1} (L) \cup f ^{-1} (\operatorname{Im} f &&\setminus L) \end{alignat}	None
f \ vert _{L(R)} = f(L \cap R)	\left(f \ vert ^{-1} _{L\right)} (R) = L \cap f ^{-1} (R)	None
(g \circ f)(L) ~ = ~ g(f(L))	(g \circ f) ^{-1} (L) ~ = ~ f ^{-1} \left(g ^{-1} (L)\right)	None (f and g are arbitrary functions).
f\left(f ^{-1} (L)\right) = L \cap \operatorname{Im} f	f ^{-1} (f(L)) ~\supseteq~ L \cap f ^{-1} (\operatorname{Im} f) = L \cap f ^{-1} (Y)	None
f\left(f ^{-1} (Y)\right) = f\left(f ^{-1} (\operatorname{Im} f)\right) = f(X)	f ^{-1} (f(X)) = f ^{-1} (\operatorname{Im} f) = X	None
f\left(f ^{-1} (f(L))\right) = f(L)	f ^{-1} \left(f\left(f ^{-1} (L)\right)\right) = f ^{-1} (L)	None

Containments ⊆ and intersections ⋂ of images and preimages

Equivalences and implications of images and preimages

Image	Preimage	Additional assumptions on sets
f(L) \subseteq \operatorname{Im} f \subseteq Y	f ^{-1} (L) = X if and only if \operatorname{Im} f \subseteq L	None
f(L) = \varnothing if and only if L \cap \operatorname{domain} f = \varnothing	f ^{-1} (L) = \varnothing if and only if L \cap \operatorname{Im} f = \varnothing	None
f(A) = \varnothing if and only if A = \varnothing	f ^{-1} (C) = \varnothing if and only if C \subseteq Y \setminus \operatorname{Im} f	A \subseteq X and C \subseteq Y
L \subseteq R implies f(L) \subseteq f(R)	L \subseteq R implies f ^{-1} (L) \subseteq f ^{-1} (R)	None
The following are equivalent: f(L) \subseteq f(R) f(L \cup R) = f(R) L \cap \operatorname{domain} f ~\subseteq~ f ^{-1} (f(R))	The following are equivalent: f ^{-1} (L) \subseteq f ^{-1} (R) f ^{-1} (L \cup R) = f ^{-1} (R) L \cap \operatorname{Im} f \subseteq R If C ~\subseteq~ \operatorname{Im} f then f ^{-1} (C) ~\subseteq~ f ^{-1} (R) if and only if C ~\subseteq~ R.	C \subseteq \operatorname{Im} f
The following are equivalent when C \subseteq Y: C \subseteq f(R) f(B) = C for some B \subseteq R	The following are equivalent: L \subseteq f ^{-1} (R) f(L) \subseteq R and L \subseteq \operatorname{domain} f The following are equivalent when A \subseteq X: A \subseteq f ^{-1} (R) f(A) \subseteq R	A \subseteq X and C \subseteq Y
The following are equivalent: f(A) ~\supseteq~ f(X \setminus A) f(A) = \operatorname{Im} f	The following are equivalent: f ^{-1} (C) ~\supseteq~ f ^{-1} (Y \setminus C) f ^{-1} (C) = X	A \subseteq X and C \subseteq Y
f\left(f ^{-1} (L)\right) \subseteq L Equality holds if the following is true: L \subseteq \operatorname{Im} f. ^[13] ^[14] Equality holds if any of the following are true: L \subseteq Y and f : X \to Y is surjective.	f ^{-1} (f(A)) \supseteq A Equality holds if the following is true: A is f -saturated. Equality holds if any of the following are true: f is injective.	A \subseteq X

Intersection of a set and a (pre)image

The following statements are equivalent:

1. \varnothing = f(L) \cap R
2. \varnothing = L \cap f ^{-1} (R)
3. \varnothing = f ^{-1} (f(L)) \cap f ^{-1} (R)
4. \varnothing = f ^{-1} (f(L) \cap R)

Thus for any

t, $$t\; \backslash not\backslash in\; f(L)\; \backslash quad\; \backslash text\; \backslash quad\; L\; \backslash cap\; f^(t)\; =\; \backslash varnothing.$$

Sequences and collections of families of sets

Definitions

A or simply a is a set whose elements are sets. A is a family of subsets of

X.

The of a set

X is the set of all subsets of X : $$\backslash wp(X)\; ~\backslash colon=~\; \backslash .$$

Notation for sequences of sets

Throughout,

S and T will be arbitrary sets and S _{\bull} 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 $$S\_\; =\; \backslash left(S\_i\backslash right)\_^\; \backslash qquad\; \backslash text\; \backslash qquad\; S\_\; =\; \backslash left(S\_i\backslash right)\_$$where \N denotes the natural numbers. A notation S _{\bull} = \left(S _{i\right)} _{i} indicates that S _{\bull} is a net directed by (I, \leq), which (by definition) is a sequence if the set I, which is called the net's indexing set, is the natural numbers (that is, if I = \N ) and \leq is the natural order on \N.

Disjoint and monotone sequences of sets

If

S _{i} \cap S _{j} = \varnothing for all distinct indices i ≠ j then S _{\bull} is called a or simply a . A sequence or net S _{\bull} of set is called or if (resp. or) if for all indices i \leq j, S _{i} \subseteq S _{j} (resp. S _{i} \supseteq S _{j} ). A sequence or net S _{\bull} of set is called (resp.) if it is non-decreasing (resp. is non-increasing) and also S _{i} ≠ S _{j} for all indices i and j. It is called if it is non-decreasing or non-increasing and it is called if it is strictly increasing or strictly decreasing.

A sequences or net

S _{\bull} is said to denoted by S _{\bull} \uparrow S or S _{\bull} \nearrow S, if S _{\bull} is increasing and the union of all S _{i} is S; that is, if $$\backslash bigcup\_\; S\_n\; =\; S\; \backslash qquad\; \backslash text\; \backslash qquad\; S\_i\; \backslash subseteq\; S\_j\; \backslash quad\; \backslash text\; i\; \backslash leq\; j.$$It is said to denoted by S _{\bull} \downarrow S or S _{\bull} \searrow S, if S _{\bull} is increasing and the intersection of all S _{i} is S that is, if $$\backslash bigcap\_\; S\_n\; =\; S\; \backslash qquad\; \backslash text\; \backslash qquad\; S\_i\; \backslash supseteq\; S\_j\; \backslash quad\; \backslash text\; i\; \backslash leq\; j.$$

Definitions of elementwise operations on families

If

l{L} and l{R} are families of sets and if S is any set then define: $$\backslash mathcal\; \backslash ;(\backslash cup)\backslash ;\; \backslash mathcal\; ~\backslash colon=~\; \backslash$$$$\backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; \backslash mathcal\; ~\backslash colon=~\; \backslash$$$$\backslash mathcal\; \backslash ;(\backslash setminus)\backslash ;\; \backslash mathcal\; ~\backslash colon=~\; \backslash$$$$\backslash mathcal\; \backslash ;(\backslash triangle)\backslash ;\; \backslash mathcal\; ~\backslash colon=~\; \backslash$$$$\backslash mathcal\backslash big\backslash vert\_S\; ~\backslash colon=~\; \backslash \; =\; \backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; \backslash$$which are respectively called , , () , , and the / The regular union, intersection, and set difference are all defined as usual and are denoted with their usual notation: l{L} \cup l{R}, l{L} \cap l{R}, l{L} \triangle l{R}, and l{L} \setminus l{R}, respectively. These elementwise operations on families of sets play an important role in, among other subjects, the theory of filters and prefilters on sets.

The of a family

l{L} \subseteq \wp(X) is the family: $$\backslash mathcal^\; ~\backslash colon=~\; \backslash bigcup\_\; \backslash \; ~=~\; \backslash$$ and the is the family:$$\backslash mathcal^\; ~\backslash colon=~\; \backslash bigcup\_\; \backslash wp(L)\; ~=~\; \backslash .$$

Definitions of categories of families of sets

The following table lists some well-known categories of families of sets having applications in general topology and measure theory.

A family

l{L} is called,, or in X if l{L} \subseteq \wp(X) and l{L} = l{L} ^{\uparrow} . A family l{L} is called if l{L} = l{L} ^{\downarrow} .

A family

l{L} is said to be:

• (resp.) if whenever

L, R \in l{L} then L \cap R \in l{L} (respectively, L \cup R \in l{L} ).

• (resp.) if whenever

L _{1,} L _{2,} L _{3,} \ldots are elements of l{L} then so is their intersections c ap ^{inf ty} _{i =1} L _{i} : = L _{1} \cap L _{2} \cap L _{3} \cap … (resp. so is their union c up ^{inf ty} _{i =1} L _{i} : = L _{1} \cup L _{2} \cup L _{3} \cup … ).

• (or) if whenever

L \in l{L} then X \setminus L \in l{L}.

A family

l{L} of sets is called a/an:

• if

l{L} ≠ \varnothing and l{L} is closed under finite-intersections.

• • Every non-empty family

l{L} is contained in a unique smallest (with respect to \subseteq ) −system that is denoted by \pi( l{L}) and called

• and is said to have if

l{L} ≠ \varnothing and \varnothing \not\in \pi( l{L}).

• if

l{L} ≠ \varnothing is a family of subsets of X that is a −system, is upward closed in X, and is also, which by definition means that it does not contain the empty set as an element.

• or if it is a non-empty family of subsets of some set

X whose upward closure in X is a filter on X.

• is a non-empty family of subsets of

X that contains the empty set, forms a −system, and is also closed under complementation with respect to X.

• is an algebra on

X that is closed under countable unions (or equivalently, closed under countable intersections).

Sequences of sets often arise in measure theory.

Algebra of sets

See also: Algebra of sets.

\Phi of subsets of a set X is said to be if \varnothing \in \Phi and for all L, R \in \Phi, all three of the sets X \setminus R, L \cap R, and L \cup R are elements of \Phi. ^[15] The article on this topic lists set identities and other relationships these three operations.

Every algebra of sets is also a ring of sets^[15] and a π-system.

Algebra generated by a family of sets

Given any family

l{S} of subsets of X, there is a unique smallest^[16] algebra of sets in X containing l{S}. ^[15] It is called and it will be denote it by \Phi _{l{S} }. This algebra can be constructed as follows:^[15]

1. If
   l{S} = \varnothing then \Phi _{l{S} } = \ and we are done. Alternatively, if l{S} is empty then l{S} may be replaced with \{\varnothing\}, \{X\}, or \{\varnothing, X\} and continue with the construction.
2. Let l{S} _{0} be the family of all sets in l{S} together with their complements (taken in X ).
3. Let l{S} _{1} be the family of all possible finite intersections of sets in l{S} _{0.} ^[17]
4. Then the algebra generated by l{S} is the set \Phi _{l{S} } consisting of all possible finite unions of sets in l{S} _{1.}

Elementwise operations on families

Let

l{L}, l{M}, and l{R} be families of sets over X. On the left hand sides of the following identities, l{L} is the eft most family, l{M} is in the iddle, and l{R} is the ight most set.

Commutativity

$$\backslash mathcal\; \backslash ;(\backslash cup)\backslash ;\; \backslash mathcal\; =\; \backslash mathcal\; \backslash ;(\backslash cup)\backslash ;\; \backslash mathcal$$$$\backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; \backslash mathcal\; =\; \backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; \backslash mathcal$$

Associativity

$$[\backslash mathcal\{L\}\; \backslash ;(\backslash cup)\backslash ;\; \backslash mathcal\{M\}]\; \backslash ;(\backslash cup)\backslash ;\; \backslash mathcal\; =\; \backslash mathcal\; \backslash ;(\backslash cup)\backslash ;\; [\backslash mathcal\{M\}\; \backslash ;(\backslash cup)\backslash ;\; \backslash mathcal\{R\}]$$$$[\backslash mathcal\{L\}\; \backslash ;(\backslash cap)\backslash ;\; \backslash mathcal\{M\}]\; \backslash ;(\backslash cap)\backslash ;\; \backslash mathcal\; =\; \backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; [\backslash mathcal\{M\}\; \backslash ;(\backslash cap)\backslash ;\; \backslash mathcal\{R\}]$$

Identity:$$\backslash mathcal\; \backslash ;(\backslash cup)\backslash ;\; \backslash \; =\; \backslash mathcal$$$$\backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; \backslash \; =\; \backslash mathcal$$$$\backslash mathcal\; \backslash ;(\backslash setminus)\backslash ;\; \backslash \; =\; \backslash mathcal$$

Domination:$$\backslash mathcal\; \backslash ;(\backslash cup)\backslash ;\; \backslash \; =\; \backslash \; ~~~~\backslash text\; \backslash mathcal\; \backslash neq\; \backslash varnothing$$$$\backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; \backslash \; =\; \backslash \; ~~~~\backslash text\; \backslash mathcal\; \backslash neq\; \backslash varnothing$$$$\backslash mathcal\; \backslash ;(\backslash cup)\backslash ;\; \backslash varnothing\; =\; \backslash varnothing$$$$\backslash mathcal\; \backslash ;(\backslash cap)\backslash ;\; \backslash varnothing\; =\; \backslash varnothing$$$$\backslash mathcal\; \backslash ;(\backslash setminus)\backslash ;\; \backslash varnothing\; =\; \backslash varnothing$$$$\backslash varnothing\; \backslash ;(\backslash setminus)\backslash ;\; \backslash mathcal\; =\; \backslash varnothing$$

Power set

$$\backslash wp(L\; \backslash cap\; R)\; ~=~\; \backslash wp(L)\; \backslash cap\; \backslash wp(R)$$$$\backslash wp(L\; \backslash cup\; R)\; ~=~\; \backslash wp(L)\; \backslash \; (\backslash cup)\backslash \; \backslash wp(R)\; ~\backslash supseteq~\; \backslash wp(L)\; \backslash cup\; \backslash wp(R).$$

If

L and R are subsets of a vector space X and if s is a scalar then$$\backslash wp(s\; L)\; ~=~\; s\; \backslash wp(L)$$$$\backslash wp(L\; +\; R)\; ~\backslash supseteq~\; \backslash wp(L)\; +\; \backslash wp(R).$$

Sequences of sets

Suppose that

L is any set such that L \supseteq R _{i} for every index i. If R _{\bull} decreases to R then L \setminus R _{\bull} : = \left(L \setminus R _{i\right)} _{i} increases to L \setminus R whereas if instead R _{\bull} increases to R then L \setminus R _{\bull} decreases to L \setminus R.

If

L and R are arbitrary sets and if L _{\bull} = \left(L _{i\right)} _{i} increases (resp. decreases) to L then \left(L _{i} \setminus R\right) _{i} increase (resp. decreases) to L \setminus R.

Partitions

Suppose that

S _{\bull} = \left(S _{i\right)} ^{inf ty} ^{i =1} is any sequence of sets, that S \subseteq c up _{i} S _{i} is any subset, and for every index i, let D _{i} = \left(S _{i} \cap S\right) \setminus c up ^{i} _{m =1} \left(S _{m} \cap S\right). Then S = c up _{i} D _{i} and D _{\bull} : = \left(D _{i\right)} ^{inf ty} ^{i =1} is a sequence of pairwise disjoint sets.

Suppose that

S _{\bull} = \left(S _{i\right)} ^{inf ty} ^{i =1} is non-decreasing, let S _{0} = \varnothing, and let D _{i} = S _{i} \setminus S _{i-1} for every i = 1 , 2 , \ldots. Then c up _{i} S _{i} = c up _{i} D _{i} and D _{\bull} = \left(D _{i\right)} ^{inf ty} ^{i =1} is a sequence of pairwise disjoint sets.

Notes

Notes

Proofs

References

• Book: Artin, Michael. Michael Artin. Algebra. 1991. Prentice Hall. 81-203-0871-9.
• Book: Blyth, T.S.. Lattices and Ordered Algebraic Structures. Springer. 2005. 1-85233-905-5. .
• Bylinski. Czeslaw. 2004. Some Basic Properties of Sets. Journal of Formalized Mathematics. 1. 5 October 2021.
• Courant, Richard, Herbert Robbins, Ian Stewart, What is mathematics?: An Elementary Approach to Ideas and Methods, Oxford University Press US, 1996. . "SUPPLEMENT TO CHAPTER II THE ALGEBRA OF SETS".
  • • • • • Book: Halmos, Paul R.. Paul Halmos. Naive set theory. registration. The University Series in Undergraduate Mathematics. van Nostrand Company. 1960. 9780442030643 . 0087.04403.
  • Book: Kelley. John L.. General Topology. 2. Graduate Texts in Mathematics. 27. 1985. Birkhäuser. 978-0-387-90125-1.
  • Book: Monk, James Donald. Introduction to Set Theory. McGraw-Hill. New York. 1969. International series in pure and applied mathematics. 978-0-07-042715-0. 1102.
    • Padlewska. Beata. 1990. Families of Sets. Journal of Formalized Mathematics. 1. 1. 5 October 2021.
    • Stoll, Robert R.;, Mineola, N.Y.: Dover Publications (1979) . "The Algebra of Sets", pp 16 - 23.
• Trybulec. Zinaida. 2002. Properties of subsets. Journal of Formalized Mathematics. 1. 1. 5 October 2021.

External links

• Operations on Sets at ProvenMath

Notes and References

1. For example, the expression (M \setminus R) \setminus A uses two of the same symbols (M and R ) that appear in the identity $$(L\; \backslash ,\backslash setminus\backslash ,\; M)\; \backslash ,\backslash setminus\backslash ,\; R\; ~=~\; (L\; \backslash ,\backslash setminus\backslash ,\; R)\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash setminus\backslash ,\; R)$$but they refer to different sets in each expression. To apply this identity to (M \setminus R) \setminus A, substitute Leftset : = M, Middleset : = R, and Rightset : = A (since these are the left, middle, and right sets in (M \setminus R) \setminus A ) to obtain: For a second example, this time applying the identity to ((M \cap R \setminus L) \setminus (A \triangle L)) \setminus L, is now given. The identity $(L\; \backslash setminus\; M)\; \backslash setminus\; R\; =\; (L\; \backslash setminus\; R)\; \backslash setminus\; (M\; \backslash setminus\; R)$ can be applied to ((M \cap R \setminus L) \setminus (A \triangle L)) \setminus L by reading L, M, and R as Left , Middle , and Right and then substituting Left = (M \cap R \setminus L), Middle = (A \triangle L), and Right = L to obtain:
2. Web site: Taylor. Courtney. March 31, 2019. What Is Symmetric Difference in Math?. 2020-09-05. ThoughtCo. en.
3. Web site: Weisstein. Eric W.. Symmetric Difference. 2020-09-05. mathworld.wolfram.com. en.
4. To deduce from, it must still be shown that { style c up\limits _{\stackrel{i} {j \in I}}} \left(L _{i} \cup R _{j\right)} ~ = ~ { style c up\limits _{i} } \left(L_i \cup R_i\right) so is not a completely immediate consequence of . (Compare this to the commentary about).
5. So for instance, it's even possible that L \cap (X \cup Y) = \varnothing, or that L \cap X ≠ \varnothing L \cap Y ≠ \varnothing (which happens, for instance, if X = Y ), etc.
6. The conclusion X \setminus f ^{-1} (R) = f ^{-1} (Y \setminus R) can also be written as: f ^{-1} (R) ^{\complement} ~ = ~ f ^{-1} \left(R ^{\complement\right).}
7. Whether or not it is even feasible for the function f to be constant and the sets L \triangle R and R to be non-empty and disjoint is irrelevant for reaching the correct conclusion about whether to use \subseteq or \supseteq.
8. See
9. Note that this condition depends entirely on R and on L.
10. Let P : = \left\{y \in Y : L \cap f ^{-1} (y) \subseteq R\right\} and let (\star) denote the set equality f(L \setminus R) = Y \setminus P, which will now be proven. If y \in Y \setminus P then L \cap f ^{-1} (y) \not\subseteq R so there exists some x \in L \cap f ^{-1} (y) \setminus R; now f ^{-1} (y) \subseteq X implies x \in L \cap X \setminus R so that y = f(x) \in f(L \cap X \setminus R) = f(L \setminus R). To prove the reverse inclusion f(L \setminus R) \subseteq Y \setminus P, let y \in f(L \setminus R) so that there exists some x \in X \cap L \setminus R such that y = f(x). Then x \in L \cap f ^{-1} (y) \setminus R so that L \cap f ^{-1} (y) \not\subseteq R and thus y \not\in P, which proves that y \in Y \setminus P, as desired. \blacksquare Defining Q : = f(L) \cap P = \left\{ y \in f(L) : L \cap f ^{-1} (y) \subseteq R \right\}, the identity f(L \setminus R) = f(L) \setminus Q follows from (\star) and the inclusions f(L \setminus R) \subseteq f(L) \subseteq Y. \blacksquare
11. Let f _{R} : = \left\{ y \in f(L) : L \cap f ^{-1} (y) \subseteq R \right\} where because f _{R} \subseteq f(R \cap L), f _{R} is also equal to f _{R} = \left\{ y \in f(R \cap L) : L \cap f ^{-1} (y) \subseteq R \right\}. As proved above, f(L \setminus R) = f(L) \setminus f _{R} so that f(L) \setminus f(R) = f(L \setminus R) if and only if f(L) \setminus f(R) = f(L) \setminus f _{R.} Since f(L) \setminus f(R) = f(L) \setminus (f(L) \cap f(R)), this happens if and only if f(L) \setminus (f(L) \cap f(R)) = f(L) \setminus f _{R.} Because f(L) \cap f(R) and f _{R} are both subsets of f(L), the condition on the right hand side happens if and only if f(L) \cap f(R) = f _{R.} Because f _{R} \subseteq f(R \cap L) \subseteq f(L) \cap f(R), the equality f(L) \cap f(R) = f _{R} holds if and only if f(L) \cap f(R) \subseteq f _{R.} \blacksquare If f(R) \subseteq f(L) (such as when L = X or R \subseteq L ) then f(L) \cap f(R) \subseteq f _{R} if and only if f(R) \subseteq f _{R.} In particular, taking L = X proves: f(X \setminus R) = f(X) \setminus f(R) if and only if f(R) \subseteq \left\{ y \in f(R \cap X) : f ^{-1} (y) \subseteq R \right\}, where f(R \cap X) = f(R). \blacksquare
12. Lee p.388 of Lee, John M. (2010). Introduction to Topological Manifolds, 2nd Ed.
13. Lee
14. Lee
15. Web site: Algebra of sets. Encyclopediaofmath.org. 16 August 2013. 8 November 2020.
16. Here "smallest" means relative to subset containment. So if \Phi is any algebra of sets containing l{S}, then \Phi _{l{S} } \subseteq \Phi.
17. Since l{S} ≠ \varnothing, there is some S \in l{S} _{0} such that its complement also belongs to l{S} _{0.} The intersection of these two sets implies that \varnothing \in l{S} _{1.} The union of these two sets is equal to X, which implies that X \in \Phi _{l{S} }.