Product Sigma-Algebras on Discrete Spaces

Discrete Spaces and Their Product Sigma-Algebras

A set equipped with its power-set sigma-algebra treats every subset as measurable. This makes individual discrete spaces straightforward, but products require care: the product sigma-algebra is generated by measurable rectangles, and it need not contain every subset of the Cartesian product. The distinction is especially important when the underlying sets are uncountable.

Throughout, a discrete measurable space means a measurable space \((S,\mathcal{P}(S))\), where \(\mathcal{P}(S)\) is the set of all subsets of \(S\). For discrete spaces \((S_i,\mathcal{P}(S_i))\), \(1\le i\le n\), their product sigma-algebra is \(\bigotimes_{i=1}^n\mathcal{P}(S_i)=\sigma\{A_1\times\cdots\times A_n:A_i\subseteq S_i\}\). No measure is assigned here: the question is which subsets belong to this sigma-algebra. A set is countable in this tutorial if it is finite or countably infinite.

Proof. First suppose one of \(S_1,\ldots,S_n\) is empty. The product is empty, and both sigma-algebras on it consist only of the empty set. Otherwise, the finite Cartesian product of countable sets is countable. For any point \(x=(x_1,\ldots,x_n)\) in that product, its singleton is the measurable rectangle \(\{x_1\}\times\cdots\times\{x_n\}\). Every subset \(E\) of the product is a countable union of such singletons, so it belongs to the product sigma-algebra. The reverse inclusion holds because the product sigma-algebra consists of subsets of the product.

For the two-factor assertion, suppose \(S\) is countable; the case where \(T\) is countable follows by reversing the factors. If \(E\subseteq S\times T\), define its row \(E_s=\{t\in T:(s,t)\in E\}\) for each \(s\in S\). Then \(E=\bigcup_{s\in S}(\{s\}\times E_s)\). Each term is a measurable rectangle, and the union is countable, so \(E\in\mathcal{P}(S)\otimes\mathcal{P}(T)\). Again, every member of that product sigma-algebra is a subset of \(S\times T\), giving equality. \(\square\)

Countable Factors in Two-Factor Products

The row decomposition in the proposition uses a feature specific to two factors: after fixing a point in the countable factor, the remaining row is an arbitrary subset of the other factor, and is itself available as a measurable set. Thus there is no restriction on how complicated the rows are, even when the other underlying set is uncountable.

For three or more factors, one countable factor alone does not give the same conclusion. Grouping the other factors into one set does not solve the issue: their natural sigma-algebra is their product sigma-algebra, which may be smaller than the power set of their Cartesian product. The next example makes this obstruction explicit.

Why a Countable Factor Is Not Enough in Longer Products

Proof. We first record why any member \(G\) of \(\mathcal{P}(U)\otimes\mathcal{P}(U)\) is generated by only countably many rectangles. Let \(\mathcal{R}\) be the family of all rectangles in \(U\times U\), and consider the family of sets belonging to \(\sigma(\mathcal{R}_0)\) for some countable subfamily \(\mathcal{R}_0\subseteq\mathcal{R}\). This family contains every rectangle. It is closed under complements, since a complement remains in the same sigma-algebra. It is closed under countable unions: for a sequence of sets, take the union of their respective countable rectangle subfamilies, which is countable. Thus this family is a sigma-algebra containing \(\mathcal{R}\), and every \(G\in\sigma(\mathcal{R})\) belongs to \(\sigma(\mathcal{R}_0)\) for some countable \(\mathcal{R}_0\).

Suppose, for contradiction, that \(\Delta_U\) is product-measurable. Choose countably many rectangles \(A_k\times B_k\), \(k\ge1\), that generate a sigma-algebra containing \(\Delta_U\); a finite family can be padded by empty rectangles. Define the membership signature \(\alpha(A)=(\chi_{A_k}(A))_{k\ge1}\) for \(A\in U\), where \(\chi_{A_k}(A)\) is \(1\) if \(A\in A_k\) and \(0\) otherwise. If \(\alpha(A)=\alpha(A')\), then for every fixed \(C\in U\), the pairs \((A,C)\) and \((A',C)\) belong to exactly the same generating rectangles: membership in \(A_k\times B_k\) requires both \(A\in A_k\) and \(C\in B_k\). The class of subsets of \(U\times U\) that cannot distinguish these two pairs is a sigma-algebra, since it is closed under complements and countable unions. Consequently every set in \(\sigma\{A_k\times B_k:k\ge1\}\) cannot distinguish them either.

If distinct \(A,A'\in U\) had the same signature, choose \(C=A\). Then \((A,A)\in\Delta_U\) but \((A',A)\notin\Delta_U\), contradicting the preceding indistinguishability. Therefore \(\alpha\) would have to be injective from \(U\) into \(\{0,1\}^{\mathbb{N}}\), a set of cardinality \(2^{\aleph_0}=|\mathbb{R}|\). But \(U=\mathcal{P}(\mathbb{R})\) has strictly larger cardinality than \(\mathbb{R}\), by Cantor's theorem. This contradiction proves that \(\Delta_U\) is not product-measurable. \(\square\)

A Common Misstep and the Practical Test

A tempting but invalid argument is: “One factor is countable, so group all other factors into one set and apply the two-factor proposition.” The proposition requires that the grouped factor have its full power-set sigma-algebra. In the example above, grouping the last two factors gives the measurable space \((U\times U,\mathcal{P}(U)\otimes\mathcal{P}(U))\), not \((U\times U,\mathcal{P}(U\times U))\). The diagonal is precisely a subset missing from that product sigma-algebra.

The correct conclusions to use are limited but useful:

• If the entire finite Cartesian product is countable, its product sigma-algebra is the full power set.
• For two factors, if either underlying set is countable, the product sigma-algebra is the full power set.
• For three or more factors, a countable factor by itself does not imply that every subset is product-measurable.

When assessing a particular subset in a longer product, write it as a countable union or combination of measurable rectangles only when that construction is justified. A finite or countable decomposition into slices works for two factors with a countable coordinate; grouping several coordinates requires checking their sigma-algebra rather than silently replacing it by a power set.