Algebra of sets

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.

Fundamentals

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\}}$.

Union and intersection

The algebra of sets studies the properties and laws of sets algebraically. Foundationally, there are two set-theoretic operations: union (⁠${\displaystyle \cup }$⁠) and intersection (⁠${\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. 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.

Empty set, universe set, and the complement of a set

Two additional pairs of properties involve the special sets called the empty set ⁠${\displaystyle \varnothing }$⁠ and the universe set ⁠${\displaystyle \mathit{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^{\prime }}$⁠ (read as "A prime"). Equivalently, the complement of a set ${\displaystyle A^{\complement }}$ is a set that is included in a universe set ⁠${\displaystyle \mathit{U}}$⁠ and not in ${\displaystyle A}$; i.e., ⁠${\displaystyle A^{\complement }=\mathit{U}\setminus A}$⁠.

Identity

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

Complement

• ⁠${\displaystyle A\cup A^{\complement }=\mathit{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 \mathit{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.