Indescribable numbers: The theorem that made me fall in love with math

> You can take any bitstring (but not all bitstrings) of any length, including infinite, and assign a specific shorter (and finite) bitstring to represent it. You then have a finite encoding for that specific infinite sequence of symbols which can henceforth be used to describe it. You just can't do it for every infinite bitstring because you have insufficiently many finite bitstrings with which to represent them.

I agree with your general idea, but, won't you run into a problem already before you run into the pigeon-hole principle?

How do you do that, even for a single one?

I mean, how do you "take" an infinite bitstring to assign a symbol to it, without first having to have a finite description of this infinite bitstring?

You can't say "this infinite bitstring is now represented by the symbol 01101", without directly or indirectly specifying what "this infinite bitstring" refers to, and you need to do that specifying in a finite amount of symbols.

So it seems to me that, if you were to (foolishly) try the above infinite task, you'd run out of infinite bitstrings (that you can describe) just as fast as you'd run out of finite bitstrings that you'd like to compress them with?

The standard intuitive explanation seems pretty easy and worthwhile:

Two sets are the same size if and only if you can pair members up.

{1, 2, 3} and {4, 5, 6}, obviously.

{1, 3, 5...} and {2, 4, 6...} are too, you can pair them up (1, 2) (3, 4) (5,6) ...

But some sets aren't the same size; you can't pair them up. It's easy if they're both finite, or one is infinite. If both are infinite, well, if they're not the same size, one has to be larger: there are elements in one that are "left over" after trying to pair them up. That's the bigger one. Cantor proved that this does, in fact, happen. The reals can't be paired up with integers.

Got any links to expound on some of your notes? Or would non-mathematicians just be better off starting from the beginning..

> The get out clause is that they are not a set, but a class.

Good grief! In axiomatic set theory, introducing 'classes' was the "get out clause" from the Russell paradox of the the set of all sets that are not members of themselves. So, the patch, the time I studied one version of axiomatic set theory, was to say that there are some sets and we know what they are and we know that the Russell paradox can't happen now, so let's go on.

It appears that the OP and alternatives to the usual treatment of the real numbers are based on what can be described. This issue doesn't impress, or, really, concern me. To me, for just an easy answer, there is the real line with points, and that's description enough for me. Apparently the OP wants a description in terms of digits and is bothered that uncountably infinitely many reals need countably infinitely many decimal digits to be described. Okay, if don't like all those digits, then just return to the points on the line and let those points be the description. Good enough for me, but at this point I have quite different fish to fry getting my business going, really like the real numbers and what classic pure and applied math do with them, and see no good reason to change the foundations of what I do.

More generally, it appears that computer science is struggling to find something to do beyond the biggies of quicksort, heap sort, merge sort, AVL trees, red-black trees, BNF, YACC, LALR parsing, relational database, P versus NP, etc. So computer science wants to take parts of statistics, optimization, control theory, and now the foundations of math for its own and, in those fields, do things differently.

Maybe I'm missing a point: Maybe the idea is to have all the 'numerical' data computing works with be describable in some finite way, that is, not just a countably infinite sequences of digits, and, thus, get rid of, say, numerical error. Maybe. Seems a bit far fetched.

You argued (without much detail, but I'll buy it) for completeness, but then snuck in ordered-ness and Archimedean-ness. As a p-adic analyst, I object to taking these latter two characteristics for granted as necessary for mathematics.

(Also, one has to be careful about the meaning of 'complete' in the uniqueness statement; i.e., it must be understood to mean complete as an ordered field (satisfying the least-upper-bound property), not just complete as a uniform space (having every Cauchy sequence converge). See Paul Sally's "Tools of the trade" (http://www.amazon.com/Tools-Trade-Paul-J-Sally/dp/0821846345) for some discussion of this.)