List of Set Identities and Relations
Browse the List of Set Identities and Relations below. View Videos or join the discussion on this topic. Add List of Set Identities and Relations to your PopFlock.com topic list for future reference or share this resource on social media.
List of Set Identities and Relations

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 (${\displaystyle \cup }$) and intersection (${\displaystyle \cap }$) satisfy many identities. Several of these identities or "laws" have well established names.

## Notation

Throughout this article, capital letters such as ${\displaystyle A,B,C,}$ and ${\displaystyle X}$ will denote sets and ${\displaystyle \wp (X)}$ will denote the power set of ${\displaystyle X.}$ If it is needed then unless indicated otherwise, it should be assumed that ${\displaystyle X}$ denotes the universe set, which means that all sets that are used in the formula are subsets of ${\displaystyle X.}$ In particular, the complement of a set ${\displaystyle A}$ will be denoted by ${\displaystyle A^{C}}$ where unless indicated otherwise, it should be assumed that ${\displaystyle A^{C}}$ denotes the complement of ${\displaystyle A}$ in (the universe) ${\displaystyle X.}$

For sets ${\displaystyle A}$ and ${\displaystyle B,}$ define:

{\displaystyle {\begin{alignedat}{4}A\cup B&&~=~\{~x~:~x\in A\;&&{\text{ or }}\;\,&&\;x\in B~\}\\A\cap B&&~=~\{~x~:~x\in A\;&&{\text{ and }}&&\;x\in B~\}\\A\setminus B&&~=~\{~x~:~x\in A\;&&{\text{ and }}&&\;x\notin B~\}.\\\end{alignedat}}}

The symmetric difference of ${\displaystyle A}$ and ${\displaystyle B}$ is:[1][2]

{\displaystyle {\begin{alignedat}{4}A\;\triangle \;B~&=~(A~\setminus ~&&B)~\cup ~&&(B~\setminus ~&&A)\\~&=~(A~\cup ~&&B)~\setminus ~&&(A~\cap ~&&B)\end{alignedat}}}

and the complement of a set ${\displaystyle B}$ is:

${\displaystyle B^{C}=X\setminus B}$

where ${\displaystyle B\subseteq X.}$ This definition may depend on context. For instance, had ${\displaystyle B}$ been declared as a subset of ${\displaystyle Y,}$ with the sets ${\displaystyle Y}$ and ${\displaystyle X}$ not necessarily related to each other in any way, then ${\displaystyle B^{C}}$ would likely mean ${\displaystyle Y\setminus B}$ instead of ${\displaystyle X\setminus B.}$

## Algebra of sets

A family ${\displaystyle \Phi }$ of subsets of a set ${\displaystyle X}$ is said to be an algebra of sets if ${\displaystyle \varnothing \in \Phi }$ and for all ${\displaystyle A,B\in \Phi ,}$ all three of the sets ${\displaystyle X\setminus A,}$ ${\displaystyle A\cap B,}$ and ${\displaystyle A\cup B}$ are elements of ${\displaystyle \Phi .}$[3] The article on this topic lists set identities and other relationships these three operations.

Every algebra of sets is also a ring of sets[3] and a ?-system.

Algebra generated by a family of sets

Given any family ${\displaystyle {\mathcal {S}}}$ of subsets of ${\displaystyle X,}$ there is a unique smallest[note 1] algebra of sets in ${\displaystyle X}$ containing ${\displaystyle {\mathcal {S}}.}$[3] It is called the algebra generated by ${\displaystyle {\mathcal {S}}}$ and we'll denote it by ${\displaystyle \Phi _{\mathcal {S}}.}$ This algebra can be constructed as follows:[3]

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

### Basic set relationships

Let ${\displaystyle A,B,}$ and ${\displaystyle C}$ be subsets of ${\displaystyle X.}$

Commutativity:[4]
• ${\displaystyle A\cup B=B\cup A}$
• ${\displaystyle A\cap B=B\cap A}$
• ${\displaystyle A\,\triangle B=B\,\triangle A}$
Associativity:[4]
• ${\displaystyle (A\cup B)\cup C=A\cup (B\cup C)}$
• ${\displaystyle (A\cap B)\cap C=A\cap (B\cap C)}$
• ${\displaystyle (A\,\triangle B)\,\triangle C=A\,\triangle (B\,\triangle C)}$
Distributivity:[4]
• ${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)}$
• ${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$
• ${\displaystyle A\cap (B\,\triangle C)=(A\cap B)\,\triangle (A\cap C)}$
• ${\displaystyle A\times (B\cap C)=(A\times B)\cap (A\times C)}$
• ${\displaystyle A\times (B\cup C)=(A\times B)\cup (A\times C)}$
• ${\displaystyle A\times (B\,\setminus C)=(A\times B)\,\setminus (A\times C)}$
Identity:[4]
• ${\displaystyle A\cap X=A}$
• ${\displaystyle A\cup \varnothing =A}$
• ${\displaystyle A\setminus \varnothing =A}$
• ${\displaystyle A\,\triangle \varnothing =A}$
Complement:[4]
• ${\displaystyle A\cup A^{C}=X}$
• ${\displaystyle A\cap A^{C}=\varnothing }$
• ${\displaystyle A\,\triangle A^{C}=X}$
Idempotent:[4]
• ${\displaystyle A\cup A=A}$
• ${\displaystyle A\cap A=A}$
Domination:[4]
• ${\displaystyle A\cup X=X}$
• ${\displaystyle A\cap \varnothing =\varnothing }$
• ${\displaystyle A\times \varnothing =\varnothing }$
Absorption laws:
• ${\displaystyle A\cup (A\cap B)=A}$
• ${\displaystyle A\cap (A\cup B)=A}$

#### Complements

{\displaystyle {\begin{alignedat}{2}A\setminus B&=A\setminus (A\cap B)\\\end{alignedat}}}

Intersection can be expressed in terms of set difference:

{\displaystyle {\begin{alignedat}{2}A\cap B&=A\setminus (A\setminus B)\\&=B\setminus (B\setminus A)\end{alignedat}}}

Set subtraction and the empty set:[4]

${\displaystyle A\setminus \varnothing =A}$
{\displaystyle {\begin{alignedat}{2}\varnothing &=A&&\setminus A\\&=\varnothing &&\setminus A\\&=A&&\setminus X~~~~{\text{ where }}A\subseteq X\\\end{alignedat}}}
Complements in a universe set

Assume that ${\displaystyle A,B,C\subseteq X.}$

${\displaystyle A^{C}=X\setminus A}$ (by definition of this notation)
De Morgan's laws:
• ${\displaystyle (A\cup B)^{C}=A^{C}\cap B^{C}}$
• ${\displaystyle (A\cap B)^{C}=A^{C}\cup B^{C}}$
Double complement or involution law:
• ${\displaystyle {(A^{C})}^{C}=A}$
Complement laws for the universe set and the empty set:
• ${\displaystyle \varnothing ^{C}=X}$
• ${\displaystyle X^{C}=\varnothing }$
Uniqueness of complements:
• If ${\displaystyle A\cup B=X}$ and ${\displaystyle A\cap B=\varnothing }$ then ${\displaystyle B=A^{C}}$
Complements and set subtraction
• ${\displaystyle B\setminus A=A^{C}\cap B}$
• ${\displaystyle (B\setminus A)^{C}=A\cup B^{C}}$
• ${\displaystyle B^{C}\setminus A^{C}=A\setminus B}$

### Subset inclusion

The following are equivalent:[4]

1. ${\displaystyle A\subseteq B}$
2. ${\displaystyle A\cap B=A}$
3. ${\displaystyle A\cup B=B}$
4. ${\displaystyle A\setminus B=\varnothing }$
5. ${\displaystyle B^{C}\subseteq A^{C}}$
Inclusion is a partial order

In words, the following three properties says that the binary relation of inclusion ${\displaystyle \subseteq }$ is a partial order.[4]

Reflexivity:
• ${\displaystyle A\subseteq A}$
Antisymmetry:
• ${\displaystyle A\subseteq B}$ and ${\displaystyle B\subseteq A}$ if and only if ${\displaystyle A=B}$
Transitivity:
• If ${\displaystyle A\subseteq B}$ and ${\displaystyle B\subseteq C,}$ then ${\displaystyle A\subseteq C}$
Lattice properties

The following proposition says that for any set ${\displaystyle S,}$ the power set of ${\displaystyle 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:
• ${\displaystyle \varnothing \subseteq A\subseteq X}$
Existence of joins:[4]
• ${\displaystyle A\subseteq A\cup B}$
• If ${\displaystyle A\subseteq C}$ and ${\displaystyle B\subseteq C}$ then ${\displaystyle A\cup B\subseteq C}$
Existence of meets:[4]
• ${\displaystyle A\cap B\subseteq A}$
• If ${\displaystyle C\subseteq A}$ and ${\displaystyle C\subseteq B}$ then ${\displaystyle C\subseteq A\cap B}$
Other properties
• If ${\displaystyle A\subseteq X}$ and ${\displaystyle B\subseteq Y}$ then ${\displaystyle A\times B\subseteq X\times Y}$[4]
• If ${\displaystyle A\subseteq B}$ then ${\displaystyle C\setminus B\subseteq C\setminus A}$

## Multiple set operations

### Expressing basic set operations

{\displaystyle {\begin{alignedat}{5}A\cap B&=A&&\,\,\setminus \,&&(A&&\,\,\setminus &&B)\\&=B&&\,\,\setminus \,&&(B&&\,\,\setminus &&A)\\&=A&&\,\,\setminus \,&&(A&&\,\triangle \,&&B)\\&=A&&\,\triangle \,&&(A&&\,\,\setminus &&B)\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{5}A\cup B&=(&&A\,\triangle \,B)&&\,\,\cup &&&&A&&&&\\&=(&&A\,\triangle \,B)&&\,\triangle \,&&(&&A&&\cap \,&&B)\\&=(&&B\,\setminus \,A)&&\,\,\cup &&&&A&&&&~~~~~{\text{(Disjoint union)}}\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{5}A\setminus B&=&&A&&\,\,\setminus &&(A&&\,\,\cap &&B)\\&=&&A&&\,\,\cap &&(A&&\,\triangle \,&&B)\\&=&&A&&\,\triangle \,&&(A&&\,\,\cap &&B)\\&=&&B&&\,\triangle \,&&(A&&\,\,\cup &&B)\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{5}A\,\triangle \,B&=&&B\,\triangle \,A&&&&\\&=(&&A\,\cup \,B)&&\,\,\setminus \,(&&A\,\,\cap \,B)\\&=(&&A^{C})&&\,\triangle \,(&&B^{C})\\&=(&&A\,\triangle \,C)&&\,\triangle \,(&&C\,\triangle \,B)\\\end{alignedat}}}

### Identities involving two set operations

In the left hand sides of the following identities, ${\displaystyle L}$ is the L eft most set, ${\displaystyle M}$ is the M iddle set, and ${\displaystyle R}$ is the R ight most set.

Identities involving set subtraction followed by a second set operation
{\displaystyle {\begin{alignedat}{3}L\setminus (M\cup R)&=(L\setminus M)&&\,\cap \,(&&L\setminus R)~~~~{\text{ (De Morgan's law) }}\\&=(L\setminus M)&&\,\,\setminus &&R\\&=(L\setminus R)&&\,\,\setminus &&M\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{2}L\setminus (M\cap R)&=(L\setminus M)\cup (L\setminus R)~~~~{\text{ (De Morgan's law) }}\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{2}L\setminus (M\setminus R)&=(L\setminus M)\cup (L\cap R)\\\end{alignedat}}}
• So if ${\displaystyle L\subseteq M}$ then ${\displaystyle L\setminus (M\setminus R)=L\cap R}$
{\displaystyle {\begin{alignedat}{2}L\setminus (M~\triangle ~R)&=(L\setminus (M\cup R))\cup (L\cap M\cap R)~~~{\text{ (the outermost union is disjoint) }}\\\end{alignedat}}}

{\displaystyle {\begin{alignedat}{2}\left(L\setminus M\right)\cup R&=(L\cup R)\setminus (M\setminus R)\\&=(L\setminus (M\cup R))\cup R~~~~~{\text{ (the outermost union is disjoint) }}\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{2}(L\setminus M)\cap R&=(&&L\cap R)\setminus (M\cap R)~~~{\text{ (distributive law of }}\cap {\text{ over }}\setminus {\text{ )}}\\&=(&&L\cap R)\setminus M\\&=&&L\cap (R\setminus M)\\\end{alignedat}}}[5]
{\displaystyle {\begin{alignedat}{2}(L\setminus M)\setminus R&=&&L\setminus (M\cup R)\\&=(&&L\setminus M)\cap (L\setminus R)\\&=(&&L\setminus R)\setminus M\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{2}(L\setminus M)~\triangle ~R&=(L\setminus (M\cup R))\cup (R\setminus L)\cup (L\cap M\cap R)~~~{\text{ (the three outermost sets are pairwise disjoint) }}\\\end{alignedat}}}
Identities involving a set operation followed by set subtraction
{\displaystyle {\begin{alignedat}{2}(L\cup M)\setminus R&=(L\setminus R)\cup (M\setminus R)\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{2}(L\cap M)\setminus R&=(&&L\setminus R)&&\cap (M\setminus R)\\&=&&L&&\cap (M\setminus R)\\&=&&M&&\cap (L\setminus R)\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{2}(L\,\triangle \,M)\setminus R&=(L\setminus R)~&&\triangle ~(M\setminus R)\\&=(L\cup R)~&&\triangle ~(M\cup R)\\\end{alignedat}}}

{\displaystyle {\begin{alignedat}{3}L\cup (M\setminus R)&=&&&&L&&\cup \;&&(M\setminus (R\cup L))&&~~~{\text{ (the outermost union is disjoint) }}\\&=[&&(&&L\setminus M)&&\cup \;&&(R\cap L)]\cup (M\setminus R)&&~~~{\text{ (the outermost union is disjoint) }}\\&=&&(&&L\setminus (M\cup R))\;&&\;\cup &&(R\cap L)\,\,\cup (M\setminus R)&&~~~{\text{ (the three outermost sets are pairwise disjoint) }}\\\end{alignedat}}}
{\displaystyle {\begin{alignedat}{2}L\cap (M\setminus R)&=(&&L\cap M)&&\setminus (L\cap R)~~~{\text{ (distributive law of }}\cap {\text{ over }}\setminus {\text{ )}}\\&=(&&L\cap M)&&\setminus R\\&=&&M&&\cap (L\setminus R)\\&=(&&L\setminus R)&&\cap (M\setminus R)\\\end{alignedat}}}[5]
If ${\displaystyle L\subseteq M}$ then ${\displaystyle L\setminus R=L\cap (M\setminus R).}$[5]

## Arbitrary families of sets

Let ${\displaystyle \left(A_{i}\right)_{i\in I},}$ ${\displaystyle \left(B_{j}\right)_{j\in J},}$ and ${\displaystyle \left(S_{i,j}\right)_{(i,j)\in I\times J}}$ be families of sets. Whenever the assumption is needed, then all indexing sets, such as ${\displaystyle I}$ and ${\displaystyle J,}$ are assumed to be non-empty.

### Definitions

Arbitrary unions defined
If ${\displaystyle I=\varnothing }$ then ${\displaystyle \bigcup _{i\in \varnothing }A_{i}=\{x~:~{\text{ there exists }}i\in \varnothing {\text{ such that }}x\in A_{i}\}=\varnothing ,}$ which is somethings called the nullary union convention (despite being called a convention, this equality follows from the definition).
Arbitrary intersections defined
If ${\displaystyle I\neq \varnothing }$ then[4]
Nullary intersections
If ${\displaystyle I=\varnothing }$ then
${\displaystyle \bigcap _{i\in \varnothing }A_{i}=\{x~:~{\text{ for all }}i,{\text{ if }}i\in \varnothing {\text{ then }}x\in A_{i}\}}$
where every possible thing ${\displaystyle x}$ in the universe vacuously satisfied the condition: "if ${\displaystyle i\in \varnothing }$ then ${\displaystyle x\in A_{i}}$". Consequently, ${\displaystyle \bigcap _{i\in \varnothing }A_{i}=\{x~:~{\text{ for all }}i,{\text{ if }}i\in \varnothing {\text{ then }}x\in A_{i}\}=\{x:{\text{ for all }}i,{\text{ true }}\}}$ consists of everything in the universe.
So if ${\displaystyle I=\varnothing }$ and:
1. if you're working in a model in which there exists some universe set ${\displaystyle X}$ then ${\displaystyle \bigcap _{i\in \varnothing }A_{i}=\{x~:~x\in A_{i}{\text{ for every }}i\in \varnothing \}~=~X.}$
2. otherwise, if you're working in a model in which "the class of all things ${\displaystyle x}$" is not a set (by far the most common situation) then ${\displaystyle \bigcap _{i\in \varnothing }A_{i}}$ is undefined. This is because ${\displaystyle \bigcap _{i\in \varnothing }A_{i}=\{x~:~{\text{ for all }}i,{\text{ if }}i\in \varnothing {\text{ then }}x\in A_{i}\}}$ consists of everything, which makes ${\displaystyle \bigcap _{i\in \varnothing }A_{i}}$ a proper class and not a set.
Assumption: Henceforth, whenever a formula requires some indexing set to be non-empty in order for an arbitrary intersection to be well-defined, then this will automatically be assumed without mention.
A consequence of this is the following assumption/definition:
A finite intersection of sets or an intersection of finitely many sets refers to the intersection of a finite collection of one or more sets.
Some authors adopt the so called nullary intersection convention, which is the convention that an empty intersection of sets is equal to some canonical set. In particular, if all sets are subsets of some set ${\displaystyle X}$ then some author may declare that the empty intersection of these sets be equal to ${\displaystyle X.}$ However, the nullary intersection convention isn't as commonly accepted 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).

### Commutativity and associativity

${\displaystyle \bigcup _{\stackrel {i\in I,}{j\in J}}S_{i,j}~~\colon =~\bigcup _{(i,j)\in I\times J}S_{i,j}~=~\bigcup _{i\in I}\left(\bigcup _{j\in J}S_{i,j}\right)~=~\bigcup _{j\in J}\left(\bigcup _{i\in I}S_{i,j}\right)}$[4]
${\displaystyle \bigcap _{\stackrel {i\in I,}{j\in J}}S_{i,j}~~\colon =~\bigcap _{(i,j)\in I\times J}S_{i,j}~=~\bigcap _{i\in I}\left(\bigcap _{j\in J}S_{i,j}\right)~=~\bigcap _{j\in J}\left(\bigcap _{i\in I}S_{i,j}\right)}$[4]
Unions of unions and intersections of intersections
${\displaystyle \left(\bigcup _{i\in I}A_{i}\right)\cup B~=~\bigcup _{i\in I}\left(A_{i}\cup B\right)}$[4]
${\displaystyle \left(\bigcap _{i\in I}A_{i}\right)\cap B~=~\bigcap _{i\in I}\left(A_{i}\cap B\right)}$[4]

and if ${\displaystyle I=J}$ then also:[note 3]

### Distributing unions and intersections

#### Binary intersection of arbitrary unions

Importantly, if ${\displaystyle I=J}$ then in general, ${\displaystyle ~\left(\bigcup _{i\in I}A_{i}\right)\cap \left(\bigcup _{i\in I}B_{i}\right)~~\neq ~~\bigcup _{i\in I}\left(A_{i}\cap B_{i}\right)~}$ (see this[note 4] footnote for an example). The single union on the right hand side must be over all pairs ${\displaystyle (i,j)\in I\times I}$: ${\displaystyle ~\left(\bigcup _{i\in I}A_{i}\right)\cap \left(\bigcup _{i\in I}B_{i}\right)~=~\bigcup _{\stackrel {i\in I,}{j\in I}}\left(A_{i}\cap B_{j}\right).~}$ The same is usually true for other similar non-trivial set equalities and relations that depend on two (potentially unrelated) indexing sets ${\displaystyle I}$ and ${\displaystyle J}$ (such as Eq. 4b or Eq. 7g[5]). Two exceptions are Eq. 2c (unions of unions) and Eq. 2d (intersections of intersections), but both of these are among the most trivial of set equalities and moreover, even for these equalities there is still something that must be proven.[note 3]

#### Arbitrary intersections and arbitrary unions

The following inclusion always holds:

In general, equality need not hold and moreover, the right hand side depends on how, for each fixed ${\displaystyle i\in I,}$ the sets ${\displaystyle \left(S_{i,j}\right)_{j\in J}}$ are labelled (see this footnote[note 5] for an example) and the analogous statement is also true of the left hand side as well. Equality can hold under certain circumstances, such as in 7e and 7f, which are respectively the special cases where ${\displaystyle S_{i,j}\colon =A_{i}\setminus B_{j}}$ and ${\displaystyle \left({\hat {S}}_{j,i}\right)_{(j,i)\in J\times I}\colon =\left(A_{i}\setminus B_{j}\right)_{(j,i)\in J\times I}}$ (for 7f, ${\displaystyle I}$ and ${\displaystyle J}$ are swapped).

For an equality of sets that extends the distributive laws, an approach other than just switching ? and ? is needed. Suppose that for each ${\displaystyle i\in I,}$ there is some non-empty index set ${\displaystyle J_{i}}$ and for each ${\displaystyle j\in J_{i},}$ let ${\displaystyle R_{i,j}}$ be any set (for example, with ${\displaystyle \left(S_{i,j}\right)_{(i,j)\in I\times J}}$ use ${\displaystyle J_{i}\colon =J}$ for all ${\displaystyle i\in I}$ and use ${\displaystyle R_{i,j}\colon =S_{i,j}}$ for all ${\displaystyle i\in I}$ and all ${\displaystyle j\in J_{i}=J}$). Let

${\displaystyle {\mathcal {F}}~\colon =~\prod _{i\in I}J_{i}}$

be the Cartesian product, which can be interpreted as the set of all functions ${\displaystyle f~:~I~\to ~\bigcup _{i\in I}J_{i}}$ such that ${\displaystyle f(i)\in J_{i}}$ for every ${\displaystyle i\in I.}$ Then

where ${\displaystyle {\mathcal {F}}~=~\prod _{i\in I}J_{i}.}$

Example application: In the particular case where all ${\displaystyle J_{i}}$ are equal (that is, ${\displaystyle J_{i}=J_{i_{2}}}$ for all ${\displaystyle i,i_{2}\in I,}$ which is the case with the family ${\displaystyle \left(S_{i,j}\right)_{(i,j)\in I\times J},}$ for example), then letting ${\displaystyle J}$ denote this common set, this set ${\displaystyle {\mathcal {F}}~\colon =~\prod _{i\in I}J_{i}}$ will be ${\displaystyle {\mathcal {F}}=J^{I}}$; that is ${\displaystyle {\mathcal {F}}}$ will be the set of all functions of the form ${\displaystyle f~:~I~\to ~J.}$ The above set equalities Eq. 5 -> and Eq. 6 -> , respectively become:

• ${\displaystyle \bigcap _{i\in I}\left[\;\bigcup _{j\in J}S_{i,j}\right]=\bigcup _{f\in J^{I}}\left[\;\bigcap _{i\in I}S_{i,f(i)}\right]}$[4]
• ${\displaystyle \bigcup _{i\in I}\left[\;\bigcap _{j\in J}S_{i,j}\right]=\bigcap _{f\in J^{I}}\left[\;\bigcup _{i\in I}S_{i,f(i)}\right]}$[4]

which when combined with Inclusion 1 ? implies:

${\displaystyle \bigcup _{i\in I}\left[\bigcap _{j\in J}S_{i,j}\right]=\bigcap _{f\in J^{I}}\left[\;\bigcup _{i\in I}S_{i,f(i)}\right]~\subseteq ~\bigcup _{g\in I^{J}}\left[\;\bigcap _{j\in J}S_{g(j),j}\right]=\bigcap _{j\in J}\left[\bigcup _{i\in I}S_{i,j}\right]}$

where the indices ${\displaystyle g\in I^{J}}$ and ${\displaystyle g(j)\in I}$ (for ${\displaystyle j\in J}$) are used on the right hand side while ${\displaystyle f\in J^{I}}$ and ${\displaystyle f(i)\in J}$ (for ${\displaystyle i\in I}$) are used on the left hand side.

Example application: To apply the general formula to the case of ${\displaystyle \left(C_{k}\right)_{k\in K}}$ and ${\displaystyle \left(D_{l}\right)_{l\in L},}$ use ${\displaystyle I\colon =\{1,2\},}$ ${\displaystyle J_{1}\colon =K,}$ ${\displaystyle J_{2}\colon =L,}$ and let ${\displaystyle R_{1,k}\colon =C_{k}}$ for all ${\displaystyle k\in J_{1}}$ and let ${\displaystyle R_{2,l}\colon =D_{l}}$ for all ${\displaystyle l\in J_{2}.}$ Every map ${\displaystyle f\in {\mathcal {F}}~\colon =~\prod _{i\in I}J_{i}=J_{1}\times J_{2}=K\times L}$ can be bijectively identified with the pair ${\displaystyle \left(f(1),f(2)\right)\in K\times L}$ (the inverse sends ${\displaystyle (k,l)\in K\times L}$ to the map ${\displaystyle f_{(k,l)}\in {\mathcal {F}}}$ defined by ${\displaystyle 1\mapsto k}$ and ${\displaystyle 2\mapsto l}$; this is technically just a change of notation). Expanding and simplifying the left hand side of Eq. 5 -> , which recall was

${\displaystyle ~\bigcap _{i\in I}\left[\;\bigcup _{j\in J_{i}}R_{i,j}\right]=\bigcup _{f\in {\mathcal {F}}}\left[\;\bigcap _{i\in I}R_{i,f(i)}\right]~}$

gives

${\displaystyle \bigcap _{i\in I}\left[\;\bigcup _{j\in J_{i}}R_{i,j}\right]=\left(\bigcup _{j\in J_{1}}R_{1,j}\right)\cap \left(\;\bigcup _{j\in J_{2}}R_{2,j}\right)=\left(\bigcup _{k\in K}R_{1,k}\right)\cap \left(\;\bigcup _{l\in L}R_{2,l}\right)=\left(\bigcup _{k\in K}C_{k}\right)\cap \left(\;\bigcup _{l\in L}D_{l}\right)}$

and doing the same to the right hand side gives:

${\displaystyle \bigcup _{f\in {\mathcal {F}}}\left[\;\bigcap _{i\in I}R_{i,f(i)}\right]=\bigcup _{f\in {\mathcal {F}}}\left(R_{1,f(1)}\cap R_{2,f(2)}\right)=\bigcup _{f\in {\mathcal {F}}}\left(C_{f(1)}\cap D_{f(2)}\right)=\bigcup _{(k,l)\in K\times L}\left(C_{k}\cap D_{l}\right)=\bigcup _{\stackrel {k\in K,}{l\in L}}\left(C_{k}\cap D_{l}\right).}$

Thus the general identity Eq. 5 -> reduces down to the previously given set equality Eq. 3b:

• ${\displaystyle \left(\bigcup _{k\in K}C_{k}\right)\cap \left(\;\bigcup _{l\in L}D_{l}\right)=\bigcup _{\stackrel {k\in K,}{l\in L}}\left(C_{k}\cap D_{l}\right).}$

### Distributing subtraction

The following set equalities can be deduced from the equalities 7a - 7d above (see this note on why the following equalties are atypical):

### Distributing products

• If ${\displaystyle I=J}$ then
${\displaystyle \left(\prod _{i\in I}A_{i}\right)\cap \left(\prod _{i\in I}B_{i}\right)~=~\prod _{i\in I}\left(A_{i}\cap B_{i}\right)}$
If ${\displaystyle I\neq J}$ then in general ${\displaystyle \left(\prod _{i\in I}A_{i}\right)\cap \left(\prod _{j\in J}B_{j}\right)=\varnothing }$ (e.g. if ${\displaystyle I:=\{1,2\}}$ and ${\displaystyle J:=\{1,2,3\}}$ with all sets equal to ${\displaystyle \mathbb {R} }$ then ${\displaystyle \prod _{i\in I}A_{i}=\mathbb {R} ^{2}}$ and ${\displaystyle \prod _{j\in J}B_{j}=\mathbb {R} ^{3}}$) so only the case ${\displaystyle I=J}$ is useful.
• More generally,
${\displaystyle \bigcap _{i\in I}\left(\prod _{j\in J}S_{i,j}\right)~=~\prod _{j\in J}\left(\bigcap _{i\in I}S_{i,j}\right)}$
${\displaystyle \bigcup _{i\in I}\left(\prod _{j\in J}S_{i,j}\right)~\subseteq ~\prod _{j\in J}\left(\bigcup _{i\in I}S_{i,j}\right)}$

## Maps and sets

### Definitions

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

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

Images and preimages of sets

If ${\displaystyle S}$ is any set then by definition, the preimage of ${\displaystyle S}$ under ${\displaystyle f}$ is the set:

f-1 (S) ? { x ? domain f   :   f (x) ? S }

and the image of ${\displaystyle S}$ under ${\displaystyle f}$ is:

f (S) ? { f (s)  :  s ? S ? domain f  }

Denote the image or range of ${\displaystyle f:X\to Y,}$ which is the set ${\displaystyle f\left(\operatorname {domain} f\right)=f(X),}$ by ${\displaystyle \operatorname {Im} f}$ or ${\displaystyle \operatorname {image} f}$:

${\displaystyle \operatorname {Im} f~:=~f(\operatorname {domain} f)~=~f(X)~=~\{f(x)~:~x\in \operatorname {domain} f=X\}.}$

A set ${\displaystyle S}$ is said to be ${\displaystyle f}$-saturated or simply saturated if ${\displaystyle S=f^{-1}(f(S)),}$ which is only possible if ${\displaystyle S\subseteq \operatorname {domain} f.}$

Compositions

If ${\displaystyle f}$ and ${\displaystyle g}$ are maps then ${\displaystyle g\circ f}$ denotes the map

${\displaystyle g\circ f~:~\left\{x\in \operatorname {domain} f~:~f(x)\in \operatorname {domain} g\right\}~\to ~\operatorname {codomain} g}$

defined by

${\displaystyle \left(g\circ f\right)(x)=g\left(f\left(x\right)\right),}$

with ${\displaystyle \operatorname {domain} (g\circ f)=\left\{x\in \operatorname {domain} f~:~f(x)\in \operatorname {domain} g\right\}}$ and ${\displaystyle \operatorname {codomain} (g\circ f)=\operatorname {codomain} g.}$

The restriction of ${\displaystyle f:X\to Y}$ to ${\displaystyle S,}$ denoted by ${\displaystyle f{\big \vert }_{S},}$ is the map

${\displaystyle f{\big \vert }_{S}~:~S\cap \operatorname {domain} f~\to ~Y}$

with ${\displaystyle \operatorname {domain} f{\big \vert }_{S}~=~S\cap \operatorname {domain} f}$ defined by sending ${\displaystyle x\in S\cap \operatorname {domain} f}$ to ${\displaystyle f(x);}$ that is, ${\displaystyle f{\big \vert }_{S}\left(x\right)=f(x).}$ Alternatively, ${\displaystyle ~f{\big \vert }_{S}~=~f\circ \operatorname {In} ~}$ where ${\displaystyle ~\operatorname {In} ~:~S\cap X\to X~}$ denotes the natural inclusion, which is defined by ${\displaystyle \operatorname {In} \left(s\right)=s.}$

### Finitely many sets

Let ${\displaystyle f:X\to Y}$ be any function.

Let ${\displaystyle R,S,}$ and ${\displaystyle T}$ be completely arbitrary sets. Assume ${\displaystyle A\subseteq X}$ and ${\displaystyle C\subseteq Y.}$

Pulling set operations out of images or preimages
Image Preimage
${\displaystyle f\left(S\cup T\right)~=~f(S)\cup f(T)}$[6] ${\displaystyle f^{-1}\left(S\cup T\right)~=~f^{-1}(S)\cup f^{-1}(T)}$[4] None
${\displaystyle f\left(S\cap T\right)~\subseteq ~f(S)\cap f(T)}$

Equality holds if any of the following are true:

1. ${\displaystyle f}$ is injective.[7]
2. The restriction ${\displaystyle f{\big \vert }_{S\cup T}}$ is injective.
3. ${\displaystyle T\cap \operatorname {domain} f~=~f^{-1}\left(f(T)\right).}$[note 7]
4. ${\displaystyle T=f^{-1}\left(f(T)\right)}$ or ${\displaystyle S=f^{-1}\left(f(S)\right).}$
5. ${\displaystyle S\subseteq T}$ or ${\displaystyle S\cap \operatorname {domain} f\subseteq T.}$
6. ${\displaystyle f(S)\subseteq f\left(S\cap T\right)}$ or ${\displaystyle f(T)\subseteq f\left(S\cap T\right).}$
${\displaystyle f^{-1}\left(S\cap T\right)~=~f^{-1}(S)\cap f^{-1}(T)}$[4] None
${\displaystyle f\left(S\setminus T\right)~\supseteq ~f\left(S\right)\setminus f\left(T\right)}$

Equality holds if any of the following are true:

1. ${\displaystyle f}$ is injective.
2. The restriction ${\displaystyle f{\big \vert }_{S\cup T}}$ is injective.
3. ${\displaystyle T\cap \operatorname {domain} f~=~f^{-1}\left(f(T)\right).}$[note 7]
4. ${\displaystyle T=f^{-1}\left(f(T)\right).}$[note 7]
{\displaystyle {\begin{alignedat}{4}f^{-1}(S)\setminus f^{-1}(T)&=f^{-1}&&(&&S&&\setminus &&T)\\&=f^{-1}&&(&&S&&\setminus [&&T\cap \operatorname {Im} f])\\&=f^{-1}&&([&&S\cap \operatorname {Im} f]&&\setminus &&T)\\&=f^{-1}&&([&&S\cap \operatorname {Im} f]&&\setminus [&&T\cap \operatorname {Im} f])\end{alignedat}}}[8][4] None
${\displaystyle f\left(X\setminus T\right)~\supseteq ~f(X)\setminus f\left(T\right)=\operatorname {Im} f\setminus f\left(T\right)}$

If ${\displaystyle f}$ is surjective then ${\displaystyle f\left(X\setminus T\right)~\supseteq ~Y\setminus f(T).}$[note 8]

{\displaystyle {\begin{alignedat}{4}X\setminus f^{-1}(T)&=f^{-1}(&&Y&&\setminus &&T)\\&=f^{-1}(&&Y&&\setminus [&&T\cap \operatorname {Im} f])\\&=f^{-1}(&&\operatorname {Im} f&&\setminus &&T)\\&=f^{-1}(&&\operatorname {Im} f&&\setminus [&&T\cap \operatorname {Im} f])\end{alignedat}}}[note 9] None
${\displaystyle f\left(S~\triangle ~T\right)~\supseteq ~f(S)~\triangle ~f(T)}$

Equality holds if any of the following are true:

1. ${\displaystyle f}$ is injective.
2. The restriction ${\displaystyle f{\big \vert }_{S\cup T}}$ is injective.
${\displaystyle f^{-1}\left(S~\triangle ~T\right)~=~f^{-1}(S)~\triangle ~f^{-1}(T)}$ None
${\displaystyle f{\big \vert }_{S}(T)=f\left(S\cap T\right)}$ ${\displaystyle \left(f{\big \vert }_{S}\right)^{-1}(T)=S\cap f^{-1}(T)}$ None
${\displaystyle (g\circ f)(S)~=~g(f(S))}$ ${\displaystyle \left(g\circ f\right)^{-1}\left(S\right)~=~f^{-1}\left(g^{-1}(S)\right)}$ ${\displaystyle f}$ and ${\displaystyle g}$ are functions.

Counter-examples:

• This example shows that the set containments listed in the leftmost column of the above table can be strict/proper: Let ${\displaystyle f:X\to Y}$ be constant with range ${\displaystyle \operatorname {Im} f=\left\{y_{0}\right\}}$ and let ${\displaystyle S,T\subseteq X}$ be non-empty and disjoint subsets (i.e. ${\displaystyle S\neq \varnothing ,}$ ${\displaystyle T\neq \varnothing ,}$ and ${\displaystyle S\cap T=\varnothing ,}$ which implies ${\displaystyle S\setminus T=S}$ and ${\displaystyle S~\triangle ~T=S\cup T}$).
• The containment ${\displaystyle ~f(S\cap T)~\subseteq ~f(S)\cap f(T)~}$ is strict:
${\displaystyle \varnothing ~=~f\left(\varnothing \right)~=~f\left(S\cap T\right)~\neq ~f(S)\cap f(T)~=~\left\{y_{0}\right\}\cap \left\{y_{0}\right\}~=~\left\{y_{0}\right\}}$
• The containment ${\displaystyle ~f(S~\triangle ~T)~\supseteq ~f(S)~\triangle ~f(T)~}$ is strict:
${\displaystyle \left\{y_{0}\right\}~=~f\left(S\cup T\right)~=~f\left(S~\triangle ~T\right)~\neq ~f(S)~\triangle ~f(T)~=~\left\{y_{0}\right\}\triangle \left\{y_{0}\right\}~=~\varnothing }$
• The containment ${\displaystyle ~f(S\setminus T)~\supseteq ~f(S)\setminus f(T)~}$ is strict:
${\displaystyle \left\{y_{0}\right\}~=~f(S)~=~f\left(S\setminus T\right)~\neq ~f(S)\setminus f(T)~=~\left\{y_{0}\right\}\setminus \left\{y_{0}\right\}~=~\varnothing }$
• The containment ${\displaystyle ~f(X\setminus T)~\supseteq ~f(X)\setminus f(T)~}$ is strict:
${\displaystyle \left\{y_{0}\right\}~=~f\left(X\setminus T\right)~\neq ~f(X)\setminus f(T)~=~\left\{y_{0}\right\}\setminus \left\{y_{0}\right\}~=~\varnothing }$
where ${\displaystyle ~\left\{y_{0}\right\}=f(X\setminus T)~}$ because ${\displaystyle ~\varnothing \neq S\subseteq X\setminus T~}$ so ${\displaystyle ~X\setminus T~}$ is not empty.
Other identities
Image Preimage Additional assumptions on sets
{\displaystyle {\begin{alignedat}{4}f(S)&=f(S\cap \operatorname {domain} f)\\&=f(S\cap X)\end{alignedat}}} {\displaystyle {\begin{alignedat}{4}f^{-1}(S)&=f^{-1}(S\cap \operatorname {Im} f)\\&=f^{-1}(S\cap Y)\end{alignedat}}} None
${\displaystyle f(X)=\operatorname {Im} f\subseteq Y}$ {\displaystyle {\begin{alignedat}{4}f^{-1}(Y)&=X\\f^{-1}(\operatorname {Im} f)&=X\end{alignedat}}} None
{\displaystyle {\begin{alignedat}{4}f(T)&=f(T\cap S~&&\cup ~&&(&&T\setminus S))\\&=f(T\cap S)~&&\cup ~f&&(&&T\setminus S))\end{alignedat}}} {\displaystyle {\begin{alignedat}{4}f^{-1}(T)&=f^{-1}(T\cap S&&\cup &&(&&T&&\setminus &&S))\\&=f^{-1}(T\cap S)&&\cup f^{-1}&&(&&T&&\setminus &&S)\\&=f^{-1}(T\cap S)&&\cup f^{-1}&&(&&T&&\setminus [&&S\cap \operatorname {Im} f])\\&=f^{-1}(T\cap S)&&\cup f^{-1}&&([&&T\cap \operatorname {Im} f]&&\setminus &&S)\\&=f^{-1}(T\cap S)&&\cup f^{-1}&&([&&T\cap \operatorname {Im} f]&&\setminus [&&S\cap \operatorname {Im} f])\end{alignedat}}} None
${\displaystyle \operatorname {Im} f=f(X)~=~f(S)\cup f(X\setminus S)}$ {\displaystyle {\begin{alignedat}{4}X&=f^{-1}(S)\cup f^{-1}(Y&&\setminus S)\\&=f^{-1}(S)\cup f^{-1}(\operatorname {Im} f&&\setminus S)\end{alignedat}}} None
Equivalences and implications of images and preimages
Image Preimage Additional assumptions on sets
${\displaystyle S\subseteq T}$ implies ${\displaystyle f(S)\subseteq f(T)}$[8] ${\displaystyle S\subseteq T}$ implies ${\displaystyle f^{-1}(S)\subseteq f^{-1}(T)}$[8] None
${\displaystyle f\left(S\right)\subseteq \operatorname {Im} f\subseteq Y}$ ${\displaystyle f^{-1}\left(S\right)=X}$ if and only if ${\displaystyle \operatorname {Im} f\subseteq S}$ None
${\displaystyle f(S)=\varnothing }$ if and only if ${\displaystyle S\cap \operatorname {domain} f=\varnothing }$ ${\displaystyle f^{-1}(S)=\varnothing }$ if and only if ${\displaystyle S\cap \operatorname {Im} f=\varnothing }$ None
${\displaystyle f(A)=\varnothing }$ if and only if ${\displaystyle A=\varnothing }$ ${\displaystyle f^{-1}(C)=\varnothing }$ if and only if ${\displaystyle C\subseteq Y\setminus \operatorname {Im} f}$ ${\displaystyle A\subseteq X}$ and ${\displaystyle C\subseteq Y}$
The following are equivalent:
1. ${\displaystyle f\left(S\right)\subseteq f\left(T\right)}$
2. ${\displaystyle f\left(S\cup T\right)=f\left(T\right)}$
3. ${\displaystyle S\cap \operatorname {domain} f~\subseteq ~f^{-1}\left(f\left(T\right)\right)}$
The following are equivalent:
1. ${\displaystyle f^{-1}(S)\subseteq f^{-1}(T)}$
2. ${\displaystyle f^{-1}(S\cup T)=f^{-1}(T)}$
3. ${\displaystyle S\cap \operatorname {Im} f\subseteq T}$

If ${\displaystyle C~\subseteq ~\operatorname {Im} f}$ then ${\displaystyle f^{-1}(C)~\subseteq ~f^{-1}(T)}$ if and only if ${\displaystyle C~\subseteq ~T.}$

${\displaystyle C\subseteq \operatorname {Im} f}$
The following are equivalent when ${\displaystyle C\subseteq Y:}$
1. ${\displaystyle C\subseteq f(T)}$
2. ${\displaystyle f(B)=C}$ for some ${\displaystyle B\subseteq T}$
The following are equivalent:
1. ${\displaystyle S\subseteq f^{-1}(T)}$
2. ${\displaystyle f(S)\subseteq T}$ and ${\displaystyle S\subseteq \operatorname {domain} f}$

The following are equivalent when ${\displaystyle A\subseteq X:}$

1. ${\displaystyle A\subseteq f^{-1}(T)}$
2. ${\displaystyle f(A)\subseteq T}$
${\displaystyle A\subseteq X}$ and ${\displaystyle C\subseteq Y}$
The following are equivalent:
1. ${\displaystyle f(A)~\supseteq ~f\left(X\setminus A\right)}$
2. ${\displaystyle f(A)=\operatorname {Im} f}$
The following are equivalent:
1. ${\displaystyle f^{-1}(C)~\supseteq ~f^{-1}\left(Y\setminus C\right)}$
2. ${\displaystyle f^{-1}(C)=X}$
${\displaystyle A\subseteq X}$ and ${\displaystyle C\subseteq Y}$

Also:

• ${\displaystyle f(S)\cap T=\varnothing }$ if and only if ${\displaystyle S\cap f^{-1}\left(T\right)=\varnothing .}$[8]
Images of preimages and preimages of images

Let ${\displaystyle S}$ and ${\displaystyle T}$ be arbitrary sets, ${\displaystyle f:X\rightarrow Y}$ be any map, and let ${\displaystyle A\subseteq X}$ and ${\displaystyle C\subseteq Y}$.

Image of preimage Preimage of image Additional assumptions on sets
${\displaystyle f\left(f^{-1}(T)\right)=T\cap \operatorname {Im} f}$
${\displaystyle f^{-1}(f(T))~\supseteq ~T\cap f^{-1}\left(\operatorname {Im} f\right)=T\cap f^{-1}(Y)}$[8] None
${\displaystyle f\left(f^{-1}(T)\right)\subseteq T}$[8]

Equality holds if and only if the following is true:

1. ${\displaystyle T\subseteq \operatorname {Im} f.}$[9][10]

Equality holds if any of the following are true:

1. ${\displaystyle T\subseteq Y}$ and ${\displaystyle f:X\to Y}$ is surjective.
${\displaystyle f^{-1}(f(A))\supseteq A}$

Equality holds if and only if the following is true:

1. ${\displaystyle A}$ is ${\displaystyle f}$-saturated.

Equality holds if any of the following are true:

1. ${\displaystyle f}$ is injective.[9][10]
${\displaystyle A\subseteq X}$
${\displaystyle f\left(f^{-1}(Y)\right)=f\left(f^{-1}\left(\operatorname {Im} f\right)\right)=f(X)}$ ${\displaystyle f^{-1}(f(X))=f^{-1}\left(\operatorname {Im} f\right)=X}$ None
${\displaystyle f\left(f^{-1}(T)\cup S\right)~=~\left(T\cap \operatorname {Im} f\right)\cup f(S)~\subseteq ~T\cup f(S)}$ ${\displaystyle f^{-1}\left(f(A)\cup S\right)~\supseteq ~A\cup f^{-1}(S)}$[11]

Equality holds if any of the following are true:

1. ${\displaystyle f(A)\subseteq S.}$
2. ${\displaystyle A\subseteq f^{-1}(S).}$
${\displaystyle A\subseteq X}$
${\displaystyle f\left(f^{-1}(T)\cap S\right)=T\cap f(S)}$[8] ${\displaystyle f^{-1}(f(T)\cap S)~\supseteq ~T\cap f^{-1}(S)}$ None
${\displaystyle f\left(f^{-1}(f(T))\right)=f(T)}$ ${\displaystyle f^{-1}\left(f\left(f^{-1}(T)\right)\right)=f^{-1}(T)}$ None

### Arbitrarily many sets

Images and preimages of unions and intersections

Images and preimages of unions are always preserved. Inverse images preserve both unions and intersections. It is only images of intersections that are not always preserved.

If ${\displaystyle \left(S_{i}\right)_{i\in I}}$ is a family of arbitrary sets indexed by ${\displaystyle I\neq \varnothing }$ then:[8]

{\displaystyle {\begin{alignedat}{2}f^{-1}\left(\bigcap _{i\in I}S_{i}\right)&~=~\bigcap _{i\in I}f^{-1}\left(S_{i}\right)\\f^{-1}\left(\bigcup _{i\in I}S_{i}\right)&~=~\bigcup _{i\in I}f^{-1}\left(S_{i}\right)\\f\left(\bigcup _{i\in I}S_{i}\right)&~=~\bigcup _{i\in I}f\left(S_{i}\right)\\f\left(\bigcap _{i\in I}S_{i}\right)&~\subseteq ~\bigcap _{i\in I}f\left(S_{i}\right)\\\end{alignedat}}}

If all ${\displaystyle S_{i}}$ are ${\displaystyle f}$-saturated then ${\displaystyle \bigcap _{i\in I}S_{i}}$ be will be ${\displaystyle f}$-saturated and equality will hold in the last relation above. Explicitly, this means:

If ${\displaystyle \left(A_{i}\right)_{i\in I}}$ is a family of arbitrary subsets of ${\displaystyle X=\operatorname {domain} f,}$ which means that ${\displaystyle A_{i}\subseteq X}$ for all ${\displaystyle i,}$ then Conditional Equality 10a becomes:

Preimage from a Cartesian product

This subsection will discuss the preimage of a subset ${\displaystyle B\subseteq \prod _{j\in J}Y_{j}}$ under a map of the form ${\displaystyle F~:~X~\to ~\prod _{j\in J}Y_{j}.}$ For every ${\displaystyle k\in J,}$

• let ${\displaystyle \pi _{k}~:~\prod _{j\in J}Y_{j}~\to ~Y_{k}}$ denote the canonical projection onto ${\displaystyle Y_{k},}$ and
• let ${\displaystyle F_{k}~:=~\pi _{k}\circ F~:~X~\to ~Y_{k}}$

so that ${\displaystyle F~=~\left(F_{j}\right)_{j\in J},}$ which is also the unique map satisfying: ${\displaystyle \pi _{j}\circ F=F_{j}}$ for all ${\displaystyle j\in J.}$ The map ${\displaystyle \left(F_{j}\right)_{j\in J}~:~X~\to ~\prod _{j\in J}Y_{j}}$ should not be confused with the Cartesian product ${\displaystyle \prod _{j\in J}F_{j}}$ of these maps, which is by definition the map

${\displaystyle \prod _{j\in J}F_{j}~:~\prod _{j\in J}X~\to ~\prod _{j\in J}Y_{j}}$ defined by sending ${\displaystyle \left(x_{j}\right)_{j\in J}\in \prod _{j\in J}X}$ to ${\displaystyle \left(F_{j}\left(x_{j}\right)\right)_{j\in J}.}$

Observation — If ${\displaystyle F=\left(F_{j}\right)_{j\in J}~:~X~\to ~\prod _{j\in J}Y_{j}}$ and ${\displaystyle B~\subseteq ~\prod _{j\in J}Y_{j}}$ then

${\displaystyle F^{-1}(B)~\subseteq ~\bigcap _{j\in J}F_{j}^{-1}\left(\pi _{j}\left(B\right)\right).}$

If ${\displaystyle B=\prod _{j\in J}\pi _{j}\left(B\right)}$ then equality will hold:

For equality to hold, it suffices for there to exist a family ${\displaystyle \left(B_{j}\right)_{j\in J}}$ of subsets ${\displaystyle B_{j}\subseteq Y_{j}}$ such that ${\displaystyle B=\prod _{j\in J}B_{j},}$ in which case:

and ${\displaystyle \pi _{j}\left(B\right)=B_{j}}$ for all ${\displaystyle j\in J.}$

## Families of sets

### Definitions

A family of sets or simply a family is a set whose elements are sets. A family over ${\displaystyle X}$ is a family of subsets of ${\displaystyle X.}$

If ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$ are families of sets then define:[12]

${\displaystyle {\mathcal {A}}\;(\cup )\;{\mathcal {B}}~\colon =~\left\{~A\cup B~:~A\in {\mathcal {A}}~{\text{ and }}~B\in {\mathcal {B}}~\right\}}$
${\displaystyle {\mathcal {A}}\;(\cap )\;{\mathcal {B}}~\colon =~\left\{~A\cap B~:~A\in {\mathcal {A}}~{\text{ and }}~B\in {\mathcal {B}}~\right\}}$
${\displaystyle {\mathcal {A}}\;(\setminus )\;{\mathcal {B}}~\colon =~\left\{~A\setminus B~:~A\in {\mathcal {A}}~{\text{ and }}~B\in {\mathcal {B}}~\right\}}$

which are respectively called pairwise union, pairwise intersection, and pairwise set difference. The regular union, intersection, and set difference are all defined as usual and are denoted with their usual notation: ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}},}$ ${\displaystyle {\mathcal {A}}\cap {\mathcal {B}},}$ and ${\displaystyle {\mathcal {A}}\setminus {\mathcal {B}},}$ respectively. These pairwise operations on families of sets play an important role in, among other subjects, the theory of filters and prefilters on sets.

The power set of a set ${\displaystyle X}$ is the set of all subsets of ${\displaystyle X}$:

${\displaystyle \wp (X)~\colon =~\{\;S~:~S\subseteq X\;\}.}$

The upward closure in ${\displaystyle X}$ of a family ${\displaystyle {\mathcal {A}}\subseteq \wp (X)}$ is the family:

${\displaystyle {\mathcal {A}}^{\uparrow X}~\colon =~\bigcup _{A\in {\mathcal {A}}}\{\;S~:~A\subseteq S\subseteq X\;\}~=~\{\;S\subseteq X~:~{\text{ there exists }}A\in {\mathcal {A}}{\text{ such that }}A\subseteq S\;\}}$

and the downward closure of ${\displaystyle {\mathcal {A}}}$ is the family:

${\displaystyle {\mathcal {A}}^{\downarrow }~\colon =~\bigcup _{A\in {\mathcal {A}}}\wp (A)~=~\{\;S~:~{\text{ there exists }}A\in {\mathcal {A}}{\text{ such that }}S\subseteq A\;\}.}$

A family ${\displaystyle {\mathcal {A}}}$ is called isotone, ascending, or upward closed in ${\displaystyle X}$ if ${\displaystyle {\mathcal {A}}\subseteq \wp (X)}$ and ${\displaystyle {\mathcal {A}}={\mathcal {A}}^{\uparrow X}.}$[12] A family ${\displaystyle {\mathcal {A}}}$ is called downward closed if ${\displaystyle {\mathcal {A}}={\mathcal {A}}^{\downarrow }.}$

### Basic properties

Suppose ${\displaystyle {\mathcal {A}},}$ ${\displaystyle {\mathcal {B}},}$ and ${\displaystyle {\mathcal {C}}}$ are families of sets over ${\displaystyle X.}$

Commutativity:[12]
• ${\displaystyle {\mathcal {A}}\;(\cup )\;{\mathcal {B}}={\mathcal {B}}\;(\cup )\;{\mathcal {A}}}$
• ${\displaystyle {\mathcal {A}}\;(\cap )\;{\mathcal {B}}={\mathcal {B}}\;(\cap )\;{\mathcal {A}}}$
Associativity:[12]
• ${\displaystyle [{\mathcal {A}}\;(\cup )\;{\mathcal {B}}]\;(\cup )\;{\mathcal {A}}={\mathcal {A}}\;(\cup )\;[{\mathcal {B}}\;(\cup )\;{\mathcal {C}}]}$
• ${\displaystyle [{\mathcal {A}}\;(\cap )\;{\mathcal {B}}]\;(\cap )\;{\mathcal {A}}={\mathcal {A}}\;(\cap )\;[{\mathcal {B}}\;(\cap )\;{\mathcal {C}}]}$
Identity:
• ${\displaystyle {\mathcal {A}}\;(\cup )\;\{\varnothing \}={\mathcal {A}}}$
• ${\displaystyle {\mathcal {A}}\;(\cap )\;\{X\}={\mathcal {A}}}$
• ${\displaystyle {\mathcal {A}}\;(\setminus )\;\{\varnothing \}={\mathcal {A}}}$
Domination:
• ${\displaystyle {\mathcal {A}}\;(\cup )\;\{X\}=\{X\}~~~~{\text{ if }}{\mathcal {A}}\neq \varnothing }$
• ${\displaystyle {\mathcal {A}}\;(\cap )\;\{\varnothing \}=\{\varnothing \}~~~~{\text{ if }}{\mathcal {A}}\neq \varnothing }$
• ${\displaystyle {\mathcal {A}}\;(\cup )\;\varnothing =\varnothing }$
• ${\displaystyle {\mathcal {A}}\;(\cap )\;\varnothing =\varnothing }$
• ${\displaystyle {\mathcal {A}}\;(\setminus )\;\varnothing =\varnothing }$
• ${\displaystyle \varnothing \;(\setminus )\;{\mathcal {B}}=\varnothing }$

## Notes

1. ^ Here "smallest" means relative to subset containment. So if ${\displaystyle \Phi }$ is any algebra of sets containing ${\displaystyle {\mathcal {S}},}$ then ${\displaystyle \Phi _{\mathcal {S}}\subseteq \Phi .}$
2. ^ Since ${\displaystyle {\mathcal {S}}\neq \varnothing ,}$ there is some ${\displaystyle S\in {\mathcal {S}}_{0}}$ such that its complement also belongs to ${\displaystyle {\mathcal {S}}_{0}.}$ The intersection of these two sets implies that ${\displaystyle \varnothing \in {\mathcal {S}}_{1}.}$ The union of these two sets is equal to ${\displaystyle X,}$ which implies that ${\displaystyle X\in \Phi _{\mathcal {S}}.}$
3. ^ a b To deduce Eq. 2c from Eq. 2a, it must still be shown that ${\displaystyle \bigcup _{\stackrel {i\in I,}{j\in I}}\left(A_{i}\cup B_{j}\right)~=~\bigcup _{i\in I}\left(A_{i}\cup B_{i}\right)}$ so Eq. 2c is not a completely immediate consequence of Eq. 2a. (Compare this to the commentary about Eq. 3b).
4. ^ Let ${\displaystyle X\neq \varnothing }$ and let ${\displaystyle I=\{1,2\}.}$ Let ${\displaystyle A_{1}\colon =B_{2}\colon =X}$ and let ${\displaystyle A_{2}\colon =B_{1}\colon =\varnothing .}$ Then ${\displaystyle X=X\cap X=\left(A_{1}\cup A_{2}\right)\cap \left(B_{2}\cup B_{2}\right)=\left(\bigcup _{i\in I}A_{i}\right)\cap \left(\bigcup _{i\in I}B_{i}\right)~\neq ~\bigcup _{i\in I}\left(A_{i}\cap B_{i}\right)=\left(A_{1}\cap B_{1}\right)\cup \left(A_{2}\cap B_{2}\right)=\varnothing \cup \varnothing =\varnothing .}$
5. ^ To see why equality need not hold when ${\displaystyle \cup }$ and ${\displaystyle \cap }$ are swapped, let ${\displaystyle I\colon =J\colon =\{1,2\},}$ and let ${\displaystyle S_{11}=\{1,2\},~}$ ${\displaystyle S_{12}=\{1,3\},~}$ ${\displaystyle S_{21}=\{3,4\},~}$ and ${\displaystyle S_{22}=\{2,4\}.}$ Then ${\displaystyle \{1,4\}=\left(S_{11}\cap S_{12}\right)\cup \left(S_{21}\cap S_{22}\right)=\bigcup _{i\in I}\left(\bigcap _{j\in J}S_{i,j}\right)~\neq ~\bigcap _{j\in J}\left(\bigcup _{i\in I}S_{i,j}\right)=\left(S_{11}\cup S_{21}\right)\cap \left(S_{12}\cup S_{22}\right)=\{1,2,3,4\}.}$ If ${\displaystyle S_{11}}$ and ${\displaystyle S_{21}}$ are swapped while ${\displaystyle S_{12}}$ and ${\displaystyle S_{22}}$ are unchanged, which gives rise to the sets ${\displaystyle {\hat {S}}_{11}:=S_{21}=\{3,4\},~}$ ${\displaystyle {\hat {S}}_{12}:=\{1,3\},~}$ ${\displaystyle {\hat {S}}_{21}:=S_{11}=\{1,2\},~}$ and ${\displaystyle {\hat {S}}_{22}:=\{2,4\},~}$ then ${\displaystyle \{2,3\}=\bigcup _{i\in I}\left(\bigcap _{j\in J}{\hat {S}}_{i,j}\right)~\neq ~\bigcap _{j\in J}\left(\bigcup _{i\in I}{\hat {S}}_{i,j}\right)=\{1,2,3,4\}.}$ In particular, the left hand side is no longer ${\displaystyle \{1,4\},}$ which shows that the left hand side ${\displaystyle \bigcup _{i\in I}\left(\bigcap _{j\in J}S_{i,j}\right)}$ depends on how the sets are labelled. Had instead ${\displaystyle S_{11}}$ and ${\displaystyle S_{12}}$ been swapped (with ${\displaystyle S_{21}}$ and ${\displaystyle S_{22}}$ unchanged) then both the left hand side and right hand side would have been equal to ${\displaystyle \{1,4\},}$ which shows that both sides depend on how the sets are labeled.
6. ^ So, for instance, it's even possible that ${\displaystyle S\cap (X\cup Y)=\varnothing ,}$ or that ${\displaystyle S\cap X\neq \varnothing }$ and ${\displaystyle S\cap Y\neq \varnothing }$ (which happens, for instance, if ${\displaystyle X=Y}$), etc.
7. ^ a b c Note that this condition ${\displaystyle T\cap \operatorname {domain} f=f^{-1}\left(f(T)\right)}$ depends entirely on ${\displaystyle T}$ and not on ${\displaystyle S.}$
8. ^ ${\displaystyle f\left(X\setminus T\right)~\supseteq ~Y\setminus f(T)}$ can be rewritten as: ${\displaystyle f\left(T^{\operatorname {C} }\right)~\supseteq ~f\left(T\right)^{\operatorname {C} }.}$
9. ^ The conclusion ${\displaystyle X\setminus f^{-1}(S)=f^{-1}\left(Y\setminus S\right)}$ can also be written as: ${\displaystyle f^{-1}(T)^{\operatorname {C} }~=~f^{-1}\left(T^{\operatorname {C} }\right).}$

## Citations

1. ^ Taylor, Courtney (March 31, 2019). "What Is Symmetric Difference in Math?". ThoughtCo. Retrieved .
2. ^ Weisstein, Eric W. "Symmetric Difference". mathworld.wolfram.com. Retrieved .
3. ^ a b c d "Algebra of sets". Encyclopediaofmath.org. 16 August 2013. Retrieved 2020.
4. Monk 1969, pp. 24-54.
5. Császár 1978, pp. 15-26.
6. ^ Kelley 1985, p. 85
7. ^ See Munkres 2000, p. 21
8. Császár 1978, pp. 102-120.
9. ^ a b See Halmos 1960, p. 39
10. ^ a b See Munkres 2000, p. 19
11. ^ See p.388 of Lee, John M. (2010). Introduction to Topological Manifolds, 2nd Ed.
12. ^ a b c d Császár 1978, pp. 53-65.