Union-closed families of sets (A problem about induction)

Question

$A$ and $B$ are two sets

If $A,B \in F,$ then $A \cup B \in F$.

Prove by induction that this property applies to a countable number of sets.

If $A_i \in F,i \in \mathbb{N}$, then $ \bigcup_{i\in\mathbb{N}}^{}A_i \in F$.

I understand it, but I don't know how to write down formally using induction.

EDIT: The context is about algebra of events in probability. $ F $ is a non-empty family of subsets of $\Omega $ closed under the union and the complement.

In order $ F $ to be an algebra of events: 1) $F \neq \emptyset $ 2) If $ A \in F $ then the complement of $A \in F$ 3) If $A,B \in F$ then $A \cup B \in F$

The 3rd property can be shown valid for the union of a finite number of events. In this case $F$ is a $\sigma-algebra$

I have to prove that $A_i \in F,i \in \mathbb{N}$, then $ \bigcup_{i\in\mathbb{N}}^{}A_i \in F$ is valid, using the 3rd property $(A,B \in F$ then $A \cup B \in F)$ and induction

EDIT2: I'm adding the following data to make the question more precise. $F \in P(\Omega)$, the power set of the sample space. For example, in an experiment of throwing a dice, the sample set is $ \Omega = \left\{{1,2,3,4,5,6}\right\}$. The power set of the sample space is $2^6$.So there are 64 possible events.$F$ can be the 64 sets or a family of them being a $\sigma$-algebra too. If I am right this a finite union (and countable) with a maximum of 64 sets. From the property "if $A,B \in F,$ then $A \cup B \in F$", how can I prove by induction that for n>2, $\bigcup_{i\in\mathbb{N}}^{}A_i \in F$. Thanks.

Answer 1

There seems to be a bit of confusion in your definitions.

With induction you can easily prove that an algebra of sets is closed under finite unions.

In general an algebra of sets is not closed under countable unions. Here is a simple counterexample. Let $\mathcal{F}$ be the set of finite subsets of $\mathbb{N}$ and complements thereof (the cofinite subsets).

Since the union of two finite subsets is finite, $\mathcal{F}$ is indeed an algebra.

Now consider the sets $A_0=\{0\},A_1=\{0,2\},A_2=\{0,2,4\},\dotsc$ or, with a recursion formula, $$ A_0=\{0\},\qquad A_{n+1}=A_n\cup\{2n+2\}. $$

It is clear that the union of these sets is the set $E$ of even numbers, whose complement is infinite, so $E\notin\mathcal{F}$.

---

Usually, the property of being a $\sigma$-algebra is reserved for algebras of sets that are also closed under countable unions.

An algebra need not be a $\sigma$-algebra, as the above example shows.

So you can't prove the given statement, because it's not generally true in an algebra.

---

Suppose $\mathcal{F}$ is an algebra of subsets of $\Omega$, that is

1. for all $A,B\in\mathcal{F}$, $A\cup B\in\mathcal{F}$;
2. for all $A\in\mathcal{F}$, $\Omega\setminus A\in\mathcal{F}$.

Then $\mathcal{F}$ is closed under finite unions. We'll prove this by induction in the form

if $A_1,A_2,\dots,A_n\in\mathcal{F}$, then $A_1\cup\dots\cup A_n\in\mathcal{F}$

The base of the induction, for $n=1$, is clear. So, suppose the assertion is true for $n-1$, with $n>1$. Then $$ A_1\cup\dots\cup A_{n-1}\cup A_n=(A_1\cup\dots\cup A_{n-1})\cup A_n $$ and, by the induction hypothesis, $B=A_1\cup\dots\cup A_{n-1}\in\mathcal{F}$. Thus, by property 1 of algebras, $B\cup A_n\in\mathcal{F}$.

If the sample space $\Omega$ is finite, also $\mathcal{F}$ is finite, because there are only a finite number of subsets of $\Omega$.

In this case $\mathcal{F}$ is also closed under countable unions: if $A_i$ ($i\in\mathbb{N}$) are elements of $\mathcal{F}$, then at most $k$ of these subsets are distinct. In particular, there will be $n\in\mathbb{N}$ such that, for any $i>n$, $A_i=A_k$, for some $1\le k\le n$. So $$ \bigcup_{i\in\mathbb{N}}A_i=A_1\cup A_2\cup \dots \cup A_n\in\mathcal{F} $$

How to convince yourself of the above statement? You can use an argument similar to Erathostenes' Sieve.

Start from $A_0$ and remove from the given family all elements $A_i$ with $i>0$ and $A_i=A_0$. This will not change the union.

Now, let $i_1$ be the lowest index still appearing in the family and remove all $A_i$ such that $i>i_1$ and $A_i=A_{i_1}$.

Repeat the process. This will eventually end, because we have only a finite number of subsets of $\Omega$ available.

Answer 2

You can't prove that by induction since it's not true. An easy counterexample is all finite subsets of $\mathbb{N}$. For any pair of finite subsets their union is finite, but the countable union is not.

To actually make this more of an answer instead of a comment let me also point out that this is an inherent limitation of "normal" induction as usually taught. Straight in the definition you get that if $P(0)\wedge \forall i\in \mathbb{N}\;(P(i)\implies P(i+1))$ then $\forall i\in \mathbb{N} \;P(i)$. Notice that this only talks about $P(i)$ for $i\in \mathbb{N}$ and since $\omega\not\in \mathbb{N}$ you can't get results about $P(\omega)$.

Edit The fact that your family is an algebra changes nothing about the analysis above. You can have algebras which are not countably closed. If you want a countably closed algebra the basic axioms are not enough. You specifically need to add an axiom requiring that the algebra is closed under countable unions.