[EM] 1-Person-1-Vote has been abandoned.

Forest Simmons fsimmons at pcc.edu
Wed Jan 15 12:58:28 PST 2003

Actually, Cantor proved that there are infinitely many distinct infinities
on the same day he proved that the cardinality of the reals is greater
than the cardinality of the rationals.

Here's the proof in modern notation:

Let X be any set (finite or infinite, it doesn't matter).  Let P(X) be the
power set of X, i.e. the collection of all subsets of X.

Then while there is a one-to-one function from X into P(X), there is no
function from X onto P(X).

In other words, the cardinality of P(X) is strictly greater than the
cardinality of X.

Let N be the set of natural numbers and (for any set A) let #A represent
the cardinality of A.

Then #N < #P(N) < #P(P(N)) < #P(P(P(N))), etc.


An example of a one-to-one function from X into P(X) is the function given
by f(x)={x}, i.e. the image of any member of X is the singleton subset for
which it is the only member.

To show that no function maps X onto P(X), suppose to the contrary that g
is such a function.

Then let Y be the member of P(X) defined by

{ x | x is not a member of g(x)}.

Since Y is a member of P(X), and g maps X onto P(X), there must be some
member x of X such that g(x)=Y.

Note that according to the definition of Y, this x is an element of Y if
and only if it is not an element of Y.

This contradiction shows the non-existence of any such map g.

This is the famous diagonal argument of Cantor slightly disguised.

Note that the points of the middle thirds Cantor set are in one to one
correspondence with the base three "decimal" expansions that have no
occurrence of the digit 1 .

These expansions are, in one to one correspondence with subsets of N.

For example x=.20020222202... corresponds to the subset

 h(x)={1,4,6,7,8,9,11,...}.  In general

h(x)={ n | the n_th  digit of x is a two (in the base three expansion)}.

So the Cantor set, which is a subset of the reals has the same cardinality
as the power set of the natural numbers.

Another of Cantor's ingenious arguments showed that the Naturals have the
same cardinality as the Rationals.

He was unable to answer the question of whether there might be other
cardinalities between those of the Naturals and the Reals.

Godel constructed a model of set theory in which there is no such

Later Cohen constructed a model in which there are infinitely many such

So just as there are both Euclidean and non-Euclidean geometries, there
are Cantorian and Non-Cantorian set theories.

In other words, the "Continuum Hypothesis" is just as logically
independent of the other basic axioms of set theory as the parallel
postulate is independent from the other axioms of geometry.


On Wed, 15 Jan 2003, Eric Gorr wrote:

> I am assuming that no one has discovered another level of infinity.

For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em

More information about the Election-Methods mailing list