Page 2 of 2 FirstFirst 12
Results 16 to 29 of 29
Like Tree4Thanks

Thread: induction for rationals??

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

    Re: induction for rationals??

    Archie, thanks for pointing out my mistake about who was arguing what. I have now fixed my original post in that regard.

    If the argument is about what the OP was asking, I suggest we ask the OP.

    Plato's response, however, reads to me as though he is saying that because there is no least positive rational, the scheme of proof that you proposed in the post preceding his is necessarily invalid. Perhaps I am misreading, but if that is his argument, I simply do not see it. The scheme proposed depends on the ordering of the natural numbers applied twice.

    SlipEternal seems to me to be arguing that there may be no ordering of the rationals where a similar proof will work. That may be plausible, but I am not sure you ever meant to imply it. If that is his argument and you are disputing THAT, I don't see that he has proved it or that you have refuted it. So I am still confused.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Quote Originally Posted by JeffM View Post
    Archie, thanks for pointing out my mistake about who was arguing what. I have now fixed my original post in that regard.

    If the argument is about what the OP was asking, I suggest we ask the OP.

    Plato's response, however, reads to me as though he is saying that because there is no least positive rational, the scheme of proof that you proposed in the post preceding his is necessarily invalid. Perhaps I am misreading, but if that is his argument, I simply do not see it. The scheme proposed depends on the ordering of the natural numbers applied twice.

    SlipEternal seems to me to be arguing that there may be no ordering of the rationals where a similar proof will work. That may be plausible, but I am not sure you ever meant to imply it. If that is his argument and you are disputing THAT, I don't see that he has proved it or that you have refuted it. So I am still confused.
    Every set can be well-ordered. This is known as the Well-Ordering Theorem (also known as Zermelo's Theorem), and it is equivalent to the Axiom of Choice. I was not implying, nor do I believe, that it is impossible to order the rationals. What I stated is that there is no canonical ordering of the rationals. Mathematical Induction (Induction using natural numbers) is axiomatic. It works the exact same way every time. To apply an induction argument when dealing with sets of rational numbers, one must create "classes" of rational numbers that are assigned to each natural number. Or one must create a one-to-one mapping from the natural numbers to the rationals. These are ways of using induction over natural numbers for rational numbers.

    The approach mentioned by Archie is not a method of mathematical induction. One could (in theory) create axioms that would support it, but they may require special care to avoid degenerate cases. In the case where you have P(1/k) implies P(1/(k+1)), then P(a/k) implies P((a+1)/k), you are essentially creating a partition of the rationals where you apply induction to all elements of the partition. Essentially, you are creating a limit set P(a/k) where k is a natural number and then attempting to prove that regardless of the denominator, you can prove P((a+1)/k). This means that every case you are attempting to prove a proposition for an infinite set of numbers, which seems as complicated (if not more complicated) than the more preferable direct proof. So, perhaps it is not that this does not work, but that it is not a useful method of proof.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Quote Originally Posted by SlipEternal View Post
    I suppose without further input from the OP, it is entirely possible that I (and likely Plato) are misunderstanding the OP.
    It's also possible that I am. But whichever it is, we are both right in the context about which we are speaking.
    Last edited by Archie; Nov 27th 2017 at 01:59 PM.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Quote Originally Posted by SlipEternal View Post
    The approach mentioned by Archie is not a method of mathematical induction.
    It's two applications of it. Why this should cause you so much trouble, I fail to see. There is no need for special axioms at all. If I prove P(1), P(\frac1n) \implies P(\frac1{n+1}), and P(\frac{m}{n}) \implies P(\frac{m+1}{n}) for all natural numbers m and n, the proposition is clearly proved for all positive rationals. It's a very simple idea.

    I never claimed that it was the best approach, but it's not as bad as you are making out. An analagous problem would be to prove that squares (m,n) on a chess board are black when (m+n) is even (where (1,1) is black). Sure, there are many proofs, but one simple one is by induction on m and n.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Quote Originally Posted by Archie View Post
    It's two applications of it. Why this should cause you so much trouble, I fail to see. There is no need for special axioms at all. If I prove P(1), P(\frac1n) \implies P(\frac1{n+1}), and P(\frac{m}{n}) \implies P(\frac{m+1}{n}) for all natural numbers m and n, the proposition is clearly proved for all positive rationals. It's a very simple idea.

    I never claimed that it was the best approach, but it's not as bad as you are making out. An analagous problem would be to prove that squares (m,n) on a chess board are black when (m+n) is even (where (1,1) is black). Sure, there are many proofs, but one simple one is by induction on m and n.
    Perhaps it is my experience dealing with limit sets that gives me pause. You are applying induction to an infinite collection of sets. Whenever you do something like that, special care is needed to ensure that the limit set is really what you think it is. Being less than careful with my limit sets, I had an occasion where my proof generated an invalid conclusion. It took my colleagues and I several days to discover that the limit set I created did not have the expected properties that I had "proven" it would have. This was not immediately apparent, and for several days after, I kept returning to the proof thinking that it had to be correct, and there was some other problem that I was missing.

    If you are not sure how this type of induction is related to limit sets, consider this:

    Let A = \{r \in \mathbb{Q}: P(r) \} and you wanted to describe A as you went through the proof, you claim you wind up with A = \bigcup_{m\ge 1} \bigcup_{n\ge 1} \left\{ \dfrac{m}{n} \right\} = \mathbb{Q}_{>0}. Upon more reflection, I realize that in this instance, the limit set does end up being what you claim, but to say that it is obvious is to not truly grasp the dangers of limit sets.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Well limit sets are a closed book to me. I was talking about the specific case.
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Member
    Joined
    May 2010
    Posts
    110

    Re: induction for rationals??

    I would like like to see a proof like this in action.
    Is there a result that is only true for rational numbers and if so will induction work? I guess thats what i am trying to get my head around.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    I honestly don't understand what your concern is. If I demonstrate that \mathcal{P}(1) is true and that \mathcal{P}(\tfrac1n) \implies \mathcal{P}(\tfrac1{n+1}) and that \mathcal{P}(\tfrac m a) \implies \mathcal{P}(\tfrac{m+1}a) for all natural numbers a,m,n it follows that \mathcal{P}(\frac m n) is true for all positive rationals \frac m n. If some condition exists that makes one of those proofs fail, that is a failure of the particular proof not of the concept.

    It's no different to demonstrating that \mathcal{Q}(1,1) is true and that \mathcal{Q}(1,n) \implies \mathcal{Q}(1,n+1) and that \mathcal{Q}(m,a) \implies \mathcal{Q}(m+1,a). If that doesn't prove that \mathcal{Q}(m,n) is true for all natural numbers m,n, then induction on the natural numbers is broken.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Quote Originally Posted by Archie View Post
    I honestly don't understand what your concern is. If I demonstrate that \mathcal{P}(1) is true and that \mathcal{P}(\tfrac1n) \implies \mathcal{P}(\tfrac1{n+1}) and that \mathcal{P}(\tfrac m a) \implies \mathcal{P}(\tfrac{m+1}a) for all natural numbers a,m,n it follows that \mathcal{P}(\frac m n) is true for all positive rationals \frac m n. If some condition exists that makes one of those proofs fail, that is a failure of the particular proof not of the concept.

    It's no different to demonstrating that \mathcal{Q}(1,1) is true and that \mathcal{Q}(1,n) \implies \mathcal{Q}(1,n+1) and that \mathcal{Q}(m,a) \implies \mathcal{Q}(m+1,a). If that doesn't prove that \mathcal{Q}(m,n) is true for all natural numbers m,n, then induction on the natural numbers is broken.
    I honestly don't understand what you are saying here. The OP is asking for an example when this induction will work. And then you say, "Yes, it will work". That is not an example. I am wracking my head trying to think of an example where this type of induction is useful. I am not coming up with anything.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    In the rationals, not so much, but in the equivalent \mathbb N^2 it certainly is. Proofs of behaviour of coupled sequences defined by recurrance formulas are one example.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    What I'm talking about doesn't require transfinite numbers. We are talking about rationals.
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Quote Originally Posted by Archie View Post
    What I'm talking about doesn't require transfinite numbers. We are talking about rationals.
    At the bottom, it gives examples of when transfinite induction is useful. You can have Borel sets of rational numbers where perhaps the induction you suggested would have value.
    Thanks from Archie
    Follow Math Help Forum on Facebook and Google+

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

    Re: induction for rationals??

    Quote Originally Posted by SlipEternal View Post
    I honestly don't understand what you are saying here. The OP is asking for an example when this induction will work. And then you say, "Yes, it will work". That is not an example. I am wracking my head trying to think of an example where this type of induction is useful. I am not coming up with anything.
    The OP asked whether a proposed method of proof was valid. After a fair amount of discussion, I thought we had reached the conclusion that such a a method is valid, but there was some debate (or at least doubt) whether the method could ever be efficient. Now we are being asked by the OP to provide an example of a proof using such a method. Given that the OP proposed the method, that strikes me as a very strange request. But I agree that repeating that the method would be valid if used goes nowhere toward proving the utility of the method.

    Part of my difficulty in responding to the NEW question comes from my lack of knowledge of theorems about the rational numbers. I might suggest starting with some basics, like proving that addition on the rationals is closed. Another possible test might be the rational root theorem.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

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