A Cool Infinity Problem - Science, Math and Philosophy Forum

Two Plus Two Forums Other Topics Science, Math, and Philosophy

A Cool Infinity Problem

Post Reply Subscribe

...

04-20-2008 , 09:52 PM

jay_shark

Pooh-Bah

Join Date: Sep 2006 Posts: 3,655

Suppose there are an infinite number of people and an infinite number of locker doors. Every person is assigned a locker number; however, an event takes place in which the locker doors are rearranged.

Prove that if there are infinite number of people with locker numbers higher than their original number, then there must be infinite number of people with locker numbers lower than their original number.

Last edited by jay_shark; 04-20-2008 at 10:05 PM.

Quote

04-21-2008 , 08:38 AM

undercheck

enthusiast

Join Date: Jul 2005 Posts: 57

The rearrangement apparently is performed so that also each locker room will be attached to a person? (otherwise, e.g., assigning everyone a locker number 1 higher than before would be a counterexample)

Quote

04-21-2008 , 09:48 AM

madnak

Cooler than Sammy Hagar

Join Date: Aug 2005 Posts: 19,742

Quote:

Originally Posted by undercheck

That counterexample doesn't work. As there is no beginning or end to the sequence (or to the line people), there must still be a 1:1 correspondence.

Given the same infinity both times, a 1:1 correspondence goes without saying. There's no way to change that. Proving the initial point probably relates to that.

But if the infinity itself changes, then I don't think this holds. For example, if the original infinity is -1, -2, -3... and the subsequent infinity is 1, 2, 3... But I assume "rearranging" doesn't involve that level of change (just taking the same numbers ie the same infinity and switching the specific lockers associates with specific people).

Quote

04-21-2008 , 10:30 AM

lastcardcharlie

Carpal \'Tunnel

Join Date: Aug 2006 Posts: 10,724

Quote:

Originally Posted by jay_shark

Suppose for contradiction that there only finitely many such people. Consider the permutation f : N -> N, where a person's second locker number is mapped to their first. There are only finitely many numbers n such that f(n) > n. Let k be the biggest number in the set {f(x) | f(x) > x}
and let K be the set {0, 1, .., k}. Then f(K) is a subset of K and then, by the Pigeonhole Principle, f(K) = K. But f(k + 1) < k + 1 and so f(k + 1) is in K, a contradiction.

Quote

04-21-2008 , 10:50 AM

bigpooch

veteran

Join Date: Sep 2003 Posts: 3,208

Quote:

The right idea, but the last sentence is incorrect; it could be
something like:

But f(k+1)=k+1 (otherwise, f(k+1)>k+1 implies f(k+1) is in K) ),
f(k+2)=k+2, etc. or f(j)=j for all j>k, i.e., there are only finitely
many n for which f(n)<n (since these n must all be in K)
contradicting the assumption that there are infinitely many
such n.

Quote

04-21-2008 , 10:58 AM

lastcardcharlie

Carpal \'Tunnel

Join Date: Aug 2006 Posts: 10,724

Quote:

Originally Posted by bigpooch

Good point. Damn!

Quote

04-21-2008 , 11:28 AM

bigpooch

veteran

Join Date: Sep 2003 Posts: 3,208

Here's a generalization that holds because of your idea:

Let W be a well-ordered set with ordering < and
g:W -> W be any bijection where the cardinality
of the set S(W,g,<) = {x in W such that g(x)<x} is
the same as that of W. Then, S(W,g,>) also has
the same cardinality (where > is defined in the usual
way with respect to <).

Thus, if you assume the axiom of choice (need this
to well-order the reals), the problem also holds true
for SOME ordering < of the reals.

Quote

04-21-2008 , 10:51 PM

Siegmund

Pooh-Bah

Join Date: Feb 2005 Posts: 4,166

The original problem says

Quote:

Suppose there are an infinite number of people and an infinite number of locker doors. Every person is assigned a locker number

It does *not* say every locker number was assigned to someone.

I assume you meant to say something in the question to force this to be about bijections of integers to integers. As it is, I think OP is trivially false: move occupied lockers up and move empty lockers down.

Quote

04-22-2008 , 04:34 AM

bigpooch

veteran

Join Date: Sep 2003 Posts: 3,208

Of course you're technically right; perhaps jay_shark should
have used a word like "permuted" rather than "rearranged".
In any case, by locker number, he means some
nonnegative integer; in any case, the truth of the OP
depends on the well-ordering of the set of nonnegative
integers and the locker numbers need only be some
infinite subset of this set.

Quote

05-03-2008 , 11:15 PM

#10

LongLiveYorke

grinder

Join Date: May 2008 Posts: 527

Quote:

Originally Posted by jay_shark

I don't think this is true. Imagine that everybody gets assigned not their original number but rather double their original number. Therefore, everybody has a higher number and nobody has a lower number. Contradiction by example.

(Clearly this is possible since 2N is isomorphic to N, so there are still the same amount of lockers)

Quote

05-04-2008 , 01:14 AM

#11

Enrique

Pooh-Bah

Join Date: Mar 2005 Posts: 3,886

Quote:

Originally Posted by LongLiveYorke

I don't think your exampls is valid, as what happened was a permutation of the doors. Multiplying by 2 is not an onto function, so you can't be a permutation.

Quote

Post Reply Subscribe

...