Proof by induction in sets

[TheMathNoob]

Homework Statement

Let A1,A 2,...be an infinite sequence of events such that A1⊂A2⊂... Prove that

Pr(∪A_i)=lim_n→infPr(A_n)

∪ is also an iterator that starts from i=1 to infinity. How can you put those iterators?[/B]

Homework Equations

I decided to use induction

The Attempt at a Solution

Proof by induction

Base case

let A₁⊂A₂[/B]
so A₁∪A₂=A₂
Therefore Pr(A₁∪A₂)=Pr(A₂)

Inductive Step

let Pr(∪A_i)=lim_k→infPr(A_k)
then we have to show that if A_k⊂A_k+1 then lim_k→infPr(A_k∪A_k+1)=lim_k→infPr(A_k+1)

so

This is true because A_k∪A_k+1=A_k+1
so lim_k→infPr(A_k∪A_k+1)=lim_k→infPr(A_k+1)

so by math induction Pr(∪A_i)=lim_n→infPr(A_n)

is that right?

 

[Fredrik]

Hit the Reply button to see the LaTeX code I used to produce this: $\bigcup_{i=1}^\infty A_i$.

Induction is useful when you want to prove a statement of the form $\forall n~ P(n)$, where P(n) is a statement about the integer n. The idea is that instead of proving P(1), P(2), and so on (a process that would never be finished), you can just prove the two statements $P(1)$ and $\forall n~ P(n)\Rightarrow P(n+1)$. If you want to use induction, the first thing you need to do is to identify the statement P(n). This isn't possible here, since the theorem you want to prove doesn't contain a statement about an integer.

So induction isn't the way to go here. I would use the fact that Pr is a measure and that measures are countably additive. Do you know how to rewrite a union as a union of disjoint sets? I'm sure you've seen $E\cup F=E\cup(F-E)$, but do you know how to rewrite $\bigcup_{i=1}^\infty A_i$ as a union of disjoint sets?

 

[Ray Vickson]

Homework Statement

Let A1,A 2,...be an infinite sequence of events such that A1⊂A2⊂... Prove that

Pr(∪A_i)=lim_n→infPr(A_n)

∪ is also an iterator that starts from i=1 to infinity. How can you put those iterators?[/B]

Homework Equations

I decided to use induction

The Attempt at a Solution

Proof by induction

Base case

let A₁⊂A₂[/B]
so A₁∪A₂=A₂
Therefore Pr(A₁∪A₂)=Pr(A₂)

Inductive Step

let Pr(∪A_i)=lim_k→infPr(A_k)
then we have to show that if A_k⊂A_k+1 then lim_k→infPr(A_k∪A_k+1)=lim_k→infPr(A_k+1)

so

This is true because A_k∪A_k+1=A_k+1
so lim_k→infPr(A_k∪A_k+1)=lim_k→infPr(A_k+1)

so by math induction Pr(∪A_i)=lim_n→infPr(A_n)

is that right?

No, it is not right. All you can get from your method is that $\lim_{n \to \infty} P(A_n) \leq P(\cup_{i=1}^{\infty} A_i)$. To actually prove equality takes some subtlety; it follows from "countable additivity" ( $P(\cup_i A_i) = \sum_i P(A_i)$ for infinitely many disjoint $A_i$ ), but not from just finite additivity ( $P(\cup_i A_i) = \sum_i P(A_i)$ for finitely many disjoint $A_i$ ). Some treatments of probability even use axioms consisting of finite additivity plus the statement you are trying to prove; from that you can prove countable additivity.

The property you are attempting to prove is known as "continuity of probability".

 

[andrewkirk]

∪ is also an iterator that starts from i=1 to infinity. How can you put those iterators?

Since Fredrik and Ray have answered your main question, I'll take the liberty of replying to your ancillary question, which is the above.

The formal interpretation of $\bigcup_{i=1}^\infty A_i$ is as follows.

First, for it to make sense at all, we need a set $\mathscr{C}$, which we can think of as a 'collection' of sets, and a function $f:\mathbb{N}\to\mathscr{C}$, which is our 'indexing' function. We denote $f(i)$ by $A_i$, which is the $i$th set in collection $\mathscr{C}$.
We also need a master set that is a superset of all the $A_i$. That is, we need a set $M$ with the property that $\forall i\in\mathbb{N}:\, A_i\subseteq M$.

With these formalities completed, we can define

$$\bigcup_{i=1}^\infty A_i\equiv \{x\in M|\exists i\in\mathbb{N}:\,x\in A_i\}$$

The existence of this set is guaranteed not by the Axiom of Union, as one would expect, as that axiom is only useful for finite unions. Instead it is guaranteed by the Axiom Schema of Separation (see the heading 'Separation Schema' under this link).

A more compact and - to me - more aesthetically pleasing notation is available whereby we discard the index function and just write:

$$\bigcup_{A\in\mathscr{C}} A$$

This is the same set as defined above. I prefer this notation as it is more 'purist' but most people find the numeric index notation more intuitive as they are used to indexing things with integers. However, once we start dealing with uncountable collections we are forced to give up the numeric index notation.