# Cantor's diagonalization

1. Jul 17, 2006

### EvLer

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?

2. Jul 17, 2006

### StatusX

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.

3. Jul 17, 2006

### HallsofIvy

Staff Emeritus
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?

4. Jul 17, 2006

### EvLer

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.

5. Jul 17, 2006

### StatusX

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.

6. Jul 17, 2006

### EvLer

oh, ok.
thanks
that makes sense.