22 replies to this topic

[Rainman]

Show that every infinite sequence of real numbers contains an infinite monotone subsequence.
---
Sequence: a set with a specified order of its elements. For example {1-2-4-3} is a different sequence from {4-1-3-2}.
Subsequence: a subset retaining the order of the original sequence. For example {2-3-5-7} is a subsequence of {1-2-3-4-5-6-7}.
Monotone: either increasing (each number is smaller than the next number) or decreasing (each number is larger than the next number).

[jim]

You need to change to the standard definition of montone.  Monotone increasing means each number is at least as large as the previous number.  If each successive number is actually larger that is called strictly monotone.  Decreasing monotone is defined in a similar way.  Note 1,1,1,1,1,1,1,... would need my definition to have any montone sequence of length greater than one.

[Rob_Gandy]

I was thinking along the same lines as jim. Using your definitions you cannot create an infinite monotone subsequence from a sequence of one repeated number.

[bushindo]

Show that every infinite sequence of real numbers contains an infinite monotone subsequence.
---
Sequence: a set with a specified order of its elements. For example {1-2-4-3} is a different sequence from {4-1-3-2}.
Subsequence: a subset retaining the order of the original sequence. For example {2-3-5-7} is a subsequence of {1-2-3-4-5-6-7}.
Monotone: either increasing (each number is smaller than the next number) or decreasing (each number is larger than the next number).

Let's relax the definition of monotone a bit and say that in a increasing monotone sequence, each number is bigger than or equal to than the last number. Same with decreasing monotone sequence. Then the statement in the OP is an extension of a previous puzzle

Spoiler for

In a previous puzzle, it was shown that in a sequence of 17 numbers, there is a monotone sequence of length 5. It is easy to extend the result there and show that for any parent sequence of length [ (N - 1)² + 1 ], there is either an increasing or decreasing monotone sub-sequence of length N. If we let the length of the parent sequence approach infinity, then the length of the monotone sub-sequence approaches infinity as well.

[Rainman]

I defined a sequence as a set, which means no two numbers can be equal. And a proof for each finite sequence is not quite enough to prove the infinite extension. For example, every finite sequence has a largest number but this doesn't imply that an infinite sequence has a largest number.

[Rainman]

To be more specific, you have proven that there are arbitrarily long monotone sub-sequences, but not that there are infinitely long ones.

[bushindo]

To be more specific, you have proven that there are arbitrarily long monotone sub-sequences, but not that there are infinitely long ones.

How about this proof then,

Spoiler for Proof by contradiction

Let A be the statement 'every infinite sequence of real numbers contains an infinite monotone subsequence'.

Let S = { a₁, a₂, a₃, ... } be a set consisting of elements a_n, where n goes between 1 and infinity.

Lemma 1: Given a sequence of [(N-1)² + 1] distinct numbers, there is a monotone subsequence of size N.

Let's assume the opposite of the A. That is, given an infinite set S, then there is no infinite monotone sub-sequence (Assumption ~A).

1) Assumption ~A implies that in an infinite sequence S, there is a monotone subsequence with a maximum finite length M. No monotone subsequence in S may have a length greater than M.
2) However, if we pick out the subsequence {a₁, a₂, a₃, ..., a_{(M*M + 1)} }, then we already have a monotone sequence of length (M+1) because of Lemma 1.

Since Assumption ~A leads to a contradiction between 1) and 2), then Assumption ~A can not be true. Therefore, every infinite sequence of real numbers contains an infinite monotone subsequence.

[Rainman]

Sorry, but there is an error in that proof. Assumption ~A does not imply that there is a monotone subsequence with maximum finite length M.

Suppose you are standing at a crossroads, with an infinite number of roads leading away from it. Each road is numbered with a unique natural number, and each road is n miles long where n is the number of the road. Whichever of these roads you choose (say road number p), it will eventually end (after p miles), so no road has infinite length. But you could always have chosen another road that is longer (road number p+1 for example).

The same thing could be true for these subsequences. You have proven that there is no longest monotone subsequence, but that doesn't imply that there is an infinite monotone subsequence.

[bonanova]

Spoiler for assume

You have an infinite sequence S of distinct natural numbers. Further, assume the longest increasing subsequence T has p elements, and its largest element is m. We inspect the indices in S of the elements of T and find that the largest index difference in S for a pair of successive elements of T is d. Then the last term in T has index in S that is no larger than pd. For T to have no more than p elements, all the natural numbers greater than m must be contained in the first pd elements of S. Since pd is finite, this is an impossibility. Therefore the longest increasing subsequence of S cannot terminate with p elements for any finite p. QED.

Edit: Ah, you said real, not natural. The crossroads derailed my thinking.

Does OP distinguish between countably and uncountably infinite?

[bushindo]

Sorry, but there is an error in that proof. Assumption ~A does not imply that there is a monotone subsequence with maximum finite length M.

Suppose you are standing at a crossroads, with an infinite number of roads leading away from it. Each road is numbered with a unique natural number, and each road is n miles long where n is the number of the road. Whichever of these roads you choose (say road number p), it will eventually end (after p miles), so no road has infinite length. But you could always have chosen another road that is longer (road number p+1 for example).

The same thing could be true for these subsequences. You have proven that there is no longest monotone subsequence, but that doesn't imply that there is an infinite monotone subsequence.

Let me restate the proof in a more direct way, and we'll see if we get anywhere

Spoiler for

Assume that there is a infinite set S, then

1) There is a monotone sequence of length 1 (Trivial statement)
2) For every monotone sequence of length K, there is a monotone sequence of length (K + 1); see Lemma from last proof.

So for any given finite monotone sequence in S of a fixed length, there is a longer monotone sequence. Therefore, there is an infinite monotone sequence in S.