0

I have problem with one-to-one correspondance

"One-to-one correspondence with the set (B) of all tags possible being represented with their binary representation (i.e. 0, 01, 00, 010101, 11000, 01010, 11 etc.) and the set of natural numbers. Prove that this is impossible."

It looks to me this is possible. Because I can make a bijaction btw N and B exept 1 condition. For 1 there are 2^1 tags in B. {0,1} For 2 there are 2^2 tags in B. {00,01,10,11} and it goes on ..

Could you help me with this problem?

Johnson Teller
  • 1
  • Since the set ${0,1}^k$ is finite, the set $\cup_{k=1}^\infty {0,1}^k$ is countable. – copper.hat Mar 19 '15 at 19:03
  • Should not be it uncountable ? Because we are trying to show there is no one-to-one correspondance – Johnson Teller Mar 19 '15 at 19:11
  • There is a bijection with $\mathbb{N}$. I am assuming that each tag has finite length. – copper.hat Mar 19 '15 at 19:13
  • to have proper bijection 2^0 must be equal to empty string. But I've thought there is no empty string in tags. I'm appreciate for your help. – Johnson Teller Mar 19 '15 at 19:22
  • I don't know what your last statement means. Define exactly what you mean by a tag. Why must $2^0$ equal an empty string??? What does that mean? – copper.hat Mar 19 '15 at 19:24
  • For example computer program name tags that are represented with binary numbers. 1 in N has bijection with {0,1} in B ;2 in N has bijection with {00,01,10,11} and so on. But 0 in N does not match any object in B – Johnson Teller Mar 19 '15 at 19:27
  • Sorry, I can't follow what you are trying to say. If you line all the strings up as in $0,1,00,01,10,11,000,001,...$ then clearly I can create a bijection with $\mathbb{N}$. It's just messy. There are lots of bijections, just change the order. Nothing says that the bijection must map some $n$ to a specific element of $B$. – copper.hat Mar 19 '15 at 19:32

0 Answers0