Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - use diagonalization to prove uncountability

  1. #1
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    use diagonalization to prove uncountability

    I have this problem to solve but I cant get my head wrapped arround it. Most of the tutorials keeps showing example of proving that there is uncountable number of binary functions. I have following problem...
    A function from N to N is said to be repeating if f(n) = f(n + 1) for some (n E N).Otherwise, f is said to be nonrepeating. Prove that there are an uncountable number of nonrepeating functions.
    Can someone give me some pointers or guide me a little to solve this problem please. I would prefer guidance over the solution becuase i need to know how to solve these kinds of problems using diagonalization.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: use diagonalization to prove uncountability

    Suppose that there are countably many nonrepeating functions (i.e., sequences). Write them horizontally one under another. Then consider the sequence of numbers on the diagonal and turn it into a sequence that is (1) different from all others written here and (2) nonrepeating.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: use diagonalization to prove uncountability

    thank you for reply. But what are those non repeating functions??
    can you write similar example just to get me going please
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: use diagonalization to prove uncountability

    The definition you gave says that f(n) is repeating if there exists an n\in\mathbb{N} such that f(n)=f(n+1). Correspondingly, f(n) is nonrepeating if f(n)\ne f(n+1) for all n\in\mathbb{N}, i.e., the value of f necessarily changes when the argument is increased by 1. Since sequences can be naturally associated with functions from \mathbb{N} to \mathbb{N}, we have that

    0, 1, 2, 2, 3, 4, 5, 6, ...

    is repeating, but

    0, 1, 2, 3, 4, 5, 6, 7, ...

    is nonrepeating.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: use diagonalization to prove uncountability

    so if I have something like this....

    0, 1, 2, 3, 4, 5, 6, 7, ...
    1, 2, 3, 4, 5, 6, 7, 8, ...
    2, 3, 4, 5, 6, 7, 8, 9, ...
    3, 4, 5, 6, 7, 8, 9, 10 ...

    so diagonal is 0,2,4,6....
    we pick something that is not 0,2,4,6...

    now i have to come up with function that can produce something that is not 0,2,4,6??

    Am i close?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: use diagonalization to prove uncountability

    The sequence you need to come up with should not simply be different from the diagonal (two sequences are different if they differ in at least one position). You need a sequence that differs with the diagonal in every position. Indeed, let's call the functions in the list f_k(n), k=0,1,\dots, and let d(n)=f_n(n) be the diagonal. If some g(n)\ne d(n)=f_n(n), then we know that g\ne f_n because g and f_n differ in the nth position. You need a g such that g\ne f_n for all n, and one way to achieve this is to make g(n)\ne d(n) for all n. However, a g(n) like this may be repeating; then nothing has been proved since the list f_k(n) may still contain all nonrepeating functions. Therefore, you need to find a nonrepeating g such that g(n)\ne d(n) for all n.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: use diagonalization to prove uncountability

    yes but how can you know what is going to be in diagonal at nth positions?? how can you assure that every position in diagonal is different?

    Suppose that we can count the non-repeating sequences. Something like this:
    \begin{array}{*{20}{c}}{{f_1}}&|&{{x_{1,1}}}&{{x_{  1,2}}}&{{x_{1,3}}}&{{x_{1,4}}}& \cdots \\{{f_2}}&|&{{x_{2,1}}}&{{x_{2,2}}}&{{x_{2,3}}}&{{  x_{2,4}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}\\{{f_n}}&|&{{x_{n,1}}}&{{x_{n,2}}}& \cdots &{{x_{n,n}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}<br />
\end{array}

    We define a new sequence in which d_1 can be any valid term so long as d_1\ne x_{1,1}.

    Next define d_2 so that d_2\ne x_{2,2}~\&~d_2\ne d_1.

    If n\ge 3 define d_n so that d_n\ne x_{n,n}~\&~d_n\ne d_{{n-1}.
    (we leave aside any issues of enough different terms).

    Now the (d(n)) sequence is non-repeating so by supposition it was counted among the f's.
    BUT it differs from any f_n at x_{n,n} (the diagonal position).
    So it cannot be any one of the f's contrary to the assumption that we can count the non-repeating sequences..
    Last edited by Plato; September 24th 2013 at 09:12 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: use diagonalization to prove uncountability

    Quote Originally Posted by stribor40 View Post
    yes but how can you know what is going to be in diagonal at nth positions?? how can you assure that every position in diagonal is different?
    Different from what? Please express yourself unambiguously.

    Are you asking how to come up with g(n) that is different from a given d(n)? Well, if you give somebody a number 10 and ask them to give you back a different number, they can surely do it. What if you need to teach a computer how to do it (i.e., return a different number)? Are you able to write an algorithm (informally, not using any particular programming language) that returns a number different from the one it is given?

    To be honest, I believe every kindergarten student who knows some numbers (he/she does not even have to know how to count) knows how to give a different number. This makes me think that you are asking something different, which brings me to the original question: Different from what?
    Last edited by emakarov; September 24th 2013 at 08:55 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: use diagonalization to prove uncountability

    i think i am just confused on how to line up all these functions and numbers in each line
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: use diagonalization to prove uncountability

    I assume that natural numbers start with 0. In your example

    0, 1, 2, 3, 4, 5, 6, 7, ...
    1, 2, 3, 4, 5, 6, 7, 8, ...
    2, 3, 4, 5, 6, 7, 8, 9, ...
    3, 4, 5, 6, 7, 8, 9, 10 ...

    d is indeed 0, 2, 4, 6, ..., so we can take g(n) to be d(n) + 1, i.e., g is 1, 3, 5, 7, ... This way g is different from f_0 because g(0)=1\ne0=d(0)=f_0(0). Similarly, g is different from f_1 because g(1)=3\ne2=d(1)=f_1(1). That is, g differs from the 0th sequence in the 0th element, it differs from the 1st sequence in the 1st element and so on. In general, g(n)\stackrel{\text{def}}{=}d(n)+1\ne d(n)=f_n(n), so g differs from f_n in the nth element. There are as many places where g can be different from f_n's as there are functions in the list, so g can be different from all of them. This is the key idea of the proof.

    So far this is just a proof that the number of integer sequences is uncountable. I agree that diagonal arguments are mind-twisting. (Maybe this is because if we have a family of functions f_k(n), we are used to considering a fixed function f_k at different arguments n or different functions f_k at a fixed argument n. That is, we are used to changing either k or n separately in f_k(n), and we are less used to changing them in a coordinated manner, as in the definition of d(n)=f_n(n).) However, you need to understand it thoroughly before going further.

    In your problem, the list contains just the nonrepeating functions. This does not mean that the diagonal is nonrepeating (i.e., there may be two neighbor arguments n and n + 1 where d takes the same values). So, if we define g(n) = d(n) + 1, g may be repeating. The challenge is not only to make g differ from d everywhere, but also make it nonrepeating.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: use diagonalization to prove uncountability

    ok i will take this example and try to digest it. I appreciate your time and effort in guiding me in this problem
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: use diagonalization to prove uncountability

    i this part i have been looking at it and it makes sense. you are choosing each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one. This all makes sense because when you actually not involving any numbers. Problem becomes when you actually have to produce actual function that satisfy "each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one" requirements..
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,658
    Thanks
    1615
    Awards
    1

    Re: use diagonalization to prove uncountability

    Quote Originally Posted by stribor40 View Post
    i this part i have been looking at it and it makes sense. you are choosing each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one. This all makes sense because when you actually not involving any numbers. Problem becomes when you actually have to produce actual function that satisfy "each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one" requirements..
    I have no idea why my post showed up under your name. But here it is again:
    yes but how can you know what is going to be in diagonal at nth positions?? how can you assure that every position in diagonal is different?

    Suppose that we can count the non-repeating sequences. Something like this:
    \begin{array}{*{20}{c}}{{f_1}}&|&{{x_{1,1}}}&{{x_{  1,2}}}&{{x_{1,3}}}&{{x_{1,4}}}& \cdots \\{{f_2}}&|&{{x_{2,1}}}&{{x_{2,2}}}&{{x_{2,3}}}&{{  x_{2,4}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}\\{{f_n}}&|&{{x_{n,1}}}&{{x_{n,2}}}& \cdots &{{x_{n,n}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}<br />
\end{array}

    We define a new sequence in which d_1 can be any valid term so long as d_1\ne x_{1,1}.

    Next define d_2 so that d_2\ne x_{2,2}~\&~d_2\ne d_1.

    If n\ge 3 define d_n so that d_n\ne x_{n,n}~\&~d_n\ne d_{{n-1}.
    (we leave aside any issues of enough different terms).

    Now the (d(n)) sequence is non-repeating so by supposition it was counted among the f's.
    BUT it differs from any f_n at x_{n,n} (the diagonal position).
    So it cannot be any one of the f's contrary to the assumption that we can count the non-repeating sequences..
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: use diagonalization to prove uncountability

    When you have numbers...

    0, 1, 2, 3, 4, 5, 6, 7, ...
    1, 2, 3, 4, 5, 6, 7, 8, ...
    2, 3, 4, 5, 6, 7, 8, 9, ...
    3, 4, 5, 6, 7, 8, 9, 10 ...

    How does chosing something different from diagonal (0,2,4,6..) to something 1,5,7,9...ensuring that is different from everything else in the list (regardless of being repeating or non repeating)
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,658
    Thanks
    1615
    Awards
    1

    Re: use diagonalization to prove uncountability

    Quote Originally Posted by stribor40 View Post
    When you have numbers...
    How does chosing something different from diagonal (0,2,4,6..) to something 1,5,7,9...ensuring that is different from everything else in the list (regardless of being repeating or non repeating)
    I have my doubts that you really understand the diagonal argument.
    Please study that webpage.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: June 2nd 2011, 10:41 PM
  2. Irrational Uncountability proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 16th 2010, 06:16 PM
  3. Diagonalization
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: April 23rd 2010, 08:17 PM
  4. Infinite sequences and uncountability
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 11th 2009, 02:18 PM
  5. uncountability
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 8th 2007, 04:32 PM

Search Tags


/mathhelpforum @mathhelpforum