Registered: Mar 2004
Posts: 132

Attached below is a notebook that allows one to enumerate all possible sequences of integers. There is an infinite number of integers, and sequences of them can be infinitely long. The function matches a number uniquely to a given sequence which can be of any length and contain any set of numbers in them. I have not found out the way to match the sequence uniquely/reversibly back to a number when enumerating all of them, but I think it's entirely possible.

Another way of saying what the function does is that it gives the non-negative integers (or natural numbers, or any infinite scale one could use to enumerate with) a one-to-one correspondence with every possible whole-number coordinate in every single dimension.

it was constructed using Matthew Szudzik's unpairing function. I remember him saying that there is also a function for enumerating the real numbers. If you were to use that function here, then I think you would be able to enumerate every set of real number coordinates. That's cool.

I don't know if this has been done before. I think it's interesting and might be useful.

Attachment: enumsn-2.nb
This has been downloaded 1490 time(s).

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Reals, or infinite sequences of arbitrary integers, are not enumerable. Yes if the length of the sequence (or in your version the number of dimensions) is bounded, then you can indeed put them into one to one correspondance with the natural numbers. But not when it is infinite. This was shown in the famous diagonalization argument of Cantor back in the 19th century.

A standard account in set theory terms is here -

http://mathworld.wolfram.com/CantorDiagonalMethod.html

The proof works by contradiction - you assume you've got 'em all, and then ask about one of them, and find you can't have got it yet. Say I've enumerated the sequences, any way you please, giving me a look up table with the natural number on the left (the n-th series) and the series on the right.

n1 <-> a1 a2 a3 a4 a5 ...
n2 <-> b1 b2 b3 b4 b5 ...
n3 <-> c1 c2 c3 c4 c5 ...
n4 <-> d1 d2 d3 d4 d5 ...
n5 <-> e1 e2 e3 e4 e5 ...
...

Now consider the sequence X == a1+1, b2+1, c3+1, d4+1, e5+1... Starting from the diagonal of your enumeration, taking one term from each series you've numbered. But then changing that term.

Is X in the enumeration? Well, it isn't n1, because it disagrees with n1 in the first term of the series. It isn't n2, because it disagrees with n2 at the second term of the series. It isn't n3, because it disagrees with n3 in the third term of the series - etc. Ergo, X is not in the enumeration.

But we did not even need to specify what the enumeration was, so this conclusion follows regardless of what enumeration method we use. All we did was assume that we had them all, and then found we had missed at least one. We got a contradiction from the assumption that we could get them all in a 1 to 1 correspondance with the natural numbers. Ergo, we can't get them all.

To relate this intuitively to what you are trying, notice that down at terms eight hundred gazillion, I might indeed have a candidate n-800 gazillion which did match my sequence X for the first 800 gazillion digits. But that is not enough. It has to match in the 800 gazillion-th and 1st digit, too.

Truly infinite in sequence length, or in number of digits, or in number of dimensions, is truly different from anything bounded in that respect. You can get the one infinity of higher and higher integers. And you can get it in more and more (but finite, bounded) dimensions or terms.

You can number all the integer location points in a space with 800 gazillion dimensions. More, you can number all the rational location points - a set that is what we call "dense" in the reals - in a space with 800 gazillion dimensions. But 800 gazillion is not infinity, and you can't number all the integer points in a space with truly infinite dimensions.

Multiple infinities are tricky. I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

There are a number of interesting enumerable sets of reals, such as the rational numbers.

The computable numbers are those which can be approximated by computations. There are just as many such numbers as there are computations, which are themselves countable.

The NKS perspective is to remain flexible in terms of getting the actual numbers from a computation.

A standard thing to do though is to look at the center column, here of rule 30, (p.871)

N[FromDigits[{Flatten[CellularAutomaton[30,{{1},0},200,{All,{0}}]],0},2],50]

which is 0.86238978394738404864080024608675112810853296362455

If you want more accuracy, you just run the computation further. It is easy to bound how much work is needed to get each new digit.

More interesting from a NKS point of view, are numbers arising from computations, without needing to be able to prove convergence.

Besides trying to enumerate reals through computations, there is also the attempt to use mathematical logic. For example, through countable models of the reals, which is its own interesting side story (p.1172), infamous for
causing confusion.

Report this post to a moderator | IP: Logged