Timeline for How do we recognize an integer inside the rationals?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 12, 2021 at 19:06 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 118 characters in body
|
| Nov 25, 2010 at 17:27 | comment | added | Kaveh | I think the definability of integers in rationals is due to Julia Robinson and the formula is given in Marker's Model Theory book. | |
| Mar 30, 2010 at 17:56 | comment | added | Pace Nielsen | 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). | |
| Mar 30, 2010 at 17:08 | comment | added | Joel David Hamkins | 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. | |
| Mar 30, 2010 at 16:58 | comment | added | Pace Nielsen | That said, thank you for your answer. | |
| Mar 30, 2010 at 16:57 | comment | added | Pace Nielsen | 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). | |
| Mar 30, 2010 at 16:56 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 486 characters in body; added 50 characters in body; added 30 characters in body; edited body
|
| Mar 30, 2010 at 16:50 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |