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
Math Forum Home || Math Library || Quick Reference || Math Forum Search