
Re: Cardinalities
Posted:
Jun 7, 2000 3:23 PM


In article <393E4DD2.D4A141D4@gmx.de>, Sebastian Holzmann <SHolzmann@gmx.de> wrote:
> Robin Chapman wrote: > > Dafydd y garreg wen <mavnw@csv.warwick.ac.uk> wrote: > > > What is the cardinality of the power set of N? Is it the same as the > > > cardinality of R? > > > > Yes. > > This answer is incorrect. This statement is an incarnation of the famous > "continuum hypothesis". It is proven to be independent of the standard > axioms of set theory. So we cannot prove it true or false using them. >
That's a common misconception. It's easy to prove that card(P(N)) = card(R) as follows
Given any subset S of N, consider the sequence of 0's and 1's whose nth term is
1 if n is an element of S, and
0 if n is not an element of S.
Putting a radix point to the left of the sequence gives the binary expression of some real between 0 and 1.
Conversely, given a real between 0 and 1, write down its binary expansion, which looks like .0011101010101 . . . say, and define S to be the subset of N consisting of those n for which the nth term of the binary expansion is 1.
I've just demonstrated a bijection between the set of reals between 0 and 1, and the power set of N.
The continuum hypothesis asks whether there is a set of reals whose cardinality is strictly between that of N and R.
Steve L

