HOME

TheInfoList



OR:

This article lists
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
properties and laws of sets, involving the set-theoretic operations of
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...
,
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
, and complementation and the relations of set
equality Equality may refer to: Society * Political equality, in which all members of a society are of equal standing ** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elite ...
and set
inclusion Inclusion or Include may refer to: Sociology * Social inclusion, aims to create an environment that supports equal opportunity for individuals and groups that form a society. ** Inclusion (disability rights), promotion of people with disabiliti ...
. It also provides systematic procedures for evaluating expressions, and performing calculations, involving these operations and relations. The
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...
s of set union (\cup) and intersection (\cap) satisfy many identities. Several of these identities or "laws" have well established names.


Notation

Throughout this article, capital letters such as A, B, C, L, M, R, S, and X will denote sets and \wp(X) will denote the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of X. If it is needed then unless indicated otherwise, it should be assumed that X denotes the universe set, which means that all sets that are used in the formula are subsets of X. In particular, the complement of a set L will be denoted by L^C where unless indicated otherwise, it should be assumed that L^C denotes the complement of L in (the universe) X. Typically, the set L will denote the eft most set, M the iddle set, and R the ight most set. For sets L and R, define: \begin L \cup R &&~:=~ \ \\ L \cap R &&~:=~ \ \\ L \setminus R &&~:=~ \ \\ \end and L \triangle R ~:=~ \ where the L \triangle R is sometimes denoted by L \ominus R and equals: \begin L \;\triangle\; R ~&=~ (L ~\setminus~ &&R) ~\cup~ &&(R ~\setminus~ &&L) \\ ~&=~ (L ~\cup~ &&R) ~\setminus~ &&(L ~\cap~ &&R). \end If L is a set that is understood (say from context, or because it is clearly stated) to be a subset of some other set X then the complement of a set L may be denoted by: L^ ~:=~ X \setminus L. The definition of L^ = X \setminus L may depend on context. For instance, had L been declared as a subset of Y, with the sets Y and X not necessarily related to each other in any way, then L^ would likely mean Y \setminus L instead of X \setminus L.


Finitely many sets


One subset involved

Assume L \subseteq X.
Identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), ...
: Definition: e is called a left identity element of a
binary operator In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary ope ...
\,\ast\, if e \,\ast\, R = R for all R and it is called a right identity element of \,\ast\, if L \,\ast\, e = L for all L. A left identity element that is also a right identity element if called an
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
. \begin L \cap X &\;=\;&& L &\;=\;& X \cap L ~~~~\text L \subseteq X \\ .4exL \cup \varnothing &\;=\;&& L &\;=\;& \varnothing \cup L \\ .4exL \,\triangle \varnothing &\;=\;&& L &\;=\;& \varnothing \,\triangle L \\ .4exL \setminus \varnothing &\;=\;&& L \\ .4ex\end but \varnothing \setminus L = \varnothing so \varnothing \setminus L = L \text L = \varnothing.
Idempotence Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
L \ast L = L and Nilpotence L \ast L = \varnothing: \begin L \cup L &\;=\;&& L && \quad \text \\ .4exL \cap L &\;=\;&& L && \quad \text \\ .4exL \,\triangle\, L &\;=\;&& \varnothing && \quad \text \\ .4exL \setminus L &\;=\;&& \varnothing && \quad \text \\ .4ex\end Domination/
Zero element In mathematics, a zero element is one of several generalizations of the number zero to other algebraic structures. These alternate meanings may or may not reduce to the same thing, depending on the context. Additive identities An additive identi ...
: \begin X \cup L &\;=\;&& X &\;=\;& L \cup X ~~~~\text L \subseteq X \\ .4ex\varnothing \cap L &\;=\;&& \varnothing &\;=\;& L \cap \varnothing \\ .4ex\varnothing \times L &\;=\;&& \varnothing &\;=\;& L \times \varnothing \\ .4ex\varnothing \setminus L &\;=\;&& \varnothing &\;\;& \\ .4ex\end but L \setminus \varnothing = L so L \setminus \varnothing = \varnothing \text L = \varnothing. Double complement or
involution Involution may refer to: * Involute, a construction in the differential geometry of curves * '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
law: \begin X \setminus (X \setminus L) &= L &&\qquad\text\quad &&\left(L^C\right)^C = L &&\quad&&\text L \subseteq X \quad \text \\ .4ex\end L \setminus \varnothing = L \begin \varnothing &= L &&\setminus L \\ &= \varnothing &&\setminus L \\ &= L &&\setminus X ~~~~\text L \subseteq X \\ \end L^C = X \setminus L \quad \text \begin L \,\cup (X \setminus L) &= X &&\qquad\text\quad &&L \cup L^C = X &&\quad&&\text L \subseteq X \\ .4ex L \,\triangle (X \setminus L) &= X &&\qquad\text\quad &&L \,\triangle L^C = X &&\quad&&\text L \subseteq X \\ .4ex L \,\cap (X \setminus L) &= \varnothing &&\qquad\text\quad &&L \cap L^C = \varnothing &&\quad&& \\ .4ex\end \begin X \setminus \varnothing &= X &&\qquad\text\quad &&\varnothing^C = X &&\quad&&\text \\ .4ex X \setminus X &= \varnothing &&\qquad\text\quad &&X^C = \varnothing &&\quad&&\text \\ .4ex\end


Two sets involved

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


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

In the left hand sides of the following identities, L is the eft most set and R is the ight most set. Whenever necessary, both L \text R should be assumed to be subsets of some universe set X, so that L^C := X \setminus L \text R^C := X \setminus R. \begin L \cap R &= L &&\,\,\setminus\, &&(L &&\,\,\setminus &&R) \\ &= R &&\,\,\setminus\, &&(R &&\,\,\setminus &&L) \\ &= L &&\,\,\setminus\, &&(L &&\,\triangle\, &&R) \\ &= L &&\,\triangle\, &&(L &&\,\,\setminus &&R) \\ \end \begin L \cup R &= (&&L \,\triangle\, R) &&\,\,\cup && &&L && && \\ &= (&&L \,\triangle\, R) &&\,\triangle\, &&(&&L &&\cap\, &&R) \\ &= (&&R \,\setminus\, L) &&\,\,\cup && &&L && && ~~~~~\text \\ \end \begin L \,\triangle\, R &= &&R \,\triangle\, L && && && && \\ &= (&&L \,\cup\, R) &&\,\setminus\, &&(&&L \,\,\cap\, R) && \\ &= (&&L \,\setminus\, R) &&\cup\, &&(&&R \,\,\setminus\, L) && ~~~~~\text \\ &= (&&L \,\triangle\, M) &&\,\triangle\, &&(&&M \,\triangle\, R) && ~~~~~\text M \text \\ &= (&&L^C) &&\,\triangle\, &&(&&R^C) && \\ \end \begin L \setminus R &= &&L &&\,\,\setminus &&(L &&\,\,\cap &&R) \\ &= &&L &&\,\,\cap &&(L &&\,\triangle\, &&R) \\ &= &&L &&\,\triangle\, &&(L &&\,\,\cap &&R) \\ &= &&R &&\,\triangle\, &&(L &&\,\,\cup &&R) \\ \end


De Morgan's laws

De Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...
state that for L, R \subseteq X: \begin X \setminus (L \cap R) &= (X \setminus L) \cup (X \setminus R) &&\qquad\text\quad &&(L \cap R)^C = L^C \cup R^C &&\quad&&\text \\ .4ex X \setminus (L \cup R) &= (X \setminus L) \cap (X \setminus R) &&\qquad\text\quad &&(L \cup R)^C = L^C \cap R^C &&\quad&&\text \\ .4ex\end


Commutativity

Unions, intersection, and symmetric difference are
commutative operation In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
s: \begin L \cup R &\;=\;&& R \cup L && \quad \text \\ .4exL \cap R &\;=\;&& R \cap L && \quad \text \\ .4exL \,\triangle R &\;=\;&& R \,\triangle L && \quad \text \\ .4ex\end Set subtraction is not commutative. However, the commutativity of set subtraction can be characterized: from (L \,\setminus\, R) \cap (R \,\setminus\, L) = \varnothing it follows that: L \,\setminus\, R = R \,\setminus\, L \quad \text \quad L = R. Said differently, if distinct symbols always represented distinct sets, then the true formulas of the form \,\cdot\, \,\setminus\, \,\cdot\, = \,\cdot\, \,\setminus\, \,\cdot\, that could be written would be those involving a single symbol; that is, those of the form: S \,\setminus\, S = S \,\setminus\, S. But such formulas are necessarily true for binary operation \,\ast\, (because x \,\ast\, x = x \,\ast\, x must hold by definition of
equality Equality may refer to: Society * Political equality, in which all members of a society are of equal standing ** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elite ...
), 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 In abstract algebra, alternativity is a property of a binary operation. A magma ''G'' is said to be if (xx)y = x(xy) for all x, y \in G and if y(xx) = (yx)x for all x, y \in G. A magma that is both left and right alternative is said to be () ...
nor
right alternative In abstract algebra, alternativity is a property of a binary operation. A magma ''G'' is said to be if (xx)y = x(xy) for all x, y \in G and if y(xx) = (yx)x for all x, y \in G. A magma that is both left and right alternative is said to be () ...
; instead, (L \setminus L) \setminus R = L \setminus (L \setminus R) if and only if L \cap R = \varnothing if and only if (R \setminus L) \setminus L = R \setminus (L \setminus L). Set subtraction is
quasi-commutative In mathematics, the quasi-commutative property is an extension or generalization of the general commutative property. This property is used in specific applications with various definitions. Applied to matrices Two matrices p and q are said to ha ...
and satisfies the
Jordan identity In abstract algebra, a Jordan algebra is a nonassociative algebra over a field whose multiplication satisfies the following axioms: # xy = yx (commutative law) # (xy)(xx) = x(y(xx)) (). The product of two elements ''x'' and ''y'' in a Jordan al ...
.


Other identities involving two sets

Absorption law In algebra, the absorption law or absorption identity is an identity linking a pair of binary operations. Two binary operations, ¤ and ⁂, are said to be connected by the absorption law if: :''a'' ¤ (''a'' ⁂ ''b'') = ''a'' ⁂ (''a'' ¤ ''b ...
s: \begin L \cup (L \cap R) &\;=\;&& L && \quad \text \\ .4exL \cap (L \cup R) &\;=\;&& L && \quad \text \\ .4ex\end Other properties \begin L \setminus R &= L \cap (X \setminus R) &&\qquad\text\quad &&L \setminus R = L \cap R^C &&\quad&&\text L, R \subseteq X \\ .4ex X \setminus (L \setminus R) &= (X \setminus L) \cup R &&\qquad\text\quad &&(L \setminus R)^C = L^C \cup R &&\quad&&\text R \subseteq X \\ .4ex L \setminus R &= (X \setminus R) \setminus (X \setminus L) &&\qquad\text\quad &&L \setminus R = R^C \setminus L^C &&\quad&&\text L, R \subseteq X \\ .4ex\end Intervals: (a, b) \cap (c, d) = (\max\, \min\)
empty Empty may refer to: ‍ Music Albums * ''Empty'' (God Lives Underwater album) or the title song, 1995 * ''Empty'' (Nils Frahm album), 2020 * ''Empty'' (Tait album) or the title song, 2001 Songs * "Empty" (The Click Five song), 2007 * ...
if the sentence \forall x (x \not\in L) is true, where the notation x \not\in L is shorthand for \lnot (x \in L). If L is any set then the following are equivalent:
  1. L is not empty, meaning that the sentence \lnot [\forall x (x \not\in L)] is true (literally, the logical negation of "L is empty" holds true).
  2. (In classical mathematics) L is Inhabited set, inhabited, meaning: \exists x (x \in L) * In
    constructive mathematics In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove th ...
    , "not empty" and "inhabited" are not equivalent: every inhabited set is not empty but the converse is not always guaranteed; that is, in constructive mathematics, a set L that is not empty (where by definition, "L is empty" means that the statement \forall x (x \not\in L) is true) might not have an
    inhabitant Domicile is relevant to an individual's "personal law," which includes the law that governs a person's status and their property. It is independent of a person's nationality. Although a domicile may change from time to time, a person has only one ...
    (which is an x such that x \in L).
  3. L \not\subseteq R for some set R
If L is any set then the following are equivalent:
  1. L is empty (L = \varnothing), meaning: \forall x (x \not\in L)
  2. L \cup R \subseteq R for every set R
  3. L \subseteq R for every set R
  4. L \subseteq R \setminus L for some/every set R
  5. \varnothing / L = L
Given any x, x \not\in L \setminus R \quad \text\quad x \in L \cap R \; \text \; x \not\in L. Moreover, (L \setminus R) \cap R = \varnothing \qquad \text.


Meets, Joins, and lattice properties

Inclusion is a
partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
: Explicitly, this means that
inclusion Inclusion or Include may refer to: Sociology * Social inclusion, aims to create an environment that supports equal opportunity for individuals and groups that form a society. ** Inclusion (disability rights), promotion of people with disabiliti ...
\,\subseteq,\, which is a
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...
, has the following three properties: The following proposition says that for any set S, the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of S, ordered by inclusion, is a
bounded lattice A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper boun ...
, and hence together with the distributive and complement laws above, show that it is a
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
. Existence of a
least element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
and a
greatest element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
: \varnothing \subseteq L \subseteq X
Joins Join may refer to: * Join (law), to include additional counts or additional defendants on an indictment *In mathematics: ** Join (mathematics), a least upper bound of sets orders in lattice theory ** Join (topology), an operation combining two topo ...
/supremums exist: L \subseteq L \cup R The union L \cup R is the join/supremum of L and R with respect to \,\subseteq\, because:
  1. L \subseteq L \cup R and R \subseteq L \cup R, and
  2. if Z is a set such that L \subseteq Z and R \subseteq Z then L \cup R \subseteq Z.
The intersection L \cap R is the join/supremum of L and R with respect to \,\supseteq.\, Meets/infimums exist: L \cap R \subseteq L The intersection L \cap R is the meet/infimum of L and R with respect to \,\subseteq\, because:
  1. if L \cap R \subseteq L and L \cap R \subseteq R, and
  2. if Z is a set such that Z \subseteq L and Z \subseteq R then Z \subseteq L \cap R.
The union L \cup R is the meet/infimum of L and R with respect to \,\supseteq.\, Other inclusion properties: L \setminus R \subseteq L (L \setminus R) \cap L = L \setminus R


Three sets involved

In the left hand sides of the following identities, L is the eft most set, M is the iddle set, and R is the ight most set. Precedence rules There is no universal agreement on the
order of precedence An order of precedence is a sequential hierarchy of nominal importance and can be applied to individuals, groups, or organizations. Most often it is used in the context of people by many organizations and governments, for very formal and state o ...
of the basic set operators. Nevertheless, many authors use
precedence rule In mathematics and computer programming, the order of operations (or operator precedence) is a collection of rules that reflect conventions about which procedures to perform first in order to evaluate a given mathematical expression. For exampl ...
s for set operators, although these rules vary with the author. One common convention is to associate intersection L \cap R = \ with logical conjunction (and) L \land R and associate union L \cup R = \ with logical disjunction (or) L \lor R, and then transfer the precedence of these logical operators (where \,\land\, has precedence over \,\lor\,) to these set operators, thereby giving \,\cap\, precedence over \,\cup.\, So for example, L \cup M \cap R would mean L \cup (M \cap R) since it would be associated with the logical statement L \lor M \land R ~=~ L \lor (M \land R) and similarly, L \cup M \cap R \cup Z would mean L \cup (M \cap R) \cup Z since it would be associated with L \lor M \land R \lor Z ~=~ L \lor (M \land R) \lor Z. Sometimes, set complement (subtraction) \,\setminus\, is also associated with logical complement (not) \,\lnot,\, in which case it will have the highest precedence. More specifically, L \setminus R = \ is rewritten L \land \lnot R so that for example, L \cup M \setminus R would mean L \cup (M \setminus R) since it would be rewritten as the logical statement L \lor M \land \lnot R which is equal to L \lor (M \land \lnot R). For another example, because L \land \lnot M \land R means L \land (\lnot M) \land R, which is equal to both (L \land (\lnot M)) \land R and L \land ((\lnot M) \land R) ~=~ L \land (R \land (\lnot M)) (where (\lnot M) \land R was rewritten as R \land (\lnot M)), the formula L \setminus M \cap R would refer to the set (L \setminus M) \cap R = L \cap (R \setminus M); moreover, since L \land (\lnot M) \land R = (L \land R) \land \lnot M, this set is also equal to (L \cap R) \setminus M (other set identities can similarly be deduced from
propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
identities in this way). However, because set subtraction is not associative (L \setminus M) \setminus R \neq L \setminus (M \setminus R), a formula such as L \setminus M \setminus R would be ambiguous; for this reason, among others, set subtraction is often not assigned any precedence at all.
Symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...
L \triangle R = \ is sometimes associated with exclusive or (xor) L \oplus R (also sometimes denoted by \,\veebar), in which case if the order of precedence from highest to lowest is \,\lnot, \,\oplus, \,\land, \,\lor\, then the order of precedence (from highest to lowest) for the set operators would be \,\setminus,\, \triangle,\, \cap,\, \cup. There is no universal agreement on the precedence of exclusive disjunction \,\oplus\, with respect to the other logical connectives, which is why symmetric difference \,\triangle\, is not often assigned a precedence.


Associativity

Definition: A
binary operator In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary ope ...
\,\ast\, is called
associative In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
if (L \,\ast\, M) \,\ast\, R = L \,\ast\, (M \,\ast\, R) always holds. The following set operators are associative: \begin (L \cup M) \cup R &\;=\;\;&& L \cup (M \cup R) \\ .4ex(L \cap M) \cap R &\;=\;\;&& L \cap (M \cap R) \\ .4ex(L \,\triangle M) \,\triangle R &\;=\;\;&& L \,\triangle (M \,\triangle R) \\ .4ex\end For set subtraction, instead of associativity, only the following is always guaranteed: (L \,\setminus\, M) \,\setminus\, R \;~~~~\; L \,\setminus\, (M \,\setminus\, R) where equality holds if and only if L \cap R = \varnothing (this condition does not depend on M). Thus \; (L \setminus M) \setminus R = L \setminus (M \setminus R) \; if and only if \; (R \setminus M) \setminus L = R \setminus (M \setminus L), \; where the only difference between the left and right hand side set equalities is that the locations of L \text R have been swapped.


Distributivity

Definition: If \ast \text \bullet are
binary operator In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary ope ...
s then if L \,\ast\, (M \,\bullet\, R) ~=~ (L \,\ast\, M) \,\bullet\, (L \,\ast\,R) \qquad\qquad \text L, M, R while if (L \,\bullet\, M) \,\ast\, R ~=~ (L \,\ast\, R) \,\bullet\, (M \,\ast\,R) \qquad\qquad \text L, M, R. The operator if it both left distributes and right distributes over \,\bullet\,.\, In the definitions above, to transform one side to the other, the innermost operator (the operator inside the parentheses) becomes the outermost operator and the outermost operator becomes the innermost operator.
Right distributivity In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic, ...
: \begin (L \,\cap\, M) \,\cup\, R ~&~~=~~&& (L \,\cup\, R) \,&&\cap\, &&(M \,\cup\, R) \qquad &&\text \,\cup\, \text \,\cap\, \text \\ .4ex(L \,\cup\, M) \,\cup\, R ~&~~=~~&& (L \,\cup\, R) \,&&\cup\, &&(M \,\cup\, R) \qquad &&\text \,\cup\, \text \,\cup\, \text \\ .4ex(L \,\cup\, M) \,\cap\, R ~&~~=~~&& (L \,\cap\, R) \,&&\cup\, &&(M \,\cap\, R) \qquad &&\text \,\cap\, \text \,\cup\, \text \\ .4ex(L \,\cap\, M) \,\cap\, R ~&~~=~~&& (L \,\cap\, R) \,&&\cap\, &&(M \,\cap\, R) \qquad &&\text \,\cap\, \text \,\cap\, \text \\ .4ex(L \,\triangle\, M) \,\cap\, R ~&~~=~~&& (L \,\cap\, R) \,&&\triangle\, &&(M \,\cap\, R) \qquad &&\text \,\cap\, \text \,\triangle\, \text \\ .4ex(L \,\cap\, M) \,\times\, R ~&~~=~~&& (L \,\times\, R) \,&&\cap\, &&(M \,\times\, R) \qquad &&\text \,\times\, \text \,\cap\, \text \\ .4ex(L \,\cup\, M) \,\times\, R ~&~~=~~&& (L \,\times\, R) \,&&\cup\, &&(M \,\times\, R) \qquad &&\text \,\times\, \text \,\cup\, \text \\ .4ex(L \,\setminus\, M) \,\times\, R ~&~~=~~&& (L \,\times\, R) \,&&\setminus\, &&(M \,\times\, R) \qquad &&\text \,\times\, \text \,\setminus\, \text \\ .4ex(L \,\cup\, M) \,\setminus\, R ~&~~=~~&& (L \,\setminus\, R) \,&&\cup\, &&(M \,\setminus\, R) \qquad &&\text \,\setminus\, \text \,\cup\, \text \\ .4ex(L \,\cap\, M) \,\setminus\, R ~&~~=~~&& (L \,\setminus\, R) \,&&\cap\, &&(M \,\setminus\, R) \qquad &&\text \,\setminus\, \text \,\cap\, \text \\ .4ex(L \,\triangle\, M) \,\setminus\, R ~&~~=~~&& (L \,\setminus\, R) &&\,\triangle\, &&(M \,\setminus\, R) \qquad &&\text \,\setminus\, \text \,\triangle\, \text \\ .4ex(L \,\setminus\, M) \,\setminus\, R ~&~~=~~&& (L \,\setminus\, R) &&\,\setminus\, &&(M \,\setminus\, R) \qquad &&\text \,\setminus\, \text \,\setminus\, \text \\ .4ex~&~~=~~&&~~\;~~\;~~\;~ L &&\,\setminus\, &&(M \cup R) \\ .4ex\end
Left distributivity In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmeti ...
: \begin L \cup (M \cap R) &\;=\;\;&& (L \cup M) \cap (L \cup R) \qquad &&\text \,\cup\, \text \,\cap\, \text \\ .4exL \cup (M \cup R) &\;=\;\;&& (L \cup M) \cup (L \cup R) &&\text \,\cup\, \text \,\cup\, \text \\ .4exL \cap (M \cup R) &\;=\;\;&& (L \cap M) \cup (L \cap R) &&\text \,\cap\, \text \,\cup\, \text \\ .4exL \cap (M \cap R) &\;=\;\;&& (L \cap M) \cap (L \cap R) &&\text \,\cap\, \text \,\cap\, \text \\ .4exL \cap (M \,\triangle\, R) &\;=\;\;&& (L \cap M) \,\triangle\, (L \cap R) &&\text \,\cap\, \text \,\triangle\, \text \\ .4exL \times (M \cap R) &\;=\;\;&& (L \times M) \cap (L \times R) &&\text \,\times\, \text \,\cap\, \text \\ .4exL \times (M \cup R) &\;=\;\;&& (L \times M) \cup (L \times R) &&\text \,\times\, \text \,\cup\, \text \\ .4exL \times (M \,\setminus R) &\;=\;\;&& (L \times M) \,\setminus (L \times R) &&\text \,\times\, \text \,\setminus\, \text \\ .4ex\end


=Distributivity and symmetric difference ∆

= Intersection distributes over symmetric difference: \begin L \,\cap\, (M \,\triangle\, R) ~&~~=~~&& (L \,\cap\, M) \,\triangle\, (L \,\cap\, R) ~&&~ \\ .4ex\end \begin (L \,\triangle\, M) \,\cap\, R~&~~=~~&& (L \,\cap\, R) \,\triangle\, (M \,\cap\, R) ~&&~ \\ .4ex\end Union does not distribute over symmetric difference because only the following is guaranteed in general: \begin L \cup (M \,\triangle\, R) ~~~~ \color (L \cup M) \,\triangle\, (L \cup R) ~ &~=~&& (M \,\triangle\, R) \,\setminus\, L &~=~&& (M \,\setminus\, L) \,\triangle\, (R \,\setminus\, L) \\ .4ex\end Symmetric difference does not distribute over itself: L \,\triangle\, (M \,\triangle\, R) ~~~~ \color (L \,\triangle\, M) \,\triangle\, (L \,\triangle\, R) ~=~ M \,\triangle\, R and in general, for any sets L \text A (where A represents M \,\triangle\, R), L \,\triangle\, A might not be a subset, nor a superset, of L (and the same is true for A).


=Distributivity and set subtraction \

= Failure of set subtraction to left distribute: Set subtraction is distributive over itself. However, set subtraction is left distributive over itself because only the following is guaranteed in general: \begin L \,\setminus\, (M \,\setminus\, R) &~~~~&& \color (L \,\setminus\, M) \,\setminus\, (L \,\setminus\, R) ~~=~~ L \cap R \,\setminus\, M \\ .4ex\end where equality holds if and only if L \,\setminus\, M = L \,\cap\, R, which happens if and only if L \cap M \cap R = \varnothing \text L \setminus M \subseteq R. For symmetric difference, the sets L \,\setminus\, (M \,\triangle\, R) and (L \,\setminus\, M) \,\triangle\, (L \,\setminus\, R) = L \,\cap\, (M \,\triangle\, R) are always disjoint. So these two sets are equal if and only if they are both equal to \varnothing. Moreover, L \,\setminus\, (M \,\triangle\, R) = \varnothing if and only if L \cap M \cap R = \varnothing \text L \subseteq M \cup R. To investigate the left distributivity of set subtraction over unions or intersections, consider how the sets involved in (both of) De Morgan's laws are all related: \begin (L \,\setminus\, M) \,\cap\, (L \,\setminus\, R) ~~=~~ L \,\setminus\, (M \,\cup\, R) ~&~~~~&& \color L \,\setminus\, (M \,\cap\, R) ~~=~~ (L \,\setminus\, M) \,\cup\, (L \,\setminus\, R) \\ .4ex\end always holds in general but equality is not guaranteed. Equality holds if and only if L \,\setminus\, (M \,\cap\, R) \;\subseteq\; L \,\setminus\, (M \,\cup\, R), which happens if and only if L \,\cap\, M = L \,\cap\, R. This observation about De Morgan's laws shows that \,\setminus\, is left distributive over \,\cup\, or \,\cap\, because only the following are guaranteed in general: \begin L \,\setminus\, (M \,\cup\, R) ~&~~~~&& \color (L \,\setminus\, M) \,\cup\, (L \,\setminus\, R) ~~=~~ L \,\setminus\, (M \,\cap\, R) \\ .4ex\end \begin L \,\setminus\, (M \,\cap\, R) ~&~~~~&& \color (L \,\setminus\, M) \,\cap\, (L \,\setminus\, R) ~~=~~ L \,\setminus\, (M \,\cup\, R) \\ .4ex\end where equality holds for one (or equivalently, for both) of the above two inclusion formulas if and only if L \,\cap\, M = L \,\cap\, R. The following statements are equivalent:
  1. L \cap M \,=\, L \cap R
  2. L \,\setminus\, M \,=\, L \,\setminus\, R
  3. L \,\setminus\, (M \,\cap\, R) = (L \,\setminus\, M) \,\cap\, (L \,\setminus\, R); that is, \,\setminus\, left distributes over \,\cap\, for these three particular sets
  4. L \,\setminus\, (M \,\cup\, R) = (L \,\setminus\, M) \,\cup\, (L \,\setminus\, R); that is, \,\setminus\, left distributes over \,\cup\, for these three particular sets
  5. L \,\setminus\, (M \,\cap\, R) \,=\, L \,\setminus\, (M \,\cup\, R)
  6. L \cap (M \cup R) \,=\, L \cap M \cap R
  7. L \cap (M \cup R) ~\subseteq~ M \cap R
  8. L \cap R ~\subseteq~ M \; and \; L \cap M ~\subseteq~ R
  9. L \setminus (M \setminus R) \,=\, L \setminus (R \setminus M)
  10. L \setminus (M \setminus R) \,=\, L \setminus (R \setminus M) \,=\, L
Quasi-commutativity: (L \setminus M) \setminus R ~=~ (L \setminus R) \setminus M \qquad \text always holds but in general, L \setminus (M \setminus R) ~~~~ L \setminus (R \setminus M). However, L \setminus (M \setminus R) ~\subseteq~ L \setminus (R \setminus M) if and only if L \cap R ~\subseteq~ M if and only if L \setminus (R \setminus M) ~=~ L. Set subtraction complexity: To manage the many identities involving set subtraction, this section is divided based on where the set subtraction operation and parentheses are located on the left hand side of the identity. The great variety and (relative) complexity of formulas involving set subtraction (compared to those without it) is in part due to the fact that unlike \,\cup, \,\cap, and \triangle,\, set subtraction is neither associative nor commutative and it also is not left distributive over \,\cup, \,\cap, \,\triangle, or even over itself.


Two set subtractions

Set subtraction is associative in general: (L \,\setminus\, M) \,\setminus\, R \;~~~~\; L \,\setminus\, (M \,\setminus\, R) since only the following is always guaranteed: (L \,\setminus\, M) \,\setminus\, R \;~~~~\; L \,\setminus\, (M \,\setminus\, R).


=(L\M)\R

= \begin (L \setminus M) \setminus R &= &&L \setminus (M \cup R) \\ .6ex&= (&&L \setminus R) \setminus M \\ .6ex&= (&&L \setminus M) \cap (L \setminus R) \\ .6ex&= (&&L \setminus R) \setminus M \\ .6ex&= (&&L \,\setminus\, R) \,\setminus\, (M \,\setminus\, R) \\ .4ex\end


=L\(M\R)

= \begin L \setminus (M \setminus R) &= (L \setminus M) \cup (L \cap R) \\ .4ex\end :* If L \subseteq M \text L \setminus (M \setminus R) = L \cap R :* L \setminus (M \setminus R) \subseteq (L \setminus M) \cup R with equality if and only if R \subseteq L.


One set subtraction


=(L\M) ⁎ R

= Set subtraction on the ''left'', and parentheses on the \begin \left(L \setminus M\right) \cup R &= (L \cup R) \setminus (M \setminus R) \\ &= (L \setminus (M \cup R)) \cup R ~~~~~ \text \\ \end :\begin (L \setminus M) \cap R &= (&&L \cap R) \setminus (M \cap R) ~~~\text \cap \text \setminus \text \\ &= (&&L \cap R) \setminus M \\ &= &&L \cap (R \setminus M) \\ \end \begin (L \,\setminus\, M) \,\cap\, (L \,\setminus\, R) ~~=~~ L \,\setminus\, (M \,\cup\, R) ~&~~~~&& \color L \,\setminus\, (M \,\cap\, R) ~~=~~ (L \,\setminus\, M) \,\cup\, (L \,\setminus\, R) \\ .4ex\end \begin (L \setminus M) ~\triangle~ R &= (L \setminus (M \cup R)) \cup (R \setminus L) \cup (L \cap M \cap R) ~~~\text \\ \end (L \,\setminus M) \times R = (L \times R) \,\setminus (M \times R) ~~~~~\text


=L\(M ⁎ R)

= Set subtraction on the ''left'', and parentheses on the \begin L \setminus (M \cup R) &= (L \setminus M) &&\,\cap\, (&&L \setminus R) ~~~~\text \\ &= (L \setminus M) &&\,\,\setminus &&R \\ &= (L \setminus R) &&\,\,\setminus &&M \\ \end \begin L \setminus (M \cap R) &= (L \setminus M) \cup (L \setminus R) ~~~~\text \\ \end where the above two sets that are the subjects of
De Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...
always satisfy L \,\setminus\, (M \,\cup\, R) ~~~~ \color L \,\setminus\, (M \,\cap\, R). \begin L \setminus (M ~\triangle~ R) &= (L \setminus (M \cup R)) \cup (L \cap M \cap R) ~~~\text \\ \end


=(L ⁎ M)\R

= Set subtraction on the ''right'', and parentheses on the \begin (L \cup M) \setminus R &= (L \setminus R) \cup (M \setminus R) \\ \end \begin (L \cap M) \setminus R &= (&&L \setminus R) &&\cap (M \setminus R) \\ &= &&L &&\cap (M \setminus R) \\ &= &&M &&\cap (L \setminus R) \\ \end \begin (L \,\triangle\, M) \setminus R &= (L \setminus R) ~&&\triangle~ (M \setminus R) \\ &= (L \cup R) ~&&\triangle~ (M \cup R) \\ \end


=L ⁎ (M\R)

= Set subtraction on the ''right'', and parentheses on the \begin L \cup (M \setminus R) &= && &&L &&\cup\; &&(M \setminus (R \cup L)) &&~~~\text \\ &= &(&&L \setminus M) &&\cup\; &&(R \cap L)\cup (M \setminus R) &&~~~\text \\ &= &&(&&L \setminus (M \cup R)) \;&&\;\cup &&(R \cap L)\,\, \cup (M \setminus R) &&~~~\text \\ \end :\begin L \cap (M \setminus R) &= (&&L \cap M) &&\setminus (L \cap R) ~~~\text \cap \text \setminus \text \\ &= (&&L \cap M) &&\setminus R \\ &= &&M &&\cap (L \setminus R) \\ &= (&&L \setminus R) &&\cap (M \setminus R) \\ \end L \times (M \,\setminus R) = (L \times M) \,\setminus (L \times R) ~~~~~\text


Three operations on three sets


=(L • M) ⁎ (M • R)

= Operations of the form (L \bullet M) \ast (M \bullet R): \begin (L \cup M) &\,\cup\,&& (&&M \cup R) && &&\;=\;\;&& L \cup M \cup R \\ .4ex(L \cup M) &\,\cap\,&& (&&M \cup R) && &&\;=\;\;&& M \cap (L \cup R) \\ .4ex(L \cup M) &\,\setminus\,&& (&&M \cup R) && &&\;=\;\;&& L \,\setminus\, (M \cup R) \\ .4ex(L \cup M) &\,\triangle\,&& (&&M \cup R) && &&\;=\;\;&& (L \,\setminus\, (M \cup R)) \,\cup\, (R \,\setminus\, (L \cup M)) \\ .4ex&\,&&\,&&\,&& &&\;=\;\;&& (L \,\triangle\, R) \,\setminus\, M \\ .4ex(L \cap M) &\,\cup\,&& (&&M \cap R) && &&\;=\;\;&& M \cup (L \cap R) \\ .4ex(L \cap M) &\,\cap\,&& (&&M \cap R) && &&\;=\;\;&& L \cap M \cap R \\ .4ex(L \cap M) &\,\setminus\,&& (&&M \cap R) && &&\;=\;\;&& (L \cap M) \,\setminus\, R \\ .4ex(L \cap M) &\,\triangle\,&& (&&M \cap R) && &&\;=\;\;&& L \,\cap M) \cup (M \,\cap R)\,\setminus\, (L \,\cap M \,\cap R) \\ .4ex(L \,\setminus M) &\,\cup\,&& (&&M \,\setminus R) && &&\;=\;\;&& (L \,\cup M) \,\setminus (M \,\cap\, R) \\ .4ex(L \,\setminus M) &\,\cap\,&& (&&M \,\setminus R) && &&\;=\;\;&& \varnothing \\ .4ex(L \,\setminus M) &\,\setminus\,&& (&&M \,\setminus R) && &&\;=\;\;&& L \,\setminus M \\ .4ex(L \,\setminus M) &\,\triangle\,&& (&&M \,\setminus R) && &&\;=\;\;&& (L \,\setminus M) \cup (M \,\setminus R) \\ .4ex&\,&&\,&&\,&& &&\;=\;\;&& (L \,\cup M) \setminus (M \,\cap R) \\ .4ex(L \,\triangle\, M) &\,\cup\,&& (&&M \,\triangle\, R) && &&\;=\;\;&& (L \,\cup\, M \,\cup\, R) \,\setminus\, (L \,\cap\, M \,\cap\, R) \\ .4ex(L \,\triangle\, M) &\,\cap\,&& (&&M \,\triangle\, R) && &&\;=\;\;&& ((L \,\cap\, R) \,\setminus\, M) \,\cup\, (M \,\setminus\, (L \,\cup\, R)) \\ .4ex(L \,\triangle\, M) &\,\setminus\,&& (&&M \,\triangle\, R) && &&\;=\;\;&& (L \,\setminus\, (M \,\cup\, R)) \,\cup\, ((M \,\cap\, R) \,\setminus\, L) \\ .4ex(L \,\triangle\, M) &\,\triangle\,&& (&&M \,\triangle\, R) && &&\;=\;\;&& L \,\triangle\, R \\ .7ex\end


=(L • M) ⁎ (R\M)

= Operations of the form (L \bullet M) \ast (R \,\setminus\, M): \begin (L \cup M) &\,\cup\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& L \cup M \cup R \\ .4ex(L \cup M) &\,\cap\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& (L \cap R) \,\setminus\, M \\ .4ex(L \cup M) &\,\setminus\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& M \cup (L \,\setminus\, R) \\ .4ex(L \cup M) &\,\triangle\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& M \cup (L \,\triangle\, R) \\ .4ex(L \cap M) &\,\cup\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& \cap (M \cup R)\cup \,\setminus\, (L \cup M)\qquad \text \\ .4ex&\,&&\,&&\,&& &&\;=\;\;&& (L \cap M) \,\triangle\, (R \,\setminus\, M) \\ .4ex(L \cap M) &\,\cap\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& \varnothing \\ .4ex(L \cap M) &\,\setminus\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& L \cap M \\ .4ex(L \cap M) &\,\triangle\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& (L \cap M) \cup (R \,\setminus\, M) \qquad \text \\ .4ex(L \,\setminus\, M) &\,\cup\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& L \cup R \,\setminus\, M \\ .4ex(L \,\setminus\, M) &\,\cap\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& (L \cap R) \,\setminus\, M \\ .4ex(L \,\setminus\, M) &\,\setminus\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& L \,\setminus\, (M \cup R) \\ .4ex(L \,\setminus\, M) &\,\triangle\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& (L \,\triangle\, R) \,\setminus\, M \\ .4ex(L \,\triangle\, M) &\,\cup\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& (L \cup M \cup R) \,\setminus\, (L \cap M) \\ .4ex(L \,\triangle\, M) &\,\cap\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& (L \cap R) \,\setminus\, M \\ .4ex(L \,\triangle\, M) &\,\setminus\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& \,\setminus\, (M \cup R)\cup (M \,\setminus\, L) \qquad \text \\ .4ex&\,&&\,&&\,&& &&\;=\;\;&& (L \,\triangle\, M) \setminus (L \,\cap R) \\ .4ex(L \,\triangle\, M) &\,\triangle\,&& (&&R \,\setminus\, M) && &&\;=\;\;&& L \,\triangle\, (M \cup R) \\ .7ex\end


=(L\M) ⁎ (L\R)

= Operations of the form (L \,\setminus\, M) \ast (L \,\setminus\, R): \begin (L \,\setminus M) &\,\cup\,&& (&&L \,\setminus R) &&\;=\;&& L \,\setminus\, (M \,\cap\, R) \\ .4ex(L \,\setminus M) &\,\cap\,&& (&&L \,\setminus R) &&\;=\;&& L \,\setminus\, (M \,\cup\, R) \\ .4ex(L \,\setminus M) &\,\setminus\,&& (&&L \,\setminus R) &&\;=\;&& (L \,\cap\, R) \,\setminus\, M \\ .4ex(L \,\setminus M) &\,\triangle\,&& (&&L \,\setminus R) &&\;=\;&& L \,\cap\, (M \,\triangle\, R) \\ .4ex&\,&&\,&&\, &&\;=\;&& (L \cap M) \,\triangle\, (L \cap R) \\ .4ex\end


Other simplifications

Other properties: L \cap M = R \;\text\; L \cap R = M \qquad \text \qquad M = R \subseteq L.


Cartesian products ⨯ of finitely many sets


Binary ⋂ of finite ⨯

(L \times R) \cap \left(L_2 \times R_2\right) ~=~ \left(L \cap L_2\right) \times \left(R \cap R_2\right) (L \times M \times R) \cap \left(L_2 \times M_2 \times R_2\right) ~=~ \left(L \cap L_2\right) \times \left(M \cap M_2\right) \times \left(R \cap R_2\right)


Binary ⋃ of finite ⨯

\begin \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\\ .5ex~&=~ \left \times \left(R \setminus R_2\right)\right~\cup~ \left _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


Difference \ of finite ⨯

\begin \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 \times \left(R \,\setminus\, R_2\right)\right\\ \end and (L \times M \times R) ~\setminus~ \left(L_2 \times M_2 \times R_2\right) ~=~ \left left(L \,\setminus\, L_2\right) \times M \times R\right~\cup~ \left \times \left(M \,\setminus\, M_2\right) \times R\right~\cup~ \left \times M \times \left(R \,\setminus\, R_2\right)\right/math>


Finite ⨯ of differences \

\left(L \,\setminus\, L_2\right) \times \left(R \,\setminus\, R_2\right) ~=~ \left(L \times R\right) \,\setminus\, \left left(L_2 \times R\right) \cup \left(L \times R_2\right)\right/math> \left(L \,\setminus\, L_2\right) \times \left(M \,\setminus\, M_2\right) \times \left(R \,\setminus\, R_2\right) ~=~ \left(L \times M \times R\right) \,\setminus\, \left left(L_2 \times M \times R\right) \cup \left(L \times M_2 \times R\right) \cup \left(L \times M \times R_2\right)\right/math>


Symmetric difference ∆ and finite ⨯

L \times \left(R \,\triangle\, R_2\right) ~=~ \left \times \left(R \,\setminus\, R_2\right)\right\,\cup\, \left \times \left(R_2 \,\setminus\, R\right)\right/math> \left(L \,\triangle\, L_2\right) \times R ~=~ \left left(L \,\setminus\, L_2\right) \times R\right\,\cup\, \left left(L_2 \,\setminus\, L\right) \times R\right/math> \begin \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\\ .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 \begin \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 In general, \left(L \,\triangle\, L_2\right) \times \left(R \,\triangle\, R_2\right) need not be a subset nor a superset of \left(L \times R\right) \,\triangle\, \left(L_2 \times R_2\right). \begin \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\\ .7ex\end \begin \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\\ .7ex\end


Arbitrary families of sets

Let \left(L_i\right)_, \left(R_j\right)_, and \left(S_\right)_ be indexed
families of sets Family (from la, familia) is a group of people related either by consanguinity (by recognized birth) or affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its members and of society. Ideall ...
. Whenever the assumption is needed, then all indexing sets, such as I and J, are assumed to be non-empty.


Definitions

A or (more briefly) a refers to a set whose elements are sets. An is a function from some set, called its , into some family of sets. An indexed family of sets will be denoted by \left(L_i\right)_, where this notation assigns the symbol I for the indexing set and for every index i \in I, assigns the symbol L_i to the value of the function at i. The function itself may then be denoted by the symbol L_\bull, which is obtained from the notation \left(L_i\right)_ by replacing the index i with a bullet symbol \bullet\,; explicitly, L_\bull is the function: \begin L_\bull :\;&& I &&\;\to \;& \left\ \\ .3ex && i &&\;\mapsto\;& L_i \\ \end which may be summarized by writing L_\bull = \left(L_i\right)_. Any given indexed family of sets L_\bull = \left(L_i\right)_ (which is a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
) can be canonically associated with its image/range \operatorname L_\bull := \left\ (which is a family of sets). Conversely, any given family of sets \mathcal may be associated with the \mathcal-indexed family of sets (B)_, which is technically the
identity map Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unch ...
\mathcal \to \mathcal. However, this is a bijective correspondence because an indexed family of sets L_\bull = \left(L_i\right)_ is required to be injective (that is, there may exist distinct indices i \neq j such as L_i = L_j), which in particular means that it is possible for distinct indexed families of sets (which are functions) to be associated with the same family of sets (by having the same image/range). Arbitrary unions defined If I = \varnothing then \bigcup_ L_i = \ = \varnothing, which is somethings called the (despite being called a convention, this equality follows from the definition). If \mathcal is a family of sets then \bigcup \mathcal denotes the set: \bigcup \mathcal ~~\colon=~ \bigcup_ B ~~\colon=~ \. Arbitrary intersections defined If I \neq \varnothing then If \mathcal \neq \varnothing is a family of sets then \bigcap \mathcal denotes the set: \bigcap \mathcal ~~\colon=~ \bigcap_ B ~~\colon=~ \ ~=~ \. Nullary intersections If I = \varnothing then \bigcap_ L_i = \ where every possible thing x in the universe vacuously satisfied the condition: "if i \in \varnothing then x \in L_i". Consequently, \bigcap_ L_i = \ consists of in the universe. So if I = \varnothing and: #if you are working in a
model A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
in which there exists some universe X then \bigcap_ L_i = \ ~=~ X. #otherwise, if you are working in a
model A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
in which "the class of all things x" is not a set (by far the most common situation) then \bigcap_ L_i is because \bigcap_ L_i consists of , which makes \bigcap_ L_i a
proper class Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map for ...
and 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 of sets or an refers to the intersection of a finite collection of sets. Some authors adopt the so called , which is the convention that an empty intersection of sets is equal to some canonical set. In particular, if all sets are subsets of some set X then some author may declare that the empty intersection of these sets be equal to X. However, the nullary intersection convention is not as commonly accepted as the nullary union convention and this article will not adopt it (this is due to the fact that unlike the empty union, the value of the empty intersection depends on X so if there are multiple sets under consideration, which is commonly the case, then the value of the empty intersection risks becoming ambiguous). Multiple index sets \bigcup_ S_ ~~\colon=~ \bigcup_ S_ \bigcap_ S_ ~~\colon=~ \bigcap_ S_


Distributing unions and intersections


Binary ⋂ of arbitrary ⋃'s

and * If all \left(L_i\right)_ are
pairwise disjoint In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
and all \left(R_j\right)_ are also pairwise disjoint, then so are all \left(L_i \cap R_j\right)_ (that is, if (i, j) \neq \left(i_2, j_2\right) then \left(L_i \cap R_j\right) \cap \left(L_ \cap R_\right) = \varnothing). * Importantly, if I = J then in general, ~\left(\bigcup_ L_i\right) \cap \left(\bigcup_ R_i\right) ~~\color\color~~ \bigcup_ \left(L_i \cap R_i\right)~ (an example of this is given below). The single union on the right hand side be over all pairs (i, j) \in I \times I: ~\left(\bigcup_ L_i\right) \cap \left(\bigcup_ R_i\right) ~~=~~ \bigcup_ \left(L_i \cap R_j\right).~ The same is usually true for other similar non-trivial set equalities and relations that depend on two (potentially unrelated) indexing sets I and J (such as or ). Two exceptions are (unions of unions) and (intersections of intersections), but both of these are among the most trivial of set equalities and moreover, even for these equalities there is still something that must be proven. * : Let X \neq \varnothing and let I = \. Let L_1 \colon= R_2 \colon= X and let L_2 \colon= R_1 \colon= \varnothing. Then X = X \cap X = \left(L_1 \cup L_2\right) \cap \left(R_2 \cup R_2\right) = \left(\bigcup_ L_i\right) \cap \left(\bigcup_ R_i\right) ~\neq~ \bigcup_ \left(L_i \cap R_i\right) = \left(L_1 \cap R_1\right) \cup \left(L_2 \cap R_2\right) = \varnothing \cup \varnothing = \varnothing. Furthermore, \varnothing = \varnothing \cup \varnothing = \left(L_1 \cap L_2\right) \cup \left(R_2 \cap R_2\right) = \left(\bigcap_ L_i\right) \cup \left(\bigcap_ R_i\right) ~\neq~ \bigcap_ \left(L_i \cup R_i\right) = \left(L_1 \cup R_1\right) \cap \left(L_2 \cup R_2\right) = X \cap X = X.


Binary ⋃ of arbitrary ⋂'s

and * Importantly, if I = J then in general, ~\left(\bigcap_ L_i\right) \cup \left(\bigcap_ R_i\right) ~~\color\color~~ \bigcap_ \left(L_i \cup R_i\right)~ (an example of this is given above). The single intersection on the right hand side be over all pairs (i, j) \in I \times I: ~\left(\bigcap_ L_i\right) \cup \left(\bigcap_ R_i\right) ~~=~~ \bigcap_ \left(L_i \cup R_j\right).~


Arbitrary ⋂'s and arbitrary ⋃'s


=Incorrectly distributing by swapping ⋂ and ⋃

= Naively swapping \;\bigcup_\; and \;\bigcap_\; may produce a different set The following inclusion always holds: In general, equality need not hold and moreover, the right hand side depends on how for each fixed i \in I, the sets \left(S_\right)_ are labelled; and analogously, the left hand side depends on how for each fixed j \in J, the sets \left(S_\right)_ are labelled. An example demonstrating this is now given. Equality in can hold under certain circumstances, such as in , which is the special case where \left(S_\right)_ is \left(L_i \setminus R_j\right)_ (that is, S_ \colon= L_i \setminus R_j with the same indexing sets I and J), or such as in , which is the special case where \left(S_\right)_ is \left(L_i \setminus R_j\right)_ (that is, \hat_ \colon= L_i \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 \cup and \cap is needed.


=Correct distributive laws

= Suppose that for each i \in I, J_i is a non-empty index set and for each j \in J_i, let T_ be any set (for example, to apply this law to \left(S_\right)_, use J_i \colon= J for all i \in I and use T_ \colon= S_ for all i \in I and all j \in J_i = J). Let J_ ~\colon=~ \prod_ J_i denote the
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...
, which can be interpreted as the set of all functions f ~:~ I ~\to~ \bigcup_ J_i such that f(i) \in J_i for every i \in I. Such a function may also be denoted using the tuple notation \left(f_i\right)_ where f_i := f(i) for every i \in I and conversely, a tuple \left(f_i\right)_ is just notation for the function with domain I whose value at i \in I is f_i; both notations can be used to denote the elements of J_. Then where J_ ~\colon=~ \prod_ J_i.


=Applying the distributive laws

= : In the particular case where all J_i are equal (that is, J_i = J_ for all i, i_2 \in I, which is the case with the family \left(S_\right)_, for example), then letting J denote this common set, the Cartesian product will be J_ ~\colon=~ \prod_ J_i = \prod_ J = J^I, which is the set of all functions of the form f ~:~ I ~\to~ J. The above set equalities and , respectively become: \bigcap_ \left ;\bigcup_ S_\right= \bigcup_ \left ;\bigcap_ S_\right/math> \bigcup_ \left ;\bigcap_ S_\right= \bigcap_ \left ;\bigcup_ S_\right/math> which when combined with implies: \bigcup_ \left bigcap_ S_\right ~=~ \bigcap_ \left ;\bigcup_ S_\right ~~\color\color~~ \bigcup_ \left ;\bigcap_ S_\right ~=~ \bigcap_ \left bigcup_ S_\right/math> where * on the left hand side, the indices f \text i range over f \in J^I \text i \in I (so the subscripts of S_ range over i \in I \text f(i) \in f(I) \subseteq J) * on the right hand side, the indices g \text j range over g \in I^J \text j \in J (so the subscripts of S_ range over j \in J \text g(j) \in g(J) \subseteq I). : To apply the general formula to the case of \left(C_k\right)_ and \left(D_\right)_, use I \colon= \, J_1 \colon= K, J_2 \colon= L, and let T_ \colon= C_k for all k \in J_1 and let T_ \colon= D_l for all l \in J_2. Every map f \in J_ ~\colon=~ \prod_ J_i = J_1 \times J_2 = K \times L can be bijectively identified with the pair \left(f(1), f(2)\right) \in K \times L (the inverse sends (k,l) \in K \times L to the map f_ \in J_ defined by 1 \mapsto k and 2 \mapsto l; this is technically just a change of notation). Recall that was ~\bigcap_ \left ;\bigcup_ T_\right= \bigcup_ \left ;\bigcap_ T_\right~ Expanding and simplifying the left hand side gives \bigcap_ \left ;\bigcup_ T_\right= \left(\bigcup_ T_\right) \cap \left(\;\bigcup_ T_\right) = \left(\bigcup_ T_\right) \cap \left(\;\bigcup_ T_\right) = \left(\bigcup_ C_k\right) \cap \left(\;\bigcup_ D_l\right) and doing the same to the right hand side gives: \bigcup_ \left ;\bigcap_ T_\right = \bigcup_ \left(T_ \cap T_\right) = \bigcup_ \left(C_ \cap D_\right) = \bigcup_ \left(C_k \cap D_l\right) = \bigcup_ \left(C_k \cap D_l\right). Thus the general identity reduces down to the previously given set equality : \left(\bigcup_ C_k\right) \cap \left(\;\bigcup_ D_l\right) = \bigcup_ \left(C_k \cap D_l\right).


Distributing subtraction over ⋃ and ⋂

The next identities are known as
De Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...
. The following four set equalities can be deduced from the equalities - above. In general, naively swapping \;\bigcup_\; and \;\bigcap_\; may produce a different set (see this note for more details). The equalities \bigcup_ \bigcap_ \left(L_i \setminus R_j\right) ~=~ \bigcap_ \bigcup_ \left(L_i \setminus R_j\right) \quad \text \quad \bigcup_ \bigcap_ \left(L_i \setminus R_j\right) ~=~ \bigcap_ \bigcup_ \left(L_i \setminus R_j\right) found in and are thus unusual in that they state exactly that swapping \;\bigcup_\; and \;\bigcap_\; will change the resulting set.


Commutativity and associativity of ⋃ and ⋂

Commutativity: \bigcup_ S_ ~~\colon=~ \bigcup_ S_ ~=~ \bigcup_ \left(\bigcup_ S_\right) ~=~ \bigcup_ \left(\bigcup_ S_\right) \bigcap_ S_ ~~\colon=~ \bigcap_ S_ ~=~ \bigcap_ \left(\bigcap_ S_\right) ~=~ \bigcap_ \left(\bigcap_ S_\right) Unions of unions and intersections of intersections: \left(\bigcup_ L_i\right) \cup R ~=~ \bigcup_ \left(L_i \cup R\right) \left(\bigcap_ L_i\right) \cap R ~=~ \bigcap_ \left(L_i \cap R\right) and and if I = J then also:To deduce from , it must still be shown that \bigcup_ \left(L_i \cup R_j\right) ~=~ \bigcup_ \left(L_i \cup R_i\right) so is not a completely immediate consequence of . (Compare this to the commentary about ).


Cartesian products Π of arbitrarily many sets


Intersections ⋂ of Π

If \left(S_\right)_ is a family of sets then * Moreover, a tuple \left(x_i\right)_ belongs to the set in above if and only if x_i \in S_ for all i \in I and all j \in J. If \left(L_i\right)_ and \left(R_i\right)_ are two families indexed by the same set then \left(\prod_ L_i\right) \cap \left(\prod_R_i\right) ~=~ \prod_ \left(L_i \cap R_i\right) So for instance, (L \times R) \cap \left(L_2 \times R_2\right) ~=~ \left(L \cap L_2\right) \times \left(R \cap R_2\right) (L \times R) \cap \left(L_2 \times R_2\right) \cap \left(L_3 \times R_3\right) ~=~ \left(L \cap L_2 \cap L_3\right) \times \left(R \cap R_2 \cap R_3\right) and (L \times M \times R) \cap \left(L_2 \times M_2 \times R_2\right) ~=~ \left(L \cap L_2\right) \times \left(M \cap M_2\right) \times \left(R \cap R_2\right) Intersections of products indexed by different sets Let \left(L_i\right)_ and \left(R_j\right)_ be two families indexed by different sets. Technically, I \neq J implies \left(\prod_ L_i\right) \cap \left(\prod_ R_j\right) = \varnothing. However, sometimes these products are somehow identified as the same set through some
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
or one of these products is identified as a subset of the other via some
injective map In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
, in which case (by
abuse of notation In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not entirely formally correct, but which might help simplify the exposition or suggest the correct intuition (while possibly minimizing errors an ...
) this intersection may be equal to some other (possibly non-empty) set. * For example, if I := \ and J := \ with all sets equal to \R then \prod_ L_i = \prod_ \R = \R^2 and \prod_ R_j = \prod_ \R = \R^3 where \R^2 \cap \R^3 = \varnothing , for example, \prod_ \R = \R^2 is identified as a subset of \prod_ \R = \R^3 through some
injection Injection or injected may refer to: Science and technology * Injective function, a mathematical function mapping distinct arguments to distinct values * Injection (medicine), insertion of liquid into the body with a syringe * Injection, in broadca ...
, such as maybe (x, y) \mapsto (x, y, 0) for instance; however, in this particular case the product \prod_ L_i actually represents the J-indexed product \prod_ L_i where L_3 := \. * For another example, take I := \ and J := \ with L_1 := \R^2 and L_2, R_1, R_2, \text R_3 all equal to \R. Then \prod_ L_i = \R^2 \times \R and \prod_ R_j = \R \times \R \times \R, which can both be identified as the same set via the bijection that sends ((x, y), z) \in \R^2 \times \R to (x, y, z) \in \R \times \R \times \R. Under this identification, \left(\prod_ L_i\right) \cap \left(\prod_R_j\right) ~=~ \R^3.


Unions ⋃ of Π

For unions, only the following is guaranteed in general: \bigcup_ \left(\prod_ S_\right) ~~\color\color~~ \prod_ \left(\bigcup_ S_\right) \qquad \text \qquad \bigcup_ \left(\prod_ S_\right) ~~\color\color~~ \prod_ \left(\bigcup_ S_\right) where \left(S_\right)_ is a family of sets. However, \begin \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\\ .5ex~&=~ \left \times \left(R \setminus R_2\right)\right~\cup~ \left _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


Difference \ of Π

If \left(L_i\right)_ and \left(R_i\right)_ are two families of sets then: \begin \left(\prod_ L_i\right) ~\setminus~ \left(\prod_R_i\right) ~&=~ \;~ \bigcup_ \; ~ \prod_ \beginL_j \,\setminus\, R_j & \text i = j \\ L_i & \text i \neq j \\ \end \\ .5ex~&=~ \;~ \bigcup_ \; ~ \Big left(L_j \,\setminus\, R_j\right) ~\times~ \prod_ L_i\Big\\ .5ex~&=~ \bigcup_ \Big left(L_j \,\setminus\, R_j\right) ~\times~ \prod_ L_i\Big\\ .3ex\end so for instance, \begin \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 \times \left(R \,\setminus\, R_2\right)\right\\ \end and (L \times M \times R) ~\setminus~ \left(L_2 \times M_2 \times R_2\right) ~=~ \left left(L \,\setminus\, L_2\right) \times M \times R\right~\cup~ \left \times \left(M \,\setminus\, M_2\right) \times R\right~\cup~ \left \times M \times \left(R \,\setminus\, R_2\right)\right/math>


Symmetric difference ∆ of Π

\begin \left(\prod_ L_i\right) ~\triangle~ \left(\prod_R_i\right) ~&=~ \;~ \left(\prod_ L_i\right) ~\cup~ \left(\prod_R_i\right) \;\setminus\; \prod_ L_i \cap R_i \\ .5ex\end


Functions and sets

Let f : X \to Y be any function. Let L \text R be completely arbitrary sets. Assume A \subseteq X \text C \subseteq Y.


Definitions

Let f : X \to Y be any function, where we denote its X by \operatorname f and denote its Y by \operatorname 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 "," 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 \cap (X \cup Y) = \varnothing, or that L \cap X \neq \varnothing L \cap Y \neq \varnothing (which happens, for instance, if X = Y), etc. This generality is useful in situations where f : X \to Y is a map between two subsets X \subseteq U and Y \subseteq V of some larger sets U and V, and where the set L might not be entirely contained in X = \operatorname f and/or Y = \operatorname f (e.g. if all that is known about L is that L \subseteq U); in such a situation it may be useful to know what can and cannot be said about f(L) and/or f^(L) without having to introduce a (potentially unnecessary) intersection such as: f(L \cap X) and/or f^(L \cap Y). Images and preimages of sets If L is set then the is defined to be the set: f(L) ~:=~ \ while the is: f^(L) ~:=~ \ where if L = \ is a singleton set then the or is f^(s) ~:=~ f^(\) ~=~ \. Denote by \operatorname f or \operatorname f the or of f : X \to Y, which is the set: \operatorname f ~=~ f(X) ~:=~ f(\operatorname f) ~=~ \. Saturated sets A set A is said to be or a if any of the following equivalent conditions are satisfied:
  1. There exists a set R such that A = f^(R). * Any such set R necessarily contains f(A) as a subset.
  2. A = f^(f(A)).
  3. A \supseteq f^(f(A)) and A \subseteq \operatorname f. * The inclusion L \cap \operatorname f \subseteq f^(f(L)) always holds, where if A \subseteq \operatorname f then this becomes A \subseteq f^(f(A)).
For a set A to be f-saturated, it is necessary that A \subseteq \operatorname f. Compositions and restrictions of functions If f and g are maps then g \circ f denotes the map g \circ f ~:~ \ ~\to~ \operatorname g with domain and codomain \begin \operatorname (g \circ f) &= \ \\ .4ex\operatorname (g \circ f) &= \operatorname g \\ .7ex\end defined by (g \circ f)(x) := g(f(x)). The denoted by f\big\vert_L, is the map f\big\vert_L ~:~ L \cap \operatorname f ~\to~ Y with \operatorname f\big\vert_L ~=~ L \cap \operatorname f defined by sending x \in L \cap \operatorname f to f(x); that is, f\big\vert_L(x) ~:=~ f (x). Alternatively, ~f\big\vert_L ~=~ f \circ \operatorname~ where ~\operatorname ~:~ L \cap X \to X~ denotes the
inclusion map In mathematics, if A is a subset of B, then the inclusion map (also inclusion function, insertion, or canonical injection) is the function \iota that sends each element x of A to x, treated as an element of B: \iota : A\rightarrow B, \qquad \iot ...
, which is defined by \operatorname(s) := s.


(Pre)Images of arbitrary unions ⋃'s and intersections ⋂'s

If \left(L_i\right)_ is a family of arbitrary sets indexed by I \neq \varnothing then: \begin f\left(\bigcap_ L_i\right) \;&~\;\color\color~ \;\;\;\bigcap_ f\left(L_i\right) \\ f\left(\bigcup_ L_i\right) \;&~=~ \;\bigcup_ f\left(L_i\right) \\ f^\left(\bigcup_ L_i\right) \;&~=~ \;\bigcup_ f^\left(L_i\right) \\ f^\left(\bigcap_ L_i\right) \;&~=~ \;\bigcap_ f^\left(L_i\right) \\ \end So of these four identities, it is 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 \bigcap_ L_i be will be f-saturated and equality will hold in the first relation above; explicitly, this means: If \left(A_i\right)_ is a family of arbitrary subsets of X = \operatorname f, which means that A_i \subseteq X for all i, then becomes:


(Pre)Images of binary set operations

Throughout, let L and R be any sets and let f : X \to Y be any function. Summary As the table below shows, set equality is guaranteed for of: intersections, set subtractions, and symmetric differences. Preimages preserve set operations Preimages of sets are well-behaved with respect to all basic set operations: \begin f^(L \cup R) ~&=~ f^(L) \cup f^(R) \\ f^(L \cap R) ~&=~ f^(L) \cap f^(R) \\ f^(L \setminus\, R) ~&=~ f^(L) \setminus\, f^(R) \\ f^(L \,\triangle\, R) ~&=~ f^(L) \,\triangle\, f^(R) \\ \end In words, preimages distribute over unions, intersections, set subtraction, and symmetric difference. Images preserve unions Images of unions are well-behaved: \begin f(L \cup R) ~&=~ f(L) \cup f(R) \\ \end but images of the other basic set operations are since only the following are guaranteed in general: \begin 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 In words, images distribute over unions but not necessarily over intersections, set subtraction, or symmetric difference. In general, equality is not guaranteed for images of set subtraction L \setminus R nor for images of the other two elementary set operators that can be defined as the difference of two sets: L \cap R = L \setminus (L \setminus R) \quad \text \quad L \triangle R = (L \cup R) \setminus (L \cap R). If L = X then f(X \setminus R) \supseteq f(X) \setminus f(R) where as in the more general case, equality is not guaranteed. If f is surjective then f(X \setminus R) ~\supseteq~ Y \setminus f(R), which can be rewritten as: f\left(R^\right) ~\supseteq~ f(R)^ if R^ := X \setminus R and f(R)^ := Y \setminus f(R).


Counter-examples: images of operations not distributing

If f : \ \to Y is constant, L = \, and R = \ then all four of the set containments \begin f(L \cap R) ~&\subseteq~ f(L) \cap f(R) \\ f(L \setminus R) ~&\supseteq~ f(L) \setminus f(R) \\ f(X \setminus R) ~&\supseteq~ f(X) \setminus f(R) \\ f(L \triangle R) ~&\supseteq~ f(L) \triangle f(R) \\ \end are strict/proper; that is, equality does not hold. 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 In mathematics, a constant function is a function whose (output) value is the same for every input value. For example, the function is a constant function because the value of is 4 regardless of the input value (see image). Basic properties ...
whose domain contains at least two (distinct) points. : Let f : X \to Y be any constant function with image f(X) = \ and suppose that L, R \subseteq X are non-empty disjoint subsets; that is, L \neq \varnothing, R \neq \varnothing, and L \cap R = \varnothing, which implies that all of the sets L ~\triangle~ R = L \cup R, \,L \setminus R = L, and X \setminus R \supseteq L \setminus R are not empty and so consequently, their images under f are all equal to \.
  1. The containment ~f(L \setminus R) ~\supseteq~ f(L) \setminus f(R)~ is strict: \ ~=~ f(L \setminus R) ~\neq~ f(L) \setminus f(R) ~=~ \ \setminus \ ~=~ \varnothing In words: functions might not distribute over set subtraction \,\setminus\,
  2. The containment ~f(X \setminus R) ~\supseteq~ f(X) \setminus f(R)~ is strict: \ ~=~ f(X \setminus R) ~\neq~ f(X) \setminus f(R) ~=~ \ \setminus \ ~=~ \varnothing.
  3. The containment ~f(L ~\triangle~ R) ~\supseteq~ f(L) ~\triangle~ f(R)~ is strict: \ ~=~ f\left(L ~\triangle~ R\right) ~\neq~ f(L) ~\triangle~ f(R) ~=~ \ \triangle \ ~=~ \varnothing In words: functions might not distribute over symmetric difference \,\triangle\, (which can be defined as the set subtraction of two sets: L \triangle R = (L \cup R) \setminus (L \cap R)).
  4. The containment ~f(L \cap R) ~\subseteq~ f(L) \cap f(R)~ is strict: \varnothing ~=~ f(\varnothing) ~=~ f(L \cap R) ~\neq~ f(L) \cap f(R) ~=~ \ \cap \ ~=~ \ In words: functions might not distribute over set intersection \,\cap\, (which can be defined as the set subtraction of two sets: L \cap R = L \setminus (L \setminus R)).
What the set operations in these four examples have in common is that they either
set subtraction In set theory, the complement of a set , often denoted by (or ), is the set of elements not in . When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is the ...
\setminus (examples (1) and (2)) or else they can naturally as the set subtraction of two sets (examples (3) and (4)). Mnemonic: In fact, for each of the above four set formulas for which equality is not guaranteed, the direction of the containment (that is, whether to use \,\subseteq \text \supseteq\,) can always be deduced by imagining the function f as being and the two sets (L and R) as being non-empty disjoint subsets of its domain. This is because equality fails for such a function and sets: one side will be always be \varnothing and the other non-empty − from this fact, the correct choice of \,\subseteq \text \supseteq\, can be deduced by answering: "which side is empty?" For example, to decide if the ? in f(L \triangle R) \setminus f(R) ~\;~?~\;~ f((L \triangle R) \setminus R) should be \,\subseteq \text \supseteq,\, pretendWhether or not it is even feasible for the function f to be constant and the sets L \triangle R and R to be non-empty and disjoint is irrelevant for reaching the correct conclusion about whether to use \,\subseteq \text \supseteq.\, that f is constant and that L \triangle R and R are non-empty disjoint subsets of f's domain; then the hand side would be empty (since f(L \triangle R) \setminus f(R) = \ \setminus \ = \varnothing), which indicates that \,?\, should be \,\subseteq\, (the resulting statement is always guaranteed to be true) because this is the choice that will make \varnothing = \text ~\;~?~\;~ \text true. Alternatively, the correct direction of containment can also be deduced by consideration of any constant f : \ \to Y with L = \ and R = \. 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 \cap R) always equals f(L) \cap f(R), or alternatively, whether or not f^(L \cap R) always equals f^(L) \cap f^(R) (although \,\cap\, was used here, it can replaced by \,\cup, \,\setminus, \text \,\triangle). The answer to such a question can, as before, be deduced by consideration of this constant function: the answer for the general case (that is, for arbitrary f, L, and R) is always the same as the answer for this choice of (constant) function and disjoint non-empty sets.


Conditions guaranteeing that images distribute over set operations

Characterizations of when equality holds for sets: For any function f : X \to Y, the following statements are equivalent:
  1. f : X \to Y is
    injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
    . * This means: f(x) \neq f(y) for all distinct x, y \in X.
  2. f(L \cap R) = f(L) \,\cap\, f(R) \, \text \, L, R \subseteq X. (The equals sign \,=\, can be replaced with \,\supseteq\,).
  3. f(L \,\setminus R) = f(L) \,\setminus\, f(R) \; \text \, L, R \subseteq X. (The equals sign \,=\, can be replaced with \,\subseteq\,).
  4. f(X \setminus R) = f(X) \setminus\, f(R) \; \text \, ~~~~~R \subseteq X. (The equals sign \,=\, can be replaced with \,\subseteq\,).
  5. f(L \,\triangle\, R) = f(L) \,\triangle\, f(R) \; \text \, L, R \subseteq X. (The equals sign \,=\, can be replaced with \,\subseteq\,).
  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) \not\in f(X \setminus \) \; \text \, x \in X.
    2. "for all disjoint singleton subsets" * For statement (d), this is the same as: "for all singleton subsets" (because the definition of "
      pairwise disjoint In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
      " 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).


=Conditions for f(L⋂R) = f(L)⋂f(R)

= f(L \cap R) ~\subseteq~ f(L) \cap f(R) \qquad\qquad \text ''Characterizations of equality'': The following statements are equivalent:
  1. f(L \cap R) ~=~ f(L) \cap f(R)
  2. f(L \cap R) ~\supseteq~ f(L) \cap f(R)
  3. L \cap f^(f(R)) ~\subseteq~ f^(f(L \cap R)) * The left hand side L \cap f^(f(R)) is always equal to L \cap f^(f(L) \cap f(R)) (because L \cap f^(f(R)) ~\subseteq~ f^(f(L)) always holds).
  4. R \cap f^(f(L)) ~\subseteq~ f^(f(L \cap R))
  5. L \cap f^(f(R)) ~=~ f^(f(L \cap R)) \cap L
  6. R \cap f^(f(L)) ~=~ f^(f(L \cap R)) \cap R
  7. If l \in L satisfies f(l) \in f(R) then f(l) \in f(L \cap R).
  8. If y \in f(L) but y \notin f(L \cap R) then y \notin f(R).
  9. f(L) \, \setminus \, f(L \cap R) ~\subseteq~ f(L) \, \setminus \, f(R)
  10. f(R) \, \setminus \, f(L \cap R) ~\subseteq~ f(R) \, \setminus \, f(L)
  11. f(L \cup R) \setminus f(L \cap R) ~\subseteq~ f(L) \,\triangle\, f(R)
  12. Any of the above three conditions (i) - (k) but with the subset symbol \,\subseteq\, replaced with an equals sign \,=.\,
''Sufficient conditions for equality'': Equality holds if any of the following are true:
  1. f is injective.See
  2. The restriction f\big\vert_ is injective.
  3. f^(f(R)) ~\subseteq~ R
  4. f^(f(L)) ~\subseteq~ L
  5. R is f-saturated; that is, f^(f(R)) = R
  6. L is f-saturated; that is, f^(f(L)) = L
  7. f(L) ~\subseteq~ f(L \cap R)
  8. f(R) ~\subseteq~ f(L \cap R)
  9. f(L \,\setminus\, R) ~\subseteq~ f(L) \setminus \, f(R) or equivalently, f(L \,\setminus\, R) ~=~ f(L) \setminus f(R)
  10. f(R \,\setminus\, L) ~\subseteq~ f(R) \setminus \, f(L) or equivalently, f(R \,\setminus\, L) ~=~ f(R) \setminus f(L)
  11. f\left(L ~\triangle~ R\right) \subseteq f(L) ~\triangle~ f(R) or equivalently, f\left(L ~\triangle~ R\right) = f(L) ~\triangle~ f(R)
  12. R \cap \operatorname f \,\subseteq L
  13. L \cap \operatorname f \,\subseteq R
  14. R \subseteq L
  15. L \subseteq R
In addition, the following always hold: f\left(f^(L) \cap R\right) ~=~ L \cap f(R) f\left(f^(L) \cup R\right) ~=~ (L \cap \operatorname f) \cup f(R)


=Conditions for f(L\R) = f(L)\f(R)

= f(L \setminus R) ~\supseteq~ f(L) \setminus f(R) \qquad\qquad \text ''Characterizations of equality'': The following statements are equivalent:
  1. f(L \setminus R) ~=~ f(L) \setminus f(R)
  2. f(L \setminus R) ~\subseteq~ f(L) \setminus f(R)
  3. L \cap f^(f(R)) ~\subseteq~ R
  4. L \cap f^(f(R)) ~=~ L \cap R \cap \operatorname f
  5. Whenever y \in f(L) \cap f(R) then L \cap f^(y) \subseteq R.
  6. f(L) \cap f(R) ~\subseteq~ \left\ * The set on the right hand side is always equal to \left\.
  7. f(L) \cap f(R) ~=~ \left\ * This is the above condition (f) but with the subset symbol \,\subseteq\, replaced with an equals sign \,=.\,
''Necessary conditions for equality'' (excluding characterizations): If equality holds then the following are necessarily true:
  1. f(L \cap R) = f(L) \cap f(R), or equivalently f(L \cap R) \supseteq f(L) \cap f(R).
  2. L \cap f^(f(R)) ~=~ L \cap f^(f(L \cap R)) or equivalently, L \cap f^(f(R)) ~\subseteq~ f^(f(L \cap R))
  3. R \cap f^(f(L)) ~=~ R \cap f^(f(L \cap R))
''Sufficient conditions for equality'': Equality holds if any of the following are true:
  1. f is injective.
  2. The restriction f\big\vert_ is injective.
  3. f^(f(R)) ~\subseteq~ RNote that this condition depends entirely on R and on L. or equivalently, R \cap \operatorname f ~=~ f^(f(R))
  4. R is f-saturated; that is, R = f^(f(R)).
  5. f\left(L ~\triangle~ R\right) \subseteq f(L) ~\triangle~ f(R) or equivalently, f\left(L ~\triangle~ R\right) = f(L) ~\triangle~ f(R)


=Conditions for f(X\R) = f(X)\f(R)

= f(X \setminus R) ~\supseteq~ f(X) \setminus f(R) \qquad\qquad \text f : X \to Y ''Characterizations of equality'': The following statements are equivalent:
  1. f(X \setminus R) ~=~ f(X) \setminus f(R)
  2. f(X \setminus R) ~\subseteq~ f(X) \setminus f(R)
  3. f^(f(R)) \,\subseteq\, R
  4. f^(f(R)) \,=\, R \cap \operatorname f
  5. R \cap \operatorname f is f-saturated.
  6. Whenever y \in f(R) then f^(y) \subseteq R.
  7. f(R) ~\subseteq~ \left\
  8. f(R) ~=~ \left\
   where if R \subseteq \operatorname f then this list can be extended to include:
  1. R is f-saturated; that is, R = f^(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^(f(R)).


=Conditions for f(L∆R) = f(L)∆f(R)

= f\left(L ~\triangle~ R\right) ~\supseteq~ f(L) ~\triangle~ f(R) \qquad\qquad \text ''Characterizations of equality'': The following statements are equivalent:
  1. f\left(L ~\triangle~ R\right) = f(L) ~\triangle~ f(R)
  2. f\left(L ~\triangle~ R\right) \subseteq f(L) ~\triangle~ f(R)
  3. f(L \,\setminus\, R) = f(L) \,\setminus\, f(R)  and  f(R \,\setminus\, L) = f(R) \,\setminus\, f(L)
  4. f(L \,\setminus\, R) \subseteq f(L) \,\setminus\, f(R)  and  f(R \,\setminus\, L) \subseteq f(R) \,\setminus\, f(L)
  5. L \cap f^(f(R)) ~\subseteq~ R  and  R \cap f^(f(L)) ~\subseteq~ L * The inclusions L \cap f^(f(R)) ~\subseteq~ f^(f(L)) and R \cap f^(f(L)) ~\subseteq~ f^(f(R)) always hold.
  6. L \cap f^(f(R)) ~=~ R \cap f^(f(L)) * If this above set equality holds, then this set will also be equal to both L \cap R \cap \operatorname f and L \cap R \cap f^(f(L \cap R)).
  7. L \cap f^(f(L \cap R)) ~=~ R \cap f^(f(L \cap R))  and  f(L \cap R) ~\supseteq~ f(L) \cap f(R).
''Necessary conditions for equality'' (excluding characterizations): If equality holds then the following are necessarily true:
  1. f(L \cap R) = f(L) \cap f(R), or equivalently f(L \cap R) \supseteq f(L) \cap f(R).
  2. L \cap f^(f(L \cap R)) ~=~ R \cap f^(f(L \cap R))
''Sufficient conditions for equality'': Equality holds if any of the following are true:
  1. f is injective.
  2. The restriction f\big\vert_ is injective.


Exact formulas/equalities for images of set operations


=Formulas for f(L\R)

For any function f : X \to Y and any sets L and R,Let P := \left\ and let (\star) denote the set equality f(L \setminus R) = Y \setminus P, which will now be proven. If y \in Y \setminus P then L \cap f^(y) \not\subseteq R so there exists some x \in L \cap f^(y) \setminus R; now f^(y) \subseteq X implies x \in L \cap X \setminus R so that y = f(x) \in f(L \cap X \setminus R) = f(L \setminus R). To prove the reverse inclusion f(L \setminus R) \subseteq Y \setminus P, let y \in f(L \setminus R) so that there exists some x \in X \cap L \setminus R such that y = f(x). Then x \in L \cap f^(y) \setminus R so that L \cap f^(y) \not\subseteq R and thus y \not\in P, which proves that y \in Y \setminus P, as desired. \blacksquare Defining Q := f(L) \cap P = \left\, the identity f(L \setminus R) = f(L) \setminus Q follows from (\star) and the inclusions f(L \setminus R) \subseteq f(L) \subseteq Y. \blacksquare \begin f(L \setminus R) &= Y ~~~\;\,\, \setminus \left\ \\ .4ex&= f(L) \setminus \left\ \\ .4ex&= f(L) \setminus \left\ \\ .4ex&= f(L) \setminus \left\ \qquad && \text \quad V \supseteq f(L \cap R) \\ .4ex&= f(S) \setminus \left\ \qquad && \text \quad S \supseteq L \cap X. \\ .7ex\end


=Formulas for f(X\R)

Taking L := X = \operatorname f in the above formulas gives: \begin f(X \setminus R) &= Y ~~~\;\,\, \setminus \left\ \\ .4ex&= f(X) \setminus \left\ \\ .4ex&= f(X) \setminus \left\ \\ .4ex&= f(X) \setminus \left\ \qquad \text \quad W \supseteq f(R) \\ .4ex\end where the set \left\ is equal to the image under f of the largest f-saturated subset of R.
  • In general, only f(X \setminus R) \,\supseteq\, f(X) \setminus f(R) always holds and equality is not guaranteed; but replacing "f(R)" with its subset "\left\" results in a formula in which equality is guaranteed: f(X \setminus R) \,=\, f(X) \setminus \left\. From this it follows that:Let f_R := \left\ where because f_R \subseteq f(R \cap L), f_R is also equal to f_R = \left\. As proved above, f(L \setminus R) = f(L) \setminus f_R so that f(L) \setminus f(R) = f(L \setminus R) if and only if f(L) \setminus f(R) = f(L) \setminus f_R. Since f(L) \setminus f(R) = f(L) \setminus (f(L) \cap f(R)), this happens if and only if f(L) \setminus (f(L) \cap f(R)) = f(L) \setminus f_R. Because f(L) \cap f(R) \text f_R are both subsets of f(L), the condition on the right hand side happens if and only if f(L) \cap f(R) = f_R. Because f_R \subseteq f(R \cap L) \subseteq f(L) \cap f(R), the equality f(L) \cap f(R) = f_R holds if and only if f(L) \cap f(R) \subseteq f_R. \blacksquare If f(R) \subseteq f(L) (such as when L = X or R \subseteq L) then f(L) \cap f(R) \subseteq f_R if and only if f(R) \subseteq f_R. In particular, taking L = X proves: f(X \setminus R) = f(X) \setminus f(R) if and only if f(R) \subseteq \left\, where f(R \cap X) = f(R). \blacksquare f(X \setminus R) = f(X) \setminus f(R) \quad \text \quad f(R) = \left\ \quad \text \quad f^(f(R)) \subseteq R.
  • If f_R := \left\ then f(X \setminus R) = f(X) \setminus f_R, which can be written more symmetrically as f(X \setminus R) = f_X \setminus f_R (since f_X = f(X)).


=Formulas for f(L∆R)

It follows from L \,\triangle\, R = (L \cup R) \setminus (L \cap R) and the above formulas for the image of a set subtraction that for any function f : X \to Y and any sets L and R, \begin f(L \,\triangle\, R) &= Y ~~~\;~~~\;~~~\; \setminus \left\ \\ .4ex&= f(L \cup R) \setminus \left\ \\ .4ex&= f(L \cup R) \setminus \left\ \\ .4ex&= f(L \cup R) \setminus \left\ \qquad && \text \quad V \supseteq f(L \cap R) \\ .4ex&= f(S) ~~\,~~~\,~\, \setminus \left\ \qquad && \text \quad S \supseteq (L \cup R) \cap X. \\ .7ex\end


=Formulas for f(L)

It follows from the above formulas for the image of a set subtraction that for any function f : X \to Y and any set L,\begin f(L) &= Y ~~~\;\, \setminus \left\ \\ .4ex&= \operatorname f \setminus \left\ \\ .4ex&= W ~~~\, \setminus \left\ \qquad \text \quad W \supseteq f(L) \\ .7ex\end This is more easily seen as being a consequence of the fact that for any y \in Y, f^(y) \cap L = \varnothing if and only if y \not\in f(L).


=Formulas for f(L⋂R)

It follows from the above formulas for the image of a set that for any function f : X \to Y and any sets L and R, \begin f(L \cap R) &= Y~~~~~ \setminus \left\ && \\ .4ex&= f(L) \setminus \left\ && \\ .4ex&= f(L) \setminus \left\ \qquad && \text \quad U \supseteq f(L) \\ .4ex&= f(R) \setminus \left\ && \\ .4ex&= f(R) \setminus \left\ \qquad && \text \quad V \supseteq f(R) \\ .4ex&= f(L) \cap f(R) \setminus \left\ && \\ .7ex\end where moreover, for any y \in Y, :L \cap f^(y) \subseteq L \setminus R~ if and only if ~L \cap R \cap f^(y) = \varnothing~ if and only if ~R \cap f^(y) \subseteq R \setminus L~ if and only if ~y \not\in f(L \cap R). The sets U and V mentioned above could, in particular, be any of the sets f(L \cup R), \;\operatorname f, or Y, for example.


(Pre)Images of set operations on (pre)images

Let L and R be arbitrary sets, f : X \to Y be any map, and let A \subseteq X and C \subseteq Y. (Pre)Images of operations on images Since f(L) \setminus f(L \setminus R) ~=~ \left\, \begin f^(f(L) \setminus f(L \setminus R)) &=&& f^\left(\left\\right) \\ &=&& \left\ \\ \end Since f(X) \setminus f(L \setminus R) ~=~ \left\, \begin f^(Y \setminus f(L \setminus R)) &~=~&& f^(f(X) \setminus f(L \setminus R)) \\ &=&& f^\left(\left\\right) \\ &=&& \left\ \\ &~=~&& X \setminus f^(f(L \setminus R)) \\ \end Using L := X, this becomes ~f(X) \setminus f(X \setminus R) ~=~ \left\~ and \begin f^(Y \setminus f(X \setminus R)) &~=~&& f^(f(X) \setminus f(X \setminus R)) \\ &=&& f^\left(\left\\right) \\ &=&& \left\ \\ &\subseteq&& R \\ \end and so \begin f^(Y \setminus f(L)) &~=~&& f^(f(X) \setminus f(L)) \\ &=&& f^\left(\left\\right) \\ &=&& \ \\ &=&& X \setminus f^(f(L)) \\ &\subseteq&& X \setminus L \\ \end


(Pre)Images and Cartesian products Π

Let \prod Y_ := \prod_ Y_j and for every k \in J, let \pi_k ~:~ \prod_ Y_j ~\to~ Y_k denote the canonical projection onto Y_k. Definitions Given a collection of maps F_j : X \to Y_j indexed by j \in J, define the map \begin \left(F_j\right)_ :\;&& X &&\;\to\; & \prod_ Y_j \\ .3ex && x &&\;\mapsto\;& \left(F_j\left(x_j\right)\right)_, \\ \end which is also denoted by F_ = \left(F_j\right)_. This is the unique map satisfying \pi_j \circ F_ = F_j \quad \text j \in J. Conversely, if given a map F ~:~ X ~\to~ \prod_ Y_j then F = \left(\pi_j \circ F\right)_. Explicitly, what this means is that if F_k ~:=~ \pi_k \circ F ~:~ X ~\to~ Y_k is defined for every k \in J, then F the unique map satisfying: \pi_j \circ F = F_j for all j \in J; or said more briefly, F = \left(F_j\right)_. The map F_ = \left(F_j\right)_ ~:~ X ~\to~ \prod_ Y_j should not be confused with the
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...
\prod_ F_j of these maps, which is by definition is the map \begin \prod_ F_j :\;&& \prod_ X &&~\;\to\;~ & \prod_ Y_j \\ .3ex && \left(x_j\right)_ &&~\;\mapsto\;~& \left(F_j\left(x_j\right)\right)_ \\ \end with domain \prod_ X = X^J rather than X. Preimage and images of a Cartesian product Suppose F_ = \left(F_j\right)_ ~:~ X ~\to~ \prod_ Y_j. If A ~\subseteq~ X then F_(A) ~~\;\color\color\;~~ \prod_ F_j(A). If B ~\subseteq~ \prod_ Y_j then F_^(B) ~~\;\color\color\;~~ \bigcap_ F_j^\left(\pi_j(B)\right) where equality will hold if B = \prod_ \pi_j(B), in which case F_^(B) = \displaystyle\bigcap_ F_j^\left(\pi_j(B)\right) and For equality to hold, it suffices for there to exist a family \left(B_j\right)_ of subsets B_j \subseteq Y_j such that B = \prod_ B_j, in which case: and \pi_j(B) = B_j for all j \in J.


(Pre)Image of a single set


Containments ⊆ and intersections ⋂ of images and preimages

Equivalences and implications of images and preimages Intersection of a set and a (pre)image The following statements are equivalent:
  1. \varnothing = f(L) \cap R
  2. \varnothing = L \cap f^(R)
  3. \varnothing = f^(f(L)) \cap f^(R)
  4. \varnothing = f^(f(L) \cap R)
Thus for any t, t \not\in f(L) \quad \text \quad L \cap f^(t) = \varnothing.


Sequences and collections of families of sets


Definitions

A or simply a is a set whose elements are sets. A is a family of subsets of X. The of a set X is the set of all subsets of X: \wp(X) ~\colon=~ \. Notation for sequences of sets Throughout, S \text T will be arbitrary sets and S_ and will denote a
net Net or net may refer to: Mathematics and physics * Net (mathematics), a filter-like topological generalization of a sequence * Net, a linear system of divisors of dimension 2 * Net (polyhedron), an arrangement of polygons that can be folded up ...
or a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of sets where if it is a sequence then this will be indicated by either of the notations S_ = \left(S_i\right)_^ \qquad \text \qquad S_ = \left(S_i\right)_ where \N denotes the
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...
. A notation S_ = \left(S_i\right)_ indicates that S_ is a
net Net or net may refer to: Mathematics and physics * Net (mathematics), a filter-like topological generalization of a sequence * Net, a linear system of divisors of dimension 2 * Net (polyhedron), an arrangement of polygons that can be folded up ...
directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''Di ...
by (I, \leq), which (by definition) is a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
if the set I, which is called the net's indexing set, is the natural numbers (that is, if I = \N) and \,\leq\, is the natural order on \N. Disjoint and monotone sequences of sets If S_i \cap S_j = \varnothing for all distinct indices i \neq j then S_ is called a or simply a . A sequence or net S_ of set is called or if (resp. or ) if for all indices i \leq j, S_i \subseteq S_j (resp. S_i \supseteq S_j). A sequence or net S_ of set is called (resp. ) if it is non-decreasing (resp. is non-increasing) and also S_i \neq S_j for all indices i \text j. It is called if it is non-decreasing or non-increasing and it is called if it is strictly increasing or strictly decreasing. A sequences or net S_ is said to denoted by S_ \uparrow S or S_ \nearrow S, if S_ is increasing and the union of all S_i is S; that is, if \bigcup_ S_n = S \qquad \text \qquad S_i \subseteq S_j \quad \text i \leq j. It is said to denoted by S_ \downarrow S or S_ \searrow S, if S_ is increasing and the intersection of all S_i is S that is, if \bigcap_ S_n = S \qquad \text \qquad S_i \supseteq S_j \quad \text i \leq j. Definitions of elementwise operations on families If \mathcal \text \mathcal are families of sets and if S is any set then define: \mathcal \;(\cup)\; \mathcal ~\colon=~ \ \mathcal \;(\cap)\; \mathcal ~\colon=~ \ \mathcal \;(\setminus)\; \mathcal ~\colon=~ \ \mathcal \;(\triangle)\; \mathcal ~\colon=~ \ \mathcal\big\vert_S ~\colon=~ \ = \mathcal \;(\cap)\; \ which are respectively called , , () , , and the / The regular union, intersection, and set difference are all defined as usual and are denoted with their usual notation: \mathcal \cup \mathcal, \mathcal \cap \mathcal, \mathcal \;\triangle\; \mathcal, and \mathcal \setminus \mathcal, respectively. These elementwise operations on families of sets play an important role in, among other subjects, the theory of
filters Filter, filtering or filters may refer to: Science and technology Computing * Filter (higher-order function), in functional programming * Filter (software), a computer program to process a data stream * Filter (video), a software component tha ...
and prefilters on sets. The of a family \mathcal \subseteq \wp(X) is the family: \mathcal^ ~\colon=~ \bigcup_ \ ~=~ \ and the is the family: \mathcal^ ~\colon=~ \bigcup_ \wp(L) ~=~ \.


Definitions of categories of families of sets

A family \mathcal is called , , or in X if \mathcal \subseteq \wp(X) and \mathcal = \mathcal^. A family \mathcal is called if \mathcal = \mathcal^. A family \mathcal is said to be: * (resp. ) if whenever L, R \in \mathcal then L \cap R \in \mathcal (respectively, L \cup R \in \mathcal). * (resp. ) if whenever L_1, L_2, L_3, \ldots are elements of \mathcal then so is their intersections \bigcap_^ L_i := L_1 \cap L_2 \cap L_3 \cap \cdots (resp. so is their union \bigcup_^ L_i := L_1 \cup L_2 \cup L_3 \cup \cdots). * (or ) if whenever L \in \mathcal then X \setminus L \in \mathcal. A family \mathcal of sets is called a/an: * if \mathcal \neq \varnothing and \mathcal is closed under finite-intersections. ** Every non-empty family \mathcal is contained in a unique smallest (with respect to \subseteq) −system that is denoted by \pi(\mathcal) and called * and is said to have if \mathcal \neq \varnothing and \varnothing \not\in \pi(\mathcal). * if \mathcal \neq \varnothing is a family of subsets of X that is a −system, is upward closed in X, and is also , which by definition means that it does not contain the empty set as an element. * or if it is a non-empty family of subsets of some set X whose upward closure in X is a filter on X. * is a non-empty family of subsets of X that contains the empty set, forms a −system, and is also closed under complementation with respect to X. * is an algebra on X that is closed under countable unions (or equivalently, closed under countable intersections).
Sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s of sets often arise in
measure theory In mathematics, the concept of a measure is a generalization and formalization of geometrical measures ( length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simil ...
. Algebra of sets A
family Family (from la, familia) is a Social group, group of people related either by consanguinity (by recognized birth) or Affinity (law), affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its ...
\Phi of subsets of a set X is said to be if \varnothing \in \Phi and for all L, R \in \Phi, all three of the sets X \setminus R, \,L \cap R, and L \cup R are elements of \Phi. The article on this topic lists set identities and other relationships these three operations. Every algebra of sets is also a
ring of sets In mathematics, there are two different notions of a ring of sets, both referring to certain families of sets. In order theory, a nonempty family of sets \mathcal is called a ring (of sets) if it is closed under union and intersection.. That is ...
and a π-system. Algebra generated by a family of sets Given any family \mathcal of subsets of X, there is a unique smallestHere "smallest" means relative to subset containment. So if \Phi is any algebra of sets containing \mathcal, then \Phi_ \subseteq \Phi. algebra of sets in X containing \mathcal. It is called and it will be denote it by \Phi_. This algebra can be constructed as follows:
  1. If \mathcal = \varnothing then \Phi_ = \ and we are done. Alternatively, if \mathcal is empty then \mathcal may be replaced with \, \, \text \ and continue with the construction.
  2. Let \mathcal_0 be the family of all sets in \mathcal together with their complements (taken in X).
  3. Let \mathcal_1 be the family of all possible finite intersections of sets in \mathcal_0.Since \mathcal \neq \varnothing, there is some S \in \mathcal_0 such that its complement also belongs to \mathcal_0. The intersection of these two sets implies that \varnothing \in \mathcal_1. The union of these two sets is equal to X, which implies that X \in \Phi_.
  4. Then the algebra generated by \mathcal is the set \Phi_ consisting of all possible finite unions of sets in \mathcal_1.


Elementwise operations on families

Let \mathcal, \mathcal, and \mathcal be families of sets over X. On the left hand sides of the following identities, \mathcal is the eft most family, \mathcal is in the iddle, and \mathcal is the ight most set.
Commutativity In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
: \mathcal \;(\cup)\; \mathcal = \mathcal \;(\cup)\; \mathcal \mathcal \;(\cap)\; \mathcal = \mathcal \;(\cap)\; \mathcal
Associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
: mathcal \;(\cup)\; \mathcal\;(\cup)\; \mathcal = \mathcal \;(\cup)\; mathcal \;(\cup)\; \mathcal/math> mathcal \;(\cap)\; \mathcal\;(\cap)\; \mathcal = \mathcal \;(\cap)\; mathcal \;(\cap)\; \mathcal/math> Identity: \mathcal \;(\cup)\; \ = \mathcal \mathcal \;(\cap)\; \ = \mathcal \mathcal \;(\setminus)\; \ = \mathcal Domination: \mathcal \;(\cup)\; \ = \ ~~~~\text \mathcal \neq \varnothing \mathcal \;(\cap)\; \ = \ ~~~~\text \mathcal \neq \varnothing \mathcal \;(\cup)\; \varnothing = \varnothing \mathcal \;(\cap)\; \varnothing = \varnothing \mathcal \;(\setminus)\; \varnothing = \varnothing \varnothing \;(\setminus)\; \mathcal = \varnothing


Power set

\wp(L \cap R) ~=~ \wp(L) \cap \wp(R) \wp(L \cup R) ~=~ \wp(L) \ (\cup)\ \wp(R) ~\supseteq~ \wp(L) \cup \wp(R). If L and R are subsets of a vector space X and if s is a scalar then \wp(s L) ~=~ s \wp(L) \wp(L + R) ~\supseteq~ \wp(L) + \wp(R).


Sequences of sets

Ruppose that L is any set such that L \supseteq R_i for every index i. If R_ decreases to R then L \setminus R_ := \left(L \setminus R_i\right)_i increases to L \setminus R whereas if instead R_ increases to R then L \setminus R_ decreases to L \setminus R. If L \text R are arbitrary sets and if L_ = \left(L_i\right)_i increases (resp. decreases) to L then \left(L_i \setminus R\right)_i increase (resp. decreases) to L \setminus R.


Partitions

Suppose that S_ = \left(S_i\right)_^ is any sequence of sets, that S \subseteq \bigcup_i S_i is any subset, and for every index i, let D_i = \left(S_i \cap S\right) \setminus \bigcup_^i \left(S_m \cap S\right). Then S = \bigcup_i D_i and D_ := \left(D_i\right)_^ is a sequence of pairwise disjoint sets. Suppose that S_ = \left(S_i\right)_^ is non-decreasing, let S_0 = \varnothing, and let D_i = S_i \setminus S_ for every i = 1, 2, \ldots. Then \bigcup_i S_i = \bigcup_i D_i and D_ = \left(D_i\right)_^ is a sequence of pairwise disjoint sets.


See also

* * * * * * * * * * * *


Notes

Notes Proofs


Citations


References

* * . * * Courant, Richard, Herbert Robbins, Ian Stewart, ''What is mathematics?: An Elementary Approach to Ideas and Methods'', Oxford University Press US, 1996.
"SUPPLEMENT TO CHAPTER II THE ALGEBRA OF SETS"
* * * * * * * * * * * * * * * * Stoll, Robert R.; , Mineola, N.Y.: Dover Publications (1979)
"The Algebra of Sets", pp 16—23
* * * *


External links



{{Set theory Articles containing proofs Basic concepts in infinite set theory Basic concepts in set theory Families of sets Functions and mappings Isomorphism theorems Mathematical identities Mathematics-related lists Mathematical relations Operations on sets Set theory Theorems in the foundations of mathematics