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,L,M,R,S,$ 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 $L$ will be denoted by $L^{C}$ where unless indicated otherwise, it should be assumed that $L^{C}$ denotes the complement of $L$ in (the universe) $X.$

Typically, the set $L$ will denote the L eft most set, $M$ the M iddle set, and $R$ the R ight most set.

For sets $L$ and $R,$ define:

{\begin{alignedat}{4}L\cup R&&~:=~\{~x~:~x\in L\;&&{\text{ or }}\;\,&&\;x\in R~\}\\L\cap R&&~:=~\{~x~:~x\in L\;&&{\text{ and }}&&\;x\in R~\}\\L\setminus R&&~:=~\{~x~:~x\in L\;&&{\text{ and }}&&\;x\notin R~\}\\\end{alignedat}}

and

L\triangle R~:=~\{~x~:~x{\text{ belongs to exactly one of }}L{\text{ and }}R~\}.

The symmetric difference of $L$ and $R$ is:[1][2]

{\begin{alignedat}{4}L\;\triangle \;R~&=~(L~\setminus ~&&R)~\cup ~&&(R~\setminus ~&&L)\\~&=~(L~\cup ~&&R)~\setminus ~&&(L~\cap ~&&R).\end{alignedat}}

If $L$ is a set that is understood (say from context, or because it is clearly stated) to be a subset of some other set $X$ then the complement of a set $L$ may be denoted by:

L^{\operatorname {C} }~:=~X\setminus L.

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

Finitely many sets and the 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 $L,R\in \Phi ,$ all three of the sets $X\setminus R,\,L\cap R,$ and $L\cup R$ 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 it will be denote it by $\Phi _{\mathcal {S}}.$ This algebra can be constructed as follows:[3]

If ${\mathcal {S}}=\varnothing$ then $\Phi _{\mathcal {S}}=\{\varnothing ,X\}$ and we are done. Alternatively, if ${\mathcal {S}}$ is empty then ${\mathcal {S}}$ may be replaced with $\{\varnothing \},\{X\},{\text{ or }}\{\varnothing ,X\}$ 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}.$

One subset involved

Assume $L\subseteq X.$

Identity:[4]

{\begin{alignedat}{10}L\cap X&\;=\;&&L~~~~{\text{ where }}L\subseteq X\\[1.4ex]L\cup \varnothing &\;=\;&&L\\[1.4ex]L\,\triangle \varnothing &\;=\;&&L\\[1.4ex]L\setminus \varnothing &\;=\;&&L\\[1.4ex]X\cap L&\;=\;&&L~~~~{\text{ where }}L\subseteq X\\[1.4ex]\varnothing \cup L&\;=\;&&L\\[1.4ex]\varnothing \,\triangle L&\;=\;&&L\\[1.4ex]\end{alignedat}}

but

\varnothing \setminus L=\varnothing

so ${\textstyle \varnothing \setminus L=L{\text{ if and only if }}L=\varnothing .}$

Idempotence[4] and Nilpotence:

{\begin{alignedat}{10}L\cup L&\;=\;&&L&&\quad {\text{ (Idempotence)}}\\[1.4ex]L\cap L&\;=\;&&L&&\quad {\text{ (Idempotence)}}\\[1.4ex]L\,\triangle \,L&\;=\;&&\varnothing &&\quad {\text{ (Nilpotence of index 2)}}\\[1.4ex]L\setminus L&\;=\;&&\varnothing &&\quad {\text{ (Nilpotence of index 2)}}\\[1.4ex]\end{alignedat}}

Domination:[4]

{\begin{alignedat}{10}X\cup L&\;=\;&&X~~~~{\text{ where }}L\subseteq X\\[1.4ex]\varnothing \cap L&\;=\;&&\varnothing \\[1.4ex]\varnothing \times L&\;=\;&&\varnothing \\[1.4ex]\varnothing \setminus L&\;=\;&&\varnothing \\[1.4ex]L\cup X&\;=\;&&X~~~~{\text{ where }}L\subseteq X\\[1.4ex]L\cap \varnothing &\;=\;&&\varnothing \\[1.4ex]L\times \varnothing &\;=\;&&\varnothing \\[1.4ex]\end{alignedat}}

but

L\setminus \varnothing =L

so ${\textstyle L\setminus \varnothing =\varnothing {\text{ if and only if }}L=\varnothing .}$

Double complement or involution law:

{\begin{alignedat}{10}X\setminus (X\setminus L)&=L&&\qquad {\text{ Also written }}\quad &&\left(L^{C}\right)^{C}=L&&\quad &&{\text{ where }}L\subseteq X\quad {\text{ (Double complement/Involution law)}}\\[1.4ex]\end{alignedat}}

L\setminus \varnothing =L

{\begin{alignedat}{4}\varnothing &=L&&\setminus L\\&=\varnothing &&\setminus L\\&=L&&\setminus X~~~~{\text{ where }}L\subseteq X\\\end{alignedat}}

[4]

L^{C}=X\setminus L\quad {\text{ (definition of notation)}}

{\begin{alignedat}{10}L\,\cup (X\setminus L)&=X&&\qquad {\text{ Also written }}\quad &&L\cup L^{C}=X&&\quad &&{\text{ where }}L\subseteq X\\[1.4ex]L\,\triangle (X\setminus L)&=X&&\qquad {\text{ Also written }}\quad &&L\,\triangle L^{C}=X&&\quad &&{\text{ where }}L\subseteq X\\[1.4ex]L\,\cap (X\setminus L)&=\varnothing &&\qquad {\text{ Also written }}\quad &&L\cap L^{C}=\varnothing &&\quad &&\\[1.4ex]\end{alignedat}}

[4]

{\begin{alignedat}{10}X\setminus \varnothing &=X&&\qquad {\text{ Also written }}\quad &&\varnothing ^{C}=X&&\quad &&{\text{ (Complement laws for the empty set))}}\\[1.4ex]X\setminus X&=\varnothing &&\qquad {\text{ Also written }}\quad &&X^{C}=\varnothing &&\quad &&{\text{ (Complement laws for the universe set)}}\\[1.4ex]\end{alignedat}}

Other properties:

If $L$ is any set then the following are equivalent:

$L$ is not empty ( $L\neq \varnothing$ ), meaning: $\lnot [\forall x(x\not \in L)]$
(In classical mathematics) $L$ $\text{[math]}$ is inhabited, meaning: $\exists x(x\in L)$ $\text{[math]}$
- In constructive mathematics, "not empty" and "inhabited" are not equivalent: every inhabited set is not empty but the converse is not always guaranteed; that is, in constructive mathematics, a set $L$ that is not empty (where by definition, " $L$ is empty" means that the statement $\forall x(x\not \in L)$ is true) might not have an inhabitant (which is an $x$ such that $x\in L$ ).
$L\not \subseteq R$ for some set $R$

If $L$ is any set then the following are equivalent:

$L$ is empty ( $L=\varnothing$ ), meaning: $\forall x(x\not \in L)$
$L\cup R\subseteq R$ for every set $R$
$L\subseteq R$ for every set $R$
$L\subseteq R\setminus L$ for some/every set $R$
$\varnothing /L=L$

Two sets involved

In the left hand sides of the following identities, $L$ is the L eft most set and $R$ is the R ight most set. Assume both $L{\text{ and }}R$ are subsets of some universe set $X.$

Elementary operations characterized

In the left hand sides of the following identities, $L$ is the L eft most set and $R$ is the R ight most set. Whenever necessary, both $L{\text{ and }}R$ should be assumed to be subsets of some universe set $X,$ so that $L^{C}:=X\setminus L{\text{ and }}R^{C}:=X\setminus R.$

{\begin{alignedat}{9}L\cap R&=L&&\,\,\setminus \,&&(L&&\,\,\setminus &&R)\\&=R&&\,\,\setminus \,&&(R&&\,\,\setminus &&L)\\&=L&&\,\,\setminus \,&&(L&&\,\triangle \,&&R)\\&=L&&\,\triangle \,&&(L&&\,\,\setminus &&R)\\\end{alignedat}}

{\begin{alignedat}{9}L\cup R&=(&&L\,\triangle \,R)&&\,\,\cup &&&&L&&&&\\&=(&&L\,\triangle \,R)&&\,\triangle \,&&(&&L&&\cap \,&&R)\\&=(&&R\,\setminus \,L)&&\,\,\cup &&&&L&&&&~~~~~{\text{ (union is disjoint)}}\\\end{alignedat}}

{\begin{alignedat}{9}L\,\triangle \,R&=&&R\,\triangle \,L&&&&&&&&\\&=(&&L\,\cup \,R)&&\,\setminus \,&&(&&L\,\,\cap \,R)&&\\&=(&&L\,\setminus \,R)&&\cup \,&&(&&R\,\,\setminus \,L)&&~~~~~{\text{ (union is disjoint)}}\\&=(&&L\,\triangle \,M)&&\,\triangle \,&&(&&M\,\triangle \,R)&&~~~~~{\text{ where }}M{\text{ is an arbitrary set. }}\\&=(&&L^{C})&&\,\triangle \,&&(&&R^{C})&&\\\end{alignedat}}

{\begin{alignedat}{9}L\setminus R&=&&L&&\,\,\setminus &&(L&&\,\,\cap &&R)\\&=&&L&&\,\,\cap &&(L&&\,\triangle \,&&R)\\&=&&L&&\,\triangle \,&&(L&&\,\,\cap &&R)\\&=&&R&&\,\triangle \,&&(L&&\,\,\cup &&R)\\\end{alignedat}}

Properties involving two sets

De Morgan's laws:

For $L,R\subseteq X:$

{\begin{alignedat}{10}X\setminus (L\cap R)&=(X\setminus L)\cup (X\setminus R)&&\qquad {\text{ Also written }}\quad &&(L\cap R)^{C}=L^{C}\cup R^{C}&&\quad &&{\text{ (De Morgan's law)}}\\[1.4ex]X\setminus (L\cup R)&=(X\setminus L)\cap (X\setminus R)&&\qquad {\text{ Also written }}\quad &&(L\cup R)^{C}=L^{C}\cap R^{C}&&\quad &&{\text{ (De Morgan's law)}}\\[1.4ex]\end{alignedat}}

Absorption laws:

{\begin{alignedat}{4}L\cup (L\cap R)&\;=\;&&L&&\quad {\text{ (Absorption)}}\\[1.4ex]L\cap (L\cup R)&\;=\;&&L&&\quad {\text{ (Absorption)}}\\[1.4ex]\end{alignedat}}

Commutativity:[4]

{\begin{alignedat}{10}L\cup R&\;=\;&&R\cup L&&\quad {\text{ (Commutativity)}}\\[1.4ex]L\cap R&\;=\;&&R\cap L&&\quad {\text{ (Commutativity)}}\\[1.4ex]L\,\triangle R&\;=\;&&R\,\triangle L&&\quad {\text{ (Commutativity)}}\\[1.4ex]\end{alignedat}}

Set subtraction is not commutative. However, the commutativity of set subtraction can be characterized: from $(L\,\setminus \,R)\cap (R\,\setminus \,L)=\varnothing$ it follows that:

L\,\setminus \,R=R\,\setminus \,L\quad {\text{ if and only if }}\quad L=R.

Said differently, if distinct symbols always represented distinct sets, then the only true formulas of the form $\,\cdot \,\,\setminus \,\,\cdot \,=\,\cdot \,\,\setminus \,\,\cdot \,$ that could be written would be those involving a single symbol; that is, those of the form: $S\,\setminus \,S=S\,\setminus \,S.$ But such formulas are necessarily true for every binary operation $\,\ast \,$ (because $x\,\ast \,x=x\,\ast \,x$ must hold by definition of equality), and so in this sense, set subtraction is as diametrically opposite to being commutative as is possible for a binary operation. Set subtraction is also neither left alternative nor right alternative; instead, $(L\setminus L)\setminus R=L\setminus (L\setminus R)$ if and only if $L\cap R=\varnothing$ if and only if $(R\setminus L)\setminus L=R\setminus (L\setminus L).$ Set subtraction is quasi-commutative and satisfies the Jordan identity.

Other properties

{\begin{alignedat}{10}L\setminus R&=L\cap (X\setminus R)&&\qquad {\text{ Also written }}\quad &&L\setminus R=L\cap R^{C}&&\quad &&{\text{ where }}L,R\subseteq X\\[1.4ex]X\setminus (L\setminus R)&=(X\setminus L)\cup R&&\qquad {\text{ Also written }}\quad &&(L\setminus R)^{C}=L^{C}\cup R&&\quad &&{\text{ where }}R\subseteq X\\[1.4ex]L\setminus R&=(X\setminus R)\setminus (X\setminus L)&&\qquad {\text{ Also written }}\quad &&L\setminus R=R^{C}\setminus L^{C}&&\quad &&{\text{ where }}L,R\subseteq X\\[1.4ex]\end{alignedat}}

{\text{If }}L\cup R=X{\text{ and }}L\cap R=\varnothing \;{\text{ then }}\;R=X\setminus L\qquad {\text{ (Uniqueness of complements)}}

Given any $x,$ $\quad x\not \in L\setminus R\quad {\text{ if and only if }}\quad x\in L\cap R{\text{ or }}x\not \in L.$
If $L\cap R=\varnothing$ then $L=R{\text{ if and only if }}L=\varnothing =R.$
If $L\subseteq R$ $\text{[math]}$ then:
- $L\,\triangle \,R=R\setminus L$

The following statements are equivalent:

$L=R$
$L\,\triangle \,R=\varnothing$
$L\,\setminus \,R=R\,\setminus \,L$

Subset inclusion

The following statements are equivalent for any $L,R\subseteq X:$ [4]

$L\subseteq R$
$L\cap R=L$
$L\cup R=R$
$L\,\triangle \,R=R\setminus L$
$L\,\triangle \,R\subseteq R\setminus L$
$L\setminus R=\varnothing$
$X\setminus R\subseteq X\setminus L\qquad$ (that is, $R^{C}\subseteq L^{C}$ )

The following statements are equivalent for any $L,R\subseteq X:$

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

Meets, Joint, and lattice properties

Inclusion is a partial order: Explicitly, this means that inclusion $\,\subseteq ,\,$ which is a binary operation, has the following three properties:[4]

Reflexivity: ${\textstyle L\subseteq L}$
Antisymmetry: ${\textstyle (L\subseteq R{\text{ and }}R\subseteq L){\text{ if and only if }}L=R}$
Transitivity: ${\textstyle {\text{If }}L\subseteq M{\text{ and }}M\subseteq R{\text{ then }}L\subseteq R}$

The following proposition says that for any set $S,$ the power set of $S,$ ordered by inclusion, is a bounded lattice, and hence together with the distributive and complement laws above, show that it is a Boolean algebra.

Existence of a least element and a greatest element:

\varnothing \subseteq L\subseteq X

Joins/supremums exist:[4]

L\subseteq L\cup R

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

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

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

Meets/infimums exist:[4]

L\cap R\subseteq L

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

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

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

Other inclusion properties:

L\setminus R\subseteq L

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

(L\setminus R)\cap R=\varnothing

If $L\subseteq X$ and $R\subseteq Y$ then $L\times R\subseteq X\times Y$ [4]
$x\not \in L\setminus R$ if and only if $x\not \in L$ or $x\in L\cap R$

Three sets involved

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.

Precedence rules

There is no universal agreement on the order of precedence of the basic set operators. Nevertheless, many authors use precedence rules for set operators, although these rules vary with the author.

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

Sometimes, set complement (subtraction) $\,\setminus \,$ is also associated with logical complement (not) $\,\lnot ,\,$ in which case it will have the highest precedence. More specifically, $L\setminus R=\{x:(x\in L)\land \lnot (x\in R)\}$ is rewritten $L\land \lnot R$ so that for example, $L\cup M\setminus R$ would mean $L\cup (M\setminus R)$ since it would be rewritten as the logical statement $L\lor M\land \lnot R$ which is equal to $L\lor (M\land \lnot R).$ For another example, because $L\land \lnot M\land R$ means $L\land (\lnot M)\land R,$ which is equal to both $(L\land (\lnot M))\land R$ and $L\land ((\lnot M)\land R)~=~L\land (R\land (\lnot M))$ (where $(\lnot M)\land R$ was rewritten as $R\land (\lnot M)$ ), the formula $L\setminus M\cap R$ would refer to the set $(L\setminus M)\cap R=L\cap (R\setminus M);$ moreover, since $L\land (\lnot M)\land R=(L\land R)\land \lnot M,$ this set is also equal to $(L\cap R)\setminus M$ (other set identities can similarly be deduced from propositional calculus identities in this way). However, because set subtraction is not associative $(L\setminus M)\setminus R\neq L\setminus (M\setminus R),$ a formula such as $L\setminus M\setminus R$ would be ambiguous; for this reason, among others, set subtraction is often not assigned any precedence at all.

Symmetric difference $L\triangle R=\{x:(x\in L)\oplus (x\in R)\}$ is sometimes associated with exclusive or (xor) $L\oplus R$ (also sometimes denoted by $\,\veebar$ ), in which case if the order of precedence from highest to lowest is $\,\lnot ,\,\oplus ,\,\land ,\,\lor \,$ then the order of precedence (from highest to lowest) for the set operators would be $\,\setminus ,\,\triangle ,\,\cap ,\,\cup .$ There is no universal agreement on the precedence of exclusive disjunction $\,\oplus \,$ with respect to the other logical connectives, which is why symmetric difference $\,\triangle \,$ is not often assigned a precedence.

Associativity

Definition: A binary operator $\,\ast \,$ is called associative if $(L\,\ast \,M)\,\ast \,R=L\,\ast \,(M\,\ast \,R)$ always holds.

The following set operators are associative:[4]

{\begin{alignedat}{5}(L\cup M)\cup R&\;=\;\;&&L\cup (M\cup R)\\[1.4ex](L\cap M)\cap R&\;=\;\;&&L\cap (M\cap R)\\[1.4ex](L\,\triangle M)\,\triangle R&\;=\;\;&&L\,\triangle (M\,\triangle R)\\[1.4ex]\end{alignedat}}

For set subtraction, instead of associativity, only the following is always guaranteed:

(L\,\setminus \,M)\,\setminus \,R\;~~{\color {red}{\subseteq }}~~\;L\,\setminus \,(M\,\setminus \,R)

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

Distributivity

Definition: If $\ast {\text{ and }}\bullet$ are binary operators then $\,\ast \,$ left distributes over $\,\bullet \,$ if

L\,\ast \,(M\,\bullet \,R)~=~(L\,\ast \,M)\,\bullet \,(L\,\ast \,R)\qquad \qquad {\text{ for all }}L,M,R

while $\,\ast \,$ right distributes over $\,\bullet \,$ if

(L\,\bullet \,M)\,\ast \,R~=~(L\,\ast \,R)\,\bullet \,(M\,\ast \,R)\qquad \qquad {\text{ for all }}L,M,R.

The operator $\,\ast \,$ distributes over $\,\bullet \,$ if it both left distributes and right distributes over $\,\bullet \,.\,$ In the definitions above, to transform one side to the other, the innermost operator (the operator inside the parentheses) becomes the outermost operator and the outermost operator becomes the innermost operator.

Right distributivity:[4]

{\begin{alignedat}{9}(L\,\cap \,M)\,\cup \,R~&~~=~~&&(L\,\cup \,R)\,&&\cap \,&&(M\,\cup \,R)\qquad &&{\text{ (Right-distributivity of }}\,\cup \,{\text{ over }}\,\cap \,{\text{)}}\\[1.4ex](L\,\cup \,M)\,\cup \,R~&~~=~~&&(L\,\cup \,R)\,&&\cup \,&&(M\,\cup \,R)\qquad &&{\text{ (Right-distributivity of }}\,\cup \,{\text{ over }}\,\cup \,{\text{)}}\\[1.4ex](L\,\cup \,M)\,\cap \,R~&~~=~~&&(L\,\cap \,R)\,&&\cup \,&&(M\,\cap \,R)\qquad &&{\text{ (Right-distributivity of }}\,\cap \,{\text{ over }}\,\cup \,{\text{)}}\\[1.4ex](L\,\cap \,M)\,\cap \,R~&~~=~~&&(L\,\cap \,R)\,&&\cap \,&&(M\,\cap \,R)\qquad &&{\text{ (Right-distributivity of }}\,\cap \,{\text{ over }}\,\cap \,{\text{)}}\\[1.4ex](L\,\triangle \,M)\,\cap \,R~&~~=~~&&(L\,\cap \,R)\,&&\triangle \,&&(M\,\cap \,R)\qquad &&{\text{ (Right-distributivity of }}\,\cap \,{\text{ over }}\,\triangle \,{\text{)}}\\[1.4ex](L\,\cap \,M)\,\times \,R~&~~=~~&&(L\,\times \,R)\,&&\cap \,&&(M\,\times \,R)\qquad &&{\text{ (Right-distributivity of }}\,\times \,{\text{ over }}\,\cap \,{\text{)}}\\[1.4ex](L\,\cup \,M)\,\times \,R~&~~=~~&&(L\,\times \,R)\,&&\cup \,&&(M\,\times \,R)\qquad &&{\text{ (Right-distributivity of }}\,\times \,{\text{ over }}\,\cup \,{\text{)}}\\[1.4ex](L\,\setminus \,M)\,\times \,R~&~~=~~&&(L\,\times \,R)\,&&\setminus \,&&(M\,\times \,R)\qquad &&{\text{ (Right-distributivity of }}\,\times \,{\text{ over }}\,\setminus \,{\text{)}}\\[1.4ex](L\,\cup \,M)\,\setminus \,R~&~~=~~&&(L\,\setminus \,R)\,&&\cup \,&&(M\,\setminus \,R)\qquad &&{\text{ (Right-distributivity of }}\,\setminus \,{\text{ over }}\,\cup \,{\text{)}}\\[1.4ex](L\,\cap \,M)\,\setminus \,R~&~~=~~&&(L\,\setminus \,R)\,&&\cap \,&&(M\,\setminus \,R)\qquad &&{\text{ (Right-distributivity of }}\,\setminus \,{\text{ over }}\,\cap \,{\text{)}}\\[1.4ex](L\,\triangle \,M)\,\setminus \,R~&~~=~~&&(L\,\setminus \,R)&&\,\triangle \,&&(M\,\setminus \,R)\qquad &&{\text{ (Right-distributivity of }}\,\setminus \,{\text{ over }}\,\triangle \,{\text{)}}\\[1.4ex](L\,\setminus \,M)\,\setminus \,R~&~~=~~&&(L\,\setminus \,R)&&\,\setminus \,&&(M\,\setminus \,R)\qquad &&{\text{ (Right-distributivity of }}\,\setminus \,{\text{ over }}\,\setminus \,{\text{)}}\\[1.4ex]~&~~=~~&&~~\;~~\;~~\;~L&&\,\setminus \,&&(M\cup R)\\[1.4ex]\end{alignedat}}

Left distributivity:[4]

{\begin{alignedat}{5}L\cup (M\cap R)&\;=\;\;&&(L\cup M)\cap (L\cup R)\qquad &&{\text{ (Left-distributivity of }}\,\cup \,{\text{ over }}\,\cap \,{\text{)}}\\[1.4ex]L\cup (M\cup R)&\;=\;\;&&(L\cup M)\cup (L\cup R)&&{\text{ (Left-distributivity of }}\,\cup \,{\text{ over }}\,\cup \,{\text{)}}\\[1.4ex]L\cap (M\cup R)&\;=\;\;&&(L\cap M)\cup (L\cap R)&&{\text{ (Left-distributivity of }}\,\cap \,{\text{ over }}\,\cup \,{\text{)}}\\[1.4ex]L\cap (M\cap R)&\;=\;\;&&(L\cap M)\cap (L\cap R)&&{\text{ (Left-distributivity of }}\,\cap \,{\text{ over }}\,\cap \,{\text{)}}\\[1.4ex]L\cap (M\,\triangle \,R)&\;=\;\;&&(L\cap M)\,\triangle \,(L\cap R)&&{\text{ (Left-distributivity of }}\,\cap \,{\text{ over }}\,\triangle \,{\text{)}}\\[1.4ex]L\times (M\cap R)&\;=\;\;&&(L\times M)\cap (L\times R)&&{\text{ (Left-distributivity of }}\,\times \,{\text{ over }}\,\cap \,{\text{)}}\\[1.4ex]L\times (M\cup R)&\;=\;\;&&(L\times M)\cup (L\times R)&&{\text{ (Left-distributivity of }}\,\times \,{\text{ over }}\,\cup \,{\text{)}}\\[1.4ex]L\times (M\,\setminus R)&\;=\;\;&&(L\times M)\,\setminus (L\times R)&&{\text{ (Left-distributivity of }}\,\times \,{\text{ over }}\,\setminus \,{\text{)}}\\[1.4ex]\end{alignedat}}

Failure of set subtraction to left distribute:

Set subtraction is right distributive over itself. However, set subtraction is not left distributive over itself because only the following is guaranteed in general:

{\begin{alignedat}{5}L\,\setminus \,(M\,\setminus \,R)&~~{\color {red}{\supseteq }}~~&&\color {black}{\,}(L\,\setminus \,M)\,\setminus \,(L\,\setminus \,R)~~=~~L\cap R\,\setminus \,M\\[1.4ex]\end{alignedat}}

where equality holds if and only if $L\,\setminus \,M=L\,\cap \,R,$ which happens if and only if $L\cap M\cap R=\varnothing {\text{ and }}L\setminus M\subseteq R.$

For symmetric difference, the sets $L\,\setminus \,(M\,\triangle \,R)$ and $(L\,\setminus \,M)\,\triangle \,(L\,\setminus \,R)=L\,\cap \,(M\,\triangle \,R)$ are always disjoint. So these two sets are equal if and only if they are both equal to $\varnothing .$ Moreover, $L\,\setminus \,(M\,\triangle \,R)=\varnothing$ if and only if $L\cap M\cap R=\varnothing {\text{ and }}L\subseteq M\cup R.$

To investigate the left distributivity of set subtraction over unions or intersections, consider how the sets involved in (both of) De Morgan's laws are all related:

{\begin{alignedat}{5}(L\,\setminus \,M)\,\cap \,(L\,\setminus \,R)~~=~~L\,\setminus \,(M\,\cup \,R)~&~~{\color {red}{\subseteq }}~~&&\color {black}{\,}L\,\setminus \,(M\,\cap \,R)~~=~~(L\,\setminus \,M)\,\cup \,(L\,\setminus \,R)\\[1.4ex]\end{alignedat}}

always holds in general but equality is not guaranteed. Equality holds if and only if $L\,\setminus \,(M\,\cap \,R)\;\subseteq \;L\,\setminus \,(M\,\cup \,R),$ which happens if and only if $L\,\cap \,M=L\,\cap \,R.$

This observation about De Morgan's laws shows that $\,\setminus \,$ is not left distributive over $\,\cup \,$ or $\,\cap \,$ because only the following are guaranteed in general:

{\begin{alignedat}{5}L\,\setminus \,(M\,\cup \,R)~&~~{\color {red}{\subseteq }}~~&&\color {black}{\,}(L\,\setminus \,M)\,\cup \,(L\,\setminus \,R)~~=~~L\,\setminus \,(M\,\cap \,R)\\[1.4ex]\end{alignedat}}

{\begin{alignedat}{5}L\,\setminus \,(M\,\cap \,R)~&~~{\color {red}{\supseteq }}~~&&\color {black}{\,}(L\,\setminus \,M)\,\cap \,(L\,\setminus \,R)~~=~~L\,\setminus \,(M\,\cup \,R)\\[1.4ex]\end{alignedat}}

where equality holds for one (or equivalently, for both) of the above two inclusion formulas if and only if $L\,\cap \,M=L\,\cap \,R.$

The following statements are equivalent:

$L\cap M\,=\,L\cap R$
$L\,\setminus \,M\,=\,L\,\setminus \,R$
$L\,\setminus \,(M\,\cap \,R)=(L\,\setminus \,M)\,\cap \,(L\,\setminus \,R);$ that is, $\,\setminus \,$ left distributes over $\,\cap \,$ for these three particular sets
$L\,\setminus \,(M\,\cup \,R)=(L\,\setminus \,M)\,\cup \,(L\,\setminus \,R);$ that is, $\,\setminus \,$ left distributes over $\,\cup \,$ for these three particular sets
$L\,\setminus \,(M\,\cap \,R)\,=\,L\,\setminus \,(M\,\cup \,R)$
$L\cap (M\cup R)\,=\,L\cap M\cap R$
$L\cap (M\cup R)~\subseteq ~M\cap R$
$L\cap R~\subseteq ~M\;$ and $\;L\cap M~\subseteq ~R$
$L\setminus (M\setminus R)\,=\,L\setminus (R\setminus M)$
$L\setminus (M\setminus R)\,=\,L\setminus (R\setminus M)\,=\,L$

Quasi-commutativity:

(L\setminus M)\setminus R~=~(L\setminus R)\setminus M\qquad {\text{ (Quasi-commutative)}}

always holds but in general,

L\setminus (M\setminus R)~~{\color {red}{\neq }}~~L\setminus (R\setminus M).

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

Distributivity and symmetric difference:

Intersection distributes over symmetric difference:

{\begin{alignedat}{5}L\,\cap \,(M\,\triangle \,R)~&~~=~~&&(L\,\cap \,M)\,\triangle \,(L\,\cap \,R)~&&~\\[1.4ex]\end{alignedat}}

{\begin{alignedat}{5}(L\,\triangle \,M)\,\cap \,R~&~~=~~&&(L\,\cap \,R)\,\triangle \,(M\,\cap \,R)~&&~\\[1.4ex]\end{alignedat}}

Union does not distribute over symmetric difference because only the following is guaranteed in general:

{\begin{alignedat}{5}L\cup (M\,\triangle \,R)~~{\color {red}{\supseteq }}~~\color {black}{\,}(L\cup M)\,\triangle \,(L\cup R)~&~=~&&(M\,\triangle \,R)\,\setminus \,L&~=~&&(M\,\setminus \,L)\,\triangle \,(R\,\setminus \,L)\\[1.4ex]\end{alignedat}}

Symmetric difference does not distribute over itself:

L\,\triangle \,(M\,\triangle \,R)~~{\color {red}{\neq }}~~\color {black}{\,}(L\,\triangle \,M)\,\triangle \,(L\,\triangle \,R)~=~M\,\triangle \,R

and in general, for any sets $L{\text{ and }}A$ (where $A$ represents $M\,\triangle \,R$ ), $L\,\triangle \,A$ might not be a subset, nor a superset, of $L$ (and the same is true for $A$ ).

Set subtraction complexity: To manage the many identities involving set subtraction, this section is divided based on where the set subtraction operation and parentheses are located on the left hand side of the identity. The great variety and (relative) complexity of formulas involving set subtraction (compared to those without it) is in part due to the fact that unlike $\,\cup ,\,\cap ,$ and $\triangle ,\,$ set subtraction is neither associative nor commutative and it also is not left distributive over $\,\cup ,\,\cap ,\,\triangle ,$ or even over itself.

Both operators are set subtraction

{\begin{alignedat}{4}(L\setminus M)\setminus R&=&&L\setminus (M\cup R)\\[0.6ex]&=(&&L\setminus R)\setminus M\\[0.6ex]&=(&&L\setminus M)\cap (L\setminus R)\\[0.6ex]&=(&&L\setminus R)\setminus M\\[0.6ex]&=(&&L\,\setminus \,R)\,\setminus \,(M\,\setminus \,R)\\[1.4ex]\end{alignedat}}

{\begin{alignedat}{4}L\setminus (M\setminus R)&=(L\setminus M)\cup (L\cap R)\\[1.4ex]\end{alignedat}}

If $L\subseteq M{\text{ then }}L\setminus (M\setminus R)=L\cap R$
${\textstyle L\setminus (M\setminus R)\subseteq (L\setminus M)\cup R}$ with equality if and only if $R\subseteq L.$

Set subtraction on the left

Parentheses on the left

{\begin{alignedat}{4}\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}{4}(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}{4}(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}}

(L\,\setminus M)\times R=(L\times R)\,\setminus (M\times R)~~~~~{\text{ (Distributivity)}}

Parentheses on the right

{\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}{4}L\setminus (M\cap R)&=(L\setminus M)\cup (L\setminus R)~~~~{\text{ (De Morgan's law) }}\\\end{alignedat}}

{\begin{alignedat}{4}L\setminus (M~\triangle ~R)&=(L\setminus (M\cup R))\cup (L\cap M\cap R)~~~{\text{ (the outermost union is disjoint) }}\\\end{alignedat}}

Set subtraction on the right

Parentheses on the left

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

{\begin{alignedat}{4}(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}{4}(L\,\triangle \,M)\setminus R&=(L\setminus R)~&&\triangle ~(M\setminus R)\\&=(L\cup R)~&&\triangle ~(M\cup R)\\\end{alignedat}}

Parentheses on the right

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

L\times (M\,\setminus R)=(L\times M)\,\setminus (L\times R)~~~~~{\text{ (Distributivity)}}

Three operators

Operations of the form $(L\bullet M)\ast (M\bullet R)$ :

{\begin{alignedat}{9}(L\cup M)&\,\cup \,&&(&&M\cup R)&&&&\;=\;\;&&L\cup M\cup R\\[1.4ex](L\cup M)&\,\cap \,&&(&&M\cup R)&&&&\;=\;\;&&M\cap (L\cup R)\\[1.4ex](L\cup M)&\,\setminus \,&&(&&M\cup R)&&&&\;=\;\;&&L\,\setminus \,(M\cup R)\\[1.4ex](L\cup M)&\,\triangle \,&&(&&M\cup R)&&&&\;=\;\;&&(L\,\setminus \,(M\cup R))\,\cup \,(R\,\setminus \,(L\cup M))\\[1.4ex]&\,&&\,&&\,&&&&\;=\;\;&&(L\,\triangle \,R)\,\setminus \,M\\[1.4ex](L\cap M)&\,\cup \,&&(&&M\cap R)&&&&\;=\;\;&&M\cup (L\cap R)\\[1.4ex](L\cap M)&\,\cap \,&&(&&M\cap R)&&&&\;=\;\;&&L\cap M\cap R\\[1.4ex](L\cap M)&\,\setminus \,&&(&&M\cap R)&&&&\;=\;\;&&(L\cap M)\,\setminus \,R\\[1.4ex](L\cap M)&\,\triangle \,&&(&&M\cap R)&&&&\;=\;\;&&[(L\,\cap M)\cup (M\,\cap R)]\,\setminus \,(L\,\cap M\,\cap R)\\[1.4ex](L\,\setminus M)&\,\cup \,&&(&&M\,\setminus R)&&&&\;=\;\;&&(L\,\cup M)\,\setminus (M\,\cap \,R)\\[1.4ex](L\,\setminus M)&\,\cap \,&&(&&M\,\setminus R)&&&&\;=\;\;&&\varnothing \\[1.4ex](L\,\setminus M)&\,\setminus \,&&(&&M\,\setminus R)&&&&\;=\;\;&&L\,\setminus M\\[1.4ex](L\,\setminus M)&\,\triangle \,&&(&&M\,\setminus R)&&&&\;=\;\;&&(L\,\setminus M)\cup (M\,\setminus R)\\[1.4ex]&\,&&\,&&\,&&&&\;=\;\;&&(L\,\cup M)\setminus (M\,\cap R)\\[1.4ex](L\,\triangle \,M)&\,\cup \,&&(&&M\,\triangle \,R)&&&&\;=\;\;&&(L\,\cup \,M\,\cup \,R)\,\setminus \,(L\,\cap \,M\,\cap \,R)\\[1.4ex](L\,\triangle \,M)&\,\cap \,&&(&&M\,\triangle \,R)&&&&\;=\;\;&&((L\,\cap \,R)\,\setminus \,M)\,\cup \,(M\,\setminus \,(L\,\cup \,R))\\[1.4ex](L\,\triangle \,M)&\,\setminus \,&&(&&M\,\triangle \,R)&&&&\;=\;\;&&(L\,\setminus \,(M\,\cup \,R))\,\cup \,((M\,\cap \,R)\,\setminus \,L)\\[1.4ex](L\,\triangle \,M)&\,\triangle \,&&(&&M\,\triangle \,R)&&&&\;=\;\;&&L\,\triangle \,R\\[1.7ex]\end{alignedat}}

Operations of the form $(L\bullet M)\ast (R\,\setminus \,M)$ :

{\begin{alignedat}{9}(L\cup M)&\,\cup \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&L\cup M\cup R\\[1.4ex](L\cup M)&\,\cap \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&(L\cap R)\,\setminus \,M\\[1.4ex](L\cup M)&\,\setminus \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&M\cup (L\,\setminus \,R)\\[1.4ex](L\cup M)&\,\triangle \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&M\cup (L\,\triangle \,R)\\[1.4ex](L\cap M)&\,\cup \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&[L\cap (M\cup R)]\cup [R\,\setminus \,(L\cup M)]\qquad {\text{ (disjoint union)}}\\[1.4ex]&\,&&\,&&\,&&&&\;=\;\;&&(L\cap M)\,\triangle \,(R\,\setminus \,M)\\[1.4ex](L\cap M)&\,\cap \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&\varnothing \\[1.4ex](L\cap M)&\,\setminus \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&L\cap M\\[1.4ex](L\cap M)&\,\triangle \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&(L\cap M)\cup (R\,\setminus \,M)\qquad {\text{ (disjoint union)}}\\[1.4ex](L\,\setminus \,M)&\,\cup \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&L\cup R\,\setminus \,M\\[1.4ex](L\,\setminus \,M)&\,\cap \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&(L\cap R)\,\setminus \,M\\[1.4ex](L\,\setminus \,M)&\,\setminus \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&L\,\setminus \,(M\cup R)\\[1.4ex](L\,\setminus \,M)&\,\triangle \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&(L\,\triangle \,R)\,\setminus \,M\\[1.4ex](L\,\triangle \,M)&\,\cup \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&(L\cup M\cup R)\,\setminus \,(L\cap M)\\[1.4ex](L\,\triangle \,M)&\,\cap \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&(L\cap R)\,\setminus \,M\\[1.4ex](L\,\triangle \,M)&\,\setminus \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&[L\,\setminus \,(M\cup R)]\cup (M\,\setminus \,L)\qquad {\text{ (disjoint union)}}\\[1.4ex]&\,&&\,&&\,&&&&\;=\;\;&&(L\,\triangle \,M)\setminus (L\,\cap R)\\[1.4ex](L\,\triangle \,M)&\,\triangle \,&&(&&R\,\setminus \,M)&&&&\;=\;\;&&L\,\triangle \,(M\cup R)\\[1.7ex]\end{alignedat}}

Operations of the form $(L\,\setminus \,M)\ast (L\,\setminus \,R)$ :

{\begin{alignedat}{9}(L\,\setminus M)&\,\cup \,&&(&&L\,\setminus R)&&\;=\;&&L\,\setminus \,(M\,\cap \,R)\\[1.4ex](L\,\setminus M)&\,\cap \,&&(&&L\,\setminus R)&&\;=\;&&L\,\setminus \,(M\,\cup \,R)\\[1.4ex](L\,\setminus M)&\,\setminus \,&&(&&L\,\setminus R)&&\;=\;&&(L\,\cap \,R)\,\setminus \,M\\[1.4ex](L\,\setminus M)&\,\triangle \,&&(&&L\,\setminus R)&&\;=\;&&L\,\cap \,(M\,\triangle \,R)\\[1.4ex]&\,&&\,&&\,&&\;=\;&&(L\cap M)\,\triangle \,(L\cap R)\\[1.4ex]\end{alignedat}}

Other properties:

L\cap M=R\;{\text{ and }}\;L\cap R=M\qquad {\text{ if and only if }}\qquad M=R\subseteq L.

If $L\subseteq M$ then $L\setminus R=L\cap (M\setminus R).$ [5]
$L\times (M\,\setminus R)=(L\times M)\,\setminus (L\times R)$
If $L\subseteq R$ then $M\setminus R\subseteq M\setminus L.$
$L\cap M\cap R=\varnothing$ if and only if for any $x\in L\cup M\cup R,$ $x$ belongs to at most two of the sets $L,M,{\text{ and }}R.$

Arbitrary families of sets

Let $\left(L_{i}\right)_{i\in I},$ $\left(R_{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}L_{i}~~\colon =~\{x~:~{\text{ there exists }}i\in I{\text{ such that }}x\in L_{i}\}

[4]

(Def. 1)

If $I=\varnothing$ then $\bigcup _{i\in \varnothing }L_{i}=\{x~:~{\text{ there exists }}i\in \varnothing {\text{ such that }}x\in L_{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}L_{i}~~\colon =~\{x~:~x\in L_{i}{\text{ for every }}i\in I\}~=~\{x~:~{\text{ for all }}i,{\text{ if }}i\in I{\text{ then }}x\in L_{i}\}.

(Def. 2)

Nullary intersections

If $I=\varnothing$ then

\bigcap _{i\in \varnothing }L_{i}=\{x~:~{\text{ for all }}i,{\text{ if }}i\in \varnothing {\text{ then }}x\in L_{i}\}

where every possible thing $x$ in the universe vacuously satisfied the condition: "if $i\in \varnothing$ then $x\in L_{i}$ ". Consequently, $\bigcap _{i\in \varnothing }L_{i}=\{x:{\text{ true }}\}$ consists of everything in the universe.

So if $I=\varnothing$ and:

if you are working in a model in which there exists some universe set $X$ then $\bigcap _{i\in \varnothing }L_{i}=\{x~:~x\in L_{i}{\text{ for every }}i\in \varnothing \}~=~X.$
otherwise, if you are working in a model in which "the class of all things $x$ " is not a set (by far the most common situation) then $\bigcap _{i\in \varnothing }L_{i}$ is undefined because $\bigcap _{i\in \varnothing }L_{i}$ consists of everything, which makes $\bigcap _{i\in \varnothing }L_{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 is not as commonly accepted as the nullary union convention and this article will not adopt it (this is due to the fact that unlike the empty union, the value of the empty intersection depends on $X$ so if there are multiple sets under consideration, which is commonly the case, then the value of the empty intersection risks becoming ambiguous).

Multiple index sets

\bigcup _{\stackrel {i\in I,}{j\in J}}S_{i,j}~~\colon =~\bigcup _{(i,j)\in I\times J}S_{i,j}

\bigcap _{\stackrel {i\in I,}{j\in J}}S_{i,j}~~\colon =~\bigcap _{(i,j)\in I\times J}S_{i,j}

Commutativity and associativity

Commutativity:[4]

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

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

Unions of unions and intersections of intersections:[4]

\left(\bigcup _{i\in I}L_{i}\right)\cup R~=~\bigcup _{i\in I}\left(L_{i}\cup R\right)

\left(\bigcap _{i\in I}L_{i}\right)\cap R~=~\bigcap _{i\in I}\left(L_{i}\cap R\right)

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

[4]

(Eq. 2a)

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

[4]

(Eq. 2b)

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

\left(\bigcup _{i\in I}L_{i}\right)\cup \left(\bigcup _{i\in I}R_{i}\right)~=~\bigcup _{i\in I}\left(L_{i}\cup R_{i}\right)

[4]

(Eq. 2c)

\left(\bigcap _{i\in I}L_{i}\right)\cap \left(\bigcap _{i\in I}R_{i}\right)~=~\bigcap _{i\in I}\left(L_{i}\cap R_{i}\right)

[4]

(Eq. 2d)

Binary intersection of arbitrary unions

\left(\bigcup _{i\in I}L_{i}\right)\cap R~=~\bigcup _{i\in I}\left(L_{i}\cap R\right)

(Eq. 3a)

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

[5]

(Eq. 3b)

If all $\left(L_{i}\right)_{i\in I}$ are pairwise disjoint and all $\left(R_{j}\right)_{j\in J}$ are also pairwise disjoint, then so are all $\left(L_{i}\cap R_{j}\right)_{(i,j)\in I\times J}$ (that is, if $(i,j)\neq \left(i_{2},j_{2}\right)$ then $\left(L_{i}\cap R_{j}\right)\cap \left(L_{i_{2}}\cap R_{j_{2}}\right)=\varnothing$ ).

Importantly, if $I=J$ then in general, $~\left(\bigcup _{i\in I}L_{i}\right)\cap \left(\bigcup _{i\in I}R_{i}\right)~~\color {Red}{\neq }\color {Black}{}~~\bigcup _{i\in I}\left(L_{i}\cap R_{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}L_{i}\right)\cap \left(\bigcup _{i\in I}R_{i}\right)~~=~~\bigcup _{\stackrel {i\in I,}{j\in I}}\left(L_{i}\cap R_{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}L_{i}\right)\cup R~=~\bigcap _{i\in I}\left(L_{i}\cup R\right)

(Eq. 4a)

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

[5]

(Eq. 4b)

Arbitrary intersections and arbitrary unions

Naively swapping $\;\bigcup _{i\in I}\;$ and $\;\bigcap _{j\in J}\;$ may produce a different set

The following inclusion always holds:

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

(Inclusion 1 ∪∩ is a subset of ∩∪)

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 =L_{i}\setminus R_{j}$ and $\left({\hat {S}}_{j,i}\right)_{(j,i)\in J\times I}\colon =\left(L_{i}\setminus R_{j}\right)_{(j,i)\in J\times I}$ (for 7f, $I$ and $J$ are swapped). For a correct formula that extends the distributive laws, an approach other than just switching $\cup$ and $\cap$ is needed.

Distributive laws

Suppose that for each $i\in I,$ $J_{i}$ is a non-empty index set and for each $j\in J_{i},$ let $T_{i,j}$ be any set (for example, to apply this law to $\left(S_{i,j}\right)_{(i,j)\in I\times J},$ use $J_{i}\colon =J$ for all $i\in I$ and use $T_{i,j}\colon =S_{i,j}$ for all $i\in I$ and all $j\in J_{i}=J$ ). Let

{\textstyle \prod }J_{\bullet }~\colon =~\prod _{i\in I}J_{i}

denote 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}}T_{i,j}\right]=\bigcup _{f\in \prod J_{\bullet }}\left[\;\bigcap _{i\in I}T_{i,f(i)}\right]

(Eq. 5 ∩∪ to ∪∩)

\bigcup _{i\in I}\left[\;\bigcap _{j\in J_{i}}T_{i,j}\right]=\bigcap _{f\in \prod J_{\bullet }}\left[\;\bigcup _{i\in I}T_{i,f(i)}\right]

(Eq. 6 ∪∩ to ∩∪)

where ${\textstyle \prod }J_{\bullet }~\colon =~\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, the Cartesian product will be ${\textstyle \prod }J_{\bullet }~\colon =~\prod _{i\in I}J_{i}=\prod _{i\in I}J=J^{I},$ which is the set of all functions of the form $f~:~I~\to ~J.$ The above set equalities Eq. 5 ∩∪ to ∪∩ and Eq. 6 ∪∩ to ∩∪, 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 ∪∩ is a subset of ∩∪ 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]~~\color {Red}{\subseteq }\color {Black}{}~~\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

on the left hand side, the indices $f{\text{ and }}i$ range over $f\in J^{I}{\text{ and }}i\in I$ (so the subscripts of $S_{i,f(i)}$ range over $i\in I{\text{ and }}f(i)\in f(I)\subseteq J$ )
on the right hand side, the indices $g{\text{ and }}j$ range over $g\in I^{J}{\text{ and }}j\in J$ (so the subscripts of $S_{g(j),j}$ range over $j\in J{\text{ and }}g(j)\in g(J)\subseteq I$ ).

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 $T_{1,k}\colon =C_{k}$ for all $k\in J_{1}$ and let $T_{2,l}\colon =D_{l}$ for all $l\in J_{2}.$ Every map $f\in {\textstyle \prod }J_{\bullet }~\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 {\textstyle \prod }J_{\bullet }$ defined by $1\mapsto k$ and $2\mapsto l;$ this is technically just a change of notation). Recall that Eq. 5 ∩∪ to ∪∩ was

~\bigcap _{i\in I}\left[\;\bigcup _{j\in J_{i}}T_{i,j}\right]=\bigcup _{f\in {\textstyle \prod }J_{\bullet }}\left[\;\bigcap _{i\in I}T_{i,f(i)}\right].~

Expanding and simplifying the left hand side gives

\bigcap _{i\in I}\left[\;\bigcup _{j\in J_{i}}T_{i,j}\right]=\left(\bigcup _{j\in J_{1}}T_{1,j}\right)\cap \left(\;\bigcup _{j\in J_{2}}T_{2,j}\right)=\left(\bigcup _{k\in K}T_{1,k}\right)\cap \left(\;\bigcup _{l\in L}T_{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 \prod J_{\bullet }}\left[\;\bigcap _{i\in I}T_{i,f(i)}\right]=\bigcup _{f\in \prod J_{\bullet }}\left(T_{1,f(1)}\cap T_{2,f(2)}\right)=\bigcup _{f\in \prod J_{\bullet }}\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 ∩∪ to ∪∩ 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}L_{i}\right)\;\setminus \;R~=~\bigcup _{i\in I}\left(L_{i}\;\setminus \;R\right)

(Eq. 7a)

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

(Eq. 7b)

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

(De Morgan's law)[5]

(Eq. 7c)

L\;\setminus \;\left(\bigcap _{j\in J}R_{j}\right)~=~\bigcup _{j\in J}\left(L\;\setminus \;R_{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}L_{i}\right)\;\setminus \;\left(\bigcup _{j\in J}R_{j}\right)~=~\bigcup _{i\in I}\left(\bigcap _{j\in J}\left(L_{i}\;\setminus \;R_{j}\right)\right)~=~\bigcap _{j\in J}\left(\bigcup _{i\in I}\left(L_{i}\;\setminus \;R_{j}\right)\right)

(Eq. 7e)

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

(Eq. 7f)

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

(Eq. 7g)

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

(Eq. 7h)

Intersections of products

If $\left(S_{i,j}\right)_{(i,j)\in I\times J}$ is a family of sets then

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

(Eq. 8)

Moreover, a tuple $\left(x_{i}\right)_{i\in I}$ belongs to the set in Eq. 8 above if and only if $x_{i}\in S_{i,j}$ for all $i\in I$ and all $j\in J.$

If $\left(L_{i}\right)_{i\in I}$ and $\left(R_{i}\right)_{i\in I}$ are two families indexed by the same set then

\left(\prod _{i\in I}L_{i}\right)\cap \left(\prod _{i\in I}R_{i}\right)~=~\prod _{i\in I}\left(L_{i}\cap R_{i}\right)

So for instance,

(L\times R)\cap \left(L_{2}\times R_{2}\right)~=~\left(L\cap L_{2}\right)\times \left(R\cap R_{2}\right)

and

(L\times M\times R)\cap \left(L_{2}\times M_{2}\times R_{2}\right)~=~\left(L\cap L_{2}\right)\times \left(M\cap M_{2}\right)\times \left(R\cap R_{2}\right)

Intersections of products indexed by different sets

Let $\left(L_{i}\right)_{i\in I}$ and $\left(R_{j}\right)_{j\in J}$ be two families indexed by different sets.

Technically, $I\neq J$ implies $\left(\prod _{i\in I}L_{i}\right)\cap \left(\prod _{j\in J}R_{j}\right)=\varnothing .$ However, sometimes these products are somehow identified as the same set through some bijection or one of these products is identified as a subset of the other via some injective map, in which case (by abuse of notation) this intersection may be equal to some other (possibly non-empty) set.

For example, if $I:=\{1,2\}$ and $J:=\{1,2,3\}$ with all sets equal to $\mathbb {R}$ then $\prod _{i\in I}L_{i}=\prod _{i\in \{1,2\}}\mathbb {R} =\mathbb {R} ^{2}$ and $\prod _{j\in J}R_{j}=\prod _{j\in \{1,2,3\}}\mathbb {R} =\mathbb {R} ^{3}$ where $\mathbb {R} ^{2}\cap \mathbb {R} ^{3}=\varnothing$ unless, for example, $\prod _{i\in \{1,2\}}\mathbb {R} =\mathbb {R} ^{2}$ is identified as a subset of $\prod _{j\in \{1,2,3\}}\mathbb {R} =\mathbb {R} ^{3}$ through some injection, such as maybe $(x,y)\mapsto (x,y,0)$ for instance; however, in this particular case the product $\prod _{i\in I=\{1,2\}}L_{i}$ actually represents the $J$ -indexed product $\prod _{j\in J=\{1,2,3\}}L_{i}$ where $L_{3}:=\{0\}.$
For another example, take $I:=\{1,2\}$ and $J:=\{1,2,3\}$ with $L_{1}:=\mathbb {R} ^{2}$ and $L_{2},R_{1},R_{2},{\text{ and }}R_{3}$ all equal to $\mathbb {R} .$ Then $\prod _{i\in I}L_{i}=\mathbb {R} ^{2}\times \mathbb {R}$ and $\prod _{j\in J}R_{j}=\mathbb {R} \times \mathbb {R} \times \mathbb {R} ,$ which can both be identified as the same set via the bijection that sends $((x,y),z)\in \mathbb {R} ^{2}\times \mathbb {R}$ to $(x,y,z)\in \mathbb {R} \times \mathbb {R} \times \mathbb {R} .$ Under this identification, $\left(\prod _{i\in I}L_{i}\right)\cap \left(\prod _{j\in J}R_{j}\right)~=~\mathbb {R} ^{3}.$

Unions of products

For unions, only the following is guaranteed in general:

\bigcup _{j\in J}\left(\prod _{i\in I}S_{i,j}\right)~~\color {Red}{\subseteq }\color {Black}{}~~\prod _{i\in I}\left(\bigcup _{j\in J}S_{i,j}\right)\qquad {\text{ and }}\qquad \bigcup _{i\in I}\left(\prod _{j\in J}S_{i,j}\right)~~\color {Red}{\subseteq }\color {Black}{}~~\prod _{j\in J}\left(\bigcup _{i\in I}S_{i,j}\right)

where $\left(S_{i,j}\right)_{(i,j)\in I\times J}$ is a family of sets.

However,

{\begin{alignedat}{9}\left(L\times R\right)~\cup ~\left(L_{2}\times R_{2}\right)~&=~\left[\left(L\setminus L_{2}\right)\times R\right]~\cup ~\left[\left(L_{2}\setminus L\right)\times R_{2}\right]~\cup ~\left[\left(L\cap L_{2}\right)\times \left(R\cup R_{2}\right)\right]\\[0.5ex]~&=~\left[L\times \left(R\setminus R_{2}\right)\right]~\cup ~\left[L_{2}\times \left(R_{2}\setminus R\right)\right]~\cup ~\left[\left(L\cup L_{2}\right)\times \left(R\cap R_{2}\right)\right]\\\end{alignedat}}

Set subtraction of products

If $\left(L_{i}\right)_{i\in I}$ and $\left(R_{i}\right)_{i\in I}$ are two families of sets then:

{\begin{alignedat}{9}\left(\prod _{i\in I}L_{i}\right)~\setminus ~\left(\prod _{i\in I}R_{i}\right)~&=~\;~\bigcup _{j\in I}\;~\prod _{i\in I}{\begin{cases}L_{j}\,\setminus \,R_{j}&{\text{ if }}i=j\\L_{i}&{\text{ if }}i\neq j\\\end{cases}}\\[0.5ex]~&=~\;~\bigcup _{j\in I}\;~{\Big [}\left(L_{j}\,\setminus \,R_{j}\right)~\times ~\prod _{\stackrel {i\in I,}{j\neq i}}L_{i}{\Big ]}\\[0.5ex]~&=~\bigcup _{\stackrel {j\in I,}{L_{j}\not \subseteq R_{j}}}{\Big [}\left(L_{j}\,\setminus \,R_{j}\right)~\times ~\prod _{\stackrel {i\in I,}{j\neq i}}L_{i}{\Big ]}\\[0.3ex]\end{alignedat}}

so for instance,

{\begin{alignedat}{9}\left(L\times R\right)~\setminus ~\left(L_{2}\times R_{2}\right)~&=~\left[\left(L\,\setminus \,L_{2}\right)\times R\right]~\cup ~\left[L\times \left(R\,\setminus \,R_{2}\right)\right]\\\end{alignedat}}

and

(L\times M\times R)~\setminus ~\left(L_{2}\times M_{2}\times R_{2}\right)~=~\left[\left(L\,\setminus \,L_{2}\right)\times M\times R\right]~\cup ~\left[L\times \left(M\,\setminus \,M_{2}\right)\times R\right]~\cup ~\left[L\times M\times \left(R\,\setminus \,R_{2}\right)\right]

Functions and sets

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

Let $L{\text{ and }}R$ be completely arbitrary sets. Assume $A\subseteq X{\text{ and }}C\subseteq Y.$

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 (that is, to $X$ or $Y$ ) so when some kind of relationship is necessary then it will be clearly indicated. Because of this, in this article, if $L$ is declared to be "any set," and it is not indicated that $L$ must be somehow related to $X$ or $Y$ (say for instance, that it be a subset $X$ or $Y$ ) then it is meant that $L$ is truly arbitrary.[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 $L$ might not be entirely contained in $X=\operatorname {domain} f$ and/or $Y=\operatorname {codomain} f$ (e.g. if all that is known about $L$ is that $L\subseteq U$ ); in such a situation it may be useful to know what can and cannot be said about $f(L)$ and/or $f^{-1}(L)$ without having to introduce a (potentially unnecessary) intersection such as: $f(L\cap X)$ and/or $f^{-1}(L\cap Y).$

Images and preimages of sets

If $L$ is any set then the image of $L$ under $f$ is defined to be the set:

f(L)~:=~\{\,f(l)~:~l\in L\cap \operatorname {domain} f\,\}

while the preimage of $L$ under $f$ is:

f^{-1}(L)~:=~\{\,x\in \operatorname {domain} f~:~f(x)\in L\,\}

where if $L=\{s\}$ is a singleton set then the filber or preimage of $s$ under $f$ is

f^{-1}(s)~:=~f^{-1}(\{s\})~=~\{\,x\in \operatorname {domain} f~:~f(x)=s\,\}.

Denote by $\operatorname {Im} f$ or $\operatorname {image} f$ the image or range of $f:X\to Y,$ which is the set:

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

Saturated sets

A set $A$ is said to be $f$ -saturated or a saturated set if any of the following equivalent conditions are satisfied:

There exists a set $R$ $\text{[math]}$ such that $A=f^{-1}(R).$ $\text{[math]}$
- Any such set $R$ necessarily contains $f(A)$ as a subset.
$A=f^{-1}(f(A)).$
$A\supseteq f^{-1}(f(A))$ $\text{[math]}$ and $A\subseteq \operatorname {domain} f.$ $\text{[math]}$
- The inclusion $L\cap \operatorname {domain} f\subseteq f^{-1}(f(L))$ always holds, where if $A\subseteq \operatorname {domain} f$ then this becomes $A\subseteq f^{-1}(f(A)).$

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

Compositions and restrictions of functions

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

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

with domain and codomain

{\begin{alignedat}{4}\operatorname {domain} (g\circ f)&=\{\,x\in \operatorname {domain} f~:~f(x)\in \operatorname {domain} g\,\}\\[0.4ex]\operatorname {codomain} (g\circ f)&=\operatorname {codomain} g\\[0.7ex]\end{alignedat}}

defined by

(g\circ f)(x):=g(f(x)).

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

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

with $\operatorname {domain} f{\big \vert }_{L}~=~L\cap \operatorname {domain} f$ defined by sending $x\in L\cap \operatorname {domain} f$ to $f(x);$ that is,

f{\big \vert }_{L}(x)~:=~f(x).

Alternatively, $~f{\big \vert }_{L}~=~f\circ \operatorname {In} ~$ where $~\operatorname {In} ~:~L\cap X\to X~$ denotes the inclusion map, which is defined by $\operatorname {In} (s):=s.$

(Pre)Image of a single set

Image	Preimage	Additional assumptions
${\begin{alignedat}{4}f(L)&=f(L\cap \operatorname {domain} f)\\&=f(L\cap X)\\&=Y~~~~\,\setminus \left\{y\in Y~~~~\,:f^{-1}(y)\subseteq X\setminus L\right\}\\&=\operatorname {Im} f\setminus \left\{y\in \operatorname {Im} f:f^{-1}(y)\subseteq X\setminus L\right\}\\\end{alignedat}}$	${\begin{alignedat}{4}f^{-1}(L)&=f^{-1}(L\cap \operatorname {Im} f)\\&=f^{-1}(L\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(L)&=f(L\cap R~&&\cup ~&&(&&L\setminus R))\\&=f(L\cap R)~&&\cup ~f&&(&&L\setminus R)\end{alignedat}}$	${\begin{alignedat}{4}f^{-1}(L)&=f^{-1}(L\cap R&&\cup &&(&&L&&\setminus &&R))\\&=f^{-1}(L\cap R)&&\cup f^{-1}&&(&&L&&\setminus &&R)\\&=f^{-1}(L\cap R)&&\cup f^{-1}&&(&&L&&\setminus [&&R\cap \operatorname {Im} f])\\&=f^{-1}(L\cap R)&&\cup f^{-1}&&([&&L\cap \operatorname {Im} f]&&\setminus &&R)\\&=f^{-1}(L\cap R)&&\cup f^{-1}&&([&&L\cap \operatorname {Im} f]&&\setminus [&&R\cap \operatorname {Im} f])\end{alignedat}}$	None
$\operatorname {Im} f=f(X)~=~f(L)\cup f(X\setminus L)$	${\begin{alignedat}{4}X&=f^{-1}(L)\cup f^{-1}(Y&&\setminus L)\\&=f^{-1}(L)\cup f^{-1}(\operatorname {Im} f&&\setminus L)\end{alignedat}}$	None
$f{\big \vert }_{L}(R)=f(L\cap R)$	$\left(f{\big \vert }_{L}\right)^{-1}(R)=L\cap f^{-1}(R)$	None
$(g\circ f)(L)~=~g(f(L))$	$(g\circ f)^{-1}(L)~=~f^{-1}\left(g^{-1}(L)\right)$	None ( $f$ and $g$ are arbitrary functions).
$f\left(f^{-1}(L)\right)=L\cap \operatorname {Im} f$	$f^{-1}(f(L))~\supseteq ~L\cap f^{-1}(\operatorname {Im} f)=L\cap f^{-1}(Y)$ [6]	None
$f\left(f^{-1}(Y)\right)=f\left(f^{-1}(\operatorname {Im} f)\right)=f(X)$	$f^{-1}(f(X))=f^{-1}(\operatorname {Im} f)=X$	None
$f\left(f^{-1}(f(L))\right)=f(L)$	$f^{-1}\left(f\left(f^{-1}(L)\right)\right)=f^{-1}(L)$	None

Equivalences and implications of images and preimages

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

Miscellaneous

$f(L)\cap R=\varnothing$ if and only if $L\cap f^{-1}(R)=\varnothing$ [6] if and only if $f^{-1}(f(L))\cap f^{-1}(R)=\varnothing .$

Thus for any $t,$ [6] $t\not \in f(L)\quad {\text{ if and only if }}\quad L\cap f^{-1}(t)=\varnothing .$

(Pre)Images of set operations

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

Summary

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

Image	Preimage	Additional assumptions on sets
$\,~~~~f(L\cup R)~=~f(L)\cup f(R)$ [9]	$f^{-1}(L\cup R)~=~f^{-1}(L)\cup f^{-1}(R)$ [4]	None
$f(L\cap R)~\subseteq ~f(L)\cap f(R)$	$f^{-1}(L\cap R)~=~f^{-1}(L)\cap f^{-1}(R)$ [4]	None
$f(L\setminus R)~\supseteq ~f(L)\setminus f(R)$	${\begin{alignedat}{4}f^{-1}(L)\setminus f^{-1}(R)&=f^{-1}&&(&&L&&\setminus &&R)\\&=f^{-1}&&(&&L&&\setminus [&&R\cap \operatorname {Im} f])\\&=f^{-1}&&([&&L\cap \operatorname {Im} f]&&\setminus &&R)\\&=f^{-1}&&([&&L\cap \operatorname {Im} f]&&\setminus [&&R\cap \operatorname {Im} f])\end{alignedat}}$ [6][4]	None
$f(X\setminus R)~\supseteq ~f(X)\setminus f(R)$	${\begin{alignedat}{4}X\setminus f^{-1}(R)&=f^{-1}(&&Y&&\setminus &&R)\\&=f^{-1}(&&Y&&\setminus [&&R\cap \operatorname {Im} f])\\&=f^{-1}(&&\operatorname {Im} f&&\setminus &&R)\\&=f^{-1}(&&\operatorname {Im} f&&\setminus [&&R\cap \operatorname {Im} f])\end{alignedat}}$ [note 7]	None
$f\left(L~\triangle ~R\right)~\supseteq ~f(L)~\triangle ~f(R)$	$f^{-1}\left(L~\triangle ~R\right)~=~f^{-1}(L)~\triangle ~f^{-1}(R)$	None

Preimages preserve set operations

Preimages of sets are well-behaved with respect to all basic set operations:

{\begin{alignedat}{4}f^{-1}(L\cup R)~&=~f^{-1}(L)\cup f^{-1}(R)\\f^{-1}(L\cap R)~&=~f^{-1}(L)\cap f^{-1}(R)\\f^{-1}(L\setminus \,R)~&=~f^{-1}(L)\setminus \,f^{-1}(R)\\f^{-1}(L\,\triangle \,R)~&=~f^{-1}(L)\,\triangle \,f^{-1}(R)\\\end{alignedat}}

In words, preimages distribute over unions, intersections, set subtraction, and symmetric difference.

Images only preserve unions

Images of unions are well-behaved:

{\begin{alignedat}{4}f(L\cup R)~&=~f(L)\cup f(R)\\\end{alignedat}}

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

{\begin{alignedat}{4}f(L\cap R)~&\subseteq ~f(L)\cap f(R)\\f(L\setminus R)~&\supseteq ~f(L)\setminus f(R)\\f(L\triangle R)~&\supseteq ~f(L)\,\triangle \,f(R)\\\end{alignedat}}

In words, images distribute over unions but not necessarily over intersections, set subtraction, or symmetric difference.

In general, equality is not guaranteed for images of set subtraction $L\setminus R$ nor for images of the other two elementary set operators that can be defined as the difference of two sets:

L\cap R=L\setminus (L\setminus R)\quad {\text{ and }}\quad L\triangle R=(L\cup R)\setminus (L\cap R).

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

Counter-examples to set equality

Picture showing

f

failing to distribute over set intersection:

f\left(A_{1}\cap A_{2}\right)\subsetneq f\left(A_{1}\right)\cap f\left(A_{2}\right).

The map

f:\mathbb {R} \to \mathbb {R}

is defined by

x\mapsto x^{2},

where

\mathbb {R}

denotes the real numbers. The sets

A_{1}=[-4,2]

and

A_{2}=[-2,4]

are shown in blue immediately below the

x

-axis while their intersection

A_{3}=[-2,2]

is shown in green.

Examples will be given demonstrating that the set containments

{\begin{alignedat}{4}f(L\cap R)~&\subseteq ~f(L)\cap f(R)\\f(L\setminus R)~&\supseteq ~f(L)\setminus f(R)\\f(X\setminus R)~&\supseteq ~f(X)\setminus f(R)\\f(L\triangle R)~&\supseteq ~f(L)\triangle f(R)\\\end{alignedat}}

might all be strict/proper; that is, equality need not hold. Specifically, the example below shows that these equalities could fail for any constant function whose domain contains at least two (distinct) points. For instance, all four containments are proper if $f:\{1,2\}\to Y$ is constant, $L=\{1\},$ and $R=\{2\}.$ Thus equality is not guaranteed for even the simplest of functions.

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

The containment $~f(L\setminus R)~\supseteq ~f(L)\setminus f(R)~$ is strict: $\{y\}~=~f(L\setminus R)~\neq ~f(L)\setminus f(R)~=~\{y\}\setminus \{y\}~=~\varnothing$
In words: functions might not distribute over set subtraction $\,\setminus \,$
The containment $~f(X\setminus R)~\supseteq ~f(X)\setminus f(R)~$ is strict: $\{y\}~=~f(X\setminus R)~\neq ~f(X)\setminus f(R)~=~\{y\}\setminus \{y\}~=~\varnothing .$
The containment $~f(L~\triangle ~R)~\supseteq ~f(L)~\triangle ~f(R)~$ is strict: $\{y\}~=~f\left(L~\triangle ~R\right)~\neq ~f(L)~\triangle ~f(R)~=~\{y\}\triangle \{y\}~=~\varnothing$
In words: functions might not distribute over symmetric difference $\,\triangle \,$ (which can be defined as the set subtraction of two sets: $L\triangle R=(L\cup R)\setminus (L\cap R)$ ).
The containment $~f(L\cap R)~\subseteq ~f(L)\cap f(R)~$ is strict: $\varnothing ~=~f(\varnothing )~=~f(L\cap R)~\neq ~f(L)\cap f(R)~=~\{y\}\cap \{y\}~=~\{y\}$
In words: functions might not distribute over set intersection $\,\cap \,$ (which can be defined as the set subtraction of two sets: $L\cap R=L\setminus (L\setminus R)$ ).

What the set operations in these four examples have in common is that they either are set subtraction $\setminus$ (examples (1) and (2)) or else they can naturally be defined as the set subtraction of two sets (examples (3) and (4)).

Mnemonic: In fact, for each of the above four set formulas for which equality is not guaranteed, the direction of the containment (that is, whether to use $\,\subseteq {\text{ or }}\supseteq \,$ ) can always be deduced by imagining the function $f$ as being constant and the two sets ( $L$ and $R$ ) as being non-empty disjoint subsets of its domain. This is because every equality fails for such a function and sets: one side will be always be $\varnothing$ and the other non-empty − from this fact, the correct choice of $\,\subseteq {\text{ or }}\supseteq \,$ can be deduced by answering: "which side is empty?" For example, to decide if the ${\displaystyle$ in

f(L\triangle R)\setminus f(R)~\;~?~\;~f((L\triangle R)\setminus R)

should be $\,\subseteq {\text{ or }}\supseteq ,\,$ pretend[note 8] that $f$ is constant and that $L\triangle R$ and $R$ are non-empty disjoint subsets of $f$ 's domain; then the left hand side would be empty (since $f(L\triangle R)\setminus f(R)=\{f{\text{'s single value}}\}\setminus \{f{\text{'s single value}}\}=\varnothing$ ), which indicates that $\,?\,$ should be $\,\subseteq \,$ (the resulting statement is always guaranteed to be true) because this is the choice that will make

\varnothing ={\text{left hand side}}~\;~?~\;~{\text{right hand side}}

true. Alternatively, the correct direction of containment can also be deduced by consideration of any constant $f:\{1,2\}\to Y$ with $L=\{1\}$ and $R=\{2\}.$

Furthermore, this mnemonic can also be used to correctly deduce whether or not equalities such as $f(L\cap R)=f(L)\cap f(R)$ or $f^{-1}(L\cap R)=f^{-1}(L)\cap f^{-1}(R)$ hold in general (although $\,\cap \,$ was used here, it can replaced by $\,\cup ,\,\setminus ,{\text{ or }}\,\triangle$ ). The answer to such a question can, as before, be deduced by consideration of this constant function: the answer for the general case (that is, for arbitrary $f,L,$ and $R$ ) is always the same as the answer for this choice of (constant) function and disjoint non-empty sets.

Conditions for equality

Characterizations of when equality holds for all sets:

For any function $f:X\to Y,$ the following statements are equivalent:

$f:X\to Y$ $\text{[math]}$ is injective.
- This means: $f(x)\neq f(y)$ for all distinct $x,y\in X.$
$f(L\cap R)=f(L)\,\cap \,f(R)\,{\text{ for all }}\,L,R\subseteq X.$ (The equals sign $\,=\,$ can be replaced with $\,\supseteq \,$ ).
$f(L\,\setminus R)=f(L)\,\setminus \,f(R)\;{\text{ for all }}\,L,R\subseteq X.$ (The equals sign $\,=\,$ can be replaced with $\,\subseteq \,$ ).
$f(X\setminus R)=f(X)\setminus \,f(R)\;{\text{ for all }}\,~~~~~R\subseteq X.$ (The equals sign $\,=\,$ can be replaced with $\,\subseteq \,$ ).
$f(L\,\triangle \,R)=f(L)\,\triangle \,f(R)\;{\text{ for all }}\,L,R\subseteq X.$ (The equals sign $\,=\,$ can be replaced with $\,\subseteq \,$ ).
Any one of the four statements (b) - (e) but with the words "for all" replaced with any one of the following:
1. "for all singleton subsets"
  - In particular, the statement that results from (d) gives a characterization of injectivity that explicitly involves only one point (rather than two): $f$ is injective if and only if $f(x)\not \in f(X\setminus \{x\})\;{\text{ for every }}\,x\in X.$
2. "for all disjoint singleton subsets"
  - For statement (d), this is the same as: "for all singleton subsets" (because the definition of "pairwise disjoint" is satisfies vacuously by any family that consists of exactly 1 set).
3. "for all disjoint subsets"

In particular, if a map is not known to be injective then barring additional information, there is no guarantee that any of the equalities in statements (b) - (e) hold.

An example above can be used to help prove this characterization. Indeed, comparison of that example with such a proof suggests that the example is representative of the fundamental reason why one of these four equalities in statements (b) - (e) might not hold (that is, representative of "what goes wrong" when a set equality does not hold).

Image of an intersection

f(L\cap R)~\subseteq ~f(L)\cap f(R)\qquad \qquad {\text{ always holds}}

Characterizations of equality: The following statements are equivalent:

$f(L\cap R)~=~f(L)\cap f(R)$
$f(L\cap R)~\supseteq ~f(L)\cap f(R)$
$L\cap f^{-1}(f(R))~\subseteq ~f^{-1}(f(L\cap R))$ $\text{[math]}$
- The left hand side $L\cap f^{-1}(f(R))$ is always equal to $L\cap f^{-1}(f(L)\cap f(R))$ (because $L\cap f^{-1}(f(R))~\subseteq ~f^{-1}(f(L))$ always holds).
$R\cap f^{-1}(f(L))~\subseteq ~f^{-1}(f(L\cap R))$
$L\cap f^{-1}(f(R))~=~f^{-1}(f(L\cap R))\cap L$
$R\cap f^{-1}(f(L))~=~f^{-1}(f(L\cap R))\cap R$
$f(L)\,\setminus \,f(L\cap R)~\subseteq ~f(L)\,\setminus \,f(R)$
$f(R)\,\setminus \,f(L\cap R)~\subseteq ~f(R)\,\setminus \,f(L)$
$f(L\cup R)\setminus f(L\cap R)~\subseteq ~f(L)\,\triangle \,f(R)$
Any of the above three conditions (g) - (i) but with the subset symbol $\,\subseteq \,$ replaced with an equals sign $\,=.\,$

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

$f$ is injective.[10]
The restriction $f{\big \vert }_{L\cup R}$ is injective.
$f^{-1}(f(R))~\subseteq ~R$ [note 9]
$f^{-1}(f(L))~\subseteq ~L$
$R$ is $f$ -saturated; that is, $f^{-1}(f(R))=R$ [note 9]
$L$ is $f$ -saturated; that is, $f^{-1}(f(L))=L$
$f(L)~\subseteq ~f(L\cap R)$
$f(R)~\subseteq ~f(L\cap R)$
$f(L\,\setminus \,R)~\subseteq ~f(L)\setminus \,f(R)$ or equivalently, $f(L\,\setminus \,R)~=~f(L)\setminus f(R)$
$f(R\,\setminus \,L)~\subseteq ~f(R)\setminus \,f(L)$ or equivalently, $f(R\,\setminus \,L)~=~f(R)\setminus f(L)$
$f\left(L~\triangle ~R\right)\subseteq f(L)~\triangle ~f(R)$ or equivalently, $f\left(L~\triangle ~R\right)=f(L)~\triangle ~f(R)$
$R\cap \operatorname {domain} f\,\subseteq L$
$L\cap \operatorname {domain} f\,\subseteq R$
$R\subseteq L$
$L\subseteq R$

In addition, the following always hold:

f\left(f^{-1}(L)\cap R\right)~=~L\cap f(R)

f\left(f^{-1}(L)\cup R\right)~=~(L\cap \operatorname {Im} f)\cup f(R)

Image of a set subtraction

f(L\setminus R)~\supseteq ~f(L)\setminus f(R)\qquad \qquad {\text{ always holds}}

Characterizations of equality: The following statements are equivalent:[proof 1]

$f(L\setminus R)~=~f(L)\setminus f(R)$
$f(L\setminus R)~\subseteq ~f(L)\setminus f(R)$
$L\cap f^{-1}(f(R))~\subseteq ~R$
$L\cap f^{-1}(f(R))~=~L\cap R\cap \operatorname {domain} f$
Whenever $y\in f(L)\cap f(R)$ then $L\cap f^{-1}(y)\subseteq R.$
${\textstyle f(L)\cap f(R)~\subseteq ~\left\{y\in f(L):L\cap f^{-1}(y)\subseteq R\right\}}$ $\text{[math]}$
- The set on the right hand side is always equal to $\left\{y\in f(L\cap R):L\cap f^{-1}(y)\,\subseteq R\right\}.$
The above condition (f) but with the symbol $\,\subseteq \,$ replaced with an equals signs $\,=\,$

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

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

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

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

Image of a set subtracted from the domain

f(X\setminus R)~\supseteq ~f(X)\setminus f(R)\qquad \qquad {\text{ always holds, where }}f:X\to Y

Characterizations of equality: The following statements are equivalent:[proof 1]

$f(X\setminus R)~=~f(X)\setminus f(R)$
$f(X\setminus R)~\subseteq ~f(X)\setminus f(R)$
$f^{-1}(f(R))\,\subseteq \,R$
$f^{-1}(f(R))\,=\,R\cap \operatorname {domain} f$
$R\cap \operatorname {domain} f$ is $f$ -saturated.
Whenever $y\in f(R)$ then $f^{-1}(y)\subseteq R.$
${\textstyle f(R)~\subseteq ~\left\{y\in f(R):f^{-1}(y)\subseteq R\right\}}$
${\textstyle f(R)~=~\left\{y\in f(R):f^{-1}(y)\subseteq R\right\}}$

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

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

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

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

Image of a symmetric difference

f\left(L~\triangle ~R\right)~\supseteq ~f(L)~\triangle ~f(R)\qquad \qquad {\text{ always holds}}

Characterizations of equality: The following statements are equivalent:

$f\left(L~\triangle ~R\right)=f(L)~\triangle ~f(R)$
$f\left(L~\triangle ~R\right)\subseteq f(L)~\triangle ~f(R)$
$f(L\,\setminus \,R)=f(L)\,\setminus \,f(R)$ and $f(R\,\setminus \,L)=f(R)\,\setminus \,f(L)$
$f(L\,\setminus \,R)\subseteq f(L)\,\setminus \,f(R)$ and $f(R\,\setminus \,L)\subseteq f(R)\,\setminus \,f(L)$
$L\cap f^{-1}(f(R))~\subseteq ~R$ $\text{[math]}$ and $R\cap f^{-1}(f(L))~\subseteq ~L$ $\text{[math]}$
- The inclusions $L\cap f^{-1}(f(R))~\subseteq ~f^{-1}(f(L))$ and $R\cap f^{-1}(f(L))~\subseteq ~f^{-1}(f(R))$ always hold.
$L\cap f^{-1}(f(R))~=~R\cap f^{-1}(f(L))$ $\text{[math]}$
- If this above set equality holds, then this set will also be equal to both $L\cap R\cap \operatorname {domain} f$ and $L\cap R\cap f^{-1}(f(L\cap R)).$
$L\cap f^{-1}(f(L\cap R))~=~R\cap f^{-1}(f(L\cap R))$ and $f(L\cap R)~\supseteq ~f(L)\cap f(R).$

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

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

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

$f$ is injective.
The restriction $f{\big \vert }_{L\cup R}$ is injective.

Image of set subtraction

For any function $f:X\to Y$ and any sets $L$ and $R,$ [proof 2]

{\begin{alignedat}{4}f(L\setminus R)&=Y~~~\;\,\,\setminus \left\{y\in Y~~~~~~~~~~\;\,~:~L\cap f^{-1}(y)\subseteq R\right\}\\[0.4ex]&=f(L)\setminus \left\{y\in f(L)~~~~~~~\,~:~L\cap f^{-1}(y)\subseteq R\right\}\\[0.4ex]&=f(L)\setminus \left\{y\in f(L\cap R)~:~L\cap f^{-1}(y)\subseteq R\right\}\\[0.4ex]&=f(L)\setminus \left\{y\in V~~~~~~~~~~~~\,~:~L\cap f^{-1}(y)\subseteq R\right\}\qquad &&{\text{ for any superset }}\quad V\supseteq f(L\cap R)\\[0.4ex]&=f(S)\setminus \left\{y\in f(S)~~~~~~~\,~:~L\cap f^{-1}(y)\subseteq R\right\}\qquad &&{\text{ for any superset }}\quad S\supseteq L\cap X.\\[0.7ex]\end{alignedat}}

Image of set subtraction from the domain

Taking $L:=X=\operatorname {domain} f$ in the above formulas gives:

{\begin{alignedat}{4}f(X\setminus R)&=Y~~~\;\,\,\setminus \left\{y\in Y~~~~\;\,\,:~f^{-1}(y)\subseteq R\right\}\\[0.4ex]&=f(X)\setminus \left\{y\in f(X)~:~f^{-1}(y)\subseteq R\right\}\\[0.4ex]&=f(X)\setminus \left\{y\in f(R)~:~f^{-1}(y)\subseteq R\right\}\\[0.4ex]&=f(X)\setminus \left\{y\in W~~~\;\,\,:~f^{-1}(y)\subseteq R\right\}\qquad {\text{ for any superset }}\quad W\supseteq f(R)\\[0.4ex]\end{alignedat}}

where the set $\left\{y\in f(R):f^{-1}(y)\subseteq R\right\}$ is equal to the image under $f$ of the largest $f$ -saturated subset of $R.$

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

Image of symmetric difference

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

{\begin{alignedat}{4}f(L\,\triangle \,R)&=Y~~~\;~~~\;~~~\;\setminus \left\{y\in Y~~~\,~~~\;~~~\,~~:~L\cap f^{-1}(y)=R\cap f^{-1}(y)\right\}\\[0.4ex]&=f(L\cup R)\setminus \left\{y\in f(L\cup R)~:~L\cap f^{-1}(y)=R\cap f^{-1}(y)\right\}\\[0.4ex]&=f(L\cup R)\setminus \left\{y\in f(L\cap R)~:~L\cap f^{-1}(y)=R\cap f^{-1}(y)\right\}\\[0.4ex]&=f(L\cup R)\setminus \left\{y\in V~~~\,~~~~~~~~~~:~L\cap f^{-1}(y)=R\cap f^{-1}(y)\right\}\qquad &&{\text{ for any superset }}\quad V\supseteq f(L\cap R)\\[0.4ex]&=f(S)~~\,~~~\,~\,\setminus \left\{y\in f(S)~~~\,~~~\;~:~L\cap f^{-1}(y)=R\cap f^{-1}(y)\right\}\qquad &&{\text{ for any superset }}\quad S\supseteq (L\cup R)\cap X.\\[0.7ex]\end{alignedat}}

Image of a set

It follows from the above formulas for the image of a set subtraction that for any function $f:X\to Y$ and any set $L,$

{\begin{alignedat}{4}f(L)&=Y~~~\;\,\setminus \left\{y\in Y~~~\;\,~:~f^{-1}(y)\cap L=\varnothing \right\}\\[0.4ex]&=\operatorname {Im} f\setminus \left\{y\in \operatorname {Im} f~:~f^{-1}(y)\cap L=\varnothing \right\}\\[0.4ex]&=W~~~\,\setminus \left\{y\in W~~\;\,~:~f^{-1}(y)\cap L=\varnothing \right\}\qquad {\text{ for any superset }}\quad W\supseteq f(L)\\[0.7ex]\end{alignedat}}

This is more easily seen as being a consequence of the fact that for any $y\in Y,$ $f^{-1}(y)\cap L=\varnothing$ if and only if $y\not \in f(L).$

Image of set intersection

It follows from the above formulas for the image of a set that for any function $f:X\to Y$ and any sets $L$ and $R,$

{\begin{alignedat}{4}f(L\cap R)&=Y~~~~~\setminus \left\{y\in Y~~~~~~:~L\cap R\cap f^{-1}(y)=\varnothing \right\}&&\\[0.4ex]&=f(L)\setminus \left\{y\in f(L)~:~L\cap R\cap f^{-1}(y)=\varnothing \right\}&&\\[0.4ex]&=f(L)\setminus \left\{y\in U~~~~~~:~L\cap R\cap f^{-1}(y)=\varnothing \right\}\qquad &&{\text{ for any superset }}\quad U\supseteq f(L)\\[0.4ex]&=f(R)\setminus \left\{y\in f(R)~:~L\cap R\cap f^{-1}(y)=\varnothing \right\}&&\\[0.4ex]&=f(R)\setminus \left\{y\in V~~~~~~:~L\cap R\cap f^{-1}(y)=\varnothing \right\}\qquad &&{\text{ for any superset }}\quad V\supseteq f(R)\\[0.4ex]&=f(L)\cap f(R)\setminus \left\{y\in f(L)\cap f(R)~:~L\cap R\cap f^{-1}(y)=\varnothing \right\}&&\\[0.7ex]\end{alignedat}}

where moreover, for any $y\in Y,$

L\cap f^{-1}(y)\subseteq L\setminus R~

if and only if

~L\cap R\cap f^{-1}(y)=\varnothing ~

if and only if

~R\cap f^{-1}(y)\subseteq R\setminus L~

if and only if

~y\not \in f(L\cap R).

The sets $U$ and $V$ mentioned above could, in particular, be any of the sets $f(L\cup R),\;\operatorname {Im} f,$ or $Y,$ for example.

Images of preimages and preimages of images of set operations

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

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

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

{\begin{alignedat}{4}f^{-1}(f(L)\setminus f(L\setminus R))&=&&f^{-1}\left(\left\{y\in f(L\cap R)~:~L\cap f^{-1}(y)\subseteq R\right\}\right)\\&=&&\left\{x\in f^{-1}(f(L\cap R))~:~L\cap f^{-1}(f(x))\subseteq R\right\}\\\end{alignedat}}

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

{\begin{alignedat}{4}f^{-1}(Y\setminus f(L\setminus R))&~=~&&f^{-1}(f(X)\setminus f(L\setminus R))\\&=&&f^{-1}\left(\left\{y\in f(X)~:~L\cap f^{-1}(y)\subseteq R\right\}\right)\\&=&&\left\{x\in X~:~L\cap f^{-1}(f(x))\subseteq R\right\}\\&~=~&&X\setminus f^{-1}(f(L\setminus R))\\\end{alignedat}}

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

{\begin{alignedat}{4}f^{-1}(Y\setminus f(X\setminus R))&~=~&&f^{-1}(f(X)\setminus f(X\setminus R))\\&=&&f^{-1}\left(\left\{y\in f(R)~:~f^{-1}(y)\subseteq R\right\}\right)\\&=&&\left\{r\in R\cap X~:~f^{-1}(f(r))\subseteq R\right\}\\&\subseteq &&R\\\end{alignedat}}

and so

{\begin{alignedat}{4}f^{-1}(Y\setminus f(L))&~=~&&f^{-1}(f(X)\setminus f(L))\\&=&&f^{-1}\left(\left\{y\in f(X\setminus L)~:~f^{-1}(y)\cap L=\varnothing \right\}\right)\\&=&&\{x\in X\setminus L~:~f(x)\not \in f(L)\}\\&=&&X\setminus f^{-1}(f(L))\\&\subseteq &&X\setminus L\\\end{alignedat}}

(Pre)Images 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(L_{i}\right)_{i\in I}$ is a family of arbitrary sets indexed by $I\neq \varnothing$ then:[6]

{\begin{alignedat}{4}f\left(\bigcap _{i\in I}L_{i}\right)\;&~\;\color {Red}{\subseteq }\color {Black}{}~\;\;\;\bigcap _{i\in I}f\left(L_{i}\right)\\f\left(\bigcup _{i\in I}L_{i}\right)\;&~=~\;\bigcup _{i\in I}f\left(L_{i}\right)\\f^{-1}\left(\bigcup _{i\in I}L_{i}\right)\;&~=~\;\bigcup _{i\in I}f^{-1}\left(L_{i}\right)\\f^{-1}\left(\bigcap _{i\in I}L_{i}\right)\;&~=~\;\bigcap _{i\in I}f^{-1}\left(L_{i}\right)\\\end{alignedat}}

If all $L_{i}$ are $f$ -saturated then $\bigcap _{i\in I}L_{i}$ be will be $f$ -saturated and equality will hold in the first relation above; explicitly, this means:

f\left(\bigcap _{i\in I}L_{i}\right)~=~\bigcap _{i\in I}f\left(L_{i}\right)\qquad {\textit {IF}}\qquad X\cap L_{i}=f^{-1}\left(f\left(L_{i}\right)\right)\quad {\text{ for all }}\quad 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)\qquad {\textit {IF}}\qquad A_{i}=f^{-1}\left(f\left(A_{i}\right)\right)\quad {\text{ for all }}\quad 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\quad {\text{ to }}\quad \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}\quad {\text{ and }}\quad B~\subseteq ~\prod _{j\in J}Y_{j}\quad {\text{ then }}$

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

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

F^{-1}(B)~=~\bigcap _{j\in J}F_{j}^{-1}\left(\pi _{j}(B)\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}(B)=B_{j}$ for all $j\in J.$

Sequences of sets

Sequences of sets often arise in measure theory.

Definitions and notation

Throughout, $S{\text{ and }}T$ will be arbitrary sets and $S_{\bullet }$ and will denote a net or a sequence of sets where if it is a sequence then this will be indicated by either of the notations

S_{\bullet }=\left(S_{i}\right)_{i=1}^{\infty }\qquad {\text{ or }}\qquad S_{\bullet }=\left(S_{i}\right)_{i\in \mathbb {N} }

where $\mathbb {N}$ denotes the natural numbers. A notation $S_{\bullet }=\left(S_{i}\right)_{i\in I}$ indicates that $S_{\bullet }$ is a net directed by $(I,\leq ),$ which (by definition) is a sequence if the set $I,$ which is called the net's indexing set, is the natural numbers (that is, if $I=\mathbb {N}$ ) and $\,\leq \,$ is the natural order on $\mathbb {N} .$

Disjoint and monotone sequences

If $S_{i}\cap S_{j}=\varnothing$ for all distinct indices $i\neq j$ then $S_{\bullet }$ is called a pairwise disjoint or simply a disjoint. A sequence or net $S_{\bullet }$ of set is called increasing or non-decreasing if (resp. decreasing or non-increasing) if for all indices $i\leq j,$ $S_{i}\subseteq S_{j}$ (resp. $S_{i}\supseteq S_{j}$ ). A sequence or net $S_{\bullet }$ of set is called strictly increasing (resp. strictly decreasing) if it is non-decreasing (resp. is non-increasing) and also $S_{i}\neq S_{j}$ for all distinct indices $i{\text{ and }}j.$ It is called monotone if it is non-decreasing or non-increasing and it is called strictly monotone if it is strictly increasing or strictly decreasing.

A sequences or net $S_{\bullet }$ is said to increase to $S,$ ) denoted by $S_{\bullet }\uparrow S$ [12] or $S_{\bullet }\nearrow S,$ if $S_{\bullet }$ is increasing and the union of all $S_{i}$ is $S;$ that is, if

\bigcup _{n}S_{n}=S\qquad {\text{ and }}\qquad S_{i}\subseteq S_{j}\quad {\text{ whenever }}i\leq j.

It is said to decrease to $S,$ denoted by $S_{\bullet }\downarrow S$ [12] or $S_{\bullet }\searrow S,$ if $S_{\bullet }$ is increasing and the intersection of all $S_{i}$ is $S$ that is, if

\bigcap _{n}S_{n}=S\qquad {\text{ and }}\qquad S_{i}\supseteq S_{j}\quad {\text{ whenever }}i\leq j.

Basic properties

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

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

Partitions

Suppose that $S_{\bullet }=\left(S_{i}\right)_{i=1}^{\infty }$ is any sequence of sets, that $S\subseteq \bigcup _{i}S_{i}$ is any subset, and for every index $i,$ let $D_{i}:=\left(S_{i}\cap S\right)\setminus \bigcup _{m=1}^{i}\left(S_{m}\cap S\right).$ Then $S=\bigcup _{i}D_{i}$ and $D_{\bullet }:=\left(D_{i}\right)_{i=1}^{\infty }$ is a sequence of pairwise disjoint sets.[12]

Suppose that $S_{\bullet }=\left(S_{i}\right)_{i=1}^{\infty }$ is non-decreasing, let $S_{0}:=\varnothing ,$ and let $D_{i}:=S_{i}\setminus S_{i-1}$ for every $i=1,2,\ldots .$ Then $\bigcup _{i}S_{i}=\bigcup _{i}D_{i}$ and $D_{\bullet }:=\left(D_{i}\right)_{i=1}^{\infty }$ is a sequence of pairwise disjoint sets.[12]

Families and elementwise operations

Families ${\mathcal {F}}$ of sets over $\Omega$
Is necessarily true of ${\mathcal {F}}\colon$ or, is ${\mathcal {F}}$ closed under:	Directed by $\,\supseteq$	$A\cap B$	$A\cup B$	$B\setminus A$	$\Omega \setminus A$	$A_{1}\cap A_{2}\cap \cdots$	$A_{1}\cup A_{2}\cup \cdots$	$\Omega \in {\mathcal {F}}$	$\varnothing \in {\mathcal {F}}$	F.I.P.
$π$ -system
Semiring										Never
Semialgebra (Semifield)										Never
Monotone class						only if $A_{i}\searrow$	only if $A_{i}\nearrow$
𝜆-system (Dynkin System)				only if $A\subseteq B$			only if $A_{i}\nearrow$ or they are disjoint			Never
Ring (Order theory)
Ring (Measure theory)										Never
δ-Ring										Never
𝜎-Ring										Never
Algebra (Field)										Never
𝜎-Algebra (𝜎-Field)										Never
Dual ideal
Filter				Never	Never				$\varnothing \not \in {\mathcal {F}}$
Prefilter (Filter base)				Never	Never				$\varnothing \not \in {\mathcal {F}}$
Filter subbase				Never	Never				$\varnothing \not \in {\mathcal {F}}$
Topology							(even arbitrary unions)			Never
Is necessarily true of ${\mathcal {F}}\colon$ or, is ${\mathcal {F}}$ closed under:	directed downward	finite intersections	finite unions	relative complements	complements in $\Omega$	countable intersections	countable unions	contains $\Omega$	contains $\varnothing$	Finite Intersection Property
Additionally, a *semiring* is a $π$ -system where every complement $B\setminus A$ is equal to a finite disjoint union of sets in ${\mathcal {F}}.$ A *semialgebra* is a semiring that contains $\Omega .$ $A,B,A_{1},A_{2},\ldots$ are arbitrary elements of ${\mathcal {F}}$ and it is assumed that ${\mathcal {F}}\neq \varnothing .$

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 {L}}{\text{ and }}{\mathcal {R}}$ are families of sets and if $S$ is any set then define:[13]

{\mathcal {L}}\;(\cup )\;{\mathcal {R}}~\colon =~\{~L\cup R~:~L\in {\mathcal {L}}~{\text{ and }}~R\in {\mathcal {R}}~\}

{\mathcal {L}}\;(\cap )\;{\mathcal {R}}~\colon =~\{~L\cap R~:~L\in {\mathcal {L}}~{\text{ and }}~R\in {\mathcal {R}}~\}

{\mathcal {L}}\;(\setminus )\;{\mathcal {R}}~\colon =~\{~L\setminus R~:~L\in {\mathcal {L}}~{\text{ and }}~R\in {\mathcal {R}}~\}

{\mathcal {L}}\;(\triangle )\;{\mathcal {R}}~\colon =~\{~L\;\triangle \;R~:~L\in {\mathcal {L}}~{\text{ and }}~R\in {\mathcal {R}}~\}

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

which are respectively called elementwise union, elementwise intersection, elementwise (set) difference, elementwise symmetric difference, and the trace/restriction of ${\mathcal {L}}$ to $S.$ The regular union, intersection, and set difference are all defined as usual and are denoted with their usual notation: ${\mathcal {L}}\cup {\mathcal {R}},{\mathcal {L}}\cap {\mathcal {R}},{\mathcal {L}}\;\triangle \;{\mathcal {R}},$ and ${\mathcal {L}}\setminus {\mathcal {R}},$ respectively. These elementwise operations on families of sets play an important role in, among other subjects, the theory of filters and prefilters on sets.

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

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

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

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

Categories of families of sets

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

A family ${\mathcal {L}}$ is said to be:

closed under finite intersections (resp. closed under finite unions) if whenever $L,R\in {\mathcal {L}}$ then $L\cap R\in {\mathcal {L}}$ (respectively, $L\cup R\in {\mathcal {L}}$ ).
closed under countable intersections (resp. closed under countable unions) if whenever $L_{1},L_{2},L_{3},\ldots$ are elements of ${\mathcal {L}}$ then so is their intersections $\bigcap _{i=1}^{\infty }L_{i}:=L_{1}\cap L_{2}\cap L_{3}\cap \cdots$ (resp. so is their union $\bigcup _{i=1}^{\infty }L_{i}:=L_{1}\cup L_{2}\cup L_{3}\cup \cdots$ ).
closed under complementation in (or with respect to) $X$ if whenever $L\in {\mathcal {L}}$ then $X\setminus L\in {\mathcal {L}}.$

A family ${\mathcal {L}}$ of sets is called a/an:

$π$ −system if ${\mathcal {L}}\neq \varnothing$ $\text{[math]}$ and ${\mathcal {L}}$ $\text{[math]}$ is closed under finite-intersections.
- Every non-empty family ${\mathcal {L}}$ is contained in a unique smallest (with respect to $\subseteq$ ) $π$ −system that is denoted by $\pi ({\mathcal {L}})$ and called the $π$ −system generated by ${\mathcal {L}}.$
filter subbase and is said to have the finite intersection property if ${\mathcal {L}}\neq \varnothing$ and $\varnothing \not \in \pi ({\mathcal {L}}).$
filter on $X$ if ${\mathcal {L}}\neq \varnothing$ is a family of subsets of $X$ that is a $π$ −system, is upward closed in $X,$ and is also proper, which by definition means that it does not contain the empty set as an element.
prefilter or filter base if it is a non-empty family of subsets of some set $X$ whose upward closure in $X$ is a filter on $X.$
algebra on $X$ is a non-empty family of subsets of $X$ that contains the empty set, forms a $π$ −system, and is also closed under complementation with respect to $X.$
σ-algebra on $X$ is an algebra on $X$ that is closed under countable unions (or equivalently, closed under countable intersections).

Basic properties

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

Commutativity:[13]

{\mathcal {L}}\;(\cup )\;{\mathcal {R}}={\mathcal {R}}\;(\cup )\;{\mathcal {L}}

{\mathcal {L}}\;(\cap )\;{\mathcal {R}}={\mathcal {R}}\;(\cap )\;{\mathcal {L}}

Associativity:[13]

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

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

Identity:

{\mathcal {L}}\;(\cup )\;\{\varnothing \}={\mathcal {L}}

{\mathcal {L}}\;(\cap )\;\{X\}={\mathcal {L}}

{\mathcal {L}}\;(\setminus )\;\{\varnothing \}={\mathcal {L}}

Domination:

{\mathcal {L}}\;(\cup )\;\{X\}=\{X\}~~~~{\text{ if }}{\mathcal {L}}\neq \varnothing

{\mathcal {L}}\;(\cap )\;\{\varnothing \}=\{\varnothing \}~~~~{\text{ if }}{\mathcal {L}}\neq \varnothing

{\mathcal {L}}\;(\cup )\;\varnothing =\varnothing

{\mathcal {L}}\;(\cap )\;\varnothing =\varnothing

{\mathcal {L}}\;(\setminus )\;\varnothing =\varnothing

\varnothing \;(\setminus )\;{\mathcal {R}}=\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(L_{i}\cup R_{j}\right)~=~\bigcup _{i\in I}\left(L_{i}\cup R_{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 $L_{1}\colon =R_{2}\colon =X$ and let $L_{2}\colon =R_{1}\colon =\varnothing .$ Then $X=X\cap X=\left(L_{1}\cup L_{2}\right)\cap \left(R_{2}\cup R_{2}\right)=\left(\bigcup _{i\in I}L_{i}\right)\cap \left(\bigcup _{i\in I}R_{i}\right)~\neq ~\bigcup _{i\in I}\left(L_{i}\cap R_{i}\right)=\left(L_{1}\cap R_{1}\right)\cup \left(L_{2}\cap R_{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 $L\cap (X\cup Y)=\varnothing ,$ or that $L\cap X\neq \varnothing$ and $L\cap Y\neq \varnothing$ (which happens, for instance, if $X=Y$ ), etc.
The conclusion $X\setminus f^{-1}(R)=f^{-1}(Y\setminus R)$ can also be written as: $f^{-1}(R)^{\operatorname {C} }~=~f^{-1}\left(R^{\operatorname {C} }\right).$
Whether or not it is even feasible for the function $f$ to be constant and the sets $L\triangle R$ and $R$ to be non-empty and disjoint is irrelevant for reaching the correct conclusion about whether to use $\,\subseteq {\text{ or }}\supseteq .\,$
Note that this condition depends entirely on $R$ and not on $L.$

Let $f_{R}:=\left\{y\in f(L):L\cap f^{-1}(y)\subseteq R\right\}$ where because $f_{R}\subseteq f(R\cap L),$ $f_{R}$ is also equal to $f_{R}=\left\{y\in f(R\cap L):L\cap f^{-1}(y)\subseteq R\right\}.$ As proved above, $f(L\setminus R)=f(L)\setminus f_{R}$ so that $f(L)\setminus f(R)=f(L\setminus R)$ if and only if $f(L)\setminus f(R)=f(L)\setminus f_{R}.$ Since $f(L)\setminus f(R)=f(L)\setminus (f(L)\cap f(R)),$ this happens if and only if $f(L)\setminus (f(L)\cap f(R))=f(L)\setminus f_{R}.$ Because $f(L)\cap f(R){\text{ and }}f_{R}$ are both subsets of $f(L),$ the condition on the right hand side happens if and only if $f(L)\cap f(R)=f_{R}.$ Because $f_{R}\subseteq f(R\cap L)\subseteq f(L)\cap f(R),$ the equality $f(L)\cap f(R)=f_{R}$ holds if and only if $f(L)\cap f(R)\subseteq f_{R}.$ $\blacksquare$ If $f(R)\subseteq f(L)$ (such as when $L=X$ or $R\subseteq L$ ) then $f(L)\cap f(R)\subseteq f_{R}$ if and only if $f(R)\subseteq f_{R}.$ In particular, taking $L=X$ proves: $f(X\setminus R)=f(X)\setminus f(R)$ if and only if $f(R)\subseteq \left\{y\in f(R\cap X):f^{-1}(y)\subseteq R\right\},$ where $f(R\cap X)=f(R).$ $\blacksquare$
Let $(\star )$ denote the set equality $f(L\setminus R)=Y\setminus P$ where $P:=\left\{y\in Y:L\cap f^{-1}(y)\subseteq R\right\};$ this equality will now be proven. If $y\in Y\setminus P$ then $L\cap f^{-1}(y)\not \subseteq R$ so there exists some $x\in L\cap f^{-1}(y)\setminus R;$ now $f^{-1}(y)\subseteq X$ implies $x\in L\cap X\setminus R$ so that $y=f(x)\in f(L\cap X\setminus R)=f(L\setminus R).$ For the reverse inclusion, let $y\in f(L\setminus R)$ so that there exists some $x\in X\cap L\setminus R$ such that $y=f(x).$ Then $x\in L\cap f^{-1}(y)\setminus R$ so that $L\cap f^{-1}(y)\not \subseteq R$ and thus $y\not \in P,$ which proves that $y\in Y\setminus P,$ as desired. $\blacksquare$ Defining $Q:=\left\{y\in f(L):L\cap f^{-1}(y)\subseteq R\right\}=f(L)\cap P,$ the identity $f(L\setminus R)=f(L)\setminus Q$ follows from $(\star )$ and the inclusions $f(L\setminus R)\subseteq f(L)\subseteq Y.\blacksquare$

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.
Császár 1978, pp. 102–120.
Lee Halmos 1960, p. 39
Lee Munkres 2000, p. 19
Kelley 1985, p. 85
See Munkres 2000, p. 21
Lee p.388 of Lee, John M. (2010). Introduction to Topological Manifolds, 2nd Ed.
Durrett 2019, pp. 1–8.
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..
Bylinski, Czeslaw (2004). "Some Basic Properties of Sets". Journal of Formalized Mathematics. 1. Retrieved 5 October 2021.
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.
Durrett, Richard (2019). Probability: Theory and Examples (PDF). Cambridge Series in Statistical and Probabilistic Mathematics. Vol. 49 (5th ed.). Cambridge New York, NY: Cambridge University Press. ISBN 978-1-108-47368-2. OCLC 1100115281. Retrieved November 5, 2020.
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. Vol. 27 (2 ed.). Birkhäuser. ISBN 978-0-387-90125-1.
Köthe, Gottfried (1983) [1969]. Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. Vol. 159. Translated by Garling, D.J.H. New York: Springer Science & Business Media. 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.
Padlewska, Beata (1990). "Families of Sets". Journal of Formalized Mathematics. 1: 1–1. Retrieved 5 October 2021.
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.
Trybulec, Zinaida (2002). "Properties of subsets" (PDF). Journal of Formalized Mathematics. 1: 1–1. Retrieved 5 October 2021.
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 (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(L_{i}\cup R_{j}\right)~=~\bigcup _{i\in I}\left(L_{i}\cup R_{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 $L_{1}\colon =R_{2}\colon =X$ and let $L_{2}\colon =R_{1}\colon =\varnothing .$ Then $X=X\cap X=\left(L_{1}\cup L_{2}\right)\cap \left(R_{2}\cup R_{2}\right)=\left(\bigcup _{i\in I}L_{i}\right)\cap \left(\bigcup _{i\in I}R_{i}\right)~\neq ~\bigcup _{i\in I}\left(L_{i}\cap R_{i}\right)=\left(L_{1}\cap R_{1}\right)\cup \left(L_{2}\cap R_{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 $L\cap (X\cup Y)=\varnothing ,$ or that $L\cap X\neq \varnothing$ and $L\cap Y\neq \varnothing$ (which happens, for instance, if $X=Y$ ), etc.

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

[17] Whether or not it is even feasible for the function $f$ to be constant and the sets $L\triangle R$ and $R$ to be non-empty and disjoint is irrelevant for reaching the correct conclusion about whether to use $\,\subseteq {\text{ or }}\supseteq .\,$

[Depends_only_on_R-19] Note that this condition depends entirely on $R$ and not on $L.$

[proofCharOfPullingLminusR-20] Let $f_{R}:=\left\{y\in f(L):L\cap f^{-1}(y)\subseteq R\right\}$ where because $f_{R}\subseteq f(R\cap L),$ $f_{R}$ is also equal to $f_{R}=\left\{y\in f(R\cap L):L\cap f^{-1}(y)\subseteq R\right\}.$ As proved above, $f(L\setminus R)=f(L)\setminus f_{R}$ so that $f(L)\setminus f(R)=f(L\setminus R)$ if and only if $f(L)\setminus f(R)=f(L)\setminus f_{R}.$ Since $f(L)\setminus f(R)=f(L)\setminus (f(L)\cap f(R)),$ this happens if and only if $f(L)\setminus (f(L)\cap f(R))=f(L)\setminus f_{R}.$ Because $f(L)\cap f(R){\text{ and }}f_{R}$ are both subsets of $f(L),$ the condition on the right hand side happens if and only if $f(L)\cap f(R)=f_{R}.$ Because $f_{R}\subseteq f(R\cap L)\subseteq f(L)\cap f(R),$ the equality $f(L)\cap f(R)=f_{R}$ holds if and only if $f(L)\cap f(R)\subseteq f_{R}.$ $\blacksquare$ If $f(R)\subseteq f(L)$ (such as when $L=X$ or $R\subseteq L$ ) then $f(L)\cap f(R)\subseteq f_{R}$ if and only if $f(R)\subseteq f_{R}.$ In particular, taking $L=X$ proves: $f(X\setminus R)=f(X)\setminus f(R)$ if and only if $f(R)\subseteq \left\{y\in f(R\cap X):f^{-1}(y)\subseteq R\right\},$ where $f(R\cap X)=f(R).$ $\blacksquare$

[ProofImagesOfSetSubtractions-21] Let $(\star )$ denote the set equality $f(L\setminus R)=Y\setminus P$ where $P:=\left\{y\in Y:L\cap f^{-1}(y)\subseteq R\right\};$ this equality will now be proven. If $y\in Y\setminus P$ then $L\cap f^{-1}(y)\not \subseteq R$ so there exists some $x\in L\cap f^{-1}(y)\setminus R;$ now $f^{-1}(y)\subseteq X$ implies $x\in L\cap X\setminus R$ so that $y=f(x)\in f(L\cap X\setminus R)=f(L\setminus R).$ For the reverse inclusion, let $y\in f(L\setminus R)$ so that there exists some $x\in X\cap L\setminus R$ such that $y=f(x).$ Then $x\in L\cap f^{-1}(y)\setminus R$ so that $L\cap f^{-1}(y)\not \subseteq R$ and thus $y\not \in P,$ which proves that $y\in Y\setminus P,$ as desired. $\blacksquare$ Defining $Q:=\left\{y\in f(L):L\cap f^{-1}(y)\subseteq R\right\}=f(L)\cap P,$ the identity $f(L\setminus R)=f(L)\setminus Q$ follows from $(\star )$ and the inclusions $f(L\setminus R)\subseteq f(L)\subseteq Y.\blacksquare$

[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.

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

[halmos-1960-p39-13] Lee Halmos 1960, p. 39

[munkres-2000-p19-14] Lee Munkres 2000, p. 19

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

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

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

[FOOTNOTEDurrett20191–8-23] Durrett 2019, pp. 1–8.

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

List of set identities and relations

Notation

Finitely many sets and the algebra of sets

One subset involved

Two sets involved

Elementary operations characterized

Properties involving two sets

Subset inclusion

Meets, Joint, and lattice properties

Three sets involved

Associativity

Distributivity

Both operators are set subtraction

Set subtraction on the left

Set subtraction on the right

Three operators

Arbitrary families of sets

Definitions

Commutativity and associativity

Binary intersection of arbitrary unions

Binary union of arbitrary intersections

Arbitrary intersections and arbitrary unions

Distributive laws

Distributing subtraction

Intersections of products

Unions of products

Set subtraction of products

Functions and sets

Definitions

(Pre)Image of a single set

(Pre)Images of set operations

Counter-examples to set equality

Conditions for equality

Image of an intersection

Image of a set subtraction

Image of a set subtracted from the domain

Image of a symmetric difference

Image of set subtraction

Image of set subtraction from the domain

Image of symmetric difference

Image of a set

Image of set intersection

Images of preimages and preimages of images of set operations

(Pre)Images of unions and intersections

Preimage from a Cartesian product

Sequences of sets

Definitions and notation

Basic properties

Partitions

Families and elementwise operations

Definitions

Basic properties

See also

Notes

Citations

References

External links