I'm trying to solve 2 problems, but I'm having some issues and would appreciate help. Here are the questions and what I thought could be done:

1) A is the set of all series of numbers, where in an even place there is an even number, and in an odd place there is an odd number (for example, the series {8,3,2,5,0,1,28,...} is a valid member of A).

Is A of countable cardinality? If it is, find a one-to-one correspondence with the natural numbers.

My solution: I thought of sending a series, to a natural number. like, the example we got? I would send that series to the number 83250128 but I don't think thats a good solution...

2) B is the set of all series that only contain values that are prime numbers. Is B of countable cardinality? If it is, find a one-to-one correspondence with the natural numbers.

  • $\begingroup$ You should be using the word sequence, not series. The word series has a different meaning associated with it. $\endgroup$
    – JessicaK
    Nov 6, 2013 at 14:49
  • $\begingroup$ סדרה = sequence, not series. Also, are you allowing only finite, or also infinite sequences? $\endgroup$
    – Asaf Karagila
    Nov 6, 2013 at 14:49
  • $\begingroup$ We were not taught that. I don't know what you mean. infinite sequences also. My bad about the series / sequence thing. English is not my main language, sorry. $\endgroup$ Nov 6, 2013 at 14:49
  • $\begingroup$ Try proving that a countably infinite union of countably infinite sets is countably infinite (hint: proof that the rationals are countably infinite) (hint 2: this is true) $\endgroup$ Nov 6, 2013 at 14:50
  • $\begingroup$ Hint: In both cases consider the map $(a_1, a_2, ...) \mapsto (a_1\mod 3, a_2\mod 3, ...)$ and realize this is a surjection onto $\{0,1,2\}^{\mathbb{N}}$. Now, why does this show uncountability? $\endgroup$
    – Tom
    Nov 6, 2013 at 14:58

1 Answer 1


For $B$:
Write each irrational $q \in [0,1]$ in binary, now identify that irrational with the sequence $\langle a_n, n < \infty \rangle$ where $a_n = 3$ if the $n^{th}$ digit of $q$ is $0$, or else $a_n = 5$ if the $n^{th}$ digit of $q$ is $1$. This defines an injection from the irrationals in $[0,1]$ to $B$, hence $B$ is uncountable.
For $A$, think about Daniel Rust's comment.

  • $\begingroup$ Could you explain what you mean by writing an irrational number in binary? $\endgroup$ Nov 6, 2013 at 15:06
  • $\begingroup$ @OriaGruber Sure, take the unit interval, divide it into two segments: $[0,\frac{1}{2}]$,$(\frac{1}{2},1]$. If your irrational number lies in the first segment, its first digit is $0$, else its first digit is $1$. Continue this process, infinitely many times. If you still do not understand, see: en.wikipedia.org/wiki/Binary_number $\endgroup$
    – Rustyn
    Nov 6, 2013 at 15:10
  • $\begingroup$ Thanks. One last question (I solved it but I just want to double check with someone more experienced). The set of all lines that pass through (0,0) is not countable (because the slope can be any real number), and the set of all lines of the form y=mx+n where m and n are rational numbers is countable (bijection with QxQ) $\endgroup$ Nov 6, 2013 at 15:17
  • $\begingroup$ The set of all lines who go through $(0,0)$ is indeed uncountable, they have the form $y=mx$, for any real $m$. So, for any real $m$, identify that real with the line $y=mx$ whose slope constant is $m$. This defines an injection from the reals to all the lines $y=mx$. Hence the set of lines that go through $(0,0)$ is uncountable. $\endgroup$
    – Rustyn
    Nov 6, 2013 at 15:33

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.