Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Discrete Mathematics
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/