CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "infinite sets : Genie vs Jenny"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #741
Reading Topic #741
newscam9
guest
Dec-05-06, 07:07 AM (EST)
 
"infinite sets : Genie vs Jenny"
 
   Hello all,

I was reading an article on this site about infinite sets and infinite subsets and the curious implication of the property that the two are in 1 on 1 correspondence. (Please, go to :
https://www.cut-the-knot.org/Probability/infinity.shtml)

Well, there is a paradox cited from a book on probability written by S. Ross (all references are in the article) which gives me a huge headscratcher.

Let me narrate the problem.

Genie and Jenny are given identical urns of limitless capacity. Both receive "from on high" balls engraved with one of the natural numbers 1, 2, 3, ... which they duly place in the urn.

The balls arrive by series of ten and after each reception Genie and Jenny take out exactly one ball from the urn ( they choose freely which ball to take out of the urn).

So, to make it more clear:

1st period: balls ##1-10 arrive and they take out one ball;
2nd period: balls ##11-20 arrive and they take out one ball;
3rd period: balls ##21-30 arrive and they take out one ball;
and so on

Genie chose to take out always the highes - numbered ball : ## 10, 20, 30 etc. Jenny chose to take out always the lowest numbered ball: ## 1, 2, 3 etc

The question is: how many balls will contain Genie's and Jenny's urns if the above - mentioned procedure is repeated infinite number of periods.

Well, those of you familiar with infinite set theory know that there will be 0 balls in Jenny's urn and (?!) that Genie's urn will be infinitely laden...


Now back to the thing I don't understand:
While I see why there should be no balls in Jenny's urn, I have a problem with the infinite amount of balls in Genies urn.

After all, there are infinite amount of numbers divisible by ten and there IS 1 on 1 correspondence between this particular infinite subset and the infinite set of natural numbers (for exemple, 1 to 10, 2 to 20, 3 to 30, ..., n to 10n). This means that any particular element of the subset has exectly one match of the set (et vice versa?). If we take out infinity from infinity, what we are left with? 0? Indeterminicity?...


On the other hand, Genie NEVER takes out ball #1 for exemple which is enough to prove that her urn does not contain zero balls...

Please help me out with this one. I do hope there is a way out which is not some kind of word play...


(ps I suspect that 1 on 1 correspondence between infintie subset and infinite set may be the culprit, but I feel this is a wrong reasonment)

Thanks for your patience.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

  Subject     Author     Message Date     ID  
infinite sets : Genie vs Jenny newscam9 Dec-05-06 TOP
  RE: infinite sets : Genie vs Jenny sfwc Dec-05-06 1
  RE: infinite sets : Genie vs Jenny alexb Dec-05-06 2
  RE: infinite sets : Genie vs Jenny newscam9 Dec-06-06 3
     RE: infinite sets : Genie vs Jenny alexb Dec-06-06 4
         RE: infinite sets : Genie vs Jenny sfwc Dec-06-06 5
             RE: infinite sets : Genie vs Jenny alexb Dec-06-06 6
             RE: infinite sets : Genie vs Jenny newscam9 Dec-07-06 7

Conferences | Forums | Topics | Previous Topic | Next Topic
sfwc
Member since Jun-19-03
Dec-05-06, 10:35 AM (EST)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
1. "RE: infinite sets : Genie vs Jenny"
In response to message #0
 
   >While I see why there should be no balls in Jenny's urn, I
>have a problem with the infinite amount of balls in Genies
>urn.
>
>After all, there are infinite amount of numbers divisible by
>ten and there IS 1 on 1 correspondence between this
>particular infinite subset and the infinite set of natural
>numbers (for exemple, 1 to 10, 2 to 20, 3 to 30, ..., n to
>10n). This means that any particular element of the subset
>has exectly one match of the set (et vice versa?). If we
>take out infinity from infinity, what we are left with? 0?
>Indeterminicity?...
This is exactly the problem illustrated by the paradox. The two different ways of 'subtracting' infinity from infinity give different answers. So the answer is indeterminate, unless you know the exact details of the subtraction. In this case, we do know those details, and so can give the correct answer: Infinity.

>On the other hand, Genie NEVER takes out ball #1 for exemple
>which is enough to prove that her urn does not contain zero
>balls...
By a similar argument, Genie NEVER takes out ball #11, or ball #21, or ball #31, or any other ball whose last digit is 1, which is enough to prove that her urn contains infinitely many balls.

Thankyou

sfwc
<><


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1928 posts
Dec-05-06, 10:52 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
2. "RE: infinite sets : Genie vs Jenny"
In response to message #0
 
   You must be careful with expressions like "infinity minus infinity."

E.g., it may mean "an infinite cardinal number minus an infinite cardinal number" or "an infinite set minus an infinite set".

You appear to use the expression both ways and this is what leads to confusion.

The difference of two cardinal numbers may or may not be defined.

The difference of two sets (whether infinite or not) is always defined, is a set, and may or may not be infinite.

For two cardinal numbers a and b,

a - b = a, if a > b,
a - b is undefined, otherwise.

For two sets A and B with the cardinalities a and b:

|A - B| = a, if a > b,
|A - B| may be any cardinal starting with a down to 0.

It may be any cardinal for arbitrary A and B, but is something for specific A and B.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
newscam9
guest
Dec-06-06, 08:08 AM (EST)
 
3. "RE: infinite sets : Genie vs Jenny"
In response to message #0
 
   Thank you sfwc and alexb

I think I have a problem with my perception of infinity and maybe I tend to attribute to it qualities which are true only for finite sets...

What I find hard to swallow are the following sequences (Please correct me where I'm wrong)

1) We are talking about an infinite cardinal set A
2) Let A1, A2, ... be some infinte cardinal subsets of A which does not contain commonn elements with each other (they do contain common elements with A however). For exemple think of A as the positive natural numbers, of A1 as positive even natural numbers and of A2 as positive uneven natural numbers
3) Since A1 is an infinte subset, then there is one-on-one correspondence between A and A1. So # elements in A = # elements in A1. Same is true for A2. So, if we take out A1 from A there will be still an infinite number of elements of A (Something like Hilbert's hotel paradox? https://en.wikipedia.org/wiki/Hilbert%27s_hotel)
4) Dynamically, at least wihtin the finite realm (can we talk of the passage finite - infinite here? can we talk of dynamics for the infinite cas? I think we can't...) Gennie's and Jenny's strategies seem similar: for both # balls in the urn rises steadily. There must be some point however from which Jenny's balls in the urn should start to decrease... Maybe this point is inside the infinite set? How fast is this decrease? Maybe it is instant...

5) The original article mentions a much stronger reusult which lead to zero balls as did Jenny's strategy (https://www.cut-the-knot.org/Probability/infinity.shtml). Actually, we can allow Jenny to choose randomly the balls at each period (accepting that she attributes equal probability for the balls in the urn). Probability to end up with zero balls is still 1.
On the other hand, we can also generalise Gennie's strategy as well. What if Genny chose, at each period to take out randomly one of the last ten balls to enter the urn? I think that her urn will still be infinitely laden.

6) One last thing (for alexb) Please reexplain your argument about cardinals and sets. I'm afraid I've stopped following you from the line where you wrote:
a-b = a if a>b


I'm aware, that we should reject the axiom that "the whole has more terms thant the part", as B. Russell put it. Still I'm not sure that my grasp on the infinite is the correct one. Help me to understand please.

Well, thank you once again



  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1928 posts
Dec-06-06, 10:40 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
4. "RE: infinite sets : Genie vs Jenny"
In response to message #3
 
   >(Please correct me where I'm wrong)
>
>1) We are talking about an infinite cardinal set A

A cardinal is a number, not a set.

Cardinals: one, two, three, ..., aleph0, ...
Ordinals: first, second, third, ..., (often) ù, ...

>2) Let A1, A2, ... be some infinte cardinal subsets of A
>which does not contain commonn elements with each other
>(they do contain common elements with A however). For
>exemple think of A as the positive natural numbers, of A1 as
>positive even natural numbers and of A2 as positive uneven
>natural numbers
>3) Since A1 is an infinte subset, then there is one-on-one
>correspondence between A and A1. So # elements in A = #
>elements in A1. Same is true for A2. So, if we take out A1
>from A there will be still an infinite number of elements of
>A (Something like Hilbert's hotel paradox?
>https://en.wikipedia.org/wiki/Hilbert%27s_hotel)

OK so far.

>4) Dynamically, at least wihtin the finite realm (can we
>talk of the passage finite - infinite here? can we talk of
>dynamics for the infinite cas? I think we can't...)

Do not even know what this means.

>Gennie's
>and Jenny's strategies seem similar: for both # balls in the
>urn rises steadily. There must be some point however from
>which Jenny's balls in the urn should start to decrease...

Do not know about that. You appear to apply "finite" reasoning to infinite sets.

>Maybe this point is inside the infinite set? How fast is
>this decrease? Maybe it is instant...

Truly do not know. It's hard to imagine how things actually (whatever this may mean) happen. This is why the whole story is referred to as a paradox.

>
>5) The original article mentions a much stronger reusult
>which lead to zero balls as did Jenny's strategy
>(https://www.cut-the-knot.org/Probability/infinity.shtml).
>Actually, we can allow Jenny to choose randomly the balls at
>each period (accepting that she attributes equal probability
>for the balls in the urn). Probability to end up with zero
>balls is still 1.

Yes. For each ball, the probability to stay in is 0.

>On the other hand, we can also generalise Gennie's strategy
>as well. What if Genny chose, at each period to take out
>randomly one of the last ten balls to enter the urn? I think
>that her urn will still be infinitely laden.

Yes, of course.

>6) One last thing (for alexb) Please reexplain your argument
>about cardinals and sets. I'm afraid I've stopped following
>you from the line where you wrote:
>a-b = a if a>b

A cardinal number is a common attribute of sets in 1-1 correspondence. "Infinity", as a cardinal number, is undefined because there are many infinities.

aleph0 is the cardinal number of the set of integers (and also the set of even integers, the set of whole numbers, the set of irrational numbers, the set of algebraic numbers, and many others.)

This is the smallest infinite cardinal. There are other "alephs". The rule for the addition of infinite cardinals says

cardinal1 + cardinal2 = max(cardinal1, cardinal2).

It is sort of "many to one" operation. This is why the reverse operation of subtraction is said to be "undertermined."

But note that you can always subtract one set from another. Their difference will be a set of certain cardinality. For two sets say C1 and C2 with cardinalities c1 and c2, the cardinality of the difference may be any cardinal number from 0 to max(cardinal1, cardinal2).

>I'm aware, that we should reject the axiom that "the whole
>has more terms thant the part", as B. Russell put it.

For finite sets this is true. So this is in fact how you define an infinite set: a set is ininite if it's in a 1-1 correspondence with its proper part.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
sfwc
Member since Jun-19-03
Dec-06-06, 12:34 PM (EST)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
5. "RE: infinite sets : Genie vs Jenny"
In response to message #4
 
   >>1) We are talking about an infinite cardinal set A
>A cardinal is a number, not a set.
This is an important distinction to keep in your head when thinking about infinity. For finite sets, any set has an associated number: The number of elements. Two sets have the same number of elements if and only if the elements of the first may be paired off with the elements of the second. It turns out we can also associate something like a number, called the cardinal number of elements, to infinite sets. Again, two sets have the same cardinal number of elements if and only if the elements of the first may be paired off with the elements of the second.

We can do some basic operations on finite numbers, like addition and subtraction. These are intended to represent operations we can do with finite sets, like taking the union of sets (if they have no elements in common) or removing subsets. The same operations on sets may of course be extended to operations on infinite sets. But, and this is important, this does not mean that the operations on finite numbers extend to operations on infinite cardinal numbers. With some care, you can show that addition does extend in this way. But subtraction does not. That is part of the paradox.

We are not talking about an infinite cardinal set A, but rather about an infinite set A. To put it another way, we are talking about a set A whose cardinal number is infinite.

>>4) Dynamically, at least wihtin the finite realm (can we
>>talk of the passage finite - infinite here? can we talk of
>>dynamics for the infinite cas? I think we can't...)
It is important to remember also that infinite sets are objects in their own right. That is, a set should not be confused with an infinite process by which it could be built. The paradox deals with both sets and processes: Processes have dynamics but sets do not. Nor do numbers. So we must be careful not to confuse any of the three closely related ideas mentioned; sets, processes and numbers.

>>Gennie's
>>and Jenny's strategies seem similar: for both # balls in the
>>urn rises steadily. There must be some point however from
>>which Jenny's balls in the urn should start to decrease...
This is not true.

If we analyse the process taking place here, it is clear that throughout the process the number of balls in Jenny's urn is increasing, just as is true for Genie. This process does not include a point at which the number of balls in Jenny's urn begins to decrease.

If, on the other hand, we analyse the set of balls finally in Jenny's urn, we find that it does not contain any of the balls. A good way to see this is to think about it from the point of view of an individual ball. Any particular ball is put in, and then, a while later, is taken out again. So it ends up not being in the urn. The set of all balls that are left in the urn forever is empty. But there is no point at which the number of balls in this set decreases: It is a set, and not a process.

Finally, this shows that the number of balls remaining in the urn is 0. This number is directly related to the set, not the process, and presents a striking contrast to the increasingly large numbers associated with the process. Hence the paradox.

>>On the other hand, we can also generalise Gennie's strategy
>>as well. What if Genny chose, at each period to take out
>>randomly one of the last ten balls to enter the urn? I think
>>that her urn will still be infinitely laden.
You are right, newscam9, as alexb has mentioned. Can you think of a way to prove this?

>aleph0 is the cardinal number of the set of
>integers (and also the set of even integers, the set of
>whole numbers, the set of irrational numbers, the set of
>algebraic numbers, and many others.)
Of course, you mean the set of rational numbers.

>But note that you can always subtract one set from another.
>Their difference will be a set of certain cardinality. For
>two sets say C1 and C2 with
>cardinalities c1 and c2, the
>cardinality of the difference may be any cardinal number
>from 0 to max(cardinal1, cardinal2).
By 'difference' here, do you mean the symmetric difference? With the more usual meaning, if c1 is strictly bigger than c2 then the cardinality of their difference is c1. Otherwise the cardinality of the difference could be anything in the range from 0 to c1. This seems to fit a little better with what you wrote in your original post.

Thankyou

sfwc
<><


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1928 posts
Dec-06-06, 12:42 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
6. "RE: infinite sets : Genie vs Jenny"
In response to message #5
 
   >>aleph0 is the cardinal number of the set of
>>integers (and also the set of even integers, the set of
>>whole numbers, the set of irrational numbers, the set of
>>algebraic numbers, and many others.)

>Of course, you mean the set of rational numbers.

Yes, of course. Sorry and thank you.

>>But note that you can always subtract one set from another.
>>Their difference will be a set of certain cardinality. For
>>two sets say C1 and C2 with
>>cardinalities c1 and c2, the
>>cardinality of the difference may be any cardinal number
>>from 0 to max(cardinal1, cardinal2).
>By 'difference' here, do you mean the symmetric difference?

Does it really matter? Ah, because of the symmetry in max(.,.), here it does does. Originally I meant the common difference.

>With the more usual meaning, if c1 is strictly
>bigger than c2 then the cardinality of their
>difference is c1. Otherwise the cardinality of
>the difference could be anything in the range from 0 to
>c1.

Right. The point to be made is that the cardinality of the difference could be anything in an infinite range, which makes the difference of the corresponding cardinals indeterminate.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
newscam9
guest
Dec-07-06, 10:50 AM (EST)
 
7. "RE: infinite sets : Genie vs Jenny"
In response to message #5
 
   >>>On the other hand, we can also generalise Gennie's strategy
>>>as well. What if Genny chose, at each period to take out
>>>randomly one of the last ten balls to enter the urn? I think
>>>that her urn will still be infinitely laden.
>You are right, newscam9, as alexb has mentioned. Can you
>think of a way to prove this?

I think a way to do this is to prove that

Prob<#"balls that are NEVER taken out of Gennie's urn"<M>=0
for M any positive integer

Since M is finite, we can be sure that after periods there will be at least M balls that will stay permanently in the urn.

As the procedure of piling balls in the urn goes to infinity, number of "permanent" balls will be greater than any finite number, which is another way to say that Gennie's urn should be infinitely laden with balls.

Thank you guys for your insights on this paradox and on infinite sets.

I tested some people with this nut, have to say it'surely provokes an eyeopener :-) People have trouble to accept it, especially those with some (superficial) knowledge and fondness to maths. Only one person which is quite away from maths gave away the correct anwser within seconds... I figure that's the way with paradoxes...

Finally, here's a link for those of you fascinanted with paradoxes that confront some erroneous perceptions concerning infinity.

https://www.c3.lanl.gov/mega-math/workbk/infinity/infinity.html


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK