4 ms·

For one, a set has unique elements, so listing duplicates won’t increase the size. But the idea is that some sets can’t be indexed. Decimal numbers/ real numbe

For one, a set has unique elements, so listing duplicates won’t increase the size. But the idea is that some sets can’t be indexed. Decimal numbers/ real numbers. Basically, if you try to list them all, you can always find one that isn’t in the list. Make the ith digit of the number different than the ith digit of the ith number in your list. That proves that decimal numbers can’t be put on a list, so there’s more decimal numbers than list-able numbers, even if they’re both infinite.

memling 4y ago
> But the idea is that some sets can’t be indexed. This is a fantastic way to put this. Maybe it's a common way of talking about uncountable infinities, but this is a more intuitive way to lead someone through the problem, I think. Thanks.
- bigmattystyles 4y ago
  I agree, a lightbulb went off for me when it was put that way. I still wonder though, is it just a semantic trick, saying an infinity can't be indexed. I get that if you have all positive decimal numbers, you can't decide what's in the first position, but it feels like asking what's in the last position of a countable infinity - a question that makes no sense. Isn't this why Godel went mad?
  - memling 3y ago
    > I agree, a lightbulb went off for me when it was put that way. I still wonder though, is it just a semantic trick, saying an infinity can't be indexed. I get that if you have all positive decimal numbers, you can't decide what's in the first position, but it feels like asking what's in the last position of a countable infinity - a question that makes no sense. Isn't this why Godel went mad? Not exactly a semantic trick, and it's not (really) about deciding what's in the first position. Cantor described two kinds of sets: countable and uncountable. A set S is considered countable if it fulfills one of two conditions: (1) if it is finite, so you can count it by definition, or (2) if there is a one-to-one onto function that maps the natural numbers N to S. This is more or less what I think GP means by "indexing." "Indexing" as a shorthand for "counting" makes sense, at least for me. I have an array of numbers. Those numbers happen to be positive even integers, but I index them (for sake of convenience) starting from 1. You can draw that on a sheet of paper and people can get it. In fact, you can show them pretty readily that there are no gaps between those numbers; if you have infinite memory, you can index the positive even integers as long as you want, and you can see a one-to-one, onto correspondence. But if you ask your hypothetical conversation partner to do that with, say, all the real numbers in [0, 1), you can always find a gap between the numbers in their function. You cannot create an index for those numbers. This is much more intuitive than trying to go through the the proof by contradiction,[1] IMO, although obviously it's not rigorous. Gödel was a paranoid hypochondriac, and I suppose it's tempting to suppose that was partially linked to his mathematical genius. But I actually rather doubt it; he was (apparently) quite lucid when going through his mathematics, and characteristically brilliant. [1] Here's a stab at it. Suppose S is the set of all positive even integers. Intuitively S feels like it should be roughly half the size of N, since we're only taking half of them. But what Cantor is saying—I think—is that a function is merely a representation of the numbers. Since f(x) = 2x suffices to map S to N, they are of equivalent "size." You can always index S and figure out what number is at what index x by plugging it into f. Cantor then proceeded to demonstrate that no such function exists that can map N to the set S of real numbers from [0, 1). He does this by contradiction using a technique called diagonalization. First, he supposes that some f does exist, that is, for any n in N, f(n) will return a member of S. Then he constructs a number m as follows: Let g_n(n) be the function that returns the nth digit from f(n). (So, for example, g_1(1) will return the first digit of f(n), g_2(2) will return the second digit of f(1), and so on.) This is where the term "diagonalization" comes from: when you write out the values of S in a grid, g_n(n) will return the digits along the diagonal. Then construct a number m such that its decimal expansion is (g_n(n) + 1) · 10^-n for n in N. m differs from f(1) in the first digit, and from f(2) in the second digit, and so on down the line—so it cannot be in S. But that can't be right: we assumed from the beginning that we would enumerate all of the values in S by using f, and here is a number that we can construct that f should have enumerated and did not.
    - bigmattystyles 3y ago
      Thank you! Great insight!

memling 4y ago

> But the idea is that some sets can’t be indexed. This is a fantastic way to put this. Maybe it's a common way of talking about uncountable infinities, but this is a more intuitive way to lead someone through the problem, I think. Thanks.

bigmattystyles 4y ago
I agree, a lightbulb went off for me when it was put that way. I still wonder though, is it just a semantic trick, saying an infinity can't be indexed. I get that if you have all positive decimal numbers, you can't decide what's in the first position, but it feels like asking what's in the last position of a countable infinity - a question that makes no sense. Isn't this why Godel went mad?
- memling 3y ago
  > I agree, a lightbulb went off for me when it was put that way. I still wonder though, is it just a semantic trick, saying an infinity can't be indexed. I get that if you have all positive decimal numbers, you can't decide what's in the first position, but it feels like asking what's in the last position of a countable infinity - a question that makes no sense. Isn't this why Godel went mad? Not exactly a semantic trick, and it's not (really) about deciding what's in the first position. Cantor described two kinds of sets: countable and uncountable. A set S is considered countable if it fulfills one of two conditions: (1) if it is finite, so you can count it by definition, or (2) if there is a one-to-one onto function that maps the natural numbers N to S. This is more or less what I think GP means by "indexing." "Indexing" as a shorthand for "counting" makes sense, at least for me. I have an array of numbers. Those numbers happen to be positive even integers, but I index them (for sake of convenience) starting from 1. You can draw that on a sheet of paper and people can get it. In fact, you can show them pretty readily that there are no gaps between those numbers; if you have infinite memory, you can index the positive even integers as long as you want, and you can see a one-to-one, onto correspondence. But if you ask your hypothetical conversation partner to do that with, say, all the real numbers in [0, 1), you can always find a gap between the numbers in their function. You cannot create an index for those numbers. This is much more intuitive than trying to go through the the proof by contradiction,[1] IMO, although obviously it's not rigorous. Gödel was a paranoid hypochondriac, and I suppose it's tempting to suppose that was partially linked to his mathematical genius. But I actually rather doubt it; he was (apparently) quite lucid when going through his mathematics, and characteristically brilliant. [1] Here's a stab at it. Suppose S is the set of all positive even integers. Intuitively S feels like it should be roughly half the size of N, since we're only taking half of them. But what Cantor is saying—I think—is that a function is merely a representation of the numbers. Since f(x) = 2x suffices to map S to N, they are of equivalent "size." You can always index S and figure out what number is at what index x by plugging it into f. Cantor then proceeded to demonstrate that no such function exists that can map N to the set S of real numbers from [0, 1). He does this by contradiction using a technique called diagonalization. First, he supposes that some f does exist, that is, for any n in N, f(n) will return a member of S. Then he constructs a number m as follows: Let g_n(n) be the function that returns the nth digit from f(n). (So, for example, g_1(1) will return the first digit of f(n), g_2(2) will return the second digit of f(1), and so on.) This is where the term "diagonalization" comes from: when you write out the values of S in a grid, g_n(n) will return the digits along the diagonal. Then construct a number m such that its decimal expansion is (g_n(n) + 1) · 10^-n for n in N. m differs from f(1) in the first digit, and from f(2) in the second digit, and so on down the line—so it cannot be in S. But that can't be right: we assumed from the beginning that we would enumerate all of the values in S by using f, and here is a number that we can construct that f should have enumerated and did not.
  - bigmattystyles 3y ago
    Thank you! Great insight!