
Re: Problem with Cantor's diagonal argument
Posted:
Feb 14, 2002 1:44 PM


In article <a4gvml$7ud9$1@ID110648.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 AbuJamal decision falls short of justice.

