Sign up ×
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'm trying to understand the equivalence relation given in this question about quasi-interactive proof on real numbers. My guess is that the asker already knows that $\forall s,r \in \mathbb{R}, \exists q,p \in \mathbb{Q}$ such that $s = qr + p$ is not true. Is that the right interpretation? If so, how do you prove that?

share|cite|improve this question
Note that if the statement were true, then by fixing an $r$, we could conclude that the set of reals is countable. – David Mitra May 25 '12 at 18:58

4 Answers 4

up vote 1 down vote accepted

That isn't what the asker is claiming--rather, that the given stepwise procedure will not (in finitely-many steps) show that the given $r,s$ are non-equivalent reals. Of course, if it were always true that for any such $r,s$ there existed such $p,q$, then the asker's claim would be completely false! Thus, that there exist $r,s$ with $r\neq_Q s$ is a necessary condition for the asker's claim.

You probably understand that "$s=_Q r$ iff $\exists p,q\in\mathbb{Q}$, $q\neq 0$ such that $s=qr+p$" defines a reflexive, symmetric, transitive relation on the reals. Thus, the reals are split into equivalency classes, modulo $=_Q$. It is trivial to note that if $s,r$ are rational, then $s=_Qr$. The answers given by Marvis and Jackson Walters demonstrate that there are multiple different equivalency classes.

share|cite|improve this answer
Awesome, thanks! – idonutunderstand May 25 '12 at 20:13

If you are looking for irrational numbers $s$ and $r$, then $s=\sqrt{3}$ and $r= \sqrt{2}$ would do the job. You can check this by squaring both sides to get a contradiction that $\sqrt{2}$ is rational.

In general, if you are looking for irrational numbers $s$ and $r$, then

$$s=\sqrt{m} \text{ and }r = \sqrt{n} \text{ where } m,n \in \mathbb{Z}^+ \backslash{\{\text{ Square integers}\}} \text{ and } \sqrt{\dfrac{m}{n}} \notin \mathbb{Q}$$

The above is just one class of such pairs. You can construct infinite such classes.

share|cite|improve this answer
@CameronBuie Yes:) ofcourse. Have changed it. – user17762 May 25 '12 at 18:53
what does $\mathbb{Z} \backslash{\{\text{ Square numbers}\}}$ mean? – idonutunderstand May 25 '12 at 19:28
@AbstractionOfMe I wanted to mean positive integers that are not squares i.e. the set $\{2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20, \ldots\}$. This is to ensure that $\sqrt{m}$ and $\sqrt{n}$ are irrational numbers. – user17762 May 25 '12 at 19:31

$s=\pi$ and $r=1$. Then $\pi$ would be a sum of two rationals which is rational.

share|cite|improve this answer

Hint $\rm\: s\in r\:\mathbb Q + \mathbb Q \subset\mathbb Q(r)\:$ is false if $\rm\:r\:$ is algebraic and $\rm\:s\:$ is transcendental over $\mathbb Q,\:$ or if they are quadratic numbers from different quadratic fields (i.e. different discriminants), etc.

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.