6 ms·

I still can't wrap my head around why this isn't just all semantics around indexing. Take the infinities of all numbers > 0 and then all even numbers > 0. So

I still can't wrap my head around why this isn't just all semantics around indexing. Take the infinities of all numbers > 0 and then all even numbers > 0. So you have 1,2,3,4,5,6,.... 2,4,6,8,........ Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs. The only way I can reason it, is that if I exclude the second from the first, I still have infinite items, whereas if I exclude the first from the second, then I'm left with nothing. Is that how to think about it? I don't why, it doesn't compute in my head.

version_five 4y ago
We do consider both of those sets to be the same size - for infinite sets, size equality means being able to uniquely put a members from one set in correspondence with members I n another. In your example, n -> 2n provides a unique mapping so the sets are equal size (cardinality)
roarcher 4y ago
Not all infinities can be indexed. Take all the real numbers between 0 and 1, for example. If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. Now take rational numbers, which are a subset of real numbers. There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Edit: It appears my sloppy language has ruffled some mathematical feathers. My apologies.
- firstlink 3y ago
  > If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. This isn't "sloppy language", it's just wrong. Don't try to downplay spreading misinformation. It remains true that there are infinitely many rationals in (0, N) and (N, 1), and yet it is entirely possible to enumerate the rationals (i.e. assign indices). > There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Also misinformation. (0, 0.5) is a subset of (0, 1) yet the two sets have the same cardinality, whether we take them both in Q or both in R.
  - roarcher 3y ago
    > This isn't "sloppy language", it's just wrong. Yes, no less than four people before you have explained what's wrong with my comment. I made the "sloppy language" edit before I fully understood them. > Don't try to downplay spreading misinformation. > Also misinformation. LMAO. Every incorrect thing you see on the internet isn't the work of a Russian troll or whatever you're trying to accuse me of here. Sometimes people are just mistaken. Your comment actually has some interesting points that could add to the discussion, but it's ruined by the impotent nerd rage.
  - deleted 3y ago
    [deleted]
- deleted 4y ago
  [deleted]
- roywiggins 4y ago
  That doesn't explain why rationals and reals are different. Rationals are a countable subset of the reals, to prove that you need to produce a method of enumerating them, not just say "they're a subset so they're smaller." Lots of subsets of the reals are uncountable, most notably if the rationals are countable and you split the reals into rationals and irrationals, the irrationals have to be uncountable. Otherwise you'd be forced to say that the union of two countable sets could be uncountable, which isn't true (if you have two countable sets you can automatically produce an enumeration of the union).
  - roarcher 4y ago
    I don't see how your point about countability invalidates what I said. Irrationals are uncountable, but there are fewer of them between 0 and 1 than reals between 0 and 1, by virtue of the fact that all irrationals are reals but not all reals are irrationals. I admit I'm using "subset" in the colloquial sense, meaning "a set that's missing some of the elements in its superset", which is not quite the correct definition (a subset doesn't have to be missing anything, i.e., every set is a subset of itself). So technically a subset does not imply fewer elements. Is that what you're getting at? I'm not particularly well versed in set theory, so maybe I'm just misunderstanding your point about countability.
    - roywiggins 4y ago
      You didn't say anything entirely incorrect, I think! But the important bit when it comes to talking about sizes of infinity is that, while both irrationals and rationals are smaller than the reals in one sense (they're both proper subsets), they're very different in another sense: you actually can index the rationals by the natural numbers whereas you can't do the same with the irrationals. That's the much more interesting sense in which the rationals are smaller (or, alternatively, that reals are bigger). The rationals are smaller than the irrationals in this sense as well, despite not being a subset of them at all.
      - roarcher 4y ago
        I think I still don't understand 100%, but that's probably my lack of formal knowledge about this stuff. I appreciate the explanation.
- contravariant 4y ago
  Depends what you mean by 'indexed'. If you accept the axiom of choice then you can index the real numbers with some uncountable ordinal.
  - roarcher 4y ago
    I meant it in the sense that I assume GP meant it, i.e., the index of an element in an ordered set is an integer corresponding to its position in that set, starting at 0 or 1 for the first element (depending on your indexing scheme of choice).
  - Dylan16807 4y ago
    Does the axiom of choice let you repeatedly pick the same real numbers in the same order out of a set? Or do you need uncountably infinite storage to keep your list of indexes?
    - contravariant 3y ago
      That's an interesting question, but kind of hard to answer. Programming is inherently constructive so approaching a non-constructive proof as a programming problem tends to be problematic. I don't think you run into any problems if you let the axiom of choice pick the same numbers every time. It would be a bit problematic if you were to add that as an extra axiom (suddenly every proof let x,y in X then ... therefore x=y would become trivial).
neonskies 4y ago
> Take the infinities of all numbers > 0 and then all even numbers > 0. Define your number first, then we'll work it out from there. From the looks of it, you are considering the integers. > So you have > 1,2,3,4,5,6,.... 2,4,6,8,........ > Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs. These sets have the same size. Two sets have the same size if you can find a function from one to the other which is bijective meaning if two sets match exactly element for element(elements don't have to be the same ones), they have the same size. For example, the sets {1, 2, 3} and {a, b, c} have the same size because we can match 1 to a, 2 to b and 3 to c. Or we can match 1 to c, 2 to a and 3 to b. So these two "matching" examples constitute two bijective functions. Going back to your example, the function f from {1,2,3,4,5,6,....} to {2,4,6,8,........} given by f(x) = 2x for x in {1,2,3,4,5,6,....} is bijective and therefore lines up the two sets in one to one correspondence. To prove f is bijective, we can find the inverse for f, multiply f and its inverse and get an identity or show f is surjective and injective. These are slightly technical, but not too bad. Any intro to discrete math textbook contains this material.
srcreigh 4y ago
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.

version_five 4y ago

We do consider both of those sets to be the same size - for infinite sets, size equality means being able to uniquely put a members from one set in correspondence with members I n another. In your example, n -> 2n provides a unique mapping so the sets are equal size (cardinality)

roarcher 4y ago

Not all infinities can be indexed. Take all the real numbers between 0 and 1, for example. If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. Now take rational numbers, which are a subset of real numbers. There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Edit: It appears my sloppy language has ruffled some mathematical feathers. My apologies.

firstlink 3y ago
> If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. This isn't "sloppy language", it's just wrong. Don't try to downplay spreading misinformation. It remains true that there are infinitely many rationals in (0, N) and (N, 1), and yet it is entirely possible to enumerate the rationals (i.e. assign indices). > There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Also misinformation. (0, 0.5) is a subset of (0, 1) yet the two sets have the same cardinality, whether we take them both in Q or both in R.
- roarcher 3y ago
  > This isn't "sloppy language", it's just wrong. Yes, no less than four people before you have explained what's wrong with my comment. I made the "sloppy language" edit before I fully understood them. > Don't try to downplay spreading misinformation. > Also misinformation. LMAO. Every incorrect thing you see on the internet isn't the work of a Russian troll or whatever you're trying to accuse me of here. Sometimes people are just mistaken. Your comment actually has some interesting points that could add to the discussion, but it's ruined by the impotent nerd rage.
- deleted 3y ago
  [deleted]
deleted 4y ago
[deleted]
roywiggins 4y ago
That doesn't explain why rationals and reals are different. Rationals are a countable subset of the reals, to prove that you need to produce a method of enumerating them, not just say "they're a subset so they're smaller." Lots of subsets of the reals are uncountable, most notably if the rationals are countable and you split the reals into rationals and irrationals, the irrationals have to be uncountable. Otherwise you'd be forced to say that the union of two countable sets could be uncountable, which isn't true (if you have two countable sets you can automatically produce an enumeration of the union).
- roarcher 4y ago
  I don't see how your point about countability invalidates what I said. Irrationals are uncountable, but there are fewer of them between 0 and 1 than reals between 0 and 1, by virtue of the fact that all irrationals are reals but not all reals are irrationals. I admit I'm using "subset" in the colloquial sense, meaning "a set that's missing some of the elements in its superset", which is not quite the correct definition (a subset doesn't have to be missing anything, i.e., every set is a subset of itself). So technically a subset does not imply fewer elements. Is that what you're getting at? I'm not particularly well versed in set theory, so maybe I'm just misunderstanding your point about countability.
  - roywiggins 4y ago
    You didn't say anything entirely incorrect, I think! But the important bit when it comes to talking about sizes of infinity is that, while both irrationals and rationals are smaller than the reals in one sense (they're both proper subsets), they're very different in another sense: you actually can index the rationals by the natural numbers whereas you can't do the same with the irrationals. That's the much more interesting sense in which the rationals are smaller (or, alternatively, that reals are bigger). The rationals are smaller than the irrationals in this sense as well, despite not being a subset of them at all.
    - roarcher 4y ago
      I think I still don't understand 100%, but that's probably my lack of formal knowledge about this stuff. I appreciate the explanation.
contravariant 4y ago
Depends what you mean by 'indexed'. If you accept the axiom of choice then you can index the real numbers with some uncountable ordinal.
- roarcher 4y ago
  I meant it in the sense that I assume GP meant it, i.e., the index of an element in an ordered set is an integer corresponding to its position in that set, starting at 0 or 1 for the first element (depending on your indexing scheme of choice).
- Dylan16807 4y ago
  Does the axiom of choice let you repeatedly pick the same real numbers in the same order out of a set? Or do you need uncountably infinite storage to keep your list of indexes?
  - contravariant 3y ago
    That's an interesting question, but kind of hard to answer. Programming is inherently constructive so approaching a non-constructive proof as a programming problem tends to be problematic. I don't think you run into any problems if you let the axiom of choice pick the same numbers every time. It would be a bit problematic if you were to add that as an extra axiom (suddenly every proof let x,y in X then ... therefore x=y would become trivial).

neonskies 4y ago

> Take the infinities of all numbers > 0 and then all even numbers > 0. Define your number first, then we'll work it out from there. From the looks of it, you are considering the integers. > So you have > 1,2,3,4,5,6,.... 2,4,6,8,........ > Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs. These sets have the same size. Two sets have the same size if you can find a function from one to the other which is bijective meaning if two sets match exactly element for element(elements don't have to be the same ones), they have the same size. For example, the sets {1, 2, 3} and {a, b, c} have the same size because we can match 1 to a, 2 to b and 3 to c. Or we can match 1 to c, 2 to a and 3 to b. So these two "matching" examples constitute two bijective functions. Going back to your example, the function f from {1,2,3,4,5,6,....} to {2,4,6,8,........} given by f(x) = 2x for x in {1,2,3,4,5,6,....} is bijective and therefore lines up the two sets in one to one correspondence. To prove f is bijective, we can find the inverse for f, multiply f and its inverse and get an identity or show f is surjective and injective. These are slightly technical, but not too bad. Any intro to discrete math textbook contains this material.

srcreigh 4y ago

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.