finite fields of sets

If S is a finite setMathworldPlanetmath 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 partitionPlanetmathPlanetmath of S.

Note that, if P is a partition of S and A,BP, we have

A¯ = (PA)
(A)(B) = (AB)
(A)(B) = (AB)

so {XXP} 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:


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 P=S.

Suppose that A and B are prime elements. Since, by definition, A and B and is a field of sets, AB. Since ABA, we must either have AB= or AB=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


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 intersectionMathworldPlanetmathPlanetmath, it follows that the intersection of a susbet of is an element of , in particular X.

Suppose that ZX and Z. If xZ, then xZ¯. Since is a field of sets, Z¯. Hence, by the construction of X, it is the case that XZ¯, hence XZ=. Together with ZX, this implies Z=. If xZ, then, by construction, XZ, 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, it is the case that (XP)AX. Since P is a partition of S,


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