finite fields of sets

If $S$ is a finite set then any field of subsets of $S$ (see “field ofsets” in the entry on rings of sets) can be described as the set of unionsof subsets of a partition of $S$.

Note that, if $P$ is a partition of $S$ and $A,B\subset P$, wehave

$\overline{{\displaystyle \bigcup A}}$$=$${\displaystyle \bigcup (P\setminus A)}$

$({\displaystyle \bigcup A})\cup ({\displaystyle \bigcup B})$$=$${\displaystyle \bigcup (A\cup B)}$

$({\displaystyle \bigcup A})\cap ({\displaystyle \bigcup B})$$=$${\displaystyle \bigcup (A\cap B)}$

so $\{\bigcup X\mid X\subset P\}$ is a field of sets.

Now assume that $ℱ$ is a field of subsets of a finite set$S$. Let us define the set of “prime elements” of $ℱ$ asfollows:

$$P=\{X\in (ℱ\setminus \mathrm{\varnothing })\mid (Y\subset X)\wedge (Y\in ℱ)\Rightarrow (Y=\mathrm{\varnothing }\vee Y=X)\}$$

The choice of terminology “prime element” is meant to be a suggestivemnemonic of how the only divisors of a prime number are 1 and thenumber itself.

We claim that $P$ is a partition. To justify this claim, we need toshow that elements of $P$ are pairwise disjoint and that $\bigcup P=S$.

Suppose that $A$ and $B$ are prime elements. Since, by definition, $A\in ℱ$ and $B\in ℱ$ and $ℱ$ is a fieldof sets, $A\cap B\in ℱ$. Since $A\cap B\subset A$, wemust either have $A\cap B=\mathrm{\varnothing }$ or $A\cap B=A$. In theformer case, $A$ and $B$ are disjoint, whilst in the latter case $A=B$.

Suppose that $x$ is any element of $S$. Then we claim that the set$X$ defined as

$$X=\bigcup \{Y\in ℱ\mid x\in Y\}$$

is a prime element of $ℱ$. To begin, note that, since$ℱ$ is finite, a forteriori any subset of $ℱ$ isfinite and, since fields of sets are assumed to be closed underintersection, it follows that the intersection of a susbet of$ℱ$ is an element of $ℱ$, in particular $X\in ℱ$.

Suppose that $Z\subset X$ and $Z\in ℱ$. If $x\notin Z$,then $x\in \overline{Z}$. Since $ℱ$ is a field of sets,$\overline{Z}\in ℱ$. Hence, by the construction of $X$, itis the case that $X\subset \overline{Z}$, hence $X\cap Z=\mathrm{\varnothing }$. Together with $Z\subset X$, this implies $Z=\mathrm{\varnothing }$. If $x\in Z$, then, by construction, $X\subset Z$,which implies $X=Z$.

Thus, we see that $X$ is a prime set. Since $x$ was arbitrarilychosen, this means that every element of $S$ is contained in a primeelement of $ℱ$, so the union of all prime elements is $S$itself. Together with the previously shown fact that prime elementsare pairwise disjoint, this shows that the prime elements for apartition of $S$.

Let $A$ be an arbitrary element of $ℱ$. Since $P\subset ℱ$, it is the case that $(\forall X\in P)A\cap X\in ℱ$. Since $P$ is a partition of $S$,

$$A=\bigcup \{A\cap X\mid X\in P\}$$

so every element of $ℱ$ can be expressed as a union ofelements of $P$.