From: Bill Dubuque
Subject: Re: The infinite hotel, shifts, 1-1 iff onto, pigeonhole principle
Date: 24 Apr 1999 18:30:51 -0400
Newsgroups: sci.math
Keywords: Hilbert Hotel
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