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

Math Help - Cardinality Problem

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    44

    Cardinality Problem

    1. Show that |Z| = |5Z| that is to say by exhibiting a one-to-one correspondence between them.
    2. Show that |Z| = |7Z|
    3. Show that |5Z| = |7Z|

    Well, I know that number 3 would follow from 1 and 2. I am not sure how to work them out though.

    Thank you in advance for your help!
    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 MathStudent1 View Post
    1. Show that |Z| = |5Z| that is to say by exhibiting a one-to-one correspondence between them.
    2. Show that |Z| = |7Z|
    3. Show that |5Z| = |7Z|

    Well, I know that number 3 would follow from 1 and 2. I am not sure how to work them out though.

    Thank you in advance for your help!



    1. This exhibition might be a little trivial, but I think it does the job

    We know the set Z can be written as 0, 1, -1, 2, -2, 3, -3,…
    And the set 5Z, which is a subset of Z, can be written as 0, 5, -5, 10, -10,….

    Thus, f:Z-->5Z may be exhibited by:

    0------------> 0
    1------------> 5
    -1-----------> -5
    2------------>10
    -2-----------> -10
    ….
    .
    .
    Which is a one to one correspondence (bijective function) between Z and 5Z. The function f:Z-->5Z can be expressed as f(x) = 5x, where x is an element of Z. f is a one-to-one, onto function between the two sets, and hence is a one to one correspondence (or bijective) function

    2. I think we can do this a little differently, using theorems which I hope you’ve heard of.

    Definition: A set is called denumerable if it is infinite and countable, that is there is a one to one correspondence between the set and the natural numbers. In other words, if a set A is denumerable, then |A| = |N|.

    Theorem: The set Z is denumerable. That is, |Z|=|N|

    Theorem: Any infinite subset of a denumerable set is denumerable.

    Thus, since 5Z is an infinite subset of Z (it selects all elements from Z that are multiples of 5), the set 5Z is denumerable. So |5Z|=|N|

    Similarly, 7Z is a subset of Z, so |7Z|=|N|=|Z|. So |Z|=|7Z| by transitivity.

    3. Also by transitivity, since |5Z|=|N| and |7Z|=|N|, we have |5Z|=|7Z|
    Last edited by Jhevon; February 27th 2007 at 11:48 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    The explanation of 1 seems okay. I am not familiar with those terms in 2. I do understand 3. I will need to keep looking at it to clear up my confusion. Any additional help would be great! Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    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 MathStudent1 View Post
    The explanation of 1 seems okay. I am not familiar with those terms in 2. I do understand 3. I will need to keep looking at it to clear up my confusion. Any additional help would be great! Thanks.

    Well, you can do 2 the same way i did 1. Just draw a mapping diagram to illustrate it. The formula would be f(x) = 7x, where x is an element of Z.

    Then for 3, which you know, just use that transitivity argument
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MathStudent1 View Post
    1. Show that |Z| = |5Z|
    Let f: Z --> 5Z
    Defined as f(x)=5x.

    Note, that f is injective.
    If f(x)=f(y) then,
    5x=5y
    x=y.

    Note, that f is surjective.
    If y in 5Z that is y=5x for some x.
    Then, f(x)=y.

    Thus, f is a bijective map.

    2. Show that |Z| = |7Z|
    Construct that same proof.
    With the map,
    g: Z --> 7Z
    Defined as g(x)=7x.

    3. Show that |5Z| = |7Z|
    I would do this as a Category diagram.
    Look below.
    Attached Thumbnails Attached Thumbnails Cardinality Problem-picture6.gif  
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    How would I know though that Z can be written as 0, 1, -1, 2, -2, 3, -3,? Also, should this be f:Z-->Z or f:Z-->5Z? Thank you!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    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 MathStudent1 View Post
    How would I know though that Z can be written as 0, 1, -1, 2, -2, 3, -3,…? Also, should this be f:Z-->Z or f:Z-->5Z? Thank you!
    Z is just the set of integers, negative and positive, i merely arranged them in a way that's convenient. we are constructing a relation, we can do that. this list was not a function, so i would not use the f notation. f:Z-->5Z is the function between Z and 5Z, where the input comes from Z and the output from 5Z
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    What about this, should it be f:Z-->Z or f:Z-->5Z? Thank you!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    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 MathStudent1 View Post
    What about this, should it be f:Z-->Z or f:Z-->5Z? Thank you!

    What this are you refering to? The function that shows |Z|=|5Z| should be f:Z-->5Z
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    Sorry, I am referring back to your original answer from the section below:

    Which is a one to one correspondence (bijective function) between Z and 5Z. The function f:Z-->Z can be expressed as f(x) = 5x, where x is an element of Z. f is a one-to-one, onto function between the two sets, and hence is a one to one correspondence (or bijective) function.

    What I put in bold should that be f:Z-->5Z instead? Not sure? Thanks.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    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 MathStudent1 View Post
    Sorry, I am referring back to your original answer from the section below:

    Which is a one to one correspondence (bijective function) between Z and 5Z. The function f:Z-->Z can be expressed as f(x) = 5x, where x is an element of Z. f is a one-to-one, onto function between the two sets, and hence is a one to one correspondence (or bijective) function.

    What I put in bold should that be f:Z-->5Z instead? Not sure? Thanks.
    Yes, correct
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    Thank you! Finally, can I just say for number 3 that it follows from a and b by transitivity that |5Z| = |7Z|?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    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 MathStudent1 View Post
    Thank you! Finally, can I just say for number 3 that it follows from a and b by transitivity that |5Z| = |7Z|?
    I don't see a problem with that. I'd probably say more though, but i'm long winded (as you can probably tell).

    Like... since |Z|=|5Z| and |Z|=|7Z|, it follows by transitivity that |5Z| = |7Z|
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    Okay, thanks Jhevon!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    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 MathStudent1 View Post
    Okay, thanks Jhevon!

    Sure thing. Be sure to consider TPH's solution as well. It's a much neater way to approach the problem when illustration is not an issue.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Cardinality Problem (2)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 9th 2011, 08:11 AM
  2. [SOLVED] Cardinality Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 4th 2011, 05:49 AM
  3. Cardinality...last one
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 5th 2010, 01:29 AM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 7th 2009, 12:34 PM
  5. cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 3rd 2008, 07:26 AM

Search Tags


/mathhelpforum @mathhelpforum