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: Equivalency of Infinite Sets
Replies: 433   Last Post: Jun 18, 1999 10:39 PM

 Messages: [ Previous | Next ]
 Bill Dubuque Posts: 156 Registered: 12/6/04
Re: Equivalency of Infinite Sets
Posted: Apr 27, 1999 4:17 AM

The essence of the Cantor diagonal argument is quite simple, namely:

Given a square matrix F one may construct a row-vector different from
those in F by simply taking the diagonal of F and changing each element.

In detail: suppose matrix F(i,j) has entries from a set B with two or
more elements (so there is a "change" map ~ on B: ~b differs from b).
Let ~F(i,i) denote the "changed diagonal" of F, i.e. the row-vector
obtained by applying ~ to each element of the diagonal F(i,i) of F.
The changed diagonal of F differs from each row-vector of F because
it differs on diagonal elements: the i'th row-vector f_i of F has
i'th entry = F(i,i) versus ~F(i,i) = i'th entry of changed diagonal:

[ f1(1) f1(2) f1(3) . . . ] row i = f_i(j) maps A to B
| |
| f2(1) f2(2) f2(3) |
| | --> [~f1(1) ~f2(2) ~f3(3) ... ]
| f3(1) f3(2) f3(3) |
| . . | = "changed diagonal" of F
| . . |
[ . . ] where ~x differs from x

Notice that the above proof required no hypotheses on the index
set of the rows and columns of F. Although classically one thinks
of a square matrix as indexed by a finite ordered set {1 2 ... n},
in fact the above proof holds for any abstract index set A; then
the rows are simply functions f(j) from A to B, and the matrix F
is just a set of such row-functions {f_i(j)}, indexed by i in A.
This matrix viewpoint is adopted in the proof given below that
nontrivial exponentiation B^A increases the cardinality |A| of A.

THEOREM Let A, B be sets, and B^A = set of functions from A to B.
If |B| > 1 then |B^A| > |A|, i.e. B^A has more than |A| functions.

Proof: Given |A| functions f_i : A -> B, construct the |A| x |A|
"matrix" F(i,j) = f_i(j). The proof presented above shows that
the changed diagonal function ~F(i,i) differs from the given |A|
functions (= row-vectors of F); hence |B^A| > |A| when |B| > 1.

In particular, for B = 2 = {0 1} the theorem implies |2^A| > |A|,
i.e. the cardinality of the powerset of A exceeds that of A; here
we've employed the well-known fact that the powerset of A is the
same as 2^A (subsets S of A are in 1-1 correspondence with functions
f : A -> 2 via: i in S <=> f(i) = 1; in other words consider f
as the characteristic function (bit-vector) for the subset S of A).
A close examination of the classical proof [1] will show that it
is essentially identical to the above "matrix-theoretic" proof.

By the way, it's a historical mistake that the diagonal construct
is attributed to Cantor. In fact it dates to at least 1871 when
du Bois-Reymond diagonalized on the growth rates of functions in
his pioneering studies on "orders of infinity" (see my prior post
[2]); in fact such a diagonalization on growth rates is a simple
way of proving that Ackermann function is not primitive recursive
(this problem was not considered until almost 60 years later [3]).

-Bill Dubuque

[1] http://www.dejanews.com/getdoc.xp?AN=470526822
[2] http://www.dejanews.com/getdoc.xp?AN=255882969
[3] http://www.dejanews.com/getdoc.xp?AN=271857318

Date Subject Author
4/21/99 Ross Finlayson
4/22/99 hcd@andrew.cmu.edu
4/22/99 Zdislav V. Kovarik
4/22/99 Hope Hubris
4/22/99 Ross Finlayson
4/22/99 Brian M. Scott
4/22/99 Ross Finlayson
4/22/99 Mike Oliver
4/22/99 Ross Finlayson
4/22/99 Mike Oliver
4/22/99 Ross Finlayson
4/24/99 standebj@SLU.EDU
4/23/99 Dave Seaman
4/23/99 Nathaniel Deeth
4/24/99 Andrew Martin
4/26/99 Ken Cox
4/27/99 David Kastrup
4/27/99 Torkel Franzen
4/27/99 Ken Cox
4/24/99 Brian David Rothbach
4/26/99 Ken Cox
4/28/99 Nathaniel Deeth
4/28/99 Ken Cox
4/28/99 Virgil Hancher
4/28/99 Ken Cox
4/28/99 Mike Oliver
4/30/99 Nathaniel Deeth
4/30/99 Doug Norris
4/30/99 Ken Cox
4/28/99 Nathaniel Deeth
4/28/99 Ken Cox
4/28/99 hale@mailhost.tcs.tulane.edu
4/30/99 Nathaniel Deeth
4/29/99 David Kastrup
4/28/99 Zdislav V. Kovarik
4/28/99 Brian David Rothbach
4/23/99 Ross Finlayson
4/23/99 Dave Seaman
4/23/99 Ross Finlayson
4/23/99 Dave Seaman
4/23/99 Ross Finlayson
4/24/99 Dave Seaman
4/24/99 Ross Finlayson
4/24/99 Dave Seaman
4/24/99 Ross Finlayson
4/24/99 Brian M. Scott
4/24/99 Ross Finlayson
4/24/99 Ross Finlayson
4/25/99 Brian M. Scott
4/25/99 Ross Finlayson
4/25/99 Brian M. Scott
4/25/99 Mike Oliver
4/25/99 Brian M. Scott
4/25/99 Mike Oliver
4/25/99 Brian M. Scott
4/25/99 Mike Oliver
4/25/99 Richard Carr
4/26/99 Brian M. Scott
4/25/99 Ross Finlayson
4/25/99 Ross Finlayson
4/25/99 Ross Finlayson
4/25/99 Brian M. Scott
4/25/99 Ross Finlayson
4/25/99 Brian M. Scott
4/25/99 Brian M. Scott
4/25/99 Ross Finlayson
4/25/99 Brian M. Scott
4/25/99 Brian M. Scott
4/25/99 Russell Easterly
4/25/99 Thomas Womack
4/25/99 Dave Seaman
4/25/99 David C. Ullrich
4/25/99 Brian M. Scott
4/24/99 Brian M. Scott
4/26/99 Michel Hack
4/26/99 Brian M. Scott
4/26/99 Ross Finlayson
4/26/99 Brian M. Scott
4/26/99 Ross Finlayson
4/26/99 Domnei
4/26/99 Ross Finlayson
4/27/99 Brian David Rothbach
4/27/99 Brian M. Scott
4/27/99 Ross Finlayson
4/27/99 Domnei
4/27/99 Jake Wildstrom
4/27/99 Ross Finlayson
4/28/99 Jake Wildstrom
4/28/99 Ross Finlayson
4/29/99 Ross Finlayson
4/29/99 Brian M. Scott
4/29/99 Ross Finlayson
4/29/99 Dave Seaman
4/29/99 Ross Finlayson
4/29/99 Dave Seaman
4/29/99 Ross Finlayson
4/29/99 Brian M. Scott
4/29/99 Ross Finlayson
4/30/99 Dave Seaman
4/30/99 Ross Finlayson
4/30/99 Nobody
4/30/99 Brian M. Scott
5/1/99 Brian David Rothbach
5/1/99 Dave Seaman
5/1/99 Dave Seaman
5/1/99 Ross Finlayson
5/1/99 Steve Leibel
5/1/99 Ross Finlayson
5/1/99 Steve Leibel
5/1/99 Ross Finlayson
5/1/99 Ross Finlayson
5/1/99 Brian M. Scott
5/2/99 Ross Finlayson
5/2/99 Brian M. Scott
5/2/99 Ross Finlayson
5/2/99 Jake Wildstrom
5/2/99 Ross Finlayson
5/3/99 Jake Wildstrom
5/3/99 Ross Finlayson
5/3/99 Ross Finlayson
5/3/99 Jake Wildstrom
5/3/99 Nobody
5/4/99 Doug Norris
5/4/99 Ross Finlayson
5/4/99 Doug Norris
5/3/99 Brian M. Scott
5/3/99 Ross Finlayson
5/3/99 Brian M. Scott
5/3/99 Richard Carr
5/2/99 Steve Leibel
5/2/99 Ross Finlayson
5/3/99 Steve Leibel
5/1/99 Brian David Rothbach
5/3/99 Nobody
5/3/99 Ross Finlayson
5/3/99 Nobody
5/4/99 Ross Finlayson
5/4/99 Brian M. Scott
5/4/99 Nobody
5/3/99 Ken Cox
5/3/99 Nobody
5/3/99 Ross Finlayson
5/3/99 Steve Leibel
5/4/99 Ross Finlayson
5/4/99 Steve Leibel
5/4/99 Ross Finlayson
5/4/99 Richard Carr
5/4/99 Ross Finlayson
5/4/99 Brian M. Scott
5/4/99 Ross Finlayson
5/4/99 Alan Morgan
5/4/99 Ross Finlayson
5/4/99 Ross Finlayson
5/4/99 Ken Cox
5/5/99 Brian M. Scott
5/5/99 David C. Ullrich
5/4/99 Nobody
5/4/99 Ross Finlayson
5/4/99 Alan Morgan
5/4/99 Nobody
5/4/99 Ross Finlayson
5/5/99 Jake Wildstrom
5/5/99 Ross Finlayson
5/5/99 standebj@SLU.EDU
5/5/99 Ross Finlayson
5/5/99 Dave Seaman
5/5/99 Steve Leibel
5/5/99 Ross Finlayson
5/5/99 Ken Cox
5/5/99 Ross Finlayson
5/5/99 Alan Morgan
5/5/99 Ken Cox
5/5/99 Dave Seaman
5/5/99 Ken Cox
5/5/99 Ross Finlayson
5/5/99 Ken Cox
5/5/99 Ross Finlayson
5/5/99 Ken Cox
5/5/99 Ross Finlayson
5/6/99 edew@netcom.com
5/6/99 Ken Cox
5/5/99 Nobody
5/5/99 Ross Finlayson
5/6/99 Steve Leibel
5/6/99 Ross Finlayson
5/6/99 Jake Wildstrom
5/6/99 Ross Finlayson
5/6/99 Steve Leibel
5/6/99 Ross Finlayson
5/6/99 Ken Cox
5/6/99 edew@netcom.com
5/6/99 Ross Finlayson
5/7/99 Nobody
5/6/99 Brian David Rothbach
5/6/99 Ross Finlayson
5/6/99 edew@netcom.com
5/7/99 Ross Finlayson
5/7/99 Nobody
5/7/99 Ross Finlayson
5/7/99 Ken Cox
5/7/99 Domnei
5/7/99 Ross Finlayson
5/8/99 Brian David Rothbach
5/9/99 Ross Finlayson
5/9/99 Brian M. Scott
5/9/99 Ross Finlayson
5/9/99 Domnei
5/9/99 Ross Finlayson
5/9/99 Brian M. Scott
5/10/99 Zdislav V. Kovarik
5/10/99 Brian M. Scott
5/10/99 Dave Seaman
5/10/99 Brian M. Scott
5/12/99 Nathaniel Deeth
5/13/99 Lau Lap Ming, Alvin
5/13/99 Zdislav V. Kovarik
5/12/99 Nathaniel Deeth
5/12/99 Dave Seaman
5/12/99 Alan Morgan
5/12/99 Ross Finlayson
5/12/99 Ross A. Finlayson
5/10/99 edew@netcom.com
5/10/99 Ross Finlayson
5/10/99 Brian David Rothbach
5/10/99 Ross Finlayson
5/10/99 Brian M. Scott
5/10/99 Ross Finlayson
5/10/99 Brian M. Scott
5/11/99 Ross Finlayson
5/11/99 Brian M. Scott
5/11/99 edew@netcom.com
5/11/99 Ross Finlayson
5/11/99 Brian M. Scott
5/11/99 Ross Finlayson
5/11/99 edew@netcom.com
5/11/99 Ross Finlayson
5/11/99 Dave Seaman
5/11/99 Brian M. Scott
5/11/99 Ross Finlayson
5/12/99 Brian M. Scott
5/12/99 Ross Finlayson
5/12/99 Brian M. Scott
5/12/99 Ken Cox
5/11/99 edew@netcom.com
5/15/99 Doug Norris
5/11/99 edew@netcom.com
5/11/99 Ken Cox
5/11/99 edew@netcom.com
5/8/99 edew@netcom.com
5/8/99 Doug Norris
5/6/99 David C. Ullrich
5/5/99 Nobody
5/5/99 Jake Wildstrom
5/5/99 Ross Finlayson
5/12/99 Ross A. Finlayson
5/13/99 Brian David Rothbach
5/13/99 Ken Cox
5/14/99 Steve Leibel
5/16/99 Jonathan W. Hoyle
5/17/99 Mike Mccarty Sr
5/17/99 Ross A. Finlayson
5/18/99 Brian M. Scott
5/18/99 Ken Cox
5/18/99 Ross A. Finlayson
5/19/99 LEBLANC ERIC
5/19/99 Brian M. Scott
5/19/99 Ross A. Finlayson
5/20/99 Nobody
5/20/99 Mike Mccarty Sr
5/19/99 Dave Seaman
5/19/99 Ross A. Finlayson
5/19/99 Doug Norris
5/19/99 Ken Cox
5/20/99 Ross A. Finlayson
5/20/99 Doug Norris
5/20/99 Ross A. Finlayson
5/20/99 Doug Norris
5/20/99 Ross A. Finlayson
5/21/99 LEBLANC ERIC
5/22/99 Ross A. Finlayson
5/20/99 Nobody
5/22/99 Ross A. Finlayson
5/22/99 edew@netcom.com
5/20/99 David Seaman
5/20/99 Ross A. Finlayson
5/20/99 Dave Seaman
5/19/99 Ken Cox
5/19/99 Ross A. Finlayson
5/19/99 Ken Cox
5/19/99 Doug Norris
5/20/99 Ross A. Finlayson
5/20/99 Richard Carr
5/20/99 Ken Cox
5/20/99 Ross A. Finlayson
5/20/99 Ken Cox
5/22/99 Ross A. Finlayson
5/22/99 b_m_scott@my-dejanews.com
5/24/99 Ken Cox
5/24/99 Brian M. Scott
5/24/99 Ken Cox
5/21/99 Zdislav V. Kovarik
5/21/99 Steve Leibel
5/22/99 Ross A. Finlayson
5/20/99 Nobody
5/20/99 Ross A. Finlayson
5/20/99 Doug Norris
5/21/99 David C. Ullrich
5/19/99 Nobody
5/18/99 Michel Hack
5/18/99 Ray Vickson
5/19/99 Nathaniel Deeth
5/19/99 Zdislav V. Kovarik
5/20/99 Michel Hack
5/18/99 Doug Norris
5/18/99 Ross A. Finlayson
5/19/99 LEBLANC ERIC
5/19/99 Nobody
5/19/99 Brian M. Scott
5/18/99 Nobody
5/29/99 Ross Finlayson
5/30/99 LEBLANC ERIC
6/1/99 Ross Finlayson
6/1/99 LEBLANC ERIC
6/1/99 Ross Finlayson
6/1/99 Doug Norris
6/3/99 Ross Finlayson
6/3/99 Erik Max Francis
6/1/99 Ken Cox
6/1/99 Zdislav V. Kovarik
6/2/99 Ross Finlayson
6/2/99 Dave Seaman
6/2/99 Ken Cox
6/2/99 Brian M. Scott
6/3/99 Zdislav V. Kovarik
6/3/99 Ross Finlayson
6/3/99 Brian M. Scott
6/5/99 Ross Finlayson
6/5/99 Brian M. Scott
6/6/99 Ross Finlayson
6/6/99 Pertti Lounesto
6/6/99 Ross Finlayson
6/6/99 Zdislav V. Kovarik
6/6/99 Ross Finlayson
6/7/99 briggs@eisner.decus.org
6/7/99 Nico Benschop
6/11/99 Ross Finlayson
6/6/99 Lee Rudolph
6/6/99 Pertti Lounesto
6/6/99 Dave Seaman
6/7/99 John R Ramsden
6/7/99 Ken Cox
6/3/99 Brian M. Scott
6/13/99 Ross Finlayson
6/13/99 Steve Leibel
6/14/99 Zdislav V. Kovarik
6/14/99 Pertti Lounesto
6/14/99 Ross Finlayson
6/14/99 Alan Morgan
6/14/99 Ross Finlayson
6/14/99 Jake Wildstrom
6/14/99 Ross Finlayson
6/14/99 Brooks Moses
6/15/99 Steve Lord
6/15/99 Mike Oliver
6/16/99 Ross Finlayson
6/16/99 randy
6/16/99 Nobody
6/17/99 Steve Leibel
6/18/99 Ross Finlayson
6/18/99 Dik T. Winter
6/18/99 Lee Rudolph
6/18/99 Dik T. Winter
6/18/99 Dave Seaman
6/18/99 David Petry
6/18/99 Dave Seaman
6/18/99 Dan Schmidt
6/18/99 Ken Cox
6/18/99 Zdislav V. Kovarik
6/18/99 Ross Finlayson
6/18/99 randy
6/18/99 Steve Leibel
6/18/99 Nobody
6/18/99 Jake Wildstrom
6/18/99 Nobody
6/18/99 Jeremy Boden
5/5/99 Nobody
5/5/99 Doug Norris
5/4/99 Steve Leibel
5/4/99 Nobody
6/6/99 Jeremy Boden
6/8/99 David Redmond
5/3/99 Nobody
4/30/99 Dave Seaman
4/30/99 Ross Finlayson
4/29/99 Steve Leibel
4/29/99 Brian M. Scott
4/30/99 Virgil Hancher
4/30/99 Ross Finlayson
4/30/99 Brian M. Scott
4/26/99 Dave Seaman
4/26/99 Jake Wildstrom
4/26/99 Virgil Hancher
4/26/99 Jeremy Boden
4/26/99 Jeremy Boden
4/26/99 Mike Oliver
4/27/99 Bill Dubuque
4/24/99 Russell Easterly
4/24/99 Dave Seaman
4/24/99 Brian M. Scott
4/24/99 Tapio Hurme
4/26/99 Ken Cox
4/24/99 Zdislav V. Kovarik
4/27/99 Jeremy Boden
4/27/99 Richard Carr
5/6/99 Jeroen Bruijning
4/23/99 Jeremy Boden
4/23/99 hcd@andrew.cmu.edu
4/23/99 Dave Seaman
4/23/99 Richard Carr
4/24/99 Dave Seaman
4/24/99 Richard Carr
4/24/99 standebj@SLU.EDU
4/23/99 Richard Carr
4/23/99 hcd@andrew.cmu.edu
4/23/99 Ross Finlayson
4/23/99 Domnei
4/24/99 Ross Finlayson
4/24/99 Richard Carr
4/24/99 Ross Finlayson
4/24/99 Dave Seaman
4/24/99 Ross Finlayson
4/24/99 Mike Oliver
4/25/99 Dave Seaman
4/24/99 hcd@andrew.cmu.edu