The algebra of sets is the study of operations on sets, such as union, intersection, and complementation, together with the identities these operations satisfy. The term also denotes a particular mathematical structure: a nonempty family of subsets of a fixed set that is closed under complements and finite unions. These meanings are closely related: the familiar laws of set operations make every such family a concrete Boolean algebra. Set algebras provide a language for set theory, logic, probability, and measure theory.
Basic operations
Fix a set , called the universe or underlying set, and let . Complements are always taken relative to this specified universe.
The principal operations are:
| Operation | Notation | Definition |
|---|---|---|
| [[set-union | Union]] | |
| [[set-intersection | Intersection]] | |
| Complement | Elements of not belonging to | |
| [[set-difference | Difference]] | |
| [[symmetric-difference | Symmetric difference]] |
Difference and symmetric difference can be expressed using the other operations:
The empty set contains no elements. The universe and the empty set serve as the two distinguished constants in the algebra.
Set difference is not generally commutative:
Symmetric difference, by contrast, is commutative and associative.
Fundamental identities
The laws of set algebra hold for arbitrary subsets .
Commutativity and associativity
Union and intersection are commutative:
They are also associative:
Associativity permits expressions such as without specifying parentheses.
Distributivity
Each operation distributes over the other:
This symmetry is an important distinction from ordinary numerical arithmetic, where multiplication distributes over addition but addition does not generally distribute over multiplication.
Identity, domination, and idempotence
The identity laws are
The domination laws are
Both operations satisfy idempotence:
Complements and absorption
Complementation satisfies
The absorption laws are
De Morgan’s laws describe how complements interchange unions and intersections:
These identities extend to arbitrary indexed families of subsets:
The identities remain valid even when a particular family of sets is not closed under the unions or intersections involved.
Inclusion and duality
The inclusion relation is characterized algebraically by
Inclusion is a partial order. Union gives the least upper bound of two sets, while intersection gives their greatest lower bound.
Many identities occur in dual pairs. Exchanging with and with transforms a valid Boolean identity into another valid identity. The two absorption laws, for example, are dual to each other.
Connection with logic
Set identities can be proved by examining membership of an arbitrary element . The basic correspondences are
Thus union corresponds to disjunction, intersection to conjunction, and complement to negation in classical propositional logic. A set identity can consequently be checked using a truth table for the corresponding logical equivalence.
For example,
This correspondence concerns classical set algebra; changing the underlying logic can change which complement identities are available.
An algebra as a family of sets
An algebra of sets on is a nonempty collection
where is the power set of , satisfying:
- If , then .
- If , then .
These conditions imply
Indeed, choosing any gives , whose complement is .
They also imply closure under finite intersections, differences, and symmetric differences. For example,
An equivalent definition requires and closure under differences and finite unions.
The expression field of sets is another name for this structure. Here “field” does not mean a field in the usual algebraic sense: a field of sets does not generally have multiplicative inverses for its nonzero elements.
Examples
The smallest algebra. For any ,
is an algebra of sets.
The full power set. The collection is an algebra containing every subset of .
Unions of partition blocks. Suppose form a finite partition of : the blocks are nonempty, pairwise disjoint, and have union . All unions of these blocks form an algebra. It has elements.
The finite–cofinite algebra. If is infinite, the family
is an algebra. A set whose complement is finite is called cofinite.
Generated algebras and atoms
Given a family , the algebra generated by is the smallest algebra containing . It exists because the intersection of all algebras on containing is itself an algebra.
Its elements are exactly the sets obtainable from members of using finitely many unions, intersections, and complements.
For finitely many generators , consider the sets
The nonempty sets of this form partition . They are the atoms of the generated algebra: its minimal nonempty members. Every member of the algebra is a unique union of these atoms.
If there are nonempty atoms, the generated algebra has exactly members. Since , an algebra generated by sets has at most
members.
More generally, every finite algebra of sets is the family of all unions of the blocks of a finite partition. Infinite algebras need not have atoms.
Relation to other algebraic structures
Boolean algebras
A set algebra , equipped with
is a Boolean algebra. An abstract Boolean algebra specifies operations satisfying the same identities without requiring its elements to be sets.
Stone’s representation theorem states that every Boolean algebra is isomorphic to an algebra of sets. This concerns preservation of the finite Boolean operations; it does not assert that the representing family is closed under arbitrary unions.
Boolean rings and rings of sets
There is also a ring interpretation:
The zero element is , and, for an algebra on , the multiplicative identity is . Every element satisfies
A ring in which every element is multiplicatively idempotent is called a Boolean ring.
A ring of sets is a nonempty family closed under finite unions and set differences. Unlike an algebra on a specified universe , it need not contain . Every algebra of sets is a ring of sets, but the converse requires the additional condition that belongs to the family.
Finite versus countable closure
An algebra of sets requires closure only under finite unions. A sigma-algebra requires closure under countable unions as well:
Every sigma-algebra is an algebra, but an algebra need not be a sigma-algebra. For example, in the finite–cofinite algebra on the natural numbers, every singleton
belongs to the algebra, but their union is neither finite nor cofinite.
Every finite algebra is a sigma-algebra. Any countable collection drawn from a finite algebra has only finitely many distinct members, so its union reduces to a finite union.
Closure requirements also distinguish set algebras from a topology: a topology requires arbitrary unions and finite intersections, but does not generally require complements.
Probability, measures, and computation
In probability theory, the universe is a sample space and subsets represent events. Union describes the occurrence of at least one event, intersection their joint occurrence, and complement nonoccurrence. Modern probability spaces use sigma-algebras so that countable combinations of events remain measurable.
In measure theory, an algebra often serves as an initial domain for assigning sizes to sets. A nonnegative, countably additive set function on an algebra is a premeasure. Carathéodory’s extension theorem extends a premeasure to a measure on the generated sigma-algebra; under a sigma-finiteness assumption, this extension is unique there. Finite closure of the domain does not by itself imply either finite or countable additivity of a set function.
For computation, subsets of a finite universe can be represented by bit vectors. Union, intersection, and symmetric difference then become bitwise OR, AND, and XOR. Complement becomes bitwise NOT restricted to the positions representing the chosen universe.
The same correspondence is expressed by the indicator function
Pointwise,
Symmetric difference corresponds to addition modulo :