Why is an algebra not a $\sigma$-algebra by induction?

Question

I am studying probability theory by reading Sidney Resnick's "A Probability Path". On page 12 and 13, algebra and $\sigma$-algebra are defined. The only difference between the two is the third requirement.

• For algebra, it is required that $A, B\in \mathcal A \Rightarrow A\cup B\in \mathcal A.$ That is, algebra is closed under finite union;
• For $\sigma$-algebra, it is required that $B_i\in \mathcal B, i\geq 1 \Rightarrow \bigcup_{i=1}^\infty B_i\in\mathcal B$. That is, $\sigma$-algebra is closed under countable union.

I find the definition for algebra confusing. If the union of $A$ and $B$ is in $\mathcal A$, then for any $C\in\mathcal A$ one has $(A\cup B)\cup C\in \mathcal A$ and so on. Then by induction, this extends to countable union. Why does induction NOT work in this case, please? Thank you!

Answer 1

Take a look at this family of sets: $$\mathcal A=\left\{\left(\frac1n, 1-\frac1n\right), n\in\mathbb N\right\}$$

If you take any two elements $A,B$ from $\mathcal A$, then $A\cup B$ is in $\mathcal A$. However, the union of all elements of $\mathcal A$ is not an element of $\mathcal A$.

Let $A_n = \left(\frac1n, 1-\frac1n\right)$. In a way, you can understand the problem this way: induction is used to prove statements about natural numbers. So, for example, the statement $$\bigcup_{i=1}^4 A_i\in\mathcal A$$ is a statement about the natural number $4$. With induction, you can prove that the statement $$\bigcup_{i=1}^n A_i\in\mathcal A$$ holds for all values of $n\in\mathbb N$. It is a statement in which, when you replace $n$ with some number, say $5$, you get a true statement about that particular number.

The statement you want to prove, however, is $$\bigcup_{i=1}^\infty A_i\in\mathcal A.$$ Unlike the previous statement, this is not a statement about the property of natural numbers. There are no natural numbers that appear in it which you can replace with actual numbers and get a correct statement.

Answer 2

There is a HUGE difference between being true for an arbitrarily large $n$, and being true an infinite set.

For a completely trivial example, you can prove that every subset of the natural numbers is bounded using the same logic, which is clearly nonsense.

To see a basic non-trivial example, consider closed sets in $\Bbb R$. By induction finite unions of closed sets are closed, but it should not be too difficult to come up with a counterexample for the countably infinite case.

Answer 3

There are many counter examples, for example consider the set $M:= \{ A\in\mathbb{R}|A\text{ is closed}\}$, clearly $A\in M,B \in M \implies A\cup B \in M$, but consider $A_i:=[0,1-\frac{1}{i}]$, then $A_i \in M \forall i\in \mathbb{N}$, but $\bigcup_{i\in\mathbb{N}}A_i=[0,1) \notin M$.

Answer 4

You can indeed prove by induction, that in an algebra $\mathcal A$ you have $$ \bigcup_{i=1}^n A_i \in \mathcal A $$ for all $n\in\mathbb N$ and $A_i\in\mathcal A$.

So induction gives you that every finite union, no matter how many sets involved, is again an element of the algebra. Still $\bigcup_{i=1}^\infty A_i$ is not a union of this kind!

Answer 5

The induction step allows you to go from $\bigcup_{i=1}^{n-1}B_i\in\mathcal{B}$ to $$\bigcup_{i=1}^{n-1}B_i\cup B_n=\bigcup_{i=1}^{n}B_i\in\mathcal{B}.$$ The step you would need would be of the form $$\bigcup_{i=1}^{\infty-1}B_i\cup B_\infty=\bigcup_{i=1}^\infty B_i\in\mathcal{B},$$ which is a nonsense expression.

Answer 6

Why does induction not work here? Well, why does it work in the finite case? Suppose it did not work. Then, we have a set $A$ of indices for which the proposition does not hold (in the case at hand: when $k \in A$, $\cup_{i=1}^k B_i\not\in\mathcal B$ in general).

By the well-ordering principle, $A$ has a least element (call it $\ell$). Thus, the proposition does hold for $n=\ell-1$. Proof by induction means you show that if the proposition holds for $n$, it must also hold for $n+1$. Therefore, if it holds for $\ell-1$, it holds for $\ell$ as well. But this is a contradiction, since $\ell$ is the first value of $n$ where the proposition does not hold.

This proves induction (in the finite case). If we try the same proof for the countably infinite case, we first have to define $A$ in a sensible way. This cannot be done via natural numbers since $\infty$ is not a natural number, so $A$ would be empty. One can use the concept of ordinal numbers, but $\omega_0$ does not have a predecessor (i.e. $\infty-1$ does not exist), so the usual step from $n$ to $n+1$ is not sufficient to reach a contradiction to $\omega_0$ being the first element of $A$.

The method of proof by induction can be extended to work in this case also (transfinite induction), but extra work is required to deal with limit ordinals (i.e. those that do not have a predecessor).

Needless to say, this extra work would fail in the case at hand since there are counter-examples.