1. ## 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.

2. Originally Posted by MathStudent1
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.

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|

3. 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.

4. Originally Posted by MathStudent1
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

5. Originally Posted by MathStudent1
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.

6. 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!

7. Originally Posted by MathStudent1
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

9. Originally Posted by MathStudent1

What this are you refering to? The function that shows |Z|=|5Z| should be f:Z-->5Z

10. 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.

11. Originally Posted by MathStudent1
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

12. Thank you! Finally, can I just say for number 3 that it follows from a and b by transitivity that |5Z| = |7Z|?

13. Originally Posted by MathStudent1
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|

14. Okay, thanks Jhevon!

15. Originally Posted by MathStudent1
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.

Page 1 of 2 12 Last