This article lists mathematical properties and laws of sets, involving the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures for evaluating expressions, and performing calculations, involving these operations and relations. The binary operations of set union ( ∪ {\displaystyle \cup } ) and intersection ( ∩ {\displaystyle \cap } ) satisfy many identities. Several of these identities or "laws" have well established names.
Notation Throughout this article, capital letters (such as A , B , C , L , M , R , S , {\displaystyle A,B,C,L,M,R,S,} and X {\displaystyle X} ) will denote sets. On the left hand side of an identity,
L {\displaystyle L} will be the L {\displaystyle L} eft most set,
M {\displaystyle M} will be the M {\displaystyle M} iddle set, and
R {\displaystyle R} will be the R {\displaystyle R} ight most set. This is to facilitate applying identities to expressions that are complicated or use the same symbols as the identity. For example, the identity
( L ∖ M ) ∖ R = ( L ∖ R ) ∖ ( M ∖ R ) {\displaystyle (L\,\setminus \,M)\,\setminus \,R~=~(L\,\setminus \,R)\,\setminus \,(M\,\setminus \,R)}
may be read as:
( Left set ∖ Middle set ) ∖ Right set = ( Left set ∖ Right set ) ∖ ( Middle set ∖ Right set ) . {\displaystyle ({\text{Left set}}\,\setminus \,{\text{Middle set}})\,\setminus \,{\text{Right set}}~=~({\text{Left set}}\,\setminus \,{\text{Right set}})\,\setminus \,({\text{Middle set}}\,\setminus \,{\text{Right set}}).}
Elementary set operations For sets L {\displaystyle L} and R , {\displaystyle R,} define:
L ∪ R = def { x : x ∈ L or x ∈ R } L ∩ R = def { x : x ∈ L and x ∈ R } L ∖ R = def { x : x ∈ L and x ∉ R } {\displaystyle {\begin{alignedat}{4}L\cup R&&~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{~x~:~x\in L\;&&{\text{ or }}\;\,&&\;x\in R~\}\\L\cap R&&~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{~x~:~x\in L\;&&{\text{ and }}&&\;x\in R~\}\\L\setminus R&&~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{~x~:~x\in L\;&&{\text{ and }}&&\;x\notin R~\}\\\end{alignedat}}}
and
L △ R = def { x : x belongs to exactly one of L and R } {\displaystyle L\triangle R~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{~x~:~x{\text{ belongs to exactly one of }}L{\text{ and }}R~\}}
where the symmetric difference L △ R {\displaystyle L\triangle R} is sometimes denoted by L ⊖ R {\displaystyle L\ominus R} and equals:
L △ R = ( L ∖ R ) ∪ ( R ∖ L ) = ( L ∪ R ) ∖ ( L ∩ R ) . {\displaystyle {\begin{alignedat}{4}L\;\triangle \;R~&=~(L~\setminus ~&&R)~\cup ~&&(R~\setminus ~&&L)\\~&=~(L~\cup ~&&R)~\setminus ~&&(L~\cap ~&&R).\end{alignedat}}}
One set L {\displaystyle L} is said to intersect another set R {\displaystyle R} if L ∩ R ≠ ∅ . {\displaystyle L\cap R\neq \varnothing .} Sets that do not intersect are said to be disjoint. The power set of X {\displaystyle X} is the set of all subsets of X {\displaystyle X} and will be denoted by
P ( X ) = def { L : L ⊆ X } . {\displaystyle {\mathcal {P}}(X)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{~L~:~L\subseteq X~\}.}
Universe set and complement notation The notation
L ∁ = def X ∖ L . {\displaystyle L^{\complement }~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~X\setminus L.}
may be used if L {\displaystyle L} is a subset of some set X {\displaystyle X} that is understood (say from context, or because it is clearly stated what the superset X {\displaystyle X} is). It is emphasized that the definition of L ∁ {\displaystyle L^{\complement }} depends on context. For instance, had L {\displaystyle L} been declared as a subset of Y , {\displaystyle Y,} with the sets Y {\displaystyle Y} and X {\displaystyle X} not necessarily related to each other in any way, then L ∁ {\displaystyle L^{\complement }} would likely mean Y ∖ L {\displaystyle Y\setminus L} instead of X ∖ L . {\displaystyle X\setminus L.}
If it is needed then unless indicated otherwise, it should be assumed that X {\displaystyle X} denotes the universe set, which means that all sets that are used in the formula are subsets of X . {\displaystyle X.} In particular, the complement of a set L {\displaystyle L} will be denoted by L ∁ {\displaystyle L^{\complement }} where unless indicated otherwise, it should be assumed that L ∁ {\displaystyle L^{\complement }} denotes the complement of L {\displaystyle L} in (the universe) X . {\displaystyle X.}
One subset involved Assume L ⊆ X . {\displaystyle L\subseteq X.}
Identity: Definition: e {\displaystyle e} is called a left identity element of a binary operator ∗ {\displaystyle \,\ast \,} if e ∗ R = R {\displaystyle e\,\ast \,R=R} for all R {\displaystyle R} and it is called a right identity element of ∗ {\displaystyle \,\ast \,} if L ∗ e = L {\displaystyle L\,\ast \,e=L} for all L . {\displaystyle L.} A left identity element that is also a right identity element if called an identity element. The empty set ∅ {\displaystyle \varnothing } is an identity element of binary union ∪ {\displaystyle \cup } and symmetric difference △ , {\displaystyle \triangle ,} and it is also a right identity element of set subtraction ∖ : {\displaystyle \,\setminus :}
L ∩ X = L = X ∩ L where L ⊆ X L ∪ ∅ = L = ∅ ∪ L L △ ∅ = L = ∅ △ L L ∖ ∅ = L {\displaystyle {\begin{alignedat}{10}L\cap X&\;=\;&&L&\;=\;&X\cap L~~~~{\text{ where }}L\subseteq X\\[1.4ex]L\cup \varnothing &\;=\;&&L&\;=\;&\varnothing \cup L\\[1.4ex]L\,\triangle \varnothing &\;=\;&&L&\;=\;&\varnothing \,\triangle L\\[1.4ex]L\setminus \varnothing &\;=\;&&L\\[1.4ex]\end{alignedat}}}
but ∅ {\displaystyle \varnothing } is not a left identity element of ∖ {\displaystyle \,\setminus \,} since
∅ ∖ L = ∅ {\displaystyle \varnothing \setminus L=\varnothing } so ∅ ∖ L = L {\textstyle \varnothing \setminus L=L} if and only if L = ∅ . {\displaystyle L=\varnothing .}
Idempotence L ∗ L = L {\displaystyle L\ast L=L} and Nilpotence L ∗ L = ∅ {\displaystyle L\ast L=\varnothing } :
L ∪ L = L (Idempotence) L ∩ L = L (Idempotence) L △ L = ∅ (Nilpotence of index 2) L ∖ L = ∅ (Nilpotence of index 2) {\displaystyle {\begin{alignedat}{10}L\cup L&\;=\;&&L&&\quad {\text{ (Idempotence)}}\\[1.4ex]L\cap L&\;=\;&&L&&\quad {\text{ (Idempotence)}}\\[1.4ex]L\,\triangle \,L&\;=\;&&\varnothing &&\quad {\text{ (Nilpotence of index 2)}}\\[1.4ex]L\setminus L&\;=\;&&\varnothing &&\quad {\text{ (Nilpotence of index 2)}}\\[1.4ex]\end{alignedat}}}
Domination/Absorbing element: Definition: z {\displaystyle z} is called a left absorbing element of a binary operator ∗ {\displaystyle \,\ast \,} if z ∗ R = z {\displaystyle z\,\ast \,R=z} for all R {\displaystyle R} and it is called a right absorbing element of ∗ {\displaystyle \,\ast \,} if L ∗ z = z {\displaystyle L\,\ast \,z=z} for all L . {\displaystyle L.} A left absorbing element that is also a right absorbing element is 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 ∪ . {\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 :}
X ∪ L = X = L ∪ X where L ⊆ X ∅ ∩ L = ∅ = L ∩ ∅ ∅ × L = ∅ = L × ∅ ∅ ∖ L = ∅ {\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
L ∖ ∅ = L {\displaystyle L\setminus \varnothing =L} where L ∖ ∅ = ∅ {\textstyle L\setminus \varnothing =\varnothing } if and only if L = ∅ . {\textstyle L=\varnothing .}
Double complement or involution law:
X ∖ ( X ∖ L ) = L Also written ( L ∁ ) ∁ = L where L ⊆ X (Double complement/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}}}
L ∖ ∅ = L {\displaystyle L\setminus \varnothing =L}
∅ = L ∖ L = ∅ ∖ L = L ∖ X where L ⊆ X {\displaystyle {\begin{alignedat}{4}\varnothing &=L&&\setminus L\\&=\varnothing &&\setminus L\\&=L&&\setminus X~~~~{\text{ where }}L\subseteq X\\\end{alignedat}}}
L ∁ = X ∖ L (definition of notation) {\displaystyle L^{\complement }=X\setminus L\quad {\text{ (definition of notation)}}}
L ∪ ( X ∖ L ) = X Also written L ∪ L ∁ = X where L ⊆ X L △ ( X ∖ L ) = X Also written L △ L ∁ = X where L ⊆ X L ∩ ( X ∖ L ) = ∅ Also written L ∩ L ∁ = ∅ {\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}}}
X ∖ ∅ = X Also written ∅ ∁ = X (Complement laws for the empty set)) X ∖ X = ∅ Also written X ∁ = ∅ (Complement laws for the universe set) {\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}}}
Two sets involved In the left hand sides of the following identities, L {\displaystyle L} is the L eft most set and R {\displaystyle R} is the R ight most set. Assume both L and R {\displaystyle L{\text{ and }}R} are subsets of some universe set X . {\displaystyle X.}
Formulas for binary set operations ⋂, ⋃, \, and ∆ In the left hand sides of the following identities, L is the L eft most set and R is the R ight most set. Whenever necessary, both L and R should be assumed to be subsets of some universe set X, so that L ∁ := X ∖ L and R ∁ := X ∖ R . {\displaystyle L^{\complement }:=X\setminus L{\text{ and }}R^{\complement }:=X\setminus R.}
L ∩ R = L ∖ ( L ∖ R ) = R ∖ ( R ∖ L ) = L ∖ ( L △ R ) = L △ ( L ∖ 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}}}
L ∪ R = ( L △ R ) ∪ L = ( L △ R ) △ ( L ∩ R ) = ( R ∖ L ) ∪ L (union is disjoint) {\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}}}
L △ R = R △ L = ( L ∪ R ) ∖ ( L ∩ R ) = ( L ∖ R ) ∪ ( R ∖ L ) (union is disjoint)