Proof check. Well-ordering principle for the natural numbers.

Question

I know there are a lot of proofs out there for the well-ordering principle already. As an exercise, I thought I'd try to prove it differently. My attempt is as follows. Would appreciate any feedback!

Prove: Every non-empty subset of the natural numbers, S, has a minimum, min(S), such that min(S) is less than or equal to all s in S.

Let Sn denote a subset (of the natural numbers) of cardinality n.

(Base case) n = 1: S contains exactly one element, x. Clearly, x is less than or equal to all s in S.

(Inductive step) Suppose inductively that min(Sn) is well-defined. It can be shown that min(Sn+1) is also well-defined. In particular, Sn+1 can be written as Sn U S1. min(S1) and min(Sn) are both well-defined. There are three possible relationships between min(S1) and min(Sn): <, =, >. If min(S1) < min(Sn), then min(S1) is less than or equal to every element in S1 and Sn and is therefore less than or equal to every element in Sn+1. [Perform the same analysis on each of the two other cases]

QED

Answer 1

Often times, the problem people have with induction is that they don't have a clearly stated proposition they are using an inductive argument to prove.

Your attempt at the problem appears to be trying to prove the proposition

$P_n \equiv$ Every subset of $n$ elements has a minimum

And to fix up your inductive step, start by saying something like

Suppose $P_n$ is true. Let $S$ be a set of $n+1$ elements. Write $S = U \cup V$ where $U$ has $n$ elements and $V$ has $1$ element

Then use $U$ and $V$ everywhere you write $S_n$ and $S_1$.

Once you've done that... you may have a correct proof of $P_{n+1}$. But it's terse and missing many details. On the one hand, it's the sort of thing I'd accept from my colleagues because I think it's clear how to fill in the details (and I imagine it's also clear to my colleagues). But on the other hand, I'm not sure that I would accept it from a student who is learning about proofs and is having trouble with the details, because I strongly suspect that the details are omitted because they don't understand how to fill them in, and at best only understand the intuitive idea.

---

But let's say you do have a correct proof, so that by induction, $P_n$ holds for every $n$. This still doesn't prove the theorem you were trying to prove, however — you can conclude that every finite set has a minimum, but it still leaves open whether or not an infinite set has a minimum.

Ultimately, you need to mix in a new idea to complete the proof.