Hey there! Sign in to join this conversationNew here? Join for free
 You are Here: Home >< Maths

# Countable sets Watch

1. If there is a function f: X -> Y where X is countable, then there is a bijection g: N -> X. What I don't understand is why is g(f(1)), g(f(2)),... a list of elements of Y? Can someone explain this to me please.
EDIT: f:X -> Y is a surjective map.
2. I don't understand that either. Firstly, f(1) isn't defined, since 1 isn't necessarily in X. Secondly, because we need some more conditions on f (even if we were taking f(g(1)), f(g(2)), ...
3. (Original post by SimonM)
I don't understand that either. Firstly, f(1) isn't defined, since 1 isn't necessarily in X. Secondly, because we need some more conditions on f (even if we were taking f(g(1)), f(g(2)), ...
Oh yeah! I forgot to mention that f: X -> Y is surjective.
4. No one?
5. If X is countable then X ~ N. If f:N->X is subjective then X is countable.

..

Spoiler:
Show
the proof of the second statement is demi non trivial as a tip you would be wise to consider the set {n | f(n) = x} where x is an element of X.
6. (Original post by DeanK22)
If X is countable then X ~ N. If f:N->X is subjective then X is countable.

..

Spoiler:
Show
the proof of the second statement is demi non trivial as a tip you would be wise to consider the set {n | f(n) = x} where x is an element of X.
Sorry I'm not sure what you mean, I just needed to know why g(f(1)),... is a list of elements of Y. Unless of course that was the explanation but I don't understand it.
7. Why does 1 happen to be in X?
8. (Original post by DeanK22)
Why does 1 happen to be in X?
I'm not sure, but this is the answer "If X is finite then so is Y because f is surjective, hence countable. So we may
assume X and Y to be infinite. Let g : N -> X be a bijection. Since g is surjective
g(f(1)), g(f(2)), g(f(3)),... is a list of the elements of Y . Obtain a new list by striking
out all repetitions in that list and for all n in N, let g(n) be the n-th element in the new list.
Then g : N -> Y is a bijection, and so Y is countable."
It doesn't say why 1 is in X and we have to show that Y is countable. I understand the rest of it, just not the part in bold.
9. Write down everything you know on a piece of paper and think what makes you get to each step. Also, you continually add more and more assumptions! Since when was g bijective? You only mentioned surjectivity.

Think hard about why 1 does not have to be in X and even if it isn't, why we cannot assume it is (well, we actually won't do any harm in this question but just think ... it is not the case 2 or 3 should be X either ...).
10. (Original post by DeanK22)
Write down everything you know on a piece of paper and think what makes you get to each step. Also, you continually add more and more assumptions! Since when was g bijective? You only mentioned surjectivity.

Think hard about why 1 does not have to be in X and even if it isn't, why we cannot assume it is (well, we actually won't do any harm in this question but just think ... it is not the case 2 or 3 should be X either ...).
I mentioned that f: X -> Y is a surjective map but the fact that X is countable means there is a function say g for example that g: N -> X is a bijection. Isn't that correct?
11. I suspect there's a been a typo. f(g(1)), f(g(2)), etc. makes much more sense.
12. (Original post by Zhen Lin)
I suspect there's a been a typo. f(g(1)), f(g(2)), etc. makes much more sense.
Thank you! It's been bothering me for a while now, it seemed very unlikely that it's a typo since it's written in the mark-scheme. But since you said it is a typo I'll believe you.

Reply
Submit reply
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: December 25, 2010
Today on TSR

### Cambridge interview invitations

Has yours come through yet?

### Official Oxford interview invite list

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

## Make your revision easier

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

Can you help? Study help unanswered threads

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• 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

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