Well ordering of the integers

• Sep 24th 2013, 01:04 PM
topsquark
Well ordering of the integers
Here's the exercise:
Quote:

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
Quote:

(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
• Sep 24th 2013, 02:04 PM
HallsofIvy
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?
• Sep 24th 2013, 02:22 PM
Plato
Re: Well ordering of the integers
Quote:

Originally Posted by topsquark
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?
• Sep 25th 2013, 05:45 AM
topsquark
Re: Well ordering of the integers
Quote:

Originally Posted by HallsofIvy
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
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
• Sep 25th 2013, 06:33 AM
Plato
Re: Well ordering of the integers
Quote:

Originally Posted by topsquark
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.
• Sep 25th 2013, 12:31 PM
emakarov
Re: Well ordering of the integers
Quote:

Originally Posted by topsquark
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.
• Sep 25th 2013, 02:00 PM
topsquark
Re: Well ordering of the integers
Quote:

Originally Posted by emakarov
(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