Page 1 of 2 12 LastLast
Results 1 to 15 of 29
Like Tree4Thanks

Thread: induction for rationals??

  1. #1
    Member
    Joined
    May 2010
    Posts
    110

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,837
    Thanks
    592

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,485
    Thanks
    2730
    Awards
    1

    Re: induction for rationals??

    Quote Originally Posted by rodders View Post
    Something occurred to me about the method of proof of induction and i don't know if there is something in this
    Quote Originally Posted by rodders View Post
    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.
    Thanks from rodders
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    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.
    Thanks from rodders
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2010
    Posts
    110

    Re: induction for rationals??

    errm... thank you. I need to get my head around whether I really understand what a well ordered set is!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,837
    Thanks
    592

    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.
    Last edited by topsquark; Nov 27th 2017 at 05:39 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,449
    Thanks
    2892

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: induction for rationals??

    Quote Originally Posted by Archie View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,837
    Thanks
    592

    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.
    Last edited by Archie; Nov 27th 2017 at 07:05 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: induction for rationals??

    Quote Originally Posted by Archie View Post
    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.
    Last edited by SlipEternal; Nov 27th 2017 at 07:16 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,837
    Thanks
    592

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: induction for rationals??

    Quote Originally Posted by Archie View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,749
    Thanks
    808

    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?
    Last edited by JeffM; Nov 27th 2017 at 11:25 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,837
    Thanks
    592

    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: induction for rationals??

    Quote Originally Posted by Archie View Post
    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.
    Thanks from Archie
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Rationals
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Mar 3rd 2010, 05:02 AM
  2. Function Continuous on Rationals but not on Rationals
    Posted in the Differential Geometry Forum
    Replies: 12
    Last Post: May 28th 2009, 09:49 AM
  3. proof by induction on rationals
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Jan 22nd 2009, 12:00 PM
  4. Please help with Rationals
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Apr 20th 2008, 06:24 PM
  5. Rationals
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Nov 6th 2007, 05:13 PM

/mathhelpforum @mathhelpforum