PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] finite fields of sets (Theorem)

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 \begin{eqnarray*} \overline{\bigcup A} &=& \bigcup (P \setminus A) \\ (\bigcup A) \cup (\bigcup B) &=& \bigcup (A \cup B) \\ (\bigcup A) \cap (\bigcup B) &=& \bigcup (A \cap B) \\ \end{eqnarray*}so $\{ \bigcup X \mid X \subset P \}$ is a field of sets.

Now assume that $\mathcal{F}$ is a field of subsets of a finite set $S$ Let us define the set of ``prime elements'' of $\mathcal{F}$ as follows: $$P = \{ X \in (\mathcal{F} \setminus {\varnothing}) \mid (Y \subset X) \wedge (Y \in \mathcal{F}) \Rightarrow (Y = \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 \mathcal{F}$ and $B \in \mathcal{F}$ and $\mathcal{F}$ is a field of sets, $A \cap B \in \mathcal{F}$ Since $A \cap B \subset A$ we must either have $A \cap B = \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 \mathcal F \mid x \in Y \} $$ is a prime element of $\mathcal{F}$ To begin, note that, since $\mathcal{F}$ is finite, a forteriori any subset of $\mathcal{F}$ is finite and, since fields of sets are assumed to be closed under intersection, it follows that the intersection of a susbet of $\mathcal{F}$ is an element of $\mathcal{F}$ in particular $X \in \mathcal{F}$

Suppose that $Z \subset X$ and $Z \in \mathcal{F}$ If $x \notin Z$ then $x \in \overline{Z}$ Since $\mathcal{F}$ is a field of sets, $\overline{Z} \in \mathcal{F}$ Hence, by the construction of $X$ it is the case that $X \subset \overline{Z}$ hence $X \cap Z = \varnothing$ Together with $Z \subset X$ this implies $Z = \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 $\mathcal{F}$ 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 $\mathcal{F}$ Since $P \subset \mathcal{F}$ it is the case that $(\forall X \in P) A \cap X \in \mathcal{F}$ Since $P$ is a partition of $S$ $$ A = \bigcup \{ A \cap X \mid X \in P \} $$ so every element of $\mathcal{F}$ can be expressed as a union of elements of $P$




"finite fields of sets" is owned by rspuzio.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: contained, implies, intersection, closed under, finite, disjoint, prime elements, pairwise disjoint, number, prime number, divisors, mnemonic, field of sets, partition, unions, rings of sets, subsets, field, finite set

This is version 5 of finite fields of sets, born on 2006-03-22, modified 2006-10-10.
Object id is 7758, canonical name is FiniteFieldsOfSets.
Accessed 1039 times total.

Classification:
AMS MSC28A05 (Measure and integration :: Classical measure theory :: Classes of sets , measurable sets, Suslin sets, analytic sets)
 03E20 (Mathematical logic and foundations :: Set theory :: Other classical set theory )

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)