Countable and uncountable sets

HOME

Math Central

Quandaries & Queries

Question from Mac, a student:

Hi, i tried to read few webpages related to the countably infinite and uncountable sets.
Even i read few questions from this forum.

But i am not convinced with this explanation. If you have any good book that
explains this in layman term, please redirect me to that.

1) Can you please explain what is the difference between these too ?
2) How could you say set of Natural number and set of even numbers are countably infinite ?
N={1,2,3,...} and Even= {2,4,6,...}
When an element in the even set is some 2n, we will map it to 'n'.So now we have a bigger number(2n) right ?
Sorry, i didn't understand that.
3) So whatever the set , do we try to map it with the Natural Number (N) ?
4) In some places, it says map it to the nature number and in some places it says, subset of natural number, can you please explain more on that ?
5) I didn't understand the explanation over here in this link,
http://www.cs.xu.edu/csci250/06s/Theorems/powerSetuncountable.pdf
Initially we are assuming 2^N is countably infinite and we are taking the subset of N (Is it all subsets..ie power set ?). Then we are defining a set A that has members other than any A(i). When we take the set of N, this set A
also should be part of that right ?

confusing subject !! spent hours today but still i didn't understand the concept.

Can you please help me out to understand that ?

Thanks
mac

Hi Mac,

The concepts of countable and uncountable can be confusing and counterintuitive. The concept most mathematicians use to distinguish the size of infinite sets comes from Georg Cantor. I want to start with an example:

Suppose you are organizing a meeting in some hall and you have put out chairs for the people sit on. Quite a few people have arrived and you wonder if you need to get more chairs. One way to determine this without counting the chairs and people is to ask everyone to sit down. If everyone sits down and there are chairs left then there are more chairs then people. If all the chairs are occupied and some people are left standing there are more people then chairs. If everyone is seated and there are no unoccupied chairs then there are the same number of chairs as people.

The idea here is that you match chairs with people. Mathematicians call this a one to one correspondence and it is used to compare the size of sets. The word we use for size is cardinality.

Definition:

Let A and B be sets. If there is a one to one correspondence from A into B we say the cardinality of A is less than or equal to the cardinality of B. If there is a one to one correspondence from A onto B we say that the cardinality of A is equal to the cardinality of B.

Before getting to your questions I want to state the Cantor–Bernstein–Schroeder theorem

If the cardinality of A is less than or equal to the cardinality of B and the cardinality of B is less than or equal to the cardinality of A then the cardinality of A is equal to the cardinality of B.

Definitions:

A set A is finite if it is empty or its cardinality is the cardinality of {1, 2, ···, n} for some natural number n.

A set A is countably infinite if its cardinality is equal to the cardinality of the natural numbers N.

A set is uncountable if it is infinite and not countably infinite.

N = {1, 2, ···, } and Even = {2, 4, ···, 6} have the same cardinality because there is one to one correspondence from N onto Even. The correspondence, as you stated is n ⇒2n.

Two other useful results involving cardinality are:

If A and B have the same cardinality and B and C have the same cardinality then A and C have the same cardinality.

If A is a subset of B then the cardinality of A is less than or equal to the cardinality of B.

These two results might explain what you are asking in 4.

After you have read this look again at http://www.cs.xu.edu/csci250/06s/Theorems/powerSetuncountable.pdf

If you still have a question then write back.

Harley

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.