请输入您要查询的字词:

 

单词 ProofOfRamseysTheorem
释义

proof of Ramsey’s theorem


ω(ω)kn

is proven by inductionMathworldPlanetmath on n.

If n=1 then this just states that any partitionMathworldPlanetmathPlanetmath of an infinite setMathworldPlanetmath into a finite number of subsets must include an infinite set; that is, the union of a finite number of finite setsMathworldPlanetmath is finite. This is simple enough to prove: since there are a finite number of sets, there is a largest set of size x. Let the number of sets be y. Then the size of the union is no more than xy.

If

ω(ω)kn

then we can show that

ω(ω)kn+1

Let f be some coloringMathworldPlanetmath of [S]n+1 by k where S is an infinite subset of ω. Observe that, given an x<ω, we can define fx:[S{x}]nk by fx(X)=f({x}X). Since S is infinite, by the induction hypothesis this will have an infinite homogeneous set.

Then we define a sequence of integers niiω and a sequence of infinite subsets of ω, Siiω by induction. Let n0=0 and let S0=ω. Given ni and Si for ij we can define Sj as an infinite homogeneous set for fni:[Sj-1]nk and nj as the least element of Sj.

Obviously N={ni} is infinite, and it is also homogeneousPlanetmathPlanetmath, since each ni is contained in Sj for each ji.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 1:56:09