Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    0
    ReputationRep:
    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.
    • Study Helper
    Online

    15
    Study Helper
    (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:

    |A|\le|B|\le|C|\le|D|\le|A|

    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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    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 |A| \leq |B| \leq |C| but I'm struggling with the next part, and also with how to state this in a rigorous way.
    • Study Helper
    Online

    15
    Study Helper
    (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 |A| \leq |B| \leq |C| 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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    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.
    Offline

    2
    ReputationRep:
    (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:

    |A|\le|B|\le|C|\le|D|\le|A|

    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 A \to B and B \to A, then there is some bijection A \to B.
    • Thread Starter
    Offline

    0
    ReputationRep:
    Would it be valid to say

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

    Let  f_1 : A \rightarrow \mathbb{Z} with  f_1(a)=\frac{a}{2} \forall a \in A.

    Let  f_2 : D \rightarrow \mathbb{N} be defined by  1 \rightarrow 1, 2 \rightarrow [1,2], 3 \rightarrow [1,[1,2]] etc.

    Let  f_3 : C \rightarrow \mathbb{Z} be defined by  1 \rightarrow 1, 2 \rightarrow 2, [1,2] \rightarrow 0, [1,2,3] \rightarrow -1  etc.

    Thus, as A and C have the same cardinality as  \mathbb{Z} and B and D have the same cardinality as  \mathbb{N} and  \mathbb{Z} has the same cardinality as  \mathbb{N} , hence they are all equal.
    Offline

    2
    ReputationRep:
    No. You need an injection from \mathbb{Z} or \mathbb{N} in each case as well, in order to show that each one have the same cardinality.
    • Study Helper
    Online

    15
    Study Helper
    (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.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: October 3, 2010
Poll
Do you like carrot cake?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.