41 ms·

/me not a mathematician! It seems to me that this definition of "countable" is obscure, and furthermore fails to show why the word "countable" is used. Is it w

/me not a mathematician! It seems to me that this definition of "countable" is obscure, and furthermore fails to show why the word "countable" is used. Is it wrong to say that a countable set is a set in which it is reasonable to ask which element is the "next" element? That's a natural-language definition, right? You can do that with natural numbers (just add 1) and with rationals (so I understand, but I can't give a procedure). Both sets have the same cardinality: aleph-null. You can't do that with the reals; that set is not countable, and furthermore has grater cardinality than aleph-null. It can also be shown that (a) there is no set with cardinality greater than aleph-null and smaller than the cardinality of the reals; and (b) no set with cardinality greater than aleph-null is countable. I can't do these proofs, but I've read them (in their non-symbolic, natural-language forms), and I was convinced.

Viliam1234 4y ago
> You can... (define "next number") ...with rationals (so I understand, but I can't give a procedure). 1/1 1/2, 2/1 1/3, 2/2, 3/1 1/4, 2/3, 3/2, 4/1 1/5, 2/4, 3/3, 4/2, 5/1 ... The first rational number is 0. Next is 1/1, that is 1. Next number to a positive rational number is its negative version, for example 1/1 is followed by -1/1. Next number to a negative positive number can be found by taking its absolute value (i.e. the previous number), locating it in the pyramid, and choosing the next number... skipping those fractions which can be simplified. For example -1/1 is followed by 1/2. So it goes like this: 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3... now we skip 2/2 because that can be simplified to 1/1, and proceed with... 3/1, -3/1, 1/4, -1/4...
nico 4y ago
> Is it wrong to say that a countable set is a set in which it is reasonable to ask which element is the "next" element? That's a natural-language definition, right? You can do that with real numbers as well. F(x)=randomreal() At any step you want a next element, you just produce a random real element. You can’t pre-determine how that random element will relate to the previously generated elements, but you can still produce real numbers, one at a time, and count them as you go. And if you do it for infinity, then you will never finish, but at every single step you will have assigned a natural number to a real number. The definitions used for the proof are fiction that you can ever fully finish counting something. The illusion that will fall for is that we think that all natural numbers are somehow pre-computed. If we are going to be generating infinite elements one by one, then you can count/number/order all of them, one at a time, no problem.
- haneul 4y ago
  If you recall, your original comment said “ If you say one infinity is larger/smaller than another, you’d be saying that the complete map for one is larger/smaller than for the other one. But if they are both infinite, you will never stop counting, so you just can’t know.”. So, if I can map all of the positive integers onto the reals and provably have reals that cannot be generated, that should suffice, no? Take the reals from 0 to 1. For each positive integer X, flip the digits and put it behind the decimal. So, 437 gets mapped to 0.734, 1000 gets mapped to .0001, etc. None of the transcendental numbers between 0 and 1 will get mapped onto. This is because all positive integers are a finite series of digits, whereas all transcendental numbers provably do not terminate. It is not possible to flip a finite sequence of digits and get a non terminating sequence of digits. So, now you have a generator function that can go through the positive integers one by one and never generate any members of an entire class of real numbers. FYI I find this quite useful in clarifying my own thinking so feel free to tell me why that isn’t convincing to you.
  - nico 4y ago
    But you are imagining “all the numbers between 0 and 1”, those numbers don’t/won’t exist until you generate them. You cannot perform the action of mapping. You can give me a formula to start mapping. But I would never finish. So you are imagining the result. There is no result, the mapping is a process, not a finite result that you can compare to another finite result. As long as you keep counting (producing naturals one after another), I can keep producing random real numbers and sorting them. There’s no point at which either one of us cannot generate one additional number. And if we keep going to infinity, then the random generator will have generated all possible real numbers.
    - haneul 4y ago
      Does pi/4 not exist? If I draw a circle of diameter 1 and erase all but one quadrant, I now have constructed a segment of length pi/4. This happens to be a transcendental number between 0 and 1. Stop using your random number generator. It is making you miss the point. It has no special value. For some reason you are assigning it a special value the same way people might assign numerical greater than order a special value. If you use the flipped positive integer generator instead, it is quite obvious that you will never generate pi/4 no matter how long you run that generator, yet that generator will run through all possible positive integers.

Viliam1234 4y ago

> You can... (define "next number") ...with rationals (so I understand, but I can't give a procedure). 1/1 1/2, 2/1 1/3, 2/2, 3/1 1/4, 2/3, 3/2, 4/1 1/5, 2/4, 3/3, 4/2, 5/1 ... The first rational number is 0. Next is 1/1, that is 1. Next number to a positive rational number is its negative version, for example 1/1 is followed by -1/1. Next number to a negative positive number can be found by taking its absolute value (i.e. the previous number), locating it in the pyramid, and choosing the next number... skipping those fractions which can be simplified. For example -1/1 is followed by 1/2. So it goes like this: 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3... now we skip 2/2 because that can be simplified to 1/1, and proceed with... 3/1, -3/1, 1/4, -1/4...

nico 4y ago

> Is it wrong to say that a countable set is a set in which it is reasonable to ask which element is the "next" element? That's a natural-language definition, right? You can do that with real numbers as well. F(x)=randomreal() At any step you want a next element, you just produce a random real element. You can’t pre-determine how that random element will relate to the previously generated elements, but you can still produce real numbers, one at a time, and count them as you go. And if you do it for infinity, then you will never finish, but at every single step you will have assigned a natural number to a real number. The definitions used for the proof are fiction that you can ever fully finish counting something. The illusion that will fall for is that we think that all natural numbers are somehow pre-computed. If we are going to be generating infinite elements one by one, then you can count/number/order all of them, one at a time, no problem.

haneul 4y ago
If you recall, your original comment said “ If you say one infinity is larger/smaller than another, you’d be saying that the complete map for one is larger/smaller than for the other one. But if they are both infinite, you will never stop counting, so you just can’t know.”. So, if I can map all of the positive integers onto the reals and provably have reals that cannot be generated, that should suffice, no? Take the reals from 0 to 1. For each positive integer X, flip the digits and put it behind the decimal. So, 437 gets mapped to 0.734, 1000 gets mapped to .0001, etc. None of the transcendental numbers between 0 and 1 will get mapped onto. This is because all positive integers are a finite series of digits, whereas all transcendental numbers provably do not terminate. It is not possible to flip a finite sequence of digits and get a non terminating sequence of digits. So, now you have a generator function that can go through the positive integers one by one and never generate any members of an entire class of real numbers. FYI I find this quite useful in clarifying my own thinking so feel free to tell me why that isn’t convincing to you.
- nico 4y ago
  But you are imagining “all the numbers between 0 and 1”, those numbers don’t/won’t exist until you generate them. You cannot perform the action of mapping. You can give me a formula to start mapping. But I would never finish. So you are imagining the result. There is no result, the mapping is a process, not a finite result that you can compare to another finite result. As long as you keep counting (producing naturals one after another), I can keep producing random real numbers and sorting them. There’s no point at which either one of us cannot generate one additional number. And if we keep going to infinity, then the random generator will have generated all possible real numbers.
  - haneul 4y ago
    Does pi/4 not exist? If I draw a circle of diameter 1 and erase all but one quadrant, I now have constructed a segment of length pi/4. This happens to be a transcendental number between 0 and 1. Stop using your random number generator. It is making you miss the point. It has no special value. For some reason you are assigning it a special value the same way people might assign numerical greater than order a special value. If you use the flipped positive integer generator instead, it is quite obvious that you will never generate pi/4 no matter how long you run that generator, yet that generator will run through all possible positive integers.