List of set identities and relations

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 leftmost set,
• $M$ will be the middle set, and
• $R$ will be the rightmost set.

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

For example, the expression $(M\; \backslash setminus\; R)\; \backslash setminus\; A$ uses two of the same symbols ($M$ and $R$) that appear in the identity

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

but they refer to different sets in each expression.

To apply this identity to $(M\; \backslash setminus\; R)\; \backslash setminus\; A,$ substitute $\backslash text\{Left\; set\}\; :=\; M,\backslash ;$ $\backslash text\{Middle\; set\}\; :=\; R,\backslash ;$ and $\backslash text\{Right\; set\}\; :=\; A$ (since these are the left, middle, and right sets in $(M\; \backslash setminus\; R)\; \backslash setminus\; A$) to obtain:

$$\backslash begin\{alignat\}\{4\}$$

(M \setminus R) \setminus A

&= (\text{Left set } &&\setminus \text{Right set}&&) &&\setminus (\text{Middle set } &&\setminus \text{Right set}) \\

&= (M &&\setminus A&&) &&\setminus (R &&\setminus A). \\

\end{alignat}

For a second example, this time applying the identity to $((M\; \backslash cap\; R\; \backslash setminus\; L)\; \backslash setminus\; (A\; \backslash triangle\; L))\; \backslash setminus\; L,$ is now given. The identity $(L\; \backslash setminus\; M)\; \backslash setminus\; R\; =\; (L\; \backslash setminus\; R)\; \backslash setminus\; (M\; \backslash setminus\; R)$ can be applied to $((M\; \backslash cap\; R\; \backslash setminus\; L)\; \backslash setminus\; (A\; \backslash triangle\; L))\; \backslash setminus\; L$ by reading $L,\; M,$ and $R$ as $\backslash text\{Left\},\; \backslash text\{Middle\},$ and $\backslash text\{Right\}$ and then substituting $\backslash text\{Left\}\; =\; (M\; \backslash cap\; R\; \backslash setminus\; L),$ $\backslash text\{Middle\}\; =\; (A\; \backslash triangle\; L),$ and $\backslash text\{Right\}\; =\; L$ to obtain:

$$\backslash begin\{alignat\}\{4\}$$

((M \cap R \setminus L) \setminus (A \triangle L)) \setminus L

&= (\text{Left } &&\setminus \text{Right}&&) &&\setminus (\text{Middle } &&\setminus \text{Right}) \\

&= ((M \cap R \setminus L) &&\setminus L&&) &&\setminus ((A \triangle L) &&\setminus L). \\

\end{alignat}

For example, the identity

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

may be read as:

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

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

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

and

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

where the {{em|symmetric difference}} $L\; \backslash triangle\; R$ is sometimes denoted by $L\; \backslash ominus\; R$ and equals:{{Cite web|last=Taylor|first=Courtney|date=March 31, 2019|title=What Is Symmetric Difference in Math?|url=https://www.thoughtco.com/what-is-the-symmetric-difference-3126594|access-date=2020-09-05|website=ThoughtCo|language=en}}{{Cite web|last=Weisstein|first=Eric W.|title=Symmetric Difference|url=https://mathworld.wolfram.com/SymmetricDifference.html|access-date=2020-09-05|website=mathworld.wolfram.com|language=en}}

$$\backslash begin\{alignat\}\{4\}$$

L \;\triangle\; R

~&=~ (L ~\setminus~ &&R) ~\cup~ &&(R ~\setminus~ &&L) \\

~&=~ (L ~\cup~ &&R) ~\setminus~ &&(L ~\cap~ &&R).

\end{alignat}

One set $L$ is said to {{em|intersect}} another set $R$ if $L\; \backslash cap\; R\; \backslash neq\; \backslash varnothing.$ Sets that do not intersect are said to be {{em|disjoint}}.

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

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

Universe set and complement notation

The notation

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

may be used if $L$ is a subset of some set $X$ that is understood (say from context, or because it is clearly stated what the superset $X$ is).

It is emphasized that the definition of $L^\backslash 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^\backslash complement$ would likely mean $Y\; \backslash setminus\; L$ instead of $X\; \backslash 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^\backslash complement$ where unless indicated otherwise, it should be assumed that $L^\backslash complement$ denotes the complement of $L$ in (the universe) $X.$

Assume $L\; \backslash subseteq\; X.$

Identity:{{sfn|Monk|1969|pp=24-54}}

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

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

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

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

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

so $\backslash varnothing\; \backslash setminus\; L\; =\; L$ if and only if $L\; =\; \backslash varnothing.$

Idempotence{{sfn|Monk|1969|pp=24-54}} $L\; \backslash ast\; L\; =\; L$ and Nilpotence $L\; \backslash ast\; L\; =\; \backslash varnothing$:

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

Domination{{sfn|Monk|1969|pp=24-54}}/Absorbing element:

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

A universe set is an absorbing element of binary union $\backslash cup.$ The empty set $\backslash varnothing$ is an absorbing element of binary intersection $\backslash cap$ and binary Cartesian product $\backslash times,$ and it is also a left absorbing element of set subtraction $\backslash ,\; \backslash setminus:$

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

but $\backslash varnothing$ is not a right absorbing element of set subtraction since

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

where $L\; \backslash setminus\; \backslash varnothing\; =\; \backslash varnothing$ if and only if $L\; =\; \backslash varnothing.$

Double complement or involution law:

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

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

$$\backslash begin\{alignat\}\{4\}$$

\varnothing

&= L &&\setminus L \\

&= \varnothing &&\setminus L \\

&= L &&\setminus X ~~~~\text{ where } L \subseteq X \\

\end{alignat}{{sfn|Monk|1969|pp=24-54}}

$$L^\backslash complement\; =\; X\; \backslash setminus\; L\; \backslash quad\; \backslash text\{\; (definition\; of\; notation)\}$$

$$\backslash begin\{alignat\}\{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{alignat}{{sfn|Monk|1969|pp=24-54}}

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

In the left hand sides of the following identities, $L$ is the {{em|L}}{{hsp}}eft most set and $R$ is the {{em|R}}{{hsp}}ight most set.

Assume both $L\; \backslash text\{\; and\; \}\; R$ are subsets of some universe set $X.$

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

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

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

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

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

De Morgan's laws state that for $L,\; R\; \backslash subseteq\; X:$

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

Unions, intersection, and symmetric difference are commutative operations:{{sfn|Monk|1969|pp=24-54}}

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

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

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

Said differently, if distinct symbols always represented distinct sets, then the {{em|only}} true formulas of the form $\backslash ,\backslash cdot\backslash ,\; \backslash ,\backslash setminus\backslash ,\; \backslash ,\backslash cdot\backslash ,\; =\; \backslash ,\backslash cdot\backslash ,\; \backslash ,\backslash setminus\backslash ,\; \backslash ,\backslash cdot\backslash ,$ that could be written would be those involving a single symbol; that is, those of the form: $S\; \backslash ,\backslash setminus\backslash ,\; S\; =\; S\; \backslash ,\backslash setminus\backslash ,\; S.$

But such formulas are necessarily true for {{em|every}} binary operation $\backslash ,\backslash ast\backslash ,$ (because $x\; \backslash ,\backslash ast\backslash ,\; x\; =\; x\; \backslash ,\backslash ast\backslash ,\; 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\; \backslash setminus\; L)\; \backslash setminus\; R\; =\; L\; \backslash setminus\; (L\; \backslash setminus\; R)$ if and only if $L\; \backslash cap\; R\; =\; \backslash varnothing$ if and only if $(R\; \backslash setminus\; L)\; \backslash setminus\; L\; =\; R\; \backslash setminus\; (L\; \backslash setminus\; L).$

Set subtraction is quasi-commutative and satisfies the Jordan identity.

Absorption laws:

$$\backslash begin\{alignat\}\{4\}$$

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

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

\end{alignat}

Other properties

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

Intervals:

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

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

The following statements are equivalent for any $L,\; R\; \backslash subseteq\; X:${{sfn|Monk|1969|pp=24-54}}

1. $L\; \backslash subseteq\; R$
   • Definition of {{em|subset}}: if $l\; \backslash in\; L$ then $l\; \backslash in\; R$

3. $L\; \backslash cap\; R\; =\; L$
4. $L\; \backslash cup\; R\; =\; R$
5. $L\; \backslash ,\backslash triangle\backslash ,\; R\; =\; R\; \backslash setminus\; L$
6. $L\; \backslash ,\backslash triangle\backslash ,\; R\; \backslash subseteq\; R\; \backslash setminus\; L$
7. $L\; \backslash setminus\; R\; =\; \backslash varnothing$
8. $L$ and $X\; \backslash setminus\; R$ are disjoint (that is, $L\; \backslash cap\; (X\; \backslash setminus\; R)\; =\; \backslash varnothing$)
9. $X\; \backslash setminus\; R\; \backslash subseteq\; X\; \backslash setminus\; L\; \backslash qquad$ (that is, $R^\backslash complement\; \backslash subseteq\; L^\backslash complement$)

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

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

{{See also|Extensionality}}

The following statements are equivalent:

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

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

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

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

1. $L$ is not empty, meaning that the sentence $\backslash lnot\; [\backslash forall\; x\; (x\; \backslash not\backslash in\; L)]$ is true (literally, the logical negation of "$L$ is empty" holds true).
2. (In classical mathematics) $L$ is inhabited, meaning: $\backslash exists\; x\; (x\; \backslash 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 $\backslash forall\; x\; (x\; \backslash not\backslash in\; L)$ is true) might not have an inhabitant (which is an $x$ such that $x\; \backslash in\; L$).

3. $L\; \backslash not\backslash subseteq\; R$ for some set $R$

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

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

Given any $x,$ the following are equivalent:

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

Moreover,

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

Inclusion is a partial order:

Explicitly, this means that inclusion $\backslash ,\backslash subseteq,\backslash ,$ which is a binary operation, has the following three properties:{{sfn|Monk|1969|pp=24-54}}

• Reflexivity:

  $L\; \backslash subseteq\; L$

• Antisymmetry:

  $(L\; \backslash subseteq\; R\; \backslash text\{\; and\; \}\; R\; \backslash subseteq\; L)\; \backslash text\{\; if\; and\; only\; if\; \}\; L\; =\; R$

• Transitivity:

  $\backslash text\{If\; \}L\; \backslash subseteq\; M\; \backslash text\{\; and\; \}\; M\; \backslash subseteq\; R\; \backslash text\{\; then\; \}\; L\; \backslash subseteq\; R$

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

Existence of a least element and a greatest element:

$$\backslash varnothing\; \backslash subseteq\; L\; \backslash subseteq\; X$$

Joins/supremums exist:{{sfn|Monk|1969|pp=24-54}}

$$L\; \backslash subseteq\; L\; \backslash cup\; R$$

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

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

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

Meets/infimums exist:{{sfn|Monk|1969|pp=24-54}}

$$L\; \backslash cap\; R\; \backslash subseteq\; L$$

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

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

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

Other inclusion properties:

$$L\; \backslash setminus\; R\; \backslash subseteq\; L$$

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

• If $L\; \backslash subseteq\; R$ then $L\; \backslash ,\backslash triangle\backslash ,\; R\; =\; R\; \backslash setminus\; L.$
• If $L\; \backslash subseteq\; X$ and $R\; \backslash subseteq\; Y$ then $L\; \backslash times\; R\; \backslash subseteq\; X\; \backslash times\; Y${{sfn|Monk|1969|pp=24-54}}

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

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\; \backslash cap\; R\; =\; \backslash \{x\; :\; (x\; \backslash in\; L)\; \backslash land\; (x\; \backslash in\; R)\backslash \}$ with logical conjunction (and) $L\; \backslash land\; R$ and associate union $L\; \backslash cup\; R\; =\; \backslash \{x\; :\; (x\; \backslash in\; L)\; \backslash lor\; (x\; \backslash in\; R)\backslash \}$ with logical disjunction (or) $L\; \backslash lor\; R,$ and then transfer the precedence of these logical operators (where $\backslash ,\backslash land\backslash ,$ has precedence over $\backslash ,\backslash lor\backslash ,$) to these set operators, thereby giving $\backslash ,\backslash cap\backslash ,$ precedence over $\backslash ,\backslash cup.\backslash ,$

So for example, $L\; \backslash cup\; M\; \backslash cap\; R$ would mean $L\; \backslash cup\; (M\; \backslash cap\; R)$ since it would be associated with the logical statement $L\; \backslash lor\; M\; \backslash land\; R\; ~=~\; L\; \backslash lor\; (M\; \backslash land\; R)$ and similarly, $L\; \backslash cup\; M\; \backslash cap\; R\; \backslash cup\; Z$ would mean $L\; \backslash cup\; (M\; \backslash cap\; R)\; \backslash cup\; Z$ since it would be associated with $L\; \backslash lor\; M\; \backslash land\; R\; \backslash lor\; Z\; ~=~\; L\; \backslash lor\; (M\; \backslash land\; R)\; \backslash lor\; Z.$

Sometimes, set complement (subtraction) $\backslash ,\backslash setminus\backslash ,$ is also associated with logical complement (not) $\backslash ,\backslash lnot,\backslash ,$ in which case it will have the highest precedence.

More specifically, $L\; \backslash setminus\; R\; =\; \backslash \{x\; :\; (x\; \backslash in\; L)\; \backslash land\; \backslash lnot\; (x\; \backslash in\; R)\backslash \}$ is rewritten $L\; \backslash land\; \backslash lnot\; R$ so that for example, $L\; \backslash cup\; M\; \backslash setminus\; R$ would mean $L\; \backslash cup\; (M\; \backslash setminus\; R)$ since it would be rewritten as the logical statement $L\; \backslash lor\; M\; \backslash land\; \backslash lnot\; R$ which is equal to $L\; \backslash lor\; (M\; \backslash land\; \backslash lnot\; R).$

For another example, because $L\; \backslash land\; \backslash lnot\; M\; \backslash land\; R$ means $L\; \backslash land\; (\backslash lnot\; M)\; \backslash land\; R,$ which is equal to both $(L\; \backslash land\; (\backslash lnot\; M))\; \backslash land\; R$ and $L\; \backslash land\; ((\backslash lnot\; M)\; \backslash land\; R)\; ~=~\; L\; \backslash land\; (R\; \backslash land\; (\backslash lnot\; M))$ (where $(\backslash lnot\; M)\; \backslash land\; R$ was rewritten as $R\; \backslash land\; (\backslash lnot\; M)$), the formula $L\; \backslash setminus\; M\; \backslash cap\; R$ would refer to the set $(L\; \backslash setminus\; M)\; \backslash cap\; R\; =\; L\; \backslash cap\; (R\; \backslash setminus\; M);$

moreover, since $L\; \backslash land\; (\backslash lnot\; M)\; \backslash land\; R\; =\; (L\; \backslash land\; R)\; \backslash land\; \backslash lnot\; M,$ this set is also equal to $(L\; \backslash cap\; R)\; \backslash setminus\; M$ (other set identities can similarly be deduced from propositional calculus identities in this way).

However, because set subtraction is not associative $(L\; \backslash setminus\; M)\; \backslash setminus\; R\; \backslash neq\; L\; \backslash setminus\; (M\; \backslash setminus\; R),$ a formula such as $L\; \backslash setminus\; M\; \backslash setminus\; R$ would be ambiguous; for this reason, among others, set subtraction is often not assigned any precedence at all.

Symmetric difference $L\; \backslash triangle\; R\; =\; \backslash \{x\; :\; (x\; \backslash in\; L)\; \backslash oplus\; (x\; \backslash in\; R)\backslash \}$ is sometimes associated with exclusive or (xor) $L\; \backslash oplus\; R$ (also sometimes denoted by $\backslash ,\backslash veebar$), in which case if the order of precedence from highest to lowest is $\backslash ,\backslash lnot,\; \backslash ,\backslash oplus,\; \backslash ,\backslash land,\; \backslash ,\backslash lor\backslash ,$ then the order of precedence (from highest to lowest) for the set operators would be $\backslash ,\backslash setminus,\backslash ,\; \backslash triangle,\backslash ,\; \backslash cap,\backslash ,\; \backslash cup.$

There is no universal agreement on the precedence of exclusive disjunction $\backslash ,\backslash oplus\backslash ,$ with respect to the other logical connectives, which is why symmetric difference $\backslash ,\backslash triangle\backslash ,$ is not often assigned a precedence.

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

The following set operators are associative:{{sfn|Monk|1969|pp=24-54}}

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

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

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

where equality holds if and only if $L\; \backslash cap\; R\; =\; \backslash varnothing$ (this condition does not depend on $M$). Thus

$\backslash ;\; (L\; \backslash setminus\; M)\; \backslash setminus\; R\; =\; L\; \backslash setminus\; (M\; \backslash setminus\; R)\; \backslash ;$ if and only if $\backslash ;\; (R\; \backslash setminus\; M)\; \backslash setminus\; L\; =\; R\; \backslash setminus\; (M\; \backslash setminus\; L),\; \backslash ;$

where the only difference between the left and right hand side set equalities is that the locations of $L\; \backslash text\{\; and\; \}\; R$ have been swapped.

Definition: If $\backslash ast\; \backslash text\{\; and\; \}\; \backslash bullet$ are binary operators then {{em|$\backslash ,\backslash ast\backslash ,$ left distributes over $\backslash ,\backslash bullet\backslash ,$}} if $$L\; \backslash ,\backslash ast\backslash ,\; (M\; \backslash ,\backslash bullet\backslash ,\; R)\; ~=~\; (L\; \backslash ,\backslash ast\backslash ,\; M)\; \backslash ,\backslash bullet\backslash ,\; (L\; \backslash ,\backslash ast\backslash ,R)\; \backslash qquad\backslash qquad\; \backslash text\{\; for\; all\; \}\; L,\; M,\; R$$

while {{em|$\backslash ,\backslash ast\backslash ,$ right distributes over $\backslash ,\backslash bullet\backslash ,$}} if $$(L\; \backslash ,\backslash bullet\backslash ,\; M)\; \backslash ,\backslash ast\backslash ,\; R\; ~=~\; (L\; \backslash ,\backslash ast\backslash ,\; R)\; \backslash ,\backslash bullet\backslash ,\; (M\; \backslash ,\backslash ast\backslash ,R)\; \backslash qquad\backslash qquad\; \backslash text\{\; for\; all\; \}\; L,\; M,\; R.$$

The operator {{em|$\backslash ,\backslash ast\backslash ,$ distributes over $\backslash ,\backslash bullet\backslash ,$}} if it both left distributes and right distributes over $\backslash ,\backslash bullet\backslash ,.\backslash ,$

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:{{sfn|Monk|1969|pp=24-54}}

$$\backslash begin\{alignat\}\{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 \,\triangle\, M) \,\times\, R ~&~~=~~&& (L \,\times\, R) \,&&\triangle\, &&(M \,\times\, R) \qquad

&&\text{ (Right-distributivity of } \,\times\, \text{ over } \,\triangle\, \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{alignat}

Left distributivity:{{sfn|Monk|1969|pp=24-54}}

$$\backslash begin\{alignat\}\{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]

L \times (M \,\triangle R) &\;=\;\;&& (L \times M) \,\triangle (L \times R)

&&\text{ (Left-distributivity of } \,\times\, \text{ over } \,\triangle\, \text{)} \\[1.4ex]

\end{alignat}

Intersection distributes over symmetric difference:

$$\backslash begin\{alignat\}\{5\}$$

L \,\cap\, (M \,\triangle\, R) ~&~~=~~&& (L \,\cap\, M) \,\triangle\, (L \,\cap\, R) ~&&~ \\[1.4ex]

\end{alignat}

$$\backslash begin\{alignat\}\{5\}$$

(L \,\triangle\, M) \,\cap\, R~&~~=~~&& (L \,\cap\, R) \,\triangle\, (M \,\cap\, R) ~&&~ \\[1.4ex]

\end{alignat}

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

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

Symmetric difference does not distribute over itself:

$$L\; \backslash ,\backslash triangle\backslash ,\; (M\; \backslash ,\backslash triangle\backslash ,\; R)$$

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

~=~ M \,\triangle\, R

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

Failure of set subtraction to left distribute:

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

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

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

For symmetric difference, the sets $L\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash triangle\backslash ,\; R)$ and $(L\; \backslash ,\backslash setminus\backslash ,\; M)\; \backslash ,\backslash triangle\backslash ,\; (L\; \backslash ,\backslash setminus\backslash ,\; R)\; =\; L\; \backslash ,\backslash cap\backslash ,\; (M\; \backslash ,\backslash triangle\backslash ,\; R)$ are always disjoint.

So these two sets are equal if and only if they are both equal to $\backslash varnothing.$

Moreover, $L\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash triangle\backslash ,\; R)\; =\; \backslash varnothing$ if and only if $L\; \backslash cap\; M\; \backslash cap\; R\; =\; \backslash varnothing\; \backslash text\{\; and\; \}\; L\; \backslash subseteq\; M\; \backslash 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:

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

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 $\{\backslash color\{red\}\{\backslash subseteq\}\}$ might be strict).

Equality holds if and only if $L\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash cap\backslash ,\; R)\; \backslash ;\backslash subseteq\backslash ;\; L\; \backslash ,\backslash setminus\backslash ,\; (M\; \backslash ,\backslash cup\backslash ,\; R),$ which happens if and only if $L\; \backslash ,\backslash cap\backslash ,\; M\; =\; L\; \backslash ,\backslash cap\backslash ,\; R.$

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

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

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

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

The following statements are equivalent:

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

Quasi-commutativity:

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

always holds but in general,

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

However, $L\; \backslash setminus\; (M\; \backslash setminus\; R)\; ~\backslash subseteq~\; L\; \backslash setminus\; (R\; \backslash setminus\; M)$ if and only if $L\; \backslash cap\; R\; ~\backslash subseteq~\; M$ if and only if $L\; \backslash setminus\; (R\; \backslash 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 $\backslash ,\backslash cup,\; \backslash ,\backslash cap,$ and $\backslash triangle,\backslash ,$ set subtraction is neither associative nor commutative and it also is not left distributive over $\backslash ,\backslash cup,\; \backslash ,\backslash cap,\; \backslash ,\backslash triangle,$ or even over itself.

Set subtraction is {{em|not}} associative in general:

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

since only the following is always guaranteed:

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

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

$$\backslash begin\{alignat\}\{4\}$$

L \setminus (M \setminus R)

&= (L \setminus M) \cup (L \cap R) \\[1.4ex]

\end{alignat}

:* If $L\; \backslash subseteq\; M\; \backslash text\{\; then\; \}\; L\; \backslash setminus\; (M\; \backslash setminus\; R)\; =\; L\; \backslash cap\; R$

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

Set subtraction on the left, and parentheses on the {{em|left}}

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

:$\backslash begin\{alignat\}\{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{alignat}{{sfn|Császár|1978|pp=15-26}}

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

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

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

Set subtraction on the left, and parentheses on the {{em|right}}

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

$$\backslash begin\{alignat\}\{4\}$$

L \setminus (M \cap R)

&= (L \setminus M) \cup (L \setminus R) ~~~~\text{ (De Morgan's law) } \\

\end{alignat}

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

$$\backslash begin\{alignat\}\{4\}$$

L \setminus (M ~\triangle~ R)

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

\end{alignat}

Set subtraction on the right, and parentheses on the {{em|left}}

$$\backslash begin\{alignat\}\{4\}$$

(L \cup M) \setminus R

&= (L \setminus R) \cup (M \setminus R) \\

\end{alignat}

$$\backslash begin\{alignat\}\{4\}$$

(L \cap M) \setminus R

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

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

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

\end{alignat}

$$\backslash begin\{alignat\}\{4\}$$

(L \,\triangle\, M) \setminus R

&= (L \setminus R) ~&&\triangle~ (M \setminus R) \\

&= (L \cup R) ~&&\triangle~ (M \cup R) \\

\end{alignat}

Set subtraction on the right, and parentheses on the {{em|right}}

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

:$\backslash begin\{alignat\}\{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{alignat}

{{sfn|Császár|1978|pp=15-26}}

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

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

$$\backslash begin\{alignat\}\{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 \cap (L \cup 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{alignat}

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

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

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

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

Other properties:

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

• If $L\; \backslash subseteq\; M$ then $L\; \backslash setminus\; R\; =\; L\; \backslash cap\; (M\; \backslash setminus\; R).${{sfn|Császár|1978|pp=15-26}}
• $L\; \backslash times\; (M\; \backslash ,\backslash setminus\; R)\; =\; (L\; \backslash times\; M)\; \backslash ,\backslash setminus\; (L\; \backslash times\; R)$
• If $L\; \backslash subseteq\; R$ then $M\; \backslash setminus\; R\; \backslash subseteq\; M\; \backslash setminus\; L.$
• $L\; \backslash cap\; M\; \backslash cap\; R\; =\; \backslash varnothing$ if and only if for any $x\; \backslash in\; L\; \backslash cup\; M\; \backslash cup\; R,$ $x$ belongs to {{em|at most two}} of the sets $L,\; M,\; \backslash text\{\; and\; \}\; R.$

Given finitely many sets $L\_1,\; \backslash ldots,\; L\_n,$ something belongs to their symmetric difference if and only if it belongs to an odd number of these sets. Explicitly, for any $x,$ $x\; \backslash in\; L\_1\; \backslash triangle\; \backslash cdots\; \backslash triangle\; L\_n$ if and only if the cardinality $\backslash left|\backslash left\backslash \{i\; :\; x\; \backslash in\; L\_i\backslash right\backslash \}\backslash right|$ is odd. (Recall that symmetric difference is associative so parentheses are not needed for the set $L\_1\; \backslash triangle\; \backslash cdots\; \backslash triangle\; L\_n$).

Consequently, the symmetric difference of three sets satisfies:

$$\backslash begin\{alignat\}\{4\}$$

L \,\triangle\, M \,\triangle\, R

&= (L \cap M \cap R) \cup \{x : x \text{ belongs to exactly one of the sets } L, M, R \} ~~~~~~ \text{ (the union is disjoint) } \\

&= [L \cap M \cap R] \cup [L \setminus (M \cup R)] \cup [M \setminus (L \cup R)] \cup [R \setminus (L \cup M)] ~~~~~~~~~ \text{ (all 4 sets enclosed by [ ] are pairwise disjoint) } \\

\end{alignat}

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

$$\backslash begin\{alignat\}\{9\}$$

(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 \,\triangle\, M) \,\times\, R ~&~~=~~&& (L \,\times\, R) \,&&\triangle\, &&(M \,\times\, R) \qquad

&&\text{ (Right-distributivity of } \,\times\, \text{ over } \,\triangle\, \text{)} \\[1.4ex]

\end{alignat}

$$\backslash begin\{alignat\}\{5\}$$

L \times (M \cap R) &\;=\;\;&& (L \times M) \cap (L \times R) \qquad

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

L \times (M \triangle R) &\;=\;\;&& (L \times M) \triangle (L \times R)

&&\text{ (Left-distributivity of } \,\times\, \text{ over } \,\triangle\, \text{)} \\[1.4ex]

\end{alignat}

But in general, ⨯ does not distribute over itself:

$$L\; \backslash times\; (M\; \backslash times\; R)\; ~\backslash color\{Red\}\{\backslash neq\}\backslash color\{Black\}\{\}~\; (L\; \backslash times\; M)\; \backslash times\; (L\; \backslash times\; R)$$

$$(L\; \backslash times\; M)\; \backslash times\; R\; ~\backslash color\{Red\}\{\backslash neq\}\backslash color\{Black\}\{\}~\; (L\; \backslash times\; R)\; \backslash times\; (M\; \backslash times\; R).$$

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

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

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

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

and

$$(L\; \backslash times\; M\; \backslash times\; R)\; ~\backslash setminus~\; \backslash left(L\_2\; \backslash times\; M\_2\; \backslash times\; R\_2\backslash 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]

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

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

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

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

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

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

In general, $\backslash left(L\; \backslash ,\backslash triangle\backslash ,\; L\_2\backslash right)\; \backslash times\; \backslash left(R\; \backslash ,\backslash triangle\backslash ,\; R\_2\backslash right)$ need not be a subset nor a superset of $\backslash left(L\; \backslash times\; R\backslash right)\; \backslash ,\backslash triangle\backslash ,\; \backslash left(L\_2\; \backslash times\; R\_2\backslash right).$

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

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

Let $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\},$ $\backslash left(R\_j\backslash right)\_\{j\; \backslash in\; J\},$ and $\backslash left(S\_\{i,j\}\backslash right)\_\{(i,\; j)\; \backslash in\; I\; \backslash 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.

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

An {{em|indexed family of sets}} is a function from some set, called its {{em|indexing set}}, into some family of sets.

An indexed family of sets will be denoted by $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\},$ where this notation assigns the symbol $I$ for the indexing set and for every index $i\; \backslash 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\_\backslash bull,$ which is obtained from the notation $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ by replacing the index $i$ with a bullet symbol $\backslash bullet\backslash ,;$ explicitly, $L\_\backslash bull$ is the function:

$$\backslash begin\{alignat\}\{4\}$$

L_\bull :\;&& I &&\;\to \;& \left\{L_i : i \in I\right\} \\[0.3ex]

&& i &&\;\mapsto\;& L_i \\

\end{alignat}

which may be summarized by writing $L\_\backslash bull\; =\; \backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}.$

Any given indexed family of sets $L\_\backslash bull\; =\; \backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ (which is a function) can be canonically associated with its image/range $\backslash operatorname\{Im\}\; L\_\backslash bull\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash left\backslash \{L\_i\; :\; i\; \backslash in\; I\backslash right\backslash \}$ (which is a family of sets).

Conversely, any given family of sets $\backslash mathcal\{B\}$ may be associated with the $\backslash mathcal\{B\}$-indexed family of sets $(B)\_\{B\; \backslash in\; \backslash mathcal\{B\}\},$ which is technically the identity map $\backslash mathcal\{B\}\; \backslash to\; \backslash mathcal\{B\}.$

However, this is {{em|not}} a bijective correspondence because an indexed family of sets $L\_\backslash bull\; =\; \backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ is {{em|not}} required to be injective (that is, there may exist distinct indices $i\; \backslash 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{{sfn|Monk|1969|pp=24-54}}

{{NumBlk||$$\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\; ~~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash \{x\; ~:~\; \backslash text\{\; there\; exists\; \}\; i\; \backslash in\; I\; \backslash text\{\; such\; that\; \}\; x\; \backslash in\; L\_i\backslash \}$$|{{EquationRef|Def. 1}}}}

If $I\; =\; \backslash varnothing$ then $\backslash bigcup\_\{i\; \backslash in\; \backslash varnothing\}\; L\_i\; =\; \backslash \{x\; ~:~\; \backslash text\{\; there\; exists\; \}\; i\; \backslash in\; \backslash varnothing\; \backslash text\{\; such\; that\; \}\; x\; \backslash in\; L\_i\backslash \}\; =\; \backslash varnothing,$ which is somethings called the {{em|nullary union convention}} (despite being called a convention, this equality follows from the definition).

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

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

Arbitrary intersections defined

If $I\; \backslash neq\; \backslash varnothing$ then{{sfn|Monk|1969|pp=24-54}}

{{NumBlk||$$\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\; ~~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash \{x\; ~:~\; x\; \backslash in\; L\_i\; \backslash text\{\; for\; every\; \}\; i\; \backslash in\; I\backslash \}\; ~=~\; \backslash \{x\; ~:~\; \backslash text\{\; for\; all\; \}\; i,\; \backslash text\{\; if\; \}\; i\; \backslash in\; I\; \backslash text\{\; then\; \}\; x\; \backslash in\; L\_i\backslash \}.$$|{{EquationRef|Def. 2}}}}

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

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

Nullary intersections

If $I\; =\; \backslash varnothing$ then

$$\backslash bigcap\_\{i\; \backslash in\; \backslash varnothing\}\; L\_i\; =\; \backslash \{x\; ~:~\; \backslash text\{\; for\; all\; \}\; i,\; \backslash text\{\; if\; \}\; i\; \backslash in\; \backslash varnothing\; \backslash text\{\; then\; \}\; x\; \backslash in\; L\_i\backslash \}$$

where every possible thing $x$ in the universe vacuously satisfied the condition: "if $i\; \backslash in\; \backslash varnothing$ then $x\; \backslash in\; L\_i$". Consequently, $\{\backslash textstyle\backslash bigcap\backslash limits\_\{i\; \backslash in\; \backslash varnothing\}\}\; L\_i\; =\; \backslash \{x\; :\; \backslash text\{\; true\; \}\backslash \}$ consists of {{em|everything}} in the universe.

So if $I\; =\; \backslash varnothing$ and:

1. if you are working in a model in which there exists some Universe set $X$ then $\{\backslash textstyle\backslash bigcap\backslash limits\_\{i\; \backslash in\; \backslash varnothing\}\}\; L\_i\; =\; \backslash \{x\; ~:~\; x\; \backslash in\; L\_i\; \backslash text\{\; for\; every\; \}\; i\; \backslash in\; \backslash varnothing\backslash \}\; ~=~\; 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 $\{\backslash textstyle\backslash bigcap\backslash limits\_\{i\; \backslash in\; \backslash varnothing\}\}\; L\_i$ is {{em|undefined}} because $\{\backslash textstyle\backslash bigcap\backslash limits\_\{i\; \backslash in\; \backslash varnothing\}\}\; L\_i$ consists of {{em|everything}}, which makes $\{\backslash textstyle\backslash bigcap\backslash limits\_\{i\; \backslash in\; \backslash varnothing\}\}\; L\_i$ a proper class and {{em|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 {{em|finite intersection}} of sets or an {{em|intersection of finitely many sets}} refers to the intersection of a finite collection of {{em|one or more}} sets.

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

$$\backslash bigcup\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; S\_\{i,j\}\; ~~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash bigcup\_\{(i,\; j)\; \backslash in\; I\; \backslash times\; J\}\; S\_\{i,j\}$$

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

{{NumBlk||$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; R\; ~=~\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cap\; R\backslash right)$$|{{EquationRef|Eq. 3a}}}}

and{{sfn|Császár|1978|pp=15-26}}

{{NumBlk||$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcup\_\{j\; \backslash in\; J\}\; R\_j\backslash right)\; ~=~\; \backslash bigcup\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; \backslash left(L\_i\; \backslash cap\; R\_j\backslash right)$$|{{EquationRef|Eq. 3b}}}}

• If all $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ are pairwise disjoint and all $\backslash left(R\_j\backslash right)\_\{j\; \backslash in\; J\}$ are also pairwise disjoint, then so are all $\backslash left(L\_i\; \backslash cap\; R\_j\backslash right)\_\{(i,\; j)\; \backslash in\; I\; \backslash times\; J\}$ (that is, if $(i,\; j)\; \backslash neq\; \backslash left(i\_2,\; j\_2\backslash right)$ then $\backslash left(L\_i\; \backslash cap\; R\_j\backslash right)\; \backslash cap\; \backslash left(L\_\{i\_2\}\; \backslash cap\; R\_\{j\_2\}\backslash right)\; =\; \backslash varnothing$).

{{anchor|Ranging over pairs of indices}}

• Importantly, if $I\; =\; J$ then in general, $$~\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; R\_i\backslash right)\; ~~\backslash color\{Red\}\{\backslash neq\}\backslash color\{Black\}\{\}~~\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cap\; R\_i\backslash right)~$$ (an example of this is given below). The single union on the right hand side {{em|must}} be over all pairs $(i,\; j)\; \backslash in\; I\; \backslash times\; I:$ $$~\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; R\_i\backslash right)\; ~~=~~\; \backslash bigcup\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; I\}\}\; \backslash left(L\_i\; \backslash cap\; R\_j\backslash right).~$$ The same is usually true for other similar non-trivial set equalities and relations that depend on two (potentially unrelated) indexing sets $I$ and $J$ (such as {{EquationNote|Eq. 4b}} or {{EquationNote|Eq. 7g}}{{sfn|Császár|1978|pp=15-26}}). Two exceptions are {{EquationNote|Eq. 2c}} (unions of unions) and {{EquationNote|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).
• {{visible anchor|CounterExampleToEqualityInterOfUnionsWhenIequalsJ|CounterExampleToEqualityUnionOfIntersWhenIequalsJ|text=Example where equality fails}}: Let $X\; \backslash neq\; \backslash varnothing$ and let $I\; =\; \backslash \{1,\; 2\backslash \}.$ Let $L\_1\; \backslash colon=\; R\_2\; \backslash colon=\; X$ and let $L\_2\; \backslash colon=\; R\_1\; \backslash colon=\; \backslash varnothing.$ Then $$X\; =\; X\; \backslash cap\; X\; =\; \backslash left(L\_1\; \backslash cup\; L\_2\backslash right)\; \backslash cap\; \backslash left(R\_2\; \backslash cup\; R\_2\backslash right)\; =\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; R\_i\backslash right)\; ~\backslash neq~\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cap\; R\_i\backslash right)\; =\; \backslash left(L\_1\; \backslash cap\; R\_1\backslash right)\; \backslash cup\; \backslash left(L\_2\; \backslash cap\; R\_2\backslash right)\; =\; \backslash varnothing\; \backslash cup\; \backslash varnothing\; =\; \backslash varnothing.$$ Furthermore, $$\backslash varnothing\; =\; \backslash varnothing\; \backslash cup\; \backslash varnothing\; =\; \backslash left(L\_1\; \backslash cap\; L\_2\backslash right)\; \backslash cup\; \backslash left(R\_2\; \backslash cap\; R\_2\backslash right)\; =\; \backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cup\; \backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; R\_i\backslash right)\; ~\backslash neq~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cup\; R\_i\backslash right)\; =\; \backslash left(L\_1\; \backslash cup\; R\_1\backslash right)\; \backslash cap\; \backslash left(L\_2\; \backslash cup\; R\_2\backslash right)\; =\; X\; \backslash cap\; X\; =\; X.$$

{{NumBlk||$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cup\; R\; ~=~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cup\; R\backslash right)$$|{{EquationRef|Eq. 4a}}}}

and{{sfn|Császár|1978|pp=15-26}}

{{NumBlk||$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cup\; \backslash left(\backslash bigcap\_\{j\; \backslash in\; J\}\; R\_j\backslash right)\; ~=~\; \backslash bigcap\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; \backslash left(L\_i\; \backslash cup\; R\_j\backslash right)$$|{{EquationRef|Eq. 4b}}}}

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

Naively swapping $\backslash ;\{\backslash textstyle\backslash bigcup\backslash limits\_\{i\; \backslash in\; I\}\}\backslash ;$ and $\backslash ;\{\backslash textstyle\backslash bigcap\backslash limits\_\{j\; \backslash in\; J\}\}\backslash ;$ may produce a different set{{anchor|Arbitrary unions/intersections and switching symbols}}

The following inclusion always holds:

{{NumBlk||$$\backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(\backslash bigcap\_\{j\; \backslash in\; J\}\; S\_\{i,j\}\backslash right)\; ~~\backslash color\{Red\}\{\backslash subseteq\}\backslash color\{Black\}\{\}~~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; S\_\{i,j\}\backslash right)$$|{{EquationRef|In. 1|2=Inclusion 1 ∪∩ is a subset of ∩∪}}|LnSty=1px dashed black}}

In general, equality need not hold and moreover, the right hand side depends on how for each fixed $i\; \backslash in\; I,$ the sets $\backslash left(S\_\{i,j\}\backslash right)\_\{j\; \backslash in\; J\}$ are labelled; and analogously, the left hand side depends on how for each fixed $j\; \backslash in\; J,$ the sets $\backslash left(S\_\{i,j\}\backslash right)\_\{i\; \backslash 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 $\backslash cup$ and $\backslash cap$ are swapped, let $I\; \backslash colon=\; J\; \backslash colon=\; \backslash \{1,\; 2\backslash \},$ and let $S\_\{11\}\; =\; \backslash \{1,\; 2\backslash \},~S\_\{12\}\; =\; \backslash \{1,\; 3\backslash \},~S\_\{21\}\; =\; \backslash \{3,\; 4\backslash \},$ and $S\_\{22\}\; =\; \backslash \{2,\; 4\backslash \}.$ Then $$\backslash \{1,\; 4\backslash \}\; =\; \backslash \{1\backslash \}\; \backslash cup\; \backslash \{4\backslash \}\; =\; \backslash left(S\_\{11\}\; \backslash cap\; S\_\{12\}\backslash right)\; \backslash cup\; \backslash left(S\_\{21\}\; \backslash cap\; S\_\{22\}\backslash right)\; =\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(\backslash bigcap\_\{j\; \backslash in\; J\}\; S\_\{i,j\}\backslash right)\; ~\backslash neq~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; S\_\{i,j\}\backslash right)\; =\; \backslash left(S\_\{11\}\; \backslash cup\; S\_\{21\}\backslash right)\; \backslash cap\; \backslash left(S\_\{12\}\; \backslash cup\; S\_\{22\}\backslash right)\; =\; \backslash \{1,\; 2,\; 3,\; 4\backslash \}.$$

  If $S\_\{11\}$ and $S\_\{21\}$ are swapped while $S\_\{12\}$ and $S\_\{22\}$ are unchanged, which gives rise to the sets $\backslash hat\{S\}\_\{11\}\; \backslash colon=\; \backslash \{3,\; 4\backslash \},~\backslash hat\{S\}\_\{12\}\; \backslash colon=\; \backslash \{1,\; 3\backslash \},~\backslash hat\{S\}\_\{21\}\; \backslash colon=\; \backslash \{1,\; 2\backslash \},$ and $\backslash hat\{S\}\_\{22\}\; \backslash colon=\; \backslash \{2,\; 4\backslash \},$ then

  $$\backslash \{2,\; 3\backslash \}\; =\; \backslash \{3\backslash \}\; \backslash cup\; \backslash \{2\backslash \}\; =\; \backslash left(\backslash hat\{S\}\_\{11\}\; \backslash cap\; \backslash hat\{S\}\_\{12\}\backslash right)\; \backslash cup\; \backslash left(\backslash hat\{S\}\_\{21\}\; \backslash cap\; \backslash hat\{S\}\_\{22\}\backslash right)\; =\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(\backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash hat\{S\}\_\{i,j\}\backslash right)\; ~\backslash neq~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash hat\{S\}\_\{i,j\}\backslash right)\; =\; \backslash left(\backslash hat\{S\}\_\{11\}\; \backslash cup\; \backslash hat\{S\}\_\{21\}\backslash right)\; \backslash cap\; \backslash left(\backslash hat\{S\}\_\{12\}\; \backslash cup\; \backslash hat\{S\}\_\{22\}\backslash right)\; =\; \backslash \{1,\; 2,\; 3,\; 4\backslash \}.$$

  In particular, the left hand side is no longer $\backslash \{1,\; 4\backslash \},$ which shows that the left hand side $\{\backslash textstyle\backslash bigcup\backslash limits\_\{i\; \backslash in\; I\}\}\; \backslash ;\; \{\backslash textstyle\backslash bigcap\backslash limits\_\{j\; \backslash 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\}$ are unchanged, which gives rise to the sets $\backslash overline\{S\}\_\{11\}\; \backslash colon=\; \backslash \{1,\; 3\backslash \},~\; \backslash overline\{S\}\_\{12\}\; \backslash colon=\; \backslash \{1,\; 2\backslash \},~\; \backslash overline\{S\}\_\{21\}\; \backslash colon=\; \backslash \{3,\; 4\backslash \},$ and $\backslash overline\{S\}\_\{22\}\; \backslash colon=\; \backslash \{2,\; 4\backslash \},$ then both the left hand side and right hand side are equal to $\backslash \{1,\; 4\backslash \},$ which shows that the right hand side also depends on how the sets are labeled.

Equality in {{EquationNote|In. 1|Inclusion 1 ∪∩ is a subset of ∩∪}} can hold under certain circumstances, such as in {{EquationNote|Eq. 7e|7e}}, which is the special case where $\backslash left(S\_\{i,j\}\backslash right)\_\{(i,j)\; \backslash in\; I\; \backslash times\; J\}$ is $\backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)\_\{(i,j)\; \backslash in\; I\; \backslash times\; J\}$ (that is, $S\_\{i,j\}\; \backslash colon=\; L\_i\; \backslash setminus\; R\_j$ with the same indexing sets $I$ and $J$), or such as in {{EquationNote|Eq. 7f|7f}}, which is the special case where $\backslash left(S\_\{i,j\}\backslash right)\_\{(i,j)\; \backslash in\; I\; \backslash times\; J\}$ is $\backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)\_\{(j,\; i)\; \backslash in\; J\; \backslash times\; I\}$ (that is, $\backslash hat\{S\}\_\{j,i\}\; \backslash colon=\; L\_i\; \backslash setminus\; R\_j$ with the indexing sets $I$ and $J$ swapped).

For a correct formula that extends the distributive laws, an approach other than just switching $\backslash cup$ and $\backslash cap$ is needed.

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

$$\{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash prod\_\{i\; \backslash in\; I\}\; J\_i$$

denote the Cartesian product, which can be interpreted as the set of all functions $f\; ~:~\; I\; ~\backslash to~\; \{\backslash textstyle\backslash bigcup\backslash limits\_\{i\; \backslash in\; I\}\}\; J\_i$ such that $f(i)\; \backslash in\; J\_i$ for every $i\; \backslash in\; I.$ Such a function may also be denoted using the tuple notation $\backslash left(f\_i\backslash right)\_\{i\; \backslash in\; I\}$ where $f\_i\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; f(i)$ for every $i\; \backslash in\; I$ and conversely, a tuple $\backslash left(f\_i\backslash right)\_\{i\; \backslash in\; I\}$ is just notation for the function with domain $I$ whose value at $i\; \backslash in\; I$ is $f\_i;$ both notations can be used to denote the elements of $\{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}.$

Then

{{NumBlk||$$\backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left[\backslash ;\backslash bigcup\_\{j\; \backslash in\; J\_i\}\; T\_\{i,j\}\backslash right]\; =\; \backslash bigcup\_\{f\; \backslash in\; \backslash prod\; J\_\{\backslash bull\}\}\; \backslash left[\backslash ;\backslash bigcap\_\{i\; \backslash in\; I\}\; T\_\{i,f(i)\}\backslash right]$$|{{EquationRef|5|2=Eq. 5 ∩∪ to ∪∩}}|LnSty=1px dashed black}}

{{NumBlk||$$\backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left[\backslash ;\backslash bigcap\_\{j\; \backslash in\; J\_i\}\; T\_\{i,j\}\backslash right]\; =\; \backslash bigcap\_\{f\; \backslash in\; \backslash prod\; J\_\{\backslash bull\}\}\; \backslash left[\backslash ;\backslash bigcup\_\{i\; \backslash in\; I\}\; T\_\{i,f(i)\}\backslash right]$$|{{EquationRef|6|2=Eq. 6 ∪∩ to ∩∪}}|LnSty=1px dashed black}}

where $\{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; J\_i.$

{{em|Example application}}: In the particular case where all $J\_i$ are equal (that is, $J\_i\; =\; J\_\{i\_2\}$ for all $i,\; i\_2\; \backslash in\; I,$ which is the case with the family $\backslash left(S\_\{i,j\}\backslash right)\_\{(i,\; j)\; \backslash in\; I\; \backslash times\; J\},$ for example), then letting $J$ denote this common set, the Cartesian product will be $\{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; J\_i\; =\; \{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; J\; =\; J^I,$ which is the set of all functions of the form $f\; ~:~\; I\; ~\backslash to~\; J.$ The above set equalities {{EquationNote|5|2=Eq. 5 ∩∪ to ∪∩}} and {{EquationNote|6|2=Eq. 6 ∪∩ to ∩∪}}, respectively become:{{sfn|Monk|1969|pp=24-54}}

$$\backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcup\_\{j\; \backslash in\; J\}\; S\_\{i,j\}\; =\; \backslash bigcup\_\{f\; \backslash in\; J^I\}\; \backslash ;\; \backslash bigcap\_\{i\; \backslash in\; I\}\; S\_\{i,f(i)\}$$

$$\backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcap\_\{j\; \backslash in\; J\}\; S\_\{i,j\}\; =\; \backslash bigcap\_\{f\; \backslash in\; J^I\}\; \backslash ;\; \backslash bigcup\_\{i\; \backslash in\; I\}\; S\_\{i,f(i)\}$$

which when combined with {{EquationNote|In. 1|2=Inclusion 1 ∪∩ is a subset of ∩∪}} implies:

$$\backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcap\_\{j\; \backslash in\; J\}\; S\_\{i,j\}$$

~=~ \bigcap_{f \in J^I} \; \bigcup_{i \in I} S_{i,f(i)}

~~\color{Red}{\subseteq}\color{Black}{}~~ \bigcup_{g \in I^J} \; \bigcap_{j \in J} S_{g(j),j}

~=~ \bigcap_{j \in J} \; \bigcup_{i \in I} S_{i,j}

where

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

{{em|Example application}}: To apply the general formula to the case of $\backslash left(C\_k\backslash right)\_\{k\; \backslash in\; K\}$ and $\backslash left(D\_\{l\}\backslash right)\_\{l\; \backslash in\; L\},$ use $I\; \backslash colon=\; \backslash \{1,\; 2\backslash \},$ $J\_1\; \backslash colon=\; K,$ $J\_2\; \backslash colon=\; L,$ and let $T\_\{1,k\}\; \backslash colon=\; C\_k$ for all $k\; \backslash in\; J\_1$ and let $T\_\{2,l\}\; \backslash colon=\; D\_l$ for all $l\; \backslash in\; J\_2.$

Every map $f\; \backslash in\; \{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; J\_i\; =\; J\_1\; \backslash times\; J\_2\; =\; K\; \backslash times\; L$ can be bijectively identified with the pair $\backslash left(f(1),\; f(2)\backslash right)\; \backslash in\; K\; \backslash times\; L$ (the inverse sends $(k,l)\; \backslash in\; K\; \backslash times\; L$ to the map $f\_\{(k,l)\}\; \backslash in\; \{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}$ defined by $1\; \backslash mapsto\; k$ and $2\; \backslash mapsto\; l;$ this is technically just a change of notation). Recall that {{EquationNote|5|2=Eq. 5 ∩∪ to ∪∩}} was

$$~\backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcup\_\{j\; \backslash in\; J\_i\}\; T\_\{i,j\}\; =\; \backslash bigcup\_\{f\; \backslash in\; \{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}\}\; \backslash ;\; \backslash bigcap\_\{i\; \backslash in\; I\}\; T\_\{i,f(i)\}.~$$

Expanding and simplifying the left hand side gives

$$\backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcup\_\{j\; \backslash in\; J\_i\}\; T\_\{i,j\}$$

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

$$\backslash bigcup\_\{f\; \backslash in\; \backslash prod\; J\_\{\backslash bull\}\}\; \backslash ;\; \backslash bigcap\_\{i\; \backslash in\; I\}\; T\_\{i,f(i)\}$$

= \bigcup_{f \in \prod J_{\bull}} \left(T_{1,f(1)} \cap T_{2,f(2)}\right)

= \bigcup_{f \in \prod J_{\bull}} \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 {{EquationNote|5|2=Eq. 5 ∩∪ to ∪∩}} reduces down to the previously given set equality {{EquationNote|Eq. 3b}}:

$$\backslash left(\backslash bigcup\_\{k\; \backslash in\; K\}\; C\_k\backslash right)\; \backslash cap\; \backslash ;\backslash bigcup\_\{l\; \backslash in\; L\}\; D\_l\; =\; \backslash bigcup\_\{\backslash stackrel\{k\; \backslash in\; K,\}\{l\; \backslash in\; L\}\}\; \backslash left(C\_k\; \backslash cap\; D\_l\backslash right).$$

{{NumBlk||$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash ;\backslash setminus\backslash ;\; R\; ~=~\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\backslash right)$$|{{EquationRef|Eq. 7a}}}}

{{NumBlk||$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash ;\backslash setminus\backslash ;\; R\; ~=~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\backslash right)$$|{{EquationRef|Eq. 7b}}}}

The next identities are known as De Morgan's laws.{{sfn|Császár|1978|pp=15-26}}

{{NumBlk||$$L\; \backslash ;\backslash setminus\backslash ;\; \backslash bigcup\_\{j\; \backslash in\; J\}\; R\_j\; ~=~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash left(L\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)\; ~~\backslash ;~~\; \backslash text\{\; De\; Morgan\text{'}s\; law\; \}$$|{{EquationRef|Eq. 7c}}}}

{{NumBlk||$$L\; \backslash ;\backslash setminus\backslash ;\; \backslash bigcap\_\{j\; \backslash in\; J\}\; R\_j\; ~=~\; \backslash bigcup\_\{j\; \backslash in\; J\}\; \backslash left(L\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)\; ~~\backslash ;~~\; \backslash text\{\; De\; Morgan\text{'}s\; law\; \}$$|{{EquationRef|Eq. 7d}}}}

The following four set equalities can be deduced from the equalities {{EquationNote|Eq. 7a|7a}} - {{EquationNote|Eq. 7d|7d}} above.

{{NumBlk||$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash ;\backslash setminus\backslash ;\; \backslash bigcup\_\{j\; \backslash in\; J\}\; R\_j\; ~=~\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(\backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)\backslash right)\; ~=~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)\backslash right)$$|{{EquationRef|Eq. 7e}}}}

{{NumBlk||$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash ;\backslash setminus\backslash ;\; \backslash bigcap\_\{j\; \backslash in\; J\}\; R\_j\; ~=~\; \backslash bigcup\_\{j\; \backslash in\; J\}\; \backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)\backslash right)\; ~=~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left(\backslash bigcup\_\{j\; \backslash in\; J\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)\backslash right)$$|{{EquationRef|Eq. 7f}}}}

{{NumBlk||$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash ;\backslash setminus\backslash ;\; \backslash bigcap\_\{j\; \backslash in\; J\}\; R\_j\; ~=~\; \backslash bigcup\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)$$|{{EquationRef|Eq. 7g}}}}

{{NumBlk||$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash ;\backslash setminus\backslash ;\; \backslash bigcup\_\{j\; \backslash in\; J\}\; R\_j\; ~=~\; \backslash bigcap\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; \backslash left(L\_i\; \backslash ;\backslash setminus\backslash ;\; R\_j\backslash right)$$|{{EquationRef|Eq. 7h}}}}

In general, naively swapping $\backslash ;\backslash cup\backslash ;$ and $\backslash ;\backslash cap\backslash ;$ may produce a different set (see this note for more details).

The equalities

$$\backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)\; ~=~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash ;\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash setminus\; R\_j\backslash right)$$

\quad \text{ and } \quad

\bigcup_{j \in J} \; \bigcap_{i \in I} \left(L_i \setminus R_j\right) ~=~ \bigcap_{i \in I} \; \bigcup_{j \in J} \left(L_i \setminus R_j\right)

found in {{EquationNote|Eq. 7e}} and {{EquationNote|Eq. 7f}} are thus unusual in that they state exactly that swapping $\backslash ;\backslash cup\backslash ;$ and $\backslash ;\backslash cap\backslash ;$ will {{em|not}} change the resulting set.

Commutativity:{{sfn|Monk|1969|pp=24-54}}

$$\backslash bigcup\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; S\_\{i,j\}$$

~~\stackrel{\scriptscriptstyle\text{def}}{=}~ \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)

$$\backslash bigcap\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; S\_\{i,j\}$$

~~\stackrel{\scriptscriptstyle\text{def}}{=}~ \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:{{sfn|Monk|1969|pp=24-54}}

$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cup\; R\; ~=~\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cup\; R\backslash right)$$

$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; R\; ~=~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cap\; R\backslash right)$$

and{{sfn|Monk|1969|pp=24-54}}

{{NumBlk||$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cup\; \backslash left(\backslash bigcup\_\{j\; \backslash in\; J\}\; R\_j\backslash right)\; ~=~\; \backslash bigcup\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; \backslash left(L\_i\; \backslash cup\; R\_j\backslash right)$$|{{EquationRef|Eq. 2a}}}}

{{NumBlk||$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcap\_\{j\; \backslash in\; J\}\; R\_j\backslash right)\; ~=~\; \backslash bigcap\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; J\}\}\; \backslash left(L\_i\; \backslash cap\; R\_j\backslash right)$$|{{EquationRef|Eq. 2b}}}}

and if $I\; =\; J$ then also:To deduce {{EquationNote|Eq. 2c}} from {{EquationNote|Eq. 2a}}, it must still be shown that $\{\backslash textstyle\backslash bigcup\backslash limits\_\{\backslash stackrel\{i\; \backslash in\; I,\}\{j\; \backslash in\; I\}\}\}\; \backslash left(L\_i\; \backslash cup\; R\_j\backslash right)\; ~=~\; \{\backslash textstyle\backslash bigcup\backslash limits\_\{i\; \backslash in\; I\}\}\; \backslash left(L\_i\; \backslash cup\; R\_i\backslash right)$ so {{EquationNote|Eq. 2c}} is not a completely immediate consequence of {{EquationNote|Eq. 2a}}. (Compare this to the commentary about {{EquationNote|Eq. 3b}}).{{sfn|Monk|1969|pp=24-54}}

{{NumBlk||$$\backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cup\; \backslash left(\backslash bigcup\_\{i\; \backslash in\; I\}\; R\_i\backslash right)\; ~=~\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cup\; R\_i\backslash right)$$|{{EquationRef|Eq. 2c}}}}

{{NumBlk||$$\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; \backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; R\_i\backslash right)\; ~=~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cap\; R\_i\backslash right)$$|{{EquationRef|Eq. 2d}}}}

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

{{NumBlk||$$\backslash bigcap\_\{j\; \backslash in\; J\}\; \backslash ;\; \backslash prod\_\{i\; \backslash in\; I\}\; S\_\{i,j\}\; ~~=~~\; \backslash prod\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcap\_\{j\; \backslash in\; J\}\; S\_\{i,j\}$$|{{EquationRef|Eq. 8}}}}

• Moreover, a tuple $\backslash left(x\_i\backslash right)\_\{i\; \backslash in\; I\}$ belongs to the set in {{EquationNote|Eq. 8|Eq. 8}} above if and only if $x\_i\; \backslash in\; S\_\{i,j\}$ for all $i\; \backslash in\; I$ and all $j\; \backslash in\; J.$

In particular, if $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ and $\backslash left(R\_i\backslash right)\_\{i\; \backslash in\; I\}$ are two families indexed by the same set then

$$\backslash left(\backslash prod\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; \backslash cap\; \backslash prod\_\{i\; \backslash in\; I\}\; R\_i\; ~=~\; \backslash prod\_\{i\; \backslash in\; I\}\; \backslash left(L\_i\; \backslash cap\; R\_i\backslash right)$$

So for instance,

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

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

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

Intersections of products indexed by different sets

Let $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ and $\backslash left(R\_j\backslash right)\_\{j\; \backslash in\; J\}$ be two families indexed by different sets.

Technically, $I\; \backslash neq\; J$ implies $\backslash left(\{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; L\_i\backslash right)\; \backslash cap\; \{\backslash textstyle\backslash prod\backslash limits\_\{j\; \backslash in\; J\}\}\; R\_j\; =\; \backslash 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\; :=\; \backslash \{1,\; 2\backslash \}$ and $J\; :=\; \backslash \{1,\; 2,\; 3\backslash \}$ with all sets equal to $\backslash R$ then $\{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; L\_i\; =\; \{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; \backslash \{1,\; 2\backslash \}\}\}\; \backslash R\; =\; \backslash R^2$ and $\{\backslash textstyle\backslash prod\backslash limits\_\{j\; \backslash in\; J\}\}\; R\_j\; =\; \{\backslash textstyle\backslash prod\backslash limits\_\{j\; \backslash in\; \backslash \{1,\; 2,\; 3\backslash \}\}\}\; \backslash R\; =\; \backslash R^3$ where $\backslash R^2\; \backslash cap\; \backslash R^3\; =\; \backslash varnothing$ {{em|unless}}, for example, $\{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; \backslash \{1,\; 2\backslash \}\}\}\; \backslash R\; =\; \backslash R^2$ is identified as a subset of $\{\backslash textstyle\backslash prod\backslash limits\_\{j\; \backslash in\; \backslash \{1,\; 2,\; 3\backslash \}\}\}\; \backslash R\; =\; \backslash R^3$ through some injection, such as maybe $(x,\; y)\; \backslash mapsto\; (x,\; y,\; 0)$ for instance; however, in this particular case the product $\{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\; =\; \backslash \{1,\; 2\backslash \}\}\}\; L\_i$ actually represents the $J$-indexed product $\{\backslash textstyle\backslash prod\backslash limits\_\{j\; \backslash in\; J\; =\; \backslash \{1,\; 2,\; 3\backslash \}\}\}\; L\_i$ where $L\_3\; :=\; \backslash \{0\backslash \}.$
• For another example, take $I\; :=\; \backslash \{1,\; 2\backslash \}$ and $J\; :=\; \backslash \{1,\; 2,\; 3\backslash \}$ with $L\_1\; :=\; \backslash R^2$ and $L\_2,\; R\_1,\; R\_2,\; \backslash text\{\; and\; \}\; R\_3$ all equal to $\backslash R.$ Then $\{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}L\_i\; =\; \backslash R^2\; \backslash times\; \backslash R$ and $\{\backslash textstyle\backslash prod\backslash limits\_\{j\; \backslash in\; J\}\}\; R\_j\; =\; \backslash R\; \backslash times\; \backslash R\; \backslash times\; \backslash R,$ which can both be identified as the same set via the bijection that sends $((x,\; y),\; z)\; \backslash in\; \backslash R^2\; \backslash times\; \backslash R$ to $(x,\; y,\; z)\; \backslash in\; \backslash R\; \backslash times\; \backslash R\; \backslash times\; \backslash R.$ Under this identification, $\backslash left(\{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; L\_i\backslash right)\; \backslash cap\; \backslash ,\; \{\backslash textstyle\backslash prod\backslash limits\_\{j\; \backslash in\; J\}\}\; R\_j\; ~=~\; \backslash R^3.$

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

$$\backslash begin\{alignat\}\{5\}$$

L \times \left(\bigcup_{i \in I} R_i\right) &\;=\;\;&& \bigcup_{i \in I} (L \times R_i) \qquad

&&\text{ (Left-distributivity of } \,\times\, \text{ over } \,\cup\, \text{)} \\[1.4ex]

L \times \left(\bigcap_{i \in I} R_i\right) &\;=\;\;&& \bigcap_{i \in I} (L \times R_i) \qquad

&&\text{ (Left-distributivity of } \,\times\, \text{ over } \,\bigcap_{i \in I}\, \text{ when } I \neq \varnothing\, \text{)} \\[1.4ex]

\left(\bigcup_{i \in I} L_i\right) \times R &\;=\;\;&& \bigcup_{i \in I} (L_i \times R) \qquad

&&\text{ (Right-distributivity of } \,\times\, \text{ over } \,\cup\, \text{)} \\[1.4ex]

\left(\bigcap_{i \in I} L_i\right) \times R &\;=\;\;&& \bigcap_{i \in I} (L_i \times R) \qquad

&&\text{ (Right-distributivity of } \,\times\, \text{ over } \,\bigcap_{i \in I}\, \text{ when } I \neq \varnothing\, \text{)} \\[1.4ex]

\end{alignat}

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

$$\{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash prod\_\{i\; \backslash in\; I\}\; J\_i$$

denote the Cartesian product, which (as mentioned above) can be interpreted as the set of all functions $f\; ~:~\; I\; ~\backslash to~\; \{\backslash textstyle\backslash bigcup\backslash limits\_\{i\; \backslash in\; I\}\}\; J\_i$ such that $f(i)\; \backslash in\; J\_i$ for every $i\; \backslash in\; I$.

Then

{{NumBlk||$$\backslash prod\_\{i\; \backslash in\; I\}\; \backslash left[\backslash ;\backslash bigcup\_\{j\; \backslash in\; J\_i\}\; T\_\{i,j\}\backslash right]\; =\; \backslash bigcup\_\{f\; \backslash in\; \backslash prod\; J\_\{\backslash bull\}\}\; \backslash left[\backslash ;\backslash prod\_\{i\; \backslash in\; I\}\; T\_\{i,f(i)\}\backslash right]$$|{{EquationRef|11|2=Eq. 11 Π∪ to ∪Π}}|LnSty=1px dashed black}}

where $\{\backslash textstyle\; \backslash prod\}\; J\_\{\backslash bull\}\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \{\backslash textstyle\backslash prod\backslash limits\_\{i\; \backslash in\; I\}\}\; J\_i.$

For unions, only the following is guaranteed in general:

$$\backslash bigcup\_\{j\; \backslash in\; J\}\; \backslash ;\; \backslash prod\_\{i\; \backslash in\; I\}\; S\_\{i,j\}\; ~~\backslash color\{Red\}\{\backslash subseteq\}\backslash color\{Black\}\{\}~~\; \backslash prod\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash bigcup\_\{j\; \backslash in\; J\}\; S\_\{i,j\}\; \backslash qquad\; \backslash text\{\; and\; \}\; \backslash qquad\; \backslash bigcup\_\{i\; \backslash in\; I\}\; \backslash ;\; \backslash prod\_\{j\; \backslash in\; J\}\; S\_\{i,j\}\; ~~\backslash color\{Red\}\{\backslash subseteq\}\backslash color\{Black\}\{\}~~\; \backslash prod\_\{j\; \backslash in\; J\}\; \backslash ;\; \backslash bigcup\_\{i\; \backslash in\; I\}\; S\_\{i,j\}$$

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

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

However,

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

If $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ and $\backslash left(R\_i\backslash right)\_\{i\; \backslash in\; I\}$ are two families of sets then:

$$\backslash begin\{alignat\}\{9\}$$

\left(\prod_{i \in I} L_i\right) ~\setminus~ \prod_{i \in I}R_i

~&=~ \;~ \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{alignat}

so for instance,

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

and

$$(L\; \backslash times\; M\; \backslash times\; R)\; ~\backslash setminus~\; \backslash left(L\_2\; \backslash times\; M\_2\; \backslash times\; R\_2\backslash 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]

$$\backslash begin\{alignat\}\{9\}$$

\left(\prod_{i \in I} L_i\right) ~\triangle~ \left(\prod_{i \in I} R_i\right)

~&=~ \;~ \left(\prod_{i \in I} L_i\right) ~\cup~ \left(\prod_{i \in I} R_i\right) \;\setminus\; \prod_{i \in I} L_i \cap R_i \\[0.5ex]

\end{alignat}

{{See also|Image (mathematics)#Properties}}

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

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

Let $f\; :\; X\; \backslash to\; Y$ be any function, where we denote its {{em|domain}} $X$ by $\backslash operatorname\{domain\}\; f$ and denote its {{em|codomain}} $Y$ by $\backslash 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 "{{em|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.So for instance, it's even possible that $L\; \backslash cap\; (X\; \backslash cup\; Y)\; =\; \backslash varnothing,$ or that $L\; \backslash cap\; X\; \backslash neq\; \backslash varnothing$ {{em|and}} $L\; \backslash cap\; Y\; \backslash neq\; \backslash varnothing$ (which happens, for instance, if $X\; =\; Y$), etc.

This generality is useful in situations where $f\; :\; X\; \backslash to\; Y$ is a map between two subsets $X\; \backslash subseteq\; U$ and $Y\; \backslash subseteq\; V$ of some larger sets $U$ and $V,$ and where the set $L$ might not be entirely contained in $X\; =\; \backslash operatorname\{domain\}\; f$ and/or $Y\; =\; \backslash operatorname\{codomain\}\; f$ (e.g. if all that is known about $L$ is that $L\; \backslash 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\; \backslash cap\; X)$ and/or $f^\{-1\}(L\; \backslash cap\; Y).$

Images and preimages of sets

If $L$ is {{em|any}} set then the {{em|Image (mathematics) of $L$ under $f$}} is defined to be the set:

$$f(L)\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash \{\backslash ,f(l)\; ~:~\; l\; \backslash in\; L\; \backslash cap\; \backslash operatorname\{domain\}\; f\backslash ,\backslash \}$$

while the {{em|preimage of $L$ under $f$}} is:

$$f^\{-1\}(L)\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash \{\backslash ,x\; \backslash in\; \backslash operatorname\{domain\}\; f\; ~:~\; f(x)\; \backslash in\; L\backslash ,\backslash \}$$

where if $L\; =\; \backslash \{s\backslash \}$ is a singleton set then the {{em|fiber}} or {{em|preimage of $s$ under $f$}} is

$$f^\{-1\}(s)\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; f^\{-1\}(\backslash \{s\backslash \})\; ~=~\; \backslash \{\backslash ,x\; \backslash in\; \backslash operatorname\{domain\}\; f\; ~:~\; f(x)\; =\; s\backslash ,\backslash \}.$$

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

$$\backslash operatorname\{Im\}\; f\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; f(X)\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; f(\backslash operatorname\{domain\}\; f)\; ~=~\; \backslash \{f(x)\; ~:~\; x\; \backslash in\; \backslash operatorname\{domain\}\; f\backslash \}.$$

Saturated sets

{{Main|Saturated set}}

A set $A$ is said to be {{em|$f$-saturated}} or a {{em|saturated set}} if any of the following equivalent conditions are satisfied:{{sfn|Monk|1969|pp=24-54}}

1. There exists a set $R$ such that $A\; =\; f^\{-1\}(R).$
   • Any such set $R$ necessarily contains $f(A)$ as a subset.
   • Any set not entirely contained in the domain of $f$ cannot be $f$-saturated.

2. $A\; =\; f^\{-1\}(f(A)).$
3. $A\; \backslash supseteq\; f^\{-1\}(f(A))$ and $A\; \backslash subseteq\; \backslash operatorname\{domain\}\; f.$
   • The inclusion $L\; \backslash cap\; \backslash operatorname\{domain\}\; f\; \backslash subseteq\; f^\{-1\}(f(L))$ always holds, where if $A\; \backslash subseteq\; \backslash operatorname\{domain\}\; f$ then this becomes $A\; \backslash subseteq\; f^\{-1\}(f(A)).$

4. $A\; \backslash subseteq\; \backslash operatorname\{domain\}\; f$ and if $a\; \backslash in\; A$ and $x\; \backslash in\; \backslash operatorname\{domain\}\; f$ satisfy $f(x)\; =\; f(a),$ then $x\; \backslash in\; A.$

5. Whenever a fiber of $f$ intersects $A,$ then $A$ contains the entire fiber. In other words, $A$ contains every $f$-fiber that intersects it.
• Explicitly: whenever $y\; \backslash in\; \backslash operatorname\{Im\}\; f$ is such that $A\; \backslash cap\; f^\{-1\}(y)\; \backslash neq\; \backslash varnothing,$ then $f^\{-1\}(y)\; \backslash subseteq\; A.$
• In both this statement and the next, the set $\backslash operatorname\{Im\}\; f$ may be replaced with any superset of $\backslash operatorname\{Im\}\; f$ (such as $\backslash operatorname\{codomain\}\; f$) and the resulting statement will still be equivalent to the rest.
6. The intersection of $A$ with a fiber of $f$ is equal to the empty set or to the fiber itself.
   • Explicitly: for every $y\; \backslash in\; \backslash operatorname\{Im\}\; f,$ the intersection $A\; \backslash cap\; f^\{-1\}(y)$ is equal to the empty set $\backslash varnothing$ or to $f^\{-1\}(y)$ (that is, $A\; \backslash cap\; f^\{-1\}(y)\; =\; \backslash varnothing$ or $A\; \backslash cap\; f^\{-1\}(y)\; =\; f^\{-1\}(y)$).

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

Compositions and restrictions of functions

If $f$ and $g$ are maps then $g\; \backslash circ\; f$ denotes the {{em|composition}} map

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

with domain and codomain

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

defined by

$$(g\; \backslash circ\; f)(x)\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; g(f(x)).$$

The {{em|restriction of $f\; :\; X\; \backslash to\; Y$ to $L,$}} denoted by $f\backslash big\backslash vert\_L,$ is the map

$$f\backslash big\backslash vert\_L\; ~:~\; L\; \backslash cap\; \backslash operatorname\{domain\}\; f\; ~\backslash to~\; Y$$

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

$$f\backslash big\backslash vert\_L(x)\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; f\; (x).$$

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

If $\backslash left(L\_i\backslash right)\_\{i\; \backslash in\; I\}$ is a family of arbitrary sets indexed by $I\; \backslash neq\; \backslash varnothing$ then:{{sfn|Császár|1978|pp=102-120}}

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

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

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

{{NumBlk||$$f\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; L\_i\backslash right)\; ~=~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; f\backslash left(L\_i\backslash right)\; \backslash qquad\; \backslash textit\{IF\}\; \backslash qquad\; X\; \backslash cap\; L\_i\; =\; f^\{-1\}\backslash left(f\backslash left(L\_i\backslash right)\backslash right)\; \backslash quad\; \backslash text\{\; for\; all\; \}\; \backslash quad\; i\; \backslash in\; I.$$|{{EquationRef|Conditional Equality 10a}}}}

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

{{NumBlk||$$f\backslash left(\backslash bigcap\_\{i\; \backslash in\; I\}\; A\_i\backslash right)\; ~=~\; \backslash bigcap\_\{i\; \backslash in\; I\}\; f\backslash left(A\_i\backslash right)\; \backslash qquad\; \backslash textit\{IF\}\; \backslash qquad\; A\_i\; =\; f^\{-1\}\backslash left(f\backslash left(A\_i\backslash right)\backslash right)\; \backslash quad\; \backslash text\{\; for\; all\; \}\; \backslash quad\; i\; \backslash in\; I.$$|{{EquationRef|Conditional Equality 10b}}}}

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

Summary

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

Preimages preserve set operations

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

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

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

Images {{em|only}} preserve unions

Images of unions are well-behaved:

$$\backslash begin\{alignat\}\{4\}$$

f(L \cup R) ~&=~ f(L) \cup f(R) \\

\end{alignat}

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

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

In words, images distribute over unions but not necessarily over intersections, set subtraction, or symmetric difference. What these latter three operations have in common is set subtraction: they either {{em|are}} set subtraction $L\; \backslash setminus\; R$ or else they can naturally {{em|be defined}} as the set subtraction of two sets:

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

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

File:Image preimage conterexample intersection.gif:

{{center|$f\backslash left(A\_1\; \backslash cap\; A\_2\backslash right)\; \backslash subsetneq\; f\backslash left(A\_1\backslash right)\; \backslash cap\; f\backslash left(A\_2\backslash right).$}}

The map $f\; :\; \backslash R\; \backslash to\; \backslash R$ is defined by $x\; \backslash mapsto\; x^2,$ where $\backslash R$ denotes the real numbers. The sets $A\_1\; =\; [-4,\; 2]$ and $A\_2\; =\; [-2,\; 4]$ are shown in {{color|blue|blue}} immediately below the $x$-axis while their intersection $A\_3\; =\; [-2,\; 2]$ is shown in {{color|green|green}}.]]

If $f\; :\; \backslash \{1,\; 2\backslash \}\; \backslash to\; Y$ is constant, $L\; =\; \backslash \{1\backslash \},$ and $R\; =\; \backslash \{2\backslash \}$ then all four of the set containments

$$\backslash begin\{alignat\}\{4\}$$

f(L \cap R) ~&\subsetneq~ f(L) \cap f(R) \\

f(L \setminus R) ~&\supsetneq~ f(L) \setminus f(R) \\

f(X \setminus R) ~&\supsetneq~ f(X) \setminus f(R) \\

f(L \triangle R) ~&\supsetneq~ f(L) \triangle f(R) \\

\end{alignat}

are strict/proper (that is, the sets are not equal) since one side is the empty set while the other is non-empty. Thus equality is not guaranteed for even the simplest of functions.

The example above is now generalized to show that these four set equalities can fail for any constant function whose domain contains at least two (distinct) points.

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

1. The containment $~f(L\; \backslash setminus\; R)\; ~\backslash supsetneq~\; f(L)\; \backslash setminus\; f(R)~$ is strict: $$\backslash \{y\backslash \}\; ~=~\; f(L\; \backslash setminus\; R)\; ~\backslash neq~\; f(L)\; \backslash setminus\; f(R)\; ~=~\; \backslash \{y\backslash \}\; \backslash setminus\; \backslash \{y\backslash \}\; ~=~\; \backslash varnothing$$

   In words: functions might not distribute over set subtraction $\backslash ,\backslash setminus\backslash ,$

2. The containment $~f(X\; \backslash setminus\; R)\; ~\backslash supsetneq~\; f(X)\; \backslash setminus\; f(R)~$ is strict: $$\backslash \{y\backslash \}\; ~=~\; f(X\; \backslash setminus\; R)\; ~\backslash neq~\; f(X)\; \backslash setminus\; f(R)\; ~=~\; \backslash \{y\backslash \}\; \backslash setminus\; \backslash \{y\backslash \}\; ~=~\; \backslash varnothing.$$

3. The containment $~f(L\; ~\backslash triangle~\; R)\; ~\backslash supsetneq~\; f(L)\; ~\backslash triangle~\; f(R)~$ is strict: $$\backslash \{y\backslash \}\; ~=~\; f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; ~\backslash neq~\; f(L)\; ~\backslash triangle~\; f(R)\; ~=~\; \backslash \{y\backslash \}\; \backslash triangle\; \backslash \{y\backslash \}\; ~=~\; \backslash varnothing$$

   In words: functions might not distribute over symmetric difference $\backslash ,\backslash triangle\backslash ,$ (which can be defined as the set subtraction of two sets: $L\; \backslash triangle\; R\; =\; (L\; \backslash cup\; R)\; \backslash setminus\; (L\; \backslash cap\; R)$).

4. The containment $~f(L\; \backslash cap\; R)\; ~\backslash subsetneq~\; f(L)\; \backslash cap\; f(R)~$ is strict: $$\backslash varnothing\; ~=~\; f(\backslash varnothing)\; ~=~\; f(L\; \backslash cap\; R)\; ~\backslash neq~\; f(L)\; \backslash cap\; f(R)\; ~=~\; \backslash \{y\backslash \}\; \backslash cap\; \backslash \{y\backslash \}\; ~=~\; \backslash \{y\backslash \}$$

   In words: functions might not distribute over set intersection $\backslash ,\backslash cap\backslash ,$ (which can be defined as the set subtraction of two sets: $L\; \backslash cap\; R\; =\; L\; \backslash setminus\; (L\; \backslash setminus\; R)$).

What the set operations in these four examples have in common is that they either {{em|are}} set subtraction $\backslash setminus$ (examples (1) and (2)) or else they can naturally {{em|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 $\backslash ,\backslash subseteq\; \backslash text\{\; or\; \}\; \backslash supseteq\backslash ,$) can always be deduced by imagining the function $f$ as being {{em|constant}} and the two sets ($L$ and $R$) as being non-empty disjoint subsets of its domain. This is because {{em|every}} equality fails for such a function and sets: one side will be always be $\backslash varnothing$ and the other non-empty − from this fact, the correct choice of $\backslash ,\backslash subseteq\; \backslash text\{\; or\; \}\; \backslash supseteq\backslash ,$ can be deduced by answering: "which side is empty?" For example, to decide if the $?$ in

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

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

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

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

true.

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

Furthermore, this mnemonic can also be used to correctly deduce whether or not a set operation always distribute over images or preimages; for example, to determine whether or not $f(L\; \backslash cap\; R)$ always equals $f(L)\; \backslash cap\; f(R),$ or alternatively, whether or not $f^\{-1\}(L\; \backslash cap\; R)$ always equals $f^\{-1\}(L)\; \backslash cap\; f^\{-1\}(R)$ (although $\backslash ,\backslash cap\backslash ,$ was used here, it can replaced by $\backslash ,\backslash cup,\; \backslash ,\backslash setminus,\; \backslash text\{\; or\; \}\; \backslash ,\backslash 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.

Characterizations of when equality holds for {{em|all}} sets:

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

1. $f\; :\; X\; \backslash to\; Y$ is injective.
   • This means: $f(x)\; \backslash neq\; f(y)$ for all distinct $x,\; y\; \backslash in\; X.$

2. $f(L\; \backslash cap\; R)\; =\; f(L)\; \backslash ,\backslash cap\backslash ,\; f(R)\; \backslash ,\; \backslash text\{\; for\; all\; \}\; \backslash ,\; L,\; R\; \backslash subseteq\; X.$ (The equals sign $\backslash ,=\backslash ,$ can be replaced with $\backslash ,\backslash supseteq\backslash ,$).

3. $f(L\; \backslash ,\backslash setminus\; R)\; =\; f(L)\; \backslash ,\backslash setminus\backslash ,\; f(R)\; \backslash ;\; \backslash text\{\; for\; all\; \}\; \backslash ,\; L,\; R\; \backslash subseteq\; X.$ (The equals sign $\backslash ,=\backslash ,$ can be replaced with $\backslash ,\backslash subseteq\backslash ,$).

4. $f(X\; \backslash setminus\; R)\; =\; f(X)\; \backslash setminus\backslash ,\; f(R)\; \backslash ;\; \backslash text\{\; for\; all\; \}\; \backslash ,\; ~~~~~R\; \backslash subseteq\; X.$ (The equals sign $\backslash ,=\backslash ,$ can be replaced with $\backslash ,\backslash subseteq\backslash ,$).

5. $f(L\; \backslash ,\backslash triangle\backslash ,\; R)\; =\; f(L)\; \backslash ,\backslash triangle\backslash ,\; f(R)\; \backslash ;\; \backslash text\{\; for\; all\; \}\; \backslash ,\; L,\; R\; \backslash subseteq\; X.$ (The equals sign $\backslash ,=\backslash ,$ can be replaced with $\backslash ,\backslash subseteq\backslash ,$).

6. Any one of the four statements (b) - (e) but with the words "for all" replaced with any one of the following:

   1. "for all singleton subsets"
      • In particular, the statement that results from (d) gives a characterization of injectivity that explicitly involves only one point (rather than two): $f$ is injective if and only if $f(x)\; \backslash not\backslash in\; f(X\; \backslash setminus\; \backslash \{x\backslash \})\; \backslash ;\; \backslash text\{\; for\; every\; \}\; \backslash ,\; x\; \backslash 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).

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

Characterizations of equality: The following statements are equivalent:

1. $f(L\; \backslash cap\; R)\; ~=~\; f(L)\; \backslash cap\; f(R)$
2. $f(L\; \backslash cap\; R)\; ~\backslash supseteq~\; f(L)\; \backslash cap\; f(R)$
3. $L\; \backslash cap\; f^\{-1\}(f(R))\; ~\backslash subseteq~\; f^\{-1\}(f(L\; \backslash cap\; R))$
   • The left hand side $L\; \backslash cap\; f^\{-1\}(f(R))$ is always equal to $L\; \backslash cap\; f^\{-1\}(f(L)\; \backslash cap\; f(R))$ (because $L\; \backslash cap\; f^\{-1\}(f(R))\; ~\backslash subseteq~\; f^\{-1\}(f(L))$ always holds).

4. $R\; \backslash cap\; f^\{-1\}(f(L))\; ~\backslash subseteq~\; f^\{-1\}(f(L\; \backslash cap\; R))$
5. $L\; \backslash cap\; f^\{-1\}(f(R))\; ~=~\; f^\{-1\}(f(L\; \backslash cap\; R))\; \backslash cap\; L$
6. $R\; \backslash cap\; f^\{-1\}(f(L))\; ~=~\; f^\{-1\}(f(L\; \backslash cap\; R))\; \backslash cap\; R$
7. If $l\; \backslash in\; L$ satisfies $f(l)\; \backslash in\; f(R)$ then $f(l)\; \backslash in\; f(L\; \backslash cap\; R).$
8. If $y\; \backslash in\; f(L)$ but $y\; \backslash notin\; f(L\; \backslash cap\; R)$ then $y\; \backslash notin\; f(R).$
9. $f(L)\; \backslash ,\; \backslash setminus\; \backslash ,\; f(L\; \backslash cap\; R)\; ~\backslash subseteq~\; f(L)\; \backslash ,\; \backslash setminus\; \backslash ,\; f(R)$
10. $f(R)\; \backslash ,\; \backslash setminus\; \backslash ,\; f(L\; \backslash cap\; R)\; ~\backslash subseteq~\; f(R)\; \backslash ,\; \backslash setminus\; \backslash ,\; f(L)$
11. $f(L\; \backslash cup\; R)\; \backslash setminus\; f(L\; \backslash cap\; R)\; ~\backslash subseteq~\; f(L)\; \backslash ,\backslash triangle\backslash ,\; f(R)$
12. Any of the above three conditions (i) - (k) but with the subset symbol $\backslash ,\backslash subseteq\backslash ,$ replaced with an equals sign $\backslash ,=.\backslash ,$

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

1. $f$ is injective.See {{harvnb|Munkres|2000|p=21}}
2. The restriction $f\backslash big\backslash vert\_\{L\; \backslash cup\; R\}$ is injective.
3. $f^\{-1\}(f(R))\; ~\backslash subseteq~\; R$
4. $f^\{-1\}(f(L))\; ~\backslash subseteq~\; L$

5. $R$ is $f$-saturated; that is, $f^\{-1\}(f(R))\; =\; R$
6. $L$ is $f$-saturated; that is, $f^\{-1\}(f(L))\; =\; L$
7. $f(L)\; ~\backslash subseteq~\; f(L\; \backslash cap\; R)$
8. $f(R)\; ~\backslash subseteq~\; f(L\; \backslash cap\; R)$
9. $f(L\; \backslash ,\backslash setminus\backslash ,\; R)\; ~\backslash subseteq~\; f(L)\; \backslash setminus\; \backslash ,\; f(R)$ or equivalently, $f(L\; \backslash ,\backslash setminus\backslash ,\; R)\; ~=~\; f(L)\; \backslash setminus\; f(R)$
10. $f(R\; \backslash ,\backslash setminus\backslash ,\; L)\; ~\backslash subseteq~\; f(R)\; \backslash setminus\; \backslash ,\; f(L)$ or equivalently, $f(R\; \backslash ,\backslash setminus\backslash ,\; L)\; ~=~\; f(R)\; \backslash setminus\; f(L)$
11. $f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; \backslash subseteq\; f(L)\; ~\backslash triangle~\; f(R)$ or equivalently, $f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; =\; f(L)\; ~\backslash triangle~\; f(R)$
12. $R\; \backslash cap\; \backslash operatorname\{domain\}\; f\; \backslash ,\backslash subseteq\; L$
13. $L\; \backslash cap\; \backslash operatorname\{domain\}\; f\; \backslash ,\backslash subseteq\; R$
14. $R\; \backslash subseteq\; L$
15. $L\; \backslash subseteq\; R$

In addition, the following always hold:

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

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

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

Characterizations of equality: The following statements are equivalent:

1. $f(L\; \backslash setminus\; R)\; ~=~\; f(L)\; \backslash setminus\; f(R)$
2. $f(L\; \backslash setminus\; R)\; ~\backslash subseteq~\; f(L)\; \backslash setminus\; f(R)$
3. $L\; \backslash cap\; f^\{-1\}(f(R))\; ~\backslash subseteq~\; R$
4. $L\; \backslash cap\; f^\{-1\}(f(R))\; ~=~\; L\; \backslash cap\; R\; \backslash cap\; \backslash operatorname\{domain\}\; f$
5. Whenever $y\; \backslash in\; f(L)\; \backslash cap\; f(R)$ then $L\; \backslash cap\; f^\{-1\}(y)\; \backslash subseteq\; R.$
6. $f(L)\; \backslash cap\; f(R)\; ~\backslash subseteq~\; \backslash left\backslash \{y\; \backslash in\; f(L)\; :\; L\; \backslash cap\; f^\{-1\}(y)\; \backslash subseteq\; R\backslash right\backslash \}$
   • The set on the right hand side is always equal to $\backslash left\backslash \{y\; \backslash in\; f(L\; \backslash cap\; R)\; :\; L\; \backslash cap\; f^\{-1\}(y)\; \backslash ,\backslash subseteq\; R\backslash right\backslash \}.$

7. $f(L)\; \backslash cap\; f(R)\; ~=~\; \backslash left\backslash \{y\; \backslash in\; f(L)\; :\; L\; \backslash cap\; f^\{-1\}(y)\; \backslash subseteq\; R\backslash right\backslash \}$
   • This is the above condition (f) but with the subset symbol $\backslash ,\backslash subseteq\backslash ,$ replaced with an equals sign $\backslash ,=.\backslash ,$

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

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

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

1. $f$ is injective.
2. The restriction $f\backslash big\backslash vert\_\{L\; \backslash cup\; R\}$ is injective.
3. $f^\{-1\}(f(R))\; ~\backslash subseteq~\; R$Note that this condition depends entirely on $R$ and {{em|not}} on $L.$ or equivalently, $R\; \backslash cap\; \backslash operatorname\{domain\}\; f\; ~=~\; f^\{-1\}(f(R))$
4. $R$ is $f$-saturated; that is, $R\; =\; f^\{-1\}(f(R)).$
5. $f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; \backslash subseteq\; f(L)\; ~\backslash triangle~\; f(R)$ or equivalently, $f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; =\; f(L)\; ~\backslash triangle~\; f(R)$

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

Characterizations of equality: The following statements are equivalent:

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

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

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

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

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

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

Characterizations of equality: The following statements are equivalent:

1. $f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; =\; f(L)\; ~\backslash triangle~\; f(R)$
2. $f\backslash left(L\; ~\backslash triangle~\; R\backslash right)\; \backslash subseteq\; f(L)\; ~\backslash triangle~\; f(R)$
3. $f(L\; \backslash ,\backslash setminus\backslash ,\; R)\; =\; f(L)\; \backslash ,\backslash setminus\backslash ,\; f(R)$  and  $f(R\; \backslash ,\backslash setminus\backslash ,\; L)\; =\; f(R)\; \backslash ,\backslash setminus\backslash ,\; f(L)$
4. $f(L\; \backslash ,\backslash setminus\backslash ,\; R)\; \backslash subseteq\; f(L)\; \backslash ,\backslash setminus\backslash ,\; f(R)$  and  $f(R\; \backslash ,\backslash setminus\backslash ,\; L)\; \backslash subseteq\; f(R)\; \backslash ,\backslash setminus\backslash ,\; f(L)$
5. $L\; \backslash cap\; f^\{-1\}(f(R))\; ~\backslash subseteq~\; R$  and  $R\; \backslash cap\; f^\{-1\}(f(L))\; ~\backslash subseteq~\; L$
   • The inclusions $L\; \backslash cap\; f^\{-1\}(f(R))\; ~\backslash subseteq~\; f^\{-1\}(f(L))$ and $R\; \backslash cap\; f^\{-1\}(f(L))\; ~\backslash subseteq~\; f^\{-1\}(f(R))$ always hold.

6. $L\; \backslash cap\; f^\{-1\}(f(R))\; ~=~\; R\; \backslash cap\; f^\{-1\}(f(L))$
   • If this above set equality holds, then this set will also be equal to both $L\; \backslash cap\; R\; \backslash cap\; \backslash operatorname\{domain\}\; f$ and $L\; \backslash cap\; R\; \backslash cap\; f^\{-1\}(f(L\; \backslash cap\; R)).$

7. $L\; \backslash cap\; f^\{-1\}(f(L\; \backslash cap\; R))\; ~=~\; R\; \backslash cap\; f^\{-1\}(f(L\; \backslash cap\; R))$  and  $f(L\; \backslash cap\; R)\; ~\backslash supseteq~\; f(L)\; \backslash cap\; f(R).$

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

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

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

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

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

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

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

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

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

• In general, only $f(X\; \backslash setminus\; R)\; \backslash ,\backslash supseteq\backslash ,\; f(X)\; \backslash setminus\; f(R)$ always holds and equality is not guaranteed; but replacing "$f(R)$" with its subset "$\backslash left\backslash \{\; y\; \backslash in\; f(R)\; :\; f^\{-1\}(y)\; \backslash subseteq\; R\; \backslash right\backslash \}$" results in a formula in which equality is {{em|always}} guaranteed:

  $$f(X\; \backslash setminus\; R)\; \backslash ,=\backslash ,\; f(X)\; \backslash setminus\; \backslash left\backslash \{\; y\; \backslash in\; f(R)\; :\; f^\{-1\}(y)\; \backslash subseteq\; R\; \backslash right\backslash \}.$$

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

  $$f(X\; \backslash setminus\; R)\; =\; f(X)\; \backslash setminus\; f(R)\; \backslash quad\; \backslash text\{\; if\; and\; only\; if\; \}\; \backslash quad\; f(R)\; =\; \backslash left\backslash \{\; y\; \backslash in\; f(R)\; :\; f^\{-1\}(y)\; \backslash subseteq\; R\; \backslash right\backslash \}\; \backslash quad\; \backslash text\{\; if\; and\; only\; if\; \}\; \backslash quad\; f^\{-1\}(f(R))\; \backslash subseteq\; R.$$

• If $f\_R\; :=\; \backslash left\backslash \{y\; \backslash in\; f(X)\; :\; f^\{-1\}(y)\; \backslash subseteq\; R\backslash right\backslash \}$ then $f(X\; \backslash setminus\; R)\; =\; f(X)\; \backslash setminus\; f\_R,$ which can be written more symmetrically as $f(X\; \backslash setminus\; R)\; =\; f\_X\; \backslash setminus\; f\_R$ (since $f\_X\; =\; f(X)$).

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

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

It follows from the above formulas for the image of a set subtraction that for any function $f\; :\; X\; \backslash to\; Y$ and any set $L,$$$\backslash begin\{alignat\}\{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{alignat}

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

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

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

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

:$L\; \backslash cap\; f^\{-1\}(y)\; \backslash subseteq\; L\; \backslash setminus\; R~$ if and only if $~L\; \backslash cap\; R\; \backslash cap\; f^\{-1\}(y)\; =\; \backslash varnothing~$ if and only if $~R\; \backslash cap\; f^\{-1\}(y)\; \backslash subseteq\; R\; \backslash setminus\; L~$ if and only if $~y\; \backslash not\backslash in\; f(L\; \backslash cap\; R).$

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

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

(Pre)Images of operations on images

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

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

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

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

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

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

and so

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

Let $\backslash prod\; Y\_\{\backslash bull\}\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash prod\_\{j\; \backslash in\; J\}\; Y\_j$ and for every $k\; \backslash in\; J,$ let

$$\backslash pi\_k\; ~:~\; \backslash prod\_\{j\; \backslash in\; J\}\; Y\_j\; ~\backslash to~\; Y\_k$$

denote the canonical projection onto $Y\_k.$

Definitions

Given a collection of maps $F\_j\; :\; X\; \backslash to\; Y\_j$ indexed by $j\; \backslash in\; J,$ define the map

$$\backslash begin\{alignat\}\{4\}$$

\left(F_j\right)_{j \in J} :\;&& X &&\;\to\; & \prod_{j \in J} Y_j \\[0.3ex]

&& x &&\;\mapsto\;& \left(F_j\left(x_j\right)\right)_{j \in J}, \\

\end{alignat}

which is also denoted by $F\_\{\backslash bull\}\; =\; \backslash left(F\_j\backslash right)\_\{j\; \backslash in\; J\}.$ This is the unique map satisfying

$$\backslash pi\_j\; \backslash circ\; F\_\{\backslash bull\}\; =\; F\_j\; \backslash quad\; \backslash text\{\; for\; all\; \}\; j\; \backslash in\; J.$$

Conversely, if given a map $$F\; ~:~\; X\; ~\backslash to~\; \backslash prod\_\{j\; \backslash in\; J\}\; Y\_j$$ then $F\; =\; \backslash left(\backslash pi\_j\; \backslash circ\; F\backslash right)\_\{j\; \backslash in\; J\}.$

Explicitly, what this means is that if

$$F\_k\; ~\backslash stackrel\{\backslash scriptscriptstyle\backslash text\{def\}\}\{=\}~\; \backslash pi\_k\; \backslash circ\; F\; ~:~\; X\; ~\backslash to~\; Y\_k$$

is defined for every $k\; \backslash in\; J,$ then $F$ the unique map satisfying: $\backslash pi\_j\; \backslash circ\; F\; =\; F\_j$ for all $j\; \backslash in\; J;$ or said more briefly, $F\; =\; \backslash left(F\_j\backslash right)\_\{j\; \backslash in\; J\}.$

The map $F\_\{\backslash bull\}\; =\; \backslash left(F\_j\backslash right)\_\{j\; \backslash in\; J\}\; ~:~\; X\; ~\backslash to~\; \backslash prod\_\{j\; \backslash in\; J\}\; Y\_j$ should not be confused with the Cartesian product $\backslash prod\_\{j\; \backslash in\; J\}\; F\_j$ of these maps, which is by definition is the map

$$\backslash begin\{alignat\}\{4\}$$

\prod_{j \in J} F_j :\;&& \prod_{j \in J} X &&~\;\to\;~ & \prod_{j \in J} Y_j \\[0.3ex]

&& \left(x_j\right)_{j \in J} &&~\;\mapsto\;~& \left(F_j\left(x_j\right)\right)_{j \in J} \\

\end{alignat}

with domain $\backslash prod\_\{j\; \backslash in\; J\}\; X\; =\; X^J$ rather than $X.$

Preimage and images of a Cartesian product

Suppose $F\_\{\backslash bull\}\; =\; \backslash left(F\_j\backslash right)\_\{j\; \backslash in\; J\}\; ~:~\; X\; ~\backslash to~\; \backslash prod\_\{j\; \backslash in\; J\}\; Y\_j.$

If $A\; ~\backslash subseteq~\; X$ then

$$F\_\{\backslash bull\}(A)\; ~~\backslash ;\backslash color\{Red\}\{\backslash subseteq\}\backslash color\{Black\}\{\}\backslash ;~~\; \backslash prod\_\{j\; \backslash in\; J\}\; F\_j(A).$$

If $B\; ~\backslash subseteq~\; \backslash prod\_\{j\; \backslash in\; J\}\; Y\_j$ then

$$F\_\{\backslash bull\}^\{-1\}(B)\; ~~\backslash ;\backslash color\{Red\}\{\backslash subseteq\}\backslash color\{Black\}\{\}\backslash ;~~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; F\_j^\{-1\}\backslash left(\backslash pi\_j(B)\backslash right)$$

where equality will hold if $B\; =\; \backslash prod\_\{j\; \backslash in\; J\}\; \backslash pi\_j(B),$ in which case $F\_\{\backslash bull\}^\{-1\}(B)\; =\; \backslash displaystyle\backslash bigcap\_\{j\; \backslash in\; J\}\; F\_j^\{-1\}\backslash left(\backslash pi\_j(B)\backslash right)$ and

{{NumBlk||$$F\_\{\backslash bull\}^\{-1\}\backslash left(\backslash prod\_\{j\; \backslash in\; J\}\; \backslash pi\_j(B)\backslash right)\; ~=~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; F\_j^\{-1\}\backslash left(\backslash pi\_j(B)\backslash right).$$|{{EquationRef|Eq. 11a}}}}

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

{{NumBlk||$$F\_\{\backslash bull\}^\{-1\}\backslash left(\backslash prod\_\{j\; \backslash in\; J\}\; B\_j\backslash right)\; ~=~\; \backslash bigcap\_\{j\; \backslash in\; J\}\; F\_j^\{-1\}\backslash left(B\_j\backslash right)$$|{{EquationRef|Eq. 11b}}}}

and $\backslash pi\_j(B)\; =\; B\_j$ for all $j\; \backslash in\; J.$

Equivalences and implications of images and preimages

Intersection of a set and a (pre)image

The following statements are equivalent:

1. $\backslash varnothing\; =\; f(L)\; \backslash cap\; R$
2. $\backslash varnothing\; =\; L\; \backslash cap\; f^\{-1\}(R)${{sfn|Császár|1978|pp=102-120}}
3. $\backslash varnothing\; =\; f^\{-1\}(f(L))\; \backslash cap\; f^\{-1\}(R)$
4. $\backslash varnothing\; =\; f^\{-1\}(f(L)\; \backslash cap\; R)$

Thus for any $t,${{sfn|Császár|1978|pp=102-120}} $$t\; \backslash not\backslash in\; f(L)\; \backslash quad\; \backslash text\{\; if\; and\; only\; if\; \}\; \backslash quad\; L\; \backslash cap\; f^\{-1\}(t)\; =\; \backslash varnothing.$$

A {{em|family of sets}} or simply a {{em|family}} is a set whose elements are sets.

A {{em|family over $X$}} is a family of subsets of $X.$

The {{em|power set}} of a set $X$ is the set of all subsets of $X$:

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

Notation for sequences of sets

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

$$S\_\{\backslash bull\}\; =\; \backslash left(S\_i\backslash right)\_\{i=1\}^\{\backslash infty\}\; \backslash qquad\; \backslash text\{\; or\; \}\; \backslash qquad\; S\_\{\backslash bull\}\; =\; \backslash left(S\_i\backslash right)\_\{i\; \backslash in\; \backslash N\}$$

where $\backslash N$ denotes the natural numbers.

A notation $S\_\{\backslash bull\}\; =\; \backslash left(S\_i\backslash right)\_\{i\; \backslash in\; I\}$ indicates that $S\_\{\backslash bull\}$ is a net directed by $(I,\; \backslash 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\; =\; \backslash N$) and $\backslash ,\backslash leq\backslash ,$ is the natural order on $\backslash N.$

Disjoint and monotone sequences of sets

If $S\_i\; \backslash cap\; S\_j\; =\; \backslash varnothing$ for all distinct indices $i\; \backslash neq\; j$ then $S\_\{\backslash bull\}$ is called a {{em|pairwise disjoint}} or simply a {{em|disjoint}}.

A sequence or net $S\_\{\backslash bull\}$ of set is called {{em|increasing}} or {{em|non-decreasing}} if (resp. {{em|decreasing}} or {{em|non-increasing}}) if for all indices $i\; \backslash leq\; j,$ $S\_i\; \backslash subseteq\; S\_j$ (resp. $S\_i\; \backslash supseteq\; S\_j$).

A sequence or net $S\_\{\backslash bull\}$ of set is called {{em|strictly increasing}} (resp. {{em|strictly decreasing}}) if it is non-decreasing (resp. is non-increasing) and also $S\_i\; \backslash neq\; S\_j$ for all {{em|distinct}} indices $i\; \backslash text\{\; and\; \}\; j.$

It is called {{em|monotone}} if it is non-decreasing or non-increasing and it is called {{em|strictly monotone}} if it is strictly increasing or strictly decreasing.

A sequences or net $S\_\{\backslash bull\}$ is said to {{em|increase to $S,$}} denoted by $S\_\{\backslash bull\}\; \backslash uparrow\; S${{sfn|Durrett|2019|pp=1-8}} or $S\_\{\backslash bull\}\; \backslash nearrow\; S,$ if $S\_\{\backslash bull\}$ is increasing and the union of all $S\_i$ is $S;$ that is, if $$\backslash bigcup\_\{n\}\; S\_n\; =\; S\; \backslash qquad\; \backslash text\{\; and\; \}\; \backslash qquad\; S\_i\; \backslash subseteq\; S\_j\; \backslash quad\; \backslash text\{\; whenever\; \}\; i\; \backslash leq\; j.$$

It is said to {{em|decrease to $S,$}} denoted by $S\_\{\backslash bull\}\; \backslash downarrow\; S${{sfn|Durrett|2019|pp=1-8}} or $S\_\{\backslash bull\}\; \backslash searrow\; S,$ if $S\_\{\backslash bull\}$ is increasing and the intersection of all $S\_i$ is $S$ that is, if $$\backslash bigcap\_\{n\}\; S\_n\; =\; S\; \backslash qquad\; \backslash text\{\; and\; \}\; \backslash qquad\; S\_i\; \backslash supseteq\; S\_j\; \backslash quad\; \backslash text\{\; whenever\; \}\; i\; \backslash leq\; j.$$

Definitions of elementwise operations on families

If $\backslash mathcal\{L\}\; \backslash text\{\; and\; \}\; \backslash mathcal\{R\}$ are families of sets and if $S$ is any set then define:{{sfn|Császár|1978|pp=53-65}}

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

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

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

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

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

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

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

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

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

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

{{Families of sets|expanded}}

A family $\backslash mathcal\{L\}$ is called {{em|isotone}}, {{em|ascending}}, or {{em|upward closed}} in $X$ if $\backslash mathcal\{L\}\; \backslash subseteq\; \backslash wp(X)$ and $\backslash mathcal\{L\}\; =\; \backslash mathcal\{L\}^\{\backslash uparrow\; X\}.${{sfn|Császár|1978|pp=53-65}}

A family $\backslash mathcal\{L\}$ is called {{em|downward closed}} if $\backslash mathcal\{L\}\; =\; \backslash mathcal\{L\}^\{\backslash downarrow\}.$

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

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

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

• {{em|{{pi}}−system}} if $\backslash mathcal\{L\}\; \backslash neq\; \backslash varnothing$ and $\backslash mathcal\{L\}$ is closed under finite-intersections.
• Every non-empty family $\backslash mathcal\{L\}$ is contained in a unique smallest (with respect to $\backslash subseteq$) {{pi}}−system that is denoted by $\backslash pi(\backslash mathcal\{L\})$ and called {{em|the {{pi}}−system generated by $\backslash mathcal\{L\}.$}}
• {{em|filter subbase}} and is said to have {{em|the finite intersection property}} if $\backslash mathcal\{L\}\; \backslash neq\; \backslash varnothing$ and $\backslash varnothing\; \backslash not\backslash in\; \backslash pi(\backslash mathcal\{L\}).$
• {{em|filter on $X$}} if $\backslash mathcal\{L\}\; \backslash neq\; \backslash varnothing$ is a family of subsets of $X$ that is a {{pi}}−system, is upward closed in $X,$ and is also {{em|proper}}, which by definition means that it does not contain the empty set as an element.
• {{em|prefilter}} or {{em|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.$
• {{em|algebra on $X$}} is a non-empty family of subsets of $X$ that contains the empty set, forms a {{pi}}−system, and is also closed under complementation with respect to $X.$
• {{em|σ-algebra on $X$}} is an algebra on $X$ that is closed under countable unions (or equivalently, closed under countable intersections).

Sequences of sets often arise in measure theory.

Algebra of sets

{{See also|Algebra of sets|:Category:Properties of binary operations}}

A family $\backslash Phi$ of subsets of a set $X$ is said to be {{em|an algebra of sets}} if $\backslash varnothing\; \backslash in\; \backslash Phi$ and for all $L,\; R\; \backslash in\; \backslash Phi,$ all three of the sets $X\; \backslash setminus\; R,\; \backslash ,L\; \backslash cap\; R,$ and $L\; \backslash cup\; R$ are elements of $\backslash Phi.${{cite web|url=https://encyclopediaofmath.org/wiki/Algebra_of_sets|title=Algebra of sets|website=Encyclopediaofmath.org|date=16 August 2013|access-date=8 November 2020}}

The article on this topic lists set identities and other relationships these three operations.

Every algebra of sets is also a ring of sets and a π-system.

Algebra generated by a family of sets

Given any family $\backslash mathcal\{S\}$ of subsets of $X,$ there is a unique smallestHere "smallest" means relative to subset containment. So if $\backslash Phi$ is any algebra of sets containing $\backslash mathcal\{S\},$ then $\backslash Phi\_\{\backslash mathcal\{S\}\}\; \backslash subseteq\; \backslash Phi.$ algebra of sets in $X$ containing $\backslash mathcal\{S\}.$

It is called {{em|the algebra generated by $\backslash mathcal\{S\}$}} and it will be denote it by $\backslash Phi\_\{\backslash mathcal\{S\}\}.$

This algebra can be constructed as follows:

1. If $\backslash mathcal\{S\}\; =\; \backslash varnothing$ then $\backslash Phi\_\{\backslash mathcal\{S\}\}\; =\; \backslash \{\backslash varnothing,\; X\backslash \}$ and we are done. Alternatively, if $\backslash mathcal\{S\}$ is empty then $\backslash mathcal\{S\}$ may be replaced with $\backslash \{\backslash varnothing\backslash \},\; \backslash \{X\backslash \},\; \backslash text\{\; or\; \}\; \backslash \{\backslash varnothing,\; X\backslash \}$ and continue with the construction.
2. Let $\backslash mathcal\{S\}\_0$ be the family of all sets in $\backslash mathcal\{S\}$ together with their complements (taken in $X$).
3. Let $\backslash mathcal\{S\}\_1$ be the family of all possible finite intersections of sets in $\backslash mathcal\{S\}\_0.$Since $\backslash mathcal\{S\}\; \backslash neq\; \backslash varnothing,$ there is some $S\; \backslash in\; \backslash mathcal\{S\}\_0$ such that its complement also belongs to $\backslash mathcal\{S\}\_0.$ The intersection of these two sets implies that $\backslash varnothing\; \backslash in\; \backslash mathcal\{S\}\_1.$ The union of these two sets is equal to $X,$ which implies that $X\; \backslash in\; \backslash Phi\_\{\backslash mathcal\{S\}\}.$
4. Then the algebra generated by $\backslash mathcal\{S\}$ is the set $\backslash Phi\_\{\backslash mathcal\{S\}\}$ consisting of all possible finite unions of sets in $\backslash mathcal\{S\}\_1.$

Let $\backslash mathcal\{L\},\; \backslash mathcal\{M\},$ and $\backslash mathcal\{R\}$ be families of sets over $X.$

On the left hand sides of the following identities, $\backslash mathcal\{L\}$ is the {{em|L}}{{hsp}}eft most family, $\backslash mathcal\{M\}$ is in the {{em|M}}{{hsp}}iddle, and $\backslash mathcal\{R\}$ is the {{em|R}}{{hsp}}ight most set.

Commutativity:{{sfn|Császár|1978|pp=53-65}}

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

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

Associativity:{{sfn|Császár|1978|pp=53-65}}

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

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

Identity:

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

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

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

Domination:

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

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

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

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

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

$$\backslash varnothing\; \backslash ;(\backslash setminus)\backslash ;\; \backslash mathcal\{R\}\; =\; \backslash varnothing$$

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

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

If $L$ and $R$ are subsets of a vector space $X$ and if $s$ is a scalar then

$$\backslash wp(s\; L)\; ~=~\; s\; \backslash wp(L)$$

$$\backslash wp(L\; +\; R)\; ~\backslash supseteq~\; \backslash wp(L)\; +\; \backslash wp(R).$$

Suppose that $L$ is any set such that $L\; \backslash supseteq\; R\_i$ for every index $i.$

If $R\_\backslash bull$ decreases to $R$ then $L\; \backslash setminus\; R\_\backslash bull\; :=\; \backslash left(L\; \backslash setminus\; R\_i\backslash right)\_i$ increases to $L\; \backslash setminus\; R${{sfn|Durrett|2019|pp=1-8}}

whereas if instead $R\_\backslash bull$ increases to $R$ then $L\; \backslash setminus\; R\_\backslash bull$ decreases to $L\; \backslash setminus\; R.$

If $L\; \backslash text\{\; and\; \}\; R$ are arbitrary sets and if $L\_\backslash bull\; =\; \backslash left(L\_i\backslash right)\_i$ increases (resp. decreases) to $L$ then $\backslash left(L\_i\; \backslash setminus\; R\backslash right)\_i$ increase (resp. decreases) to $L\; \backslash setminus\; R.$

Suppose that $S\_\backslash bull\; =\; \backslash left(S\_i\backslash right)\_\{i\; =\; 1\}^\backslash infty$ is any sequence of sets, that $S\; \backslash subseteq\; \backslash bigcup\_i\; S\_i$ is any subset, and for every index $i,$ let $D\_i\; =\; \backslash left(S\_i\; \backslash cap\; S\backslash right)\; \backslash setminus\; \backslash bigcup\_\{m=1\}^i\; \backslash left(S\_m\; \backslash cap\; S\backslash right).$

Then $S\; =\; \backslash bigcup\_i\; D\_i$ and $D\_\backslash bull\; :=\; \backslash left(D\_i\backslash right)\_\{i=1\}^\backslash infty$ is a sequence of pairwise disjoint sets.{{sfn|Durrett|2019|pp=1-8}}

Suppose that $S\_\backslash bull\; =\; \backslash left(S\_i\backslash right)\_\{i\; =\; 1\}^\backslash infty$ is non-decreasing, let $S\_0\; =\; \backslash varnothing,$ and let $D\_i\; =\; S\_i\; \backslash setminus\; S\_\{i-1\}$ for every $i\; =\; 1,\; 2,\; \backslash ldots.$ Then $\backslash bigcup\_i\; S\_i\; =\; \backslash bigcup\_i\; D\_i$ and $D\_\backslash bull\; =\; \backslash left(D\_i\backslash right)\_\{i=1\}^\backslash infty$ is a sequence of pairwise disjoint sets.{{sfn|Durrett|2019|pp=1-8}}

• {{annotated link|Algebra of sets}}
• {{annotated link|Complement (set theory)}}
• {{annotated link|Image (mathematics)#Properties}}
• {{annotated link|Inclusion–exclusion principle}}
• {{annotated link|Intersection (set theory)}}
• {{annotated link|List of mathematical identities}}
• {{annotated link|Naive set theory}}
• {{annotated link|Pigeonhole principle}}
• {{annotated link|Set (mathematics)}}
• {{annotated link|Simple theorems in the algebra of sets}}
• {{annotated link|Symmetric difference (set theory)}}
• {{annotated link|Union (set theory)}}

Notes

{{reflist|group=note}}

Proofs

{{reflist|group=proof}}

{{reflist}}

{{sfn whitelist|CITEREFDurrett2019}}

• {{cite book|last=Artin|first= Michael|author-link=Michael Artin|title= Algebra|year=1991|publisher=Prentice Hall|isbn= 81-203-0871-9}}
• {{cite book|last=Blyth|first=T.S.|title=Lattices and Ordered Algebraic Structures|publisher= Springer|year= 2005|isbn=1-85233-905-5}}.
• {{cite journal|last=Bylinski|first=Czeslaw|date=2004|title=Some Basic Properties of Sets|url=http://www.mizar.org/JFM/Vol1/zfmisc_1.html|journal=Journal of Formalized Mathematics|volume=1|issue=|pages=|doi=|access-date=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}}. [https://books.google.com/books?id=UfdossHPlkgC&dq=%22algebra+of+sets%22&pg=PA17-IA8 "SUPPLEMENT TO CHAPTER II THE ALGEBRA OF SETS"].
• {{Császár General Topology}}
• {{Dixmier General Topology}}
• {{Dolecki Mynard Convergence Foundations Of Topology}}
• {{Dugundji Topology}}
• {{Durrett Probability Theory and Examples 5th Edition}}
• {{cite book|last=Halmos|first=Paul R.|author-link=Paul Halmos|title=Naive set theory|url=https://archive.org/details/naivesettheory0000halm|url-access=registration|series=The University Series in Undergraduate Mathematics|publisher=van Nostrand Company|year=1960|isbn=9780442030643 |zbl=0087.04403}}
• {{Joshi Introduction to General Topology}}
• {{cite book|last1=Kelley|first1=John L.|title=General Topology|edition=2|series=Graduate Texts in Mathematics|volume=27|year=1985|publisher=Birkhäuser|isbn=978-0-387-90125-1}}
• {{Köthe Topological Vector Spaces I}}
• {{cite book|last=Monk|first=James Donald|title=Introduction to Set Theory|publisher=McGraw-Hill|publication-place=New York|url=http://euclid.colorado.edu/~monkd/monk11.pdf|year=1969|series=International series in pure and applied mathematics|isbn=978-0-07-042715-0|oclc=1102}}
• {{Munkres Topology|edition=2}}
• {{Narici Beckenstein Topological Vector Spaces|edition=2}}
• {{cite journal|last=Padlewska|first=Beata|date=1990|title=Families of Sets|url=http://mizar.org/JFM/Vol1/setfam_1.html|journal=Journal of Formalized Mathematics|volume=1|issue=|pages=1|doi=|access-date=5 October 2021}}
• {{Schechter Handbook of Analysis and Its Foundations}}
• {{Schubert Topology}}
• Stoll, Robert R.; {{em|Set Theory and Logic}}, Mineola, N.Y.: Dover Publications (1979) {{ISBN|0-486-63829-4}}. [https://books.google.com/books?id=3-nrPB7BQKMC&pg=PA16 "The Algebra of Sets", pp 16—23].
• {{cite journal|last=Trybulec|first=Zinaida|date=2002|title=Properties of subsets|url=https://fm.mizar.org/1990-1/pdf1-1/subset_1.pdf|journal=Journal of Formalized Mathematics|volume=1|issue=|pages=1|doi=|access-date=5 October 2021}}
• {{Wilansky Modern Methods in Topological Vector Spaces|edition=1}}
• {{Willard General Topology}}

• [http://www.apronus.com/provenmath/btheorems.htm Operations on Sets at ProvenMath]

{{Mathematical logic}}

{{Set theory}}

{{DEFAULTSORT:Set identities and relations}}

Category:Articles containing proofs

Category:Basic concepts in infinite set theory

Category:Basic concepts in set theory

Category:Families of sets

Category:Functions and mappings

Category:Isomorphism theorems

Category:Mathematical identities

Category:Mathematics-related lists

Category:Mathematical relations

Category:Operations on sets

Category:Set theory

Category:Theorems in the foundations of mathematics