1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cantor's diagonalization

  1. Jul 17, 2006 #1
    I am stumpt on this problem:
    Use Cantor's diagonalization method to show that the set of all infinite
    strings of the letters {a,b} is not countable:

    Can I have a hint? :redface:
  2. jcsd
  3. Jul 17, 2006 #2


    User Avatar
    Homework Helper

    Do you understand the argument that shows that the set of decimal numbers between 0 and 1 is uncountable? Try running that argument in base two, and you have what you want.
  4. Jul 17, 2006 #3


    User Avatar
    Science Advisor

    Do you know Cantor's diagonal method? The application here is pretty direct. Assume that the set of all infinite sequences of {a,b} is countable. Then you can put them in a numbered list. Create a string z by "if the nth letter in the nth sequence is a, the nth letter in z is b, else the nth letter in z is a". Where is z in the list?
  5. Jul 17, 2006 #4
    I guess my problem is coming up with a numbering scheme of these strings, so that I could see a diagonal. Do i always need to disprove by diagonal? I know it is called diagonalization principle but still.....
    I think I understand the principle, but sometimes the prof changes a small thing and then we all are lost.
    So, yeah, if someone can lead me on numbering, that would be appreciated.
  6. Jul 17, 2006 #5


    User Avatar
    Homework Helper

    You don't need a numbering scheme. The assumption that the set is countable is equivalent to the statement that there exists a bijection between it and the natrual numbers. So if you assume the existence of such a bijection and reach a contradiction, you have disproved the hypothesis that the set is countable.
  7. Jul 17, 2006 #6
    oh, ok.
    that makes sense.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook