So I was thinking about the countability of the set of binary strings of finite length.
I approached using two ways.
The worst thing is I am getting different answers in both approaches.
Here is the way I proceeded.
My Ideas.
If I am given a binary string whose left most digit is $0$ then truncate it. Remove the $0$. Do it untill you get a $1$ at the left most place.
This is simply an extension of the fact that $0334$ and $334$ are equal and the $0$ in the left of $3$ in $0334$ isn't necessary!
Now coming to the solution
Method 1.
Map each binary string to it corresponding decimal representation.
And map each Natural Number to the binary representation.
This is a bijection as both the mapping are $1-1$.
Hence our set is countable as its isomorphic to $\mathbb{N}$.
Method 2.
Consider the mapping from the set of Binary Strings to Power Set of $\mathbb{N}$.
If the binary string is $a_k a_{k-1} …a_3 a_2 a_1$ then define the set $$X=\{k\in \mathbb{N} | a_k=1\}$$
This also gives a bijection which shows that the set of binary string is Uncountable!
Where is the Error?
Best Answer
Your mapping in "method 2" maps (finite) binary strings to finite subsets of $\mathbb N$. The power set of $\mathbb N$ includes infinite subsets. So this is not a bijection.