Ramsey's Theorem and Infinite Sequence
Date: 06/01/99 at 04:46:22 From: Keith Chan Subject: Infinite sequence Prove that every infinite sequence S of distinct positive integers contains either: a) an infinite subsequence such that, for every pair of terms, neither term ever divides the other, OR b) an infinite subsequence such that, in every pair of terms, one always divides the other. Keith
Date: 06/01/99 at 16:49:53 From: Doctor Wilkinson Subject: Re: Infinite sequence Hi, Keith! This is a form of Ramsey's Theorem. It has nothing to do with divisibility of course, but only with the fact that you have two relations one of which is the negation of the other. Here's a sketch of one way to prove it. Let's say x and y are related if either x divides y or y divides x. Let's call an element of S "friendly" if it's related to all but a finite number of elements of S, and unfriendly if it's related to only a finite number of elements of S. Let F be the set of friendly elements of S, and U the set of unfriendly elements of S. Now if F is infinite, you can construct an infinite set of elements in F every two of which are related. Similarly if U is infinite, you can construct an infinite set of elements in U no two of which are related. But if F and U are both finite, then T = S - U - F is infinite and contains no friendly or unfriendly elements, and in this case you can construct an infinite set of elements in T every two of which are related, or if you prefer, an infinite set no two of which are related. - Doctor Wilkinson, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.