Results 1 to 3 of 3

Math Help - denumerability

  1. #1
    mathkid
    Guest

    denumerability

    Prove that if A is denumerable and B is a finite subset of A, then A \ B is denumerable.
    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 mathkid
    Prove that if A is denumerable and B is a finite subset of A, then A \ B is denumerable.
    Lets assume you are using the definition of denumerable as meaning
    countably infinite.

    Let a_1,\ a_2,\ ...,\ a_n,\ ... be an enumeration of A.
    We can rearrange this enumeration so that <you may need to prove that this can be done>:

    B\ =\ \{a_1,\ a_2,\ ...,\ a_{N_B}\}

    ( N_B is the number of elements of B)

    Then:

    A \backslash B\ =\ \{a_{N_B+1},\ a_{N_B+2},\ ...\}.

    So c_1,\ c_2,\ ...,\ c_N,\ ... where c_n\ =\ a_{N_B+n} is an enumeration of A \backslash B

    RonL
    Last edited by CaptainBlack; December 6th 2005 at 11:26 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    I like to use the definition of "countable" as "can be injected into the natural numbers". It is then immediate that a subset of a countable set is countable. "Denumerable" is countable and not finite, where "finite" means every injection of the set to itself is also a surjection. All that remains is to prove that the union of two finite sets is finite; use the lemma that a finite set injects into {1..n} for some natural number n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Denumerability
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: November 15th 2010, 09:24 AM

/mathhelpforum @mathhelpforum