9
$\begingroup$

Can the equality of two real numbers always be determined?

Let us say that we have derived an expression for a real number X. We also have obtained an (entirely different) expression for a real number Y.

Now one mathematician claims that X and Y must necessarily be exactly equal. Another mathematician claims that X and Y can not be equal, however their difference is extremely small; say 0.5^N with N some unknown but very large number.

To settle the dispute the mathematicians decide to use a Turing machine.
As input the machine takes the binary expansions x(n) for X [n=1,2,3,4...] and y(n) for Y. If the machine finds that for some n the pair of digits x(n) and y(n) are unequal, then it concludes that X and Y are unequal and the program halts. However if X and Y are equal, the machine will continue to check digits "ad infinitum" without ever reaching a conclusion. So in the case of equality (X = Y) there appears to be no halting criterium.

In the example that I described, the Turing machine is of no great help. The machine just continues to run "forever". Thus it remains unresolved whether this is because X and Y are exactly equal, or whether they are unequal but the first difference in their digits occurs at some unattainable high index N (required CPU time > age of the universe).

$\endgroup$
3
  • $\begingroup$ Most real numbers are transcendental which means they have an infinite expansion, if the two numbers are very close it may take "forever" to compare them. If however you already have an expression for one simply verify that the expression holds for the second. Note, however that most real numbers won't have such nice expression. $\endgroup$
    – Asaf Karagila ♦
    May 11, 2012 at 5:15
  • $\begingroup$ I wonder whether your second mathematician can know that. It might help to examine how he could reach that conclusion. For example, I can demonstrate X and Y are distinct by exhibiting a rational number Z between them. How else can I know they're distinct? $\endgroup$
    – MikeC
    May 11, 2012 at 17:08
  • 4
    $\begingroup$ Case in point: $X = 0$, $Y = \sum_{n=1}^\infty 2^{-n} d_n$ where $d_n = 1$ if $n$ is an odd perfect number and $0$ otherwise. So if we could tell whether or not $X=Y$ we would know whether or not an odd perfect number exists. Similarly for many other unsolved questions of number theory. $\endgroup$
    – Robert Israel
    May 13, 2012 at 5:18

2 Answers 2

Reset to default
12
$\begingroup$

It depends on what kind of "expressions" are allowed. The theory of real closed fields is decidable, so for expressions using only +,-,*,/, RootOf and explicit integers the equivalence can be decided algorithmically. If other operations are allowed, it may be undecidable. See e.g. http://en.wikipedia.org/wiki/Richardson%27s_theorem and http://dl.acm.org/citation.cfm?id=190429

$\endgroup$
4
$\begingroup$

The way you stated the problem (with real numbers given as infinite sequences of binary digits) there is no way to determine if two numbers are equal, the argument for which is simple (and similar to the one for halting problem):

For simplicity, assume that we're considering the question for numbers in $[0,1]$.

Suppose, by contradiction, that we have an algorithm which could solve the question of any two numbers. Such an algorithm would necessarily finish after reading only finitely many digits (we can assume without loss of generality that it reads them in sequence, and reads the same number of digits from each).

Let $n$ be the number of digits the algorithm reads before reaching the conclusion that, in fact, $0=0$. Then, when supplied with $0$ and $2^{-n-1}$, it would read the exact same input as in the $0=0$ case, so it would also say that they're equal, which is a contradiction.

As shown by Robert Israel, the question heavily depends on the permitted presentations of the numbers. Note that while there are only countably many numbers that can be expressed in the language of real closed fields (which somewhat limits the scope of Robert's answer), any real number (even undefinable) has a binary expansion, and no two numbers share one (even though it is not, in general, computable, even for definable numbers).

$\endgroup$
3
  • 1
    $\begingroup$ Thank you very much. It would seem to me (but I am layman!) that this result might have profound consequences. For example for set theory. Let S be any finite or countably infinite subset of the real numbers, with elements X(j) [j=1,2,3,4...]. Now we ask a very simple question: is a certain real number Y a member of S? This means establishing whether Y = X(j) for at least one index j. However, as has been discussed above, equality between two real numbers can not always be determined. So a fundamental property of set theory (membership of a set) can sometimes be undecidable. $\endgroup$
    – M. Wind
    May 12, 2012 at 1:02
  • $\begingroup$ The fact you mentioned can be shown for subsets of natural numbers, and it's a classical result which can be done in an even simpler way: there are only countably many algorithms (since they're finitely described procedures), while there are uncountably many subsets of the natural numbers. It's quite a bit harder to show that there are recursively denumerable sets of natural numbers (that is, ones for which there is an algorithmic procedure which "writes out" all members of the set) for which membership is not decidable. Such sets are called simple: en.wikipedia.org/wiki/Simple_set $\endgroup$
    – tomasz
    May 13, 2012 at 5:05
  • $\begingroup$ @M.Wind: But set theory do not deal with decidable procedures. This is logic, recursion theory, computability, and such aim. Set theory allows constructs which are far far more complicated than anything imaginable. Indeed just trying to imagine large countable ordinals might be cause one to stare flabbergasted with a hint of horror on their face. $\endgroup$
    – Asaf Karagila ♦
    May 14, 2012 at 23:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .