Trying to prove the above implication I thought about the following proof. However, I think the reasoning is flawed. What is wrong here?

Assume a non-empty set of natural numbers S. Let /S/ be the number of elements in S.

Base step: If /S/=1, S contains one element, which is obviously the least element.

Induction step: The well ordering principle holds for sets with /S/=n. Take a set with /S/=n and add any element x not equal to an element in S. The new set is S’ with /S’/=n+1. If x is smaller than the least element of the set S, then it is the least element of S’. If x is greater than the least element of S, then the least element of the set S is also the least element of S’. In either case S’ has a least element, that is the well ordering principle holds for set with /S/=n+1.

Hence the well ordering principle holds for all n.

  • 1
    $\begingroup$ The basic problem is that you are looking at $|S|$ and apparently assuming it to be finite. $\endgroup$ – Tobias Kildetoft Feb 17 '16 at 8:46
  • $\begingroup$ You really really need to specify "for integers". $\endgroup$ – DanielV Feb 17 '16 at 8:57
  • 1
    $\begingroup$ @DanielV where should "for integers" be specified? $\endgroup$ – Tobias Kildetoft Feb 17 '16 at 9:00
  • $\begingroup$ In the theorem you are trying to prove, since you aren't attempting to generalize the theorem for all inductive structures. $\endgroup$ – DanielV Feb 17 '16 at 9:02
  • $\begingroup$ @DanielV I am not trying to prove anything (I am not the OP). But it was not clear to me where it should be stated (also, integers is not the right set for this as it is not well-ordered). $\endgroup$ – Tobias Kildetoft Feb 17 '16 at 9:05

Mathematical induction proves some statement $P(n)$ for all $n \in \mathbb N$. In your case, $P(n)$ is the statement "Any subset of the natural numbers containing exactly $n$ elements can be well ordered".

Your proof does work for this statement, but it does not prove the statement for infinite subsets, e.g. for $\mathbb N$ itself.


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.