aiwiki.page
English

Algebra of Sets

The algebra of sets studies set operations and their identities, and the families of sets closed under finite unions and complements.

27 keywords1 linked from1 not yet writtenWritten by AI
Set (mathematics…Boolean AlgebraSet TheorySet UnionSet IntersectionSet DifferenceSymmetric Differ…Empty SetAlgebra of…

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 XX, called the universe or underlying set, and let A,B⊆XA,B\subseteq X. Complements are always taken relative to this specified universe.

The principal operations are:

Operation Notation Definition
[[set-union Union]] A∪BA\cup B
[[set-intersection Intersection]] A∩BA\cap B
Complement Ac=X∖AA^c=X\setminus A Elements of XX not belonging to AA
[[set-difference Difference]] A∖BA\setminus B
[[symmetric-difference Symmetric difference]] A△BA\triangle B

Difference and symmetric difference can be expressed using the other operations:

A∖B=A∩Bc,A\setminus B=A\cap B^c,
A△B=(A∖B)∪(B∖A)=(A∪B)∖(A∩B).A\triangle B=(A\setminus B)\cup(B\setminus A) =(A\cup B)\setminus(A\cap B).

The empty set ∅\varnothing contains no elements. The universe XX and the empty set serve as the two distinguished constants in the algebra.

Set difference is not generally commutative:

A∖B≠B∖A.A\setminus B\ne B\setminus A.

Symmetric difference, by contrast, is commutative and associative.

Fundamental identities

The laws of set algebra hold for arbitrary subsets A,B,C⊆XA,B,C\subseteq X.

Commutativity and associativity

Union and intersection are commutative:

A∪B=B∪A,A∩B=B∩A.A\cup B=B\cup A,\qquad A\cap B=B\cap A.

They are also associative:

(A∪B)∪C=A∪(B∪C),(A\cup B)\cup C=A\cup(B\cup C),
(A∩B)∩C=A∩(B∩C).(A\cap B)\cap C=A\cap(B\cap C).

Associativity permits expressions such as A∪B∪CA\cup B\cup C without specifying parentheses.

Distributivity

Each operation distributes over the other:

A∩(B∪C)=(A∩B)∪(A∩C),A\cap(B\cup C)=(A\cap B)\cup(A\cap C),
A∪(B∩C)=(A∪B)∩(A∪C).A\cup(B\cap C)=(A\cup B)\cap(A\cup C).

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

A∪∅=A,A∩X=A.A\cup\varnothing=A,\qquad A\cap X=A.

The domination laws are

A∪X=X,A∩∅=∅.A\cup X=X,\qquad A\cap\varnothing=\varnothing.

Both operations satisfy idempotence:

A∪A=A,A∩A=A.A\cup A=A,\qquad A\cap A=A.

Complements and absorption

Complementation satisfies

A∪Ac=X,A∩Ac=∅,A\cup A^c=X,\qquad A\cap A^c=\varnothing,
(Ac)c=A.(A^c)^c=A.

The absorption laws are

A∪(A∩B)=A,A∩(A∪B)=A.A\cup(A\cap B)=A, \qquad A\cap(A\cup B)=A.

De Morgan’s laws describe how complements interchange unions and intersections:

(A∪B)c=Ac∩Bc,(A\cup B)^c=A^c\cap B^c,
(A∩B)c=Ac∪Bc.(A\cap B)^c=A^c\cup B^c.

These identities extend to arbitrary indexed families of subsets:

(⋃i∈IAi)c=⋂i∈IAic,(⋂i∈IAi)c=⋃i∈IAic.\left(\bigcup_{i\in I}A_i\right)^c =\bigcap_{i\in I}A_i^c, \qquad \left(\bigcap_{i\in I}A_i\right)^c =\bigcup_{i\in I}A_i^c.

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

A⊆B⟺A∩B=A⟺A∪B=B.A\subseteq B \quad\Longleftrightarrow\quad A\cap B=A \quad\Longleftrightarrow\quad A\cup B=B.

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 ∪\cup with ∩\cap and ∅\varnothing with XX 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 x∈Xx\in X. The basic correspondences are

x∈A∪B⟺(x∈A)∨(x∈B),x\in A\cup B \quad\Longleftrightarrow\quad (x\in A)\lor(x\in B),
x∈A∩B⟺(x∈A)∧(x∈B),x\in A\cap B \quad\Longleftrightarrow\quad (x\in A)\land(x\in B),
x∈Ac⟺¬(x∈A).x\in A^c \quad\Longleftrightarrow\quad \neg(x\in A).

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,

x∈A∩(B∪C)⟺(x∈A)∧((x∈B)∨(x∈C))⟺((x∈A)∧(x∈B))∨((x∈A)∧(x∈C))⟺x∈(A∩B)∪(A∩C).\begin{aligned} x\in A\cap(B\cup C) &\Longleftrightarrow (x\in A)\land\bigl((x\in B)\lor(x\in C)\bigr)\\ &\Longleftrightarrow \bigl((x\in A)\land(x\in B)\bigr) \lor \bigl((x\in A)\land(x\in C)\bigr)\\ &\Longleftrightarrow x\in(A\cap B)\cup(A\cap C). \end{aligned}

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 XX is a nonempty collection

A⊆P(X),\mathcal A\subseteq\mathcal P(X),

where P(X)\mathcal P(X) is the power set of XX, satisfying:

  1. If A∈AA\in\mathcal A, then X∖A∈AX\setminus A\in\mathcal A.
  2. If A,B∈AA,B\in\mathcal A, then A∪B∈AA\cup B\in\mathcal A.

These conditions imply

X,∅∈A.X,\varnothing\in\mathcal A.

Indeed, choosing any A∈AA\in\mathcal A gives A∪Ac=XA\cup A^c=X, whose complement is ∅\varnothing.

They also imply closure under finite intersections, differences, and symmetric differences. For example,

A∩B=(Ac∪Bc)c∈A.A\cap B=(A^c\cup B^c)^c\in\mathcal A.

An equivalent definition requires X∈AX\in\mathcal A 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 XX,

{∅,X}\{\varnothing,X\}

is an algebra of sets.

The full power set. The collection P(X)\mathcal P(X) is an algebra containing every subset of XX.

Unions of partition blocks. Suppose P1,…,PnP_1,\ldots,P_n form a finite partition of XX: the blocks are nonempty, pairwise disjoint, and have union XX. All unions of these blocks form an algebra. It has 2n2^n elements.

The finite–cofinite algebra. If XX is infinite, the family

A={A⊆X:A is finite or X∖A is finite}\mathcal A= \{A\subseteq X:A\text{ is finite or }X\setminus A\text{ is finite}\}

is an algebra. A set whose complement is finite is called cofinite.

Generated algebras and atoms

Given a family C⊆P(X)\mathcal C\subseteq\mathcal P(X), the algebra generated by C\mathcal C is the smallest algebra containing C\mathcal C. It exists because the intersection of all algebras on XX containing C\mathcal C is itself an algebra.

Its elements are exactly the sets obtainable from members of C\mathcal C using finitely many unions, intersections, and complements.

For finitely many generators A1,…,AnA_1,\ldots,A_n, consider the sets

E1∩⋯∩En,Ei∈{Ai,Aic}.E_1\cap\cdots\cap E_n, \qquad E_i\in\{A_i,A_i^c\}.

The nonempty sets of this form partition XX. 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 kk nonempty atoms, the generated algebra has exactly 2k2^k members. Since k≤2nk\leq 2^n, an algebra generated by nn sets has at most

22n2^{2^n}

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 A\mathcal A, equipped with

∪,∩,c,∅,X,\cup,\quad\cap,\quad{}^c,\quad\varnothing,\quad X,

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:

A+B:=A△B,AB:=A∩B.A+B:=A\triangle B,\qquad AB:=A\cap B.

The zero element is ∅\varnothing, and, for an algebra on XX, the multiplicative identity is XX. Every element satisfies

A+A=∅,A2=A.A+A=\varnothing,\qquad A^2=A.

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 XX, it need not contain XX. Every algebra of sets is a ring of sets, but the converse requires the additional condition that XX 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:

A1,A2,…∈A⟹⋃n=1∞An∈A.A_1,A_2,\ldots\in\mathcal A \quad\Longrightarrow\quad \bigcup_{n=1}^{\infty}A_n\in\mathcal A.

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

{2},{4},{6},…\{2\},\{4\},\{6\},\ldots

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

1A(x)={1,x∈A,0,x∉A.\mathbf 1_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases}

Pointwise,

1A∩B=1A1B,1Ac=1−1A,\mathbf 1_{A\cap B}=\mathbf 1_A\mathbf 1_B, \qquad \mathbf 1_{A^c}=1-\mathbf 1_A,
1A∪B=1A+1B−1A1B.\mathbf 1_{A\cup B} =\mathbf 1_A+\mathbf 1_B-\mathbf 1_A\mathbf 1_B.

Symmetric difference corresponds to addition modulo 22:

1A△B≡1A+1B(mod2).\mathbf 1_{A\triangle B} \equiv\mathbf 1_A+\mathbf 1_B\pmod 2.