Proof critique of least number principle, please! I am independently working through Elliot Mendelson's "Number Systems and the Foundations of Analysis," which I find very well-written and rigorous, along with providing a healthy set of exercises. I have recently finished reading the order relation in Peano Systems section. The section finishes with the Least Number Principle theorem; the proof is (to me) somewhat jumbled and, at times, not precisely rigorous. As such, I wanted to rewrite it myself, filling in the gaps. EDIT- I can now see why many explicit steps were perhaps omitted or left to the reader =), this got quite tedious, upon completion.
(Let $P$ denote the underlying set of a Peano system with distinguished element $1$, unary operation S (successor) on $P$, and the familiar binary operation and relation $+$ and $<$, respectively, on $P$.)
Theorem 4.5: (Least Number Principle) Any non-empty subset of $P$ has a least element.
Proof: Let $A$ be a non-empty subset of $P$. Suppose, to the contrary, $A$ has no least element. Let $B := \{x \in P\  |\ (\forall u \in P)(u \leqslant x \implies u \notin A\}$. First, we show by mathematical induction that $B=P$. Note that $1\in B$, for if not: $1\notin P \lor (\exists u \in P)(u\leqslant 1\ \land u\in A)$. $1\in P$ by the definition of Peano system, so it must be the case that $(\exists u \in P)(u\leqslant 1\ \land u\in A)$. By Lemma 1, it follows that $u=1$, so $1\in A$. But by Lemma 2, then, $1$ would be a least element of $A$, a contradiction. Thus, $1\in B$. Next, we must show that $(y\in B \implies S(y) \in B)$, so assume $y\in B$.
This implies $(\forall u \in P)(u \leqslant y \implies u \notin A\}$. Suppose $S(y) \in A$. But if so, we can prove $S(y)$ to be a least element of $A$. To do so, let $v\in P$ and assume too that $v \in A$. But by the contrapositive of $(\forall u \in P)(u \leqslant y \implies u \notin A\}$ applied to $u=v$, this implies $y < v$. But by lemma 3, $y<v \iff S(y) \leqslant v$. But this means $S(y)$ is a least element of $A$, a contradiction. Hence, $S(y) \notin A$. Now, to prove that $S(y) \in B$, we must show that $(\forall u \in P)(u \leqslant S(y) \implies u \notin A\}$, so let $u\in P$ be arbitrary and suppose $u \leqslant S(y)$. If $u = S(y)$, then $S(y) \notin A$, as we have shown above. If $u < S(y)$, then by Lemma 4, $u \leqslant y$, in which case $u \notin A$ by the inductive step hypothesis, i.e., $(\forall u \in P)(u \leqslant y \implies u \notin A\}$. Hence, $S(y)\in B$. We have thus shown by induction that $B=P$. Note by Lemma 5 that $A\ \cap B = \emptyset$. But $B=P$, so $A\ \cap P = \emptyset$. By lemma 6, this implies $A = \emptyset$, since $P \ne \emptyset$, as $1\in P$. But $A$ is non-empty by hypothesis above, thus yielding a contradiction. As a result, $A$ must possess a least element.
$\\$
$\\$
Theorem 1.1 Every element different from $1$ is a successor.
Proof: (provided in text)
Lemma 1. $(\forall x\in P)(x\leqslant 1 \implies x=1)$.
Proof: Let $x\in P$ and suppose $x\leqslant 1$. If $x=1$, then we have proven our desired result. If $x < 1$, then by the definition of $<$, $x + u = 1$ for some $u\in P$. If $u=1$, then $x+1 = 1$, or $S(x) = 1$. But this contradicts an axiom of Peano systems; namely, that $(\forall x \in P)(1 \ne S(x))$ If $u\ne 1$, then by theorem 1.1 above, $u = S(w)$ for some $w\in P$. So $x  + u = x + S(w) = x + (w+1) = (x+w) + 1$, where the second equality holds by the definition of $+$ in $P$ (defined and proven in text, i.e., $(\forall x\in P)(x+1 = S(x))$), and the third equality holds via the associativity of $+$ on $P$ (also proven in text). Hence, $1 = S(x+w)$, which is again a contradiction to the same Peano axiom referenced in the previous sentence. As a result, $\lnot(x < 1)$, so it must be that $x=1$.
Lemma 2. $(\forall N\subseteq P)(1\in N \implies 1$ is a least element of $N)$.
Proof: Let $N\subseteq P$ be arbitrary and suppose $1\in N$. To prove that $1$ is a least element of $N$, we must prove that $(\forall u\in P)(u\in N \implies 1 \leqslant u)$. Thus, let $u\in P$ and suppose also $u\in N$. By theorem 1.1 above, either $u=1$ or $u=S(x)$ for some $x\in P$. If $u=1$, then clearly $1\leqslant u$, since $1 \leqslant 1$. If $u=S(x)$ for some $x\in P$, then $u = x+ 1 = 1 + x$, so by the definition of $<$, $1<u$; so $1\leqslant u$. In either case, $1\leqslant u$, so $1$ is a least element of $N$.
Lemma 3. $(\forall x,y \in P)(x < y \iff S(x) \leqslant y)$.
Proof: (provided in text)
Lemma 4. $(\forall x,y \in P)(x < S(y) \implies x \leqslant y)$.
Proof: (provided in text)
Lemma 5. $A\ \cap B = \emptyset$.
Proof: We must show that $(\lnot\exists z\in P)(z \in A\ \land z \in B)$. In other words, $(\forall z \in P)(z\in A \implies z\notin B)$. To prove this statement, let $z\in P$ be arbitrary. Suppose, furthermore, $z\in A$. If $z\in B$, then by the definition of $B$, $(\forall u \in P)(u \leqslant z \implies u \notin A\}$. Applying this statement for $u=z$, and noting that $z=z$, so clearly $z\leqslant z$, we may conclude that $z\notin A$. But this is a contraction, as $z\in A$ by hypothesis above. Hence, it must be the case that $z\notin B$. Since $z$ was arbitrary, $(\forall z \in P)(z\in A \implies z\notin B)$. So $A\ \cap B = \emptyset$.
Lemma 6. $(\forall X \subseteq P)(X \cap P = \emptyset \implies X = \emptyset)$.
Proof: Suppose $X\subseteq P$ and let $X \cap P = \emptyset$. Then $(\lnot \exists x\in P)(x\in P \wedge x\in X)$. Suppose $X  \ne \emptyset$. Then $\exists y\in X$. But $X\subseteq P$, so $y\in P$. But this means $y\in X$ and $y\in P$, or $y\in (X \cap P)$. But this is a contradiction, as $X \cap P = \emptyset$ by hypothesis. Thus, $X = \emptyset$.
 A: Your proof seems correct; I can't find any errors other than a few typos. However, it's not totally clear to read, nor is it the nicest thing to look at. Here are some tips on how to make it better:
First, excessive use of symbols can obscure your message. Your definition of $B$ made me do a double-take. I would re-write a lot of these in plain English, maybe followed by the symbolic definition if you think it's necessary. Something along the lines of "Let $B$ be the set of all $x\in P$ such that no $u\leq x$ is an element of $A$; in other words, $B=\{x\in P\,|\, (u\leq x)\implies (u\not\in A)\}$." (Incidentally, I'm not sure that your use of $\forall u\in P$ is strictly necessary; the domain of discourse is unambiguous to me.)
Further, paragraphs are critically important with any proof that's more than a few sentences. Make a point, prove it, new paragraph. This is especially important when you're working with something I like to call "nested contradiction," where you have a proof by contradiction with cases that also use contradiction. That statement "Suppose $S(y)\in A$" is where I got confused and needed to re-read a few times. To that end, I might structure the proof like this:

Let $A$ be a nonempty subset of $P$ and suppose to the contrary that $P$ has no least element. Define the set $B$ as (insert definition here). We will proceed by induction to show that $B=P$.
First, we show that $1\in B$. (Reasons, etc). So $1\in B$.
Now, we show that $(y\in B)\implies (S(y)\in B)$. To do this, let $y\in B$. We will consider two cases: either $S(y)\in A$ or $S(y)\not\in A$. (Telling us what you will do before you do it adds organization and makes it easier to follow along.)
In the case $S(y)\in A$, (insert reasons here) which means that $S(y)$ is a least element of $A$. But this is a contradiction because $A$ has no least element, so clearly $S(y)\not \in A$.
So, $S(y)\not\in A$, and (reasons reasons reasons). Therefore, $S(y)\in B$.
(You just completed a big step in the proof. Recap it.) We showed above that $1\in B$ and $(y\in B)\implies (S(y)\in B)$. Therefore, $B=P$.
(Finish the proof here) and so every subset of $P$ has a least element. QED

