Let ${x_n}$ be a sequence of real numbers. consider the set
$$P=\{n\in \mathbb{N}:x_n>x_m \forall m \in \mathbb{N}\hspace{4 pt} with \hspace{4 pt}m>n \}$$
Then which of the following is/are true?
(A) If P is finite, then $\{x_n\}$ has a monotonically increasing subsequence.
(B) If P is finite, then no subsequence of $\{x_n\}$ is monotonically increasing.
(C) If P is infinite, then $\{x_n\}$ has a monotonically decreasing subsequence.
(D) If P is infinite, then no subsequence of $\{x_n\}$ is monotonically decreasing.
Here is my work
If P is infinite then It is very clear that $\{x_n\}$ has a monotonically decreasing subsequence from the definition of P.
But there can be more than one answer. Since (C) is true (D) has to be false, But I am confused when P is finite.
For example ${x_n}=1,2,3,1,2,3,1,2,3…$
Here P is empty which is finite. But there exist a subsequence $1,2,3,3,3,3,3,3…$ which is monotonically increasing. This implies (B) is false.
We can conclude (A) is correct.
So (A) and (C) are correct.
Am I missing something?
Best Answer
Yes, your reasoning for (C) is correct. Your counterexample shows that (B) cannot be correct too. You are right in that (A) is correct, but you may want to come up with a proof as to why it is true whenever $P$ is finite. To do so, simply consider discarding all the elements in the sequence $(x_n)_{n \geq 1}$ up to and including the last element of $P$. After that, what can you say about each element $x_n$ remaining? (Hint: there exists $m > n$ such that $x_n \leq x_m$...)