# denumerable vs uncountable

• December 13th 2008, 03:32 PM
mathcnc
denumerable vs uncountable
why is the set of all integer powers of 2 {2^x|x is in z} is denumerable

Then why is the set of all prime numbers denumeralbe
and explain why the number of points on a circle is denumerable or uncountable
• December 13th 2008, 03:39 PM
Jhevon
Quote:

Originally Posted by mathcnc
why is the set of all integer powers of 2 {2^x|x is in z} is denumerable

we can find a bijective function from the naturals to the set. so it has the same cardinality as the naturals.

or better yet, since the integers are denumerable, it suffices to find a bijection from the integers to the set, which would be a bit easier to describe. the desired result follows by transitivity

Quote:

Then why is the set of all prime numbers denumeralbe
you can list and enumerate them using the natural numbers. since there are an infinite number of primes, it follows the set is denumerable.

Quote:

and explain why the number of points on a circle is denumerable or uncountable
you can think of a circle as a section of the real line bent into a circle, right? is a segment of the real line denumerable or uncountable?
• December 23rd 2008, 06:02 PM
HallsofIvy
Quote:

Originally Posted by mathcnc
why is the set of all integer powers of 2 {2^x|x is in z} is denumerable

There exist the obvious mapping x->2^x and there is a well known mapping from N to Z: f(n)= n/2 if n is even, -(n+1)/2 if n is odd.

Quote:

Then why is the set of all prime numbers denumeralbe
The set of prime numbers is infinite and a subset of N.

Quote:

and explain why the number of points on a circle is denumerable or uncountable
Denumerable or UNCOUNTABLE? That's like asking you to explain why every integer must be either even or odd! It has to be one or the other. (In fact, since the function $f(x)= (R cos(2\pi x), R sin(2\pi x))$ maps the interval [0, 1) onto the circle with radius R, it is easy to prove that it is uncountable.