Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hello friends of mathematics :) I have some problems with the topic "Is something definable in a structure". I can solve some problems for example the following questions:

  • Is the relation definable in the structure $(\Bbb{Q},+,0,1)$
  • Is the function "sin" definable in the structure $(\Bbb{R},<,+,\cdot,0,1)$
  • Is $\Bbb{N}$ definable subset of $(\Bbb{Z},<,+,\cdot,0,1)$

The answers are No, No, Yes resp.

But now i want to solve the following problems:

  • Is $\Bbb{Z}$ definable subset of $(\Bbb{R},<,+,\cdot,0,1)$
  • Is $\Bbb{Q}$ definable subset of $(\Bbb{R},<,+,\cdot,0,1)$
  • There is no qeuntifier-free formula that defines the set $2\Bbb{Z}$ in the structure $(\Bbb{Z},+,<,S,0)$ (with $S$ the sucessorfunction)

For the first problem i thought this: If we can define $\Bbb{Z}$ then we could find a polynomial with zeros in all integers. But such a polynomial doesn't exist. I don't know how to solve it on another way. Can someone help me? Thank you beforehand :)

share|improve this question
    
For the first one: math.stackexchange.com/questions/263284/… –  Asaf Karagila Dec 29 '12 at 21:31
add comment

1 Answer

For the non-definability of $\mathbb{Z}$ in the reals, there is good structure theory (keyword: o-minimal) for the definable subsets of $\mathbb{R}$. One can also argue using decidability/undecidability.

It is an old result of Tarski that there is a decision procedure for the elementary theory of real-closed fields. If $Z$ were definable, that decision procedure could be used to produce a decision procedure that would determine, for every sentence $\phi$, whether or not $\phi$ is true in the natural numbers.

For definability of $\mathbb{Q}$, again structural information about definable subsets of $\mathbb{R}$ will do it. Another approach is to use the old, and not easy, result of Julia Robinson that the natural numbers are definable in $\mathbb{Q}$. (Please See Definability and Decision Problems in Arithmetic Journal of Symbolic Logic, Vol. 14, No. 2 (June 1949).)

Hence if $\mathbb{Q}$ were definable in $\mathbb{R}$, then $\mathbb{Z}$ would be. This, as shown above, is not true.

share|improve this answer
    
In the lecture we do not use the keyword o-minimal. Oh yes but such a procedure doesn't exist because of uncompleteness theorem thus $\Bbb{Z}$ is not definable, true?! Wat do you mean with the last sentence? –  Mathematic Research Dec 29 '12 at 21:40
    
@MathematicResearch: I have added a sentence at the end which I hope clarifies things. –  André Nicolas Dec 29 '12 at 21:44
    
Dear André, I am currently doing a little undergraduate research project in o-minimal structures. Thank you for showing me that this is actually something more people know about :P –  akkkk Dec 29 '12 at 21:48
    
@André Nicolas: Thank you :) i think i understand the argument ... but is the argument with uncompleteness theorem correct? –  Mathematic Research Dec 29 '12 at 21:48
    
The "we could find a polynomial $\dots$" argument is, at least, highly incomplete. And for example $\mathbb{Z}$ is definable in $\mathbb{Q}$, so an argument based on roots of polynomials is unlikely to be enough. For a good understanding of definability in $\mathbb{R}$, the fact that the definable subsets are simple combinations of semi-algebraic sets is the key result, and in a sense undecidability is peripheral. –  André Nicolas Dec 29 '12 at 22:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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