Response to a comment on my post on Cantor diagonalization.

An anonymous reader commented last weekend on a post from 26 months ago; he asked several questions I wish to address here. I’ve reordered and numbered them below for ease of writing my response

Let’s assume, for the sake of argument, that I found a bijection between ℕ and ℝ.

1. Would this invalidate Cantor’s argument?

2. What sort(s) of proof or test would be sufficient to demonstrate it is a bijection?

3. How, if at all, would such a discovery impact the notion of set cardinality?

I’ll take each of these questions one at a time.

Would a bijection invalidate Cantor’s argument?

No. He starts be assuming you found such a bijection and then proves by contradiction that it is not, in fact, a bijection. His approach will work just as well with your bijection as with anyone else’s.

However, in my experience approximately 10% of students in graduate level computational theory courses never accept Cantor’s argument. I talked a little bit about why in my earlier post, but for this post I’m going to just ignore Cantor and related proof approaches and work constructively.

How would you demonstrate it is a bijection?

There are many ways. In the end, you need

• two functions

• that are inverses of each other,

• one with a domain of all natural numbers

• and the other with a domain of all real numbers.

If we call these two functions r2n and n2r I use multi-glyph function names because I am a computer scientist and we like meaningful names more than we like letters in strange typefaces, though we do like those too… then along the way you’ll have to show one particular sub-property of bijections which causes most of the trouble:

This is hard. This is what Cantor proved to classical-logic-minds is impossible. This is the property that I’ll address in this post.

∀ r ∈ ℝ, ∃ n ∈ ℕ such that n2r(n) = r

What is this asking? It’s saying, for any finite Finite magnitude, not necessarily with a finite decimal expansion. real number I care to mention, you have to convince me that there is a finite Why finite? Because all natural and real numbers are finite. We can’t start to use “‍infinite numbers‍”, whatever those are, until after we define what infinity is, which is what all this talk of cardinality was for in the first place. natural number that would create it. The problem with this is there are so many real numbers!

Let’s list some things that won’t work. Fractions won’t work because of √2 and π and so on. Basing it on decimal expansion also won’t work because of the same examples. π is actually a good counterexample to many possible mappings, but hardly the only one; for example, we need to be able to have a natural number for the largest x such that ³√6 x^4π + 2 x⁹ – 2 = 0. And so on.

So, what about saying “‍describe the number in English; write it in ASCII, then treat that text as a big base-128 number?‍” This will give us a natural number for every real we can describe in English (which, presumably, is all of the real numbers we will ever see) but now we have two different problems: first, many many ASCII texts don’t describe real numbers (e.g, “‍Pwi$$gt&‍”); and second, r2n is no longer a function. “‍Two‍”, “‍two‍”, and “‍one plus one‍” all describe the same real number but in this encoding they are:

A better description-based definition can be designed if we switch to a more structured language than English. Like computer code, for example. Not all numbers can be generated precisely by code, but we can write code that, the if it were to run forever, would converge arbitrarily close to any real number we have ever thought of Per the Church-Turing Thesis, we expect this to always be the case, for all future reals we identify, too. . If we let that converging code represent the number it approximates then we can write r2n(r) as follows: enumerate every program in some deterministic order, counting all the ones that generate numbers other than r and stopping when we see one that generates r.

The above r2n is well defined (or can be; I was loose in the definition) and, from a classical logic standpoint, it shows that the computable numbers are countably infinite… but in constructive logics we haven’t finished defining it because we haven’t shown it itself can be computed. Classically, this r2n is not computable (by Rice’s theorem); but we are ignoring that family of proofs in this post, so…

The code return 1+1; and the code return 2; both give us the same number. Because r2n needs to be a function, we need to count only one of those pieces of code. Thus, we need to count those programs that generate numbers we haven’t yet seen another program generate. Now, that’s all well and good except telling if two programs generate the same number is… well, at least very very hard (and classically impossible). Consider, for example, the followingthis example uses the traditional definition of ℕ, which excludes 0:

This code results in x = 0 if and only if Fermat’s Last Theorem is true. It took mathematicians 358 years to prove that theorem, so we now know that it does result in 0; but it is pretty easy to make similar code for just about every unsolved mathematical problem we know of. In other words, if you can compute a code-based (or text-based) r2n then you can also prove every mathematical postulate there is. All I actually showed is if you can compute this code-based r2n then you can solve almost any mathematical problem. But a similar process can be used with every other code-based r2n I know….

So maybe we go away from the program technique altogether…

How can we find a natural number for each real number, including reals we haven’t even yet invented the mathematics to describe; and not base our mapping on digits, or fractions, or other finite sets of operations; and also not based it on textual descriptions or programs? I don’t know. Maybe you do?

Oh, and by the way, don’t forget about Cantor’s number. Once you get your r2n and n2r, r2n had better be able to handle the real number x that the following code converges toward:

Assuming n2r is defined, the x that code converges toward is a single, well-defined real number (even though, like π, it is not finitely-computable). Your bijection had better have an n for it, too…

Impact on Cardinality

If Cantor’s proof is wrong and |ℕ| = |ℝ|, which is what a bijection would mean, then, as far as I am aware, we would not have evidence that any infinite set has a different number of elements from any other infinite set. All of the proofs I have yet seen stem from a version of Cantor. Of course, I do not follow these categories of proofs that closely, so I may have missed some.

That said, classical logic can prove Cantor is right, and constructionist logic has never yet proven him wrong.

Impact on Logic

Constructionist logic has yet to disprove anything that classical logic has proved. If someone were to prove that |ℕ| = |ℝ| then the really big result would be the fall of classical logic. Since many very important theories are proven classically that would be a much more significant result than deciding that the infinities are all one size.