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}$
Best Answer
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$.