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?
Reals (edit: moreover irrationals) $s,r$ that do not satisfy $\exists q,p \in \mathbb{Q}$ such that $s = qr + p$
-
2Note that if the statement were true, then by fixing an $r$, we could conclude that the set of reals is countable. – 2012-05-25
4 Answers
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.
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.
-
0@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. – 2012-05-25
$s=\pi$ and $r=1$. Then $\pi$ would be a sum of two rationals which is rational.
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.
-
0Awesome, thanks! – 2012-05-25