Results 1 to 9 of 9

Thread: Well ordered-set

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Well ordered-set

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

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

    Question: Did the author mean $\displaystyle T \subseteq \mathbb{Z}$ or $\displaystyle 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 $\displaystyle T \subseteq \mathbb{Z}$ or $\displaystyle T-\mathbb{Z}$?
    I guess no. $\displaystyle \mathbb{N}$ is well ordered while $\displaystyle \mathbb{Z}$ is not: $\displaystyle T\subseteq\mathbb{Z}$ does not help. Furthermore $\displaystyle 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 $\displaystyle T \subseteq \mathbb{N}$ or $\displaystyle 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.

    $\displaystyle T-\mathbb{Z}$ does not make sense because it suggests that $\displaystyle 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
    22
    Quote Originally Posted by novice View Post
    $\displaystyle T-\mathbb{Z}$ does not make sense because it suggests that $\displaystyle T \cap \mathbb{Z}^c = \emptyset$, which is impossible.
    What?? $\displaystyle 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?? $\displaystyle 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 $\displaystyle m$, the set $\displaystyle S=\{i \in \mathbb{Z}: i\geq m\} $ is a well-ordered set.

    Proof:

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

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

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


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


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

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

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

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



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

    $\displaystyle 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?? $\displaystyle 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.

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

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

    To say $\displaystyle T\cap\mathbb{Z}^c = \emptyset$ is to say $\displaystyle 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 $\displaystyle T$ be a nonempty subset of $\displaystyle S$. So we may say that $\displaystyle T \subseteq \mathbb{N}$ or $\displaystyle T-\mathbb{N}$
    Be careful, the underlined sentence has no meaning. What was proposed is : we have either ($\displaystyle T\subseteq \mathbb{N}$) or ($\displaystyle T-\mathbb{N}$ is finite and non-empty).

    Your first case proof is correct, but try again for the second one. You cannot use $\displaystyle \mathbb{Z}$ symmetry about $\displaystyle 0,$ see that what you wrote applies for $\displaystyle S=\mathbb{Z}:$ you did not use the fact that S has a minimal element and therefore $\displaystyle 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 $\displaystyle S=\mathbb{Z}:$ you did not use the fact that S has a minimal element and therefore $\displaystyle 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 $\displaystyle T$ be a subset of a well-ordered set $\displaystyle S$ with the following properties:
    (1) $\displaystyle m \in S$,
    (2)$\displaystyle s(a) \subseteq S \Rightarrow a \in S$
    where $\displaystyle m$ is the least element in $\displaystyle S$, and $\displaystyle s(a)$ the set of elements precede $\displaystyle 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 $\displaystyle T$ being a nonempty subset of $\displaystyle S$ and that $\displaystyle T \subseteq \mathbb{N}$, it follows that $\displaystyle T$ has a least element $\displaystyle t_0$; therefore, $\displaystyle T$ is well-ordered.

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

    Suppose that none of the least element $\displaystyle t_0 \in T \subset \mathbb{N}$ is the first element $\displaystyle m$ of $\displaystyle S$, then $\displaystyle t_0 \not \in T- \mathbb{N}, t_0-1 \in T-\mathbb{N}$ and $\displaystyle m \in T-\mathbb{N}$. Hence $\displaystyle T-\mathbb{N}$ has a least element $\displaystyle m$ and the largest element $\displaystyle t_0-1$. As a consequence, $\displaystyle 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 $\displaystyle S$.

    I hope it works this time.
    Last edited by novice; Mar 13th 2010 at 08: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: Mar 9th 2010, 01:22 PM
  2. Ordered pair
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Nov 29th 2009, 06:52 PM
  3. Well ordered set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 3rd 2009, 02:36 AM
  4. Set ordered
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Nov 23rd 2008, 12:43 PM
  5. How many different ordered pairs?
    Posted in the Geometry Forum
    Replies: 4
    Last Post: Nov 12th 2008, 04:37 PM

Search Tags


/mathhelpforum @mathhelpforum