To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

List of set identities and relations

From Wikipedia, the free encyclopedia

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.

YouTube Encyclopedic

  • 1/5
    Views:
    31 573
    19 388
    736
    61 662
    44 342
  • Discrete Math - 2.2.2 Set Identities
  • Discrete Math 2.2.2 Set Identities
  • Set Identities in Discrete Math
  • Discrete Math 2.2.3 Proving Set Identities
  • Discrete Math - 2.1.2 Set Relationships

Transcription

Notation

Throughout this article, capital letters such as and will denote sets and will denote the power set 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)

Typically, the set will denote the L eft most set, the M iddle set, and the R ight most set.

For sets and define:

and
where the symmetric difference is sometimes denoted by and equals:[1][2]
If is a set that is understood (say from context, or because it is clearly stated) to be a subset of some other set then the complement of a set may be denoted by:
The definition of may depend 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

Finitely many sets

One subset involved

Assume

Identity:[3]

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[3] and Nilpotence :

Domination[3]/Zero element:

but
so

Double complement or involution law:

[3]

[3]

Two sets involved

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 ∆

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

De Morgan's laws state that for

Commutativity

Unions, intersection, and symmetric difference are commutative operations:[3]

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

Absorption laws:

Other properties

Intervals:

Subsets ⊆ and supersets ⊇

The following statements are equivalent for any [3]

  1. (that is, )

The following statements are equivalent for any

  1. There exists some

Set equality

The following statements are equivalent:

  • If then if and only if
  • Uniqueness of complements: If then
Empty set

A set is empty if the sentence is true, where the notation is shorthand for

If is any set then the following are equivalent:

  1. is not empty, meaning that the sentence is true (literally, the logical negation of " is empty" holds true).
  2. (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 ).
  3. for some set

If is any set then the following are equivalent:

  1. is empty (), meaning:
  2. for every set
  3. for every set
  4. for some/every set

Given any

Moreover,

Meets, Joins, and lattice properties

Inclusion is a partial order: Explicitly, this means that inclusion which is a binary operation, has the following three properties:[3]

  • 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:[3]

The union is the join/supremum of and with respect to because:

  1. and and
  2. if is a set such that and then

The intersection is the join/supremum of and with respect to

Meets/infimums exist:[3]

The intersection is the meet/infimum of and with respect to because:

  1. if and and
  2. 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 [3]

Three sets involved

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

Definition: A binary operator is called associative if always holds.

The following set operators are associative:[3]

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

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:[3]

Left distributivity:[3]

Distributivity and symmetric difference ∆

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 \

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 in general but equality is not guaranteed. 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:

  1. that is, left distributes over for these three particular sets
  2. that is, left distributes over for these three particular sets
  3. 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

Set subtraction is not associative in general:

since only the following is always guaranteed:
(L\M)\R

L\(M\R)

  • If
  • with equality if and only if

One set subtraction

(L\M) ⁎ R

Set subtraction on the left, and parentheses on the left

[4]

L\(M ⁎ R)

Set subtraction on the left, and parentheses on the right

where the above two sets that are the subjects of De Morgan's laws always satisfy

(L ⁎ M)\R

Set subtraction on the right, and parentheses on the left

L ⁎ (M\R)

Set subtraction on the right, and parentheses on the right

[4]

Three operations on three sets

(L • M) ⁎ (M • R)

Operations of the form :

(L • M) ⁎ (R\M)

Operations of the form :

(L\M) ⁎ (L\R)

Operations of the form :

Other simplifications

Other properties:

  • If then [4]
  • If then
  • if and only if for any belongs to at most two of the sets

Cartesian products ⨯ of finitely many sets

Binary ⋂ of finite ⨯

Binary ⋃ of finite ⨯

Difference \ of finite ⨯

and

Finite ⨯ of differences \

Symmetric difference ∆ and finite ⨯

In general, need not be a subset nor a superset of

Arbitrary families of sets

Let and be indexed families of sets. Whenever the assumption is needed, then all indexing sets, such as and are assumed to be non-empty.

Definitions

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

An indexed family of sets is a function from some set, called its indexing set, into some family of sets. An indexed family of sets will be denoted by where this notation assigns the symbol for the indexing set and for every index assigns the symbol to the value of the function at The function itself may then be denoted by the symbol which is obtained from the notation by replacing the index with a bullet symbol explicitly, is the function:

which may be summarized by writing

Any given indexed family of sets (which is a function) can be canonically associated with its image/range (which is a family of sets). Conversely, any given family of sets may be associated with the -indexed family of sets which is technically the identity map However, this is not a bijective correspondence because an indexed family of sets is not required to be injective (that is, there may exist distinct indices such as ), 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[3]

 

 

 

 

(Def. 1)

If then which is somethings called the nullary union convention (despite being called a convention, this equality follows from the definition).

If is a family of sets then denotes the set:

Arbitrary intersections defined

If then[3]

 

 

 

 

(Def. 2)

If is a non-empty family of sets then denotes the set:

Nullary intersections

If then

where every possible thing in the universe vacuously satisfied the condition: "if then ". Consequently, consists of everything in the universe.

So if and:

  1. if you are working in a model in which there exists some universe set then
  2. otherwise, if you are working in a model in which "the class of all things " is not a set (by far the most common situation) then is undefined because consists of everything, which makes a proper class and not a set.
Assumption: Henceforth, whenever a formula requires some indexing set to be non-empty in order for an arbitrary intersection to be well-defined, then this will automatically be assumed without mention.

A consequence of this is the following assumption/definition:

A finite intersection of sets or an intersection of finitely many sets refers to the intersection of a finite collection of one or more sets.

Some authors adopt the so called nullary intersection convention, which is the convention that an empty intersection of sets is equal to some canonical set. In particular, if all sets are subsets of some set then some author may declare that the empty intersection of these sets be equal to 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 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

Distributing unions and intersections

Binary ⋂ of arbitrary ⋃'s

 

 

 

 

(Eq. 3a)

and[4]

 

 

 

 

(Eq. 3b)

  • If all are pairwise disjoint and all are also pairwise disjoint, then so are all (that is, if then ).

  • Importantly, if then in general,
    (an example of this is given below). The single union on the right hand side must be over all pairs
    The same is usually true for other similar non-trivial set equalities and relations that depend on two (potentially unrelated) indexing sets and (such as Eq. 4b or Eq. 7g[4]). Two exceptions are Eq. 2c (unions of unions) and Eq. 2d (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.[note 1]
  • Example where equality fails: Let and let Let and let Then
    Furthermore,

Binary ⋃ of arbitrary ⋂'s

 

 

 

 

(Eq. 4a)

and[4]

 

 

 

 

(Eq. 4b)

  • Importantly, if then in general,
    (an example of this is given above). The single intersection on the right hand side must be over all pairs

Arbitrary ⋂'s and arbitrary ⋃'s

Incorrectly distributing by swapping ⋂ and ⋃

Naively swapping and may produce a different set

The following inclusion always holds:

 

 

 

 

(Inclusion 1 ∪∩ is a subset of ∩∪)

In general, equality need not hold and moreover, the right hand side depends on how for each fixed the sets are labelled; and analogously, the left hand side depends on how for each fixed the sets are labelled. An example demonstrating this is now given.

  • Example of dependence on labeling and failure of equality: To see why equality need not hold when and are swapped, let and let and Then
    If and are swapped while and are unchanged, which gives rise to the sets and then
    In particular, the left hand side is no longer which shows that the left hand side depends on how the sets are labelled. If instead and are swapped while and are unchanged, which gives rise to the sets and then both the left hand side and right hand side are equal to which shows that the right hand side also depends on how the sets are labeled.

Equality in Inclusion 1 ∪∩ is a subset of ∩∪ can hold under certain circumstances, such as in 7e, which is the special case where is (that is, with the same indexing sets and ), or such as in 7f, which is the special case where is (that is, with the indexing sets and swapped). For a correct formula that extends the distributive laws, an approach other than just switching and is needed.

Correct distributive laws

Suppose that for each is a non-empty index set and for each let be any set (for example, to apply this law to use for all and use for all and all ). Let

denote the Cartesian product, which can be interpreted as the set of all functions such that for every Such a function may also be denoted using the tuple notation where for every and conversely, a tuple is just notation for the function with domain whose value at is both notations can be used to denote the elements of Then

 

 

 

 

(Eq. 5 ∩∪ to ∪∩)

 

 

 

 

(Eq. 6 ∪∩ to ∩∪)

where

Applying the distributive laws

Example application: In the particular case where all are equal (that is, for all which is the case with the family for example), then letting denote this common set, the Cartesian product will be which is the set of all functions of the form The above set equalities Eq. 5 ∩∪ to ∪∩ and Eq. 6 ∪∩ to ∩∪, respectively become:[3]

which when combined with Inclusion 1 ∪∩ is a subset of ∩∪ implies:

where
  • on the left hand side, the indices range over (so the subscripts of range over )
  • on the right hand side, the indices range over (so the subscripts of range over ).


Example application: To apply the general formula to the case of and use and let for all and let for all Every map can be bijectively identified with the pair (the inverse sends to the map defined by and this is technically just a change of notation). Recall that Eq. 5 ∩∪ to ∪∩ was

Expanding and simplifying the left hand side gives
and doing the same to the right hand side gives:

Thus the general identity Eq. 5 ∩∪ to ∪∩ reduces down to the previously given set equality Eq. 3b:

Distributing subtraction over ⋃ and ⋂

 

 

 

 

(Eq. 7a)

 

 

 

 

(Eq. 7b)

The next identities are known as De Morgan's laws.[4]

 

 

 

 

(Eq. 7c)

 

 

 

 

(Eq. 7d)

The following four set equalities can be deduced from the equalities 7a - 7d above.

 

 

 

 

(Eq. 7e)

 

 

 

 

(Eq. 7f)

 

 

 

 

(Eq. 7g)

 

 

 

 

(Eq. 7h)

In general, naively swapping and may produce a different set (see this note for more details). The equalities

found in Eq. 7e and Eq. 7f are thus unusual in that they state exactly that swapping and will not change the resulting set.

Commutativity and associativity of ⋃ and ⋂

Commutativity:[3]

Unions of unions and intersections of intersections:[3]

and[3]

 

 

 

 

(Eq. 2a)

 

 

 

 

(Eq. 2b)

and if then also:[note 1][3]

 

 

 

 

(Eq. 2c)

 

 

 

 

(Eq. 2d)

Cartesian products Π of arbitrarily many sets

Intersections ⋂ of Π

If is a family of sets then

 

 

 

 

(Eq. 8)

  • Moreover, a tuple belongs to the set in Eq. 8 above if and only if for all and all

In particular, if and are two families indexed by the same set then

So for instance,
and

Intersections of products indexed by different sets

Let and be two families indexed by different sets.

Technically, implies However, sometimes these products are somehow identified as the same set through some bijection or one of these products is identified as a subset of the other via some injective map, in which case (by abuse of notation) this intersection may be equal to some other (possibly non-empty) set.

  • For example, if and with all sets equal to then and where unless, for example, is identified as a subset of through some injection, such as maybe for instance; however, in this particular case the product actually represents the -indexed product where
  • For another example, take and with and all equal to Then and which can both be identified as the same set via the bijection that sends to Under this identification,

Unions ⋃ of Π

For unions, only the following is guaranteed in general:

where is a family of sets.

However,

Difference \ of Π

If and are two families of sets then:

so for instance,
and

Symmetric difference ∆ of Π

Functions and sets

Let be any function.

Let be completely arbitrary sets. Assume

Definitions

Let be any function, where we denote its domain by and denote its codomain by

Many of the identities below do not actually require that the sets be somehow related to 's domain or codomain (that is, to or ) so when some kind of relationship is necessary then it will be clearly indicated. Because of this, in this article, if is declared to be "any set," and it is not indicated that must be somehow related to or (say for instance, that it be a subset or ) then it is meant that is truly arbitrary.[note 2] This generality is useful in situations where is a map between two subsets and of some larger sets and and where the set might not be entirely contained in and/or (e.g. if all that is known about is that ); in such a situation it may be useful to know what can and cannot be said about and/or without having to introduce a (potentially unnecessary) intersection such as: and/or

Images and preimages of sets

If is any set then the image of under is defined to be the set:

while the preimage of under is:
where if is a singleton set then the filber or preimage of under is

Denote by or the image or range of which is the set:

Saturated sets

A set is said to be -saturated or a saturated set if any of the following equivalent conditions are satisfied:

  1. There exists a set such that
    • Any such set necessarily contains as a subset.
  2. and
    • The inclusion always holds, where if then this becomes

For a set to be -saturated, it is necessary that

Compositions and restrictions of functions

If