Infinite monotone subsequence

[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

In a 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,

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]

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

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.

[Rainman]

Sorry, you still can't justify that conclusion based on those premises. Let me put it this way.

1) There is a natural number 1.

2) For every natural number K, there is a natural number K+1.

Conclusion: there is an infinite natural number.

The premises 1 and 2 are correct, but I think we both know there is no infinite natural number. So the conclusion can't be made.

Arbitrarily long: for any given natural number K, there is a monotone sub-sequence of length L>K. Proven.

Infinitely long: there is a monotone sub-sequence S such that for any given natural number K, S is more than K units long. Not proven.

bonanova, regarding countable vs uncountable infinity, my OP is unclear. I am only considering countable infinity.

Edited September 9, 2012 by Rainman

[Rainman]

Let me provide a definition for infinite sequence as well, to clear up the countability issue.

Infinite sequence: a sequence S satisfying the following conditions.

1) S has a first element P.

2) For each element E, there is a next element E+.

3) Every element in S, except P itself, is a descendant of P. That is, it can be reached by starting at P and going to the next element a certain number of times.

[CaptainEd]

I'm perplexed. Bushindo's proof has the same form as Euclid's proof of the infinity of primes: for each one that is alleged to be the largest one, there's one that's larger. What's wrong with that?

[Rainman]

That proves that there are infinitely many primes, not that there is an infinitely large prime. Every prime is of course finite. In the same way, Bushindo has proven that there are infinitely many monotone subsequences, not that there is an infinitely long one.

[bonanova]

Rainman, if a sequence can have its elements placed in a one-to-one correspondence with the natural numbers then the sequence and the natural numbers have the same cardinalities. The cardinality is Aleph null. I think Bushindo has done that. Each individual natural number is finite. Each term in Bushindo's sequence has a finite index. But saying that each integer is finite is different from saying there are a finite number of integers.

The integers, and sequences with corresponding terms, are countably infinite.

[Rainman]

The set of natural numbers has Aleph null cardinality, yes. The set of monotone subsequences also has Aleph null cardinality. Which means that there are infinitely many such subsequences. But that's not what I asked you to prove. I asked you to prove that there is a monotone subsequence that is infinitely long, i.e. it does not have a finite length. So far you have only proven that there is a subsequence of any given finite length.

[bonanova]

That proves that there are infinitely many primes, not that there is an infinitely large prime. Every prime is of course finite. In the same way, Bushindo has proven that there are infinitely many monotone subsequences, not that there is an infinitely long one.

I'm not convinced.

So the primes can be assembled in increasing order, with each prime greater than its integer index, and you would conclude the primes are bounded? If there is no infinitely large prime (if that even has any meaning: infinity is not a value) then there certainly is no "infinitely large" integer. Every integer is "of course" finite. But that does say there is a largest one. Each of Bushindo's sequences has finite length, but that does not mean there is a longest one - one that is only as long as the greatest integer.

[Rainman]

Rainman, if a sequence can have its elements placed in a one-to-one correspondence with the natural numbers then the sequence and the natural numbers have the same cardinalities. The cardinality is Aleph null. I think Bushindo has done that. Each individual natural number is finite. Each term in Bushindo's sequence has a finite index. But saying that each integer is finite is different from saying there are a finite number of integers.

The integers, and sequences with corresponding terms, are countably infinite.

The problem is to show that there is an individual monotone subsequence that is not finite. To show that the set of monotone subsequence is different from the set of natural numbers in that respect.

You are right in (almost) every aspect, bonanova. The primes are not bounded, but each individual prime is still finite. The natural numbers are not bounded, but each individual natural number is still finite. The set of monotone subsequences is not bounded, and there is an individual monotone subsequence that is infinite. That last part is what remains to be proven.

It is proven that there is no longest finite monotone subsequence, but that doesn't imply that there is an infinitely long monotone subsequence. If it did, that same reasoning would imply that there are infinitely large natural numbers.

[Rainman]

Good work so far though I don't want to come off as being rude, and I would love to give credit for a problem solved. It just isn't quite solved yet.

[plasmid]

I'm no expert on the various different flavors of infinity, but would simply rephrasing Bushindo's answer do?

He claims he can prove that for any sequence of length (N-1)²+1 there will be a monotonic subsequence of length N. Meaning that for a sequence of length M he can prove that there's a monotonic subsequence of length sqrt(M-1)+1 (rounding down). So for a sequence of length infinity, this would prove that there's a subsequence of length sqrt(infinity-1)+1, which is infinity.

Of course you could still take him to task on proving his lemma. I looked at the thread he linked to, and I don't think SP's proof is sufficient as stated: S_j>S_k or S_j<S_k will not imply that S_j can extend the longest subsequence because S_k is not necessarily the last digit in either the longest increasing or longest decreasing subsequence, and is certainly not involved in both. I think that Bushindo's proof from that thread is correct at least for the case of a sequence of length 17, and I think it can be extended as he says, but I haven't completely convinced myself of it yet.

Edit: If we're still not there yet, maybe giving us an example of what it takes to prove that you have an infinitely long sequence would help clarify the goal.

Edited September 9, 2012 by plasmid

[Rainman]

Rephrasing it would not be enough, IIRC the lemma was proven using some kind of pigeon hole principle - there are more pairs of indices than there are numbers in the sequence - and the lemma is true for natural numbers. But in the infinite case we can't apply that principle.

One way of proving that there is an infinite monotone subsequence, is to devise an algorithm that generates a monotone subsequence and prove that it never ends. A crude attempt is to simply start at the first number P and then skip to the first number that is larger than P, then to the next number that is larger than that, and so on. This attempt would fail if we reached a number such that no number that comes after it is larger.

[bonanova]

Still not convinced. Anyway here's a formal proof.

Let S be an infinite sequence {a_i} of reals. It can be bounded, but needn't be.

Suppose there is an element a_p in S that is larger than any succeeding term in S.

That is q > p implies a_q < a_p. We have two cases.

1. There are in infinite number of such elements.
   They comprise a monotone decreasing subsequence.
   .
   
2. There are a finite number of such elements; let a_t be the last one, and let t1=t+1.
   If S is not bounded, the number of such elements may be zero. In such a case let t=1.
   Consider a_t1. Since it follows a_t, there must be an a_t2 that is larger than a_t1.
   Similarly, since a_t2 also follows a_t, there must be an a_t3 that is larger than a_t2.
   This reasoning leads to an infinite monotone increasing subsequence.
   
   
   

[Rainman]

Yes, that proves it nicely done!

On a side note, I said in an earlier reply that the set of monotone subsequences has Aleph null cardinality. Then I thought about it and realized I spoke to soon. It contains every element in the power set of an infinite subsequence, and so it must have greater than Aleph null cardinality. So there is an uncountably infinite number of monotone subsequences.