Equalities for combinations of sets
This article lists mathematical properties and laws of sets, involving the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures for evaluating expressions, and performing calculations, involving these operations and relations.
The binary operations of set union () and intersection () satisfy many identities. Several of these identities or "laws" have well established names.
Notation[edit]
Throughout this article, capital letters (such as and ) will denote sets. On the left hand side of an identity, typically,
- will be the L eft most set,
- will be the M iddle set, and
- will be the R ight most set.
This is to facilitate applying identities to expressions that are complicated or use the same symbols as the identity.[note 1] For example, the identity
may be read as:
Elementary set operations[edit]
For sets and define:
and
where the
symmetric difference is sometimes denoted by
and equals:
[1][2] One set is said to intersect another set if Sets that do not intersect are said to be disjoint.
The power set of is the set of all subsets of and will be denoted by
Universe set and complement notation
The notation
may be used if
is a subset of some set
that is understood (say from context, or because it is clearly stated what the superset
is). It is emphasized that the definition of
depends on context. For instance, had
been declared as a subset of
with the sets
and
not necessarily related to each other in any way, then
would likely mean
instead of
If it is needed then unless indicated otherwise, it should be assumed that denotes the universe set, which means that all sets that are used in the formula are subsets of In particular, the complement of a set will be denoted by where unless indicated otherwise, it should be assumed that denotes the complement of in (the universe)
One subset involved[edit]
Assume
Identity:
Definition: is called a left identity element of a binary operator if for all and it is called a right identity element of if for all A left identity element that is also a right identity element if called an identity element.
The empty set is an identity element of binary union and symmetric difference and it is also a right identity element of set subtraction
but
is not a left identity element of
since
so
if and only if
Idempotence and Nilpotence :
Domination/Zero element:
but
so
Double complement or involution law:
Two sets involved[edit]
In the left hand sides of the following identities, is the L eft most set and is the R ight most set. Assume both are subsets of some universe set
Formulas for binary set operations ⋂, ⋃, \, and ∆[edit]
In the left hand sides of the following identities, is the L eft most set and is the R ight most set. Whenever necessary, both should be assumed to be subsets of some universe set so that
De Morgan's laws[edit]
De Morgan's laws state that for
Commutativity[edit]
Unions, intersection, and symmetric difference are commutative operations:
Set subtraction is not commutative. However, the commutativity of set subtraction can be characterized: from it follows that:
Said differently, if distinct symbols always represented distinct sets, then the
only true formulas of the form
that could be written would be those involving a single symbol; that is, those of the form:
But such formulas are necessarily true for
every binary operation
(because
must hold by definition of
equality), and so in this sense, set subtraction is as diametrically opposite to being commutative as is possible for a binary operation. Set subtraction is also neither
left alternative nor
right alternative; instead,
if and only if
if and only if
Set subtraction is
quasi-commutative and satisfies the
Jordan identity.
Other identities involving two sets[edit]
Absorption laws:
Other properties
Intervals:
Subsets ⊆ and supersets ⊇[edit]
The following statements are equivalent for any
-
- Definition of subset: if then
- and are disjoint (that is, )
- (that is, )
The following statements are equivalent for any
- There exists some
Set equality[edit]
The following statements are equivalent:
- If then if and only if
- Uniqueness of complements: If then
Empty set[edit]
A set is empty if the sentence is true, where the notation is shorthand for
If is any set then the following are equivalent:
- is not empty, meaning that the sentence is true (literally, the logical negation of " is empty" holds true).
- (In classical mathematics) is inhabited, meaning:
- In constructive mathematics, "not empty" and "inhabited" are not equivalent: every inhabited set is not empty but the converse is not always guaranteed; that is, in constructive mathematics, a set that is not empty (where by definition, " is empty" means that the statement is true) might not have an inhabitant (which is an such that ).
- for some set
If is any set then the following are equivalent:
- is empty (), meaning:
- for every set
- for every set
- for some/every set
Given any
Moreover,
Meets, Joins, and lattice properties[edit]
Inclusion is a partial order: Explicitly, this means that inclusion which is a binary operation, has the following three properties:
- Reflexivity:
- Antisymmetry:
- Transitivity:
The following proposition says that for any set the power set of ordered by inclusion, is a bounded lattice, and hence together with the distributive and complement laws above, show that it is a Boolean algebra.
Existence of a least element and a greatest element:
Joins/supremums exist:
The union is the join/supremum of and with respect to because:
- and and
- if is a set such that and then
The intersection is the join/supremum of and with respect to
Meets/infimums exist:
The intersection is the meet/infimum of and with respect to because:
- if and and
- if is a set such that and then
The union is the meet/infimum of and with respect to
Other inclusion properties:
- If then
- If and then
Three sets involved[edit]
In the left hand sides of the following identities, is the L eft most set, is the M iddle set, and is the R ight most set.
Precedence rules
There is no universal agreement on the order of precedence of the basic set operators. Nevertheless, many authors use precedence rules for set operators, although these rules vary with the author.
One common convention is to associate intersection with logical conjunction (and) and associate union with logical disjunction (or) and then transfer the precedence of these logical operators (where has precedence over ) to these set operators, thereby giving precedence over So for example, would mean since it would be associated with the logical statement and similarly, would mean since it would be associated with
Sometimes, set complement (subtraction) is also associated with logical complement (not) in which case it will have the highest precedence. More specifically, is rewritten so that for example, would mean since it would be rewritten as the logical statement which is equal to For another example, because means which is equal to both and (where was rewritten as ), the formula would refer to the set moreover, since this set is also equal to (other set identities can similarly be deduced from propositional calculus identities in this way). However, because set subtraction is not associative a formula such as would be ambiguous; for this reason, among others, set subtraction is often not assigned any precedence at all.
Symmetric difference is sometimes associated with exclusive or (xor) (also sometimes denoted by ), in which case if the order of precedence from highest to lowest is then the order of precedence (from highest to lowest) for the set operators would be There is no universal agreement on the precedence of exclusive disjunction with respect to the other logical connectives, which is why symmetric difference is not often assigned a precedence.
Associativity[edit]
Definition: A binary operator is called associative if always holds.
The following set operators are associative:
For set subtraction, instead of associativity, only the following is always guaranteed:
where equality holds if and only if
(this condition does not depend on
). Thus
if and only if
where the only difference between the left and right hand side set equalities is that the locations of
have been swapped.
Distributivity[edit]
Definition: If are binary operators then left distributes over if
while
right distributes over if
The operator
distributes over if it both left distributes and right distributes over
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:
Left distributivity:
Distributivity and symmetric difference ∆[edit]
Intersection distributes over symmetric difference:
Union does not distribute over symmetric difference because only the following is guaranteed in general:
Symmetric difference does not distribute over itself:
and in general, for any sets
(where
represents
),
might not be a subset, nor a superset, of
(and the same is true for
).
Distributivity and set subtraction \[edit]
Failure of set subtraction to left distribute:
Set subtraction is right distributive over itself. However, set subtraction is not left distributive over itself because only the following is guaranteed in general:
where equality holds if and only if
which happens if and only if
For symmetric difference, the sets and are always disjoint. So these two sets are equal if and only if they are both equal to Moreover, if and only if
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:
always holds (the equalities on the left and right are De Morgan's laws) but equality is not guaranteed in general (that is, the containment
might be strict). Equality holds if and only if
which happens if and only if
This observation about De Morgan's laws shows that is not left distributive over or because only the following are guaranteed in general:
where equality holds for one (or equivalently, for both) of the above two inclusion formulas if and only if
The following statements are equivalent:
- that is, left distributes over for these three particular sets
- that is, left distributes over for these three particular sets
- and
Quasi-commutativity:
always holds but in general,
However,
if and only if
if and only if
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 and set subtraction is neither associative nor commutative and it also is not left distributive over or even over itself.
Two set subtractions[edit]
Set subtraction is not associative in general:
since only the following is always guaranteed:
(L\M)\R[edit]
L\(M\R)[edit]
- If
- with equality if and only if
One set subtraction[edit]
(L\M) ⁎ R[edit]
Set subtraction on the left, and parentheses on the left