Viliam's Shortform

Viliam

This is a special post for quick takes by Viliam. Only they can create top-level comments. Comments here also appear on the Quick Takes page and All Posts page.

How many real numbers can be defined?

On one hand, there are countably many definitions. Each definition can be written on computer in a text file; now take its binary form as a base-256 integer.

On the other hand, Cantor's diagonal argument applies here, too. I mean, for any countable list of definable real numbers, it provides a definition of a real number that is not included in the list.

Funny, isn't it?

(solution)

2Viliam2y

The important thing is not to move the goalpost. We assumed that we have an enumeration of all X numbers (where X means "real" or "definable real"). Then we found an X number outside the enumeration, therefore the assumption that the enumeration contains all X numbers was wrong. The End. We don't really "go to a higher cardinality", we just show that we are not there yet, which is a contradiction to the assumption that we are. A proof by contradiction does not let you take another iteration when needed. The spirit is "take all the iterations you need, even infinitely many of them, and when you are done, come here and read the argument why the enumeration you have is still not the enumeration of all X". If you say "yeah, well I need a few more iterations", that's cheating; you should have already done that. Because if we allow the "one more iteration, please", then we could kinda prove that any set is countable. I mean, I give you an enumeration that I say contains all, you find a counter-example, I say oops and give you a set+1, you find another counter-example, oops again, but still countable + countable = countable. The only way out is when you say "okay, don't waste my time, give me your final interation", and then you refuse to do one more iteration to fix the problem. * And if this still doesn't make you happy... well, there is a reason for that, and if you tried to carefully follow to its source, you might eventually get to Skolem's paradox (which says, kind of, "in first-order logic, everything is kinda countable, even things that are provably uncountable"). But it's complicated. I think the lesson from all this is that you have to be really super careful about definitions, because you get into a territory where the tiniest changes in definitions might have a "butterfly effect" on the outcome. For example, the number that is "definable" despite not being in the enumeration of "definable numbers" is simply definable for a slightly different definition of

1philip_b2y

I guess I was not clear enough. In your original post, you wrote "On one hand, there are countably many definitions ..." and "On the other hand, Cantor's diagonal argument applies here, too. ...". So, you talked about two statements - "On one hand, (1)", "On the other hand, (2)". I would expect that when someone says "One one hand, ..., but on the other hand, ...", what they say in those ellipses should contradict each other. So, in my previous comment, I just wanted to point out that (2) does not contradict (1) because countable infinity + 1 is still countable infinity. [...] Could you clarify how I would construct that? [...] I didn't say "the next cardinality". I said "a higher cardinality".

Cantor's diagonal argument is not "I can find +1, and n+1 is more than n", which indeed would be wrong. It is "if you believe that you have a countable set that already contains all of them, I can still find +1 it does not contain". The problem is not that +1 is more, but that there is a contradiction between the assumption that you have the things enumerated, and the fact that you have not -- because there is at least one (but probably much more) item outside the enumeration.

I am sorry, this is getting complicated and my free time budget is short these days, so... I'm "tapping out".

Viliam's Shortform

9

Viliam's Shortform

9