I heard about it while watching a TV show, and even after reading through the wikipedia I cannot understand it. [Here](https://en.m.wikipedia.org/wiki/Cantor%27s_paradox) is the wiki for reference. I’d like to understand what the “paradox” behind this is because these sort of things bother me and I feel like I won’t be able to continue without understanding. Thanks in advance!
In: 2
Imagine a set S of all existing sets. Now what if we wanted to get, say, the power set that we would call PS. How can that set be new? It must be inside S already, so the paradox lies in the fact that no matter what you do, if you are trying to make a set that includes everything, it cannot be as infinite as the sizes of the infinite sets inside, it must be a larger infinite, the term paradox is coined here because we often think of infinite as, well, infinite, but there are different infinites. Say you were about to count all the way from 0 to infinite, it is larger than infinite for the simple reason that even the set between 0 and 1
is infinite, so counting from 0 to 1 is actually infinite, this is why the actual real set called R is an uncountable infinite and follows this kind of paradox
Imagine a set S of all existing sets. Now what if we wanted to get, say, the power set that we would call PS. How can that set be new? It must be inside S already, so the paradox lies in the fact that no matter what you do, if you are trying to make a set that includes everything, it cannot be as infinite as the sizes of the infinite sets inside, it must be a larger infinite, the term paradox is coined here because we often think of infinite as, well, infinite, but there are different infinites. Say you were about to count all the way from 0 to infinite, it is larger than infinite for the simple reason that even the set between 0 and 1
is infinite, so counting from 0 to 1 is actually infinite, this is why the actual real set called R is an uncountable infinite and follows this kind of paradox
How many numbers are there?
We could put them all in a box^1, and count how many things are in the box^2 . That’s how many numbers there are. Let’s call it C.
But what if we took a random selection of numbers from the box. How many possibilities are there^3 ? Well, for every number in the box, we either select it or we don’t. This means that we can calculate the number of possibilities by 2^C , as it’s C binary choices.
But hold on: 2^C > C
This means that either:
We have all the numbers at least up to 2^C , and there are more than C numbers
We have only some of the numbers up to 2^C , so our set of all the numbers is missing some.
Either of these options is a contradiction
_____
1. The box is a set.
2. This is the cardinality of the set.
3. The set of these possibilities is the powerset of the original set.
How many numbers are there?
We could put them all in a box^1, and count how many things are in the box^2 . That’s how many numbers there are. Let’s call it C.
But what if we took a random selection of numbers from the box. How many possibilities are there^3 ? Well, for every number in the box, we either select it or we don’t. This means that we can calculate the number of possibilities by 2^C , as it’s C binary choices.
But hold on: 2^C > C
This means that either:
We have all the numbers at least up to 2^C , and there are more than C numbers
We have only some of the numbers up to 2^C , so our set of all the numbers is missing some.
Either of these options is a contradiction
_____
1. The box is a set.
2. This is the cardinality of the set.
3. The set of these possibilities is the powerset of the original set.
ELI5 will be difficult, as this touches to formal set theory.
In set theory, everything is represented as a set, including numbers.
In this case, a natural number (non-negative integer) is just a set with a specific structure: ∅ (the empty set) is 0, {0} is 1, {0,1} is 2, etc. So each natural number is basically the (finite) set of all natural numbers before it.
A cardinality is an extension of these natural numbers, it answers the question”how many elements are there in this set?”. So N, the set of all natural numbers, is the cardinality of the natural numbers. It’s how many natural numbers there are, quite literally. This is obviously infinite and things get weird quickly, but there are actually more than one infinite cardinality. For example, there are more real numbers than natural numbers.
So each cardinality is basically the (possibly infinite) set of all cardinalities before it.
Now, let’s say we are able to construct the set of all cardinalities.
What is its cardinality? Well, whatever it is, obviously, it is part of the set. And that cardinality would contain all the cardinalities smaller than it.
Since the set contains all cardinalities, its cardinality will need to contain at least all of these as well.
This is probably the most hand-wavy bit: if the cardinality didn’t contain all the cardinalities, then there would be at least one missing, which means either it would be smaller than the set or it would not contain all the cardinalities smaller than itself (and not be a cardinality).
So the cardinality of the set of all cardinalities contains all the cardinalities. Which means it has to contains itself.
This is forbidden by the axioms of set theory (axiom of regularity or foundation). So the set of all cardinalities cannot exist.
ELI5 will be difficult, as this touches to formal set theory.
In set theory, everything is represented as a set, including numbers.
In this case, a natural number (non-negative integer) is just a set with a specific structure: ∅ (the empty set) is 0, {0} is 1, {0,1} is 2, etc. So each natural number is basically the (finite) set of all natural numbers before it.
A cardinality is an extension of these natural numbers, it answers the question”how many elements are there in this set?”. So N, the set of all natural numbers, is the cardinality of the natural numbers. It’s how many natural numbers there are, quite literally. This is obviously infinite and things get weird quickly, but there are actually more than one infinite cardinality. For example, there are more real numbers than natural numbers.
So each cardinality is basically the (possibly infinite) set of all cardinalities before it.
Now, let’s say we are able to construct the set of all cardinalities.
What is its cardinality? Well, whatever it is, obviously, it is part of the set. And that cardinality would contain all the cardinalities smaller than it.
Since the set contains all cardinalities, its cardinality will need to contain at least all of these as well.
This is probably the most hand-wavy bit: if the cardinality didn’t contain all the cardinalities, then there would be at least one missing, which means either it would be smaller than the set or it would not contain all the cardinalities smaller than itself (and not be a cardinality).
So the cardinality of the set of all cardinalities contains all the cardinalities. Which means it has to contains itself.
This is forbidden by the axioms of set theory (axiom of regularity or foundation). So the set of all cardinalities cannot exist.
Latest Answers