Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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). –  user3180 May 5 '11 at 7:01
    
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|$? –  Martin Sleziak May 5 '11 at 7:24
    
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. –  André Nicolas May 5 '11 at 7:52
    
Get the notes from a classmate. –  Gerry Myerson May 5 '11 at 12:47
add comment

2 Answers

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.

share|improve this answer
    
@user: Note, I assume that you are familiar with Cantor-Bernstein as well (I write this as I read Martin's comment above). –  mixedmath May 5 '11 at 7:30
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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