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: Matrices: If AB = I, then BA = I.
Replies: 52   Last Post: Apr 24, 1999 10:56 PM

 Messages: [ Previous | Next ]
 Bill Dubuque Posts: 156 Registered: 12/6/04
Re: The infinite hotel, shifts, 1-1 iff onto, pigeonhole principle
Posted: Apr 24, 1999 6:30 PM

The Hilbert Hotel is a classical popular realization of the first
infinite ordinal w. It's a nice example of the dichotomy between
the finite and the infinite: the right-shift operator n -> n+1
is 1-1 but not onto the infinite set w; contrast this with a
finite set, where a function is 1-1 if and only if it is onto
(the pigeonhole principle). The exact same contrast occurs between
finite and infinite dimensional vectors spaces and can again be
illustrated via shift operators, e.g. if V has infinite dimension

let R = (Right) shift operator: R(a b c d ...) = (0 a b c ...)
and L = (Left) shift operator: L(a b c d ...) = (b c d e ...)
so LR = I but RL != I since: RL(a b c d ...) = (0 b c d ...)

This has a simple model in a vector space V of polynomials. Let V
have basis {1, x, x^2 ...}, so (a b c ...) = a + b x + c x^2 + ...
with shift operators R p(x) = x p(x), L p(x) = 1/x (p(x)-p(0))
so that LR = I but RL != I since RL p(x) = p(x)-p(0). Note

L is onto but not 1-1, since L(Rp)=p but L(1)=0.

R is 1-1 but not onto; its image RV = xV is a proper

subspace isomorphic to V (since Im R ~= V/(Ker R) = V/0 = V);
note: dim V is infinite iff V is isomorphic to a proper subspace,
just as a set is infinite iff it's isomorphic to a proper subset.

In fact this equivalence between 1-1 and onto maps comes from
a general pigeonhole principle in lattices - in particular it
holds for any algebraic structure of finite height (in its
lattice of subalgebras) -- see my soon to appear post [1].

The shift operator is of fundamental importance in linear algebra,
e.g. see the review of Fuhrmann's book in my prior post [2].

The hotel is usually called "Hilbert's Hotel" - named after the great
mathematician David Hilbert, who often mentioned it in his popular
lectures; cf. Rucker: Infinity and the Mind p. 73, where it is also
mentioned that the Polish science fiction writer Stanislew Lem once
wrote a short story about Hilbert's Hotel, which appears in Vilenkin's
book Stories About Sets. Rudy Rucker's book is one of the best popular
expositions of most all aspects of infinity - highly recommended [3] [4].

-Bill Dubuque

[1] http://www.dejanews.com/dnquery.xp?QRY=dubuque%20fuhrmann%20holder&groups=sci.math&ST=PS
[2] http://www.dejanews.com/dnquery.xp?QRY=dubuque%20fuhrmann&groups=sci.math&ST=PS
[3] http://www.dejanews.com/getdoc.xp?AN=437551805
[4] http://www.dejanews.com/dnquery.xp?QRY=dubuque%20rucker&groups=sci.math%2A%20sci.logic&ST=PS

Date Subject Author
3/13/99 JRic395488
3/14/99 Chan-Ho
3/14/99 John Creighton
3/14/99 David C. Ullrich
3/14/99 David C. Ullrich
3/15/99 Horst Kraemer
3/14/99 Hope Hubris
3/14/99 JRic395488
3/17/99 David Kastrup
3/15/99 bobs@rsa.com
3/15/99 Ake Brannstrom
3/16/99 Paul Hammond
3/16/99 Mike ROBSON
3/15/99 Christian Ohn
3/15/99 David C. Ullrich
3/16/99 Christian Ohn
3/18/99 David C. Ullrich
3/18/99 Christian Ohn
3/19/99 David C. Ullrich
3/18/99 Zdislav V. Kovarik
3/19/99 David C. Ullrich
3/20/99 David C. Ullrich
3/17/99 D. J. Bernstein
3/17/99 JRic395488
3/19/99 David C. Ullrich
3/18/99 David C. Ullrich
3/19/99 David C. Ullrich
3/15/99 bobs@rsa.com
3/15/99 David Kastrup
3/15/99 David C. Ullrich
3/16/99 bobs@rsa.com
3/15/99 Richard Carr
3/15/99 David C. Ullrich
3/15/99 Lee Rudolph
3/16/99 David C. Ullrich
3/16/99 Timothy Murphy
3/17/99 John Harper
3/16/99 Keith Ramsay
3/18/99 D. J. Bernstein
3/19/99 Charles H. Giffen
3/15/99 JRic395488
3/15/99 Doug Norris