13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ look up stack of infinities ? $\endgroup$ – user451844 Aug 20 '17 at 1:38
  • 1
    $\begingroup$ for intuition, look to yourself, surely this is obvious. $\endgroup$ – James S. Cook Aug 20 '17 at 5:15
21
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Randall Aug 20 '17 at 1:45
  • 4
    $\begingroup$ @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}$. $\endgroup$ – Michael Burr Aug 20 '17 at 1:45
  • 1
    $\begingroup$ @Randall: See my edit ~ let me know if you would like to see more. $\endgroup$ – Kyle Aug 20 '17 at 1:55
  • 1
    $\begingroup$ @KyleGannon: Dang, that last argument makes a ton of sense. $\endgroup$ – Randall Aug 20 '17 at 1:58
  • 1
    $\begingroup$ @Intuition: You are correct. Fixed. $\endgroup$ – Kyle Aug 20 '17 at 18:10
15
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – user2407038 Aug 20 '17 at 3:39
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Steven Stadnicki Aug 20 '17 at 17:10
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This is untrue. This is assuming GCH. $\endgroup$ – Kyle Aug 20 '17 at 4:08
  • $\begingroup$ 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} $. $\endgroup$ – Chris Custer Aug 20 '17 at 5:02
  • 2
    $\begingroup$ 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$. $\endgroup$ – Kyle Aug 20 '17 at 6:11
  • $\begingroup$ 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... $\endgroup$ – Chris Custer Aug 20 '17 at 6:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeppe Stig Nielsen Aug 20 '17 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.