Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Infinite monotone subsequence


  • Please log in to reply
22 replies to this topic

#11 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 09 September 2012 - 11:36 AM

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.

  • 0

#12 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 09 September 2012 - 12:00 PM

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.
  • 0

#13 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 09 September 2012 - 03:59 PM

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?
  • 0

#14 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 09 September 2012 - 04:11 PM

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.
  • 0

#15 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5637 posts
  • Gender:Male
  • Location:New York

Posted 09 September 2012 - 08:51 PM

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.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#16 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 09 September 2012 - 08:59 PM

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.
  • 0

#17 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5637 posts
  • Gender:Male
  • Location:New York

Posted 09 September 2012 - 09:20 PM

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.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#18 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 09 September 2012 - 09:31 PM

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.
  • 0

#19 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 09 September 2012 - 09:33 PM

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.
  • 0

#20 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1331 posts
  • Gender:Male

Posted 09 September 2012 - 10:07 PM

I'm no expert on the various different flavors of infinity, but would simply rephrasing Bushindo's answer do?
Spoiler for
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.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users