Prove that for each integer , the set is well-ordered. [Hint: For every subset of , either or is a finite nonempty set.]

I know how to prove this, but I have a simple question.

Question: Did the author mean or ?

Printable View

- Mar 12th 2010, 09:32 AMnoviceWell ordered-set
Prove that for each integer , the set is well-ordered. [Hint: For every subset of , either or is a finite nonempty set.]

I know how to prove this, but I have a simple question.

Question: Did the author mean or ? - Mar 12th 2010, 09:57 AMclic-clac
- Mar 12th 2010, 01:46 PMnovice
There is no mistake that the author meant it or . He was trying to make the set either a set of all positive integers or a set of all non-positive integers.

does not make sense because it suggests that , which is impossible. - Mar 12th 2010, 03:00 PMDrexel28
- Mar 13th 2010, 06:48 AMnovice
Sorry for causing so much confusion. I raised a very stupid question and then realized that asked too soon.

Well, since we are at it, if you don't mind I would like to show you my proof so that you can evaluate whether it's legitimate.

Here we go:

We are asked to prove that for each integer , the set is a well-ordered set.

*Proof:*

Let be a nonempty subset of . So we may say that or . In other words,

. Now we have inclusively in S, two separate sets, namely and

Case 1: Consider . In this case, since , we know by Well-ordering theorem that T is well-ordered.

Case 2: . We will take advantage of the symmetry of about zero. Now let

for every integer .

Since is a set of positive integers, again by Well ordering theorem, has a least element . Hence

for every . Therefore,

and for every . So by the Well-ordering theorem, has a greatest element ; therefore, is also well-ordered.

Consequently, is well-ordered.

Question: I am trying to avoid having to deal with the zero, I contrived

. Is this legitimate? - Mar 13th 2010, 07:32 AMnovice
- Mar 13th 2010, 08:23 AMclic-clac
I answer about your proof.

Be careful, the underlined sentence has no meaning. What was proposed is : we have either ( ) or ( is finite and non-empty).

Your first case proof is correct, but try again for the second one. You cannot use symmetry about see that what you wrote applies for you did not use the fact that S has a minimal element and therefore is finite (and of course a finite set of integers is well ordered by the restriction of the natural order).

Recall that a well ordered set is an ordered set whose any non-empty subset has a minimal element; having a maximal element does not make your order be a well order. - Mar 13th 2010, 08:32 AMnovice
Will be back later in the day. Currently have a commitment to fulfill. Thanks for the comment on the greatest element.

- Mar 13th 2010, 02:15 PMnovice
I understand that we can prove it by Principle of Transfinite Induction, which says

Let be a subset of a well-ordered set with the following properties:

(1) ,

(2)

where is the least element in , and the set of elements precede .

However, I am still at the elementary level where the chapter has not cover Principle of Transfinite Induction. So I would like to do my best without using it and see if I could prove it at my level.

I was being too creative that I twisted the principle. Yes, it's laughable.

Let's try again:

We have proved that since being a nonempty subset of and that , it follows that has a least element ; therefore, is well-ordered.

Now in case 2: where and .

Suppose that none of the least element is the first element of , then and . Hence has a least element and the largest element . As a consequence, is a finite set of integers. Since every nonempty finite set of real numbers is well-ordered, T-N is well-ordered, so is .

I hope it works this time.