Re: Question about induction argument

From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 10/07/04 

Date: Thu, 07 Oct 2004 09:19:53 -0400

Agapito Martinez wrote:

> Consider interval [a_0, b_0]. There is a collection {(a_j, b_j):
> 1<=j<=n} of (open) intervals such that
>
> Union (j=1 -> n) (a_j, b_j) contains [a_0, b_0].
>
> It is intuitively clear that there exists a subset of {(a_j, b_j)},
> {(a_k, b_k): 1<= k <= m <= n} such that :
>
> a_1 < a_0 < b_1, a_m < b_0 < b_m and
>
> for m>1, a_(k+1) < b_k < b_(k+1), 1 <= k <= m-1
>
> How does one construct a formal induction argument to prove this?

The following is a rough proof ignoring the induction idea. You may
need to fill in a few details to make it rigorous. You know that
[a_0,b_0] is a subset of Union (j=1,n) of (a_j,b_j). There are two
possibilities:

1) [a_0,b_0] is a subset of one of the (a_j,b_j). This trivially
satisfies the conditions.

2) [a_0,b_0] is not a subset of any of the (a_j,b_j). In this case,
consider a minimal collection (with renumbering as necessary) of
(a_k,b_k) where k=1 to m, a_1<a_2<a_3<...<a_m and Union (k=1,m) of
(a_k,b_k) contains [a_0,b_0]. Now, to be a minimal collection,
b_1<b_2<b_3<...<b_m, otherwise you have an i where (a_k,b_k) contains
(a_(k+1),b_(k+1)). Now, suppose a_1<a_0<b_1 is not true, then either
a_0 < a_1, or b_1<a_0. In the first case, a_0 is not in the union,
violating the fact that the union is a cover. In the second case, the
(a_k,b_k) where k=2 to m must be a cover, violating the minimality.
Similarly, a_m < b_0 < b_m. Now, suppose there is a k, 1<=k<=m-1,
where a_(k+1) < b_k < b_(k+1) is not true. We know from above that
b_k<b_(k+1), so we must have b_k<a_(k+1). In that case, the union does
not cover [b_k,a_(k+1)]. Since it does cover [a_0,b_0], this must mean
that the intersection of [b_k,a_(k+1)] and [a_0,b_0] is empty. So,
either b_1<b_k<a_(k+1)<a_0 -> b_1<a_0, a contradiction with the above,
or b_0<b_k<a_(k+1)<a_m -> b_0 < a_m, a contradiction with the above.

QED

I think the only detail that could be strengthened is the existence of
the minimal covering of [a_0,b_0], but since there is a finite cover of
open sets to begin with, getting a minimal cover by throwing out the
excess sets shouldn't be too hard. 

-- 
Will Twentyman
email: wtwentyman at copper dot net

Relevant Pages

  • Re: Topology with A and finite.
    ... descending chain of open sets containing x, ... their intersection would violate minimality. ... If A was infinite, some U_x would contain infinitely many points of A, ... but then every neighborhood of x contains infinitely many points of A, ...
    (sci.math)
  • Re: Topology with A and finite.
    ... descending chain of open sets containing x, ... their intersection would violate minimality. ... Since topology is finite, U_x is open nhood x, ... If A was infinite, some U_x would contain infinitely many points of A, ...
    (sci.math)
  • Re: Topology with A and finite.
    ... descending chain of open sets containing x, ... their intersection would violate minimality. ... If A was infinite, some U_x would contain infinitely many points of A, ... but then every neighborhood of x contains infinitely many points of A, ...
    (sci.math)