1
$\begingroup$

Theorem. Well-Ordering Principle.

Every non-empty subset of natural numbers has a least element.

I have seen some proofs for the theorem, but is very "complex"proof really needed here?

My attempt of proof:

Let $$ D \subset \mathbb{N}= \left\{ 1, \ 2, \ 3, \ \dots \right\} $$ be an arbitrary non-empty subset of natural numbers. Therefore it has at least one element $$  n \in D.$$

Consider the finite set $$ \left\{1, \ \dots, \ n \right\}.$$ We check which of those natural numbers are elements of D. Then we choose the smallest one of those. There we have the least element.

$\endgroup$
2
  • 6
    $\begingroup$ The principle is so obvious that you accidentally used it while trying to prove it: "we choose the smallest one of those" assumes this constructed set of natural numbers ... has a smallest element. $\endgroup$
    – aschepler
    Feb 27, 2021 at 13:41
  • $\begingroup$ In mathematics what do you mean by "we check"? That sounds like a practical algorithm but even obtaining one element or checking membership is really not trivial for some sets. $\endgroup$ Feb 27, 2021 at 13:52

2 Answers 2

0
$\begingroup$

aschepler's comment points out the problem exactly. First you construct the set $$D\cap \{ 1,2,\ldots n\}$$ and then you consider the smallest element of this set...

Except that without the well-ordering principle, you cant be sure that it has a smallest element!

It might be instructive to consider what happens in your argument if you try to apply it to prove that $\Bbb Z$ is well-ordered.

$\endgroup$
2
  • $\begingroup$ This I don't understand. In {1, ..., n} I have finitely many numbers. 1 < 2 < ... < n (by some axiom of real numbers). When I take the intersection, I again have finitely many numbers. So how would it not be quarantined that there is a smallest element? @MJD $\endgroup$
    – mathslover
    Feb 27, 2021 at 14:51
  • $\begingroup$ and OK, I have been going through this precise proof as well. The one part that I don't understand is that when I have shown that the intersection of D and {1, 2, ..., n} has a smallest element, how does it (exactly) follow, that it is the smallest element of D as well? Could you explain this? $\endgroup$
    – mathslover
    Feb 27, 2021 at 14:54
0
$\begingroup$

This is a proof by induction. The theorem states that every non-empty subset of $\mathbb{N}$ has a least element.

Let $A\subseteq \mathbb{N}$ be a set with no least element. We want to prove that $A=\varnothing $, that is $\forall n$ $\in \mathbb{N}$, $n\notin A$. For induction on $n$ we have that:

$0\notin A$, in fact if $0 \in A$ we would have that: $0=$min$\mathbb{N}=$min$A$, but $A$ has no least element.

Suppose now that $\begin{Bmatrix} 0,1,...,n \end{Bmatrix}\cap A=\varnothing $. What we want to prove is that: $n+1\notin A$. If $n+1\in A$, infact, $n+1\neq$ min$A$ , since $A$ has no minimum for hypotesis. So $\exists m\in A$, $m<n+1$, which is a contradiction with the inductive hypothesis. So $n+1 \notin A$.

Hence $A=\varnothing$, as we wanted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.