This exercise if taken from Probability: An Introduction by Grimmett and Welsh. In what follows, $\Omega$ is a set and $\mathcal{F}$ is an event space of subsets of $\Omega$ (that is, $\mathcal{F}$ is a collection of subsets of $\Omega$ which is non-empty, and is closed under both complements and countable unions). At this stage we know that $\mathcal{F}$ is also closed under intersection, difference and symmetric difference.

If $A_{1},A_{2},\ldots,A_{m}\in\mathcal{F}$ and $k$ is a positive integer, show that the set of points of $\Omega$ which belong to exactly $k$ of the $A$'s belongs to $\mathcal{F}$.

I've tried to come up with some kind of inductive approach (given the set for one value of $k$, construct the set for the next value of $k$ and show that it's in $\mathcal{F}$), but this didn't seem fruitful.

What would be ideal is to say something along the lines of "all the relevant sets can be constructed using union, intersection, difference and symmetric difference, so we are done by previous results". Unfortunately, what exactly "all the relevant sets" are and precisely why they can be constructed this way is not clear to me.

Is there some operation or combination of operations $f$ which makes the following work? I don't think symmetric difference works. If not, can anyone provide suggestions for more fruitful approaches?

For each $k$-subset $I$ of $\{1,2,\ldots,m\}$, let $B(I) = \bigcap_{i\in I} A_{i}$. It follows that, for each $k$-subset $I$ of $\{1,2,\ldots,m\}$, we have $B(I)\in\mathcal{F}$. Letting $\mathcal{B} = \{B(I):I\text{ is a $k$-subset of $\{1,2,\ldots,m\}$}\}$, it follows that $f(\mathcal{B})\in\mathcal{F}$. But $f(\mathcal{B})$ is precisely the set of points of $\Omega$ which belong to exactly $k$ of the $A$'s, so we are done.


I think it is more handsome here to use induction on $m$.

Denote the set by $B_k(A_1,\dots,A_m)$.

Actually you can write: $$B_k\left(A_{1},\dots,A_{m}\right)=\left\{ x\in\Omega\mid1_{A_{1}}\left(x\right)+\cdots+1_{A_{m}}\left(x\right)=k\right\}$$

Working out the equality: $$B_k\left(A_{1},\dots,A_{m}\right)=\left(B_k\left(A_{1},\dots,A_{m}\right)\cap A_{m}\right)\cup\left(B_k\left(A_{1},\dots,A_{m}\right)\cap A_{m}^{c}\right)$$ we arrive at:

$$B_k(A_1,\dots,A_m)=(B_{k-1}(A_1,\dots,A_{m-1})\cap A_m)\cup(B_{k}(A_1,\dots,A_{m-1})\cap A_m^c)$$

The induction step can be made on base of this equality.

Note that also $f:=1_{A_1}+\cdots+1_{A_m}$ can be shown to be a function that is measurable with respect to $\mathcal F$. This on base of the rule: if $g,h:\Omega\to\mathbb R$ are measurable then $g+h$ is measurable.

From this it can be concluded directly that $B_k(A_1,\dots,A_m)=f^{-1}(\{k\})\in\mathcal F$.

| cite | improve this answer | |
  • $\begingroup$ If I'm not mistaken, the way to interpret your equation is as follows: to find the set of points in $k$ of the sets $A_{1},\ldots,A_{m}$, first take the points in $k-1$ of the sets $A_{1},\ldots,A_{m-1}$ and intersect that with $A_{m}$ (what you have so far is a set of points in $k$ of the sets), and throw in the points in exactly $k$ of the sets $A_{1},\ldots,A_{m-1}$ and exclude those which are also in $A_{m}$ (this ensures we don't double count, and clearly must account for all of the remaining points we seek). I don't think I would have thought about it that way. $\endgroup$ – Will R Jan 31 '16 at 17:27
  • $\begingroup$ To your edit: what do you mean by $B$ (no subscript)? Are you using this notation as a placeholder, meaning "I'll just put this here until I figure out what actually goes here"? $\endgroup$ – Will R Jan 31 '16 at 19:11
  • $\begingroup$ I just forgot the subscript. Sorry for that, and thanks for attending me. It is repaired now. $\endgroup$ – drhab Jan 31 '16 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.