33
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 9
    $\begingroup$ I find it hard to get my head round this question. How is the rational number presented to us? And why can't we presuppose that we know how to write an arbitrary rational number as a quotient of integers and reduce? I thought I did know how to do that ... $\endgroup$
    – gowers
    Mar 30, 2010 at 15:45
  • 1
    $\begingroup$ Here's the link to the paper quoted: www-math.mit.edu/~poonen/papers/ae.pdf $\endgroup$
    – Sonia Balagopalan
    Mar 30, 2010 at 15:55
  • 7
    $\begingroup$ @gowers: that is the crux of the question. The rationals are presented 'abstractly' in this question, as a priori indecomposable units. Can you still pick out the integers? $\endgroup$
    – Jacques Carette
    Mar 30, 2010 at 16:08
  • 3
    $\begingroup$ @gowers: My question is fairly open-ended, and so you (personally) may assume that the rationals are presented in any manner you want. For example, you might assume they are given with their ordering, or without their ordering. They may be given as ratios of integers, or perhaps as a priori indecomposable units (as Jacques put it). What I want is to hear how people might check, given whichever presentation they prefer, whether a given rational is an integer. I gave a few simple examples in my original question. I'm hoping that I'll see some characterizations I've never seen before. $\endgroup$
    – Pace Nielsen
    Mar 30, 2010 at 16:43
  • 1
    $\begingroup$ @Kaveh, but if the problem is to recognise integers, then "multiply by 2 until you get an integer" is suspect as a step along the way! $\endgroup$
    – LSpice
    Aug 25, 2014 at 15:44

6 Answers 6

Reset to default
29
$\begingroup$

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|$.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ If I recall correctly from the days when I studied number theory, this "silly idea" is a "starting point" for much of algebraic number theory! $\endgroup$
    – Kevin H. Lin
    Mar 31, 2010 at 6:26
36
$\begingroup$

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.)

Improve this answer
$\endgroup$
5
  • $\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$
    – Pace Nielsen
    Mar 30, 2010 at 16:57
  • 1
    $\begingroup$ That said, thank you for your answer. $\endgroup$
    – Pace Nielsen
    Mar 30, 2010 at 16:58
  • 2
    $\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$
    – Joel David Hamkins
    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$
    – Pace Nielsen
    Mar 30, 2010 at 17:56
  • 7
    $\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$
    – Kaveh
    Nov 25, 2010 at 17:27
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice! Many thanks for the reference! $\endgroup$
    – Andrés E. Caicedo
    Jan 28, 2012 at 6:47
  • $\begingroup$ Just saw this -- excellent! $\endgroup$
    – Todd Trimble ♦
    Sep 18, 2012 at 23:53
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
2
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm not looking for an answer in first order logic, per se. That is the motivation behind the question, but the question itself is to simply give algorithms or descriptions of the integers, when presented with the rationals [in some manner]. My hope, of course, would be that these descriptions could eventually be turned into first order logical characterizations (as Poonen did with option B above), but I'm leaving that for a later date. $\endgroup$
    – Pace Nielsen
    Mar 30, 2010 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.