Proof by induction in sets

  • #1
189
4

Homework Statement


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

Pr(∪Ai)=limn→infPr(An)

∪ 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 A1⊂A2[/B]
so A1∪A2=A2
Therefore Pr(A1∪A2)=Pr(A2)

Inductive Step

let Pr(∪Ai)=limk→infPr(Ak)

then we have to show that if Ak⊂Ak+1 then limk→infPr(Ak∪Ak+1)=limk→infPr(Ak+1)

so

This is true because Ak∪Ak+1=Ak+1
so limk→infPr(Ak∪Ak+1)=limk→infPr(Ak+1)


so by math induction Pr(∪Ai)=limn→infPr(An)

is that right?
 

Answers and Replies

  • #2
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
415
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?
 
Last edited:
  • #3
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

Homework Statement


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

Pr(∪Ai)=limn→infPr(An)

∪ 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 A1⊂A2[/B]
so A1∪A2=A2
Therefore Pr(A1∪A2)=Pr(A2)

Inductive Step

let Pr(∪Ai)=limk→infPr(Ak)

then we have to show that if Ak⊂Ak+1 then limk→infPr(Ak∪Ak+1)=limk→infPr(Ak+1)

so

This is true because Ak∪Ak+1=Ak+1
so limk→infPr(Ak∪Ak+1)=limk→infPr(Ak+1)


so by math induction Pr(∪Ai)=limn→infPr(An)

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".
 
  • #4
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,913
1,474
∪ 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.
 

Related Threads on Proof by induction in sets

Replies
3
Views
10K
Replies
2
Views
1K
Replies
3
Views
5K
  • Last Post
Replies
6
Views
872
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
928
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
769
Top