Ok, so let’s say you’ve been able to find a countably infinite amount of real numbers and you now call them “definable”. You apply the Cantor’s argument to generate one more number that’s not in this set (and you go from the language to the meta language when doing this). Countably infinite + 1 is still only countably infinite. How would you go to a higher cardinality of “definable” objects? I don’t see an easy way.
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 “definable”. Which feels irrelevant… but maybe it’s the number of the slightly different definitions that is uncountable? (I am out of my depth here.)
It also doesn’t help that this exercise touches other complicated topics in set theory. For example, what is the “next cardinality” after countable? That’s what the Continuum Hypothesis is about—the answer doesn’t actually follow from the ZF(C) axioms; it could be anything, depending on what additional axioms you adopt.
I wish I understood this better, then I would probably write some articles about it. For the moment, if you are interested in this, I recommend Introduction to Set Theory by Hrbacek and Jech, A Beginner’s Guide to Mathematical Logic by Smullyan, and maybe some book on Model Theory. The idea seems to be that the first-order logic is incapable to express some relatively simple intuitions, so the things you define are never exactly the things that you wanted to define; and whenever set theory says that something is undecidable, it means that in the Platonic universe there is some monstrosity that technically follows the axioms for sets, despite being something… completely alien.
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.
take all the iterations you need, even infinitely many of them
Could you clarify how I would construct that?
For example, what is the “next cardinality” after countable?
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”.
Ok, so let’s say you’ve been able to find a countably infinite amount of real numbers and you now call them “definable”. You apply the Cantor’s argument to generate one more number that’s not in this set (and you go from the language to the meta language when doing this). Countably infinite + 1 is still only countably infinite. How would you go to a higher cardinality of “definable” objects? I don’t see an easy way.
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 “definable”. Which feels irrelevant… but maybe it’s the number of the slightly different definitions that is uncountable? (I am out of my depth here.)
It also doesn’t help that this exercise touches other complicated topics in set theory. For example, what is the “next cardinality” after countable? That’s what the Continuum Hypothesis is about—the answer doesn’t actually follow from the ZF(C) axioms; it could be anything, depending on what additional axioms you adopt.
I wish I understood this better, then I would probably write some articles about it. For the moment, if you are interested in this, I recommend Introduction to Set Theory by Hrbacek and Jech, A Beginner’s Guide to Mathematical Logic by Smullyan, and maybe some book on Model Theory. The idea seems to be that the first-order logic is incapable to express some relatively simple intuitions, so the things you define are never exactly the things that you wanted to define; and whenever set theory says that something is undecidable, it means that in the Platonic universe there is some monstrosity that technically follows the axioms for sets, despite being something… completely alien.
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”.