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. On the left hand side of an identity, typically,

• $L$ will be the L eft most set,
• $M$ will be the M iddle set, and
• $R$ will be the R ight most set.

This is to facilitate applying identities to expressions that are complicated or use the same symbols as the identity. For example, the identity

$$(L\,\setminus \,M)\,\setminus \,R~=~(L\,\setminus \,R)\,\setminus \,(M\,\setminus \,R)$$

may be read as:

$$({\text{Left set}}\,\setminus \,{\text{Middle set}})\,\setminus \,{\text{Right set}}~=~({\text{Left set}}\,\setminus \,{\text{Right set}})\,\setminus \,({\text{Middle set}}\,\setminus \,{\text{Right set}}).$$

Elementary set operations

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

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

and

$$L\triangle R~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{~x~:~x{\text{ belongs to exactly one of }}L{\text{ and }}R~\}$$

where the symmetric difference $L\triangle R$ is sometimes denoted by $L\ominus R$ and equals:

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

One set $L$ is said to intersect another set $R$ if $L\cap R\neq \varnothing .$ Sets that do not intersect are said to be disjoint.

The power set of $X$ is the set of all subsets of $X$ and will be denoted by

$$\wp (X)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{~L~:~L\subseteq X~\}.$$

Universe set and complement notation

The notation

$$L^{\complement }~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~X\setminus L.$$

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

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

One subset involved

Assume $L\subseteq X.$

Identity:

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

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

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

but $\varnothing$ is not a left identity element of $\,\setminus \,$ since

$$\varnothing \setminus L=\varnothing$$

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

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

$${\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/Zero element:

$${\begin{alignedat}{10}X\cup L&\;=\;&&X&\;=\;&L\cup X~~~~{\text{ where }}L\subseteq X\\[1.4ex]\varnothing \cap L&\;=\;&&\varnothing &\;=\;&L\cap \varnothing \\[1.4ex]\varnothing \times L&\;=\;&&\varnothing &\;=\;&L\times \varnothing \\[1.4ex]\varnothing \setminus L&\;=\;&&\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^{\complement }\right)^{\complement }=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}}$$

$$L^{\complement }=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^{\complement }=X&&\quad &&{\text{ where }}L\subseteq X\\[1.4ex]L\,\triangle (X\setminus L)&=X&&\qquad {\text{ Also written }}\quad &&L\,\triangle L^{\complement }=X&&\quad &&{\text{ where }}L\subseteq X\\[1.4ex]L\,\cap (X\setminus L)&=\varnothing &&\qquad {\text{ Also written }}\quad &&L\cap L^{\complement }=\varnothing &&\quad &&\\[1.4ex]\end{alignedat}}$$

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

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

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

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^{\complement }:=X\setminus L{\text{ and }}R^{\complement }:=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^{\complement })&&\,\triangle \,&&(&&R^{\complement })&&\\\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}}$$

De Morgan's laws

De Morgan's laws state that 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)^{\complement }=L^{\complement }\cup R^{\complement }&&\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)^{\complement }=L^{\complement }\cap R^{\complement }&&\quad &&{\text{ (De Morgan's law)}}\\[1.4ex]\end{alignedat}}$$

Commutativity

Unions, intersection, and symmetric difference are commutative operations:

$${\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 identities involving two sets

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

Other properties

$${\begin{alignedat}{10}L\setminus R&=L\cap (X\setminus R)&&\qquad {\text{ Also written }}\quad &&L\setminus R=L\cap R^{\complement }&&\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)^{\complement }=L^{\complement }\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^{\complement }\setminus L^{\complement }&&\quad &&{\text{ where }}L,R\subseteq X\\[1.4ex]\end{alignedat}}$$

Intervals:

$$(a,b)\cap (c,d)=(\max\{a,c\},\min\{b,d\})$$

$$[a,b)\cap [c,d)=[\max\{a,c\},\min\{b,d\})$$

Subsets ⊆ and supersets ⊇

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

1. $L\subseteq R$
   • Definition of subset: if $l\in L$ then $l\in R$
3. $L\cap R=L$
4. $L\cup R=R$
5. $L\,\triangle \,R=R\setminus L$
6. $L\,\triangle \,R\subseteq R\setminus L$
7. $L\setminus R=\varnothing$
8. $L$ and $X\setminus R$ are disjoint (that is, $L\cap (X\setminus R)=\varnothing$)
9. $X\setminus R\subseteq X\setminus L\qquad$ (that is, $R^{\complement }\subseteq L^{\complement }$)

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

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

Set equality

See also: Extensionality

The following statements are equivalent:

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

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

Empty set

A set $L$ is empty if the sentence $\forall x(x\not \in L)$ is true, where the notation $x\not \in L$ is shorthand for $\lnot (x\in L).$

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

1. $L$ is not empty, meaning that the sentence $\lnot [\forall x(x\not \in L)]$ is true (literally, the logical negation of "$L$ is empty" holds true).
2. (In classical mathematics) $L$ is inhabited, meaning: $\exists x(x\in L)$
   • In constructive mathematics, "not empty" and "inhabited" are not equivalent: every inhabited set is not empty but the converse is not always guaranteed; that is, in constructive mathematics, a set $L$ that is not empty (where by definition, "$L$ is empty" means that the statement $\forall x(x\not \in L)$ is true) might not have an inhabitant (which is an $x$ such that $x\in L$).
3. $L\not \subseteq R$ for some set $R$

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

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

Given any $x,$

$$x\not \in L\setminus R\quad {\text{ if and only if }}\quad x\in L\cap R\;{\text{ or }}\;x\not \in L.$$

Moreover,

$$(L\setminus R)\cap R=\varnothing \qquad {\text{ always holds}}.$$

Meets, Joins, and lattice properties

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

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

$$L\subseteq L\cup R$$

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

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

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

Meets/infimums exist:

$$L\cap R\subseteq L$$

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

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

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

Other inclusion properties:

$$L\setminus R\subseteq L$$

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

• If $L\subseteq R$ then $L\,\triangle \,R=R\setminus L.$
• If $L\subseteq X$ and $R\subseteq Y$ then $L\times R\subseteq X\times Y$

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:

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

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

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

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$).

Distributivity and set subtraction \

Failure of set subtraction to left distribute:

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

$${\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 (the equalities on the left and right are De Morgan's laws) but equality is not guaranteed in general (that is, the containment ${\color {red}{\subseteq }}$ might be strict). Equality holds if and only if $L\,\setminus \,(M\,\cap \,R)\;\subseteq \;L\,\setminus \,(M\,\cup \,R),$ which happens if and only if $L\,\cap \,M=L\,\cap \,R.$

This observation about De Morgan's laws shows that $\,\setminus \,$ is 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:

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

Quasi-commutativity:

$$(L\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.$

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

Two set subtractions

Set subtraction is not associative in general:

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

since only the following is always guaranteed:

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

(L\M)\R

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

L\(M\R)

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

One set subtraction

(L\M) ⁎ R

Set subtraction on the left, and 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}}$

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

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

L\(M ⁎ R)

Set subtraction on the left, and 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}}$$

where the above two sets that are the subjects of De Morgan's laws always satisfy $L\,\setminus \,(M\,\cup \,R)~~{\color {red}{\subseteq }}~~\color {black}{\,}L\,\setminus \,(M\,\cap \,R).$

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

(L ⁎ M)\R

Set subtraction on the right, and 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}}$$

L ⁎ (M\R)

Set subtraction on the right, and 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}}$

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

Three operations on three sets

(L • M) ⁎ (M • R)

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\cup (L\cap 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}}$$

(L • M) ⁎ (R\M)

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

(L\M) ⁎ (L\R)

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 simplifications

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).$
• $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.$

Cartesian products ⨯ of finitely many sets

Binary ⋂ of finite ⨯

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

$$(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)$$

Binary ⋃ of finite ⨯

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

Difference \ of finite ⨯

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

Finite ⨯ of differences \

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

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

Symmetric difference ∆ and finite ⨯

$$L\times \left(R\,\triangle \,R_{2}\right)~=~\left[L\times \left(R\,\setminus \,R_{2}\right)\right]\,\cup \,\left[L\times \left(R_{2}\,\setminus \,R\right)\right]$$

$$\left(L\,\triangle \,L_{2}\right)\times R~=~\left[\left(L\,\setminus \,L_{2}\right)\times R\right]\,\cup \,\left[\left(L_{2}\,\setminus \,L\right)\times R\right]$$

$${\begin{alignedat}{4}\left(L\,\triangle \,L_{2}\right)\times \left(R\,\triangle \,R_{2}\right)~&=~&&&&\,\left[\left(L\cup L_{2}\right)\times \left(R\cup R_{2}\right)\right]\;\setminus \;\left[\left(\left(L\cap L_{2}\right)\times R\right)\;\cup \;\left(L\times \left(R\cap R_{2}\right)\right)\right]\\[0.7ex]&=~&&&&\,\left[\left(L\,\setminus \,L_{2}\right)\times \left(R_{2}\,\setminus \,R\right)\right]\,\cup \,\left[\left(L_{2}\,\setminus \,L\right)\times \left(R_{2}\,\setminus \,R\right)\right]\,\cup \,\left[\left(L\,\setminus \,L_{2}\right)\times \left(R\,\setminus \,R_{2}\right)\right]\,\cup \,\left[\left(L_{2}\,\setminus \,L\right)\cup \left(R\,\setminus \,R_{2}\right)\right]\\\end{alignedat}}$$

$${\begin{alignedat}{4}\left(L\,\triangle \,L_{2}\right)\times \left(M\,\triangle \,M_{2}\right)\times \left(R\,\triangle \,R_{2}\right)~&=~\left[\left(L\cup L_{2}\right)\times \left(M\cup M_{2}\right)\times \left(R\cup R_{2}\right)\right]\;\setminus \;\left[\left(\left(L\cap L_{2}\right)\times M\times R\right)\;\cup \;\left(L\times \left(M\cap M_{2}\right)\times R\right)\;\cup \;\left(L\times M\times \left(R\cap R_{2}\right)\right)\right]\\\end{alignedat}}$$

In general, $\left(L\,\triangle \,L_{2}\right)\times \left(R\,\triangle \,R_{2}\right)$ need not be a subset nor a superset of $\left(L\times R\right)\,\triangle \,\left(L_{2}\times R_{2}\right).$

$${\begin{alignedat}{4}\left(L\times R\right)\,\triangle \,\left(L_{2}\times R_{2}\right)~&=~&&\left(L\times R\right)\cup \left(L_{2}\times R_{2}\right)\;\setminus \;\left[\left(L\cap L_{2}\right)\times \left(R\cap R_{2}\right)\right]\\[0.7ex]\end{alignedat}}$$

$${\begin{alignedat}{4}\left(L\times M\times R\right)\,\triangle \,\left(L_{2}\times M_{2}\times R_{2}\right)~&=~&&\left(L\times M\times R\right)\cup \left(L_{2}\times M_{2}\times R_{2}\right)\;\setminus \;\left[\left(L\cap L_{2}\right)\times \left(M\cap M_{2}\right)\times \left(R\cap R_{2}\right)\right]\\[0.7ex]\end{alignedat}}$$

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 indexed families of sets. Whenever the assumption is needed, then all indexing sets, such as $I$ and $J,$ are assumed to be non-empty.

Definitions

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

An indexed family of sets is a function from some set, called its indexing set, into some family of sets. An indexed family of sets will be denoted by $\left(L_{i}\right)_{i\in I},$ where this notation assigns the symbol $I$ for the indexing set and for every index $i\in I,$ assigns the symbol $L_{i}$ to the value of the function at $i.$ The function itself may then be denoted by the symbol $L_{\bullet },$ which is obtained from the notation $\left(L_{i}\right)_{i\in I}$ by replacing the index $i$ with a bullet symbol $\bullet \,;$ explicitly, $L_{\bullet }$ is the function:

$${\begin{alignedat}{4}L_{\bullet }:\;&&I&&\;\to \;&\left\{L_{i}:i\in I\right\}\\[0.3ex]&&i&&\;\mapsto \;&L_{i}\\\end{alignedat}}$$

which may be summarized by writing $L_{\bullet }=\left(L_{i}\right)_{i\in I}.$

Any given indexed family of sets $L_{\bullet }=\left(L_{i}\right)_{i\in I}$ (which is a function) can be canonically associated with its image/range $\operatorname {Im} L_{\bullet }~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\left\{L_{i}:i\in I\right\}$ (which is a family of sets). Conversely, any given family of sets ${\mathcal {B}}$ may be associated with the ${\mathcal {B}}$-indexed family of sets $(B)_{B\in {\mathcal {B}}},$ which is technically the identity map ${\mathcal {B}}\to {\mathcal {B}}.$ However, this is not a bijective correspondence because an indexed family of sets $L_{\bullet }=\left(L_{i}\right)_{i\in I}$ is not required to be injective (that is, there may exist distinct indices $i\neq j$ such as $L_{i}=L_{j}$), which in particular means that it is possible for distinct indexed families of sets (which are functions) to be associated with the same family of sets (by having the same image/range).

Arbitrary unions defined

$$\bigcup _{i\in I}L_{i}~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{x~:~{\text{ there exists }}i\in I{\text{ such that }}x\in L_{i}\}$$

 

 

 

 

(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).

If ${\mathcal {B}}$ is a family of sets then $\cup {\mathcal {B}}$ denotes the set:

$$\bigcup {\mathcal {B}}~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\bigcup _{B\in {\mathcal {B}}}B~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{x~:~{\text{ there exists }}B\in {\mathcal {B}}{\text{ such that }}x\in B\}.$$

Arbitrary intersections defined

If $I\neq \varnothing$ then

$$\bigcap _{i\in I}L_{i}~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{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)

If ${\mathcal {B}}\neq \varnothing$ is a non-empty family of sets then $\cap {\mathcal {B}}$ denotes the set:

$$\bigcap {\mathcal {B}}~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\bigcap _{B\in B}B~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{x~:~x\in B{\text{ for every }}B\in {\mathcal {B}}\}~=~\{x~:~{\text{ for all }}B,{\text{ if }}B\in {\mathcal {B}}{\text{ then }}x\in B\}.$$

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, ${\textstyle \bigcap \limits _{i\in \varnothing }}L_{i}=\{x:{\text{ true }}\}$ consists of everything in the universe.

So if $I=\varnothing$ and:

1. if you are working in a model in which there exists some universe set $X$ then ${\textstyle \bigcap \limits _{i\in \varnothing }}L_{i}=\{x~:~x\in L_{i}{\text{ for every }}i\in \varnothing \}~=~X.$
2. 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 ${\textstyle \bigcap \limits _{i\in \varnothing }}L_{i}$ is undefined because ${\textstyle \bigcap \limits _{i\in \varnothing }}L_{i}$ consists of everything, which makes ${\textstyle \bigcap \limits _{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}~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\bigcup _{(i,j)\in I\times J}S_{i,j}$$

$$\bigcap _{\stackrel {i\in I,}{j\in J}}S_{i,j}~~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\bigcap _{(i,j)\in I\times J}S_{i,j}$$

Distributing unions and intersections

Binary ⋂ of arbitrary ⋃'s

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

 

 

 

 

(Eq. 3a)

and

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

 

 

 

 

(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)~$$
  (an example of this is given below). 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). Two exceptions are Eq. 2c (unions of unions) and Eq. 2d (intersections of intersections), but both of these are among the most trivial of set equalities (although even for these equalities there is still something that must be proven).
• Example where equality fails: 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 .$$
  Furthermore,
  $$\varnothing =\varnothing \cup \varnothing =\left(L_{1}\cap L_{2}\right)\cup \left(R_{2}\cap R_{2}\right)=\left(\bigcap _{i\in I}L_{i}\right)\cup \left(\bigcap _{i\in I}R_{i}\right)~\neq ~\bigcap _{i\in I}\left(L_{i}\cup R_{i}\right)=\left(L_{1}\cup R_{1}\right)\cap \left(L_{2}\cup R_{2}\right)=X\cap X=X.$$

Binary ⋃ of arbitrary ⋂'s

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

 

 

 

 

(Eq. 4a)

and

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

 

 

 

 

(Eq. 4b)

• Importantly, if $I=J$ then in general,
  $$~\left(\bigcap _{i\in I}L_{i}\right)\cup \left(\bigcap _{i\in I}R_{i}\right)~~\color {Red}{\neq }\color {Black}{}~~\bigcap _{i\in I}\left(L_{i}\cup R_{i}\right)~$$
  (an example of this is given above). The single intersection on the right hand side must be over all pairs $(i,j)\in I\times I:$
  $$~\left(\bigcap _{i\in I}L_{i}\right)\cup \left(\bigcap _{i\in I}R_{i}\right)~~=~~\bigcap _{\stackrel {i\in I,}{j\in I}}\left(L_{i}\cup R_{j}\right).~$$

Arbitrary ⋂'s and arbitrary ⋃'s

Incorrectly distributing by swapping ⋂ and ⋃

Naively swapping $\;{\textstyle \bigcup \limits _{i\in I}}\;$ and $\;{\textstyle \bigcap \limits _{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; and analogously, the left hand side depends on how for each fixed $j\in J,$ the sets $\left(S_{i,j}\right)_{i\in I}$ are labelled. An example demonstrating this is now given.

• Example of dependence on labeling and failure of equality: To see why equality need not hold when $\cup$ and $\cap$ are swapped, let $I\colon =J\colon =\{1,2\},$ and let $S_{11}=\{1,2\},~S_{12}=\{1,3\},~S_{21}=\{3,4\},$ and $S_{22}=\{2,4\}.$ Then
  $$\{1,4\}=\{1\}\cup \{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}\colon =\{3,4\},~{\hat {S}}_{12}\colon =\{1,3\},~{\hat {S}}_{21}\colon =\{1,2\},$ and ${\hat {S}}_{22}\colon =\{2,4\},$ then
  $$\{2,3\}=\{3\}\cup \{2\}=\left({\hat {S}}_{11}\cap {\hat {S}}_{12}\right)\cup \left({\hat {S}}_{21}\cap {\hat {S}}_{22}\right)=\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)=\left({\hat {S}}_{11}\cup {\hat {S}}_{21}\right)\cap \left({\hat {S}}_{12}\cup {\hat {S}}_{22}\right)=\{1,2,3,4\}.$$
  In particular, the left hand side is no longer $\{1,4\},$ which shows that the left hand side ${\textstyle \bigcup \limits _{i\in I}}\;{\textstyle \bigcap \limits _{j\in J}}S_{i,j}$ depends on how the sets are labelled. If instead $S_{11}$ and $S_{12}$ are swapped while $S_{21}$ and $S_{22}$