the transfinite subway
Scott Huddleston
as follows: there is a station at each ordinal number, and every station is
assigned a unique ordinal. The subway stops at each station, in order.
At each station people disembark and board, in order, as follows:
i). if any passengers are on the subway, exactly 1 disembarks, then
ii). aleph_0 passengers board the subway.
Station 0 is at the airport, and the Hilbert hotel is at station
w_1 (the first uncountable cardinal). The subway starts its journey
empty. Aleph_0 passengers board the subway to the Hilbert hotel at the
airport (station 0), and off it goes.
The puzzle: when the subway pulls up to the Hilbert hotel at station w_1,
how many passengers are on it? Is it 0, aleph_1, some determinate value in
between, or indeterminate?
--
Scott Huddleston
sc...@crl.labs.tek.com
Stephen Montgomery-Smith
I hope this wasn't meant to be a philisophical question, or I will
be flamed very badly.
After station 0, there will always be an infinite number of people
on the subway. Therefore, the one passenger disembarking makes no
difference. Hence we will have added aleph_0 passengers aleph_1 times,
and hence the total number of passengers on the subway at the end is
aleph_1.
Stephen Montgomery-Smith mathsms@umcvmb
ste...@mont.cs.missouri.edu
David Seal
Huddleston) writes:
Is the train *ever* going to pull up at the Hilbert hotel??? (half :-)
All the usual tricks for making infinite sequences of events take finite
time (e.g. let event N happen at time 1-1/N) seem to be totally defeated by
trying to go as far as w_1.
Possibly another important question is: how is the passenger who is going to
get off selected? This will define an ordering of the aleph_0 passengers,
and thus an ordinal number. But this ordinal number can be any ordinal with
cardinality aleph_0, and the exact choice of this ordinal makes a difference
to what happens at stations prior to w_1.
Whether it makes any difference to what happens at station w_1 I don't know.
My *guess* is that the answer is that nothing ever happens at station w_1,
regardless of the ordering of the passengers...
David Seal
ds...@armltd.co.uk
All opinions are mine only...
Herman Rubin
>In <22...@crl.LABS.TEK.COM> sc...@ferrari.LABS.TEK.COM (Scott Huddleston) writes:
|There is a subway line from the airport to the Hilbert hotel which operates
|as follows: there is a station at each ordinal number, and every station is
|assigned a unique ordinal. The subway stops at each station, in order.
|At each station people disembark and board, in order, as follows:
|i). if any passengers are on the subway, exactly 1 disembarks, then
|ii). aleph_0 passengers board the subway.
|Station 0 is at the airport, and the Hilbert hotel is at station
|w_1 (the first uncountable cardinal). The subway starts its journey
|empty. Aleph_0 passengers board the subway to the Hilbert hotel at the
|airport (station 0), and off it goes.
|The puzzle: when the subway pulls up to the Hilbert hotel at station w_1,
|how many passengers are on it? Is it 0, aleph_1, some determinate value in
|between, or indeterminate?
>I hope this wasn't meant to be a philisophical question, or I will
>be flamed very badly.
>After station 0, there will always be an infinite number of people
>on the subway. Therefore, the one passenger disembarking makes no
>difference. Hence we will have added aleph_0 passengers aleph_1 times,
>and hence the total number of passengers on the subway at the end is
>aleph_1.
This is another one of the same as before. It is possible to say a
little about the number of passengers at some of the stations. At
each station numbered a+1, the number of passengers on board is aleph_0.
At limit ordinals, however, it can be anything with a few restrictions;
the number at a limit of limit ordinals is at most the lower limit of
the numbers at those ordinals, but can be anything less, if that limit
is non-0.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hru...@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!hrubin(UUCP)
Stephen Montgomery-Smith
Yes, you are right and I was wrong. For instance, suppose we number
the people at the first w stations by ordered pairs (m,n), where
m represents the station they are at. And let phi be an enumaration
of these ordered pairs such that phi(m,n) > m. Then at station m
we let off person phi^{-1}(m) and then let on all the people at
station m. Then when we get to station w_0, there is no-one left.
It is just like the ``put 10 in, remove 1'' paradox.
Of course, in this way, you can make the number of people left on
the subway by w_1 to be anything you like (less than or equal
to aleph_1).
Am I correct, or did I get something else wrong?
Stephen Montgomery-Smith
H. Enderton
Hold it. Before going to omega_1, let's take the local as far as
omega_0. The surprising result (which makes this an interesting
puzzle, I think) is that the number of passengers at omega_0 can be
anything from aleph_0 down to *zero*. It depends on how you choose the
passenger to eject.
Here is a system that empties the entire train. At station n, assign
each embarking passenger a rank: <n,0>, <n,1>,.... Here <x,y> is a
standard pairing function. Or you can use 2^x times 3^y if you don't
know a better function. The rule is that you disembark the passenger with
lowest rank.
At station omega_0, the train is *empty*. (Suppose you got on the
train. You have finite rank r. After no more than r stops you have
the smallest rank of anyone on the train. At the next stop, off you
go!)
In other words, the answer doesn't just depend on the cardinalities of
the embarking and disembarking passengers. It also depends on how you
decide on whom to throw to the wolves. Curious.
--Herb Enderton (h...@math.ucla.edu)
Tom Costello
Robert M. Solovay
The answer is 0.
Here is a solution to the "transfinite subway" problem. I assume that
once someone departs the train they never get on again.
Use the ordinals $\gamma$ such that:
$\omega\alpha \leq \gamma < \omega\alpha + \omega$ to label the
people that get on at stop $\alpha$.
I use the notions of ``closed unbounded subset'' and ``stationary
subset'' of $\omega_1$. See Kunen's or Jech's book on set theory for a
treatment of this topic.
I say that for a closed unbounded set of $\alpha$'s less than
$\omega_1$, the train is empty when it pulls into the $\alpha$'th
station. It will follow, of course that the train is empty when it
pulls into the $\omega_1$'th stop.
Deny. Then for a stationary set of $\alpha's$, someone gets off at the
$\alpha$'th stop. Now for a clubs worth of $\alpha$'s, we have
$\omega\alpha=\alpha$. So for a stationary set of $\alpha$'s, say $A$,
we have a function $f$ which is one-to-one on $A$ and such that $\alpha \in
A$ implies that $f(\alpha) < \alpha$. (The function $f$ tells who gets
off at the $\alpha$'th stop, namely $f(\alpha)$.) But this contradicts
a well-known theorem of Fodor.
--
Robert Solovay sol...@math.berkeley.edu
Mathematics Department (415)654-3047
University of California
Berkeley, CA 94720
Scott Huddleston
subway problem. I give a simpler derivation of the solution below.
I heard this problem made the rounds at an AMS meeting several years back.
In article <1991Aug9.0...@agate.berkeley.edu> sol...@math.berkeley.edu (Robert M. Solovay) writes:
>In article <22...@crl.LABS.TEK.COM> sc...@ferrari.LABS.TEK.COM (Scott Huddleston) writes:
>>There is a subway line from the airport to the Hilbert hotel which operates
>>as follows: there is a station at each ordinal number, and every station is
>>assigned a unique ordinal. The subway stops at each station, in order.
>>At each station people disembark and board, in order, as follows:
>>i). if any passengers are on the subway, exactly 1 disembarks, then
>>ii). aleph_0 passengers board the subway.
>>
>>Station 0 is at the airport, and the Hilbert hotel is at station
>>w_1 (the first uncountable cardinal). The subway starts its journey
>>empty. Aleph_0 passengers board the subway to the Hilbert hotel at the
>>airport (station 0), and off it goes.
>>
>>The puzzle: when the subway pulls up to the Hilbert hotel at station w_1,
>>how many passengers are on it? Is it 0, aleph_1, some determinate value in
>>between, or indeterminate?
>>--
>>Scott Huddleston
>>sc...@crl.labs.tek.com
>
>The answer is 0.
[solution using regressive functions on stationary sets omitted]
[alternate solution without using much machinery from set theory follows]
Show, for each countable ordinal x, there's a countable E(x) > x
s.t. the train is empty when it pulls into station E(x). To find E(x),
define functions b and d from passengers to w_1 by:
b(p) = z s.t. passenger p boards at station z,
d(p) = z if p disembarks at station z < w_1
= 0 if p reaches station w_1
Given x, define
y_0 = x
y_(i+1) = sup { d(p) | b(p) <= y_i } for 0 <= i < w_0
E(x) = sup { y_i | i < w_0 }
Note that y_i is an increasing sequence of countable ordinals, so
E(x) is a countable limit ordinal. The train is empty when pulling
into E(x), for if not there would be some z < E(x), some p with b(p)=z
and d(p) >= E(x), and some k with z <= y_k < E(x), giving y_(k+1) >= E(x)
and y_(k+2) > E(x), a contradiction.
Since every passenger p disembarks before station E(b(p)) < w_1, no one
reaches w_1.
Moral: If you're booked at the Hilbert hotel, you won't get there on the
subway. Better to enquire at the Long Line limo and cab company.
--
Scott Huddleston
sc...@crl.labs.tek.com
Lambert Meertens
) Moral: If you're booked at the Hilbert hotel, you won't get there on the
) subway. Better to enquire at the Long Line limo and cab company.
Here is a twist to the problem.
According to custom, the "oldest" passenger aboard (the first to board the
train) gets to pick who gets off at a station whenever there is more than
one passenger aboard. Luck has it that you were the first to get on at the
airport. You want to defer your being forced to detrain as much as
possible, what with the unspeakable tariffs of the Long Line company for
uncountable destinations. What is your strategy?
(I suspect that for any countable ordinal there is a picking rule that will
let you ride to at least the corresponding subway station. If that is
true, can you give such a rule? If not, what is the least station you
cannot possibly reach?)
--
--Lambert Meertens, CWI, Amsterdam; lam...@cwi.nl
news
>According to custom, the "oldest" passenger aboard (the first to board the
>train) gets to pick who gets off at a station whenever there is more than
>one passenger aboard. Luck has it that you were the first to get on at the
>airport. You want to defer your being forced to detrain as much as
>possible, what with the unspeakable tariffs of the Long Line company for
>uncountable destinations. What is your strategy?
>
>(I suspect that for any countable ordinal there is a picking rule that will
>let you ride to at least the corresponding subway station. If that is
>true, can you give such a rule? If not, what is the least station you
>cannot possibly reach?)
You can get to any countable ordinal a as follows: before
you get on, inject a into w-{0}. Call the injection i, and
remember it. Then at any stop s, for s<a, kick off the i(s)-th
passenger who got on with you at the airport.
You can't get to w1, however, especially if (as others have
shown) the subway is necessarily empty then. But here's
another proof.
Lemma: There is no function f:(w1-{0})->w1 with these two properties:
1. f(a)<a; and
2. for any a there are at most countably many b with a=f(b).
Proof: Suppose there is such an f. Construct a tree of ordinals, rooted
at 0, with parent=f(child). Since the ordinals are finitely-descending,
every ordinal <w1 must occur at finite depth in that tree, and so it is
the limit of its (countably-branching) finitely-deep prefixes. Each of
those is countable, and there are a countable number of them, if
one considers only those of uniform depth (which is good enough).
Thus there are only a countable number of nodes overall, but w1 is
uncountable: a contradiction.
Now if there were a strategy that got you to the hotel at w1, you could
construct an f as above with the definition "the person kicked off at a
got on at f(a)".
--Carroll Morgan, PRG Oxford UK
news
>According to custom, the "oldest" passenger aboard (the first to board the
>train) gets to pick who gets off at a station whenever there is more than
>one passenger aboard. Luck has it that you were the first to get on at the
>airport. You want to defer your being forced to detrain as much as
>possible, what with the unspeakable tariffs of the Long Line company for
>uncountable destinations. What is your strategy?
>
>(I suspect that for any countable ordinal there is a picking rule that will
>let you ride to at least the corresponding subway station. If that is
>true, can you give such a rule? If not, what is the least station you
>cannot possibly reach?)
The first person on CAN get to Omega 1 ... but only by changing places with
the driver !
Carroll Morgan's analysis shows that there MUST be a COUNTABLE ordinal
at which the train is empty (except for the driver of course), dependent
on the stratagy for selecting the disembarkees.