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

# Getting confused on the cardinality of infinite sets? watch

1. Okay 2 questions to help clear some things up for me.

To show a set A has cardinality equal to the cardinaility of the natural numbers do we need to establish an injection A--->N or an injection N--->A or a bijection A---->N or bijection N---->A? I've seen different notes using different methods so I'm getting confused. Part of me seems to think there is some kind of equivalence between these when we are dealing with infinite sets but I would like some clarity.

secondly I'm on this question and I don't know what it means really:

deduce that the set of all functions f:{0,1}----->N is countably infinite.

I don't really get what it is getting at. surely a function with domain {0,1} can only map to 2 elements of N otherwise it would be one to many therefore not a function.....?

Thanks.
2. (Original post by alex2100x)
Okay 2 questions to help clear some things up for me.

To show a set A has cardinality equal to the cardinaility of the natural numbers do we need to establish an injection A--->N or an injection N--->A or a bijection A---->N or bijection N---->A? I've seen different notes using different methods so I'm getting confused. Part of me seems to think there is some kind of equivalence between these when we are dealing with infinite sets but I would like some clarity.
Surely it's got to be a bijection ?

There's an injection from but the sets don't have the same cardinality and there's an injection from and a similar comment applies.

secondly I'm on this question and I don't know what it means really:

deduce that the set of all functions f:{0,1}----->N is countably infinite.
I guess you can consider the set of all possible co-domains of f. For each co-domain C, .
3. (Original post by atsruser)
Surely it's got to be a bijection ?

There's an injection from but the sets don't have the same cardinality and there's an injection from and a similar comment applies.

I guess you can consider the set of all possible co-domains of f. For each co-domain C, .
Okay thanks I guess that clears it up somewhat for me. Can I just ask why DFranklin said this yesterday "For many of these questions, the "quick way" is to show there's an injection into N; this immediately establishes countability (and that N x N is infinite is obvious)."

Is this because there would be a bijection iff there is an injection show showing that there is an injection is sufficient?
4. (Original post by alex2100x)
Okay thanks I guess that clears it up somewhat for me. Can I just ask why DFranklin said this yesterday "For many of these questions, the "quick way" is to show there's an injection into N; this immediately establishes countability (and that N x N is infinite is obvious)."
I have no idea. As it stands the statement seems to make no sense. What was the context?
5. (Original post by atsruser)
I have no idea. As it stands the statement seems to make no sense. What was the context?

http://www.thestudentroom.co.uk/show...995&p=52709009
6. (Original post by alex2100x)
Okay thanks I guess that clears it up somewhat for me. Can I just ask why DFranklin said this yesterday "For many of these questions, the "quick way" is to show there's an injection into N; this immediately establishes countability (and that N x N is infinite is obvious)."

Is this because there would be a bijection iff there is an injection show showing that there is an injection is sufficient?
Countability is defined is one of two ways: people either say a set is countable if it has the same cardinality as the naturals (so this definition requires that we exhibit a bijection from our set to the naturals), or if it is 'no bigger' than the naturals (so this requires an injection from our set to the naturals).

So DFranklin obviously uses the second definition. I would too - after all, we can count finite sets, so it would be better if the word countable takes these into account.
7. (Original post by Drederick Tatum)
Countability is defined is one of two ways: people either say a set is countable if it has the same cardinality as the naturals (so this definition requires that we exhibit a bijection from our set to the naturals), or if it is 'no bigger' than the naturals (so this requires an injection from our set to the naturals).

So DFranklin obviously uses the second definition. I would too - after all, we can count finite sets, so it would be better if the word countable takes these into account.
Got it thanks!!!!

I kept seeing these differing definitions popping up and I never really had that explained so cheers.

Question: if there is an injection from NxN--->N would there also be a bijection because eventually all n in N would be mapped to by some element of NxN?

What about the other way? (Does an injection N---->NxN also mean a bijection by the same reasoning.)
8. (Original post by alex2100x)
Got it thanks!!!!

I kept seeing these differing definitions popping up and I never really had that explained so cheers.

Question: if there is an injection from NxN--->N would there also be a bijection because eventually all n in N would be mapped to by some element of NxN?

What about the other way? (Does an injection N---->NxN also mean a bijection by the same reasoning.)
Well, there must be a bijection between NxN and N, but not for the reason you have given. See http://en.wikipedia.org/wiki/Schr%C3...nstein_theorem
9. (Original post by Drederick Tatum)
Well, there must be a bijection between NxN and N, but not for the reason you have given. See http://en.wikipedia.org/wiki/Schr%C3...nstein_theorem
okay thanks will take a read through that.
10. (Original post by Drederick Tatum)
Well, there must be a bijection between NxN and N, but not for the reason you have given. See http://en.wikipedia.org/wiki/Schr%C3...nstein_theorem
Although, the method you gave of finding an injection between NxN and N in the other thread (by sort of snaking through the elements of NxN) is indeed a surjection (and therefore a bijection).
11. (Original post by Drederick Tatum)
Countability is defined is one of two ways: people either say a set is countable if it has the same cardinality as the naturals (so this definition requires that we exhibit a bijection from our set to the naturals), or if it is 'no bigger' than the naturals (so this requires an injection from our set to the naturals).
Isn't this back to front? Surely to show that has the same cardinality as , we'd need to show that is "no bigger" than i.e. we need an injection *from* *to* .

As I pointed out above, there's an injection from to , but they don't have the same cardinality.
12. (Original post by atsruser)
Isn't this back to front?
No.

Surely to show that has the same cardinality as , we'd need to show that is "no bigger" than i.e. we need an injection *from* *to* .
No, to show that has the same cardinality as you'd need to show they are the same size.

As I pointed out above, there's an injection from to , but they don't have the same cardinality.
No, they don't. But the way I use the word (and also Drederick Tatum), countability isn't equivalent to cardinality.

To be totally clear, the two definitions he provided:

(1) "people either say a set is countable if it has the same cardinality as the naturals "

(2) ",,,or if it is 'no bigger' than the naturals"

are NOT equivalent and are not supposed to be equivalent. He and I both use definition (2). (If I want to express (1), I say "countably infinite").
13. (Original post by DFranklin)
No.
Right. I was misled by the fact that the OP talks mainly about cardinality, but the discussion changed to countability. I ignored that. (In fact, having reread the OP, I think that he's used the terms interchangeably himself).

BTW, as a matter of definition, do you distinguish between "a countable set" and "a countably infinite set"; would you consider a finite set to be "countably infinite" or merely "countable"? To me, those are different things.
14. (Original post by atsruser)
BTW, as a matter of definition, do you distinguish between "a countable set" and "a countably infinite set"; would you consider a finite set to be "countably infinite" or merely "countable"? To me, those are different things.
With my definitions:

All countably infinite sets are countable, but not all countable sets are infinite. Whether I distinguish between the two will depend on terms will depend on context, just like anything else. (e.g.. sometimes it will be important to know that rather than and sometimes it won't matter).

So sometimes I might describe as a countable set and sometimes a countably infinte set. Although to be honest, in this case and most others, it's so obvious the set is infinite that everyone will "know" that countable means "countably infinite" here.

On the other hand, I would never describe a finite set as countably infinite. That's just wrong.

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: January 8, 2015
Today on TSR

### Been caught plagiarising...

...for the 2nd time this year

### Mum says she'll curse me if I don't go to uni

Discussions on TSR

• Latest
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

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest

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