# Homework - countable infinity

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.

• You should be using the word sequence, not series. The word series has a different meaning associated with it. – JessicaK Nov 6 '13 at 14:49
• סדרה = sequence, not series. Also, are you allowing only finite, or also infinite sequences? – Asaf Karagila Nov 6 '13 at 14:49
• 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. – Oria Gruber Nov 6 '13 at 14:49
• 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) – Tim Ratigan Nov 6 '13 at 14:50
• 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? – Tom Nov 6 '13 at 14:58

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.

• Could you explain what you mean by writing an irrational number in binary? – Oria Gruber Nov 6 '13 at 15:06
• @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 – Rustyn Nov 6 '13 at 15:10
• 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) – Oria Gruber Nov 6 '13 at 15:17
• 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. – Rustyn Nov 6 '13 at 15:33