Results 1 to 15 of 15

Math Help - countable sets

  1. #1
    Member
    Joined
    Jun 2007
    Posts
    117

    countable sets

    Show that the union of two countable sets is countable?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2007
    Posts
    117
    Quote Originally Posted by galactus View Post

    Show that the union of two countable sets is countable.
    Proof. Let A and B be the two countable sets. Then B\A is countable due to Prob. 34. From Thm. 1.7-A, the elements of A and B\A can be listed as A = {a0, a1, a2, . . . } and B\A = {c0, c1, c2, . . . } Then A B = A (B\A) = {a0, c0, a1, c1, a2, c2, . . . } is a list whose elements are all distinct and also includes all elements of A B. Hence by Thm. 1.7-A, A B is countable.

    whats does B\A means here? can someone explain to me in a bit more detail
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1
    As the link in the previous posting shows (BTW: that is an awful proof!) any proof of this really dependents upon the definitions and theorems in your particular text. There many ways to show this some are easier than other. But they depend in particular definitions.
    Last edited by Plato; July 16th 2007 at 09:46 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1
    Here is one definition of countable: a set A is countable if there is a injection, one-to-one, function f:A \mapsto N = \{ 0,1,2, \cdots \}.
    Now suppose that each of A & B is countable set, now there is also an injection such that g:B \mapsto N. We now define an injection <br />
h(x) = \left\{ {\begin{array}{lr}<br />
   {2f(x)} & {x \in A\backslash B}  \\<br />
   {2g(x) + 1} & {x \in B\backslash A}  \\<br />
\end{array}} \right.<br />
.
    BTW:  A\backslash B is set of elements in A but not in B.
    Now you must show that h is an injection.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2007
    Posts
    117
    Quote Originally Posted by Plato View Post
    Here is one definition of countable: a set A is countable if there is a injection, one-to-one, function f:A \mapsto N = \{ 0,1,2, \cdots \}.
    Now suppose that each of A & B is countable set, now there is also an injection such that g:B \mapsto N. We now define an injection <br />
h(x) = \left\{ {\begin{array}{lr}<br />
   {2f(x)} & {x \in A\backslash B}  \\<br />
   {2g(x) + 1} & {x \in B\backslash A}  \\<br />
\end{array}} \right.<br />
.
    BTW:  A\backslash B is set of elements in A but not in B.
    Now you must show that h is an injection.
    My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1
    Quote Originally Posted by TheRekz View Post
    My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?
    That is equivalent to the definition I used above. If you follow the proof I gave, then you do not have to consider cases.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TheRekz View Post
    My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?
    I would suppose I have enumerations of the two sets and take it from there.

    RonL
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2007
    Posts
    117
    Quote Originally Posted by TheRekz View Post
    My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?
    I am getting more confused by your explanation.. If both A and B are countable because they are finite then it doesn't matter because then the union of both of them have a cardinality which then can be proofed to be a injection.. I am confused by the example of Plato here giving such function g(x), say that A\B is {1,2,3,4,5} and B\A is {7,8,9,10,11} I am confused to show this injection
    Last edited by TheRekz; July 17th 2007 at 07:16 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2007
    Posts
    117
    anyone??
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TheRekz View Post
    anyone??
    If both A and B-A are countably infinite, let:  \{ a_i, i \in \mathbb{N} \} \{b_i, i \in \mathbb{N} \} be enumerations of A and B-A respectivly.

    Then:

    <br />
\{c_i, i \in \mathbb{N} \}<br />

    where c_{2j} = a_j, \ j \in \mathbb{N},\ c_{2k+1}=b_k, \ k \in \mathbb{N} is an enumeration of A \cup B and so A \cup B is countable.

    The cases where one or both of A and B are finite is easily disposed of by an enumeration where the elements of A or B-A (whichever is finite or either if both are) are taken first follwed by the elements of the other.

    RonL
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2007
    Posts
    117
    Quote Originally Posted by CaptainBlack View Post
    If both A and B-A are countably infinite, let:  \{ a_i, i \in \mathbb{N} \} \{b_i, i \in \mathbb{N} \} be enumerations of A and B-A respectivly.

    Then:

    <br />
\{c_i, i \in \mathbb{N} \}<br />

    where c_{2j} = a_j, \ j \in \mathbb{N},\ c_{2k+1}=b_k, \ k \in \mathbb{N} is an enumeration of A \cup B and so A \cup B is countable.

    The cases where one or both of A and B are finite is easily disposed of by an enumeration where the elements of A or B-A (whichever is finite or either if both are) are taken first follwed by the elements of the other.

    RonL
    why do you have to use A - B to proof this?? any reason?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TheRekz View Post
    why do you have to use A - B to proof this?? any reason?
    It gets rid of the duplicate elements. Its not strictly necessary but it cleans things up a bit.

    RonL
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2007
    Posts
    117
    Quote Originally Posted by CaptainBlack View Post
    It gets rid of the duplicate elements. Its not strictly necessary but it cleans things up a bit.

    RonL
    and why is c2j = aj
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TheRekz View Post
    and why is c2j = aj
    Because you are mapping one enumeration onto the even terms of the combined enumeration, and the other to the odd terms.

    Thus a_0, b_0, a_1, b_1, a_2, b_2, ... is the enumeration of A \cup B

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  3. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  4. Countable Sets
    Posted in the Calculus Forum
    Replies: 0
    Last Post: December 8th 2008, 05:17 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum