• No products in the cart.

Profile Photo

Countable or not? (TIFR 2013 problem 34)



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.


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


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.


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\).

No comments, be the first one to comment !

Leave a Reply

Your email address will not be published. Required fields are marked *

© Cheenta 2017



FACEBOOKGOOGLE Create an Account
Create an Account Back to login/register