Proving Well-Ordered Subsets of Real Numbers

[srfriggen]

Homework Statement

"Prove that if A is any well-ordered set of real numbers and B is a nonempty subset of A, then B is also well-ordered"

Homework Equations

The Attempt at a Solution

If B \subseteq A, then B\subseteq{x1, x2, x3...xn}.

Since B\subseteqA, the smallest possible subset B can be is {x1} which has a least element, ie x1.

Therefore B is well-ordered.

 

[Kreizhn]

I think there is an important flaw here. So yes, we know that every subset of A has a minimal element right? But just because A is well ordered does not mean it is finite, or even countable!

So what do you need to show? To show that B is well ordered, you need to show that every non-empty subset of B has a minimal element right? So maybe start by taking a non-empty subset of B. Why does this set have to have a minimal element?

 

[srfriggen]

I think there is an important flaw here. So yes, we know that every subset of A has a minimal element right? But just because A is well ordered does not mean it is finite, or even countable!

So what do you need to show? To show that B is well ordered, you need to show that every non-empty subset of B has a minimal element right? So maybe start by taking a non-empty subset of B. Why does this set have to have a minimal element?

In the extreme case that A is not finite, then would every subset of A be finite, except for the subset that equals A? (say if you took the power set, without the empty set).

So every set not equal to A would be finite. Call one of those sets B. Then every subset of B would have a least element?


(Sorry if the above is just gibberish, I'm running into a mental roadblock with most questions involving sets. Trying very hard to comprehend though.)

 

[Kreizhn]

That's okay, we're here to help.

Think about the \mathbb R. I know it's hard to imagine a well-ordering on the reals but there is one (by the Well-Ordering Theorem). Now notice that certainly not all subsets of \mathbb R are finite.

I think you're thinking about this too hard. Remember that subset inclusion is a transitive operation, so that if X \subseteq Y and Y \subseteq Z then X \subseteq Z.

Now let B \subseteq A, and we want to show that B is well-ordered. So we need to show that every non-empty subset of B has a minimal element. So let's choose a non-empty subset C \subseteq B.

Can you connect the dots from here?

 

[srfriggen]

That's okay, we're here to help.

Think about the \mathbb R. I know it's hard to imagine a well-ordering on the reals but there is one (by the Well-Ordering Theorem). Now notice that certainly not all subsets of \mathbb R are finite.

I think you're thinking about this too hard. Remember that subset inclusion is a transitive operation, so that if X \subseteq Y and Y \subseteq Z then X \subseteq Z.

Now let B \subseteq A, and we want to show that B is well-ordered. So we need to show that every non-empty subset of B has a minimal element. So let's choose a non-empty subset C \subseteq B.

Can you connect the dots from here?

Ok so C\subseteqB and B\subseteqA, then C\subseteqA? But what implication does that have on B being well ordered?

B contains more elements than C and less elements than a well-ordered set - but I don't see how that indicates B has a least element :/

 

[Kreizhn]

But A is well ordered right? So what does that mean? If C \subseteq A is a non-empty subset, then...

 

[srfriggen]

But A is well ordered right? So what does that mean? If C \subseteq A is a non-empty subset, then...

If C\subseteqA, then every element of C is contained in A, and since C is a nonempty subset of A and A is well ordered, it follows that C has as least element. And since every element of C is in B, B must also contain the least element of C, so B is well ordered?

 

[Kreizhn]

Okay, let's slow down. You're finished, but you don't realize you're finished.

The definition of well ordered:

A set A is well-ordered if A has a strict total-ordering in which every non-empty subset has a least element.

Now we are given that A is well ordered, and told that B \subseteq A is a non-empty subset. We want to show that B is also well-ordered. Let's look at the definition to figure out what this means. Firstly, we know that B has a strict total-order inherited from A, so we don't care about that. This means that all we need to do is show that every non-empty subset of B has a minimal element.

Now sure, B has a minimal element in A, but we don't care about that. We want to show that if C \subseteq B, then C has a minimal element. But C \subseteq A and A is well-ordered, so by definition C has a minimal element and we're done, since C was chosen arbitrarily.

See? Everything is there! We've finished the proof. It's just a matter now of you seeing that the proof is indeed done.

 

[srfriggen]

Im starting to get it. I'm going to have to go over it a bit later when I get back and really get it down.

Thanks for your help and patience!