6
$\begingroup$

I missed a lecture for my set theory class, so I'm stuck on the following homework problems:

Prove that each of the following sets has the power of the continuum:

a. The set of all infinite sequences of positive integers; b. The set of all ordered n-tuples of real numbers; c. the set of all infinite sequences of real numbers;

From google I was able to find out the definition of the power of continuum but as far as any equivalence proofs I'm stumped. Any insight would be appreciated!

  • 1
    Often the easiest way to prove two sets have the same cardinality is to find an injection (1 to 1 map) from one set to the other, and vice versa. Also, if you are willing to believe that no set has cardinality larger than $R$ then only one direction of this is needed for your questions(you would just find an injection from $R$ to the set you have listed in each of your three questions).2011-05-05
  • 0
    The question is what are you allowed to use. Have you already covered cardinal numbers and some rules of cardinal arithmetic in class? Do you already know that $|\mathcal P(\mathbb N)|=|\mathbb R|$? Have you already learn Cantor-Bernstein theorem (which is implicitly mentioned in Joe's comment), that $|A|\le|B|$ and $|B|\le|A|$ implies $|A|=|B|$?2011-05-05
  • 0
    If we assume as known that the cardinality of the continuum is equal to the cardinality of the set of infinite sequences of $0$s and $1$s, all the rest can be done by fairly simply discovered explicit bijections.2011-05-05
  • 0
    Get the notes from a classmate.2011-05-05

2 Answers 2

4

There are three "usual" methods to approach such problem:

  1. Find explicit bijections, or use the Cantor-Schroeder-Bernstein theorem by finding two injections.
  2. Use cardinality inequalities, which employs the Cantor-Schroeder-Bernstein theorem in the background, e.g. $|\mathbb R|\le |\{0,1\}^\mathbb N|\le |\mathbb Z^\mathbb N| = |\mathbb N^\mathbb N| = |\mathbb R|$ (of course you would need to justify these by previous equalities or injections/bijections - but this is usually somewhat simpler than writing the functions one by one).
  3. Cardinal arithmetics, e.g. $|\mathbb R^\mathbb N| = |(2^\mathbb N)^\mathbb N| = |2^{\mathbb N\times\mathbb N}|=|2^\mathbb N| = |\mathbb R|$.

As for the $n$-tuples, this can be shown easily by induction and cardinal arithmetic:

For $n=1$ clearly $\mathbb R$ is of cardinality continuum.

Suppose for $n$ it is true, then $\mathbb R^{n+1} = \mathbb R^n\times\mathbb R$, and the cardinality is $|\mathbb R^n|\cdot |\mathbb R|=2^{\aleph_0}\times 2^{\aleph_0} = 2^{\aleph_0+\aleph_0}=2^{\aleph_0}$ as needed.

2

Sometimes these things have sort of a strange feel to them. I will speak on something very similar to question b): the set of all ordered n-tuples of real numbers in [0,1). Suppose our n-tuples have the form $$ ( 0. \gamma^1 _1 \gamma^1 _2 \gamma^1 _3 \gamma^1 _4 ..., 0. \gamma^2 _1 \gamma^2 _2 \gamma^2 _3 ..., 0. \gamma^3 _1 \gamma^3 _2 ..., ..., 0.\gamma^n _1 \gamma^n _2...)$$

Then we can associate a distinct real number to each ordered n-tuple by simply going through the 1st digits of all the numbers, then the second, then the third, and so on. i.e. we associate the number $$0. \gamma^1_1 \gamma^2_1 ... \gamma^n_1 \gamma^1_2 \gamma^2_2 ... \gamma^n_2 \gamma^1_3 ...$$ and so on. If we require numbers to be written in non-terminating decimals only, then this satisfies the required relationship.

In addition, we know that there is a bijection between all real numbers and the reals in $[0,1]$, so this is a bit closer to directly answering your homework question than I might have liked to admit. But this is an example of the sort of flavour of these questions.

  • 0
    @user: Note, I assume that you are familiar with Cantor-Bernstein as well (I write this as I read Martin's comment above).2011-05-05