I’m by no means a mathematician so this is a layman’s confusion after watching Youtube videos.
I understand why the (new) real number couldn’t be at any position (i.e. if it were, its [integer index] digit would be different, so it contradicts the assumption). But how does this **prove** that the set of real numbers is larger? This number indeed couldn’t be at any position, but it can **still** be mapped to an integer, because there are infinite integers – neither set can be larger because neither is finite.
Or are just “larger” or there being “more real numbers than integers” wrong terms to describe cardinality?
Pardon my ignorance.
Thank you.
In: Mathematics
> This number indeed couldn’t be at any position, but it can still be mapped to an integer
That’s a contradictory statement. If the number can be mapped to an integer, that integer indicates its position, but you’ve said the number can’t be at any position. Mapping to an integer and having a position in the list are equivalent things. Either you have both or you have neither.
The description of one being larger than the other is misleading. The simplest explanation is that there are different types of infinities that behave in different ways mathematically.
One of these types of infinities is the “listable” or “countable” infinities. The total number of natural numbers (the set of {1,2,3,…} ) is “countably” infinite.
Cantor’s diagonal argument is used to show that the size of the set of all real numbers is not countably infinite, as you can never make an infinite list of all the real numbers.
I think the claim that one is “bigger” however is misleading. At first glance it might appear that there are more integers than even numbers, because even numbers is a subset of integers. But both of these sets are countably infinite and we can make a unique one-to-one correlation between the two sets.
Instead, in math I think it’s clearer to understand that there are different types of infinities which have different properties, and unless you go into high level mathematics, you will mostly encounter the countable infinities.
there are infinities that are larger than other infinities.
To find out if two infinite sets are the same “infinity”, you need to come up with a 1-to-1 correspondence. if you can’t (and that is Cantors prove) the other infinity is larger.
Not a mathematician myself, but the concept is not that difficult.
You’re on the right track! We can compare the cardinality (size) of two sets by seeing if we can make a one-to-one mapping between the elements of the sets. Like how a farmer might count a herd of sheep– in the morning, get a pile of rocks, and each time a sheep passes, move a rock to a second pile. In the evening you don’t have to count th sheep, but move the rocks back to the original pile. If there is a rock for each sheep, the two sets are the size.
By showing that in ANY possible mapping, there is at least one real number that can’t be mapped to the naturals, you’ve shown that they aren’t the same cardinality.
Btw, this is why sets that can be mapped to the naturals are called “countable” sets– because it’s possible to assign a unique number to each element.
Does this help?
> This number indeed couldn’t be at any position, but it can still be mapped to an integer, because there are infinite integers – neither set can be larger because neither is finite.
The original list of real numbers is, by definition, mapped to every existing integer. There are none remaining to place the new real number. But by the assumptions of the diagonal argument, the list contains **every** real number. Since the assumption (every real number is in the list) and the conclusion (this real number is not) are in contradiction, one of the assumptions made in the construction must be false – specifically, the assumption that you could create a countable list of all real numbers.
What you’re confused about is the concept of a proof by contradiction.
So let’s break down the logic a bit. We want to show that the set of real numbers is strictly larger than the set of integers. By the definition of “larger” for sets, this means we want to prove that there’s no perfect one-to-one pairing between integers and real numbers.
We use proof by contradiction: we assume the opposite of what we want to prove, and then show that this leads to a contradiction. We assume that we have a perfect one-to-one pairing between integers and real numbers, and then show that, in fact, we don’t have such a pairing, because at least one real number is left out even though every integer is taken. In other words, we’ve shown that if such a one-to-one correspondence exists, then it actually doesn’t exist. That contradiction is enough to show that our initial assumption is false.
> This number indeed couldn’t be at any position, but it can still be mapped to an integer, because there are infinite integers – neither set can be larger because neither is finite.
That’s not true. By assumption, every integer is already mapped to a real number. You give me any integer, and I’ll give you the real number that it’s already mapped to, that’s not the new one we’ve found. You can’t just take the “next” integer—they’re ALL taken, including that “next” one, and the one after that, and all 50 billion after that, and so on. Just because there are infinitely many integers doesn’t mean any are still available—in fact, we assume at the outset that they’re all taken!
Your confusion might come from the fact that the argument is presented as writing out a list of these pairs, and clearly we can’t actually write out infinitely many pairs. But that’s just a simplification that’s made to make the argument easier to understand to laypeople—we don’t actually have to write out every single pairing. We just have to know that every pairing exists, and that every single integer is already paired up with a real number, so there are no integers left.
If you’re willing to wade through more abstraction, you might find the formal version of the argument presented on this wikipedia page clearer (this is a generalized statement, but the fact that the cardinality of the reals is larger than the cardinality of the integers is a consequence, since it’s pretty intuitive that we can establish bijection between the reals and the powerset of the integers using decimal expansions): https://en.wikipedia.org/wiki/Cantor%27s_theorem
Latest Answers