1
$\begingroup$

In my calculus course, there's example stated on the book:

Given that $M$ is an ordered set and the sequence $\{a_n\}\subset M$, prove that there's a (weakly) monotonic subsequence of $\{a_n\}$.

After some searching work, I realized that it's a special case (Hint: the color of $(j,k)$ depends on whether $a_j\le a_k$) of infinite Ramsey's theorem, well, and to my surprise, the finite one is implied in the infinite one. I read these two proofs. They are actually concise and graceful.

However, I cannot appreciate the aspect or essence of these two proofs. Observing more closely, I find that these proofs of infinite Ramsey's theorem use both constructive technique and non-constructive technique. For example, pigeonhole principle is non-constructive:

If $A\cup B$ is infinite, then $A$ is infinite or $B$ is infinite.

It seems that we cannot construct the infinite subset of $A$ or $B$ explicitly by the infiniteness of $A\cup B$. In the proof of infinite Ramsey's theorem, pigeonhole principle is used, but it's not the only technique. We should mention that sequence $\{a_n\}$ is constructed explicitly.

Now my question arises: How can we observe the infinity? How can we conceive these proofs on our owns? Maybe it's more a question about methodology and how to solve problems.

Thanks!

  • 1
    Look deeply into the night sky.2012-10-26
  • 0
    You should note that why the pigeonhole principle is not constructive, it follows from a very basic understanding that the union of two finite sets is finite. Therefore in splitting an infinite set into two, at least one of the parts has to be infinite.2012-10-26
  • 0
    @AsafKaragila I'm not sure whether I used the right word. I consider that writing a set explicitly or inductively is constructive. For example, if $\{1,2,3,\ldots\}\subset U$, then $U$ is infinite, or inductively, just like the proof in wikipedia, it writes $a_1,a_2,\ldots$ one by one. At first, I've been thinking how to prove infinite Ramsey theorem by writing $M=\{m_1,m_2,\ldots\}$ explicitly, but failed.2012-10-26
  • 0
    @AsafKaragila Your proof of pigeonhole principle is reductio ad absurdum. I don't think it's constructive.2012-10-26
  • 0
    I don't see a proof anywhere. I also think that mathematics in which you can split an infinite set into two parts and both of them are finite is plain wrong (philosophically).2012-10-26
  • 0
    @AsafKaragila It's really **evident** but I think obvious things could be complicated in a intricate problem because we don't really **understand** these obvious stuff. At least, for me, infinite Ramsey theorem is so hard.2012-10-27

0 Answers 0