4

So I am supposed to prove that the well ordering principle is equivalent with the maximum principle.

Well ordering principle: Every nonempty subset of the set of positive integers has a least element.

The maximum principle: let $T \subset Z_{\geq 0}$ be a nonempty subset which is bounded above. Then $T$ has a greatest element.

Actually, I dont see how I am going to use WOP to prove TMP, I know it might be wrong but since we consider integers, isn't TMP rather obvious? I mean, if it did not contain a greatest element then it would not be bounded above (this is of course not true if we consider real numbers). Am I thinking about this in a wrong way?

2 Answers2

2

Suppose the WOP, and let $\;\emptyset\neq T\subset\Bbb N\;$ be bounded above. Let $\;X\;$ be the set of upper bounds of $\;T\;$ , i.e.:

$$X:=\{x\in\Bbb N\;;\;\forall y\in T\;,\;\;y\le x\}$$

Since $\;X\neq\emptyset\;$ (why?), there's an element $\;x\in X\;$ which is minimal, from which it follows that $\;x-1\notin X\;$ ...complete the proof now.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • That won't work if, say, $T = {1,3}$. Look instead at the set of upper bounds for $T$, that is, ${x : \text{for all $y \in T$, we have $x \ge y$}}$. – Stephen Montgomery-Smith Apr 10 '14 at 03:37
  • Good point, @StephenMontgomery-Smith. Thanks, editing on its way. – DonAntonio Apr 10 '14 at 03:59
  • I think you should edit your answer, for instance, the definition of $X$ doesnt make sense. Am I missing something? –  Apr 10 '14 at 22:42
  • Thanks @GeorgeMouselli: that's part of the prior version that remained unedited. I think it is fine now. – DonAntonio Apr 11 '14 at 05:15
  • I would like to ask you, isnt WOP considered as an axiom? Something that is always true? So WOP is true independent of TMP, the second part of the question was to show that TMP implies WOP, this must be obvious since WOP is an axiom, do you see my point or am I wrong? –  Jun 07 '14 at 01:40
  • I think they both can be considered axioms, @Sodan. The point is that, under certain assumptions, they both are equivalent. – DonAntonio Jun 07 '14 at 08:55
0

Suppose that there is no greatest element of $T$. Let an upperbound of $T$ be denoted as $\zeta$. We choose $\zeta$ to be a positive integer (such an integer always exists by the Archimedean Property of the Number System, and that follows from the WOP) . Now choose any element $t_0$ $\in$ $T$. By assumption since there is no greatest element of $T$ hence we conclude that there must be an infinite number of integers between two integers which in view of The Principle of Mathematical Induction (and its corollary that if for a set of integers $S$, 1. $-1$ $\in$ $S$, 2. $k$ $\in$ $S$ $\implies$ $k-1$ $\in$ $S$ then $S$ is the set of all negative integers) is impossible.

Now note that PMI only states that any two positive (by the corollary that I have stated above, negative also) integers can be reached by a finite number of addition of $1$. But my proof is still incomplete because I have not yet proved that the element $0$ can be reached in finitely many steps from any integer. Now this is trivial because start from any integer $a$, if it is positive then reach $1$ in finitely many steps and then just take one more step to go to $0$. Similar is the argument for negative $a$.

Hence proved.

William Hilbert
  • 1,223