Results 1 to 3 of 3

Math Help - A diagonalization example

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    13

    A diagonalization example

    I found the argument below on MathReference archive

    all the finite sets of integers are countable, but not so for the infinite subsets. Here is a simple diagonalization argument. If the infinite sets are countable then the correspondence builds a list of all possible subsets. Build a new subset S as follows. Let n be in S iff n is not in the nth subset on the list. Therefore S cannot appear anywhere on the list. If S is in position n, then S contains n iff it doesn't. Every possible correspondence fails, because it misses some set S.

    The bold part does not make sense to me. Could you please give me an explanation of that part? I would really appreciate that.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Suppose that S \subseteq \mathbb{Z} is infinite and the collection of all such sets is countable.
    Then we can give it a name, j, S_j .
    Each subset of the integers is countable, so we can name each element S_j  = \left\{ {n_{j,k} :k \in \mathbb{Z}^ +  } \right\}.
    Thus n_{4,10} is the tenth element in the fourth set.
    Now we have the ideal setup for a ‘diagonal argument’.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    13

    Thumbs up

    Quote Originally Posted by Plato View Post
    Suppose that S \subseteq \mathbb{Z} is infinite and the collection of all such sets is countable.
    Then we can give it a name, j, S_j .
    Each subset of the integers is countable, so we can name each element S_j  = \left\{ {n_{j,k} :k \in \mathbb{Z}^ +  } \right\}.
    Thus n_{4,10} is the tenth element in the fourth set.
    Now we have the ideal setup for a ‘diagonal argument’.
    That's very clear. Thank you very much!
    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. about diagonalization
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 6th 2009, 05:48 PM
  5. Diagonalization
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 23rd 2009, 11:31 AM

Search Tags


/mathhelpforum @mathhelpforum