Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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

    StatusX

    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

    HallsofIvy

    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

    StatusX

    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.
    thanks
    that makes sense.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook