关于有限覆盖定理的证明.pdf

《关于有限覆盖定理的证明.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、关于有限覆盖定理的证明Carbon.ChenOctober31,2013Contents1说在前⾯12记号及定理阐述13定理证明14写在最后25参考⽂献211说在前⾯10⽉25⽇是张巍班上的数分期中测试，果然班长在期中前就找了⼀份前两年的数分卷来做（不过看上去不像张巍班的卷⼦……）。最后⼀道题是让你证明有限覆盖定理。去杭州⽐赛的路上还是挺⽆聊的，就在车⼦上yy了⼀个构造性的证明（据⾦总说，似乎和教科书上见到的都不太⼀样）。到杭州后和⾦总交流了⼀下，⼀开始被challenge了，随后⼜修补了⼀下，现在开来似乎没有什么问题，于是写个⽂档交流⼀下。2记号及定理阐述Definition1

2、.∪开覆盖：集合A=f(ai,bi)g是⼀组开区间，U是⼀个数集合，若U(ai,bi)，则称开区间簇A覆盖了UTheorem1.有限覆盖定理：A是闭区间[α,β]的⼀簇开覆盖，则必有有限的A′A，使得A′也是[α,β]上的开覆盖3定理证明设A是[α,β]上的⼀簇开覆盖，为了⽅便不妨设：8i(ai,bi)2A,aiα+1,βbi+1(1)⾸先定义如下⼀种构造⽅法：设定初始覆盖集合为ϕ，构造数列R，初始为空，待覆盖区间为[α,β]，考察如下开区间簇：A~1=f(ai,bi)j(ai,bi)2A^aiabig(2)其中中所有的bi构成了集合B，显然，B集合是有界的，设Su

3、p(B)=MaxB，下⾯分两种情况讨论：1.9bi2B,bi=Sup(B)在这种情况下取开区间(ai,bi)加⼊覆盖集，并把bi加⼊数列R。2.8bi2B,biaj则把如上提到的(ai,bi)和(aj,bj)加⼊覆盖集，并把bj加⼊数列R。在这步之后，待覆盖区间变成了[r1,β]，重复这⼀步，直到某步加⼊R的rn>β。接下来⽤反正法证明这样⼀个构造的过程能在有限步之内能够结束。若8n,rnβ，则R=r1,r

4、2,r3...显然是⼀个单调递增，并且有界的数列。由单调有界数列必有极限定理，R存在极限Xβ，X=Sup(R)，并且不存在rnX。考虑X点，因为A是[α,β]上的开覆盖，所以9i,(ai,bi)2A,aiai，则这个(ai,bi)属于第i+1步中所考察的开区间簇A~i+11.若第i+1步属于情况1，则Sup(Bi+1)>bi>X，与ri+1bi>X，同样与ri+1

5、盖，且是有限的(证毕)4写在最后证明略有些长，具体稍有⼀些细节不太完整，符号有些重复，⼤家谅解。欢迎合理challenge~(^_^)~最后，纯蛋疼之作，写着玩的，内容较⽔，不太规范，不喜勿喷。5参考⽂献海涅－博雷尔定理fromWikipedia2