Thread: induction for rationals??

1. induction for rationals??

Something occurred to me about the method of proof of induction and i don't know if there is something in this?

Is it possible to use induction to prove results other than ones involving natural numbers?
So instead of, check n=1, assume true for n=k, prove n=k+1 works etc, can you do something like, check n=1/2, assume true for n=1/k, prove it works for n=1/(k+1) , hence true for n=1/3, 1/4 etc.
Can this method be extended even further to prove everything except results involving irrationals?
This may be gibberish...

2. Re: induction for rationals??

You'd need to steps: one on the numerator and one on the denominator. For example (for only positive rationals):
1. show true for $\frac{1}{1}$;
2. assume true for $\frac{1}{k}$;
3. prove true for $\frac{1}{k+1}$;
1. show true for $\frac{1}{a}$;
2. assume true for $\frac{k}{a}$;
3. prove true for $\frac{k+1}{a}$.

You can actually have more complicated interactions between the two halves of the proof as long as you can show that all rationals are covered by the scheme.

3. Re: induction for rationals??

Originally Posted by rodders
Something occurred to me about the method of proof of induction and i don't know if there is something in this
Originally Posted by rodders
Is it possible to use induction to prove results other than ones involving natural numbers?
The short answer is decidedly NO. But to understand why that is one must know the axioms for the construction of numbers.
An ordered set is said to be well ordered if and only (iff) every non-empty subset contains a first term.
Now it should be clear to you that the set of natural numbers $\mathbb{N}= {0}\cup\mathbb{Z}^+$ is well ordered.

Now suppose that $\mathcal{P}$ is a statement about about members of $\mathbb{N}$. If it is known that $\mathcal{P}(0)$ is true. Furthermore, it is known that whenever for $k\in\mathbb{N}$ and $\mathcal{P}(k)$ is true then $\mathcal{P}(k+1)$ must also true. The question becomes: IS $\mathcal{P}$ a true for all $\mathbb{N}~?$
Suppose that $\exists t\in\mathbb{N}$ such that $\mathcal{P}(t)$ is not true.
Define $\mathscr{S}=\{x\in\mathbb{N}: \mathcal{P}(k)\text{ is not true}\}$
Why do we know that $\mathscr{S}\ne\emptyset~?$ HINT what about $t$.
By well order we know that $\mathscr{S}$ has a first element, call it $s$, that is $\mathcal{P}(s)$ is not true.
Here are facts you must explain.
$\mathcal{P}(s-1)$ is true. BUT by the hypothesis if $\mathcal{P}(s-1)$ is true then $\mathcal{P}([s-1]+1)=\mathcal{P}(s)$ is also true. Why is that a contradiction? So induction has been proved on well ordered sets.

In the set of positive rationals define $\mathcal{T}\{x\in\mathbb{R}^+:x^2<2\}$ it is easy to prove that the set $\mathcal{T}$ has no least term. Thus the positive rational numbers are not well ordered, So induction is not applicable.

4. Re: induction for rationals??

Plato is correct, but I feel a little more should be stated about the topic. When induction is first introduced, it can either be proven as a consequence of other axioms, or it may be given as an axiom on its own.

Should you desire a method of proof "similar" to induction, it would require a different set of axioms. I have not thought about it enough, but rather than proving a base case and a single induction step, perhaps an axiomatization could include the following:

P(0)
$a,b\in \mathbb{N}$
$P\left(\dfrac{a}{b}\right) \Rightarrow \left[ P\left(\dfrac{a+1}{b}\right) \text{ and } P\left(\dfrac{a}{b+1}\right) \right]$
Finally for any $x\in \mathbb{Q}$
$P(x)\Rightarrow P(-x)$

With a well-worded set of axioms (and some care to ensure there are no degenerate cases), this may suffice as something that looks a bit like induction, but may work for rational numbers.

5. Re: induction for rationals??

errm... thank you. I need to get my head around whether I really understand what a well ordered set is!

6. Re: induction for rationals??

You can use the method of induction to prove sonething for all rationals, but it will not use a single ever-increasing sequence of rationals. Any scheme that covers all rationals will suffice. Here's one for the positive rationals.

7. Re: induction for rationals??

Because the set of all rational numbers is countable there exist a one-to-one mapping of the positive integers to the rational numbers. One certainly can construct such an mapping (there are infinitely many), prove proposition P for rational number that "1" is mapped into, then prove that "if P(r1) is true where positive integer k is mapped to r1 then P(r2)) is true where k+1 is mapped to r2. Of course the "details", actually writing out such a one-to-one mapping in order to determine exactly what rational r corresponds to positive integer k, can be extremely difficult.

8. Re: induction for rationals??

Originally Posted by Archie
Plato and SlipEternal are decidely wrong, except on a very narrow definition of induction.

You can use the method of induction to prove sonething for all rationals, but it will not use a single ever-increasing sequence of rationals. Any scheme that covers all rationals will suffice. Here's one for the positive rationals.
While possible, it is not practical to use induction on an arbitrary mapping. The mapping you have chosen is not (and cannot be) canonical. This is because the rationals are not well-ordered. While you chose one particular well-ordering, it is incredibly unlikely that a particular statement will be provable by induction over the mapping. So, that kinda makes you wrong. Very wrong. Decidedly wrong. Sorry, Archie.

9. Re: induction for rationals??

In practice in that scheme you'd use induction for $\frac m n$ over $(n+m)$ and then for either $m$ or $n$. It obviously covers all the rationals - it's just a two step process.

I earlier gave a different example of a construction that uses induction to prove something over the rationals.

Sorry SlipEternal, the claim that you can't use induction for rationals is wrong, decidedly wrong, obviously wrong.

It's interesting that Plato's argument is based on the rationals not being well ordered while you admit that such well-orderings exist.

10. Re: induction for rationals??

Originally Posted by Archie
In practice in that scheme you'd use induction for $\frac m n$ over $(n+m)$ and then for either $m$ or $n$. It obviously covers all the rationals - it's just a two step process.

I earlier gave a different example of a construction that uses induction to prove something over the rationals.

Sorry SlipEternal, the claim that you can't use induction for rationals is wrong, decidedly wrong, obviously wrong.

It's interesting that Plato's argument is based on the rationals not being well ordered while you admit that such well-orderings exist.
I did not say that it did not cover all rationals. I said that your method of induction is not supported. Using induction over n+m is not distinct. This would require additional proof that such an induction actually proves a claim. It is not "obvious" that it would work. You are assuming the complete absence of degenerate cases. That assumption is not obvious. I am not even sure that it would work. You are building new axioms for induction as you go and claiming they are automatically supported, "obviously". That is not only wrong, it is not how math works. Math works by proof. Show me how you would prove that your axioms for induction lead to correct proofs, and I will believe you. Until then, it is anything but obvious.

Any set can be well-ordered. I said that the rationals are NOT well-ordered, but could be. The well-ordering is NOT canonical. You seem to enjoy ignoring any statements that do not support your case.

11. Re: induction for rationals??

No, I am talking about how induction is used in practice to prove things for the rationals. It doesn't require any special axioms because rationals are just ordered pairs of integers. Yes, care has to be taken over the interactions between each element of the pair, but it still works.

12. Re: induction for rationals??

Originally Posted by Archie
No, I am talking about how induction is used in practice to prove things for the rationals. It doesn't require any special axioms because rationals are just ordered pairs of integers. Yes, care has to be taken over the interactions between each element of the pair, but it still works.
Saying that "in practice, induction is used over the natural numbers where classes of rational numbers (such as all rational numbers n/m when n+m = k) are evaluated all at once" is very different from what the OP is asking for. You are using standard induction to prove things about sets that are not the natural numbers. Neither Plato nor I implied that was impossible. We implied that what the OP asked for was not possible under the standard axiomatization for induction.

13. Re: induction for rationals??

I am not following this argument.

Archie says you may be able to prove a statement P(r) about all positive integers with the following argument

$P(1 \div 1) \text { is true.}$ Step 1.

$\therefore \exists \ k \in \mathbb N^+ \text { such that } P(1 \div k) \text { is true.}$

$\therefore P\{1 \div (k + 1)\} \text { is true.}$ Step 2.

$\therefore n \in \mathbb N^+ \implies P(1 \div n) \text { is true.}$ First induction step.

$\because \ P(1 \div n) \text { is true for any } n \in \mathbb N+ \therefore \exists\ m \in \mathbb N^+ \text { such that }P(m \div n) \text { is true.}$

$\therefore P\{(m + 1) \div n\} \text { is true.}$ Step 3.

$\therefore p, n \in \mathbb N^+ \implies P(p \div n) \text { is true.}$ Final induction step.

Then Plato and SlipEternal, who are certainly better mathematicians than I am and far, far better trained, say that proof is invalid, indeed that it is "obviously wrong."

Sorry. I do not see what in the world is wrong with it if it can be done. Is what is being said is that it is "definitively wrong" if it can be done? If so, why? Or is what is being said is that it is not necessarily possible to do it?

14. Re: induction for rationals??

Plato and SlipEternal (not skipjack) are saying that there is no direct analogue to inductions that works on the rationals by which I understand that they are restricting the induction step reasoning to something like $$P(q) \implies P(r)$$ for some fixed relationship between $q$ and $r$.

I agree with that, but I don't think that's what the OP asked. The OPs example follows exactly the idea you summarised: using induction on the integers to get all results of the form $\frac1n$. I then extended it to demonstrate covering all rationals $\frac m n$, again as per your summary.

SlipEternal doesn't seem to countenance the idea that this is what the OP was interested in.

15. Re: induction for rationals??

Originally Posted by Archie
Plato and SlipEternal (not skipjack) are saying that there is no direct analogue to inductions that works on the rationals by which I understand that they are restricting the induction step reasoning to something like $$P(q) \implies P(r)$$ for some fixed relationship between $q$ and $r$.

I agree with that, but I don't think that's what the OP asked. The OPs example follows exactly the idea you summarised: using induction on the integers to get all results of the form $\frac1n$. I then extended it to demonstrate covering all rationals $\frac m n$, again as per your summary.

SlipEternal doesn't seem to countenance the idea that this is what the OP was interested in.
I suppose without further input from the OP, it is entirely possible that I (and likely Plato) are misunderstanding the OP.

Page 1 of 2 12 Last