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!

  • 0
    Get the notes from a classmate.2011-05-05

2 Answers 2

5

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 t$h$at you are familiar wit$h$ Cantor-Bernstein as well (I write this as I read Martin's comment above).2011-05-05