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?
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.
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,
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.
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??
There is such a variant, called 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.
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?
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.
You’ve just proved that for all integers X, the set of integers from 0 to X is finite. That’s true.
Not unless you have an infinite number of base cases.
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.
Your conclusion is bad. All that you’ve proven is that the set {0…X] is finite for any natural number X.
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.
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.
