x Turn on thread page Beta
 You are Here: Home >< Maths

# Cardinality of sets: watch

1. I'm relatively new to set theory, so I'm not entirely sure where I'm going...

Let A={...,-4,-2,0,2,4,...}, B={0,1,2,3,4,5,...}, C={1,{1,2},2,{1,2,3},3,...}, D={1,{1,2},{1,{1,{1,2}}},...}.

Show that all sets, A, B, C, D have the same cardinality.

I know I have to find a bijective function that maps them onto each other, but I'm not entirely sure how to do it.

Any hints/info would be appreciated.

Thanks.
2. (Original post by Scott3142)
Any hints/info would be appreciated.
I'm very rusty on this, and not clear what set D is.

Since you're talking about bijections, then I presume you have some familiarity with injections.

Rather than construct bijections, you will probably find it easier to construct injections to show that:

and hence they all have the same cardinality. A different ordering of the sets may make it easier; as I said, I'm v. rusty.
3. Okay, so I can see that every element of A maps to an element of B, and also that there are all natural numbers in C, plus the additional subsets. So I can see that but I'm struggling with the next part, and also with how to state this in a rigorous way.
4. (Original post by Scott3142)
Okay, so I can see that every element of A maps to an element of B, and also that there are all natural numbers in C, plus the additional subsets. So I can see that but I'm struggling with the next part, and also with how to state this in a rigorous way.
As I said, I'm not clear what set D is. It may be something standard, but if it is, it's not one I am familiar with; and even if I was familiar with it I may not know the answer as it's a looonng time ago.

Regarding making it rigorous; you need to explicitely state what the injective functions are. If it's not obvious start with a verbal description, and then try converting it into mathematical notation.

Edit: Part of the problem with set D is that from what you've posted, I've no idea what the rest of the elements are that make up that set, there doesn't seem to be a consistent rule governing their construction.

Hopefully there will be someone more knowledgeable along who can help further.
5. Okay, thanks anyway. I can give a verbal description of what the functions are I think, but only for the first 2, I'm still not entirely clear on the last bits.
6. (Original post by ghostwalker)
I'm very rusty on this, and not clear what set D is.

Since you're talking about bijections, then I presume you have some familiarity with injections.

Rather than construct bijections, you will probably find it easier to construct injections to show that:

and hence they all have the same cardinality. A different ordering of the sets may make it easier; as I said, I'm v. rusty.
This is valid, however, without the formalism of transfinite cardinals (e.g. in first-year mathematics), this is unlikely to be accepted as correct without some explanation. It's pedagogically cleaner to use the Cantor-Bernstein theorem instead, which tells us that if we have injections and , then there is some bijection .
7. Would it be valid to say

B is the set of natural numbers, which is known to have the same cardinality as Z.

Let with

Let be defined by etc.

Let be defined by etc.

Thus, as A and C have the same cardinality as and B and D have the same cardinality as and has the same cardinality as , hence they are all equal.
8. No. You need an injection from or in each case as well, in order to show that each one have the same cardinality.
9. (Original post by Zhen Lin)
This is valid, however, without the formalism of transfinite cardinals (e.g. in first-year mathematics), this is unlikely to be accepted as correct without some explanation.
Poor notation on my part, sorry; I was thinking, if there exists an injection from A to B, and B to C, C to D, and D to A, then by compostion of functions, there exists injections form B to A, etc. Took a step too far with the cardinalities.

Edit: And by the looks of things not the best route anyway.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: October 3, 2010
Today on TSR

### Complete university guide 2019 rankings

Find out the top ten here

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams