# Mathematical Induction over real numbers **URL:** \ **Category:** Factual Questions\ **Created:** [October 22, 2005, 6:33am UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407 "2005-10-22T06:33:28Z")\ **Posts on this page:** 17\ **Page:** 1
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [October 22, 2005, 6:33am UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/1 "2005-10-22T06:33:28Z")
The **Kozumic** thread reminded me of something I figured out when I was small and I was wondering if it was valid. When we were in HS, we were taught Proof by Mathematical Induction over positive integers that wen’t something like: Given a function F(x) if F(1) is true and if, given F(n) is true, F(n+1) is true, then it must be true for all x = 1, 2, 3… However, I came up with my own version of MI that should work for all real numbers that goes something like this: Given a function F(x) if (F(1) is true and if, given F(n) is true, F(n/2) is true and if, given F(n[sub]1[/sub]) is true and F(n[sub]2[/sub]) is true, F(n[sub]1[/sub] + n[sub]2[/sub]) is true then it must hold true for all positive real numbers. Is this a valid proof and has it ever been used before? PS: I am not a crank ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [October 22, 2005, 6:55am UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/2 "2005-10-22T06:55:05Z")
This won’t cover all of the real numbers. As it stands, these criteria are not enough to demonstrate that, for example, F(pi) is true. What your criteria do is show that F(x) is true only for some subset of the rational numbers. (Not even all of the rationals will be covered. I don’t believe, for example, that they demonstrate the truth of F(1/3)). I believe your induction only covers the positive rationals whose denominator is a power of 2. These numbers are dense in the positive reals, however, so if we extend it by one more property: Whenever {x[sub]n[/sub]} is a convergent sequence in the positive reals and F(x[sub]n[/sub]) is true for all n, we also have F(lim x[sub]n[/sub]) is true. Then this will complete the criteria needed to cover all of the positive reals. ---
**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\ **Post date:** [October 22, 2005, 6:58am UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/3 "2005-10-22T06:58:43Z")
No, the proposition would be true for all the numbers that you can generate by those two rules. They would be the positive rational numbers that have a terminating expression in binary notation. For example, you cannot reach 1/3 with those operations, though you can approach it as closely as you wish, ---
**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\ **Post date:** [October 22, 2005, 7:00am UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/4 "2005-10-22T07:00:43Z")
If I had previewed, I would have seen that **Cabbage** had already said essentially the same as I did. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [October 22, 2005, 1:19pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/5 "2005-10-22T13:19:27Z")
So is there a way to do MI over reals without introducing limits? ---
**Author:** ![Wendell\_Wagner](https://avatars.discourse-cdn.com/v4/letter/w/8491ac/32.png) [@Wendell\_Wagner](https://boards.straightdope.com/u/Wendell_Wagner)\ **Post date:** [October 22, 2005, 2:17pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/6 "2005-10-22T14:17:26Z")
No, it’s impossible to use even a variant form of induction to prove something about the real numbers (unless your variant of induction is so different that it doesn’t deserve the name of induction.) Let’s suppose that the general form of a variant of induction is that you start with a property that’s true for all members of a set that’s finite or at least countably infinite. Suppose in this variant of induction at each new step you could prove that if the property is true of any number n, then it is also true for some set of other numbers related to n, where this set is also finite or at least countably infinite. Then you still can’t reach all the real numbers, since at each step you’re adding at most a countably infinite set of numbers to the set of numbers which satisfy the property. You will never have an uncountable set of numbers satisfying the property, even if you continue forever the adding of new sets of numbers to the set of numbers satisfying it, since there are only a countably infinite number of steps in an induction. A countable infinite number times a countably infinite number is still a countably infinite number. The number of real numbers is uncountably infinite and can’t be all reached by any such method. For instance, suppose that you start with the proposition that a certain property is true of all the integers. Suppose further that you say that if the property is true of a number n, then it is also true for n + (1/10)^m, where m is an integer. Then your property is true for all real numbers with terminating decimal expansions. This is not all real numbers, and it’s not uncountably infinite. It doesn’t matter than you’re starting with a countable infinite number of numbers with the property. It doesn’t matter that at each step you’re adding a countable infinite number of numbers to the set of numbers that satisfy the property. You’re still only going to do a countably infinite number of steps and at each step you only add a countably infinite number of new numbers to the set of numbers satisfying the property. ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [October 22, 2005, 2:22pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/7 "2005-10-22T14:22:33Z")
As people have said, it would be hard to come up with a variant of this that would cover irrational real numbers. Can anyone think of a pattern that would cover all irrationals?? 🙂 ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [October 22, 2005, 4:00pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/8 "2005-10-22T16:00:08Z")
Try this: Prove P(x) is true for x in [0,1) Prove P(x+1) is true if P(x) is true. Conclude that P(x) is true for all x \>=0. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 22, 2005, 4:22pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/9 "2005-10-22T16:22:04Z")
> [@ftg](#): > > Try this: > > Prove P(x) is true for x in [0,1) > > Prove P(x+1) is true if P(x) is true. > > Conclude that P(x) is true for all x \>=0. That’s pretty much exactly what I was going to post. To cover all reals, of course, you’d need to show that P(x) -\> P(x - 1). Is this method a piece of trivia, or is it actually used? ---
**Author:** ![Topologist](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/topologist/32/3208_2.png) [@Topologist](https://boards.straightdope.com/u/Topologist)\ **Post date:** [October 22, 2005, 5:59pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/10 "2005-10-22T17:59:37Z")
> [@Wendell Wagner](#): > > No, it’s impossible to use even a variant form of induction to prove something about the real numbers (unless your variant of induction is so different that it doesn’t deserve the name of induction.) There is such a variant, called [transfinite induction](http://en.wikipedia.org/wiki/Transfinite_induction). To use it to prove things about the reals, you have to assume that you can well-order them, which you can do if you accept the Axiom of Choice. (Not that I don’t, but people like to be aware that they’re using it.) A well-ordering is an ordering in which every subset has a least element. The usual ordering of the reals is obviously not one: consider (0,1], for example, or the set of all reals. But, if you assume the Axiom of Choice, then any set can be well-ordered. Transfinite induction says that, if you have a well-ordered set and a property P such that, if P(y) is true for all y \< x, then P(x) is true, then P is true of all elements of the set. Is this useful for proving things about all real numbers? Depends on what your property P is, since we have little control over what the well-ordering looks like. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [October 22, 2005, 6:50pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/11 "2005-10-22T18:50:16Z")
> [@Wendell Wagner](#): > > No, it’s impossible to use even a variant form of induction to prove something about the real numbers (unless your variant of induction is so different that it doesn’t deserve the name of induction.) Let’s suppose that the general form of a variant of induction is that you start with a property that’s true for all members of a set that’s finite or at least countably infinite. Suppose in this variant of induction at each new step you could prove that if the property is true of any number n, then it is also true for some set of other numbers related to n, where this set is also finite or at least countably infinite. Then you still can’t reach all the real numbers, since at each step you’re adding at most a countably infinite set of numbers to the set of numbers which satisfy the property. You will never have an uncountable set of numbers satisfying the property, even if you continue forever the adding of new sets of numbers to the set of numbers satisfying it, since there are only a countably infinite number of steps in an induction. A countable infinite number times a countably infinite number is still a countably infinite number. The number of real numbers is uncountably infinite and can’t be all reached by any such method. > > For instance, suppose that you start with the proposition that a certain property is true of all the integers. Suppose further that you say that if the property is true of a number n, then it is also true for n + (1/10)^m, where m is an integer. Then your property is true for all real numbers with terminating decimal expansions. This is not all real numbers, and it’s not uncountably infinite. It doesn’t matter than you’re starting with a countable infinite number of numbers with the property. It doesn’t matter that at each step you’re adding a countable infinite number of numbers to the set of numbers that satisfy the property. You’re still only going to do a countably infinite number of steps and at each step you only add a countably infinite number of new numbers to the set of numbers satisfying the property. No, I don’t think that’s true. I think the step: if, given F(n1) is true and F(n2) is true, F(n1 + n2) is true means that your adding more than a countably infinite set. Both n1 and n2 are countably infinite sets and this step requires a permutation of two countably infinite sets. To put it another way, restricting ourselves to (0, 1] to make the math a bit simpler, my version of MI basically states that it can be proven for any non-terminating binary decimal (what is a binary decimal meant to be called? a bicimal?), the condition will hold. I’m pretty sure that the original cantor proof of uncountable infinities used precisely non-terminating decimal sequences to prove uncountability. And upon reflection, I don’t think the limit step is neccesary. Aren’t real numbers defined as a non-terminating decimal? Therefore, wouldn’t they be equivilant? Also: going back to standard MI, what if F(X) is “that the size of the set {0…X} is finite”. F(1) is definately true… If F(X) is true, F(X+1) is also true… ergo, we conclude that the set of integers is finite… waitaminute! what’s going on here? ---
**Author:** ![Topologist](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/topologist/32/3208_2.png) [@Topologist](https://boards.straightdope.com/u/Topologist)\ **Post date:** [October 22, 2005, 7:09pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/12 "2005-10-22T19:09:21Z")
> [@Shalmanese](#): > > if, given F(n1) is true and F(n2) is true, F(n1 + n2) is true > > means that your adding more than a countably infinite set. Both n1 and n2 are countably infinite sets and this step requires a permutation of two countably infinite sets. Aren’t n1 and n2 numbers, not sets?? > [@](#): > > To put it another way, restricting ourselves to (0, 1] to make the math a bit simpler, my version of MI basically states that it can be proven for any non-terminating binary decimal. What your version appears to do is show that something is true for every _terminating_ binary decimal, which gives you the set of all rational numbers with denominators a power of 2, as others have noted. > [@](#): > > Also: going back to standard MI, what if F(X) is “that the size of the set {0…X} is finite”. F(1) is definately true… If F(X) is true, F(X+1) is also true… ergo, we conclude that the set of integers is finite… waitaminute! what’s going on here? You’ve just proved that _for all integers X_, the set of integers from 0 to X is finite. That’s true. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 22, 2005, 7:10pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/13 "2005-10-22T19:10:05Z")
> [@Shalmanese](#): > > No, I don’t think that’s true. I think the step: > > if, given F(n1) is true and F(n2) is true, F(n1 + n2) is true > > means that your adding more than a countably infinite set. Both n1 and n2 are countably infinite sets and this step requires a permutation of two countably infinite sets. Not unless you have an infinite number of base cases. > [@](#): > > To put it another way, restricting ourselves to (0, 1] to make the math a bit simpler, my version of MI basically states that it can be proven for any non-terminating binary decimal (what is a binary decimal meant to be called? a bicimal?), the condition will hold. I’m pretty sure that the original cantor proof of uncountable infinities used precisely non-terminating decimal sequences to prove uncountability. No, you’ve only proven it for terminating binary numbers. If you don’t think that’s true, please explain in detail how your method would be used to prove statements about 1/3 or 0. > [@](#): > > Also: going back to standard MI, what if F(X) is “that the size of the set {0…X} is finite”. F(1) is definately true… If F(X) is true, F(X+1) is also true… ergo, we conclude that the set of integers is finite… waitaminute! what’s going on here? Your conclusion is bad. All that you’ve proven is that the set {0…X] is finite for any natural number X. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 22, 2005, 7:12pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/14 "2005-10-22T19:12:11Z")
> [@Topologist](#): > > What your version appears to do is show that something is true for every _terminating_ binary decimal, which gives you the set of all rational numbers with denominators a power of 2, as others have noted. His version is a little more general than that, working for rationals that can be expressed as finite sums of negative powers of 2. ---
**Author:** ![Wendell\_Wagner](https://avatars.discourse-cdn.com/v4/letter/w/8491ac/32.png) [@Wendell\_Wagner](https://boards.straightdope.com/u/Wendell_Wagner)\ **Post date:** [October 22, 2005, 11:19pm UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/15 "2005-10-22T23:19:22Z")
Topologist, has transfinite induction ever been used to prove anything useful? Shalmanese writes: \> I’m pretty sure that the original cantor proof of uncountable infinities used \> precisely non-terminating decimal sequences to prove uncountability. Yes, and the example I gave only reached all terminating decimal sequences. The Cantor proof of the non-countability of the real numbers uses the fact that they are represented by non-terminating decimal sequences. The point that you go from terminating decimal sequences to non-terminating decimal sequences is the point that you go from countable infinite sets to non-countable ones. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [October 23, 2005, 2:20am UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/16 "2005-10-23T02:20:25Z")
> [@Wendell Wagner](#): > > Topologist, has transfinite induction ever been used to prove anything useful? There are lots of proofs in general topology and set theory which use transfinite induction (probably other fields as well, but these are what I’m most familiar with). For example, in his paper _Homogeneity Problems in the Theory of Cech Compactifications_, Walter Rudin uses transfinite induction to prove a certain property of the Stone-Cech remainder of the natural numbers. > [@ultrafilter](#): > > His version is a little more general than that, working for rationals that can be expressed as finite sums of negative powers of 2. Isn’t that the same thing? For example, a/2[sup]m[/sup] + b/2[sup]n[/sup] = (2[sup]n[/sup]a + 2[sup]m[/sup]b)/2[sup]m+n[/sup] In other words, a finite sum of negative powers of 2 is still a rational whose denominator is a power of 2. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 23, 2005, 3:06am UTC](https://boards.straightdope.com/t/mathematical-induction-over-real-numbers/327407/17 "2005-10-23T03:06:34Z")
> [@Cabbage](#): > > Isn’t that the same thing? For example, > > a/2[sup]m[/sup] + b/2[sup]n[/sup] = (2[sup]n[/sup]a + 2[sup]m[/sup]b)/2[sup]m+n[/sup] > > In other words, a finite sum of negative powers of 2 is still a rational whose denominator is a power of 2. Yeah, I goofed. If that’s the dumbest thing I say today, I’ll go to bed happy. > [@Wendell Wagner](#): > > Topologist, has transfinite induction ever been used to prove anything useful? It plays the same role in the theory of transfinite numbers that normal induction plays in the theory of natural numbers.