• Support PF! Buy your school textbooks, materials and every day products Here!

Well Ordered sets

  • Thread starter srfriggen
  • Start date
  • #1
288
3

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 [tex]\subseteq[/tex] A, then B[tex]\subseteq[/tex]{x1, x2, x3...xn}.

Since B[tex]\subseteq[/tex]A, the smallest possible subset B can be is {x1} which has a least element, ie x1.

Therefore B is well-ordered.

Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
743
1
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?
 
  • #3
288
3
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.)
 
  • #4
743
1
That's okay, we're here to help.

Think about the [itex] \mathbb R [/itex]. 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 [itex] \mathbb R [/itex] are finite.

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

Now let [itex] B \subseteq A [/itex], 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 lets choose a non-empty subset [itex] C \subseteq B [/itex].

Can you connect the dots from here?
 
  • #5
288
3
That's okay, we're here to help.

Think about the [itex] \mathbb R [/itex]. 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 [itex] \mathbb R [/itex] are finite.

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

Now let [itex] B \subseteq A [/itex], 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 lets choose a non-empty subset [itex] C \subseteq B [/itex].

Can you connect the dots from here?

Ok so C[tex]\subseteq[/tex]B and B[tex]\subseteq[/tex]A, then C[tex]\subseteq[/tex]A? 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 :/
 
  • #6
743
1
But A is well ordered right? So what does that mean? If [itex] C \subseteq A [/itex] is a non-empty subset, then....
 
  • #7
288
3
But A is well ordered right? So what does that mean? If [itex] C \subseteq A [/itex] is a non-empty subset, then....

If C[tex]\subseteq[/tex]A, 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?
 
  • #8
743
1
Okay, let's slow down. You're finished, but you don't realize you're finished.

The definition of well ordered:
A set [itex] A [/itex] is well-ordered if [itex] A [/itex] has a strict total-ordering in which every non-empty subset has a least element.
Now we are given that [itex] A [/itex] is well ordered, and told that [itex] B \subseteq A [/itex] 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 [itex] B [/itex] 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 [itex] C \subseteq B [/itex], then C has a minimal element. But [itex] C \subseteq A [/itex] 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.
 
  • #9
288
3
Im starting to get it. I'm gonna have to go over it a bit later when I get back and really get it down.

Thanks for your help and patience!
 

Related Threads for: Well Ordered sets

  • Last Post
Replies
1
Views
382
  • Last Post
Replies
1
Views
977
  • Last Post
Replies
4
Views
2K
Replies
0
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
954
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
2K
Top