1. ## Cantor's Diagonalization

Hi folks.

Got a Set question here:

"Use Cantor's diagonalization method to show that the set of all infinite strings of the letters {a,b} is not countable."

So here's what I have already tried:

I assumed it was denumerable to begin with and I want to produce a number that's not on the list in order to prove it's actually not countable.

First I figure I'll depict the string in a list... and I want to have 3 elements to do a proper diagonalization, but I couldn't get it to work well since I only have a and b...
S1 = L11 L12 L13
S2 = L21 L22 L23
S3 = L31 L32 L33

So, X = X1 X2 ...
if L11 = a, X1 = a, otherwise X1 = b
if L22 = a, X2 = a, otherwise X2 = b

Honestly I'm not really sure what to do at this point.

2. Originally Posted by mander
Hi folks.

Got a Set question here:

"Use Cantor's diagonalization method to show that the set of all infinite strings of the letters {a,b} is not countable."

So here's what I have already tried:

I assumed it was denumerable to begin with and I want to produce a number that's not on the list in order to prove it's actually not countable.

First I figure I'll depict the string in a list... and I want to have 3 elements to do a proper diagonalization, but I couldn't get it to work well since I only have a and b...
S1 = L11 L12 L13
S2 = L21 L22 L23
S3 = L31 L32 L33

So, X = X1 X2 ...
if L11 = a, X1 = a, otherwise X1 = b
if L22 = a, X2 = a, otherwise X2 = b

Honestly I'm not really sure what to do at this point.
The way I see it you just list all strings. Since its countably many, we can index it using natural numbers.

Let $s_{ij}$ denote the 'j'th letter of the 'i'th string in your list.

Now create a new string x such that $x_{j} = \text{NOT}(s_{jj})$, where $x_j$ denotes the jth letter of the string.(Note that NOT(a) = b and NOT(b) = a)

Now claim that x cannot equal any of the strings in the list.

3. Originally Posted by Isomorphism
The way I see it you just list all strings. Since its countably many, we can index it using natural numbers.

Let $s_{ij}$ denote the 'j'th letter of the 'i'th string in your list.

Now create a new string x such that $x_{j} = \text{NOT}(s_{jj})$, where $x_j$ denotes the jth letter of the string.(Note that NOT(a) = b and NOT(b) = a)

Now claim that x cannot equal any of the strings in the list.
Hi Isomorphism,

Thank you for your help with this.

i think I mostly understand what you're saying, but how do I claim that X is not equal to any of the strings in the countable list?

Do I have to prove that other than differentiating it by saying its jth letter is NOT the jth letter of S ?

Thanks again

4. Originally Posted by mander
Hi Isomorphism,

Thank you for your help with this.

i think I mostly understand what you're saying, but how do I claim that X is not equal to any of the strings in the countable list?

Do I have to prove that other than differentiating it by saying its jth letter is NOT the jth letter of S ?

Thanks again
Well its simple. For two strings to be identical, every position's letter must be equal to the corresponding position's letter. Consider the ith string in the list.. It definitely differs in the ith position if x, since we constructed x such that $s_{ii} \neq x_i$. This means $x$ definitely varies in at least one position when compared to $s_i$. But "i" assumed was arbitrary. So it must work for all natural numbers 'i'.

But this argument implies that we have created a new string thats not there in the list. Thus our initial assumption that the number of strings is countably many is wrong.

5. Originally Posted by mander
Hi folks.

Got a Set question here:

"Use Cantor's diagonalization method to show that the set of all infinite strings of the letters {a,b} is not countable."

So here's what I have already tried:

I assumed it was denumerable to begin with and I want to produce a number that's not on the list in order to prove it's actually not countable.

First I figure I'll depict the string in a list... and I want to have 3 elements to do a proper diagonalization, but I couldn't get it to work well since I only have a and b...
S1 = L11 L12 L13
S2 = L21 L22 L23
S3 = L31 L32 L33

So, X = X1 X2 ...
if L11 = a, X1 = a, otherwise X1 = b
if L22 = a, X2 = a, otherwise X2 = b

Honestly I'm not really sure what to do at this point.
What you have done is not right, the idea is that X should differ from Si at the i-th position, your construction has X agree with Si at the i-th position.

You need:

So, X = X1 X2 ...
if L11 = a, X1 = b, otherwise X1 = a
if L22 = a, X2 = b, otherwise X2 = a
:
:

Then since X differs at some position from every S it cannot be amoung the S's, hence the assumption of denumerability must be false

RonL

6. Aha!
Great, thanks for your help, Isomorphism and RonL.
I understand now!