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

Math Help - denumerable sets

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    3

    denumerable sets

    ok im confused on how to start with this
    we had previously proved that A is a denumerable set and x is an element not in A, then A union {x} is also deumerable.
    Prove that if S = {x1, x2, ...,xn} is a set of n elements, none of which are in A, then A union S is denumerable
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by mathcnc View Post
    ok im confused on how to start with this
    we had previously proved that A is a denumerable set and x is an element not in A, then A union {x} is also deumerable.
    Prove that if S = {x1, x2, ...,xn} is a set of n elements, none of which are in A, then A union S is denumerable
    prove by induction on the "size" of S
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by mathcnc View Post
    ok im confused on how to start with this
    we had previously proved that A is a denumerable set and x is an element not in A, then A union {x} is also deumerable.
    Prove that if S = {x1, x2, ...,xn} is a set of n elements, none of which are in A, then A union S is denumerable
    Since A\cup\left\{x\right\}=A_1 is countable it follows that A_1\cup\left\{x_1\right\} is countable and it follows that A_{n}\cup\left\{x_n\right\} is countable assuming that n is finite. The reason for the finiteness of n is that any finite set is countable since if you have a set with n elements you can easily find a bijection with the nth natural number. If n were infinite then we could have that S=\mathbb{R}-\mathbb{Q} or any other uncountable set, the only way to guarantee countability is finitness. In fact, it is true that if both A,B are countable then so is A\cup B regardless of their individual cardinalities, but since S was not given as either countable or uncountable we may not use this argument.

    EDIT: I completely missed you post Jhevon, my apologies.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Mathstud28 View Post
    if you have a set with n elements you can easily find a bijection with the nth natural number.
    ???
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Moo View Post
    ???
    in set theory, natural numbers are defined in terms of sets. zero is the null set, and every natural number after that is defined as the set containing all previous sets, so for instance, 1 = {0}, 2 = {0,1}, 3 = {0,1,2}, ...

    so that if we have a set with n elements, we can find a bijection between that set and the nth natural number, since the natural number n is itself a set with n elements. thus we can do with finite sets and natural numbers the same thing we can do with infinite countable sets (a.k.a denumerable sets) and the set \mathbb{N}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jhevon View Post
    in set theory, natural numbers are defined in terms of sets. zero is the null set, and every natural number after that is defined as the set containing all previous sets, so for instance, 1 = {0}, 2 = {0,1}, 3 = {0,1,2}, ...
    You need an initial element, in this case:

     <br />
0=\{\}=\emptyset<br />

    but this is not the only way to define the natural numbers, some of us prefer the Peano axioms, so in a general setting we should avoid terminology that depends on a particular means of setting up the Naturals.

    CB
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by CaptainBlack View Post
    but this is not the only way to define the natural numbers, some of us prefer the Peano axioms, so in a general setting we should avoid terminology that depends on a particular means of setting up the Naturals.

    CB
    Agree
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by CaptainBlack View Post
    You need an initial element, in this case:

     <br />
0=\{\}=\emptyset<br />
    yes, i mentioned that

    but this is not the only way to define the natural numbers, some of us prefer the Peano axioms, so in a general setting we should avoid terminology that depends on a particular means of setting up the Naturals.

    CB
    indeed. i was merely explaining where Mathstud was coming from. i believe he was thinking of natural numbers in this context.

    of course, i do not think that this is how the OP would have the natural numbers defined in his/her course. which is why i suggested induction in the first place, to avoid this issue altogether.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jhevon View Post
    yes, i mentioned that
    Well I have looked at your post again and I still can't see it

    CB
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by CaptainBlack View Post
    Well I have looked at your post again and I still can't see it

    CB
    zero is the null set


    The reason for the finiteness of n is that any finite set is countable
    There is something disturbing me above, why wouldn't n be finite ? ^^'
    If one defines a set of n elements, doesn't it mean it's finite ?
    Oh right, again, it may be something related to the definition of natural numbers...
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Moo View Post
    There is something disturbing me above, why wouldn't n be finite ? ^^'
    If one defines a set of n elements, doesn't it mean it's finite ?
    Oh right, again, it may be something related to the definition of natural numbers...
    Finite set is which is equipotent to a natural number (where the natural numbers are defined in terms of sets above).
    Infinite set is not finite.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by ThePerfectHacker View Post
    Finite set is which is equipotent to a natural number (where the natural numbers are defined in terms of sets above).
    Infinite set is not finite.
    But n designs a natural number... ><
    Nevermind
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Hows this?

    We are given that a set A is countable, as well as the set A_1=A\cup\left\{x_1\right\}. Now let us prove that for finite n\in\mathbb{N} that A_n=A\cup\left\{x_1,x_2,\cdots,x_n\right\} is finite. To do this we use induction:

    \bullet It is given that the base case, A\cup x_1, is true.
    \bullet Now let us restate our inductve hypothesis: If n\in\mathbb{N} is finite and A countable then A_n=A\cup\left\{x_1,x_2,\cdots,x_n\right\} is countable.
    \bullet We left to prove that if A_n is countable then so is A_{n+1}. To do this we first observe that A_{n+1}=A_n\cup\left\{x_{n+1}\right\}. Now if A_n is countably infinite this is obviously true because the cardinality of A_{n+1} would be \aleph_0+1=\aleph_0. Now suppose that A_n is finite with cardinality m. Then by the countability of A_n we may find a bijection between the mth natural number and A_n. Let's call this bijection f(k). Now it is clear then that if we define the cardinality of A_n as m that we can construct the following function: g(k)=\left\{ \begin{array}{rcl} f(k) & \mbox{if} & 1\leqslant k \leqslant m\\<br />
A_{n+1} & \mbox{if} & k=m+1 \end{array}\right. which is bijective. Thus we have shown that there is a bijection between the m+1th natural number and A_{n+1}, thus it is countable.

    Note: The neccessity of the finiteness of n is that if n were infinite then \left\{x_1,x_2,\cdots,x_n\right\} could be any number of uncountable sets such as the irrationals or the reals. The only way to guarantee the coutability of \left\{x_1,x_2,\cdots,x_n\right\} is to restrict its cardinality.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Dec 2008
    Posts
    3
    ok that helps me out a lot
    but im still having trouble what this means
    i understand the steps to prove it
    but what does it mean!?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by mathcnc View Post
    ok that helps me out a lot
    but im still having trouble what this means
    i understand the steps to prove it
    but what does it mean!?
    How do you understand the steps to prove it but don't understand it? It is basically saying that if A is countable and B has finite cardinality then A\cup B is countable.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 2nd 2010, 12:21 PM
  2. Prove that sets are denumerable
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: July 4th 2010, 01:02 PM
  3. finite and infinite sets...denumerable
    Posted in the Differential Geometry Forum
    Replies: 15
    Last Post: November 22nd 2009, 06:38 PM
  4. Denumerable sets...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 5th 2009, 11:26 PM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: February 20th 2008, 11:08 AM

Search Tags


/mathhelpforum @mathhelpforum