Why Disjoint Refinements Matter
A finite cover may be easy to describe but contain substantial overlap. In measure arguments, overlap prevents us from adding the sizes of the covering sets directly. A semiring supplies exactly the operation needed to remove that overlap: the difference of two of its sets can be expressed as finitely many disjoint sets that remain in the semiring. Repeating that operation in a fixed order converts a finite cover into disjoint pieces without changing its union.
All statements here concern a set \(X\) and a family \(\mathcal{S}\) of subsets of \(X\); no measure, finiteness of a measure space, or measurability assumption is needed. A finite family is allowed to contain empty sets or repetitions. Empty pieces in a resulting refinement may be omitted.
The difference axiom does not say that \(A\setminus B\) is itself in \(\mathcal{S}\). Nor does it say that the semiring is closed under arbitrary finite unions. The construction below uses only intersections and the stated finite disjoint decomposition of differences.
Subtracting Several Sets
The basic step is to handle a set after subtracting a finite union. The pieces produced at each stage must remain disjoint: otherwise the next subtraction would not give a disjoint refinement of the original difference.
Proof. We use induction on \(r\). If \(r=0\), the single piece \(A\in\mathcal{S}\) gives the result. Suppose it holds for \(r\), and write \(A\setminus\bigcup_{j=1}^{r}B_j=\bigcup_{k=1}^{q}C_k\), where \(C_1,\ldots,C_q\in\mathcal{S}\) are pairwise disjoint; \(q=0\) is allowed. Then \[ A\setminus\bigcup_{j=1}^{r+1}B_j =\left(A\setminus\bigcup_{j=1}^{r}B_j\right)\setminus B_{r+1} =\bigcup_{k=1}^{q}(C_k\setminus B_{r+1}). \] For each \(k\), the semiring difference axiom expresses \(C_k\setminus B_{r+1}\) as a finite union of pairwise disjoint members of \(\mathcal{S}\). Pieces arising from different \(k\)'s are also disjoint, since each lies inside its corresponding \(C_k\), and the \(C_k\)'s are disjoint. Combining all these finite families proves the induction step. \(\square\)
This lemma addresses one set minus many sets. To disjointify a finite family, apply it to each set after removing all earlier sets in the chosen order.
Proof. For each \(i\in\{1,\ldots,n\}\), use the lemma to write \[ D_i:=A_i\setminus\bigcup_{j<i}A_j \] as a finite union of pairwise disjoint members of \(\mathcal{S}\). For \(i=1\), the union being subtracted is empty, so \(D_1=A_1\). Pieces from a single \(D_i\) are disjoint by the lemma. If \(i<k\), every piece from \(D_i\) is contained in \(A_i\), while every piece from \(D_k\) is contained in \(D_k\subseteq X\setminus A_i\). Thus pieces from different indices are disjoint as well. Each piece lies in some \(A_i\), so their union is contained in \(\bigcup_i A_i\). Conversely, if \(x\in\bigcup_i A_i\), let \(i\) be the least index for which \(x\in A_i\). Then \(x\notin A_j\) for every \(j<i\), so \(x\in D_i\), and hence belongs to one of its pieces. This proves the reverse containment and the theorem. \(\square\)
In a cover of a set \(E\in\mathcal{S}\), where \(E\subseteq\bigcup_i A_i\), first replace each covering set \(A_i\) by \(E\cap A_i\). These intersections belong to \(\mathcal{S}\), cover \(E\), and are subsets of \(E\). Applying the theorem gives a disjoint semiring refinement of the cover of \(E\). This version makes explicit which original set each piece refines.
Worked Refinements
Worked Example: A Cover by Half-Open Intervals
Take \(X=\mathbb{R}\) and let \(\mathcal{S}\) consist of the empty set and all bounded half-open intervals \([a,b)\) with \(a\le b\). These sets form a semiring: intersections are empty or half-open intervals, and the difference of two such intervals is empty, one interval, or the union of at most two disjoint half-open intervals. Disjointify \(A_1=[0,2)\), \(A_2=[1,4)\), and \(A_3=[3,5)\), in that order.
The first set contributes \(D_1=A_1=[0,2)\). For the second set, the overlap with \(A_1\) is \([1,2)\), so \[ D_2=A_2\setminus A_1=[1,4)\setminus[0,2)=[2,4). \] The union of the first two sets is \([0,4)\). Therefore \[ D_3=A_3\setminus(A_1\cup A_2)=[3,5)\setminus[0,4)=[4,5). \] The refined pieces are \([0,2)\), \([2,4)\), and \([4,5)\). They are disjoint, and their union is \([0,5)\), which is also the union of the original three intervals.
Check: The boundary point \(2\) is excluded from \([0,2)\) and included in \([2,4)\); the point \(4\) is excluded from \([2,4)\) and included in \([4,5)\). Thus no endpoint is lost or counted twice.
Worked Example: A Cover with a Gap Before the Last Set
Use the same interval semiring and order the sets as \(A_1=[0,1)\), \(A_2=[2,3)\), and \(A_3=[1/2,5/2)\). The first two are already disjoint, so \(D_1=[0,1)\) and \(D_2=[2,3)\). Their union is \([0,1)\cup[2,3)\). Removing both intervals from the third gives \[ D_3=[1/2,5/2)\setminus\bigl([0,1)\cup[2,3)\bigr)=[1,2). \] Indeed, the portion from \(1/2\) up to but not including \(1\) has already been covered by \(A_1\), and the portion from \(2\) up to but not including \(5/2\) has already been covered by \(A_2\).
The disjoint refinement is \([0,1)\), \([2,3)\), and \([1,2)\). Its union is \([0,3)\), the same as the union of the original family. The ordering explains why the new piece \([1,2)\) comes from \(A_3\), even though the pieces can be listed in increasing spatial order as \([0,1)\), \([1,2)\), \([2,3)\).
Check: The point \(1\) is in \(D_3\), not \(D_1\); the point \(2\) is in \(D_2\), not \(D_3\). Both original intervals and refined pieces use the half-open convention, so these endpoint assignments agree exactly.
Worked Example: A Cover by Half-Open Rectangles
In \(X=\mathbb{R}^2\), consider the semiring of empty sets and bounded half-open rectangles \([a,b)\times[c,d)\), with \(a\le b\) and \(c\le d\). Intersections are empty or rectangles. For differences, split a rectangle along the coordinate boundaries of its intersection with the rectangle being removed; the resulting finite grid cells are half-open rectangles, and the cells outside the intersection give a disjoint decomposition. Now take \[ A_1=[0,2)\times[0,2),\quad A_2=[1,3)\times[1,3),\quad A_3=[2,3)\times[0,2). \]
The first contribution is \(D_1=A_1\). The intersection \(A_2\cap A_1\) is \([1,2)\times[1,2)\). Removing it from \(A_2\) leaves two disjoint rectangles: \[ D_2=\bigl([2,3)\times[1,3)\bigr)\ \cup\ \bigl([1,2)\times[2,3)\bigr). \] For the third set, \(A_3\cap A_1=\varnothing\), because the first coordinate of \(A_3\) begins at \(2\), which \(A_1\) excludes. Also \(A_3\cap A_2=[2,3)\times[1,2)\). Hence \[ D_3=A_3\setminus(A_1\cup A_2)=[2,3)\times[0,1). \]
The full refinement consists of \(A_1\) and the three rectangles displayed in \(D_2\) and \(D_3\). They are pairwise disjoint: the two pieces of \(D_2\) meet only at the excluded boundary \(y=2\); the \(D_3\) piece has \(y<1\), whereas the first piece of \(D_2\) has \(y\ge1\), and its second piece has \(y\ge2\). The pieces of \(D_2\) and \(D_3\) have first coordinate at least \(2\), while \(A_1\) has first coordinate less than \(2\).
Check: The point \((2,0)\) belongs to \(A_3\) and to its refined piece \([2,3)\times[0,1)\). The point \((2,1)\) belongs to \(A_2\) and to \([2,3)\times[1,3)\), not to the \(D_3\) piece. This verifies the boundary assignments at the split \(y=1\).
Common Mistakes and the Finite Scope
A frequent error is to treat a semiring as if it were closed under set difference. For example, in the half-open interval semiring, \[ [0,3)\setminus[1,2)=[0,1)\cup[2,3), \] which is not one half-open interval. The correction is to keep both disjoint semiring pieces; replacing their union by a single interval would incorrectly put the points in \([1,2)\) back into the difference.
A second error is to subtract only one earlier set when more than one has already appeared. In the second interval example, subtracting \(A_1\) from \(A_3\) alone gives \([1,5/2)\), which still overlaps \(A_2=[2,3)\) on \([2,5/2)\). The correct construction subtracts the entire earlier union \(A_1\cup A_2\), giving \([1,2)\). The lemma ensures this subtraction can still be carried out using finitely many semiring pieces.
The result is specifically finite. Its proof repeatedly uses the finite-difference axiom a finite number of times and produces a finite family. It does not assert that subtracting countably many semiring sets gives a finite semiring decomposition, nor that countable covers can be disjointified by this finite procedure. When the pieces are later used with a set function, disjointness permits finite additivity to be applied to the refinement; the set-theoretic argument itself requires no assumptions about such a function.
Check Your Understanding
In each question, retain the stated ordering of the cover sets and use half-open endpoint conventions.
- For \(A_1=[0,1)\), \(A_2=[1/2,3/2)\), \(A_3=[1,2)\), find each set \(D_i=A_i\setminus\bigcup_{j<i}A_j\) and verify their union.
- Explain why the semiring difference axiom does not imply that \(A\setminus B\) is always a single member of the semiring.
- In the rectangle example, which refined piece contains the point \((2,2)\), and why does it belong to no other piece?
- State the induction step that proves a set minus a finite union is a finite disjoint union of semiring sets.
- If \(E\in\mathcal{S}\) is covered by \(A_1,\ldots,A_n\in\mathcal{S}\), which sets should be disjointified to obtain pieces contained in \(E\)?