Algebra of sets

In mathematics, particularly in the study of set theory, the algebra of sets^a defines the properties and laws of sets, 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.

Any set of sets closed under the set-theoretic operations forms a Boolean algebra with the join operator being union, the meet operator being intersection, the complement operator being set complement,¹ the bottom being ⁠${\displaystyle \varnothing }$⁠ and the top being the universe set under consideration.

A set is a collection of many mathematical objects. Examples of such objects are numbers, symbols, points in space, lines, other geometric shapes, variables, functions, or even other sets.² A set is usually denote a upper-case letter and curly braces, as in ${\displaystyle A=\{1,2,3,4\}}$ and ${\displaystyle B=\{a,b,c,x,y,z\}}$.

The algebra of sets studies the properties and laws of sets algebraically. Foundationally, there are two set-theoretic operations of union (⁠${\displaystyle \cup }$⁠), intersection and (⁠${\displaystyle \cap }$⁠). A union is a set-theoretic operation that collects all members of two or more sets into a single set. An intersection collects the common elements of two or more sets. For instance, let ${\displaystyle A=\{1,2,3,5\}}$ and ${\displaystyle B=\{2,4,6\}}$. Then ${\displaystyle A\cup B=\{1,2,3,4,5,6\}}$, ${\displaystyle A\cap B=\{2\}}$. Analogically, the algebra of sets can be interpreted as the algebra of numbers. Just as arithmetic addition and multiplication are associative and commutative, so are set union and intersection.^3b Similarly for the arithmetic relation "less than or equal" is reflexive, antisymmetric and transitive, so is the set relation of "subset".⁴ Several of these identities or "laws" are the following.⁵

Commutative property

• ⁠${\displaystyle A\cup B=B\cup A}$⁠
• ⁠${\displaystyle A\cap B=B\cap A}$⁠

Associative property

• ⁠${\displaystyle (A\cup B)\cup C=A\cup (B\cup C)}$⁠
• ⁠${\displaystyle (A\cap B)\cap C=A\cap (B\cap C)}$⁠

Distributive property

• ⁠${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)}$⁠
• ⁠${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$⁠

The union and intersection of sets may be seen as analogous to the addition and multiplication of numbers. Like addition and multiplication, the operations of union and intersection are commutative and associative, and intersection distributes over union.³ However, unlike addition and multiplication, union also distributes over intersection.

Two additional pairs of properties involve the special sets called the empty set ⁠${\displaystyle \varnothing }$⁠ and the universe set ⁠${\displaystyle {\boldsymbol {U}}}$⁠. These sets have no members, and the universe set has all possible members (in a particular context), respectively. A set where the members are not in a set ${\displaystyle A}$ is the complement; the operator denotes ⁠${\displaystyle A^{\complement }}$⁠ or ⁠${\displaystyle A'}$⁠ (read as "A prime"). Equivalently, the complement of a set ${\displaystyle A^{\complement }}$ is a set that is included in a universe set ⁠${\displaystyle {\boldsymbol {U}}}$⁠ and not in ${\displaystyle A}$; i.e., ⁠${\displaystyle A^{\complement }={\boldsymbol {U}}\setminus A}$⁠.⁶

Identity

• ⁠${\displaystyle A\cup \varnothing =A}$⁠
• ⁠${\displaystyle A\cap {\boldsymbol {U}}=A}$⁠

Complement

• ⁠${\displaystyle A\cup A^{\complement }={\boldsymbol {U}}}$⁠
• ⁠${\displaystyle A\cap A^{\complement }=\varnothing }$⁠

The identity expressions (together with the commutative expressions) say that, just like 0 and 1 for addition and multiplication,⁷ ⁠${\displaystyle \varnothing }$⁠ and ⁠${\displaystyle {\boldsymbol {U}}}$⁠ are the identity elements for union and intersection, respectively.

Unlike addition and multiplication, union and intersection do not have inverse elements. However, the complement laws give the fundamental properties of the somewhat inverse-like unary operation of set complementation.

The preceding five pairs of formulae—the commutative, associative, distributive, identity, and complement formulae—encompass all of set algebra, in the sense that every valid proposition in the algebra of sets can be derived from them.

If the complement formulae are weakened to the rule ⁠${\displaystyle (A^{\complement })^{\complement }=A}$⁠, then this is exactly the algebra of propositional linear logic.

Each of the identities stated above is one of a pair of identities such that each can be transformed into the other by interchanging ⁠${\displaystyle \cup }$⁠ and ⁠${\displaystyle \cap }$⁠, while also interchanging ⁠${\displaystyle \varnothing }$⁠ and ⁠${\displaystyle {\boldsymbol {U}}}$⁠.

These are examples of an extremely important and powerful property of set algebra, namely, the principle of duality for sets, which asserts that for any true statement about sets, the dual statement obtained by interchanging unions and intersections, interchanging ⁠${\displaystyle {\boldsymbol {U}}}$⁠ and ⁠${\displaystyle \varnothing }$⁠ and reversing inclusions is also true. A statement is said to be self-dual if it is equal to its own dual.

For any subsets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠ of a universe set ⁠${\displaystyle {\boldsymbol {U}}}$⁠, the following identities hold:

idempotent laws

• ⁠${\displaystyle A\cup A=A}$⁠^{proof 1}
• ⁠${\displaystyle A\cap A=A}$⁠^{proof 2}

domination laws

• ⁠${\displaystyle A\cup {\boldsymbol {U}}={\boldsymbol {U}}}$⁠
• ⁠${\displaystyle A\cap \varnothing =\varnothing }$⁠

absorption laws

• ⁠${\displaystyle A\cup (A\cap B)=A}$⁠^{proof 3}
• ⁠${\displaystyle A\cap (A\cup B)=A}$⁠^{proof 4}

Intersection can be expressed in terms of set difference:

⁠${\displaystyle A\cap B=A\setminus (A\setminus B)}$⁠

Let ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠ be subsets of a universe ⁠${\displaystyle {\boldsymbol {U}}}$⁠, then:

de Morgan's laws

• ⁠${\displaystyle (A\cup B)^{\complement }=A^{\complement }\cap B^{\complement }}$⁠
• ⁠${\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }}$⁠

double complement or involution law

• ⁠${\displaystyle (A^{\complement })^{\complement }=A}$⁠

complement laws for the universe set and the empty set

• ⁠${\displaystyle \varnothing ^{\complement }={\boldsymbol {U}}}$⁠
• ⁠${\displaystyle {\boldsymbol {U}}^{\complement }=\varnothing }$⁠

Notice that the double complement law is self-dual. The following is also self-dual, saying that the complement of a set is the only set that satisfies the complement laws. In other words, complementation is characterized by the complement laws: Let ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠ be subsets of a universe ⁠${\displaystyle {\boldsymbol {U}}}$⁠,

uniqueness of complements

• If ⁠${\displaystyle A\cup B={\boldsymbol {U}}}$⁠, and ⁠${\displaystyle A\cap B=\varnothing }$⁠, then ⁠${\displaystyle B=A^{\complement }}$⁠

The algebra of sets include the inclusion of sets. That is, the binary relation of one set being a subset of another, which is a partial order. If ⁠${\displaystyle A}$⁠, ⁠${\displaystyle B}$⁠ and ⁠${\displaystyle C}$⁠ are sets then the following hold:

reflexivity

• ⁠${\displaystyle A\subseteq A}$⁠

antisymmetry

• ⁠${\displaystyle A\subseteq B}$⁠ and ⁠${\displaystyle B\subseteq A}$⁠ if and only if ⁠${\displaystyle A=B}$⁠

transitivity

• If ⁠${\displaystyle A\subseteq B}$⁠ and ⁠${\displaystyle B\subseteq C}$⁠, then ⁠${\displaystyle A\subseteq C}$⁠

For any set ⁠${\displaystyle S}$⁠, the power set of ⁠${\displaystyle S}$⁠, ordered by inclusion, is a bounded lattice, and hence together with the distributive and complement laws above, shows that it is a Boolean algebra. That is, if ⁠${\displaystyle A}$⁠, ⁠${\displaystyle B}$⁠ and ⁠${\displaystyle C}$⁠ are subsets of a set ⁠${\displaystyle S}$⁠ then the following hold:

existence of a least element and a greatest element

• ⁠${\displaystyle \varnothing \subseteq A\subseteq S}$⁠

existence of joins

• ⁠${\displaystyle A\subseteq A\cup B}$⁠

• If ⁠${\displaystyle A\subseteq C}$⁠ and ⁠${\displaystyle B\subseteq C}$⁠, then ⁠${\displaystyle A\cup B\subseteq C}$⁠

existence of meets

• ⁠${\displaystyle A\cap B\subseteq A}$⁠
• If ⁠${\displaystyle C\subseteq A}$⁠ and ⁠${\displaystyle C\subseteq B}$⁠, then ⁠${\displaystyle C\subseteq A\cap B}$⁠

The inclusion set ⁠${\displaystyle A\subseteq B}$⁠ is equivalent to various other statements involving unions, intersections, and complements. That is, for any two sets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠, the following are equivalent:

• ⁠${\displaystyle A\subseteq B}$⁠
• ⁠${\displaystyle A\cap B=A}$⁠
• ⁠${\displaystyle A\cup B=B}$⁠
• ⁠${\displaystyle A\setminus B=\varnothing }$⁠
• ⁠${\displaystyle B^{\complement }\subseteq A^{\complement }}$⁠

This shows that the relation of set inclusion can be characterized by either of the operations of set union or set intersection, meaning that the notion of set inclusion is axiomatically superfluous.

The following proposition lists several identities concerning relative complements and set-theoretic differences.

PROPOSITION 9: For any universe ⁠${\displaystyle {\boldsymbol {U}}}$⁠ and subsets ⁠${\displaystyle A}$⁠, ⁠${\displaystyle B}$⁠ and ⁠${\displaystyle C}$⁠ of ⁠${\displaystyle {\boldsymbol {U}}}$⁠, the following identities hold:

• ⁠${\displaystyle C\setminus (A\cap B)=(C\setminus A)\cup (C\setminus B)}$⁠
• ⁠${\displaystyle C\setminus (A\cup B)=(C\setminus A)\cap (C\setminus B)}$⁠
• ⁠${\displaystyle C\setminus (B\setminus A)=(A\cap C)\cup (C\setminus B)}$⁠
• ⁠${\displaystyle (B\setminus A)\cap C=(B\cap C)\setminus (A\cap C)=(B\cap C)\setminus A=B\cap (C\setminus A)}$⁠
• ⁠${\displaystyle (B\setminus A)\cup C=(B\cup C)\setminus (A\setminus C)}$⁠
• ⁠${\displaystyle (B\setminus A)\setminus C=B\setminus (A\cup C)}$⁠
• ⁠${\displaystyle A\setminus A=\varnothing }$⁠
• ⁠${\displaystyle \varnothing \setminus A=\varnothing }$⁠
• ⁠${\displaystyle A\setminus \varnothing =A}$⁠
• ⁠${\displaystyle B\setminus A=A^{\complement }\cap B}$⁠
• ⁠${\displaystyle (B\setminus A)^{\complement }=A\cup B^{\complement }}$⁠
• ⁠${\displaystyle {\boldsymbol {U}}\setminus A=A^{\complement }}$⁠
• ⁠${\displaystyle A\setminus {\boldsymbol {U}}=\varnothing }$⁠