# Principle of mathematical induction to prove well ordering principle for set of rationals.

I am not being able to find what is wrong in this proof.

statement: For any set of rationals there is a least element in the set.

Hypothesis: $p(k)$=For set of k rationals there exist a least element in the set.

now,

It is trivial to prove that p(1) and p(2) are true.

Now suppose $p(k)$ is true. For Every set of k rationals there is a least element in the set.

Now we check truth value of $p(k+1)$ .

as we can split set $k+1$ of rationals as set of $k$ and 1 rational.

Now , as we know both of them have least element hence least among them will be least element in the set.

Hence,$$p(k)\implies P(k+1)$$ and Hence, Using PMI we prove that any set of rational elements has a least element .

Which is not true for rationals belonging in (0,1).

• So, you're proving that every finite set of rationals has a least element. – Daniel Aug 10 '15 at 15:46
• NO, any countable set of rationals has a least element. – Shubham Ugare Aug 10 '15 at 15:47
• @ShubhamUgare Consider the set of all rationals greater than zero - which is countable because the rationals are. – Mark Bennet Aug 10 '15 at 15:49
• To reiterate in a slightly different way what has been said already here: the natural numbers contain an infinite amount of elements. But each element is finite. The size of each set in your proof is some natural number, which is finite. So you are only proving this for all finite sets- even thought the amount of these sets is infinite. – Colm Bhandal Aug 10 '15 at 16:06
• @SolidSnake I was being a bit ambiguous. There are two meanings to what I said really. On the one hand, any number is finite in size, syntactically. E.g. we can represent it with a finite number of digits in base 10. On the other hand, the meaning of a natural number, when interpreted as a cardinality, represents a finite cardinality. The latter is more related to this question. – Colm Bhandal Aug 10 '15 at 16:31

What you're proving is that every finite set of rationals has a least element, that's why it doesn't work in the set $\Bbb Q\cap (0,1)$.
You think that you've proved it for any countable subset of $\Bbb Q$, but, if this were true, you'd have proved it for any subset of $\Bbb Q$ since $\Bbb Q$ is countable by itself.
Please keep in mind that induction can only prove statements about finite things, but any finite number of them. For example, you can prove by induction that for every finite set of natural numbers, there is always a 'biggest' element, it doesn't matter the set has $1000$ or $10^{10^{100}}$ elements, but this fails to happen if the set is infinite.