I'm really trying to sweep out the cobwebs in my memory here... The hardest thing to characterize in a theory of the integers is the "finite # of steps between any two integers". I.e., "finiteness" is the hard property, not infiniteness. This well-ordering property requires a _second order_ axiom, and hence integers require a "second order" theory. I think you may have to formally axiomatize what the properties of "ceil(x)" are. Presumably the integers are the range of ceil(), and then you have to see if you can find two numbers x,y, and two integers ceil(x)<ceil(y) such that there is no integer ceil(z), where ceil(x)<ceil(z)<ceil(y). Then define succ(ceil(x))=ceil(y), and start bootstrapping. --- I don't know if the concept of "algebraic integer" has any relevance here... At 11:22 AM 9/24/2008, James Propp wrote:
I wrote:
Using the well-orderedness property of the non-negative integers, plus the usual axioms of R as an ordered field and Z as an ordered ring, one can show that the the Archimedean property ("For all real x there exists an integer n with n > x") implies the existence of the ceiling function ("For all real x there exists a smallest integer n with n greater than or equal to x"). But does one need well-orderedness (or equivalently the axiom of induction) to prove this? That is, from the assumption that the ceiling function exists, can one derive the axiom of induction?
It seems to me that the proposition that the ceiling function exists has an intermediate character: it cannot be derived from the ordered field and ordered ring axioms, but neither is it strong enough to imply induction. Are there a couple of nice non-standard models of (R,Z,0,1,+,x,>) that make this completely patent?
Henry Baker replied:
I think it boils down to what it means (in your system) to be an "integer".
1. ceil(x) always returns an integer, so "integer" is the range of ceil().
2. integers are totally ordered.
3. between any two integers, there are only a finite number (including zero) of other integers. But this is basically well-ordering.
There are a number of interesting models which are less powerful than the real numbers. There are "real closed fields", which don't support integers (proof: real closed fields are decidable, whereas full integers get you undecidability). There are decidable models which include a "successor" function, and can support addition, and multiplication by a constant, but not multiplication of two arbitrary numbers.
I may be misinterpreting Henry's reply, but his first sentence seems to suggest that my question doesn't have a well-defined answer, but I maintain that the question I'm trying to ask does have a well-defined answer (even if I don't know yet what that answer is!), so I guess I didn't ask my question clearly enough.
Let me try to clarify things by asking, and then answering, an anologous but simpler question about the set of natural numbers (i.e. non-negative integers):
Question: Do the first two Peano postulates (0 is not the successor of any natural number; if two natural numbers are unequal, then their successors are unequal) imply the third (if S is any set of natural numbers that contains 0 and has the property that whenever it contains s it contains the successor of s, then S contains all natural numbers)?
Answer: No. As a counterexample, consider the model consisting of two copies of the (standard) natural numbers:
0 -> 1 -> 2 -> ...
0'-> 1'-> 2'-> ...
This satisfies the first two Peano postulates but not the third. We might call this a non-standard model of the first two Peano postulates, since it's not "the one we had in mind".
Note that the question "Do the first two Peano postulates imply the third?" is a well-defined question that a priori has a well-defined answer, even before one knows what the answer is.
To bring the notion of "meaning" into the story, we might paraphrase the question as: "Does every model that satisfies the first two Peano postulates also satisfy the third?" Each model that satisfies those two postulates gives a different answer to the query "What do you _mean_ by a natural number?" The answer to the question "Is the third Peano postulate true?" depends on what model one uses, i.e., on what the words in the postulates mean; but the answer to the question "Do the first two Peano postulates imply the third?" means "Does there exist a model of the first two Peano postulates in which the third Peano postulate fails?" and is not a question about what the words mean --- though you might poetically describe it as a question about all _possible_ meanings of the first two postulates.
So I believe the only issue is, was I sufficiently clear about what postulates I am assuming for Z and R? Assuming I was, then Henry or someone else should be able to tell me whether these postulates imply that every non-empty subset of Z that's bounded below has a least element.
Jim