1. ## 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.

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.

2. ## Re: induction for rationals??

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

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.

3. ## Re: induction for rationals??

Originally Posted by SlipEternal
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.

4. ## Re: induction for rationals??

Originally Posted by SlipEternal
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 $\displaystyle P(1)$, $\displaystyle P(\frac1n) \implies P(\frac1{n+1})$, and $\displaystyle P(\frac{m}{n}) \implies P(\frac{m+1}{n})$ for all natural numbers $\displaystyle m$ and $\displaystyle 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 $\displaystyle (m,n)$ on a chess board are black when $\displaystyle (m+n)$ is even (where $\displaystyle (1,1)$ is black). Sure, there are many proofs, but one simple one is by induction on $\displaystyle m$ and $\displaystyle n$.

5. ## Re: induction for rationals??

Originally Posted by Archie
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 $\displaystyle P(1)$, $\displaystyle P(\frac1n) \implies P(\frac1{n+1})$, and $\displaystyle P(\frac{m}{n}) \implies P(\frac{m+1}{n})$ for all natural numbers $\displaystyle m$ and $\displaystyle 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 $\displaystyle (m,n)$ on a chess board are black when $\displaystyle (m+n)$ is even (where $\displaystyle (1,1)$ is black). Sure, there are many proofs, but one simple one is by induction on $\displaystyle m$ and $\displaystyle 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 $\displaystyle 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 $\displaystyle 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.

6. ## Re: induction for rationals??

Well limit sets are a closed book to me. I was talking about the specific case.

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

8. ## Re: induction for rationals??

I honestly don't understand what your concern is. If I demonstrate that $\displaystyle \mathcal{P}(1)$ is true and that $\displaystyle \mathcal{P}(\tfrac1n) \implies \mathcal{P}(\tfrac1{n+1})$ and that $\displaystyle \mathcal{P}(\tfrac m a) \implies \mathcal{P}(\tfrac{m+1}a)$ for all natural numbers $\displaystyle a,m,n$ it follows that $\displaystyle \mathcal{P}(\frac m n)$ is true for all positive rationals $\displaystyle \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 $\displaystyle \mathcal{Q}(1,1)$ is true and that $\displaystyle \mathcal{Q}(1,n) \implies \mathcal{Q}(1,n+1)$ and that $\displaystyle \mathcal{Q}(m,a) \implies \mathcal{Q}(m+1,a)$. If that doesn't prove that $\displaystyle \mathcal{Q}(m,n)$ is true for all natural numbers $\displaystyle m,n$, then induction on the natural numbers is broken.

9. ## Re: induction for rationals??

Originally Posted by Archie
I honestly don't understand what your concern is. If I demonstrate that $\displaystyle \mathcal{P}(1)$ is true and that $\displaystyle \mathcal{P}(\tfrac1n) \implies \mathcal{P}(\tfrac1{n+1})$ and that $\displaystyle \mathcal{P}(\tfrac m a) \implies \mathcal{P}(\tfrac{m+1}a)$ for all natural numbers $\displaystyle a,m,n$ it follows that $\displaystyle \mathcal{P}(\frac m n)$ is true for all positive rationals $\displaystyle \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 $\displaystyle \mathcal{Q}(1,1)$ is true and that $\displaystyle \mathcal{Q}(1,n) \implies \mathcal{Q}(1,n+1)$ and that $\displaystyle \mathcal{Q}(m,a) \implies \mathcal{Q}(m+1,a)$. If that doesn't prove that $\displaystyle \mathcal{Q}(m,n)$ is true for all natural numbers $\displaystyle 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.

10. ## Re: induction for rationals??

In the rationals, not so much, but in the equivalent $\displaystyle \mathbb N^2$ it certainly is. Proofs of behaviour of coupled sequences defined by recurrance formulas are one example.

12. ## Re: induction for rationals??

What I'm talking about doesn't require transfinite numbers. We are talking about rationals.

13. ## Re: induction for rationals??

Originally Posted by Archie
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.

14. ## Re: induction for rationals??

Originally Posted by SlipEternal
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.

Page 2 of 2 First 12