Results 1 to 8 of 8

Math Help - countability of a set

  1. #1
    Member
    Joined
    Feb 2010
    Posts
    133

    countability of a set

    Hello to all

    How do I prove that the set S of real sequences (x_{n}), where each x_{n} is either 0 or 1, is not a countable set.

    Hints/suggestions on how to start would be appreciated.

    Are there any books on teqhniques on proving-methods?

    Thanks a lot.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by surjective View Post
    Hello to all

    How do I prove that the set S of real sequences (x_{n}), where each x_{n} is either 0 or 1, is not a countable set.

    Hints/suggestions on how to start would be appreciated.

    Are there any books on teqhniques on proving-methods?

    Thanks a lot.
    You may consider an element of $$S as a real in [0,1] in binary, but the representation is not unique each terminating real will correspond to two elements of $$S.

    Hence \text{card}(S) \ge \text{card}([0,1]) ...

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    There are lots of ways to do this. One way is to produce an injection from a set you already know is uncountable to this set. This is essentially what CaptainBlack was suggesting.

    Here is a method that doesn't require any knowledge on the cardinality of other sets. It is called a diagonalization argument:

    I will explain the argument and you see if you can write out the details. If you're still stuck I will help you fill them in.

    We will use an indirect argument. Assume that the set S is countable. This means we can list the elements. Write down each sequence in this list (double subscripts will be helpful).
    Now see if you can "diagonalize" to produce a sequence that is not on this list.


    I'm not sure what kind of book you're looking for. If you're looking for a book on how to do proofs, then I'm not sure if there are any good sources currently out there (someone correct me if I'm wrong). If you're looking for a book that has cardinality arguments, then there are lots of them. Any book on introductory set theory will have these arguments, and many analysis books will have some arguments like this in the introductory chapter. Unfortunately I haven't really found a set theory book that I particularly like, so when I teach set theory I use my own material. I'm not saying that the books out there don't have good material - only that I don't know of a book that I would personally base a whole course around.
    Last edited by DrSteve; January 5th 2011 at 02:53 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Feb 2010
    Posts
    133
    Hey,

    Im not familiar with the principle of diagonalizing? How does that work?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by DrSteve View Post
    I'm not sure what kind of book you're looking for. If you're looking for a book on how to do proofs, then I'm not sure if there are any good sources currently out there (someone correct me if I'm wrong). If you're looking for a book that has cardinality arguments, then there are lots of them. Any book on introductory set theory will have these arguments, and many analysis books will have some arguments like this in the introductory chapter. Unfortunately I haven't really found a set theory book that I particularly like, so when I teach set theory I use my own material. I'm not saying that the books out there don't have good material - only that I don't know of a book that I would personally base a whole course around.
    I am fond of set theory. The books I'd suggest you look at (most likely you already have, but it can't hurt to suggest ) are Halmos-Naive Set Theory, Stoll-Set Theory and Logic, Goldrei-Classical Set Theory, or if you're up for as serious challenge-Jech-Set Theory.

    Quote Originally Posted by surjective View Post
    Hey,

    Im not familiar with the principle of diagonalizing? How does that work?
    Diagonalizing is a term I haven't heard applied to this argument, but the following may be what Dr. Steve means. Suppose that f:\mathbb{N}\to\{0,1\}^{\mathbb{N}} is surjective and define a_n= \pi_n(f(n))+1\text{ mod }2. Deduce that a_n\in \{0,1\}^{\mathbb{N}}-f\left(\mathbb{N}\right) contradicting surjectivity.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    I enjoy this problem. Suppose each element of S can be named with a positive integer: S=\{x_k:k\in\mathbb{Z}^+\}.

    Now say we look at x_j=(x_{j,1}, x_{j,2}, x_{j,3},\cdots, x_{j,j},\cdots) .
    So  x_{j,j} is either 0\text( or )1.

    Now we define a new bit-sequence: y_{k,j}=\left\{ {\begin{array}{*{20}c}   0 & {x_{j,j}  = 1}  \\1 & \text{else}  \\ \end{array} } \right..

    How can y be in the original list?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Drexel28 View Post
    Diagonalizing is a term I haven't heard applied to this argument, but..
    Cantor's diagonal slash.

    CB
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Plato's solution is what I had in mind. His solution is correct of course, but it may seem confusing at first. So let me try to motivate what he has done with a specific list.

    So our assumption is that we can list all such sequences. Let me write down a specific list (the "correct" list may look nothing like this of course):

    10101010101010...
    11111111111111...
    01010101010101...
    01001000100001...
    10100100010000...
    ... ... .... ...

    I will now show that this specific list cannot be correct. The main idea is that to come up with a new sequence that disagrees with each of these sequences we just need our new one to disagree with each of these in one position. So we will make it disagree with the first one in the first position, the second in the second position, and so on...

    Since the first sequence has a 1 in the first position we will put a 0 in the first position of our new sequence

    Since the second sequence has a 1 in the second position we will put a 0 in the second position, etc.

    So our new sequence looks like this:

    00111...

    If you understand this specific list, you can now try to understand the general argument with an arbitrary list. See Plato's post for this.

    Drexel's post is the same idea, but is a little more sophisticated.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Countability
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: February 15th 2010, 08:36 PM
  2. Countability
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 23rd 2009, 12:09 AM
  3. Bijection - Countability
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 20th 2009, 08:42 AM
  4. Countability
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 28th 2008, 10:49 AM
  5. Countability
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2008, 06:26 AM

Search Tags


/mathhelpforum @mathhelpforum