Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
How can I solve this question in only 2.5 minutes? It must be solved using deep insight and intuition, which I do not have. Could anyone help me, please?
Thanks!
Which of the following sets has the greatest cardinality?
(A) $\mathbb{R}$
(B) The set of all functions from $\mathbb{Z}$ to $\mathbb{Z}$
(C) The set of all functions from $\mathbb{R}$ to $\{0, 1\}$
(D) The set of all finite subsets of $\mathbb{R}$
(E) The set of all polynomials with coefficients in $\mathbb{R}$
This is one of those questions where you would have to have some previous knowledge about cardinalities of infinite sizes. I don't think that someone can eyeball this question without having worked with infinite cardinals before.
$(a)$ has size $2^{\aleph_0}$; $(b)$ has size $|\mathbb{Z}|^{|{\mathbb{Z}}|} = \aleph_0^{\aleph_0} = 2^{\aleph_0}$; (c) has size $2^{|\mathbb{R}|} = 2^{(2^{\aleph_0})}$; (d) and (e) are the size of $\mathbb{R}$ which again is $2^{\aleph_0}$. Therefore, the answer is (c).
Since there is some debate, we will show that (e) is bounded by the size of the reals. Let $P(\mathbb{R})$ be the collection of all polynomials over $\mathbb{R}$. Let $P_n(\mathbb{R})$ be the collection of all polynomials of degree $n$. Then $P(\mathbb{R})=\bigcup_{n\in\mathbb{N}}P_n(\mathbb{R})$. Now, $|P_n(\mathbb{R})| = |\prod_{i =1}^n \mathbb{R}|$. Therefore $$|P(\mathbb{R})| = |\bigcup_{n\in\mathbb{N}}P_n(\mathbb{R})| \leq \sum_{n \in \mathbb{N}} |P_n(\mathbb{R})| = \sum_{n \in \mathbb{N}}|\prod_{i=1}^n \mathbb{R}|= \sum_{n\in \mathbb{N}} |\mathbb{R}| = |\mathbb{R}|$$
A very similar argument shows that (d) is bounded by the size of the $\mathbb{R}$. In particular, you replace $P_n(\mathbb{R})$ with sets of size $n$.
You don't really need to compute all the sizes of these objects, but you do need to know a bit about how various infinities play together.
Facts:
The power set of a set is bigger than the set itself.
A countable sum of copies of $\mathbb{R}$ has the same cardinality as $\mathbb{R}$.
This means that right away, we can see that $A$, $D$, and $E$ are the same size.
$D$: There are fewer subsets of $\mathbb{R}$ of size $n$ than there are points in $\mathbb{R}^n$ (an ordered $n$-tuple may define a subset of $\mathbb{R}$ of size $n$). Each of $\mathbb{R}^n$ is the same size and adding them all up gives a countable sum.
$E$: It's easiest to think of this in terms of a single variable, but it works for up to countably many variables. The set of polynomials can be written out as: $$ \mathbb{R}+x\mathbb{R}+x^2\mathbb{R}+x^3\mathbb{R}+\cdots $$ this is a countable sum of copies of $\mathbb{R}$, so it's the same size as $\mathbb{R}$.
$C$: Now, we can see that $C$ is strictly larger than $A$, $D$, and $E$. If you take a function $f:\mathbb{R}\rightarrow\{0,1\}$, this corresponds to a subset of $\mathbb{R}$ by taking the elements of $\mathbb{R}$ which map to $1$. Since this can be done for any subset of $\mathbb{R}$, these functions are in bijection correspondence with the power set of $\mathbb{R}$. Therefore, $C$ is larger than $A$, $D$, and $E$.
$B$: The set of functions from $\mathbb{Z}$ to itself can be worked through in the following way. Instead of looking at functions from $\mathbb{Z}$ to $\mathbb{Z}$, we can look at functions from $\mathbb{N}$ to $\mathbb{N}$ since these have the same size. This means that these functions are the same as sequences to the natural numbers. This is the same size as $\mathbb{R}$ because one could map them into $\mathbb{R}$ via continued fractions (or other means). There's likely a slicker way to look at this last one since continued fractions aren't so common on the GREs. See the comments for nice alternative ways to look at the cardinality of this set.
These are also some important links for solving my question(at least from my point of view):
(B)What is the cardinality of the set of all functions from $\mathbb{Z} \to \mathbb{Z}$?
(C)What is the cardinality of the set of all functions from $\mathbb{R}$ to {0,1}?
(D)Cardinality of the Set of all finite subset of $\mathbb{R}$
(E)Cardinality of the set of all polynomials with coefficients in $\mathbb R$
(C) is actually $\beth_2$, whereas the other choices are all $\beth_1$. As $\beth_n=2^{\beth{n-1}}\gt \beth_{n-1} $ we are done. That the power set has greater order than the original set follows from Cantor's diagonal argument. ..
