Re: [math-fun] induction from completeness?
Josh Zucker writes:
I'm not sure exactly what you're taking as your axioms here, so I'm not sure if I'm on the right track at all.
They include all the usual first-order axioms governing N, Z, Q, and R, but no second-order axioms other than the axiom of completeness.
This last line isn't making sense to me. x is a lower bound for E, and it is an integer, so x is in E, and thus not in S.
I fumbled the end of that proof. Plus, the whole thing was too terse to be readable. I should have written: Let S be some set of positive integers that contains 1 and has the property that for all n in S, n+1 is also in S. Suppose there exists some positive integer that is not in S. Let x be the greatest lower bound of the set E of all such exceptional positive integers. If x is not an integer, then we can find x' > x with no integers between x and x', and x' is also a lower bound on E, contradicting the choice of x as the greatest lower bound. Hence x is an integer. It follows that x-1 and x+1 are integers, and we'll make the assumption that there are no integers between x-1 and x, or between x and x+1. Now since x is a lower bound for E (remember, it's the greatest lower bound of E) and since x+1 isn't a lower bound for E (since it's greater than the greatest lower bound of E), there must be some element of E in the interval [x,x+1). But there's only one integer in this interval, namely x, so we must have x in E. That is, the integer x is not in S. Since the set S is inductive, it follows that x-1 is not in S. Hence x-1 is in E. But then x is not a lower bound on E: contradiction. (I grant that it seems a bit odd to derive a fundamental property of Z from a property of R, especially if you accept Kronecker's ontology of number!) Jim Propp
On Fri, Sep 4, 2009 at 1:22 PM, James Propp<jpropp@cs.uml.edu> wrote:
It follows that x-1 and x+1 are integers, and we'll make the assumption that there are no integers between x-1 and x, or between x and x+1.
Is this based on the assumption that 1 is the smallest positive integer, which is what you said you needed as an additional assumption? This step seems like the key to the proof.
Now since x is a lower bound for E (remember, it's the greatest lower bound of E) and since x+1 isn't a lower bound for E (since it's greater than the greatest lower bound of E), there must be some element of E in the interval [x,x+1). But there's only one integer in this interval, namely x, so we must have x in E. That is, the integer x is not in S. Since the set S is inductive, it follows that x-1 is not in S. Hence x-1 is in E. But then x is not a lower bound on E: contradiction.
But x-1 might not be positive? Hm, some details to worry about. Also, couldn't we simplify this whole thing? Induction is equivalent to the statement that any set of positive integers has a least element. So all you need is the part that establishes that the greatest lower bound of E is itself in E, right? You don't even need the set S at all. Something like this: Let S be a set of positive integers. Let x be the greatest lower bound of S. Then, to quote you, If x is not an integer, then we can find x' > x with no integers between x and x', and x' is also a lower bound on E, contradicting the choice of x as the greatest lower bound. Hence x is an integer. So, done! But wait a minute. How do you know that for any x that is not an integer, you can find x' > x with no integers between x and x'? This seems also equivalent to what you're trying to prove. (I'm imagining counterexamples of the form "all fractions with denominator a power of 2".) --Joshua Zucker
participants (2)
-
James Propp -
Joshua Zucker