Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

[This is a cleaner and simpler restatement of a question I asked earlier on Theoretical CS forum. Please re-tag as appropriate.]

Suppose you have two oracles (black boxes) that represent real numbers. Each oracle works like this: you give it integer $n$ and it returns integer $k$ such that $k/n \leq r < (k+1)/n$, where $r$ is the real number the oracle represents.

Suppose Bob knows the numbers and wants to prove to Alice that they are different. He then may produce input $n$ such that the oracles return different answers.

Now consider the equivalence relation $s =_Q r \Leftrightarrow \exists q,p \in \mathbb{Q}, q \neq 0$ such that $s = qr + p$, (where $\mathbb{Q}$ is the set of rational numbers).

Can Bob prove to Alice that $s \neq_Q r$ in a finite number of steps using only finite inputs? I think he can't, but how do you prove it?

share|cite|improve this question
Given a finite set of inputs, you've narrowed the value of $r$ to some interval, $[a,b)$. Now just show that, given two non-empty intervals $[a,b)$ and $[c,d)$ there must by a $r_1\in[a,b)$ and $r_2\in[c,d)$ that are such that $r_1\neq_Q r_2$. So the finite number of steps hasn't restricted your real number enough. – Thomas Andrews Feb 15 '12 at 13:45
@Thomas, what you mean, I think, is that $[a,b)$ must contain $r'$ such that $s =_Q r'$. Then $r'$ will produce the exact same sequence of outputs as $r$. – malenkiy_scot Feb 15 '12 at 14:05
Your relation is not an equivalence relation (every rational $s$ is related to every real $r$ (taking $q=0$) but not symemtrically). The closest thing I can see that is an equivalence relation is that the images in the rational vector space $\mathbb R/\mathbb Q$ of $r,s$ are related by a nonzero rational factor. Is that what you meant, or something different? – Marc van Leeuwen Feb 15 '12 at 14:11
@Marc, obviously $q \neq 0$, otherwise the relation is not reflexive (you can't express $r$ via $s$). I'll edit it in. Thanks. – malenkiy_scot Feb 15 '12 at 14:24
@malenkiy_scot Another way of looking at it is to say that for any $x$ and any interval $[a,b)$ with $a<b$, there is an $x'=_Q x$ for some $x'\in [a,b)$. So, no matter how many finite steps of $r$ you take, you have not narrowed down its equivalence class under $=_Q$ at all - it could be a member of any of the equivalence classes. – Thomas Andrews Feb 15 '12 at 14:28
up vote 3 down vote accepted

The answer turns out to be rather trivial (Thomas, thanks for pointing me in the right direction):

After a finite sequence of queries proving that $s \neq_Q r$ the possible value of $r$ is restricted to an interval $[a,b)$. That interval will necessarily contain some $r'$ such that $r' =_Q s$. But the oracle for $r'$ would produce the exact same sequence of answers as the oracle for $r$. Contradiction.

share|cite|improve this answer

Your Answer


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.