Results 1 to 9 of 9

Math Help - Well ordered-set

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Well ordered-set

    Prove that for each integer m, the set S=\{i \in \mathbb{Z}: i\geq m \} is well-ordered. [Hint: For every subset T of S, either T \subseteq N or T-N is a finite nonempty set.]

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

    Question: Did the author mean T \subseteq \mathbb{Z} or T-\mathbb{Z}?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Quote Originally Posted by novice View Post
    Question: Did the author mean T \subseteq \mathbb{Z} or T-\mathbb{Z}?
    I guess no. \mathbb{N} is well ordered while \mathbb{Z} is not: T\subseteq\mathbb{Z} does not help. Furthermore T-\mathbb{Z}=\emptyset.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    There is no mistake that the author meant it T \subseteq \mathbb{N} or T-\mathbb{N}. He was trying to make the set either a set of all positive integers or a set of all non-positive integers.

    T-\mathbb{Z} does not make sense because it suggests that T \cap \mathbb{Z}^c = \emptyset, which is impossible.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by novice View Post
    T-\mathbb{Z} does not make sense because it suggests that T \cap \mathbb{Z}^c = \emptyset, which is impossible.
    What?? T\subseteq\mathbb{Z}\implies \mathbb{Z}'\subseteq T'\implies T\cap \mathbb{Z}'\subseteq T\cap T'=\varnothing\implies T\cap\mathbb{Z}'=\varnothing.

    Why is that impossible?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    What?? T\subseteq\mathbb{Z}\implies \mathbb{Z}'\subseteq T'\implies T\cap \mathbb{Z}'\subseteq T\cap T'=\varnothing\implies T\cap\mathbb{Z}'=\varnothing.

    Why is that impossible?
    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 m, the set S=\{i \in \mathbb{Z}: i\geq m\} is a well-ordered set.

    Proof:

    Let T be a nonempty subset of S. So we may say that T \subseteq \mathbb{N} or T-\mathbb{N}. In other words,

    S=T \cup (T \cap N^c). Now we have inclusively in S, two separate sets, namely T \subseteq S and T \cap \mathbb{N}^c \subseteq S

    Case 1: Consider T \subseteq S \subseteq \mathbb{N}. In this case, since T \subseteq N, we know by Well-ordering theorem that T is well-ordered.


    Case 2: T \cap \mathbb{N}^c. We will take advantage of the symmetry of \mathbb{Z} about zero. Now let


    A=\{n+1: -n\in T\cap \mathbb{N}^c\} for every integer n.

    Since A is a set of positive integers, again by Well ordering theorem, A has a least element m. Hence
    m \leq n for every n \in A. Therefore,

    -m \in T \cap \mathbb{N}^c and -m\geq -n for every n\in T \cap \mathbb{N}^c. So by the Well-ordering theorem, T\cap \mathbb{N}^c has a greatest element -m; therefore, T \cap \mathbb{N}^c is also well-ordered.

    Consequently, S=T \cup (T \cap N^c) is well-ordered.



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

    A=\{n+1: -n\in T\cap \mathbb{N}^c\}. Is this legitimate?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    What?? T\subseteq\mathbb{Z}\implies \mathbb{Z}'\subseteq T'\implies T\cap \mathbb{Z}'\subseteq T\cap T'=\varnothing\implies T\cap\mathbb{Z}'=\varnothing.

    Why is that impossible?
    Sorry again, I did not answer your question.

    T\cap\mathbb{Z}^c = \emptyset is impossible because T \subseteq \mathbb{Z} and  T \not = \emptyset.

    T is a nonempty subset of S with a least element. If T is empty, we would have nothing to prove.

    To say T\cap\mathbb{Z}^c = \emptyset is to say T = \emptyset
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    I answer about your proof.

    Quote Originally Posted by novice View Post
    Let T be a nonempty subset of S. So we may say that T \subseteq \mathbb{N} or T-\mathbb{N}
    Be careful, the underlined sentence has no meaning. What was proposed is : we have either ( T\subseteq \mathbb{N}) or ( T-\mathbb{N} is finite and non-empty).

    Your first case proof is correct, but try again for the second one. You cannot use \mathbb{Z} symmetry about 0, see that what you wrote applies for S=\mathbb{Z}: you did not use the fact that S has a minimal element and therefore T\cap\mathbb{N}^c 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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Sep 2009
    Posts
    502
    Will be back later in the day. Currently have a commitment to fulfill. Thanks for the comment on the greatest element.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by clic-clac View Post

    ...see that what you wrote applies for S=\mathbb{Z}: you did not use the fact that S has a minimal element and therefore T\cap\mathbb{N}^c is finite (and of course a finite set of integers is well ordered by the restriction of the natural order).
    I understand that we can prove it by Principle of Transfinite Induction, which says

    Let T be a subset of a well-ordered set S with the following properties:
    (1) m \in S,
    (2)  s(a) \subseteq S \Rightarrow a \in S
    where m is the least element in S, and s(a) the set of elements precede a.

    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.

    Quote Originally Posted by clic-clac View Post
    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.
    I was being too creative that I twisted the principle. Yes, it's laughable.

    Let's try again:

    We have proved that since T being a nonempty subset of S and that T \subseteq \mathbb{N}, it follows that T has a least element t_0; therefore, T is well-ordered.

    Now in case 2: T-\mathbb{N} where T-\mathbb{N} \subseteq S and T-\mathbb{N} \not = \emptyset.

    Suppose that none of the least element t_0 \in T \subset \mathbb{N} is the first element m of S, then t_0 \not \in T- \mathbb{N}, t_0-1 \in T-\mathbb{N} and m \in T-\mathbb{N}. Hence T-\mathbb{N} has a least element m and the largest element t_0-1. As a consequence, T-\mathbb{N} is a finite set of integers. Since every nonempty finite set of real numbers is well-ordered, T-N is well-ordered, so is S.

    I hope it works this time.
    Last edited by novice; March 13th 2010 at 09:13 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A well-ordered set
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 9th 2010, 02:22 PM
  2. Ordered pair
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 29th 2009, 07:52 PM
  3. Well ordered set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2009, 03:36 AM
  4. Set ordered
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 23rd 2008, 01:43 PM
  5. How many different ordered pairs?
    Posted in the Geometry Forum
    Replies: 4
    Last Post: November 12th 2008, 05:37 PM

Search Tags


/mathhelpforum @mathhelpforum