Results 1 to 7 of 7
Like Tree4Thanks
  • 1 Post By HallsofIvy
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By emakarov

Math Help - Well ordering of the integers

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Well ordering of the integers

    Here's the exercise:
    Prove the well-ordering Property of \mathbb{Z} by induction and prove the minimal element is unique.
    About well-ordering of \mathbb{Z}, my text says
    (Well Ordering of \mathbb{Z}) If A is any nonempty subset of \mathbb{Z} ^+, there is some element m \in A such that m \leq a, for all a \in A. (m is called the "minimal element" of A.)
    This is some pretty basic stuff, but how can I show that \mathbb{Z} is well-ordered, seeing as it isn't in its usual ordering? (The text hasn't covered different orderings.)

    My next question (assuming that I'm supposed to show the well ordering of \mathbb{Z} ^+) is how to structure the induction? I want to use the fact, for example, that \{ \{ 1, 2, 3, \text{ ...}, m \}, m + 1 \} is isomorphic to \{ 1, 2, 3, \text{ ... }, m + 1 \} but the text hasn't covered isomorphisms yet. Can anyone think of another approach?

    Thanks!

    -Dan

    PS By the by, I know that A can be of the form {1, 2, 4, 5, 6, 100}. The proof should be essentially identical to the case {1, 2, 3, 4, 5, 6}. and I feel more comfortable with using the chain (is that the correct term?)

    -Dan
    Last edited by topsquark; September 24th 2013 at 01:07 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,707
    Thanks
    1470

    Re: Well ordering of the integers

    I don't understand what you mean by "seeing as it isn't in its usual ordering". Where are you told that it isn't?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1

    Re: Well ordering of the integers

    Quote Originally Posted by topsquark View Post
    Here's the exercise:
    About well-ordering of \mathbb{Z}, my text says
    This is some pretty basic stuff, but how can I show that \mathbb{Z} is well-ordered, seeing as it isn't in its usual ordering? (The text hasn't covered different orderings.)
    I am confused. The integers are not well ordered.
    The set negative integers, \mathbb{Z}^-, is a nonempty subset of \mathbb{Z} but that set has no first term.

    Now any nonempty subset of \mathbb{Z} that is bounded below is well ordered.

    What exactly are you asked to prove?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Re: Well ordering of the integers

    Quote Originally Posted by HallsofIvy View Post
    I don't understand what you mean by "seeing as it isn't in its usual ordering". Where are you told that it isn't?
    The problem comes from "Abstract Algebra" by Dummit and Foote. It's an undergrad Group Theory/Abstract Algebra text. I am working through the "preliminary" section so I doubt that there's any ordering properties that are not "standard." By that I mean we can take 4 > 3 > 2 > 1 > 0 as opposed to other ordering schemes.

    Quote Originally Posted by Plato View Post
    I am confused. The integers are not well ordered.
    The set negative integers, \mathbb{Z}^-, is a nonempty subset of \mathbb{Z} but that set has no first term.

    Now any nonempty subset of \mathbb{Z} that is bounded below is well ordered.

    What exactly are you asked to prove?
    The problem statement is the first quote in the OP. The definition my text gives me for a definition of well-ordering is the second quote.

    The point about the set of negative integers was my exact thought that the question is worded wrong. As you agree with me I won't sweat it any longer and just skip the problem.

    Thanks to both of you.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1

    Re: Well ordering of the integers

    Quote Originally Posted by topsquark View Post
    The problem comes from "Abstract Algebra" by Dummit and Foote. It's an undergrad Group Theory/Abstract Algebra text.
    I have a old pre-publication review copy of the second edition of that book.
    And you are correct that problem is exactly as you said. I spent some time looking at posted errata sheets for the book but no luck.
    So I went back and reviewed their definition. It says, (Well ordering for \mathbb{Z}), if A is a subset of \mathbb{Z}^+ then ....
    Thus, I think that you are to show that every A\subset\mathbb{Z}^+ has a first term using induction.

    Like so much else in Dummit/Foote, I find them to use confusing language here. But then I learned algebra from book by Herstein and then Mac Lane nearly a half century ago.
    Last edited by Plato; September 25th 2013 at 06:36 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Well ordering of the integers

    Quote Originally Posted by topsquark View Post
    My next question (assuming that I'm supposed to show the well ordering of \mathbb{Z} ^+) is how to structure the induction?
    (See also StackExchange.) The proof is by strong induction. Let B be a nonempty subset of \mathbb{Z}^+ and suppose B does not have the least element. Let J=\mathbb{Z}^+\setminus B. We will show that J=\mathbb{Z}^+. Indeed, 1\in J because otherwise 1 would be the least element of B. Next, assume 1, ..., n ∈ J. If n+1 ∈ B, then n+1 is the least element of B (since 1, ..., n ∉ B), so n+1 ∈ J. Thus, J=\mathbb{Z}^+ and B is empty, a contradiction.

    One can notice that the proof is by contradiction and we consider the complement of B. It can be shown that the contrapositive of strong induction for a predicate P is the well-ordering principle for the the set \{n\in\mathbb{Z}^+\mid\neg P(n)\} (see this post). Thus, strong induction and well-ordering principle are equivalent. Strong induction, in turn, can be proved from regular induction.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Re: Well ordering of the integers

    Quote Originally Posted by emakarov View Post
    (See also StackExchange.) The proof is by strong induction. Let B be a nonempty subset of \mathbb{Z}^+ and suppose B does not have the least element. Let J=\mathbb{Z}^+\setminus B. We will show that J=\mathbb{Z}^+. Indeed, 1\in J because otherwise 1 would be the least element of B. Next, assume 1, ..., n ∈ J. If n+1 ∈ B, then n+1 is the least element of B (since 1, ..., n ∉ B), so n+1 ∈ J. Thus, J=\mathbb{Z}^+ and B is empty, a contradiction.

    One can notice that the proof is by contradiction and we consider the complement of B. It can be shown that the contrapositive of strong induction for a predicate P is the well-ordering principle for the the set \{n\in\mathbb{Z}^+\mid\neg P(n)\} (see this post). Thus, strong induction and well-ordering principle are equivalent. Strong induction, in turn, can be proved from regular induction.
    Thanks. I have used strong induction so rarely I didn't consider it as a method.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ordering of a set
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 18th 2012, 06:44 AM
  2. Replies: 7
    Last Post: August 3rd 2010, 01:31 PM
  3. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 02:02 PM
  4. Well-Ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 08:13 AM
  5. Replies: 4
    Last Post: February 24th 2008, 03:08 PM

Search Tags


/mathhelpforum @mathhelpforum