3
$\begingroup$

$A$ and $B$ are well-ordered sets. $A, B \subseteq \mathbb{R}$

$$ C := \{ n+m : n \in A , m \in B \} $$

How do i now prove that $C$ is well ordered? It seem logical to me, but I have to prove that ever $S \subset C$ has a minimum.

  • 0
    What is your ordering and what is operator $+$? Are $A$ and $B$ just subsets of natural numbers?2012-11-29
  • 0
    $A$ is well-ordered means that every subset of $A$ has a minimum2012-11-29
  • 0
    Yeah, but with no knowledge of $+$ operator, you cannot prove it. Maybe it is monotonic or something?2012-11-29
  • 0
    Are $A$ and $B$ sets of ordinals?2012-11-29
  • 0
    $A$ and $B$ are subsets of the real numbers2012-11-29
  • 0
    Well, that is quite a substantial information.2012-11-29

1 Answers 1

3

Hint: Let's assume that $C$ is not well-ordered, then there is in an infinite strictly decreasing sequence $c_1 > c_2 > \ldots$. Each of those is of the form $a_i + b_j$, so at least one of the $\{a_i\}_i$ or $\{b_j\}_j$ has to contain infinite strictly decreasing sequence, contradiction.

Edit: According to Andres Caicedo (as pointed out in the comments), the follow-up is a standard technique in Ramsey theory.

  • 0
    This was too quick. Let's see. Let's call $a_i\in A$ and $b_i\in B$ numbers such that $c_i=a_i+b_i$. Then $c_{i+1} gives us that either $a_{i+1}, or $b_{i+1}. For example, we could have $a_2, $b_3, $a_4, etc. How are you getting a decreasing sequence of $a_i$s or of $b_i$s out of this? One can use Ramsey's theorem, which completes the proof. But it seems to me that in fact something like Ramsey's theorem is needed in any argument (that is, it is not automatic). Do you have a quick, elementary argument in mind?2012-11-29
  • 0
    @AndresCaicedo The point is that something has to cause this negative step. Let's assume that $\{a_i\}$ doesn't have such a sequence (if it does then we are done), let's pick ${c'_i} \subset {c_i}$ to be subsequence such that $a'_i \leq a'_{i+1}$ then set $c''_i = a'_1 + b'_i$ which is still a strictly decreasing sequence and therefore $b'_i$ is a strictly decreasing sequence.2012-11-29
  • 0
    Again, the existence of your subsequence $c'$ needs that you can argue "coherence" in the order of the $a_i$ in an infinite set. This needs a Ramsey theoretic argument: You need $a_1'$ such that there are infinitely many points above it, and among those some $a_2'$ with infinitely many points above it, and among those ...2012-11-30
  • 1
    @AndresCaicedo One fact I know is that if you can't find a point which has infinetely many weakly-above it, then there exists strictly decreasing sequence. You pick $a'_1$, then skip the finitely many above it, pick $a'_2$, skip the finitely many above it, etc. I have no idea if it is called Ramsey's theoretic argument, but it seems similar to what you are telling.2012-11-30
  • 0
    Yes, this is the usual argument. It is Ramsey theory, but analysis books tend not to mention the word. (You may want to add a remark or so to your answer, to clarify this detail.)2012-11-30