List of set identities and relations

${\displaystyle \,\ast \,}$

${\displaystyle z\,\ast \,R=z}$

${\displaystyle R}$

${\displaystyle \,\ast \,}$

${\displaystyle L\,\ast \,z=z}$

${\displaystyle L.}$

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

$${\displaystyle {\begin{alignedat}{10}X\cup L&\;=\;&&X&\;=\;&L\cup X~~~~{\text{ where }}L\subseteq X\\[1.4ex]\varnothing \cap L&\;=\;&&\varnothing &\;=\;&L\cap \varnothing \\[1.4ex]\varnothing \times L&\;=\;&&\varnothing &\;=\;&L\times \varnothing \\[1.4ex]\varnothing \setminus L&\;=\;&&\varnothing &\;\;&\\[1.4ex]\end{alignedat}}}$$ but ${\displaystyle \varnothing }$ is not a right absorbing element of set subtraction since $${\displaystyle L\setminus \varnothing =L}$$ where ${\textstyle L\setminus \varnothing =\varnothing }$ if and only if ${\textstyle L=\varnothing .}$

Double complement or involution law:

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

$${\displaystyle L\setminus \varnothing =L}$$ $${\displaystyle {\begin{alignedat}{4}\varnothing &=L&&\setminus L\\&=\varnothing &&\setminus L\\&=L&&\setminus X~~~~{\text{ where }}L\subseteq X\\\end{alignedat}}}$$^[3]

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

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

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

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

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

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

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

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

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

De Morgan's laws state that for ${\displaystyle L,R\subseteq X:}$

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

Unions, intersection, and symmetric difference are

Set subtraction is not commutative. However, the commutativity of set subtraction can be characterized: from ${\displaystyle (L\,\setminus \,R)\cap (R\,\setminus \,L)=\varnothing }$ it follows that: $${\displaystyle L\,\setminus \,R=R\,\setminus \,L\quad {\text{ if and only if }}\quad L=R.}$$ Said differently, if distinct symbols always represented distinct sets, then the only true formulas of the form ${\displaystyle \,\cdot \,\,\setminus \,\,\cdot \,=\,\cdot \,\,\setminus \,\,\cdot \,}$ that could be written would be those involving a single symbol; that is, those of the form: ${\displaystyle S\,\setminus \,S=S\,\setminus \,S.}$ But such formulas are necessarily true for every binary operation ${\displaystyle \,\ast \,}$ (because ${\displaystyle x\,\ast \,x=x\,\ast \,x}$ must hold by definition of equality), and so in this sense, set subtraction is as diametrically opposite to being commutative as is possible for a binary operation. Set subtraction is also neither

${\displaystyle (L\setminus L)\setminus R=L\setminus (L\setminus R)}$

${\displaystyle L\cap R=\varnothing }$

${\displaystyle (R\setminus L)\setminus L=R\setminus (L\setminus L).}$

Absorption laws:

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

Other properties

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

Intervals:

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

The following statements are equivalent for any ${\displaystyle L,R\subseteq X:}$^[3]

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

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

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

The following statements are equivalent:

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

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

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

If ${\displaystyle L}$ is any set then the following are equivalent:

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

If ${\displaystyle L}$ is any set then the following are equivalent:

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

Given any ${\displaystyle x,}$ the following are equivalent:

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

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

Inclusion is a

${\displaystyle \,\subseteq ,\,}$

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

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

Existence of a

$${\displaystyle \varnothing \subseteq L\subseteq X}$$

$${\displaystyle L\subseteq L\cup R}$$

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

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

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

$${\displaystyle L\cap R\subseteq L}$$

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

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

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

Other inclusion properties:

$${\displaystyle L\setminus R\subseteq L}$$ $${\displaystyle (L\setminus R)\cap L=L\setminus R}$$

• If ${\displaystyle L\subseteq R}$ then ${\displaystyle L\,\triangle \,R=R\setminus L.}$
• If ${\displaystyle L\subseteq X}$ and ${\displaystyle R\subseteq Y}$ then ${\displaystyle L\times R\subseteq X\times Y}$[3]

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

Precedence rules

There is no universal agreement on the

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

Sometimes, set complement (subtraction) ${\displaystyle \,\setminus \,}$ is also associated with

${\displaystyle \,\lnot ,\,}$

${\displaystyle L\setminus R=\{x:(x\in L)\land \lnot (x\in R)\}}$

${\displaystyle L\land \lnot R}$

${\displaystyle L\cup M\setminus R}$

${\displaystyle L\cup (M\setminus R)}$

${\displaystyle L\lor M\land \lnot R}$

${\displaystyle L\lor (M\land \lnot R).}$

${\displaystyle L\land \lnot M\land R}$

${\displaystyle L\land (\lnot M)\land R,}$

${\displaystyle (L\land (\lnot M))\land R}$

${\displaystyle L\land ((\lnot M)\land R)~=~L\land (R\land (\lnot M))}$

${\displaystyle (\lnot M)\land R}$

${\displaystyle R\land (\lnot M)}$

${\displaystyle L\setminus M\cap R}$

${\displaystyle (L\setminus M)\cap R=L\cap (R\setminus M);}$

${\displaystyle L\land (\lnot M)\land R=(L\land R)\land \lnot M,}$

${\displaystyle (L\cap R)\setminus M}$

${\displaystyle (L\setminus M)\setminus R\neq L\setminus (M\setminus R),}$

${\displaystyle L\setminus M\setminus R}$

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

Definition: A

${\displaystyle \,\ast \,}$

${\displaystyle (L\,\ast \,M)\,\ast \,R=L\,\ast \,(M\,\ast \,R)}$

The following set operators are associative:^[3]

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

For set subtraction, instead of associativity, only the following is always guaranteed: $${\displaystyle (L\,\setminus \,M)\,\setminus \,R\;~~{\color {red}{\subseteq }}~~\;L\,\setminus \,(M\,\setminus \,R)}$$ where equality holds if and only if ${\displaystyle L\cap R=\varnothing }$ (this condition does not depend on ${\displaystyle M}$). Thus ${\textstyle \;(L\setminus M)\setminus R=L\setminus (M\setminus R)\;}$ if and only if ${\displaystyle \;(R\setminus M)\setminus L=R\setminus (M\setminus L),\;}$ where the only difference between the left and right hand side set equalities is that the locations of ${\displaystyle L{\text{ and }}R}$ have been swapped.

Definition: If ${\displaystyle \ast {\text{ and }}\bullet }$ are

${\displaystyle \,\ast \,}$

left distributes over

${\displaystyle \,\bullet \,}$

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

${\displaystyle \,\ast \,}$

right distributes over

${\displaystyle \,\bullet \,}$

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

${\displaystyle \,\ast \,}$

distributes over

${\displaystyle \,\bullet \,}$

${\displaystyle \,\bullet \,.\,}$