Proving the so-called "Well Ordering Principle"

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.

Solution 1:

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$.

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.

Solution 2:

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.

Solution 3:

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.