Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Problem with Cantor's diagonal argument
Replies: 65   Last Post: Mar 4, 2002 1:36 PM

 Messages: [ Previous | Next ]
 Dave Seaman Posts: 555 Registered: 12/6/04
Re: Problem with Cantor's diagonal argument
Posted: Feb 14, 2002 1:44 PM

In article <a4gvml\$7ud9\$1@ID-110648.news.dfncis.de>,
Herman Jurjus <h.jurjus@hetnet.nl> wrote:

>"Dave Seaman" <dseaman@seaman.cc.purdue.edu> wrote in message
>news://a4gf7t\$2or@seaman.cc.purdue.edu...

>> We don't have to create the list. The list is given to us in the
>> hypothesis of the theorem. In geometry, we accept that infinitely long
>> lines exist, even though we can never finish drawing them. In analysis,
>> we accept that real numbers exist, even though we can never finish
>> writing them down.

>OK. But aren't there people outthere who can imagine 'potentially' infinite
>sets, but not 'actual' infinite sets?
>To those people, would Cantor's argument make sense?

There is more than one Cantor argument. The one that seems most
appropriate here is the power set version. Given any set X, the power
set of X, P(X), is the set of all subsets of X. A version of Cantor's
theorem says that if X is any set at all (finite or infinite), then |X| <
|P(X)|.

Proof: There is an obvious injection f: X -> P(X) given by x |-> {x}.
This establishes that |X| <= |P(X)|. In order to show that the
cardinalities are not equal, we need to show that no mapping f: X -> P(X)
is a surjection. That is, given f: X -> P(X), we need to find a member S
of P(X) (depending on f) such that S is not in the range of f.

Let S = { x in X : not(x in f(x)) }. It follows from this definition
that for every x in X, x belongs to S <==> x does not belong to f(x).
Therefore, S differs from f(x) for every x in X, which is what it means
to say S is not in the range of f.

Corollary. The powerset of the natural numbers, P(N), is uncountable.

Now, you can deny that infinite sets exist if you like, but you can't
deny that Cantor's proof applies to all sets that exist. You can deny
that there is a set N if you like, but you can't deny that *if* there is
a set N, then the set P(N) is larger than N.

--
Dave Seaman dseaman@purdue.edu
Amnesty International says Mumia Abu-Jamal decision falls short of justice.

Date Subject Author
2/13/02 Henry
2/13/02 Andy Berget
2/14/02 Mike Oliver
2/14/02 Doug Norris
2/14/02 Keith Keller
2/14/02 Dudley Brooks
2/14/02 Mike Oliver
2/14/02 Dudley Brooks
2/14/02 Dave Seaman
2/14/02 Dudley Brooks
2/14/02 Dave Seaman
2/14/02 Dudley Brooks
2/14/02 Bob Kolker
2/14/02 Dave Seaman
2/14/02 Seth Dutter
2/14/02 mareg@mimosa.csv.warwick.ac.uk
2/14/02 Nico Benschop
2/14/02 mareg@mimosa.csv.warwick.ac.uk
2/14/02 Willondon
2/14/02 Henry
2/14/02 magidin@math.berkeley.edu
2/15/02 Doug Magnoli
2/14/02 mareg@mimosa.csv.warwick.ac.uk
2/14/02 Dudley Brooks
2/14/02 Nico Benschop
2/15/02 Nico Benschop
2/15/02 Nico Benschop
2/15/02 Nico Benschop
2/14/02 Dave Seaman
2/14/02 Herman Jurjus
2/14/02 Dave Seaman
2/15/02 Jon and Mary Frances Miller
2/15/02 Torkel Franzen
2/15/02 Virgil
2/15/02 Harlan Messinger
2/15/02 Virgil
2/15/02 Harlan Messinger
2/15/02 Virgil
2/18/02 Harlan Messinger
2/18/02 Virgil
2/19/02 Harlan Messinger
2/19/02 Virgil
2/19/02 Dudley Brooks
3/4/02 Alexey Dejneka
3/4/02 Torkel Franzen
3/4/02 Alan Stern
2/16/02 Chip Eastham
2/20/02 SRK
2/14/02 Dale Hurliman
2/14/02 Randy Poe
2/14/02 Henry
2/14/02 Randy Poe
2/14/02 nospam@auerbachatunity.ncsu.edu
2/14/02 Dudley Brooks
2/15/02 Chris Menzel
2/15/02 Dudley Brooks
2/14/02 Phil Carmody
2/14/02 Harlan Messinger
2/14/02 Jim Heckman
2/15/02 Randy Poe
2/15/02 LarryLard
2/18/02 Harlan Messinger
2/14/02 George Greene
2/15/02 Duran Castore
2/18/02 Jonathan Hoyle