Just to clarify: it should be emphasized that Henry's statements are referring (per convention) to the *elementary* theories of these structures, that is, what statements are true and false in the predicate calculus, where you can quantify over elements of the structure in question (real numbers, the integers, etc)., but you can't quantify over sets. Mathematicians talking about mathematics don't really pay attention to the distinction. It's impossible to define the predicate "integer" in terms of the elementary theory of the reals: this follows from the results (noted by Henry) of Tarski, who proved that the theory of the real field is decidable, and Godel, who proved that the theory of the ring of integers is undecidable. As soon as you allow quantification over sets, it's much easier to express undecidable questions; for instance, it's easy to define the integers from the reals as the smallest subset that contains 0 and is closed under successor and negation, so therefore you can express undecidable questions. Bill On Oct 21, 2011, at 11:51 PM, Henry Baker wrote:

The theory of "real numbers" (or at least the theory of algebraic numbers) is easier than the theory of "integers".

The theory of real order is decidable. The theory of real addition & ordering is decidable. The theory of real closed fields (+,*,<; i.e., polynomials with integral coefficients) is decidable. The theory of integers with a single successor function ("1+") is decidable, but harder than that of real closed fields. This is like the integers, but you can only emulate addition/subtraction of constants, and cannot emulate multiplication of 2 arbitrary integers.

The theory of integers (with addition & multiplication) is undecidable.

So, in order to define the integers within the real numbers, you need to add enough additional structure to emulate finite chains (i.e., induction). Most of the emulations I've seen involve things like complex numbers, sines & cosines, so you emulate the integral periodic structure of sines/cosines.

At 06:13 PM 10/21/2011, David Wilson wrote:

...

How do you show that there is an integer greater than any given real number?

The real question is, given the axioms for the real numbers (Dedekind-complete ordered field), how do you define the "real integers" within them.

Two possibilities spring to mind.

Definition A: The "real integers" are the minimal subset of R that contains 1 and is closed over negation and addition.

Definition B: 1 is a "real integer", and there is a unique "real integer" in every half-open unit interval of R.

Definition A seems more in the spirit of the number theory definition of Z. However, I do not immediately see how it answers my original question.

Definition B immediately answers my original question. For any real number r, there is a unique integer on the half-open interval (r, r+1] which must be greater than r.

Presumably definitions A and B are equivalent. Is the proof easy?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun