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)

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.

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).

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 technically the correct definition (every set is a subset of itself, i.e. a subset doesn't have to be missing anything). 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.

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.

I think I still don't understand 100%, but that's probably my lack of formal knowledge about this stuff. I appreciate the explanation.

Consider it from a measure theory point of view, at least colloquially. If you could assign a mass of 1 (lb/kg/g/whatever) to the reals and separate them into two piles: rational and irrational then weigh again. The irrational pile would weigh 1 and the rationals, 0. So yes you took something out, but also in some sense, it doesn't matter.

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

This is the important point where you are wrong. For a simpler to explain example : the naturals are a subset of the integers, and yet the set of all integers is exactly as big as the set of all naturals. We say this because we can actually find a natural number that corresponds to every integer number: 0:0, 1:+1, 2:-1, 3:+2, 4:-2,... A slightly more complicated construction exists for the naturals compared to the rationals: they are also the same size.

However, it can be shown that the same can't be done between the naturals and the reals, or even any real interval. So, by this definition, there are more real numbers between 0 and 1 than there are in the entire set of natural numbers.

Depends what you mean by 'indexed'. If you accept the axiom of choice then you can index the real numbers with some uncountable ordinal.

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).

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?

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).

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

> This isn't "sloppy language", it's just wrong.

Yes, no less than four people 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. Have you considered getting a life?

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

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.

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

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?

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

Thank you! Great insight!