2
$\begingroup$

I am trying to understand why is the well ordering principle stated as an axiom of integers.

In the process, I found a "proof" of the principle (which is obviously wrong) and want to understand where the error is.

Let $S$ be a subset of $\mathbb{N}$, let $n \in S$. Then we have :

  • Either $n$ is less than every other element of $S$ and then $S$ has a least element.
  • Either the above is false, then take $m$ to be least element of the finite set $S\cap [0\ldots n]$ which is necessarily non empty (because if contains at least $n$ itself) and then $m$ will be less than any element of $S$.

Where is the error? Is it the use of axiom of choice when I take "let $n \in S$"? In that case is it true that axiom of choice implies well ordering principle of integers? (I know axiom of choice implies well ordering theorem, but here i am talking about well ordering principle of integers with natural order).

May be the error is assuming that every finite subset of $\mathbb{N}$ has a least element? Thanks for help.

$\endgroup$
5
  • 1
    $\begingroup$ "which is necessarily non empty (because if empty then n would be least element of S) " No. It would mean $n$ is smaller than all elements of $S$. $\endgroup$
    – fleablood
    Jul 1 '18 at 15:54
  • 2
    $\begingroup$ Simply put, icking a single element from a non-empty set does not involve the Axiom of Choice. However, how do you know that every bounded subset of $\Bbb N$ has a least element? $\endgroup$ Jul 1 '18 at 15:54
  • 1
    $\begingroup$ Replace $\mathbb N$ with $\mathbb R$ and let $S = (n+1, n+2)$ which has no least element. No consider $T = [0...n]\cap (n+1,n + 2)$. Are you going to claim that $T$ is non-empty because other wise it would imply that $n$ is the least element of $(n+1, n+2)$. That simply makes zero sense. $\endgroup$
    – fleablood
    Jul 1 '18 at 15:58
  • $\begingroup$ @fleablood $n$ is also in $S$ by hypothesis, I should explain that better $\endgroup$
    – volatile
    Jul 1 '18 at 20:10
  • 1
    $\begingroup$ You are assuming a lot of things. You are assuming a finite set has a least element. You are assuming the set $[0....n]$ is well defined and finite. And you are assume $S$ does not have any elements that are less than any element in $[0..... n]\cap S$. These are all provable by axioms but I believe you must use the well ordering principal to do so. $\endgroup$
    – fleablood
    Jul 1 '18 at 20:31
2
$\begingroup$

First you are assuming that finite sets are well ordered without question.

Which I suppose follows from the induction principle.

But really the statement: $S \cap [0.... n]$ is necessarily non-empty or else $n$ would be the least element of $S$--- is simply wrong. You might as well say or else Micky Mouse would be a bulldog, for all the logical implication I can see.

Well, maybe that was an exageration.

$[0.... n]$ contains all natural number equal or less than $n$ so if $S\cap [0...n]$ is empty then one can conclude $S$ contains only natural numbers greater than $n$.

So what?

It certainly does NOT contain $n$ (because $S\cap [0...n]$ is empty; it does NOT contain $n$) and $n$ is certainly NOT the least element of $S$ ($n$ is not eve in $S$). You could conclude $n$ is less than any and all of the elements of $S$. ....

But what does that have to do with whether $S$ has a least element or not?

$\endgroup$
3
  • $\begingroup$ To the proposer: It's all about definitions. What is the def'n of "finite" and how do you know that $\{m\in \Bbb N: m\leq n\}$ meets this def'n? And you can't answer that without a def'n of $\Bbb N$..............+1 $\endgroup$ Jul 1 '18 at 18:31
  • 1
    $\begingroup$ In my hypothesis, I already picked $n \in S$ so $S\cap \mathbb{N}$ is not empty, because it contains $n$ already. So if the intersection is only $n$ then n is least element of $S$, and if any other elements are in the intersection then I take the minimum of them $\endgroup$
    – volatile
    Jul 1 '18 at 20:09
  • 1
    $\begingroup$ You are assuming a lot of things. You are assuming a finite set has a least element. You are assuming the set $[0....n]$ is well defined and finite. And you are assume $S$ does not have any elements that are less than any element in $[0..... n]\cap S$. These are all provable by axioms but I believe you must use the well ordering principal to do so. $\endgroup$
    – fleablood
    Jul 1 '18 at 20:29
1
$\begingroup$

We need to be clear on our axioms here. I will be using this list of the Peano axioms because it includes an axiomatic ordering of the numbers and does not include an induction axiom nor the well ordering principle. We will also need ZFC.

There are some problems with your proof under these axioms:

  1. The symbol $\{0, 1, \dots, n\}$ is not defined by any of the axioms. You have to define that yourself (probably using the axiom schema of specification).
  2. None of the axioms guarantee that the resulting subset is finite (which you probably need induction to do, but see next point). If we're very strict, the word "finite" does not appear in the ZFC axioms at all, so you may need to define it and prove various other things about it as well.
  3. None of the axioms guarantee that all finite subsets of the natural numbers (of whatever size) have a least element, and I don't believe you can prove that fact without using induction in some form. You can prove a bounded form of this (i.e. if you pick some number $k$, then you can prove that all finite sets of at most $k$ elements have a least element), but your proof needs the unbounded form to find $m \in \{0, 1, \dots, n\} \cap S$ (because you don't know the value of $n$ in advance).
$\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.