finite fields of sets

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

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

$\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 $ℱ$ as follows:

$$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 suggestive mnemonic of how the only divisors of a prime number are 1 and the number itself.

We claim that $P$ is a partition. To justify this claim, we need to show 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 field of sets, $A\cap B\in ℱ$. Since $A\cap B\subset A$, we must either have $A\cap B=\mathrm{\varnothing }$ or $A\cap B=A$. In the former 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 $ℱ$ is finite and, since fields of sets are assumed to be closed under intersection, 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$, it is 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 arbitrarily chosen, this means that every element of $S$ is contained in a prime element of $ℱ$, so the union of all prime elements is $S$ itself. Together with the previously shown fact that prime elements are pairwise disjoint, this shows that the prime elements for a partition 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 of elements of $P$.

Title	finite fields of sets
Canonical name	FiniteFieldsOfSets
Date of creation	2013-03-22 15:47:49
Last modified on	2013-03-22 15:47:49
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	8
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 28A05
Classification	msc 03E20