Countability of set of sequences

[SiddharthM]

I was looking at some practice tests and I came upon this tricky question. I'm not sure I would have got it on an exam!

Consider the set, S, of all infinite sequences whose entries are either 1 or 2. However, if the nth term is 2 then the n+1th term is 1. I.e every 2 is followed by a one.

Theorem: S is uncountable

That it is infinite is simple to show. Consider the set of all sequences described as above except with only a single 2. Then this subset is equivalent to the natural numbers.

Consider the subset of S where every even term is a one, then list these. Now to show there is a sequence in the subset that is not listed create a new one by switching the odd terms diagonally. That is

2,1,2,1,2,1...(1st term is 2)
1,1,1,1,1,1...(3rd term is 1)
1,1,2,1,1,1...(5th term is 1)

so the new sequence begins with 1,1,2,1,2,1...

Another way to see how this works is to consider 2,1 = 1 and 1,1 =0, then each of these sequences can be written as sequences of zeros and ones which we know is uncountable by using a similar method of proof.

Since this subset of S is uncountable, and S is infinite, S must be uncountable.

 

[HallsofIvy]

How about this: map every sequence of 1s and 2s to a sequence of 0s and 1s. One way to do that is to just change every 2 to a 0. That's clearly a one-to-one correspondence. Now, do you see that that corresponds to every number between 0 and 1, written in binary?

 

[SiddharthM]

How about this: map every sequence of 1s and 2s to a sequence of 0s and 1s. One way to do that is to just change every 2 to a 0. That's clearly a one-to-one correspondence.

I'm not so sure. Take the sequence that is identically 0. There is no sequence in S that maps (in the way you described) to the identically 0 sequence. You would need the identically 2 sequence to be in S but given the restriction that every 2 is followed by a one this sequence is NOT in S. So that mapping is not a one-to-one correspondence with S.

 

[HallsofIvy]

Sorry, I completely missed the "However, if the nth term is 2 then the n+1th term is 1" part.
How about this. map every "2" except the "nth" term to 0. If the nth term is 2, map it and the succeeding 1 to "2". That way you get a sequence of 0, 1, or 2: then real numbers from 0 to 1 in base 3.