Results 1 to 6 of 6

Math Help - Cantor's Diagonalization

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    27

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by mander View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2008
    Posts
    27
    Quote Originally Posted by Isomorphism View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by mander View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by mander View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2008
    Posts
    27
    Aha!
    Great, thanks for your help, Isomorphism and RonL.
    I understand now!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Diagonalization
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: January 23rd 2011, 01:58 PM
  2. diagonalization
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 4th 2010, 03:06 PM
  3. Diagonalization
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: April 23rd 2010, 08:17 PM
  4. A diagonalization example
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 28th 2009, 07:13 AM
  5. Diagonalization
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 23rd 2009, 11:31 AM

Search Tags


/mathhelpforum @mathhelpforum