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 ( $\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,$ and $X$ will denote sets and $\wp (X)$ will denote the power set of $X.$ 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 $A$ will be denoted by $A^{C}$ where unless indicated otherwise, it should be assumed that $A^{C}$ denotes the complement of $A$ in (the universe) $X.$

For sets $A$ and $B,$ define:

{\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 $A$ and $B$ is:[1][2]

{\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 $B$ is:

B^{C}=X\setminus B

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

Algebra of sets

A family $\Phi$ of subsets of a set $X$ is said to be an algebra of sets if $\varnothing \in \Phi$ and for all $A,B\in \Phi ,$ all three of the sets $X\setminus A,$ $A\cap B,$ and $A\cup B$ are elements of $\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 ${\mathcal {S}}$ of subsets of $X,$ there is a unique smallest[note 1] algebra of sets in $X$ containing ${\mathcal {S}}.$ [3] It is called the algebra generated by ${\mathcal {S}}$ and we'll denote it by $\Phi _{\mathcal {S}}.$ This algebra can be constructed as follows:[3]

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

Basic set relationships

Let $A,B,$ and $C$ be subsets of $X.$

Commutativity:[4]

$A\cup B=B\cup A$
$A\cap B=B\cap A$
$A\,\triangle B=B\,\triangle A$

Associativity:[4]

$(A\cup B)\cup C=A\cup (B\cup C)$
$(A\cap B)\cap C=A\cap (B\cap C)$
$(A\,\triangle B)\,\triangle C=A\,\triangle (B\,\triangle C)$

Distributivity:[4]

$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
$A\cap (B\,\triangle C)=(A\cap B)\,\triangle (A\cap C)$
$A\times (B\cap C)=(A\times B)\cap (A\times C)$
$A\times (B\cup C)=(A\times B)\cup (A\times C)$
$A\times (B\,\setminus C)=(A\times B)\,\setminus (A\times C)$

Identity:[4]

$A\cap X=A$
$A\cup \varnothing =A$
$A\setminus \varnothing =A$
$A\,\triangle \varnothing =A$

Complement:[4]

$A\cup A^{C}=X$
$A\cap A^{C}=\varnothing$
$A\,\triangle A^{C}=X$

Idempotent:[4]

$A\cup A=A$
$A\cap A=A$

Domination:[4]

$A\cup X=X$
$A\cap \varnothing =\varnothing$
$A\times \varnothing =\varnothing$

Absorption laws:

$A\cup (A\cap B)=A$
$A\cap (A\cup B)=A$

Complements

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

Intersection can be expressed in terms of set difference:

{\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]

A\setminus \varnothing =A

{\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 $A,B,C\subseteq X.$

A^{C}=X\setminus A

(by definition of this notation)

De Morgan's laws:

$(A\cup B)^{C}=A^{C}\cap B^{C}$
$(A\cap B)^{C}=A^{C}\cup B^{C}$

Double complement or involution law:

${(A^{C})}^{C}=A$

Complement laws for the universe set and the empty set:

$\varnothing ^{C}=X$
$X^{C}=\varnothing$

Uniqueness of complements:

If $A\cup B=X$ and $A\cap B=\varnothing$ then $B=A^{C}$

Complements and set subtraction

$B\setminus A=A^{C}\cap B$

$(B\setminus A)^{C}=A\cup B^{C}$

$B^{C}\setminus A^{C}=A\setminus B$

Subset inclusion

The following are equivalent:[4]

$A\subseteq B$
$A\cap B=A$
$A\cup B=B$
$A\setminus B=\varnothing$
$B^{C}\subseteq A^{C}$

Inclusion is a partial order

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

Reflexivity:

$A\subseteq A$

Antisymmetry:

$A\subseteq B$ and $B\subseteq A$ if and only if $A=B$

Transitivity:

If $A\subseteq B$ and $B\subseteq C,$ then $A\subseteq C$

Lattice properties

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:

$\varnothing \subseteq A\subseteq X$

Existence of joins:[4]

$A\subseteq A\cup B$
If $A\subseteq C$ and $B\subseteq C$ then $A\cup B\subseteq C$

Existence of meets:[4]

$A\cap B\subseteq A$
If $C\subseteq A$ and $C\subseteq B$ then $C\subseteq A\cap B$

Other properties

If $A\subseteq X$ and $B\subseteq Y$ then $A\times B\subseteq X\times Y$ [4]

If $A\subseteq B$ then $C\setminus B\subseteq C\setminus A$

Multiple set operations

Expressing basic set operations

{\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}}

{\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}}

{\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}}

{\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, $L$ is the L eft most set, $M$ is the M iddle set, and $R$ is the R ight most set.

Identities involving set subtraction followed by a second set operation

{\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}}

{\begin{alignedat}{2}L\setminus (M\cap R)&=(L\setminus M)\cup (L\setminus R)~~~~{\text{ (De Morgan's law) }}\\\end{alignedat}}

{\begin{alignedat}{2}L\setminus (M\setminus R)&=(L\setminus M)\cup (L\cap R)\\\end{alignedat}}

So if $L\subseteq M$ then $L\setminus (M\setminus R)=L\cap R$

{\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}}

{\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}}

{\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]

{\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}}

{\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

{\begin{alignedat}{2}(L\cup M)\setminus R&=(L\setminus R)\cup (M\setminus R)\\\end{alignedat}}

{\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}}

{\begin{alignedat}{2}(L\,\triangle \,M)\setminus R&=(L\setminus R)~&&\triangle ~(M\setminus R)\\&=(L\cup R)~&&\triangle ~(M\cup R)\\\end{alignedat}}

{\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}}

{\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

L\subseteq M

then

L\setminus R=L\cap (M\setminus R).

[5]

Arbitrary families of sets

Let $\left(A_{i}\right)_{i\in I},$ $\left(B_{j}\right)_{j\in J},$ and $\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 $I$ and $J,$ are assumed to be non-empty.

Definitions

Arbitrary unions defined

\bigcup _{i\in I}A_{i}~~\colon =~\{x~:~{\text{ there exists }}i\in I{\text{ such that }}x\in A_{i}\}

[4]

(Def. 1)

If

I=\varnothing

then

\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

I\neq \varnothing

then[4]

\bigcap _{i\in I}A_{i}~~\colon =~\{x~:~x\in A_{i}{\text{ for every }}i\in I\}~=~\{x~:~{\text{ for all }}i,{\text{ if }}i\in I{\text{ then }}x\in A_{i}\}.

(Def. 2)

Nullary intersections

If

I=\varnothing

then

\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

x

in the universe vacuously satisfied the condition: "if

i\in \varnothing

then

x\in A_{i}

". Consequently,

\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

I=\varnothing

and:

if you're working in a model in which there exists some universe set $X$ then $\bigcap _{i\in \varnothing }A_{i}=\{x~:~x\in A_{i}{\text{ for every }}i\in \varnothing \}~=~X.$
otherwise, if you're working in a model in which "the class of all things $x$ " is not a set (by far the most common situation) then $\bigcap _{i\in \varnothing }A_{i}$ is undefined. This is because $\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 $\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

X

then some author may declare that the empty intersection of these sets be equal to

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

\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]

\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

\left(\bigcup _{i\in I}A_{i}\right)\cup B~=~\bigcup _{i\in I}\left(A_{i}\cup B\right)

[4]

\left(\bigcap _{i\in I}A_{i}\right)\cap B~=~\bigcap _{i\in I}\left(A_{i}\cap B\right)

[4]

\left(\bigcup _{i\in I}A_{i}\right)\cup \left(\bigcup _{j\in J}B_{j}\right)~=~\bigcup _{\stackrel {i\in I,}{j\in J}}\left(A_{i}\cup B_{j}\right)

[4]

(Eq. 2a)

\left(\bigcap _{i\in I}A_{i}\right)\cap \left(\bigcap _{j\in J}B_{j}\right)~=~\bigcap _{\stackrel {i\in I,}{j\in J}}\left(A_{i}\cap B_{j}\right)

[4]

(Eq. 2b)

and if $I=J$ then also:[note 3]

\left(\bigcup _{i\in I}A_{i}\right)\cup \left(\bigcup _{i\in I}B_{i}\right)~=~\bigcup _{i\in I}\left(A_{i}\cup B_{i}\right)

[4]

(Eq. 2c)

\left(\bigcap _{i\in I}A_{i}\right)\cap \left(\bigcap _{i\in I}B_{i}\right)~=~\bigcap _{i\in I}\left(A_{i}\cap B_{i}\right)

[4]

(Eq. 2d)

Binary intersection of arbitrary unions

\left(\bigcup _{i\in I}A_{i}\right)\cap B~=~\bigcup _{i\in I}\left(A_{i}\cap B\right)

(Eq. 3a)

\left(\bigcup _{i\in I}A_{i}\right)\cap \left(\bigcup _{j\in J}B_{j}\right)~=~\bigcup _{\stackrel {i\in I,}{j\in J}}\left(A_{i}\cap B_{j}\right)

[5]

(Eq. 3b)

Importantly, if

I=J

then in general,

~\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

(i,j)\in I\times I

:

~\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

I

and

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]

Binary union of arbitrary intersections

\left(\bigcap _{i\in I}A_{i}\right)\cup B~=~\bigcap _{i\in I}\left(A_{i}\cup B\right)

(Eq. 4a)

\left(\bigcap _{i\in I}A_{i}\right)\cup \left(\bigcap _{j\in J}B_{j}\right)~=~\bigcap _{\stackrel {i\in I,}{j\in J}}\left(A_{i}\cup B_{j}\right)

[5]

(Eq. 4b)

Arbitrary intersections and arbitrary unions

The following inclusion always holds:

\bigcup _{i\in I}\left(\bigcap _{j\in J}S_{i,j}\right)~\subseteq ~\bigcap _{j\in J}\left(\bigcup _{i\in I}S_{i,j}\right)

(Inclusion 1 ∪∩ ⊆ ∩∪)

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\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 $S_{i,j}\colon =A_{i}\setminus B_{j}$ and $\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, $I$ and $J$ are swapped).

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

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

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

\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]

(Eq. 5 ∩∪ → ∪∩)

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

(Eq. 6 ∪∩ → ∩∪)

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

Example application: 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,j)\in I\times J},$ for example), then letting $J$ denote this common set, this set ${\mathcal {F}}~\colon =~\prod _{i\in I}J_{i}$ will be ${\mathcal {F}}=J^{I}$ ; that is ${\mathcal {F}}$ will be the set of all functions of the form $f~:~I~\to ~J.$ The above set equalities Eq. 5 ∩∪ → ∪∩ and Eq. 6 ∪∩ → ∩∪, respectively become:

$\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]

$\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:

\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 $g\in I^{J}$ and $g(j)\in I$ (for $j\in J$ ) are used on the right hand side while $f\in J^{I}$ and $f(i)\in J$ (for $i\in I$ ) are used on the left hand side.

Example application: To apply the general formula to the case of $\left(C_{k}\right)_{k\in K}$ and $\left(D_{l}\right)_{l\in L},$ use $I\colon =\{1,2\},$ $J_{1}\colon =K,$ $J_{2}\colon =L,$ and let $R_{1,k}\colon =C_{k}$ for all $k\in J_{1}$ and let $R_{2,l}\colon =D_{l}$ for all $l\in J_{2}.$ Every map $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 $\left(f(1),f(2)\right)\in K\times L$ (the inverse sends $(k,l)\in K\times L$ to the map $f_{(k,l)}\in {\mathcal {F}}$ defined by $1\mapsto k$ and $2\mapsto l$ ; this is technically just a change of notation). Expanding and simplifying the left hand side of Eq. 5 ∩∪ → ∪∩, which recall was

~\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

\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:

\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:

$\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

\left(\bigcup _{i\in I}A_{i}\right)\;\setminus \;B~=~\bigcup _{i\in I}\left(A_{i}\;\setminus \;B\right)

(Eq. 7a)

\left(\bigcap _{i\in I}A_{i}\right)\;\setminus \;B~=~\bigcap _{i\in I}\left(A_{i}\;\setminus \;B\right)

(Eq. 7b)

A\;\setminus \;\left(\bigcup _{j\in J}B_{j}\right)~=~\bigcap _{j\in J}\left(A\;\setminus \;B_{j}\right)

(De Morgan's law)[5]

(Eq. 7c)

A\;\setminus \;\left(\bigcap _{j\in J}B_{j}\right)~=~\bigcup _{j\in J}\left(A\;\setminus \;B_{j}\right)

(De Morgan's law)[5]

(Eq. 7d)

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

\left(\bigcup _{i\in I}A_{i}\right)\;\setminus \;\left(\bigcup _{j\in J}B_{j}\right)~=~\bigcup _{i\in I}\left(\bigcap _{j\in J}\left(A_{i}\;\setminus \;B_{j}\right)\right)~=~\bigcap _{j\in J}\left(\bigcup _{i\in I}\left(A_{i}\;\setminus \;B_{j}\right)\right)

(Eq. 7e)

\left(\bigcap _{i\in I}A_{i}\right)\;\setminus \;\left(\bigcap _{j\in J}B_{j}\right)~=~\bigcup _{j\in J}\left(\bigcap _{i\in I}\left(A_{i}\;\setminus \;B_{j}\right)\right)~=~\bigcap _{i\in I}\left(\bigcup _{j\in J}\left(A_{i}\;\setminus \;B_{j}\right)\right)

(Eq. 7f)

\left(\bigcup _{i\in I}A_{i}\right)\;\setminus \;\left(\bigcap _{j\in J}B_{j}\right)~=~\bigcup _{\stackrel {i\in I,}{j\in J}}\left(A_{i}\;\setminus \;B_{j}\right)

(Eq. 7g)

\left(\bigcap _{i\in I}A_{i}\right)\;\setminus \;\left(\bigcup _{j\in J}B_{j}\right)~=~\bigcap _{\stackrel {i\in I,}{j\in J}}\left(A_{i}\;\setminus \;B_{j}\right)

(Eq. 7h)

Distributing products

If $I=J$ then

\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

I\neq J

then in general

\left(\prod _{i\in I}A_{i}\right)\cap \left(\prod _{j\in J}B_{j}\right)=\varnothing

(e.g. if

I:=\{1,2\}

and

J:=\{1,2,3\}

with all sets equal to

\mathbb {R}

then

\prod _{i\in I}A_{i}=\mathbb {R} ^{2}

and

\prod _{j\in J}B_{j}=\mathbb {R} ^{3}

) so only the case

I=J

is useful.

More generally,

\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)

\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 $f:X\to Y$ be any function, where we denote its domain $X$ by $\operatorname {domain} f$ and denote its codomain $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 (i.e. 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 $S$ is declared to be "any set," and it is not indicated that $S$ must be somehow related to $X$ or $Y$ (say for instance, that it be a subset $X$ or $Y$ ) then it is meant that $S$ is truly arbitrary.[note 6] 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 $S$ might not be entirely contained in $X=\operatorname {domain} f$ and/or $Y=\operatorname {codomain} f$ (e.g. if all that is known about $S$ is that $S\subseteq U$ ); in such a situation it may be useful to know what can and cannot be said about $f(S)$ and/or $f^{-1}(S)$ without having to introduce a (potentially unnecessary) intersection such as: $f(S\cap X)$ and/or $f^{-1}(S\cap Y).$

Images and preimages of sets

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

f -1 (S) ≝ {x \in domain f : f (x) \in S}

and the image of $S$ under $f$ is:

f (S) ≝ {f (s) : s \in S \cap domain f}

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

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

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

Compositions

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

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

defined by

\left(g\circ f\right)(x)=g\left(f\left(x\right)\right),

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

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

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

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

Finitely many sets

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

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

Pulling set operations out of images or preimages

Image	Preimage	Additional assumptions on sets
$f\left(S\cup T\right)~=~f(S)\cup f(T)$ [6]	$f^{-1}\left(S\cup T\right)~=~f^{-1}(S)\cup f^{-1}(T)$ [4]	None
$f\left(S\cap T\right)~\subseteq ~f(S)\cap f(T)$ Equality holds if any of the following are true: $f$ is injective.[7] The restriction $f{\big \vert }_{S\cup T}$ is injective. $T\cap \operatorname {domain} f~=~f^{-1}\left(f(T)\right).$ [note 7] $T=f^{-1}\left(f(T)\right)$ or $S=f^{-1}\left(f(S)\right).$ $S\subseteq T$ or $S\cap \operatorname {domain} f\subseteq T.$ $f(S)\subseteq f\left(S\cap T\right)$ or $f(T)\subseteq f\left(S\cap T\right).$	$f^{-1}\left(S\cap T\right)~=~f^{-1}(S)\cap f^{-1}(T)$ [4]	None
$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: $f$ is injective. The restriction $f{\big \vert }_{S\cup T}$ is injective. $T\cap \operatorname {domain} f~=~f^{-1}\left(f(T)\right).$ [note 7] $T=f^{-1}\left(f(T)\right).$ [note 7]	${\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
$f\left(X\setminus T\right)~\supseteq ~f(X)\setminus f\left(T\right)=\operatorname {Im} f\setminus f\left(T\right)$ If $f$ is surjective then $f\left(X\setminus T\right)~\supseteq ~Y\setminus f(T).$ [note 8]	${\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
$f\left(S~\triangle ~T\right)~\supseteq ~f(S)~\triangle ~f(T)$ Equality holds if any of the following are true: $f$ is injective. The restriction $f{\big \vert }_{S\cup T}$ is injective.	$f^{-1}\left(S~\triangle ~T\right)~=~f^{-1}(S)~\triangle ~f^{-1}(T)$	None
$f{\big \vert }_{S}(T)=f\left(S\cap T\right)$	$\left(f{\big \vert }_{S}\right)^{-1}(T)=S\cap f^{-1}(T)$	None
$(g\circ f)(S)~=~g(f(S))$	$\left(g\circ f\right)^{-1}\left(S\right)~=~f^{-1}\left(g^{-1}(S)\right)$	$f$ and $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 $f:X\to Y$ $\text{[math]}$ be constant with range $\operatorname {Im} f=\left\{y_{0}\right\}$ $\text{[math]}$ and let $S,T\subseteq X$ $\text{[math]}$ be non-empty and disjoint subsets (i.e. $S\neq \varnothing ,$ $\text{[math]}$ $T\neq \varnothing ,$ $\text{[math]}$ and $S\cap T=\varnothing ,$ $\text{[math]}$ which implies $S\setminus T=S$ $\text{[math]}$ and $S~\triangle ~T=S\cup T$ $\text{[math]}$ ).
- The containment $~f(S\cap T)~\subseteq ~f(S)\cap f(T)~$ is strict:
  $\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 $~f(S~\triangle ~T)~\supseteq ~f(S)~\triangle ~f(T)~$ is strict:
  $\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 $~f(S\setminus T)~\supseteq ~f(S)\setminus f(T)~$ is strict:
  $\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 $~f(X\setminus T)~\supseteq ~f(X)\setminus f(T)~$ is strict:
  $\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 $~\left\{y_{0}\right\}=f(X\setminus T)~$ because $~\varnothing \neq S\subseteq X\setminus T~$ so $~X\setminus T~$ is not empty.

Other identities

Image	Preimage	Additional assumptions on sets
${\begin{alignedat}{4}f(S)&=f(S\cap \operatorname {domain} f)\\&=f(S\cap X)\end{alignedat}}$	${\begin{alignedat}{4}f^{-1}(S)&=f^{-1}(S\cap \operatorname {Im} f)\\&=f^{-1}(S\cap Y)\end{alignedat}}$	None
$f(X)=\operatorname {Im} f\subseteq Y$	${\begin{alignedat}{4}f^{-1}(Y)&=X\\f^{-1}(\operatorname {Im} f)&=X\end{alignedat}}$	None
${\begin{alignedat}{4}f(T)&=f(T\cap S~&&\cup ~&&(&&T\setminus S))\\&=f(T\cap S)~&&\cup ~f&&(&&T\setminus S))\end{alignedat}}$	${\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
$\operatorname {Im} f=f(X)~=~f(S)\cup f(X\setminus S)$	${\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
$S\subseteq T$ implies $f(S)\subseteq f(T)$ [8]	$S\subseteq T$ implies $f^{-1}(S)\subseteq f^{-1}(T)$ [8]	None
$f\left(S\right)\subseteq \operatorname {Im} f\subseteq Y$	$f^{-1}\left(S\right)=X$ if and only if $\operatorname {Im} f\subseteq S$	None
$f(S)=\varnothing$ if and only if $S\cap \operatorname {domain} f=\varnothing$	$f^{-1}(S)=\varnothing$ if and only if $S\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$
The following are equivalent: $f\left(S\right)\subseteq f\left(T\right)$ $f\left(S\cup T\right)=f\left(T\right)$ $S\cap \operatorname {domain} f~\subseteq ~f^{-1}\left(f\left(T\right)\right)$	The following are equivalent: $f^{-1}(S)\subseteq f^{-1}(T)$ $f^{-1}(S\cup T)=f^{-1}(T)$ $S\cap \operatorname {Im} f\subseteq T$ If $C~\subseteq ~\operatorname {Im} f$ then $f^{-1}(C)~\subseteq ~f^{-1}(T)$ if and only if $C~\subseteq ~T.$	$C\subseteq \operatorname {Im} f$
The following are equivalent when $C\subseteq Y:$ $C\subseteq f(T)$ $f(B)=C$ for some $B\subseteq T$ $f(B)=C$ for some $B\subseteq T\cap \operatorname {domain} f$	The following are equivalent: $S\subseteq f^{-1}(T)$ $f(S)\subseteq T$ and $S\subseteq \operatorname {domain} f$ The following are equivalent when $A\subseteq X:$ $A\subseteq f^{-1}(T)$ $f(A)\subseteq T$	$A\subseteq X$ and $C\subseteq Y$
The following are equivalent: $f(A)~\supseteq ~f\left(X\setminus A\right)$ $f(A)=\operatorname {Im} f$	The following are equivalent: $f^{-1}(C)~\supseteq ~f^{-1}\left(Y\setminus C\right)$ $f^{-1}(C)=X$	$A\subseteq X$ and $C\subseteq Y$

Also:

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

Images of preimages and preimages of images

Let $S$ and $T$ be arbitrary sets, $f:X\rightarrow 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}(T)\right)=T\cap \operatorname {Im} f$	$f^{-1}(f(T))~\supseteq ~T\cap f^{-1}\left(\operatorname {Im} f\right)=T\cap f^{-1}(Y)$ [8]	None
$f\left(f^{-1}(T)\right)\subseteq T$ [8] Equality holds if and only if the following is true: $T\subseteq \operatorname {Im} f.$ [9][10] Equality holds if any of the following are true: $T\subseteq Y$ and $f:X\to Y$ is surjective.	$f^{-1}(f(A))\supseteq A$ Equality holds if and only if the following is true: $A$ is $f$ -saturated. Equality holds if any of the following are true: $f$ is injective.[9][10]	$A\subseteq X$
$f\left(f^{-1}(Y)\right)=f\left(f^{-1}\left(\operatorname {Im} f\right)\right)=f(X)$	$f^{-1}(f(X))=f^{-1}\left(\operatorname {Im} f\right)=X$	None
$f\left(f^{-1}(T)\cup S\right)~=~\left(T\cap \operatorname {Im} f\right)\cup f(S)~\subseteq ~T\cup f(S)$	$f^{-1}\left(f(A)\cup S\right)~\supseteq ~A\cup f^{-1}(S)$ [11] Equality holds if any of the following are true: $f(A)\subseteq S.$ $A\subseteq f^{-1}(S).$	$A\subseteq X$
$f\left(f^{-1}(T)\cap S\right)=T\cap f(S)$ [8]	$f^{-1}(f(T)\cap S)~\supseteq ~T\cap f^{-1}(S)$	None
$f\left(f^{-1}(f(T))\right)=f(T)$	$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 $\left(S_{i}\right)_{i\in I}$ is a family of arbitrary sets indexed by $I\neq \varnothing$ then:[8]

{\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 $S_{i}$ are $f$ -saturated then $\bigcap _{i\in I}S_{i}$ be will be $f$ -saturated and equality will hold in the last relation above. Explicitly, this means:

f\left(\bigcap _{i\in I}S_{i}\right)~=~\bigcap _{i\in I}f\left(S_{i}\right)

IF

X\cap S_{i}=f^{-1}(f(S_{i}))

for all

i\in I.

(Conditional Equality 10a)

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

f\left(\bigcap _{i\in I}A_{i}\right)~=~\bigcap _{i\in I}f\left(A_{i}\right)

IF

A_{i}=f^{-1}(f(A_{i}))

for all

i\in I.

(Conditional Equality 10b)

Preimage from a Cartesian product

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

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

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

\prod _{j\in J}F_{j}~:~\prod _{j\in J}X~\to ~\prod _{j\in J}Y_{j}

defined by sending

\left(x_{j}\right)_{j\in J}\in \prod _{j\in J}X

to

\left(F_{j}\left(x_{j}\right)\right)_{j\in J}.

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

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

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

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

(Eq. 11a)

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

F^{-1}\left(\prod _{j\in J}B_{j}\right)~=~\bigcap _{j\in J}F_{j}^{-1}\left(B_{j}\right)

(Eq. 11b)

and $\pi _{j}\left(B\right)=B_{j}$ for all $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 $X$ is a family of subsets of $X.$ The power set of a set $X$ is the set of all subsets of $X$ :

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

If ${\mathcal {A}}$ and ${\mathcal {B}}$ are families of sets and if $S$ is any set then define:[12]

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

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

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

{\mathcal {A}}\;(\triangle )\;{\mathcal {B}}~\colon =~\left\{~A\;\triangle \;B~:~A\in {\mathcal {A}}~{\text{ and }}~B\in {\mathcal {B}}~\right\}

{\mathcal {A}}{\big \vert }_{S}~\colon =~\left\{A\cap S~:~A\in {\mathcal {A}}\right\}={\mathcal {A}}\;(\cap )\;\{S\}

which are respectively called elementwise union, elementwise intersection, elementwise (set) difference, elementwise symmetric difference, and the trace/restriction of ${\mathcal {A}}$ to $S.$ The regular union, intersection, and set difference are all defined as usual and are denoted with their usual notation: ${\mathcal {A}}\cup {\mathcal {B}},$ ${\mathcal {A}}\cap {\mathcal {B}},$ ${\mathcal {A}}\;\triangle \;{\mathcal {B}},$ and ${\mathcal {A}}\setminus {\mathcal {B}},$ 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 upward closure in $X$ of a family ${\mathcal {A}}\subseteq \wp (X)$ is the family:

{\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 ${\mathcal {A}}$ is the family:

{\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 ${\mathcal {A}}$ is called isotone, ascending, or upward closed in $X$ if ${\mathcal {A}}\subseteq \wp (X)$ and ${\mathcal {A}}={\mathcal {A}}^{\uparrow X}.$ [12] A family ${\mathcal {A}}$ is called downward closed if ${\mathcal {A}}={\mathcal {A}}^{\downarrow }.$

A family ${\mathcal {A}}$ is called closed under finite intersections (resp. closed under finite unions) if whenever $A,B\in {\mathcal {A}}$ then $A\cap B\in {\mathcal {B}}$ (respectively, $A\cup B\in {\mathcal {B}}$ ). A family ${\mathcal {A}}$ is called a $π$ -system if ${\mathcal {A}}\neq \varnothing$ and ${\mathcal {A}}$ is closed under finite-intersections. Every non-empty family ${\mathcal {A}}$ is contained in a unique smallest (with respect to $\subseteq$ ) $π$ -system that is denoted by $\pi ({\mathcal {A}})$ and called the $π$ -system generated by ${\mathcal {A}}.$ A family ${\mathcal {A}}$ is called a filter subbase and is said to have the finite intersection property if ${\mathcal {A}}\neq \varnothing$ and $\varnothing \not \in \pi ({\mathcal {A}}).$

Basic properties

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

Commutativity:[12]

${\mathcal {A}}\;(\cup )\;{\mathcal {B}}={\mathcal {B}}\;(\cup )\;{\mathcal {A}}$
${\mathcal {A}}\;(\cap )\;{\mathcal {B}}={\mathcal {B}}\;(\cap )\;{\mathcal {A}}$

Associativity:[12]

$[{\mathcal {A}}\;(\cup )\;{\mathcal {B}}]\;(\cup )\;{\mathcal {A}}={\mathcal {A}}\;(\cup )\;[{\mathcal {B}}\;(\cup )\;{\mathcal {C}}]$
$[{\mathcal {A}}\;(\cap )\;{\mathcal {B}}]\;(\cap )\;{\mathcal {A}}={\mathcal {A}}\;(\cap )\;[{\mathcal {B}}\;(\cap )\;{\mathcal {C}}]$

Identity:

${\mathcal {A}}\;(\cup )\;\{\varnothing \}={\mathcal {A}}$
${\mathcal {A}}\;(\cap )\;\{X\}={\mathcal {A}}$
${\mathcal {A}}\;(\setminus )\;\{\varnothing \}={\mathcal {A}}$

Domination:

${\mathcal {A}}\;(\cup )\;\{X\}=\{X\}~~~~{\text{ if }}{\mathcal {A}}\neq \varnothing$
${\mathcal {A}}\;(\cap )\;\{\varnothing \}=\{\varnothing \}~~~~{\text{ if }}{\mathcal {A}}\neq \varnothing$
${\mathcal {A}}\;(\cup )\;\varnothing =\varnothing$
${\mathcal {A}}\;(\cap )\;\varnothing =\varnothing$
${\mathcal {A}}\;(\setminus )\;\varnothing =\varnothing$
$\varnothing \;(\setminus )\;{\mathcal {B}}=\varnothing$

Notes

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

Citations

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

References

Artin, Michael (1991). Algebra. Prentice Hall. ISBN 81-203-0871-9.
Blyth, T.S. (2005). Lattices and Ordered Algebraic Structures. Springer. ISBN 1-85233-905-5..
Courant, Richard, Herbert Robbins, Ian Stewart, What is mathematics?: An Elementary Approach to Ideas and Methods, Oxford University Press US, 1996. ISBN 978-0-19-510519-3. "SUPPLEMENT TO CHAPTER II THE ALGEBRA OF SETS".
Császár, Ákos (1978). General topology. Translated by Császár, Klára. Bristol England: Adam Hilger Ltd. ISBN 0-85274-275-4. OCLC 4146011.
Dixmier, Jacques (1984). General Topology. Undergraduate Texts in Mathematics. Translated by Berberian, S. K. New York: Springer-Verlag. ISBN 978-0-387-90972-1. OCLC 10277303.
Dolecki, Szymon; Mynard, Frederic (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917.
Dugundji, James (1966). Topology. Boston: Allyn and Bacon. ISBN 978-0-697-06889-7. OCLC 395340485.
Halmos, Paul R. (1960). Naive set theory. The University Series in Undergraduate Mathematics. van Nostrand Company. Zbl 0087.04403.
Joshi, K. D. (1983). Introduction to General Topology. New York: John Wiley and Sons Ltd. ISBN 978-0-85226-444-7. OCLC 9218750.
Kelley, John L. (1985). General Topology. Graduate Texts in Mathematics. 27 (2 ed.). Birkhäuser. ISBN 978-0-387-90125-1.
Köthe, Gottfried (1969). Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. 159. Translated by Garling, D.J.H. New York: Springer Science & Business Media. ISBN 978-3-642-64988-2. MR 0248498. OCLC 840293704.
Monk, James Donald (1969). Introduction to Set Theory (PDF). International series in pure and applied mathematics. New York: McGraw-Hill. ISBN 978-0-07-042715-0. OCLC 1102.
Munkres, James R. (2000). Topology (Second ed.). Upper Saddle River, NJ: Prentice Hall, Inc. ISBN 978-0-13-181629-9. OCLC 42683260.
Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.
Schubert, Horst (1968). Topology. London: Macdonald & Co. ISBN 978-0-356-02077-8. OCLC 463753.
Stoll, Robert R.; Set Theory and Logic, Mineola, N.Y.: Dover Publications (1979) ISBN 0-486-63829-4. "The Algebra of Sets", pp 16—23.
Wilansky, Albert (2013). Modern Methods in Topological Vector Spaces. Mineola, New York: Dover Publications, Inc. ISBN 978-0-486-49353-4. OCLC 849801114.
Willard, Stephen (2004) [1970]. General Topology. Dover Books on Mathematics (First ed.). Mineola, N.Y.: Dover Publications. ISBN 978-0-486-43479-7. OCLC 115240.
Munkres, James R. (2000). Topology (Second ed.). Upper Saddle River, NJ: Prentice Hall, Inc. ISBN 978-0-13-181629-9. OCLC 42683260.

External links

Operations on Sets at ProvenMath

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[4] Here "smallest" means relative to subset containment. So if $\Phi$ is any algebra of sets containing ${\mathcal {S}},$ then $\Phi _{\mathcal {S}}\subseteq \Phi .$

[5] Since ${\mathcal {S}}\neq \varnothing ,$ there is some $S\in {\mathcal {S}}_{0}$ such that its complement also belongs to ${\mathcal {S}}_{0}.$ The intersection of these two sets implies that $\varnothing \in {\mathcal {S}}_{1}.$ The union of these two sets is equal to $X,$ which implies that $X\in \Phi _{\mathcal {S}}.$

[DeducingIntersectionOfIntersections-8] To deduce Eq. 2c from Eq. 2a, it must still be shown that $\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).

[9] Let $X\neq \varnothing$ and let $I=\{1,2\}.$ Let $A_{1}\colon =B_{2}\colon =X$ and let $A_{2}\colon =B_{1}\colon =\varnothing .$ Then $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 .$

[10] 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 $\{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 $S_{11}$ and $S_{21}$ are swapped while $S_{12}$ and $S_{22}$ are unchanged, which gives rise to the sets ${\hat {S}}_{11}:=S_{21}=\{3,4\},~$ ${\hat {S}}_{12}:=\{1,3\},~$ ${\hat {S}}_{21}:=S_{11}=\{1,2\},~$ and ${\hat {S}}_{22}:=\{2,4\},~$ then $\{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 $\{1,4\},$ which shows that the left hand side $\bigcup _{i\in I}\left(\bigcap _{j\in J}S_{i,j}\right)$ depends on how the sets are labelled. Had instead $S_{11}$ and $S_{12}$ been swapped (with $S_{21}$ and $S_{22}$ unchanged) then both the left hand side and right hand side would have been equal to $\{1,4\},$ which shows that both sides depend on how the sets are labeled.

[11] So, for instance, it's even possible that $S\cap (X\cup Y)=\varnothing ,$ or that $S\cap X\neq \varnothing$ and $S\cap Y\neq \varnothing$ (which happens, for instance, if $X=Y$ ), etc.

[Depends_only_on_T-14] Note that this condition $T\cap \operatorname {domain} f=f^{-1}\left(f(T)\right)$ depends entirely on $T$ and not on $S.$

[16] $f\left(X\setminus T\right)~\supseteq ~Y\setminus f(T)$ can be rewritten as: $f\left(T^{\operatorname {C} }\right)~\supseteq ~f\left(T\right)^{\operatorname {C} }.$

[17] The conclusion $X\setminus f^{-1}(S)=f^{-1}\left(Y\setminus S\right)$ can also be written as: $f^{-1}(T)^{\operatorname {C} }~=~f^{-1}\left(T^{\operatorname {C} }\right).$

[Taylor_2019-1] Taylor, Courtney (March 31, 2019). "What Is Symmetric Difference in Math?". ThoughtCo. Retrieved 2020-09-05.

[Weisstein_2020-2] Weisstein, Eric W. "Symmetric Difference". mathworld.wolfram.com. Retrieved 2020-09-05.

[Encyclopedia_of_math-3] "Algebra of sets". Encyclopediaofmath.org. 16 August 2013. Retrieved 8 November 2020.

[FOOTNOTEMonk196924-54-6] Monk 1969, pp. 24-54.

[FOOTNOTECsászár197815-26-7] Császár 1978, pp. 15-26.

[kelley-1985-12] Kelley 1985, p. 85

[munkres-2000-p21-13] See Munkres 2000, p. 21

[FOOTNOTECsászár1978102-120-15] Császár 1978, pp. 102-120.

[halmos-1960-p39-18] See Halmos 1960, p. 39

[munkres-2000-p19-19] See Munkres 2000, p. 19

[lee-2010-p388-20] See p.388 of Lee, John M. (2010). Introduction to Topological Manifolds, 2nd Ed.

[FOOTNOTECsászár197853-65-21] Császár 1978, pp. 53-65.

List of set identities and relations

Notation

Algebra of sets

Basic set relationships

Complements

Subset inclusion

Multiple set operations

Expressing basic set operations

Identities involving two set operations

Arbitrary families of sets

Definitions

Commutativity and associativity

Binary intersection of arbitrary unions

Binary union of arbitrary intersections

Arbitrary intersections and arbitrary unions

Distributing subtraction

Distributing products

Maps and sets

Definitions

Finitely many sets

Arbitrarily many sets

Families of sets

Definitions

Basic properties

See also

Notes

Citations

References

External links