How do we recognize an integer inside the rationals? My question is fairly simple, and may at first glance seem a bit silly, but stick with me.  If we are given the rationals, and we pick an element, how do we recognize whether or not what we picked is an integer?
Some obvious answers that we might think of are:
A. Write it in lowest terms, and check the denominator is 1.
B. Check that the p-adic valuation is non-negative, for all p.
C. Decide whether the number is positive (or negative) and add 1 to itself (or -1 to itself) until it is bigger than the rational you picked.  (If these multiples ever equaled your rational, then you picked an integers.)
Each of these methods has pluses and minuses.  For example, in option A we presuppose we know how to write an arbitrary rational number q as a quotient of integers and reduce.  In C, we have issues with stopping times. etc..
To provide some context for my question: We know, due to the work of Davis, Putnam, Robinson, and Matijasevic, that the positive existential theory of $\mathbb{Z}$ is undecidable.  The same question for $\mathbb{Q}$ is not entirely answered.  One approach to this new question is to show that that, using very few quantifiers, one can describe the set of integers inside the rationals; and then reduce to the integer case.  For example, see Bjorn Poonen's paper "Characterizing integers among rational numbers with a universal-existential formula."  There, he finds a way to describe the p-valuation of a rational number (i.e. he finds a way to encode option B in the language of quantifiers and polynomials on the rationals).  I'm wondering if there are other characterizations of the integers which would follow suit.
 A: I'm a little new to this stuff so I might not know exactly what you're asking.
I believe there is a conjecture of Mazur that implies the type of description of $\Bbb Z$ you are looking for is impossible.
This paper by Poonen would be a good place to start. Of course Poonen would be able to give a much more satisfying answer. I only caught the end of his talk about this stuff at the Joint Meetings.
EDIT: 
Here Cornelissen and Zahidi show that Mazur's conjecture on the real topology of rational points on varieties implies that there is no diophantine model of $\Bbb Z$ over $\Bbb Q$. They also show that the analogue of Mazur's conjecture is false in the function field case, where Hilbert's Tenth has a negative answer.
A: The integers can indeed be defined in the rational field, but not in the real field.
$\newcommand\Q{\mathbb{Q}}\newcommand\Z{\mathbb{Z}}\newcommand\R{\mathbb{R}}$
The question can be made precise by introducing some tools of first order logic. What you are asking about is the definability of the integers inside the rationals. For example, if you might consider the rational field structure $\langle\Q,+,\cdot,0,1\rangle$ and inquire whether the integers are defined by a first order order formula in this structure. That is, is there a first order formula $\varphi(x)$ such that this structure satisfies $\varphi(x)$ if and only if $x$ is an integer? The answer is yes, and this paper appears to be about investigating how complex the definition is.
The fact that $\Z$ is definable in $\Q$ implies that the theory of the rational field is not a decidable theory. That is, there can be no computable algorithm which correctly tells us whether a given statement holds or fails in the rational field. The reason is that if we had such an algorithm, then by using the definability of the integers, we would be able to tell whether or not an arithmetic statement held or failed in the natural numbers, and with this, we would be able to solve the halting problem, which is impossible.
This situation contrasts sharply with the real field $\langle\R,+,\cdot,0,1\rangle$, whose theory IS decidable. Indeed, Tarski proved that the theory of real-closed (ordered) fields $\langle\R,+,\cdot,0,1,<\rangle$ is decidable. It follows that neither the integers nor the rationals are first-order definable in the real ordered field.
(Lastly, let me point out that the particular suggestions that you make for the definition are not first order definitions, and may suffer the criticism, as in some of the comments, that they beg the question concerning how the integers are implicit in your structure. The concept of first-order definability seems to avoid these criticisms, while clarifying both the question and the answers.)
A: Here's one way: Show that the rational number is an algebraic integer. This may sound like a silly idea, but it has non-trivial applications. A rational number is an integer if it has an expression as a sum of products of algebraic integers. See for example, Prop. 5 in the appendix of Groups and Representations by J.L. Alperin, and Rowen B. Bell, where this is used to prove that, for an irreducible character $\chi$ of a finite group $G$, $\chi(1)$ divides $|G|$.
A: The following paper by Stan Wagon and Dan Flath might be of some interest to you:
How to pick out the integers in the rationals: An application of number theory to logic, American Mathematical Monthly, 98 (1991) 812-823.
(I would have included a hyperlink if I was able to find one - unfortunately, my Internet browsing skills failed me this time.)
A: I just ran across the following paper: Defining Z in Q
It uses another characterization of the integers inside the rationals that none of us listed, perhaps because it is so trivial.  Namely, the integers are the complement of the set $\mathbb{Q}\setminus\mathbb{Z}$!  Apparently this basic fact is put to good use in the paper.
A: I'm very rusty on this stuff, but I think you need to be very careful in how to pose this question.  The cautionary example to stay aware of is that while there is no complete set of first order axioms for the integers, the standard axioms for the real numbers are known to be both consistent and complete.  The reason this can be is exactly because there is no way in first order logic to identify the integers as a subset of the reals.
If you are defining the rationals as equivalence classes of ratios, then #1 seems to be the best approach.  If you have some more abstract axiomatization of the rationals, it is not clear to me that there is an answer within first order logic.
