## 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

# Infinite monotone subsequence

22 replies to this topic

### #21 Rainman

Rainman

• Members
• 162 posts

Posted 09 September 2012 - 10:51 PM

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.

Spoiler for hint for solving

• 0

### #22 bonanova

bonanova

bonanova

• Moderator
• 6160 posts
• Gender:Male
• Location:New York

Posted 10 September 2012 - 04:44 AM

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

Spoiler for Suppose

• 0

Vidi vici veni.

### #23 Rainman

Rainman

• Members
• 162 posts

Posted 10 September 2012 - 09:40 AM

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

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users