Inducing on Q+: Is it Possible?

[Treadstone 71]

Is it possible to induce on Q+ by showing that a statement is true for n=1 and (n/m=>(n+1)/m AND n/m=>n/(m+1))?

 

[JasonRox]

Is it possible to induce on Q by showing that a statement is true for n=1 and (n=>n+1 AND n=>n/(n+1))?

First, have you tried induction on the integers?

Positive and Negative.

 

[Treadstone 71]

Yes, I have used induction many times before on the integers. My question is whether it is possible prove that a statement is true for all (positive) rational numbers, by induction, in principle.

 

[JasonRox]

Yes, I have used induction many times before on the integers. My question is whether it is possible prove that a statement is true for all (positive) rational numbers, by induction, in principle.

Yes, that is entirely possible.

 

[Treadstone 71]

Excellent, thanks for the reply.

 

[matt grime]

Any set that can be well ordered can be inducted upon, and every set can be well ordered (if we accept the axiom of choice), it's just that it's difficult in general, though easier for the rationals since they are lexicographically ordered naturally. The usual way to do it is to assume that there is a set of counter examples, by the well ordering there is a minimal one and we try to deduce a deduction. FOr example one can show that the nCr function is integer valued by induction like this.