3 ms·
A set is countable iff there is a sequence that counts it. That doesn't require that there be One True Notion of next-ness in the set itself. For instance, if
by gjm11 4y ago
A set is countable iff there is a sequence that counts it. That doesn't require that there be One True Notion of next-ness in the set itself.
For instance, if I give you the rational number 337/912 and ask "what's the next rational number?" there isn't a canonical answer. But the rational numbers are countable.
So the fact that there isn't a canonical answer to "what's the next real number?" doesn't tell us anything about whether or not the real numbers are countable.
(For the avoidance of doubt: in ordinary set theory with ordinary logic, the reals are definitely not countable. The research being reported on here looks at what happens when you weaken your logic, by throwing out the "law of the excluded middle", and weaken your set theory, by not having any form of the "axiom of choice". It turns out that in this case there are multiple things you might reasonably mean by "the real numbers", and for at least one of these you can no longer prove that they're uncountable, and we can tell this because there's a so-called topos in which "the real numbers" are countable. A topos is a sort of generalized "notion of what a set is", and if something is provable intuitionistically and without any version of the axiom of choice then it is true in every topos. I think. Something along those lines, anyway.)
- denton-scratch 4y agoTHank you. I had no idea there were different ideas of what "real" meant, and it's my first encounter with the notion of a topos (other than a place: the "topos" was the toilet, the place where the boys went to piss at my boarding school). [Edit] Also, I hadn't grokked that rationals were countable; but now you point it out, I guess they must be. Does countable imply enumerable?
- gjm11 4y agoIn ordinary mathematics there are plenty of ways to define the real numbers, but they're all equivalent; you can translate from one to another and if anything's true of one then its translation will be true of another. With the restrictions being used here, though, the different definitions aren't all equivalent, and apparently it turns out that one version of "the real numbers" is necessarily countable and another isn't (because it's countable "in a particular topos"). "Countable" and "enumerable" are the same thing. (But there's a separate term, "recursively enumerable", that means something else.) One way to see that the rational numbers are countable: write them down in a sort of square where m/n goes in position (m,n). You'll have e.g. 2/3 and 4/6 and 6/9 and ..., all in different places, but that's harmless. Then start at (1,1) and walk along the finite diagonals: 1/1, then 1/2, 2/1, then 1/3, 2/2, 3/1, etc. Boom, you've counted the rational numbers :-).