How many algebras are there of finite-sized $\Omega$?

An algebra of $\Omega$ is a family that contains $\Omega,$ is closed under complement and finite union.

If $\Omega=\{\}$, there can only be 1 algebra associated with $\Omega$: $2^{\Omega}.$

If $\Omega=\{1\}$, there can only be 1 algebra associated with $\Omega$: $2^\Omega$.

If $\Omega=\{1,2\}$, there are 2 possible algebras: $2^\Omega, \{\Omega,\varnothing\}.$

If $\Omega=\{1,2,3\},$ there are 5 possible algebras: $2^\Omega,\{\Omega,\varnothing\},\{\Omega,\varnothing,\{1\},\{2,3\}\},\{\Omega,\varnothing,\{2\},\{1,3\}\},\{\Omega,\varnothing,\{3\},\{1,2\}\}.$

If $\Omega=\{1,2,3,4\},$ there are 15 possible algebras: $2^\Omega, \{\{1,2,3,4\}, \{\}\}, \{\{1,2,3,4\}, \{\}, \{1\}, \{2,3,4\}\}, \{\{1,2,3,4\}, \{\}, \{2\}, \{1,3,4\}\}, \{\{1,2,3,4\}, \{\}, \{3\}, \{1,2,4\}\}, \{\{1,2,3,4\}, \{\}, \{4\}, \{1,2,3\}\}, \{\{1,2,3,4\}, \{\}, \{1,2\}, \{3,4\}\}, \{\{1,2,3,4\}, \{\}, \{1,3\}, \{2,4\}\}, \{\{1,2,3,4\}, \{\}, \{1,4\}, \{2,3\}\}, \{\{1,2,3,4\}, \{\}, \{1\}, \{2\}, \{1,2\}, \{3,4\}, \{2,3,4\}, \{1,3,4\}\}, \{\{1,2,3,4\}, \{\}, \{1\}, \{3\}, \{1,3\}, \{2,4\}, \{1,2,4\}, \{2,3,4\}\}, \{\{1,2,3,4\}, \{\}, \{1\}, \{4\}, \{1,4\}, \{2,3\}, \{1,2,3\}, \{2,3,4\}\}, \{\{1,2,3,4\}, \{\}, \{2\}, \{3\}, \{2,3\}, \{1,4\}, \{1,2,4\}, \{1,3,4\}\}, \{\{1,2,3,4\}, \{\}, \{2\}, \{4\}, \{2,4\}, \{1,3\}, \{1,2,3\}, \{1,3,4\}\}, \{\{1,2,3,4\}, \{\}, \{3\}, \{4\}, \{3,4\}, \{1,2\}, \{1,2,3\}, \{1,2,4\}\}.$

How many algebras of $\Omega$ are there if $\Omega$ is of size $n$? The first few terms look like 'Bell Numbers' (OEIS A000110). Is it the same?

1 Answer

The number of such "algebras of subsets" of a given set $\Omega$ is the number of (set) partitions of $\Omega$, and the number of partitions is given by the Bell numbers.

To see this, note that for any such algebra $\mathcal{A}$ of subsets, we can define an equivalence relation $\sim$ on the elements of $\Omega$ such that $x \sim y$ iff they always occur together: whenever $x$ occurs in some element of $\mathcal{A}$ so does $y$, and vice-versa. (Thus $\mathcal{A}$ "doesn't distinguish" betwen $x$ and $y$.) This equivalence relation defines a partition on $\Omega$. (In other words, if you define $\displaystyle A_x = \cap_{S \in \mathcal{A}, x \in S} S$, then $x \sim y$ iff $A_x = A_y$. The sets $A_x$ constitute the partition.)

Thus each algebra $\mathcal{A}$ defines a unique partition on $\Omega$. This part is true even if $\mathcal{A}$ isn't an algebra; just any arbitrary family of subsets of $\Omega$. But to prove that this map is a bijection, i.e., that two different $\mathcal{A}$ cannot define the same partition, we need to use the properties of $\mathcal{A}$ being an algebra.

Namely, $\mathcal{A}$ must contain all unions of sets $A_x$ (if there are $m$ such $A_x$, then all $2^m$ of them), because it is closed under unions. And these are the only sets it contains, which can prove as follows: let $S$ be a nonempty set in $\mathcal{A}$. Then $S$ must intersect at least some $A_x$ (because their union is all of $\Omega$). Then as $\mathcal{A}$ is closed under intersections, $S \cap A_x$ is in $\mathcal{A}$, so for any $y$ in $S \cap A_x$, we must have $A_y \subseteq (S \cap A_x)$ by definition, but also $A_y = A_x$ as $y \in A_x$. So for every $A_x$ which $S$ intersects, $S \cap A_x = A_x$, which means that $S$ is a union of the sets $A_x$.

Thus the partition uniquely defines the algebra $\mathcal{A}$, which means that the number of algebras of subsets of a given set $\Omega$ is precisely the number of set partitions of $\Omega$, which is given by the Bell number $B_n$ where $n = |\Omega|$.