5
$\begingroup$

Let $F = \{E_1, E_2, ..., E_n\}$ be a collection of $n$ subsets of a set $X$, where $n$ is a positive integer. How many distinct sets could there be in $\sigma(F)$?

Here are my thoughts: the largest that $\sigma(F)$ could be would be the power set of $F$, with $2^n$ elements.
This doesn't satisfy me (and is probably wrong!) because a) our prof said that the answer is much larger than $2^n$, and b) this doesn't use the hypothesis about the sets $E_i$ in any way.
How can I begin to wrap my head around this?

  • 1
    @Qiaochu: Even $E_1$ and $E_2$ are disjoint and $n=2$, the answer need not be $2^n=4$. For example, if $X=\{1,2,3\}$, $E_1 = \{1\}$, $E_2=\{2\}$, $\sigma(F)$ contains at least $X$, $\emptyset$, $\{1\}$, $\{2\}$, and $\{1,2\}$, which already gives you 5 elements, more than $2^2$. Here, you have $8$ elements in $\sigma(F)$. If $E_1$ and $E_2$ are disjoint *and* their union is all of $X$, though, then you would be correct that $\sigma(F)$ would have $2^2$ elements.2011-08-31

1 Answers 1

6

For each $x\in X$, consider the function $\chi_x\colon \mathcal{P}(X)\to \{0,1\}$ given by the "membership function"; that is, $\chi_x(E) = 1$ if $x\in E$, and $\chi_x(E)=0$ if $x\notin E$.

Define a relation on $X$ by $x\sim y$ if and only if $\chi_x(E_i)=\chi_y(E_i)$ for $i=1,\ldots,n$. It is easy to see that this is an equivalence relation.

Question. If $x\sim y$, will $\chi_x(E) = \chi_y(E)$ for all $E\in\sigma(F)$?

To see that the answer is "yes", let $M(x,y)\subseteq \mathcal{P}(X)$ be the set of all subsets of $X$ on which $\chi_x$ and $\chi_y$ agree. Clearly, $F\subseteq M(x,y)$. Prove that $M(x,y)$ is a $\sigma$-algebra.

Then show that we can consider the question in $X/\sim$ instead of $X$ (intuitively: if the sets in $F$ cannot distinguish between $x$ and $y$, then neither can the sets in $\sigma(F)$, so you may as well consider $x$ and $y$ "the same point"). This set has at most $2^n$ elements (the possible values of the membership function on $F$). What does that tell you about $\sigma(F)$? Since it is a subset of $\mathcal{P}(X)$, it has at most $2^{2^n}$ elements.

To verify that this is indeed the best you can say, try to construct a set $X$ with $2^n$ elements, and an $F$ with $n$ such that $\sigma(F)$ is all of $\mathcal{P}(X)$. Hint: Take $X=\{0,1,\ldots,2^{n}-1\}$, and think binary expansion.

  • 1
    @The Chaz: If $A$ is a set and $\sim$ is an equivalence relation, then $A/\sim$ is the set of all equivalence classes of $A$ under $\sim$; basically, one element for every equivalence class. It's called the "quotient of $A$ modulo $\sim$. When we go to $X/\sim$, we are reducing the problem to a set $X$ with *at most* $2^n$ elements (it could have fewer).2011-08-31