Spoiler for hint for solving

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

Started by Rainman, Sep 07 2012 10:19 PM

22 replies to this topic

### #21

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.

### #22

Posted 10 September 2012 - 04:44 AM

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

Spoiler for Suppose

*The greatest challenge to any thinker is stating the problem in a way that will allow a solution.*

- Bertrand Russell

### #23

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.

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 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users