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