# Which of the following sets has the greatest cardinality?(Math subject GRE exam 0568 Q.61 )

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!

1. 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}$

• look up stack of infinities ?
– user451844
Aug 20, 2017 at 1:38
• for intuition, look to yourself, surely this is obvious. Aug 20, 2017 at 5:15

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$.

• Pardon my ignorance: why is (d) the cardinality of $\mathbb{R}$ again? (It's been awhile since I had to think about this stuff deeply.) Aug 20, 2017 at 1:45
• @Platty The set of all functions from $\mathbb{R}$ to $\{0,1\}$ has the same cardinality as the power set of $\mathbb{R}$, which is bigger than $\mathbb{R}$. Aug 20, 2017 at 1:45
• @Randall: See my edit ~ let me know if you would like to see more. Aug 20, 2017 at 1:55
• @KyleGannon: Dang, that last argument makes a ton of sense. Aug 20, 2017 at 1:58
• @Intuition: You are correct. Fixed. Aug 20, 2017 at 18:10

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:

1. The power set of a set is bigger than the set itself.

2. 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.

• For B, I've seen this reasoning several times before: $\mathbb{N} \rightarrow \mathbb{N}$ (an infinite sequence of naturals) and $\mathbb{N} \rightarrow \{0,1\}$ (an infinite sequence of bits) are equinumerous since each natural can be written as a finite sequence of bits, and the product of countable finite sets is countable; and $\mathbb{N} \rightarrow \{0,1\}$ is a 'standard' definition for $\mathbb{R}$ (i.e. this latter fact is probably part of the knowledge expected of a student taking this test). Aug 20, 2017 at 3:39
• Another way I've seen: consider the 'truth table' of a mapping $f: \Bbb{N}\mapsto\Bbb{N}$; that is, the function $g: \Bbb{N}\times\Bbb{N}\mapsto\{0,1\}$ defined by $g(x,y)=1$ if $f(x)=y$ and $g(x,y)=0$ otherwise. It's clear that any $f$ maps to a unique $g$, and so the set of functions from $\Bbb{N}\mapsto\Bbb{N}$ is a subset of the set of functions from $\Bbb{N}\times\Bbb{N}\mapsto\{0,1\}$. But now you can use your favorite bijection from $\Bbb{N}\times\Bbb{N}$ to $\Bbb{N}$ to equate this with the set of functions $\Bbb{N}\mapsto\{0,1\}$ which is classically of size $\Bbb{R}$. Aug 20, 2017 at 17:10

These are also some important links for solving my question(at least from my point of view):

(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. ..

• This is untrue. This is assuming GCH. Aug 20, 2017 at 4:08
• I see what you mean : I guess it hasn't been proved there are no intermediate levels $\kappa$ with $\aleph_n \lt \kappa \lt \aleph_{n+1}$.
– user403337
Aug 20, 2017 at 5:02
• The issue isn't whether there exists some $\kappa$ as you have mentioned above, but that it is consistent with ZFC that $|\mathbb{R}| \neq \aleph_1$ and likewise, it is consistent that $|2^{\mathbb{R}}| \neq \aleph_2$. Aug 20, 2017 at 6:11
• Ok, well as long as you agree that the power set has greater cardinality, I think the reasoning behind this problem is essentially the same. .. it was an oversight on my part. .. only independence was proved...
– user403337
Aug 20, 2017 at 6:24
• If you had written instead: (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 then it would have been much more correct. See beth numbers. Aug 20, 2017 at 22:44