Is there anything wrong with the following proof?
Theorem. Every non-empty subset $B \subset\mathbb{N}$ has a least member.
Proof. Assume not. Then, of necessity, we'd have to have $B=\varnothing$, for if $B$ contained even one $b\in\mathbb{N}$, then that $b$ would satisfy $b=min(B). $ Contradiction, end proof.
I get the sense there is something wrong here, but I can't seem to define exactly what. Also, is there a context where one can simply take this principle as an axiom, and not have to prove it? After all, it is extremely intuitive. Thanks.
$\endgroup$ 25 Answers
$\begingroup$You should be more detailed in what you claim. Your proof is wrong, and it is very hard to understand why you obtain said conclusions. My point is:
"Then, of necessity..." Why?
"...if $B$ contained even one $b∈\Bbb N$, then that $b$ would satisfy $b=\min(B)$? Why?
A correct proof would go as follows:
P Let $B\subseteq \Bbb N$ be nonempty. We prove by induction that $B$ has a least element. Assume by contradiction that $B$ has no least element. Let $J$ be the set of elements that are not in $B$. Since $0$ is a lower bound of $\Bbb N$, $0\notin B$ (else it would be a least element) so $0\in J$. We prove by induction that $0,1,\dots,n\in J\implies n+1\in J$. Indeed, suppose that $0,1,\dots,n\in J\implies n+1\in J$. Then $n+1$ cannot be in $B$ since then it would be a lower bound of $B$, and since $0,1,\dots,n\notin B$, it would be a least element. It follows $n+1\notin J$. By induction, $J=\Bbb N$ so $B=\varnothing$ which is impossible.
As Pete is saying, WOP is equivalent to PMI.
PROP Suppose every nonempty subset of $\Bbb N$ has a least element. Let $B$ be a subset of $\Bbb N$ with the following properties
$(1)$ $0\in B$.
$(2)$ $n\in B\implies n+1\in B$
We show that $B=\Bbb N$.
$\endgroup$ 6 $\begingroup$P Let $B$ be as above. Consider the set of $\Bbb N\setminus B$, and assume by contradiction it is not empty. By the WOP, it has a least element, call it $a$. Since $0\in B$, this element must be of the form $a=n+1$ for some $n\in \Bbb N$. Since $n+1$ is the first element that is not in $B$, $n$ is an element of $B$. But then $n+1\in B$, which is absurd. It follows that $\Bbb N\setminus B$ must be empty, so $B=\Bbb N$, as claimed.
What do you mean by "if $B$ contained even one $b \in \mathbb{N}$?" Your argument works if $B$ contains exactly one $b$. It doesn't seem to work otherwise: e.g. the subset $\{1,3\}$ contains "even one element $3$", but $3$ is not the least element.
Also, yes: you can take WOP as part of an axiomatic description of the natural numbers $\mathbb{N}$. You should know that -- for instance, given the other four Peano axioms -- it is equivalent to the Principle of Mathematical Induction.
$\endgroup$ 6 $\begingroup$Assume not. Then, of necessity, we'd have to have $B=\varnothing$, for if $B$ contained even one $b\in\mathbb{N}$, then that $b$ would satisfy $b=\min(B). $
This only works if $B$ contains exactly one element. For any other $B$, you have to assume that $\min$ is well-defined, i.e. every subset of $\mathbb{N}$ has a least member, so your reasoning is circular.
$\endgroup$ $\begingroup$Here is another proof from the book Topology by Munkres:
Would this work as a proof of the well ordering principle alone? Perhaps not at all the "if POI is true then WOP" part...
Assume that $S$ is a non empty subset of $\mathbb{N}$ and that it is has no least element. Then, there must exist an $m$ such that $m$ is a natural number and an element of $S$ as otherwise $S$ would be empty. Then: $$inf(\mathbb{N}) \le inf(S) \le m$$ since if $S$ had included a lesser element than $inf(\mathbb{N})$ that element wouldn't be in $\mathbb{N}$ and it is bounded above by $m$ because we know $m \in S$ we don't need anything greater than m to be the least infimum of $S$ as there is always $m$. So $inf(S)$ is bounded in a finite region which suggests that there exists a least element in $S$, this is a contradiction.
$\endgroup$
