The Equals Sign is a Myth
The ability to tell whether two things are equal or not is a pretty fundamental ability in mathematics. The famed inability to divide by zero, for example, means that in order to evaluate rational functions we need to be able to check if the denominator is equal to zero or not. Similarly, if we take the union of two sets, the number of elements in the union depends on the number of elements that are shared — equal — between the two sets. With numbers being fundamental objects in mathematics, we should be able to tell whether two numbers are equal… right?
Let’s see if we can actually determine whether numbers are equal or not. This will necessarily depend on how we choose to represent the numbers, so we start with the integers. We might say that an integer is any of the unique symbols we have defined to be an integer: certainly, 0 is an integer, as is its successor, 1, and its predecessor, -1, and so on in either direction.
If I thus have an integer, say 525,600, I can be sure that I can distinguish it from any other integer, and verify its equality otherwise.
Is it equal to 1? No, the first symbol doesn’t match. Is it equal to 525? No, there are a different number of symbols. Is it equal to 525,600? Yes, all of the symbols are the same.
Even better, I know at worst how long it will take to check equality against any other number — I check each of the digits of my number and the total number of digits.
Let’s look at rationals now. The rational numbers have two common representations, either as a pair of integers (a fraction) or as an eventually-repeating decimal expansion. These representations aren’t always unique, so we also impose an equivalence relation that lets us know when two representations refer to the same rational number.
We might have the rational number 1/4, or 0.250̅, zero repeating, and ask if it is equal to some other rational number.
Is it equal to 5/20? We check the equivalence relation: since 1⋅20=5⋅4, indeed they are. What about being equal to 0.249̅, nine repeating? We are a little concerned that the symbols don’t immediately match, but these representations aren’t unique, and just as 0.9̅ and 1.0̅ represent the same rational number, so do 0.250̅ and 0.249̅.
Unfortunately, we’ve lost the ability to bound how long it will take to determine equality of the fraction representations since the other fraction can be arbitrarily large and still equivalent to ours, but we still know that determining equality or disequality will be done in finite time.
Increasing our scope again, let’s talk about the algebraic numbers, numbers x which satisfy P(x)=0 for some polynomial P with integer coefficients. Just as rational numbers carry the data of a fraction or repeating decimal that yields them, algebraic numbers carry the data of a polynomial that they satisfy. This makes our job even more difficult, because not only is the choice of polynomial not unique, but polynomials can have multiple roots. An algebraic number, then, might be a polynomial paired with some distinguishing information about the roots, or just a decimal number with a polynomial that it satisfies.
For example, perhaps my algebraic number is “the largest root of the polynomial x²-2” (√2). Mathematicians have worked for centuries developing ways to determine properties of roots, and in particular to approximate their values, so we can also generate the decimal expansion to arbitrary precision: 1.4142….
We might then look at two other algebraic numbers: the middle root of x³-3x²-2x+6 (=1.4142…) and the real root of 8000x³-22627 (=1.4142…). Certainly, if one of them is not equal to ours, the decimal expansion will differ at some point, but unlike with the rational numbers, there is no structure to the digits that tells us when that might happen. Without that structure, we could never determine if the algebraic numbers are equal!
It turns out, however, that we can determine the level of precision we need because these polynomials have an inherent structure to them. We’ll use two relevant results from the mathematician Siegfried Rump in 1979. The first will help us determine if our algebraic number even satisfies the other’s polynomial.
Lemma (Rump ‘79): Let P and Q be polynomials with integer coefficients and degrees n and m (respectively), and x such that P(x) ≠0 but Q(x) = 0. Then, letting ‖P‖ denote the sum of the absolute value of the coefficients of P, the following bound holds:
With this result, we have a (very small!) bound on how small a nonzero value can be, and hence we need only determine the value of our root to a level of precision that determines whether or not it is greater than the given bound. Using this, we can verify that √2 does not satisfy 8000x³-22627, and so must be a different algebraic number. It does, however, satisfy x³-3x²-2x+6, and so we have our second problem: how can we distinguish roots of the same polynomial? Rump again saves us:
Theorem (Rump ‘79): Let P be a polynomial with integer coefficients, degree n, and let x and y be non-equal roots of P. Then the following bound holds:
Now we know how much precision is needed to distinguish roots of a given polynomial, although again the sufficient precision is very high. Knowing this, we can verify that √2 is in fact equal to the middle root of x³-3x²-2x+6, and so those algebraic numbers are equal.
With algebraic numbers under our belt, let’s continue to the computable numbers. Broadly speaking, unless you’ve gone out of your way to see a non-computable number, this encompasses every number you’ve ever seen. Computable numbers are those whose decimal expansion can be written by a Turing machine, a formalized representation of an algorithm. In this case, the data that comes with a computable number is a Turing machine that produces the digits. Can we distinguish these? Here are a few examples:
Define the nth digit of the number x to be 1 if 2^(2^n)+1 is prime, and 0 otherwise, giving the digits x=1.11110…
Some numbers, sure, we can distinguish, but not really for computability reasons. The quotient of logarithms appears to approximate √2, but we can show that this number is not algebraic, and hence cannot be equal to √2. For the digit-defined number x, it is an open problem in number theory whether this is equal to the rational number 11,111/10,000 — but this will likely be decided through number-theoretic means, not computability theory.
It turns out that we cannot determine, in general, whether two computable numbers are equal — assuming we want to do so via a Turing machine (which is generally what “can” would mean). If you’ve seen computable numbers before the reason won’t be surprising, as this boils down to a fundamental result in computability — the Halting Problem — that there is no Turing machine that can, for any Turing machine, determine if it will halt.
The proof of the Halting Problem is surprisingly simple: consider a machine X that is the negation of the Halting Machine: halts if its input would not, and loops if its input would halt. Consider the machine given by inputting X to X; as a valid machine, the Halting Machine must say whether or not this machine halts, however X will do the opposite of what the Halting Machine decrees, yielding the contradiction.
We can convert any Turing machine to a computable number in the following way: the nth digit is 1 if the machine halts after n steps, and 0 otherwise. The Halting Problem is then equivalent to asking whether we can determine, for each of these computable numbers, whether they are equal to zero or not. Yet, to be equal to zero is to not halt, and to not be equal to zero is to halt, and since determining halting is impossible, distinguishing arbitrary computable numbers from zero is also impossible.
One interesting thing to point out is that the computable numbers under consideration in that proof are all rational: either 0 or 1/9 ⋅10⁻ᵏ for some integer k. The issue of distinguishability is not that the computable numbers are too close together, it’s that the data that comes with them is too weak.
With that in mind, it should not be surprising that we also cannot distinguish arbitrary real numbers from each other. The data that comes with real numbers is far too weak to work with — in fact, any sequence of digits (with a decimal point somewhere) represents a valid real number. Other representations, such as continued fractions, Cauchy sequences, or Dedekind cuts, also give practically zero finite-time control over the value of the real number. If I have two different real numbers, say 3.1415… and 3.1415…, they could have equal digits for arbitrarily many places, so I could never claim that they’re equal.
We only ever know what numbers are up to some small value around them; this is fine for the integers, where it’s enough to know an integer to within 1/2, and the data of the rationals and algebraics allow us to uniquely identify a number given a small enough neighborhood. This idea of finding a small allowance of error that results in a small enough change in the result is well-studied in mathematics, and is called continuity. The real fundamental issue here is that we really can only give answers to continuous statements, and equality, in general, is not continuous.
If you’ve seen topology before, you might recognize that “True/False” is a disconnected space, and so there cannot be a continuous (and surjective) map from the real numbers to this space. Any interesting True/False decision involving real numbers is necessarily going to involve determining equality, and that is just something we cannot do. Moreover, even though the computable numbers are topologically disconnected, they are computably connected, to a similar effect.
This is part of why continuity is such a useful and important property to have of functions in general. There are scenarios in which we talk about non-continuous functions, however, with the most prominent example being “integrable” functions. But integrable functions also avoid worrying about determining equality, as they are not strictly speaking functions but rather equivalence classes of functions, in which the behavior on measure-zero sets, like singletons, is not well defined. We can’t work with individual points here anyway, so determining equality is less important. In some cases, we can enforce a well-defined value for the function at certain points, but that necessarily involves continuity again!
This discussion also illustrates the importance of context for equality. To determine whether two algebraic numbers were equal, recall that the data that came with two equal algebraic numbers could be very different. We said that the largest root of x²-2 and the middle root of x³-3x²-2x+6 were equal, even though they had different data! When we talked about equality there, we restricted ourselves to only asking about the value of the number, not equality of the data; in some sense, we really meant “isomorphic as numbers”. But, harping on a distinction between equality and isomorphism isn’t useful, as equality in mathematics is always context-dependent.