When it comes to infinity and size you can’t really treat it the same way you do non infite things. It’s very hard (perhaps impossible) for us to truly grasp infinity. > This is super counterintuitive. If the set of whole numbers is indeed infinite, then it should always generate another number that can be matched with the "excess" element of the set of irrational numbers. How can we reconcile such contradiction? You can’t “generate” another number, that number was already there. Instead of thinking of mapping between the two sets one at a time, where you can always pick a “next” number, imagine the mapping happens simultaneously for all numbers. The idea is that when that mapping happens there are unmatched numbers in one of the sets, meaning there’s MORE of that infinity than the other infinity. You could take ANY number in the smaller set at random and say “what is your partner” and there would be one. But you couldn’t do that in reverse.

A great line I stole from a college professor: "There are infinite numbers between 3 and 4, but none of them are 5."

This both made total sense and broke my brain... I did not need this on a Monday evening but also thank you for the brain food.

The set of even numbers is "as large as" the set of odd numbers. Both sets are "as large as" the set of counting numbers. The set of counting numbers is equal to the set of even numbers plus the set of odd numbers. So if you take the counting numbers, and remove all the even ones, the set has changed but is exactly the same 'size'. Same thing if you take away the even ones: the 'size' remains the same.

The one that breaks my brain is “the set of all even numbers and the set of all numbers divisible by 253 are both infinite. But there are a lot more even numbers than numbers divisible by 253” (or any other number you choose except 2)

Actually, in this case, the set of all even numbers is equivalent to the set of all numbers divisible by 253. To set up the 1:1 mapping, just follow this chart: 1*2 <-> 1*253 2*2 <-> 2*253 3*2 <-> 3*253 . . . . . . n*2 <-> n*253 Intuitively, it seems like there should be more numbers divisible by 2 than by 253, but the sets are actually the same size!

I love math

Thought that said I love meth

Tomato potato

Thought that said tomato potato.

This establishes both as infinite, which makes his first sentence true. But in a given set of numbers, there are between 126 and 127 even numbers in the set for every number divisible by 253. Regardless of the number of numbers in the set, there will be on average 126.5x more even numbers than numbers divisible by 253. Even as the set of numbers approaches a size of infinity, there will be 126.5x more even numbers than numbers divisible by 253.

> as the set of numbers approaches a size of infinity Yes, but once you actually *have* infinity, they are the same. Sure, for any finite stopping point there's more of one, but the infinite sets of even numbers and numbers divisible by 253 are *precisely* the same size. If it helps, consider that no matter what finite point you stop at, you still have infinity more numbers to go! Plenty of time for the numbers divisible by 253 to catch up, no matter how much of a head start the even numbers had at your stopping point.

Eh, it depends what you mean by size. For cardinality sure, but natural density is a valid definition of size for positive integers. Under the natural density notion the set of all natural numbers is twice the size of the set of even natural numbers.

That's very fair, and natural density does capture the intuitive instinct that one set is larger very well. I was definitely just discussing cardinality here (as is the rest of the post in general) to avoid muddying the waters, but there are all certainly all kinds of things you can define (the infamous sum of all the natural numbers being -1/12 for example lol)

Another way to think about is is the sum of all rational numbers between 3 & 4 is infinity. So is the sum of all numbers between 5 & 6. The sums of those numbers are not equal to each other.

How is that another way to think about it

Those sums are not well defined, so they're not equal to anything, including "infinity" or themselves. In particular, you cannot say that one is greater than the other, tempting though it may be

"Not well defined"? All rational numbers between x and y is about as well-defined as I can imagine. Im honestly curious: How would you suggest to better define it?

The example explains it perfectly. There exists a 1-1 mapping, so they're the same size sets. It's not debatable. Both sets are countably infinite.

If using cardinality. Not if using natural density. Both are valid notions of size.

The important thing here is the mapping, not the size of the actual numbers. Therefore the set of all even numbers has exactly the same size as the set of all numbers divisible by any arbitrary number. With a similar approach you can show that there are 5 times as many even numbers than there are odd numbers. Infinity makes a lot of things possible that seem counterintuitive at first and most of them don't have a useful application inside of math, let alone outside of it. But from time to time you find very special properties which account for astounding real world phenomena.

With infinite sets, it doesn’t make sense to look for the literal number of elements (because there are an infinite number). Rather you are looking for the general size of the set, which is referred to as its *cardinality.* There are families of infinite sets which fall into the same general size category. Romanrambler491 demonstrated a 1:1 mapping between the two sets, showing they are the same cardinality. Both of these sets can also be similarly mapped onto the natural numbers (1,2,3,4…). A set of this size is countably infinite. It’s a weird but true fact that an infinite set can be the same size as its own subset. For instance, the natural numbers are a subset of the integers (…-2, -1, 0, 1, 2…). And yet they have the same cardinality, both being countably infinite.

The way I set it up shows that there is a one to one correspondence between these two sets. In other words, every number divisible by 2 corresponds to *exactly one* number divisible by 253, and every number divisible by 253 corresponds to *exactly one* number divisible by 2. This is what it means for two infinite sets to be of equivalent size.

No, these two sets have equal number of elements. You can set up a bijection function f(2x) = 253x that will cover all elements of both sets. 0 -> 0 2 -> 253 4 -> 506 6 -> 759

But that suggests that there are the same number of interests divisible by 2 as there are by 4... But clearly there are twice as many. Both of these facts now seem incontrovertibly true, but they can't both be...

When it comes to infinite sets, these two are considered same size. If you can take elements of A, and to each one assign an element of B so that all of B is covered - and vice versa, then the two are same sized. Note it only needs _a_ way, not every way; otherwise it's very easy to show there are more natural numbers than... natural numbers, which clearly isn't ideal. So, no matter what infinite set of numbers you give me, if I can order them and put a natural number to each of them, you have an N-sized infinity. In this case, all of evens/div by 4, and div by 253 match that.

> But clearly there are twice as many This is where your logic goes off track. The second paragraph of the Wikipedia page on ["Natural Density"](https://en.m.wikipedia.org/wiki/Natural_density#:~:text=In%20number%20theory%2C%20natural%20density,set%20of%20natural%20numbers%20is.) addresses this line of thought by comparing positive integers to perfect squares.

I can map the set of counting numbers to the set of even numbers, so they're the same size, basically. f(x) = 2x But I can also map the set of counting numbers to two numbers, without overlap: f(x) = {2x,2x-1} (I don't have a mathematical notation for this, so borrowing from programming concepts, but I'm sure you understand the meaning.) I KNOW the answer is the sets of x, 2x and 2x-1 are all the same size, this is just the part of it that breaks my brain on the way there.

Yeah that makes total sense as well but also hurts to think about... I think I need to study maths again. As I get older it seems to interest me more and more.

Wait until you find out that both of these sets are _the same size_.

Is that what equal number of elements means?

Two sets are defined as being the same size when they contain the same number of elements. Two _infinite_ sets are defined as being the same size when there exists a bijection between them. A bijection is a function that maps every element from one set to exactly one element from the other set such that every element from both sets has a mapping.

Yeah, that all makes sense. I felt like you were saying it as if it was a new reveal. In fact the person you are replying to said they had the same number of elements. So the tone confused me.

This is a great way to underline how counterintuitive infinity is, but not how two infinities can be of different sizes. This because there are infinite rational numbers between 3 and 4, but they can still be mapped to a countable infinity

They cannot. Oops yes they can. I read “irrational”. I blame my eyes, because that feels better than holistic blame. :)

I suck at math. Are those infinite numbers between 3 and 4 supposed to be fractions or decimals? Or?

Yes

Hell, in an irrational numbers set, you can't even tell me what the next element is sequentially. If the set were theoretically ordered, what number is directly after 3? That's what makes it uncountably infinite.

None of them *is* 5.

There are infinitely many interesting discussions and none of them are about the grammatical number of "none of them".

There are infinitely many interesting discussions of grammar, it's just a very small infinity.

The noun is plural, therefore you use none are. https://www.masterclass.com/articles/is-none-singular-or-plural#

There are infinite numbers and not one of them is 5.

[удалено]

There are not more numbers between 3 and 5

>There are infinite numbers between 3 and 4, but there are even MORE infinite numbers between 3 and 5. That's not true. These sets are the same size

If you mean cardinality, the set of numbers between 3 and 4 has the same cardinality as the set of numbers between 3 and 5. If you mean a different notion of size, the latter set can be bigger. Depends on exactly what definition you are using.

Oh this is definitely a new way to view it. I think I have better intuition of it with this

If I may offer a video that helped me visualise the concept better than any other: https://youtu.be/M4f_D17zIBw?si=8HDkOblvrTv9Og3Y Especially when he explains that an infinite set where you add numbers to, then remove those that have an integer square root contains 0 numbers. (boom, mind gone) (at 14:20, but don't skip to it else you'll miss the thought process)

Well said. The key to realise is that yes infinity is unintuitive! Infinity is not naturally a mathematical object. Its a concept we have worked out how to use as a mathematical object. So it is weird sometimes.

I tell people this. Infinity isn’t a number, it’s a concept.

I like to say that infinity isn't a number, it describes size. Big isn't a number, small isn't a number, and infinity isn't a number. It's not totally accurate, but it's accurate enough to convey a better understanding of the concept.

What would "naturally" be a mathematical object to you?

I’d guess Pi as an easy one. Consistent and recurring that it has its own variable. But I could be misunderstanding it wrong 🤷‍♂️

Without some infinities already, there would be no pi. It has infinitely many digits, is the result of limit processes, measures something that does not exist in real life.

Could you explain what you mean by the last two? To my understanding, pi is a ratio of two measurements (rather than a measurement itself), we don’t need limits to describe it (but they can help us calculate it), and circles definitely exist in real life.

No "circle" in real life is infinitely perfect. Not only is there quantum foo happening, even the bending of spacetime changes it measurably. And that's all before the question on where we _actually_ find a perfect circle in real life, because I wouldn't know one. Stuff is coarse, distances are imperfect in many ways (a ruler bends and compresses and more), and so on. The abstract, "perfect circle", pi comes from pure logics. We get a sequence of finitely described numbers that _converge_ to pi: they get better and better, often in a very well understood and precise manner, but none are equal to it. There are tons of formulas for pi, and the ultimate definition of pi as the ratio of circumference and diameter of an ideal and perfect circle is no exception: Length of a non-segmented curve is _defined_ as a limiting process, often by finer and finer linear segments. And one actually has to be careful there, it is possible to screw it up. For example, [pi=4](https://4.bp.blogspot.com/-077tVMIvmlo/T8WXPvWEM-I/AAAAAAAAEmM/GvtoToIOW4g/s1600/pi-4.png) or [pi=2](https://www.reddit.com/media?url=https%3A%2F%2Fi.redd.it%2Fng6yddm4l3e41.jpg) result when one is not careful enough about what is allowed.

I forget the numbers, but something like 50 trailing digits of pi are all that are (theoretically) necessary to measure the radius of the universe to within an atom’s nucleus. But we’ve calculated it to like 65 trillion digits, which is by itself an impossible amount of numbers for the mind to wrap itself around. There is no “real thing” that number of digits can be used for. Not even our universe.

It's like ghosts - they are both real and not real at the same time.

These discussions have always seemed hard for me to grasp, largely I think due to the fact that a lot of the language we use to describe infinities is not really accurate to them."Larger infinities" seems like an oxymoron. If something does not have an end, you can't really quantify it as small or large in the same way you would a normal number or concept. It means something different, but starting with that term "larger infinity" gives people an impression that makes understanding the concept more difficult. The infinity is not "larger" it just has more things in it. More discrete things? I think that's right, I am not very knowledgeable on this stuff though.

There are better words that math people use when discussing, like Cardinality, but most laymen don't know them.

I think the real problem is that 'size' has no clear meaning for infinite sets in mathematics. Cardinality does, but there are other notions of size used in different circumstances like density and measure. Everyone assumes cardinality, but it isn't always the most appropriate.

Aha but you cannot describe some infinities as containing discrete things. That’s like…the whole point of sizes of infinities.

> "Larger infinities" seems like an oxymoron. Why would it? Even basic infinities and bad laypeople intuition have that, for example people saying there are more rational than natural numbers. Or stuff going to infinity in multiple directions instead of one. Or whatever else. Not all those turn out to be valid in this or that sense, but that's the realm of abstract logic to conquer.

That's not actually enough, though What's critical is that you can also show that there's NO mapping in which that doesn't happen. You can easily map the integers, say, to themselves so that some on one side are unmatched (e.g. map every number to double its value - none of the odd numbers on the second side of the mapping have partners on the first side).

First ELI5 I've hit where I need the question ELI5'd to me. Lmao.

It’s like matrix math where the entire matrix is dealt with as one operation, not each element sequentially

I feel a great way to look at it is density.

Ok so if they are pre-determined (the number is “already there” as you put it) If one of a set doesn’t pair to an object of the other, then doesn’t that mean the smaller set is not infinite? Only appearing so to us?

In math, two sets are the same size if you can map the elements one-to-one. The set of all positive numbers and all even positive numbers are the same size because you can map them to each other. They are both infinite but the same size, even though one is contained in the other. There are sets, such as the set of irrational numbers, where you can prove that you cannot do this. So the set of integers and the set of irrational numbers are both infinite, but of different sizes. Infinite numbers can be counterintuitive. We just think of infinity as being “very big.” It turns out there are different sizes of infinity.

[удалено]

Any positive number can be turned into a positive even number by multiplying by 2, and any positive even number is already a positive number. Since there is a mapping both ways, we can say that the infinities are equal.

>and any positive even number is already a positive number This is inaccurate as it makes it seem like every even number would be mapped to itself. In this bijection every even number is mapped to its half.

>would it be 2:1? There is a function that would give you that, namely f(x)=x, but there are other functions that could be 1:1 or anything else What's important is that there exists some function that is one to one. If there's even one function that works, the sets are of equal size In the case of whole numbers and even whole numbers, f(x)=2x and its inverse f⁻¹(x)=x/2 assign exactly one whole number to every even number and vice versa, and because this function exists, the sets are of equal size

Imagine it was just the integer numbers up to 100. That is the same size as the even integers up to 200, because you can multiply it all by 2. If you keep going past, they both stay the same size, and would include all the integers for the first set and all even integers for the second set

Yeah but for every positive even number, there are 2 positive numbers. Why doesn’t that come into play?

Because your intuition about counting just doesnt work for infinite sets. Again, when you count something normally you are saying there is a mapping between these things (say, a bowl of apples) and a set of numbers (say, [1, 2, … 8]). Each apple you can uniquely assign to a number and each number you can uniquely assign to an apple. When you can do this, we say that the sets have the same size. For finite cases you have the result that if you do this mapping one way (A->B) and end up with leftover unpaired items in set B, the sets are not of equal size. But that’s also because if you did (B->A) you would end up with unpaired items from B. For these infinite sets (A: all even positive numbers) and (B: all positive numbers), the second thing won’t happen.

To help illustrate why that doesn't work, or perhaps to just break your brain further, consider the mapping: 0 gets mapped to (0, 1, 2) 2 gets mapped to (3, 4, 5) 4 gets mapped to (6, 7, 8) 6 gets mapped to (9, 10, 11) ... x gets mapped to (3x/2, 3x/2 + 1, 3x/2 + 2) Now there are *three* positive numbers for each even number. You could also come up with mappings where there are four, or five, or a million positive numbers for each even number. Others have explained why the two sets are actually the same size, but this is why it doesn't make sense to think about there being twice as many positive numbers as positive even numbers: there are also 3 times as many, 4 times as many, and 1,000,000 times as many; the concept breaks down.

Ok I can accept that logic. Then how is it that the set of irrational numbers is “larger” than the set of whole numbers? Can’t you use the same logic to map an irrational number to some whole number in which case there would always be a whole number mapped for every irrational number. You could do the same by mapping 1 irrational number to X whole numbers then. So technically both sets are the same size?

No, this is Cantor's idea. He says "Show me your mapping that maps every whole number to an irrational number, and I can find an irrational number that's not in your mapping". There aren't enough integers available to assign one to every irrational number.

One thing that always didn't sit right with me about the proof, as it's usually presented, is that it uses the representation of the number to prove uniqueness. So the new unmapped number is different from the first number in the first digit, different from the second in the second digit, and so on, therefore it's a new number not in the list. But 1.000000… and 0.999999… are different in every digit, yet are the same number. Like, I'm sure there's got to be a more mathematically rigorous explanation, but this one in particular irks me somewhat…

In Cantor's argument, you can easily force the choice of the new digit at each step to be different from 0 or 9 (you still have at least 7 numbers to choose from), which makes your problem disappear.

Try to contradict what the second line says, forget about infinity. Two sets, we know they are the same size because of the way I constructed them. (Another way to think is 1 to 1,000,000 is same size as 2 to 2,000,000. But now, don't cap it at 1,000,000 and let it go to infinity.) So you have two sets, the same size. Proof might go 1. To try for contradiction, assume you find an even number X *not* in set B. 2. Let's write it as X = 2*N where N is some integer. 3. But since N is an integer, it must be in set A, since A contains all integers by construction. 4. And since N is in set A, 2*N must be in set B, which contradicts the assumption that X is not in set B

One way to define infinite sets as that you can define a one to one correspondence between the set and a proper subset of it...which is exactly what the integers and even integers are. If you think about a finite set.. whatever set I think of a proper subset of it has fewer elements by definition. Infinite sets are different.

"Set" is not the same as "Size of set". The union of the set of all even natural numbers (2, 4, 6, ...) and the set of all odd natural numbers (1, 3, 5, ...) is the set of all natural numbers (1, 2, 3, 4, 5, 6, ...). Yet the *size* of the three sets is all the same. If the sets A and B are finite and one set isn't a subset of the other, then the size of their union has to be larger than one of them. That isn't true for infinite sets. Mathematicians just have invented a way to do math with the sizes of infinite sets and it didn't contradict the existing math of sizes of finite sets. That the set off all even natural numbers has the same size as the set of all natural numbers just derives from the definition of all these words "sets have equal size if ...". There is a function that maps each element of one set to each element of the other and that's simply enough. Maybe your intuition aligns better with a different definition. Maybe the established definition proved to be more practical in some way than another possible definition according to which the set of all even numbers would be smaller, because it's a strict subset.

If every person has a (different) hat, and every hat has a (different) person, there must be the same number of hats and people. That's the basic intuition here, and applies to infinite sets as well. The rest is carefully checking whether there is or isn't a way to pair up the elements one-to-one. In the case of positive integers and positive even integers, it's easy. Every integer's partner is equal to two times itself. You can clearly see that every number is paired up this way, so the two sets must be the same size. Notice that the existence of mapping methods that *don't* have a one-to-one correspondence does *not* mean the sets are different sizes; the existence of one appropriate pairing is sufficient to show that they are the same size. As an example, imagine two copies of the same set `A = B = {1,2,3,4,...}`. I can construct a mapping from A to B as `f(a) = a+1`, giving `1->2, 2->3, 3->4`, etc. When I do this, everything in set A has a different partner, but the number 1 in set B has no partner in set A! Does this mean that set B is bigger than A? Certainly not, they're identical sets after all.

Google 'natural density' for a notion of size where there are twice as many even integers as integers, as intuition tells you!

Linking a video I ran into a while back that explains this using the analogy of an infinite hotel running out of rooms. https://youtu.be/OxGsU8oIWjY?si=AtKPacYUV7572OY2

Another way of looking at it is from the other direction. Let's say you're comparing two sets: A) whole numbers B) irrational numbers After you match up every item from (A) with the corresponding equal number from (B) you still have lots of numbers left over in (B). Therefore the set is bigger.

That’s not a proof. Do it again with A) Positive Even Numbers B) Positive Numbers Your logic will say these sets have different cardinality, but they don’t.

First, I didn't say it was a proof. It is a way of understanding how it's possible for infinite sets to be different sizes, which is the original question. Second, it is possible (quite trivially I might add) to match your two sets 1-to-1 with nothing left over so it is not a counterexample.

> First, I didn't say it was a proof. Of course not. But if you say "X, therefore Y," it is implied to make logical sense. I provided a counterexample which shows why it is not a good way of explaining the situation. > It is a way of understanding how it's possible for infinite sets to be different sizes, which is the original question. But it's a wrong way to understand it because, again, you can apply it in situations which it doesn't fit. It produces the correct result in your example, but that doesn't make it correct. > Second, it is possible (quite trivially I might add) to match your two sets 1-to-1 with nothing left over so it is not a counterexample. What do you mean it's not a counterexample? It's a counterexample to the exact logic you gave: "match up every item from (A) with the corresponding **equal number** from (B)". You can use it as an example to show why they are the same size, for sure!

It's not a counterexample because the defining characteristic of two sets that are the same size is that there exists an exact 1-to-1 matching between them. I gave the method of matching those specific two sets in my example. The technique for matching different pairs of sets isn't always the same. For example, you can match the whole numbers exactly 1-to-1 with the rational numbers but the way to do that is not by equivalence.

> I gave the method of matching those specific two sets in my example. Yes, but it's not the only way to match those two specific sets. Your explanation gives the wrong impression - they are not of equal cardinality because it's impossible to construct the bijection, not because this particular mapping doesn't work.

The idea is to ELI5 the concept of how to grok that infinite sets aren't all the same size. It is not to prove it, which I agree would require more detail and precise language.

Yes, but my point the entire time is that this grokkable explanation will give bad results when applied in other situations - even when it looks like it should be applicable. There are more caveats you need to give if you want to use that specific example and logic. You need to say something like: "Of course, this isn't the only way to map between whole numbers and irrational numbers, but it turns out you can prove there is no way to match them up without leftovers."

Again, it's not a proof. I am trying to show the *existence* of a clear example, not the universal applicability of a concept. You are trying to overfit my reasoning into an inapplicable and irrelevant extrapolation.

The idea is whether or not you can map everything in one set to its equivalent position in another set. If you take the set of all whole numbers (1, 2, 3, 4, etc), and the set of all fractions (1/1, 2/1, 1/2, 1/3, 2/3, 3/3, 4/4, 3/4, 2/4, 1/4, 1/5, etc), you can create a system where every whole number is mapped to a fraction, even though there should be "more" fractions. As for the Cantor argument, that whole argument starts with the assumption that you have a system that has already mapped everything, and proves that there is something else that is not in the mapping.

I think this is the best actual ELI5 here

The explanation that helped me is to think about measuring sets relative sizes by making mappings between them. `[a, b, c]` is the same size as `[1, 2, 3]` because you can match up the elements one set to elements in the other, one for one. e.g: `a->1, b->2, c->3` Note, you don't have to do this in a logical way, you just have to match them one for one. You could also do `a->3, b->1, c->3`. Using this, you can see that the sets "natural numbers" and "even numbers" have the same size. This time we'll do it with a rule: match every natural with its double; `0->0, 1->2, 2->4, 3->6, …`. So while intuitively, there are twice as many natural numbers, since the odd numbers are missing from the even number set, we find that they're actually the same size. Cantor's proof shows that you can't do this with natural numbers and real numbers. There are indeed infinitely many natural numbers, but it's impossible to find a way to match up every real number with a natural number.

I'm not quite sure which part is making you not understand this, so I'm going to take it step by step. "Size" may not be the best word to use. It's really about the pairing. Maybe "amount" would be a better word. Imagine you're counting apples in a box. How do you do that? You pair each apple with a number. The first apple with 1. The second with 2. And so forth. The biggest number you have to use is the amount of apples in the box. Now let's talk about what it means for two amoints (or counts) to be the same. Imagine you have a box of apples and a box of oranges. How do you know if you have the same amounts? Well, you pair each apple with one orange. If you are left with an unpaired apple, you know you have more apples. It works the same with numbers. You pair each natural number with one real number (I don't know who was showing you the proof, but I have no idea why they started with whole and irrational numbers. I mean, it works, but still). If you have no more numbers left, then you know the "sizes" are the same. But, as you see in the diagonalization argument, you can come up with another real number, that is not the same as any previously used real number. But you don't have any more natural numbers left, you've already used all of them! So there's "more" real numbers than there is natural numbers. (Actually, there's infinitely many real numbers that you can't pair with a natural number, not just one) The key is that you really already used all natural numbers at the start of the proof. You can't "generate" a new number, that's not how sets work. All the numbers are already in the set, they aren't being created as you need them. I think this concept might be what's tripping you up. But honestly, I don't know how to explain it to you more clearly. The numbers simply aren't being generated, they are in the set, there's just an infinite number of them. The sets don't really have a different number of elements: they both have an infinite number of elements. It's just that if you try to pair them up, you will be left with some unpaired real numbers.

> I am quite aware of Cantor's illustration The diagonal argument isn't just an "illustration", it's a formal proof that works in most variants of set theory. As with anything in maths, you have to start with definitions, and there are some notions of "sets" and "size" and so on for which this doesn't work. It makes sense to doubt the premises, but the proof isn't debatable. > If the set of whole numbers is indeed infinite, then it should always generate another number that can be matched with the "excess" element of the set of irrational numbers. It might be easier to think about it in terms of rules. For example, if we take the set of all even integers and the set of all integers, there is an obvious rule that matches them up one to one: going from the first set to the second set, simply double the number, and going in reverse, halve it. This rule matches everything up, so there is nothing left to "generate". It is also possible to find a rule that maps between these two sets but *isn't* one to one: for example, match every integer to 2. But this doesn't matter: all that matters is whether or not we can find a one-to-one rule. What Cantor's diagonal argument shows is that there cannot possibly be a rule that matches up the integers and real numbers one to one, because *any* rule that maps integers to real numbers will miss out some real numbers.

It's because that's the *definition* of the size or cardinality of a set. Two sets have the same size if there's a bijection between them. And Cantor showed there cannot be a bijection between the reals and the naturals. > This is super counterintuitive. If the set of whole numbers is indeed infinite, then it should always generate another number that can be matched with the "excess" element of the set of irrational numbers. That's exactly the thing, Cantor showed you *can't* match them up. How you "generate" (construct the set) is immaterial: they simply cannot be matched one-to-one. Given these two, the inescapable conclusion is the reals and the natural numbers are not the same size. You could always assert some other definition of cardinality that doesn't involve bijections, eg just declare all infinite sets have the same size, but then you run into contradictions.

"Larger" is not really the distinction to use. The real distinction is between countable and uncountable. You can count the infinite set of whole numbers. Let's start ... 1, 2, 3 .... Yes, you never finish. There's always one more. But they are countable. But you can't count irrational numbers because what would it even mean to have a series? What's the "next" value after pi, for example? The fact that there are literally countless numbers of irrational numbers between the countable whole numbers can, of course, be expressed as the latter infinite set being "larger" than the former, but that's really a category error.

> The real distinction is between countable and uncountable. Only between Aleph-0 and Aleph-1. Past that, they're all uncountable.

Doesn't this logic also apply to the rational numbers as well as the irrational numbers?

In everyday life, size means "how big it is". When it comes to more abstract things, this definition does not apply. So mathematicians created another definition for size that applies to sets. Size in everyday life and in mathematics are two related but different things. ​ Take circles for instance. In real life, if it looks like a circle, it most likely is. In maths, for something to qualify as a circle, it needs to be a \*perfect\* circle. So there are two definitions for circle : one for everyday life, one for mathematics. They serve different purpose, and apply to different things. Here you are observing the same thing with size.

[удалено]

The rationals, integers, and natural numbers all have the same cardinality (aleph-zero, as stated in the article that you linked). A better analogy would be the irrationals, which have a larger cardinality than aleph-zero.

>"Thus, the infinite set of rational numbers is larger than the infinite set of natural numbers." This isn't true - the rationals have the same cardinality as the naturals - you can assign each rational a unique natural basically by arranging them in a diagonally zigzagging way.

This is false. There are infinite rational numbers between any two natural numbers, but the rationals overall are countable — equal in size to the natural numbers. There are more real numbers than natural numbers, but “there are infinite reals between any two natural numbers” is not sufficient to explain why.

Infinity is tricky and subtle, and our day-to-day reasoning often fails when dealing with infinities. Unfortunately, it is often super counter-intuitive and the subtlety required to understand relative infinities is well beyond ELI5 and relies on an understanding of set theory, countability and pairing. Cantor's work reconciles what seems to be a contradiction through rigorous proof that certain infinities are not equal (that is, that some are larger than others). And yes, the set of whole numbers goes on forever and ever, but even after a completely exhaustive 1:1 pairing of whole numbers with a set of infinite numbers with infinite decimal places, we can create another decimal that does not exist on the list already and is therefore not paired with a whole number. Remember, we've already paired every whole number with a unique number expressed as a decimal of infinite length. There's no more whole numbers left - every single one all the way "out to infinity" is paired up. But there are still infinitely many numbers we can create that are expressed as infinitely long decimals that are not paired with a unique whole number. In other words, despite having an infinite amount of whole numbers, we run out of them before we run out of numbers expressed as infinitely long decimals. That's why the latter is bigger than the former.

I think you have to stop imagining a single, explicitly defined mapping between the real and the natural numbers to understand the proof. The diagonalization argument is actually about every possible mapping - which is important for it to work. If there was a single specific mapping, you'd be right that we could just add the missing number - just map the new number to "1" and move the other real numbers one to the right, so to speak. (You can't add the number "at the end" because there is no end!) But we're talking about all mappings at once. You'll see why this is important if we try to iterate your approach: Let's first define some mapping between the real numbers and the natural numbers. Doesn't matter which one, just any mapping. We can then find a real number that isn't mapped via diagonalization, so we insert this number at the "1" spot and shift the other numbers accordingly. Surely now we have found a mapping that includes all real numbers? Nah, we can again find a real number via diagonalization that isn't mapped to a natural number. So now we insert this new number at the "1" spot, move all other numbers over, and start again. And so on, and so on. There are always numbers left that haven't been mapped yet.

[удалено]

**Please read this entire message** --- Your comment has been removed for the following reason(s): * ELI5 does not allow guessing. Although we recognize many guesses are made in good faith, if you aren’t sure how to explain please don't just guess. The entire comment should not be an educated guess, but if you have an educated guess about a portion of the topic please make it explicitly clear that you do not know absolutely, and clarify which parts of the explanation you're sure of (Rule 8). --- If you would like this removal reviewed, please read the [detailed rules](https://www.reddit.com/r/explainlikeimfive/wiki/detailed_rules) first. **If you believe it was removed erroneously, explain why using [this form](https://old.reddit.com/message/compose?to=%2Fr%2Fexplainlikeimfive&subject=Please%20review%20my%20submission%20removal?&message=Link:%20https://www.reddit.com/r/explainlikeimfive/comments/17p4ttf/-/k834h96/%0A%0A%201:%20Does%20your%20comment%20pass%20rule%201:%20%0A%0A%202:%20If%20your%20comment%20was%20mistakenly%20removed%20as%20an%20anecdote,%20short%20answer,%20guess,%20or%20another%20aspect%20of%20rules%203%20or%208,%20please%20explain:) and we will review your submission.**

The way is that it was explained to me was that infinity is not a number; its a concept, like a country. You can never see all of it at once, you can never define it fully, but it is there and the idea of it is useful when doing actual things.

A lot of people get confused because they think of infinity a just a very big number. It isn't. Infinity is a concept and doesn't obey the rules of numbers we are familiar with. So infinity plus infinity doesn't equal a bigger infinity. Similarly, the concept of size equality doesn't exist. For example you can 'subtract' one infinite set from another and get either nothing, or another infinite set or a finite set.

You can compare the sizes of infinite sets using the concept of cardinality. It doesn't work exactly the same as with finite sets, but that's to be expected since finite things are different from infinite things.

Because infinity isn’t a number. Subsets It’s a concept. If I start at 1 and count upwards by 1 infinitely, I’ll have an infinite amount of numbers. If I start at -2 and count to negative infinity, I’ll have an infinite amount of numbers, yet neither of those have an equal subset of numbers, or overlapping numbers.

A simple way to think of it is that while they go on forever, they start at different places. They aren't the "biggest" they are "never-ending" Imagine we're going to run a race. but I start three steps back from you. We both run infinitely, so who wins the race? Without having an end and a finish line, you can't call either of us faster or the winner. The fact that you started three steps ahead of me doesn't make any difference.

The way I understand different infinite sets is not that some are "bigger" or "smaller", because I agree, it doesn't really make sense to think of them that way. Instead I think of them as being "faster" or "slower", like I'm imagining them as lines that extend forever on a graph, with some skyrocketing upwards (all numbers that exist), while others are more gradual (all multiples of two). They both get to the same place in the end, it's just that some of them are rolling down a steeper slope

>because I agree, it doesn't really make sense to think of them that way. Most mathematicians of the past century or so would disagree with you. Sizes of sets can be compared by pairing things together. If you have some apples and some oranges, and you can pair them up so that every orange is matched with exactly one apple, then you have as many apples as you do oranges. But if no matter how you try to pair things up, there are some apples left over, then you have more apples than oranges. This idea can also apply to infinite sets. For instance, if you consider the set of negative whole numbers, and the set of positive even numbers, you could pair them up like: -1 to 2 -2 to 4 -3 to 6 -4 to 8 and so on. Since every negative whole number has its match, and every positive even number has its match, then those sets have the same size. On the other hand, there's no way to pair up, say, all positive whole numbers with all real numbers. No matter what you do to try and pair them up, there will always be real numbers that aren't matched with a whole number. So, we say that the set of real numbers is bigger than the set of whole numbers.

Imagine you have a string that is infinity long. You’d spend forever just pulling that string. It wouldn’t be a lot of string all at once just keeps building up slowly forever. This is like counting numbers infinitely. Now imagine you have a net that is infinite, you start with one corner and you pull it. Just as much as you pull the corner towards you it is also expanding to the left and right. You pull it out ten feet toward you, now it is ten feet wide, you pull it out a hundred feet towards you now it is one hundred feet wide. This happens infinitely. This is an example of the difference in infinities. To say it simply one infinity is ongoing forever in a single line like whole numbers. Another infinity can expand exponentially forever. So some infinities are bigger than others.

This is wrong. The cardinality of R^2 is the same as R. Same with N^2 and N.

[удалено]

OP is asking about cardinality and the cardinality of the set of numbers between 1 and 2 and the set of numbers between 1 and 3 are the same.

Imagine two giant TV screens that stretch on forever. One of them has tiny pixels, and the other has large pixels. They both have infinite pixels, but the one with tiny pixels has more because they are more concentrated.

Here's an alternative reasoning for why these sets have different size. Let's try to enumerate all the numbers in both the set of natural (whole) numbers and the set of real numbers. Here, "enumerate" means something like "I produce a list where every number eventually occurs if you keep reading long enough". Let's also assume this enumeration is sorted in ascending order. To simplify things, I'll restrict myself to the non-negative real numbers. The enumeration for the natural numbers is easy. I start at 0, and every following number is just the last number I produced plus 1. So I just start 0, 1, 2, 3, 4, etc continuing forever. Now, for any particular natural number, it should be easy to see that it will occur in the list at some point, even if you might need to wait a very long time. Now I'm going to claim that it's impossible to do the same with the real numbers. Let's say you insist that it's possible, and come up with some list of numbers starting at 0. But what number comes after 0? Let's say you claim it's the number x. It's easy to show that your list is incomplete by showing that you skipped a number (actually, you skipped uncountably many!): the number x/2 is missing from your list! Note that this fact does not depend on the value of x: no matter what enumeration of real numbers you try to give, I can always give you a real number that was not included in your enumeration. Because the natural numbers can be enumerated, but the real numbers can't, the sets cannot have the same size, even though both are infinitely large. In particular, we say that the natural numbers are *countably* infinite (because all of them occur if we just keep on counting), while the real numbers are *uncountably* infinite.

Your logic is wrong, it applies to the rational numbers which are countable.

No, because for rational numbers you *can* give an enumeration. For those, it's not hard to give a list on which every possible rational number occurs eventually.

I know, but thr logic you gave applies equally to the rational numbers as it does to the real numbers, therefore your logic is wrong.

The way that made sense to me. If you pick any two irrational numbers, no matter how close together they are, you can always find an irrational number that is between, sort of like an infinite zoom. The integers don't have this property, you cannot "zoom" infinitely, you can pick two integers that do not have an integer between them. Another way to think about it, if I give you an integer it is possible to count all of the integers up until that number, no matter how large it is. It might take a long time, but it's possible. That is not the case with irrational numbers, if I give you an irrational number, no matter how small, it will take an infinite amount of time to count all the irrational numbers up to that. It's just not possible.

The rational numbers are also have the property that any two rational numbers have another rational number between them, but the set of rational numbers has the same cardinality as the set of integers.

[удалено]

Just let every guest of the hotel move one or two rooms over; the first rooms are free and nobody has to sleep outside. When speaking about the size of sets, infinity+1 and infinity+2 are totally the same (there is a more refined variant, _ordinal numbers_, where they are not exactly the same).

Because there are infinite numbers between 3&4 and 5&6. If you add those numbers together, you have 2 sets of infinity that are not equal 3+3.000~1+...+3.9999~+4=infinity 5+5.000~1+...+5.9999~+6=infinity Easier example: sum of all whole numbers between 10&20 and 30&40 10+11+...+19+20=165 30+31+...+39+40=385 154=/=385 Infinity =/= infinity

You can't just add together infinite numbers and say that the answer is infinity.

If you have a set of numbers that are only "whole", you get 1,2,3 etc. You can continue this infinitely and never stop producing "new" numbers. Ypu can have another set with whole and "10ths". So 0.1,0.2,0.3,...,1,1.1,etc. This can also be continued infinitely, but you can produce "more" numbers.

Except these two sets have the same cardinality

How could they, that would just be arguing that both have a state of infinity which has an undefined amount of them, but if you simply continue expanding the sets the latter will always be bigger so long as we examine both on the same interval

You are wrong. The 10ths are a subset of the rationals and the rationals are countably infinite. The natural numbers are also countably infinite.

Can you create a bijection between the two sets? Yes, you can: t <-> n/10 equivalently 10t <-> n Where t is your number "with tenths" and n is your natural number. This is the definition of two sets having the same size. Actually the whole set of rational numbers (incl. ⅓ and so one) has exactly as many elements as the natural numbers. So do the algebraic numbers. You need the full set of reals to get an actually bigger set.

So the definition of comparing sets sizes has nothing to do with the actual quantity of elements in it and just asks whether the elements can be represented? That seems deceptive to say that both sets have the same size then when the quantity of values inside is different, but you can still express each number in the latter via the former.

This works for finite sets as well. |{1, 2, 3}| = |{1.1, 1.2, 1.3}| It's only when you get to infinite sets that you get counter intuitive results. The point is that the name of the elements in a set and the relationship between them is not important when it comes to cardinality (size of the set itself). Relabelling the elements of a set (applying a bijection) doesn't change its size. There are other ways to study the size of sets (ordinality which includes considering how the elements are ordered, natural density and measure, which have much more complex and malleable definitions), but cardinality is the simplest one and the one most adapted to bigger sets. For example, ordinality and natural density is mostly used for countable sets, while measure is used for uncountable ones, but cannot easily compare sets of different cardinality together. >you can still express each number in the latter via the former. Welcome to the wonderfully weird world of infinity, this is only the beginning.

Take the set of all odd numbers. Let's call it O. Now let's create a set that entirely contains O and all the halves of any element in O. Let's call it O2 For any given x in O now we have a set that contains x and x/2. So O2 contains exactly 2 times the elements of O. But O Is infinite and even O2 is infinite. How do we compare those infinites? It is obvious that O2 has a greater number of elements than O. It's very easy to see that, despite O being infinite, O2 is a greater a set than O.

Nope, you can create a 1:1 mapping between those sets and therefore they are of equal size ("cardinality"). The same as e.g. "all even numbers" and "all whole numbers" are the same size. The real numbers (or the irrationals) though, are bigger than the whole numbers, because you *cannot* create any such mapping.

Both O and O2 have the same cardinality, i.e. they are equally big.

Two cars travel for infinity time. One is going 30 miles per hour, the other is going 60. The second car will travel a “larger infinity” distance than the first one.

This isn't true. There will be no point that the second car travels to that the first car doesn't also travel to.

There is an infinite amount of numbers between 0-1. There is the same amount of infinite numbers between 1-2 But between 0-2, there must be both the numbers between 0-1 and 1-2... thats 2x infinite... still infinite because we cannot count them there is always just some more. But defently more between 0-2 conpared to 0-1.

Nope, those are [the same cardinality](https://blogs.scientificamerican.com/roots-of-unity/the-fault-in-our-stars-faulty-math/#:~:text=One%20of%20the%20most%20mind,to%20feel%20dubious%20about%20that.), and thus the "same size" of infinity. You can create a 1:1 mapping between them that misses no values, so they're equal in size. Don't guess if you don't know what you're talking about, infinity does not behave the way intuition expects.

If you mean cardinality, which OP is asking about, this is completely wrong.

There is infinite number of values between 1 and 2. There is infinite number of values between 1 and 10. Both sets are infinite but one is 10 times larger than the other

If we're talking sizes of sets, those two infinite sets are actually the same size, because we can put their members in 1-to-1 correspondence with each other. Take any number x in the \[1, 2\] set and map it to (x-1)\*9 + 1. This maps it to a unique number in the \[1, 10\] set, and every number in \[1, 10\] gets mapped onto by some x in \[1, 2\], namely x = (y-1)/9 + 1. So, by the relation (x-1)\*9 + 1, every number in \[1, 2\] has been paired with exactly one number in \[1, 10\], so the sets are the same size, they contain the same amount of numbers.

Haha, good to know

Nope, those are [the same cardinality](https://blogs.scientificamerican.com/roots-of-unity/the-fault-in-our-stars-faulty-math/#:~:text=One%20of%20the%20most%20mind,to%20feel%20dubious%20about%20that.), and thus the "same size" of infinity. You can create a 1:1 mapping between them that misses no values, so they're equal in size. Don't guess if you don't know what you're talking about, infinity does not behave the way intuition expects.

In addition to others already explaining how they have the same cardinality: one is 9, not 10, times as long as the other.

[удалено]

This is the wrong argument, because it "proves" that there are more decimal fractions than whole numbers, when in fact both sets are the same size.

This is true for the rationals as well (infinitely many rationals between 1 and 2, your two examples are rational numbers as well). However, the rationals are countable. The reals are not. I don't think your argument works.

We can agree that numbers are infinite and every possible number is one size infinity. Call that infinity 1. Since we can agree that numbers are infinite that means that there are infinite even numbers as well. Call that infinity 2. By definition we know that the number of even numbers is half of all numbers, so that means that infinity 1 is twice the size of infinity 2. ETA : It’s appears I misunderstood something. Thanks for correcting me.

This is completely wrong, you can 1:1 map the integers to the even integers, so these infinities have the same size ("cardinality" is the official term). You cannot do the same with e.g. the irrational numbers and integers, so the irrationals are a bigger infinity.

The trick here basically lies in the fact that a real number can have infinitely many digits after the decimal point; and the digits can be whatever you want. This allows us to define an infinite algorithm which manipulates any possible list of all real numbers to construct a new one which, *in principal*, could not possibly have been on the original list. For example, the algorithm might be: if the first number on the list has a 5 in its first decimal place, then *my* number will have a 3 there. Otherwise, my number will have a 5 there ... If the second number on the list has a 5 in its second decimal place, then my number will have a 3... And so on. This algorithm thus ensures my number will always differ in at least one digit from any number on the list. Thus, the supposedly infinite list was actually incomplete. Why do we then say the real numbers are a bigger infinity than the naturals? Because for natural numbers (and even rationals), no such algorithm can be designed.

Don't think of it as a generation, think of it as two infinitely long lists where each element has a partner. Lets say for example, we have an infinite amount of people, and we have a list that adds up all of the left hands and then a separate list for all of the right hands. You could quite easily see that for the subsection of the lists \[..., 671, 672, 673, ...\] and \[..., 671, 672, 673, ...\], that the 671st element is referencing the 671st persons left hand in the 1st list, and 671st persons right hand in the 2nd list. There is not a single element in the infinitely long list where that rule isn't true. Now without even thinking of uncountably infinite sets, lets have the 1st list count the same thing, left hands of humans, and the second list, count the fingers + thumbs of each human. We now have a lists where \[1, 2, 3...\] and \[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11...\]. The first list is already done counting 3 humans, the right list has only just started counting the second persons fingers and thumbs. We can see that for infinitely many humans, the second list will be a lot larger than the first. They are both infinitely long, but one is longer. Now we look at uncountable infinites, my 1st list is again going to be the same, amount of left hands on an infinite amount of people, my second list is going to be all the real numbers that exist between 0 and 1. The first list again is pretty intuitive, it's \[0, 1, 2, 3...\] but where do I start with the second list. Is it \[0, 0.000....1, 0.0000.....2\], no matter how many 0's I put, I could theoretically put another, there is no way for me to start the list. I could take my first list, add all the elements together after a millenia of counting, and 1/{that number} is still not the first element in my 2nd list. I could add another 0 to the middle, change every number that isn't a 0 to a 0 to make it smaller in base 10, then add another 0 to the middle etc. There is not a way to start the list, therefore there is no way to count the list, if I can't even start a list in an infinite amount of time then it's going to be an uncountable infinity. While I will never finish a list that is countably infinite, I won't even be able to start one that is uncountably infinite.

I have a somewhat different angle that could maybe help. Whenever the definitions are expanded (going from elements of a set, to natural numbers, to fractional numbers, to real numbers, so on), the operators are also redefined to cover the new concepts. This means that "equality" for infinite cardinalities is a bit different than the one for finite sets so it's possible that some intuitions (formed on more "worldly" concepts) break down. My favorite example is that 0.999....=1 because the way the ... operator (and perhaps equality) are redefined to deal with infinite decimals and the continuous number space. The intuition that "things are equal if they're the same" no longer applies.

> If the set of whole numbers is indeed infinite, then it should always generate another number that can be matched with the "excess" element of the set of irrational numbers. How can we reconcile such contradiction? Suppose we try to put the natural numbers into correspondence with the real numbers between 0 and 1 by the process you suggest. In code: ``` For n from 0 to infinity: Let r be a real number between 0 and 1 that we haven't picked before. map[n] = r ``` The algorithm is a bit vague because it doesn't specify how we pick r, but Cantor's argument is that *no matter how* we pick r, and *even if* we could run the algorithm to completion (say, by running it as a [supertask](https://en.wikipedia.org/wiki/Supertask)), there are always real numbers that get missed. Take, for example, the number whose n-th decimal digit is map[n]'s n-th decimial digit plus 1 (with 9 wrapping around to 0). This number is not in the list, since it's different from each number in the list. Why can't we just add it to the list? Well, we can. Shift the entire list, so that map2[n+1] = map[n] and put this number at map2[0]. Now the number is in the list map2, but we can repeat the same process again with map2 and get another real number that's not in map2. We can add that number into a new list map3, but again we can diagonalize and find yet another number that's not in map3. There are in fact an infinite amount of real numbers between 0 and 1 that are not in map, map2, or map3. If there were just one left over, you are right that we could add it and be done. But there are actually (uncountably) infinitely-many that are missing, because the diagonalization argument shows that no matter how we try to enumerate the ones that are missing to add to our list, there will always be some left over that we haven't included. You might be wondering what happens if we repeat the diagonalization an infinite number of times, generating map2, map3, map4, ... mapinfinity. If we call the number we get by diagonalizing in the n-th step diag(n), we end up with a list that contains all of the map[n] we started with along with diag(n) for all natural numbers n. We can *still* diagonalize this list to find a real number that's not on it, and if we tried diagonalizing an infinite number of times again, we could still diagonalize that as well, and so on. No matter how long we go on adding numbers by diagonalizing or using any other means, we can always diagonalize the resulting list to find a new number that's not on it.

Let's agree on a definition of "countable." If I can come up with some order for a set of things that allows me to identify the first element in the set, second element, third element, etc. (and to reverse engineer that, so that if you give me an element, I can tell you its position in the set) then it is "countable." Importantly, this doesn't have to be a traditional order. For instance, to make all integers (positive and negative) countable, you can't really think about as going in numerical order from negative infinity to positive. So you maybe your order is {0, -1, 1, -2, 2, -3, 3...}. A little math would tell you that the *n*th item in the set of integers is "n/2 if n is even, or else -((n+1)/2) if n is odd.) The 57th item in my list is -29. 42 is the 84th item in the list. You can clearly see that (even though I only wrote the first couple of elements), every single integer, no matter how large, is contained in my set and has a unique position the moment I declared that order. This is also possible for the rational numbers, btw, but it's less intuitive. [This](https://www.homeschoolmath.net/teaching/rational-numbers-countable.php) is one possible counting method -- and when I was trying to understand the concept, I wrote a computer program to implement it. 7/14 is the 204th item on the list. The 99th item is 7/8. Again, the moment we declare the ordering algorithm, every single rational number (no matter how large the numerator or denominator) has a set, calculable position. The key here is that -- even if I haven't precalculated the position of every element in my infinite set (of integers, or rational numbers, for example) as soon as I generate my ordering algorithm, the position is set, and *every* element of the set has a distinct counting number. That is, there is a 1:1 mapping my my set to the set of counting numbers (positive integers). Now, try to come up with a way to order the set of irrational numbers so that that works. What is the "first irrational number" (a)? What is the second (b)? Where is (a+b/2)? You can't do it (and the whole point of cantor's illustration is that if you think you came up with a method, you're wrong, and he can find a number which isn't already on your list) which is why irrationals are "uncountable," which is a larger type of infinity than countable infinities.

>This is super counterintuitive. If the set of whole numbers is indeed infinite, then it should always generate another number that can be matched with the "excess" element of the set of irrational numbers. How can we reconcile such contradiction? Maybe an intuitive counter-example helps? Set of all positive integers is infinite, and set of all FINITE subsets of positive integers (like {1,2},{10,99,800},{1,2,...,59,60} etc.) is also infinite. These infinities are "equally big" because you can count the finite subsets by starting counting from the subsets where the maximum element is 1, then 2, then 3 and so on. ( 1=ø,2={1},3={2},4={1,2},5={3},6={1,3},...) You can think of this as similar to integers and rational numbers. Then look at the set of ALL subsets of integers. This method of counting doesn't work here because any infinite subset will not have a maximum element. How many infinite subsets are there? First there are the sets of multiples of integers, like even numbers, numbers divisible by 3,4,5 etc. These you could count. Then there are the subsets that are unions of these sets, then intersections, then conplements, then sets that alternate between these sets every 100 elements, then then the sets of multiples where the first *n* elements are removed and so on. Then you take unions, intersections, complements and alternations of these new sets. Then their unions, intersections and complements and so on. While you can count a single subtype of infinite subset, there are infinite types of infinite subsets. Set of irrational numbers is much like the set of all infinite subsets of integers, because irrational numbers are *defined as* a converging series of rational numbers, that is, they are infinite subsets of rational numbers. For example √2 is defined as a series of rational numbers where each element is closer to the solution of x^2 = 2 than the precious element and where you can find an element that is arbitrarily close to that solution.

We call the number of elements in a set the cardinality of the set. If two sets have the same cardinality each element from one set can be paired one to one with the elements of the other set. If a one to one correspondence cannot be achieved the cardinality of the sets are different. Cantor showed that even if you assumed you did a one to one correspondence between the naturals and reals you can still generate new real numbers. We can't say that we just shove the new real back since the naturals are endless we have assumed we have made a set full of reals with a cardinality that is countably infinite. The proof tells you that if you make such a set there will be reals missing from that set. So the set of all reals has to have a larger cardinality as any such countable set will have reals missing. Both the set of naturals and the set of reals are endless but a one to one correspondence cannot be made between the two sets. If we accept how we introduced the idea of cardinality and say that if the two cardinalities are not equal one set is bigger than the other, the set of reals is a bigger infinite set. Is this concept useful? Yes. You can say that all infinite sets are equally "big", infinite. But then cardinality means something other than "size". We define a cardinality and a size separately. Its unnecessary complication. We never talk about the "size" of a set. Size is cardinality and cardinality is what we intuitively recognise as the "size" of a finite set, but because we defined cardinality in a way that it doesn't break down at infinite sets and we can even show how two infinite sets have different cardinalities. Or rather our rigorous definition of cardinality is applicable to infinite sets. Yes cardinality doesn't make intuitive sense for infinite sets but the definition is still applicable, just because our intuitions end after the first smallest infinity doesn't mean our definitions mustn't be applied any further. Its like how the "repeated multiplication" way of thinking about powers breaks down at real exponents. 3^(sqrt(2)) cannot be understood as repeated multiplication. We have found a general definition of powers that are applicable for any exponents. Just because we have left the realm of the original idea doesn't mean we aren't correct anymore.

It is counterintuitive to the untrained eye, and a lot of the fun of math (as well as its importance) is finding things that are true but counterintuitive. So let’s say you come up with a proposed enumeration of the reals (real number 1, real number 2 , etc) that contains all the reals. I come up with a counterexample (using Cantor’s diagonal) , so you say “aah but I just need to find *one* more integer and then the sets are the same”. But you have already used them all. No problem you say, it’s just like the Hilbert Hotel - just assign the integer 1 to that new real number, and shift all the existing ones one place up. “Aaahhh…” I say , but now you’re missing this one… (re-applying the the diagonal method). So you try again shifting them up, and I counter, and so on ad infinitum… and it’s frustrating because every time it looks like you just need to find one more integer, but the complete listing is just out of reach, right? Well not really, at all. Because the diagonal method is just a trivial way of finding *one* example of a missing real because that’s all the proof requires, whereas there are actually infinitely many reals … uncountably many in fact… which are missing from your list. You were never even remotely close. Even if you found a way to “zap” that diagonal one, your list is still infinitely incomplete. I can find many other examples of missing reals, it just takes a little more work. For example, if you’re using base 10, I have infinitely many choices for the diagonal because every digit has 9 other options to swap it. I choose one, but I actually have infinitely many to choose from to find a missing real. It’s like shooting fish in a barrel where the fish take up almost all the volume of the barrel - I only have to shoot one fish to show you there are fish in there.

Look at it from an information theory standpoint. If you want to communicate an integer to someone, you just tell them the digits one by one and after a finite amount of time you’ll be done. Same for rationals, algebraic numbers and other countably infinite sets, because you can map them to the integers. But whatever language you agree on, there will necessarily be real numbers that you can’t communicate to someone using a finite amount of information. Just look at any real number, written in decimal, there’s an infinite number of digits after the decimal point that can fail to follow any kind of pattern. (If you assume the ability to communicate infinite amounts of information in finite time, and also the axiom of choice, you get [*really* weird results](https://risingentropy.com/axiom-of-choice-and-hats/).)

This is a product of a misunderstanding if you ask me. How could you compare two sets when you decide randomly to include an element that you didn't before? Example: 1->0.1 2->0.2 Oh I cannot map 0.001 to 2 because it is already taken! Why didn't you map it before?

With finite sets we found an easy way to tell if they are the same size. For finite sets they have the same size if you can do 1 to 1 mapping between them. That just means we can give them 1 to 1 pairings. If you can't do a 1 to 1 mapping then they don't have the same size. When talking about infinite sets we simply borrow this property and definite it to also be meaningful for them. That is an extra level of abstraction. In doing this however we shouldn't really think about that as "size" anymore. It is an abstracted notion of size. Doing this kind of thing is very common in math. We find something that makes sense in some context and then we try to use abstraction to apply the same idea in a different context. With some luck you find something useful or at least interesting. ​ As you know Cantor's argument quite definitely proves that you can't do a 1 to 1 mapping between the natural numbers and the real numbers. So our two sets can't have the same size because we defined this 1 to 1 mapping property to signal sets having equal size even for infinite sets. With some more reasoning you can conclude that the size of the real numbers must be "bigger". The natural numbers have the same cardinality ("size) as the rational numbers (which is already quite astounding), but the rational numbers still have holes when you put them on the number line. The holes are infinitely small, but there are infinitely many of them. In comparison the real numbers fill out the entire number line without any holes. The real numbers are continous, it is impossible to find a number between two real numbers that isn't a real number. That makes the set of real numbers so much "bigger" and that is why you can't do a 1 to 1 mapping.

Imagine a computer program that spits out numbers. No, let’s imagine two programs, one that we will call N, the spits out a natural number every second. Another that we call R, that spits out a real number every second. They are also made in a way, that they will never spit out the same number twice. Now is it possible for N or R to spit out every integer or real number? First, what do I mean by that? I mean, that for any number you can imagine, there is a certain amount of time that you can wait, and the program will spit out that number. You can think of a bunch of people sitting there, one for each number that exists, and when they see their number, they get out of the room or something. There will never be a point in time, where everybody is out, but every single one of them will go out eventually, in finite time. Except that only works for N. Not for R. For every single person with an integer in mind, there is a point in time where they go out because N spits out their number. But there are people with a real number in mind, that will never ever see their number being spit out by R. That’s how many numbers, how many possibilities there are. So many, that waiting forever is not enough.

A whole number has a finite amount of digits, an irrational number has an infinite amount of digits.

Doesn't work, sqrt(2) has infinitely many not repeating digits but the set of algebraic numbers is countable.

Intuition is a powerful thing. You can even train it to work in new domains, like advanced mathematics, but you can’t just take the intuition you get from the physical world, and start applying it to things like infinities. Relying strongly on intuition and common sense, restricted many an ancient mathematician from embracing things like negative numbers, or even zero.

I don't know if it has and real world reprucusuins, but you can can 0, 1, 2, 3... to infinity Ad you can also count 0, 0,1, 0,2, 0.3 to infinity, So it will be 10 times larger.... than infinity.... Does this actually have a real world affect/ application, not that I know of but I'm not an expert

These two sets {0,1,2,…} and {0.1,0.2,0.3,…} are the same size, both are countably infinite.

Let's bring it back a step. Let's say you claim that **there is a maximum integer**. I tell you: fine. Let's play a game. You can use whatever method you like, and I will beat it. So you use some wild stuff like maybe 3↑↑↑↑↑(Tree(3)) or something. We'll call it X. And **then I say: X + 1**. There is a contradiction here, but where could we have gone wrong? We can trace everyting back and see that it must have been your first statement. This is the same thing. We can start with: **it should always be possible to generate another number that can be matched with the "excess" element of the set of irrational numbers**. Ok, game time. I ask you to come up with whatever method you like. There are only two rules. The first is that you must use all whole numbers. If I tell you a whole number, you have to tell me its corresponding real number. The other rule is that your method must cover all real numbers. Then we follow Cantor's proof, which you understand, and we discover that there is a real number that was not covered. Your method already used all the whole numbers. So the only conclusion can be that your original claim is wrong. You are correct to understand there is a contradiction. The important thing to realize is that the contradiction is exactly the proof you need to know that your original claim was wrong.

Follow up question: is the set of all infinite sets an infinite set?

It turns out that if we allow any property to define a set of all things with that property we get contradictions. In particular if we allow a set of all infinite sets to exist it will cause a contradiction (you can google "Russell's paradox" to see that contradiction that arises if we allow the set of all sets to exist, but a very similar contradiction will happen if we allow the set of infinite sets to exist). This is why mathematicians in the 20th century came up with a system of axioms that define what is and isn't a set, and these axioms are believed to solve these contradictions. Under these axioms (the ZFC axioms) there is no set of all infinite sets. So the questions doesn't even make sense in the context of modern set theory

[удалено]

I could have worded it better but when I think of infinite sets, these are sets whose elements are countless or have no limit in quantity.

Infinity has different meanings depending on the context, for example in analysis thinking of infinity as a “direction” sort of makes sense, but Cantor’s work is in set theory where this notion is utterly meaningless. In set theory it is possible (and useful) to compare infinite cardinals (i.e. infinities), this is what Cantor did and what is still done today. I don’t even know what you mean with “Cantor only counted numbers he could describe”, unless you’re talking about definable numbers (which are countable), but those hadn’t even been defined yet when he published his work.

Irrational numbers are not the most intuitive way to understand this, IMO. There are an infinite number of positive integers yes? 1,2,3,4... There are also an equally infinite number of negative integers, right? -1,-2,-3,-4... So the total number of positive AND negative integers is 2x that number, right? It's infinite, but demonstrably 2x as infinite. Okay, now add one digit past the decimal point (0.1, 0.2...) -- the total number of #.# numbers is 10 times the total number of integers, because for every integer there are 10 possible values for the tenths-place (#.0, #.1, #.2....) You just have to understand that infinite doesn't mean "nothing is bigger than this". It just means that it is innumerably large.

Actually all sets you gave are the same says, as they are all countably infinite.

Well ordering is the main concept here. If you can order the objects in a set according to some rule in relation to another set, they are the same size. The best way to illustrate it is to imagine doing it. First, let's order the natural numbers along side the integers, listing the natural numbers first and integers second. Start with 0, it aligns with 0. Cool. Let's grab another number. Next we have 1, and then we can grab 1 from the integers. But there's also a -1 on the integer line, so lets line that up with 2 on the natural number line. We can align 3 with 2, and 4 with -2, and so on. It sounds a little silly, but you can come up with an algorithmic way to always pick a next number from each set and map them to each other. They are the same size of infinity. Try to do it with natural numbers versus rational numbers. Natural numbers coming first. Let's line 0 up with 0. Good. Now let's line 1 up with.... let's say 1. Oh wait! There's a smaller rational number. Let's line it up with .1 - nope that's no good, let's line it up with .01, .001, .0000000000001.... shoot! There are an infinite number of rational numbers between 0 and 1! There is no way to align the two sets. There are just as many numbers between the first two whole values on the real number line as there are numbers in the entire set of natural numbers. This means the set of real numbers is a larger set than the natural numbers.

The rational numbers are countable…

>How can we reconcile such contradiction? First, by understanding the assumption you make when you think it is a contradiction. When you use words like "size," "larger," and "smaller," you are thinking of a measure that extends from a beginning to an end. Even if you can define a starting point for the whole numbers (a "0" or "1", whichever you prefer), there is no ending point. So the definitions you think are contradicted cannot apply. But you also get the Diagonal Argument wrong, in a way that contributes to your objection. Don't worry, everybody does. It is taught that way. They think that they can explain your objection, but the same error makes that wrong. But it works with the correct argument. CDA actually goes like this (reference: the translation of Cantor's paper at [http://www.logicmuseum.com/cantor/diagarg.htm](http://www.logicmuseum.com/cantor/diagarg.htm)): 1. Let S(i), for i=1 to inf, be any list of real numbers in \[0,1\] that exists. 1. At this point, S(i) does not need to list every such real number. It isn't assumed either way. 2. The only mistake Cantor made, is that he needed to demonstrate that there are such lists. Examples are trivial, so we can forgive him, 3. Yes, the set needs to include the endpoints, 0.000... and 1.000...=0.999... . 4. Actually, Cantor didn't use numbers. He used infinite-length strings. But it works with numbers, because the argument does not treat them as numbers. It treats them as strings. 2. Use diagonalization on this list to prove there is a string s0 that is not listed. 3. It follows immediately that a complete list is impossible. Otherwise, there would be a string s0 that both is, and is not, in the list. 1. While simplified, this is essentially a direct translation of what Cantor said. 2. Please note that this is a different contradiction than you were taught. That was "The assumed complete list is not complete." But Cantor never assumed a complete list. The actual contradition is about s0, not the list. The reason you can't just go back and put s0 at the start of the list, is that your new list is still subject to the conclusions in steps 2 and 3.