No form of Induction for Real Numbers


By Anonymous on Friday, June 01, 2001 - 09:29 pm:
In proving something such as 2n > n3 for n10, real n, can it be done through some sort of continuous induction (i.e. instead of showing that it holds true as nn+1, showing that it holds true as nn+a, where a is a positive real)? Or, in this case, can one simply argue that the functions are continuous, and it therefore holds once you've shown it for nn+1?
By Kerwin Hui (Kwkh2) on Friday, June 01, 2001 - 10:50 pm:

Unfortunately, given an inequality of continuous functions that is true for integers does not imply inequality holds for all reals. There are functions that have small peaks at, say n+½ for all n in Z , 0 at integers and continous in between, e.g., the function f(x)=sin2 (pi x). So we can prove that f(n) < 1/2 for all integral n, but the inequality f(x) < 1/2 for all real x is not true.

Kerwin


By Dan Goodman (Dfmg2) on Saturday, June 02, 2001 - 12:11 am:

There is no such thing as "continuous induction", because for induction to make sense you need to have the idea of a "next element in the series". You don't have this for the real numbers (or even for the rationals), because you can choose a to be arbitrarily small.

The next paragraph is a bit technical. I'm including it in case anyone's interested, but don't worry if it doesn't make any sense. Unless you're in your last year at university you probably don't need to worry about this stuff.

More precisely, you need a property called "wellfoundedness", which means that any non-empty set has a least element, this is true for the natural numbers, but not for the reals, the set 0 < x < 1 has no least element. It is possible to construct induction arguments on uncountable sets, but you need to order the elements in a very different way. For example, it is possible to prove using "transfinite induction" that you can partition R 3 using mutually non-parallel lines, i.e. you can find an uncountable set {La } (with a in some uncountable indexing set A) such that if a not equal to b implies La intersected with Lb is empty and La is not parallel to Lb .


By Jonathan Kirby (Pjk30) on Friday, June 08, 2001 - 09:46 pm:

There are models of set theory without the axiom of choice in which there is no well order for the reals. It follows (not immediately) that it is actually impossible to define a well ordering of the reals. You need to use the axiom of choice, which means that although you can prove that such a wellordering must exist, you cannot write one down, even in principle.

Going back to the original question, no, there is no continuous version of induction, for the reasons given. However, you can sometimes tackle the sort of question you posed in several steps, starting with induction. For example, you can prove by induction that what you want is true for integers. Then you need another argument to show that it's true for ratios of integers, that is for rational numbers. Then if your function is continuous, you can deduce it for all real numbers since the rationals are dense in the reals. This means that given any real number you can find a rational number as close as you like to it. That's probably not much help without an example, but I can't think of one off the top of my head. I'll try to think of one. Does anyone else have one?


By Kerwin Hui (Kwkh2) on Saturday, June 09, 2001 - 02:27 pm:

Here is an example: Suppose we want a map f:R-> R such that

f(x+y)=f(x)+f(y), f(xy)=f(x)f(y)

i.e. a field homomorphism. It is a trivial matter to see that f(0)=0, f(1)=1,f(-x)=-f(x) (assuming f is not identically zero), and so by induction we see that f(n)=n for all integer n.

Next, we find that f(m/n)=f(m)/f(n), and so f(x)=x for all rational x.

Now the crucial step: We see that f(x2 )=f(x)2 , so we conclude that the non-negative is mapped to the non-negative, and the negative to negative. Use this fact to show that f is monotone, and thus f(x)=x for all real x.

Kerwin