0
$\begingroup$

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?

  • 2
    Note 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 4

1

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.

4

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
2

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

1

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.

  • 0
    Awesome, thanks!2012-05-25