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.

I want to prove the following statements:

  • Is the function "sin" definable in the structure $(\Bbb{R},<,+,\cdot,0,1)$, that is does there exists a formula $\phi=\phi(x_0,x_1)$ such that for all $a,b\in\Bbb{R}$: $sin(a)=b$ iff $(\Bbb{R},<,+,\cdot,0,1)$ realizes $\phi[a,b]$ ?!
  • Is $\Bbb{Z}$ a definable subset of $(\Bbb{R},<,+,\cdot,0,1)$ ?
  • Is $\Bbb{Q}$ a definable subset of $(\Bbb{R},<,+,\cdot,0,1)$ ?

I have no idea how to solve this questions. I think i have to prove that i have to show that in a extension of the structure the subsets are not definable or i have to give a formula. Can someone help me?! Thanks

share|improve this question
    
Note that $\sin$ definable implies $\mathbb Z$ defineable ($x\in\mathbb Z\iff \sin(\pi x)=0$ where $\pi$ is the smallest positive zero of $\sin$) implies $\mathbb Q$ defineable ($x\in\mathbb Q\iff \exists a,b\colon a,b\in \mathbb Z, b\ne0, bx=a$). –  Hagen von Eitzen Dec 8 '12 at 20:24
1  
These are not statements. They are questions. You probably want to answer them, not prove them. –  tomasz Dec 9 '12 at 14:22

2 Answers 2

Inevitably the tools one should use depend on the theorems already available in the course. In particular, if you are already familiar with the structure theory of definable subsets of the reals, then the answer by Chris Eagle is the better path, particularly for $\mathbb{Q}$. I hope that the approaches described below will still be of some interest.

For (b) and (c), the answer is no. One can give very similar justifications. If $\mathbb{Z}$ were definable, so would $\mathbb{N}$. But there is an algorithm for deciding whether a sentence is true in the reals, and there isn't for $\mathbb{N}$. A defining formula for $\mathbb{Z}$ would let us use Tarski's algorithm to decide all number-theoretic questions. Too bad!

For the rationals, the same argument holds, since (not obvious, this is a theorem of Julia Robinson) $\mathbb{Z}$ is a definable subset of $\mathbb{Q}$.

Because $\sin(1)$ is transcendental, the answer to (a) is no. The reason is that the real algebraics are elementarily equivalent to $\mathbb{R}$.

Another approach to (a) is that if $\sin$ were definable, then $\mathbb{Z}$ would be definable, via the roots of $\sin x$.

Added: We give more or less full detail for the $\sin(1)$ is transcendental approach to a).

$1$) Suppose there is a formula $\phi(x,y)$ that "says" $y=\sin x$. Then the sentence that says there is a (unique) $y$ such that $\phi(1,y)$ is true in the reals.

$2$) The same sentence is then true in the real algebraics. So there is a real algebraic number $b$ such that $\phi(1,b)$ is true in the real algebraics.

$3$) Because $b$ is algebraic, we can in principle write down explicit polynomials $P(y)$ and $Q(y)$, not identically equal, with non-negative integer coefficients, such that $P(b)=Q(b)$.

$4$) Thus $\exists y(\phi(1,y)\land (P(y)=Q(y)))$ is true in the real algebraics.

$5$) It follows that the above sentence is true in the reals. But that is not the case, since $\sin(1)$ is transcendental.

Note that the above approach can be used to show many similar things, such as the fact that the relation $y=2^x$ is not definable in the reals. (The number $2^{\sqrt{2}}$ is transcendental.)

share|improve this answer
    
But how to show that formally? –  Prime Dec 8 '12 at 20:35
    
What is "that?" For (b) for example, the details by which one uses a supposed defining formula to translate a sentence "about" integers numbers are mechanical. Let $\psi(x)$ be the supposed defining formula. Just replace $\exists x \phi$ by $\exists x(\psi(x)\land \phi)$, with an analogous replacement for universal quantifiers. (Note: will be away from computer for at least 45 minutes.) –  André Nicolas Dec 8 '12 at 20:43
    
@AndréNicolas: the approach to sine is interesting, as are the other ones, but I don't think that decidability of the reals and non-decidability of naturals are more elementary than o-minimality in this case. :) –  tomasz Dec 9 '12 at 15:15
    
Certainly not more elementary. But perhaps known in a general purpose Senior course in logic. –  André Nicolas Dec 9 '12 at 15:46

An alternative approach is to start by proving that $M=(\Bbb{R},<,+,\cdot,0,1)$ eliminates quantifiers. It then easily follows that $M$ is o-minimal; that is, the only definable sets (even with parameters) are Boolean combinations of intervals. Thus $\Bbb{Q}$ and $\Bbb{Z}$ are not definable, and so neither is $\sin$, since a definition of $\sin$ would allow us to define $\Bbb{Z}$.

share|improve this answer

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.