• No products in the cart.

# Countable or not? (TIFR 2013 problem 34)

Question:

True/False?

Let $$S$$ be the set of all sequences $$\{a_1,a_2,…,a_n,…\}$$ where each entry $$a_i$$ is either $$0$$ or $$1$$. Then $$S$$ is countable.

Hint:

What if instead of $$0$$ and $$1$$ the values were allowed to be any digit from $$0$$ to 9? What would that correspond to?

Discussion:

Given a sequence  $$\{a_1,a_2,…,a_n,…\}$$ , we can associate it to the binary number $$0.a_1a_2…a_n…$$. This association (or function if you like) is one-one, and onto the set of all real numbers having binary expansion in the form of $$0.something$$, which is same as the set $$(0,1)$$, which is uncountable.

Remark:

One could use Cantor’s diagonalization argument as well to argue in this problem. If possible let $$x_1,x_2,…$$ is an enumeration of the given set (of sequences) then consider the sequence $$\{b_1,b_2,…\}$$ in $$S$$ defined by $$b_i \ne x_i$$. We get a contradiction because this is a sequence which is not in the enumeration but is a member of $$S$$.

September 12, 2017