5 ms·

> 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 t

> 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 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?
- 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!

bigmattystyles 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?

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!