Where's the flaw in this construction of a set that's both countable and uncountable? Say we constructed a set of all finite math expressions, which is countable. Then we take the subset of expressions that evaluate to a single real number. That subset should still be countable. Now we apply the Cantor argument to this subset to construct a new real number. I'm assuming all of this can probably be done using a finite expression, so this number should've been in the subset already.
So the subset is both countable and uncountable at the same time. Where's the flaw in this logic? Are there multiple?
 A: I keep finding near-duplicates but can't find an exact duplicate, so here goes:

Note that you haven't  been clear about what "finite expression" means. This is in fact the problem that turns into the fundamental error:

"I'm assuming all of this can probably be done using a finite expression."

Your whole argument hinges on the claim that the "antidiagonal real" corresponding to whatever system of definitions you're using is definable by a definition within that system itself. This may feel obvious, especially since we're generally not very careful about the precise nature of mathematical language. However, it is in fact false: a general theorem of Tarski, usually stated for first-order logic but much more broadly applicable than that, says that this is in fact almost never the case!

I think the main obstacle to understanding this is the fact that we generally only have one "mathematical language" in mind, namely the informal-but-"rigorous" natural language we actually use to talk about mathematics. To de-mystify things a bit, consider "local" versions of Cantor's theorem: given a "complexity class" (in a very broad sense) $\mathfrak{C}$ we can talk about $(i)$ reals definable by an expression in $\mathfrak{C}$ and $(ii)$ arrays definable by an expression in $\mathfrak{C}$. The process of forming the antidiagonal corresponding to a given array is simple enough that, for "reasonable" $\mathfrak{C}$, it's something $\mathfrak{C}$ lets us do. The "local Cantor's theorem," then, is this:

The $\mathfrak{C}$-definable reals can never be put into a single $\mathfrak{C}$-definable array. Put another way, the set of $\mathfrak{C}$-definable reals is not "$\mathfrak{C}$-countable.

For example:

*

*The polynomial-time-computable reals, while obviously countable, are not polynomial-time-computably countable.


*The computable reals, while obviously countable, are not computably countable.


*The reals which are first-order definable over $(\mathbb{R};+,\times)$ without parameters, while obviously countable, are not $(\mathbb{R};+,\times)$-definably-without-parameters countable.
And so on. In my opinion this "local" analysis will, once understood, clear up a lot of the issues one may have with both Cantor's argument and general ideas about definability broadly construed. (That's not to say that everything about definability and countability suddenly becomes intuitive - see e.g. here for an example which trips plenty of people up! - but it's a good first step.)
