Munkres’ Proof of Well Ordering Property

In Munkres’ Topology the proof for the Well-Ordering Property is stated as follows:
enter image description here

  • I’m having confusion with the first and second underlined part: “Let A be the set of all positive integers n for which the statement holds.” Isn’t this the very statement that we are trying to show is true in this subproof ? Can you please restate this in a different way because I feel as though it might be ambigious??
  • When he says “this set” in the last underlined part does he mean the set $C cap {1,…, n }$ or the set $A$?
  • And I’m sorry to put it so generally but what is the key idea behind the subproof; is it to show that intersection between the set of the first $n$ integers and any subset of it has a least element? I don’t see how such an intersection should imply the existence of a least element.

Thanks in advance guys, I hate asking to clarify so many little points but this one just ain’t clicking for me.

Answer

I’m having confusion with the first and second underlined part: “Let A be the set of all positive integers n for which the statement holds.” Isn’t this the very statement that we are trying to show is true in this subproof ? Can you please restate this in a different way because I feel as though it might be ambigious??

No, this statement is merely a definition. The symbol $A$ is being defined to refer to the set of $n$ such that the statement holds. We don’t yet know that the statement holds for all $n$, and we’re just collecting all the $n$ such that it does hold into a set and calling that set $A$. We’re not asserting that the statement ever actually does hold; maybe $A$ is empty.

The role of $A$ is that we now want to prove $A=mathbb{Z}_+$. That means that every positive integer is an element of $A$, or in other words that the statement holds for every positive integer $n$.

When he says “this set” in the last underlined part does he mean the set $C cap {1,…, n }$ or the set $A$?

He means $C cap {1,…, n }$. The statement $nin A$ by definition means that any nonempty subset of ${1,dots,n}$ has a least element. Since $Ccap {1,dots,n}$ is a nonempty subset of ${1,dots,n}$, it therefore has a least element.

And I’m sorry to put it so generally but what is the key idea behind the subproof; is it to show that intersection between the set of the first $n$ integers and any subset of it has a least element? I don’t see how such an intersection should imply the existence of a least element.

I’m not quite sure what you’re asking here. The overall goal is to prove that if $D$ is any nonempty subset of $mathbb{Z}_+$, then it has a least element. We do this using the following observation: if $nin D$, then the least element of $D$ must be less than or equal to $n$. So if we find the least element $k$ of $Dcap {1,dots,n}$, then $k$ is actually the least element of all of $D$. Indeed, for any $din D$, if $dleq n$, then $kleq d$ since $din Dcap{1,dots,n}$ and $k$ is the least element of $Dcap{1,dots,n}$. And if $d>n$, then obviously $kleq d$ since $kleq n$.

So using this idea, we only need to prove that $Dcap {1,dots,n}$ has a least element. Now we rename $Dcap{1,dots,n}$ to $C$ and think of $C$ as just some arbitrary nonempty subset of ${1,dots,n}$. So what we want to prove now is that any nonempty subset of ${1,dots,n}$ has a least element. This is what the subproof is proving, and it does so by induction on $n$.

Leave a Reply

Your email address will not be published. Required fields are marked *