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

570 Views Asked by At

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).

1

There are 1 best solutions below

4
On BEST ANSWER

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)$.

Notice your argument works even if the set is not from the rationals but from a totally ordered set.

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.