[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?