4 ms·

My understanding of "countable" is that it's reasonable to ask which is the "next" in sequence. You can't do that with reals. /me didn't watch the video.

denton-scratch 4y ago
Hey, I don't mind being downvoted at all. But if I'm wrong, then can you please explain how? I thought only sequences could be counted. If I'm downvoted for not watching the video, I think that's mean. I was interested in the subject, but I'd prefer a transcript to a video.
- 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 ago
    THank 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 ago
      In 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 :-).
aantthony 4y ago
If a set is countable, then there exists a mapping which is a one-to-one correspondence between the items and the natural numbers (that’s the definition of countable). This correspondence would always allow you to determine the “next” item (by converting to a natural, incrementing, then converting back). However there could be multiple mappings (sorted differently, for instance) and so it’s more specifically, whether it’s possible to have a next function. In other words, there can be multiple next functions, but a set is countable iff there is at least one of them.
- ogogmad 4y ago
  Your definition would rule out finite sets. You don't need a bijection. A surjection from the natural numbers suffices. In plain English, you need to construct an infinite sequence (a,b,c,d,...) which (i) consists of elements of a set S (ii) contains every element of S at least once - sometimes many times over. We also allow the members of this sequence to equal an exceptional value we denote with an asterisk: *. This is to take into account the possibility that S may be an empty set. Without this exceptional value, such a sequence cannot exist if S is empty. If S has at least 1 element, then we don't need the exceptional value. I don't know if this means you can sensibly talk about a "next" element. The problem is that an element of S might repeat. What you're describing sounds equally like a total ordering. Assuming the Axiom Of Choice, every set has a total ordering, but the indices are not in general natural numbers, but may be ordinal numbers. You cannot in general exhibit such a total ordering, because anything proved using the Axiom Of Choice is merely known to exist, but cannot always be computed or constructed.
  - aantthony 4y ago
    Ah, yes. The definition I tried to use was from Wikipedia, in full: "In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers." I missed the part where it said finite. Thank you for correcting that. If you take your sequence construction, then by removing duplicates from the sequence, this new sequence would allow finding a "next" element.

denton-scratch 4y ago

Hey, I don't mind being downvoted at all. But if I'm wrong, then can you please explain how? I thought only sequences could be counted. If I'm downvoted for not watching the video, I think that's mean. I was interested in the subject, but I'd prefer a transcript to a video.

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 ago
  THank 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 ago
    In 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 :-).

aantthony 4y ago

If a set is countable, then there exists a mapping which is a one-to-one correspondence between the items and the natural numbers (that’s the definition of countable). This correspondence would always allow you to determine the “next” item (by converting to a natural, incrementing, then converting back). However there could be multiple mappings (sorted differently, for instance) and so it’s more specifically, whether it’s possible to have a next function. In other words, there can be multiple next functions, but a set is countable iff there is at least one of them.

ogogmad 4y ago
Your definition would rule out finite sets. You don't need a bijection. A surjection from the natural numbers suffices. In plain English, you need to construct an infinite sequence (a,b,c,d,...) which (i) consists of elements of a set S (ii) contains every element of S at least once - sometimes many times over. We also allow the members of this sequence to equal an exceptional value we denote with an asterisk: *. This is to take into account the possibility that S may be an empty set. Without this exceptional value, such a sequence cannot exist if S is empty. If S has at least 1 element, then we don't need the exceptional value. I don't know if this means you can sensibly talk about a "next" element. The problem is that an element of S might repeat. What you're describing sounds equally like a total ordering. Assuming the Axiom Of Choice, every set has a total ordering, but the indices are not in general natural numbers, but may be ordinal numbers. You cannot in general exhibit such a total ordering, because anything proved using the Axiom Of Choice is merely known to exist, but cannot always be computed or constructed.
- aantthony 4y ago
  Ah, yes. The definition I tried to use was from Wikipedia, in full: "In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers." I missed the part where it said finite. Thank you for correcting that. If you take your sequence construction, then by removing duplicates from the sequence, this new sequence would allow finding a "next" element.