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!(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Countability of set of sequences

Loading...

Similar Threads for Countability sequences | Date |
---|---|

Proof that algebraic numbers are countable | Nov 19, 2011 |

Set of all rational sequences countable? | Nov 6, 2011 |

The Boundary of a Countable Union of Almost Disjoint Cubes | Sep 26, 2010 |

A question on proving countable additivity | Jul 9, 2010 |

Cardinality: |R\N| = |R\C| where C is countable | Mar 15, 2010 |

**Physics Forums - The Fusion of Science and Community**