22 replies to this topic

[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 by Rainman, 09 September 2012 - 11:46 AM.

[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?

Spoiler for

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 by plasmid, 09 September 2012 - 10:14 PM.