1

It seems to me that the purpose of the well-ordering principle is to prove that something that is a natural number exists and proving that something exists really has nothing to do with having a least element.. unless of course we must specify what that least element is... or is bounded within a range. We first prove that a set that is a subset of the naturals is non-empty by naming an example of when a condition of that set is satisfied. show that a natural number q satisfies property P(q), Then we say that because there is a set with a least element, we don't care about how many elements exactly there are in the set of whether there actually is a least element or what that least element is... therefore there exists some natural number satisfying some property.

I feel like we never use the well-ordering principle to prove that there is a least element, which is kind of like a lower-bound, an infimum or to address what the lower bound is, or to show how many elements there are in a set, we just try to show if there is non-empty set then there exists a q $\in$

$\mathbb{N}$. Why do we even mention that the well-ordering principle shows that there is a least element if the most frequent use of the WOP is to show that something exists? If we use the WOP as a tool to show existence, lets say in euclidean division algorithm n=ad+c, there exists a c, why do we care whether they is a least element? I think learning the fact that WOP shows that there exists some least element is useless. We should just show non-empty is the subset of natural numbers and therefore there exists a remainder from Euclidean division.

I feel like the least element implication of the WOP is a useless fact to know and it's not important to write in a proof if the only practical purpose of WOP is to show existence.

  • is the least element derived from WOP the lower bound for which the predicate works? P(n) works for n>=3. let 3 be the least element of the set {3,4,5,6} which is a subset of the naturals. –  Jun 12 '17 at 03:29
  • Definitions are your friends, and the definition of a well-ordering of a set does more than "mention" a least element. It is the essential definition that a well-ordering of a set designates a least element of every nonempty subset. So you may not see that well-ordering as a concept has any application other than the natural numbers $\mathbb{N}$, but it does find application outside of number theory. – hardmath Jun 12 '17 at 15:29

1 Answers1

2

I don't understand what you're asking, so let me prove a classical theorem using the well ordering principle, and you can tell me if there is some kind of problem with the way I'm using it.

Let $n$ be a natural number which is $\geq 2$. We say that $n$ is composite if there exist natural numbers $a$ and $b$, both less than $n$, such that $n = ab$. Otherwise, $n$ is called prime.

Theorem: Every natural number $n \geq 2$ can be written as a product of prime numbers. That is, there exists a natural number $k \geq 1$, and prime numbers $p_1, ... , p_k$, such that $n = p_1 \cdots p_k$.

Proof: Suppose not. Then the set $S$ of natural numbers which are $\geq 2$ and which cannot be written as a product of prime numbers is not empty. Being a nonempty subset of the natural numbers, the well ordering principle tells us that $S$ must contain a least element $s$.

Now $s$ is itself not prime, so there exist natural numbers $a$ and $b$, both less than $s$, such that $s = ab$. It is clear that $a$ and $b$ are both $\geq 2$. Since they are both less than $s$, they do not lie in $S$, and so they are both expressible as products of prime numbers. Hence $s$ is a product of prime numbers, contradiction. $\blacksquare$

D_S
  • 33,891