Dichotomic search over $\mathbb{Q}$ and irrational numbers

Question

The set $\mathbb{Q}$ is continuous in the sense that if $a,b\in\mathbb{Q}\implies\frac{a+b}{2}\in\mathbb{Q}$. Let's consider the following dichotomic search:

finder(a, b, t):

  while (a < t and t < b)
     m = (a + b)/2
   
     if (m < t)
        a = m
     else
        b = m

where $a$ and $b$ are rational numbers such that $t\in[a, b]$. If the algorithm stops, $t$ has been found. I expect $\text{finder}(1, 2, \sqrt{2})$ doesn't stop. Can we define then the set of irrational numbers as the $t$s such that, for example $\text{finder}(\lfloor t\rfloor, \lfloor t\rfloor + 1, t)$, doesn't stop? How can you prove that the above algorithm won't stop if $t=\sqrt{2}$ (without using as premise that $t$ is not a rational number)? (How can you prove that the above algorithm DO stop if $t$ is a rational number?)

Only by considering the existence of the above algorithm, picturing $\sqrt{2}$ as a "gap on $\mathbb{Q}$" turns fuzzy to me because there's an infinite amount of possible finite number of iterations, so I can reduce any gap as much as I want; I just have to keep iterating. Consider that the length of the gap at any iteration is $\frac{b-a}{2}$, which is also a rational number. So the length of any gap, no matter how stretched, can be expressed as a rational number and I can "corner" any number as much as I can; it's all about how many iterations do I need.

Answer 1

The algorithm will only stop for rational numbers $\dfrac{k}{2^n}$ where the denominator is a power of $2$. (These are often called dyadic rational numbers).

To see this, notice that:

• The first time you run the algorithm, $a$ and $b$ are integers, which are dyadic rational numbers.
• If $a$ and $b$ are dyadic rational numbers, $\dfrac{a+b}{2}$ is also a dyadic rational number.
• So at every step, the endpoints of your interval are dyadic rational numbers.
• The algorithm can only stop if $t$ becomes an endpoint of an interval.

Essentially you are computing the binary expansion of a number, and the algorithm will only stop if that binary expansion terminates.

You can prove that the algorithm will not terminate for $\sqrt{2}$ as follows: suppose that $\sqrt{2}=\dfrac{k}{2^n}$. We can't have $n=0$ because $\sqrt{2}$ is not an integer. So if this fraction is in lowest terms, then $k$ must be odd. Then $2=(\sqrt{2})^2=\frac{k^2}{2^{2n}}$ and so $2^{2n+1}=k^2$. But this is impossible as $2^{2n+1}$ is even and $k^2$ is odd.

Intuitively, if $\sqrt{2}$ had a terminating binary expansion, then $2$ would have a terminating binary expansion with more bits after the decimal point (binary point?). But $2$ is an integer so this is impossible.