locating any point on a real number line

Question

So my question is really simple (and may be a bit naive):

The claim is, I can locate any point in a 2D-plane by recursively applying the following method (possibly infinite number of times):

1. For simplicity, assume the plane be drawn as a grid (imagine a graph paper)

2. Now I can locate the bigger grid (essentially a square) in which the point lies, and then try to narrow it down.

The idea is, if I keep doing this infinitely I will eventually hit the point somewhere.

Is this claim true? Looking at this problem in 1-D means that I can find a point on the real number line in (possibly infinite steps) by always narrowing down by one decimal digit (like multiplying by 10 for example)?

Answer 1

In every step $n$, your grid has intervals of size $10^{−n}$ each. Hence, the distance between your number to the boundaries of the selected interval is at most $10^{−n}$. When $n\to\infty$, this distance goes to $0$. Hence, after an infinite number of steps, the interval contains exactly your number and nothing else.

By the way, a similar "narrowing-down" process on a triangle leads to a solution of an interesting fair division problem.

Answer 2

Personally I would like to think that one will not "hit" the point. It depends on how you specify what is meant by "narrowing" your grid down. Say you divide it into a certain number of smaller grids you can definitely determine which sub-grid contains your point. But you can prove that given any grid you can divide it into a specified number of sub-grids. So the issue is that your search never ends.

But as stated by Nimda, you can definitely approximate your point as accurately as you want. That is the key concept of a "point". You can make your sub-grids as small as you wish.

Another problem is how you would locate your point. Regardless of how small the pointer you use to "hit " your point as long as it has a positive diameter there are infinite number of points which fall under your pointer - any one of which can be the point you are looking for.

Answer 3

This problem is the "cartesian square" of a simpler problem:

We have to prove that, given a nested sequence $$I_n:=[a_n,b_n]$$ of intervals with $$b_{n+1}-a_{n+1}={1\over10}(b_n-a_n)$$ for all $n\geq0$, there is exactly one real number $\xi$ which belongs to all $I_n$. (Replace $10$ by $2$, if you prefer.)

There cannot be two different such numbers: When $\xi-\xi'>0$ then there is an $n$ such that $b_n-a_n={1\over 10^n}(b_0-a_0)<\xi-\xi'$. Therefore it is impossible that both $\xi$ and $\xi'$ belong to $I_n$ (and all subsequent $I_{n'}$).

But there could still be a "hole" in ${\mathbb R}$ right where we we hoped to catch the $\xi$. That this is not the case is the content of the so-called completeness of ${\mathbb R}$, which can be formulated in various ways. E.g., we could note that the $a_n$ form a monotonically increasing sequence bounded above by $b_j$, whatever $j$. Completeness then guarantees that the sequence $(a_n)_{n\geq0}$ has a limit $\xi\in{\mathbb R}$, and it is easy to see that $\xi\in I_n$ for all $n\geq 0$.

Maybe the limiting $\xi$ cannot be realized (as a floating point number) in your computer; but that's another story.

Answer 4

No, you cannot always "hit" the point i.e. the narrowing down method cannot generate all possible points.

For simplicity, just consider that the point you want to locate(or generate) lies in the range $[0,1]$. If we prove that such a recursive algorithm cannot cover all the points in the range, then we are done.

Consider the following algorithm:

In step 1, it places 9 points on the line segment $[0,1]$ such that each pair of consecutive points has the same length. So we have $[0, 1/10, . . . , 9/10, 1]$. This is much like your graph paper example.

In step two, it places $9 \times 10$ such equidistant points between each pair of existing consecutive points.

In step $i$, therefore, this algorithm will place $9 \times 10^{i-1}$ number of points; and so on.

This continues till infinity.

Let $P$ denote the set of all points generated by this algorithm. Observe that the number of points generated till the $(i-1)^{th}$ iteration is $(9 + 9 \times 10 + ... + 9 \times 10^{i-2})$ = $10^{i-1} - 1 = k_{i}$ (say). Now, we can enumerate the points in $P$ that are generated in the general $i^{th}$ iteration as $p_{k_{i} + 1},p_{k_{i}+2}, ... p_{k_{i}+9 \times 10^{i-1}}$, respectively in increasing order.

Since this enumeration forms a bijection with the set of natural numbers, we have:

$|P| = |\mathbb{N}| < |\mathbb{R}|$, where $\mathbb{N}$ and $\mathbb{R}$ denote the set of natural numbers and real numbers respectively. Considering that the number of points in $[0,1]$ is equal to $|\mathbb{R}|$, it is proved that the given algorithm cannot generate all the points in $[0,1]$.