Skip to main content
MathOverflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

4
  • $\begingroup$ It appears I wasn't very clear in my question. Even this method of describing the integers inside the rationals has its pluses and minuses. For example, universal quantifiers do not lend themselves very easily to algorithmic checking. [We know that the primes are characterized as roots to a polynomial, but we wouldn't want to check primality that way.] I was simply asking for other characterizations we might add to my list of three options, and gave Poonen's paper as context for why this question might be interesting (because he transfered one such characterization into another context). $\endgroup$ Commented Mar 30, 2010 at 16:57
  • 3
    $\begingroup$ Yes, the complexity of the definition of Z in Q affects certain decidability questions (although not the undecidability of the theory, as I explained in my answer), and this is the topic of the paper to which I linked. Your methods A, B, C, D are not first order definitions at all, and I do not take them as definitions of Z in Q, but rather, as definitions of Z in some other more elaborate structure in which the integers are already present. For example, in A, the rationals are given to you in some kind of fractional form, so you have in effect defined Z in ZxZ, which is trivial. $\endgroup$ Commented Mar 30, 2010 at 17:08
  • $\begingroup$ True. Option A seems trivial. Option B seems even more unnecessary--we not only assume we know about the integers, but about ALL the primes! But it is ultimately the one which Poonen used to describe the best level of undecidability [to date] for the first order theory on the rationals. Who is to say which description is the right one? I'm interested in them all (trivial and non-trivial). $\endgroup$ Commented Mar 30, 2010 at 17:56
  • 8
    $\begingroup$ I think the definability of integers in rationals is due to Julia Robinson and the formula is given in Marker's Model Theory book. $\endgroup$ Commented Nov 25, 2010 at 17:27