|
This is probably the hardest puzzle that i've solved myself:
An infinite number of ppl are given either a black or a white hat. They can't see what colour hat they have on but they can see everyone elses. They cannot communicate with each other in anyway once they've been given the hats but they can devise a strategy before the game starts. Then, at a predetermined time, they all have to shout out the colour hat they think they have on [at the same time]. They win if only finitely many get it wrong.
There are no pissy tricks like "looking in a mirror" or sneaking round the "no communication" rule and we assume they can see all the the other ppl at once and perform any computations they might need to instantly.
right so if you don't know/believe the axiom of choice you'll have to come up with a solution i haven't thought of yet. You might have come across the axiom in one of it's many forms (Zorn's lemma, Well-ordering principle) at some point in a maths degree but otherwise, even if you look it up on wiki, you'll struggle to know how to use it. It (roughly) says that if you have any collection of sets, you can pick an element in each of them, equivalently it says you can "well order" any set (ie you can say x<y or y<x for any x not equal to y).
I was told this puzzle a while ago, but it's solution actually came up the other day in some proper maths i was doing in a really natural way. One thing that's pretty weird is that i don't think it's possible to come up with a strategy that works if we replace "only finitely many" with "less than n" for an arbitrarily large n
|
People don't have to shout out their hat color at the same time, right?
|
yes they do [have to shout at the same time]
|
How about everybody yells one color
|
what if i handed out the hats black white black white ... all the way up? then which ever you shout you're wrong. In fact what if you all shout one colour and i handed out all of them the other colour?
oh and you need a plan that works all the time, not just one that gives you a good chance of winning
|
I think what I'm proposing might count as a method of communication, but here's my first idea.
Arrange all the people in a line in any arbitrary order. First two people stand out in a separate line. The next person will look at the first two, and if there is a change of color in the line, he will stand right in between the two colors. If there is not, he will stand at the end of the line. In either case, the line will now be split between black and white, or is all of one color.
IE
If the line is WW, the guy will stand at the end, so the line is now WWB or WWW
If the line is WB, the guy will stand in between, so the line is now WWB or WBB.
Therefore there is always a clear division between the black hats and white hats.
Once the infinitely many people have gone into place (plausible because they can compute instantly?). Then the last person to go into the line will define the division between the two colors, and everyone else can just look at the other side of that division to find out what color their side is.
The only person that would not know what color his hat is would be the last guy.
|
this is what i said the first time i saw the puzzle but this comes under the (rather too vague) heading of not communicating at all.
imagine everyone's in a prison cell and all they can see is one little light for every person apart from you which is either on or off depending on the colour hat they have on.
by the well ordering principle you can assign everyone a number (or element of an indexing set if you want to go cardinals on it, the solution i know works for any cardinal)
|
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^
|
well done, i'd hoped it'd take longer than that
places you might have seen it: a basis of any infinite dim'l vector space
|
Muirhead: i don't suppose you'd know any places i could read up on the algebraic geometry approach to ramification do you? all i can find is number theory books
|
Hm... I don't know quite what level of book you want. You might check out some sections of Liu's book on Algebraic Geometry and Arithmetic Curves as a start?
|
so it's for a postgrad reading group on galois thy that's sort of branched out a bit. That book looks pretty good. i don't really know a lot of alge geo but when ever i talk to my supervisor about what's going on in these rings i'm looking at he always starts drawing pictures and makes me feel i should get on it.
|
United States24613 Posts
On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^
Can you explain what that means.
|
|
|
for convenience label each of the ppl 1,2,3,... Now let a(i) be a sequence of 0's and 1's and we'll say that a(i)=0 if person i's hat is white, a(i)=1 if the persons hat is black.
For example a(i) is one way of giving out the hats a(1)=1 a(2)=0 a(3)=0 would be BWW
Let b(i) be the same as a(i) for a different way of handing out hats, so b(1)=1 b(2)=1 b(3)=1 would be BBB.
then we say a(i) "=" b(i) if and only if only finitely many of the ( a(i) - b(i) ) are not equal to 0.
(the collection of the x(i) which are "=" are the equivalence classes)
Now pick a list a(i), b(i), c(i),... so that a(i) is not "=" to b(i) or c(i) or d(i) etc and b(i) is not "=" to c(i) or ...
(forgive me for the implied countableness, (countable is a technical maths term))
now how ever i hand out the hats there will be a x(i) in the list such that x(i) is "=" to the way i hand out the hats. everybody shouts out the colour of hat they should have in x(i), and only finitly many will be wrong
|
United States24613 Posts
Forgive me for pointing out how inaccessible that explanation was, but I have no idea how that jargon results in people knowing what color to yell out.
|
On May 10 2009 12:29 micronesia wrote:Show nested quote +On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^ Can you explain what that means.
Think of the people with white hats as a subset of the people. If two subsets only differ by finitely many elements, then we group those two sets together (into a set of subsets of the people). This is our equivalence relation. There's some conditions you have to prove about equivalence classes, but in this case it's easy enough not to be worth mentioning.
In algebra, you can reduce a group with an equivalence class to the unique equivalence classes, for example, the integers by 0 mod p, 1 mod p, ..., p-1 mod p (or odds or evens if that's simpler) into p elements, hence the OP's solution motivated by n-dimensional vector spaces (where dividing the space by the equivalence class of lines is common).
edit: oops solution is simpler than i thought.
anyway, you have your equivalence classes of subsets. There are infinitely many, but that doesn't matter, and from each equivalence class, you choose one element, that is, one specific way of handing out hats. Since you've covered every equivalence class, any subset of the people will match to all but finitely many of one of the chosen elements.
When the hats are handed out, you can see everybody else's hat, and your own hat can only increase the number of possible wrong matches by 1, so you know equivalence class that particular hat distribution is in. Everyone now votes their according to what their representative element would have as a hat.
|
I'm not understanding this...if you hand out the hats to an infinite number of people... then the number wrong will be infinite... simply because the whole set is infinite. You would also never reach the time when everyone would call out what color they think there hat is...because you'd still be handing out hats..
and even if you did...even if you came up with a plan before hand that weeded out 99% of errors 1% of infinite is well infinite.... the continuum hypothesis be damned.
|
(Disclaimer: I'm not a mathematician)
I don't buy the equivalence relation thing. If we're allowed to apply "a = b if a(i) != b(i) for only a finite # of i" an infinite number of times (why not? everything else in this problem seems to be infinite  ), then everything breaks.
Also, if we just coin-flip for each hat, 50% of the guesses are going to be wrong no matter how they were derived?
|
i think I know how to do it by moving into lines going right or left based on the 2 hats in front of u
but it's too hard to explain lol and i can't put it into math terms cuz i dont know how
|
we assume they can see all the the other ppl at once This assumption completely breaks the game. I can get down to 0-1 mistakes if you assume this.
|
United States24613 Posts
On May 10 2009 12:54 igotmyown wrote:Show nested quote +On May 10 2009 12:29 micronesia wrote:On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^ Can you explain what that means. Think of the people with white hats as a subset of the people. If two subsets only differ by finitely many elements, then we group those two sets together (into a set of subsets of the people). This is our equivalence relation. There's some conditions you have to prove about equivalence classes, but in this case it's easy enough not to be worth mentioning. In algebra, you can reduce a group with an equivalence class to the unique equivalence classes, for example, the integers by 0 mod p, 1 mod p, ..., p-1 mod p (or odds or evens if that's simpler) into p elements, hence the OP's solution motivated by n-dimensional vector spaces (where dividing the space by the equivalence class of lines is common). edit: oops solution is simpler than i thought. anyway, you have your equivalence classes of subsets. There are infinitely many, but that doesn't matter, and from each equivalence class, you choose one element, that is, one specific way of handing out hats. Since you've covered every equivalence class, any subset of the people will match to all but finitely many of one of the chosen elements. When the hats are handed out, you can see everybody else's hat, and your own hat can only increase the number of possible wrong matches by 1, so you know equivalence class that particular hat distribution is in. Everyone now votes their according to what their representative element would have as a hat.
Hm... maybe it would be clearer if you could tell me what instructions you would give to a random person who needs to make a decision about what color to pick?
|
He picks what his element in the chosen member of the equivalence class would have.
Example: the chosen member of the equivalence relation is all odd representatives have white hats. The equivalence class is subsets that differ from the odd numbers in finitely many ways. He is 5. He observes that the people wearing white hats are persons # 101, 103, 105, 107, ... No matter what he is wearing, this differs finitely many ways from the set odd people wear white hats.
He chooses white since he's #5 and odd.
And it's clearly an equivalence relation due to the finitely many differences criteria:
Definition
Let A be a set and ~ be a binary relation on A. ~ is called an equivalence relation if and only if for all a,b,c\in A, all the following holds true:
* Reflexivity: a ~ a
* Symmetry: if a ~ b then b ~ a
* Transitivity: if a ~ b and b ~ c then a ~ c.
|
By an assignment of hats to people, I mean, for example:
First person gets white hat
Second person gets black hat
...
We consider two assignments to be "equivalent" if there are only a finite number of people whose hat colour changes from assignment 1 to assignment 2.
Using this equivalence test, we can split up all the possible assignments into "equivalence classes". An assignment is equivalent to every other assignment in its equivalence class, but is not equivalent to any assignment in any other equivalence class. We can do this because our equivalence test passes for an "equivalence relation" (see wikipedia for details).
Using the axiom of choice (see wikipedia for details), we now pick one assignment from each of these equivalence classes, and everyone remembers which one we picked from each equivalence class (quite a lot to remember, as there will be an infinite number of these equivalence classes ).
That's the preparation stage.
Now, to decide which colour to report...
First, we decide which equivalence class the current assignment of hats to people is in. This is possible because there are only 2 possible assignments -- the one where we have a white hat and the one where we have a black hat -- and they are equivalent (and so will be in the same equivalence class).
Now, using our infinite memory, we recall the particular assignment we picked out for this equivalence class (which we did in the last stage of preparation). The key here is that everyone will recall the same assignment.
We then report the colour assigned to us in this assignment. Because everyone recalled the same assignment, the reported assignment is the same as the assignment we recalled. And the assignment we recalled was in the same equivalence class as the current assignment, which means that only a finite number of people reported the wrong hat colour. Tada!
(Still don't buy it though)
|
On May 10 2009 12:50 drift0ut wrote:
for convenience label each of the ppl 1,2,3,... Now let a(i) be a sequence of 0's and 1's and we'll say that a(i)=0 if person i's hat is white, a(i)=1 if the persons hat is black.
For example a(i) is one way of giving out the hats a(1)=1 a(2)=0 a(3)=0 would be BWW
Let b(i) be the same as a(i) for a different way of handing out hats, so b(1)=1 b(2)=1 b(3)=1 would be BBB.
then we say a(i) "=" b(i) if and only if only finitely many of the ( a(i) - b(i) ) are not equal to 0.
(the collection of the x(i) which are "=" are the equivalence classes)
Now pick a list a(i), b(i), c(i),... so that a(i) is not "=" to b(i) or c(i) or d(i) etc and b(i) is not "=" to c(i) or ...
(forgive me for the implied countableness, (countable is a technical maths term))
now how ever i hand out the hats there will be a x(i) in the list such that x(i) is "=" to the way i hand out the hats. everybody shouts out the colour of hat they should have in x(i), and only finitly many will be wrong
This makes sense, that's quite interesting problem haha.
Let me explain it in a more basic terms so maybe non-math majors can comprehend it.
|
Help me understand. If one assignment had an infinite number of white hats, and another had an infinite number of white hats except for two black hats, would they be in the same equivalence class because only two people have changed, which is a finite amount? If so, would an assignment with an infinite number of white hats except for one black hat be in that equivalence class as well?
|
numLock: Yes all of those listed above are equivalent
Obviously you should fill your own math blog problems with more jargon evanthebouncy  . Then I might get a chance to answer them before tons of other people do. It would be nice if you occasionally posted some more difficult, technical, or less well-known problems given how quickly people are answering.
|
Edit: I'll start a new blog on this particular section...
First we'd like to understand what is equivalent class
Equivalent class is a way that you can use partitioning a set. It is useful because it let us look at a big, maybe confusing set, in smaller pieces called partitions by separating the big set into equivalent classes.
That's probably a lot of stuff so we start small:
What is a partition?
Say your set is a pizza, we can cut it into 4 slices, and that makes a "partition".
In a more precise term, a partition is an action, or a result of that action, on a set such that you divide the set into subsets, and when you concatenate all the subsets, you get the whole set back, and yet no subsets intersects each other.
Example:
Set A = {1 2 3 4 5 6}
A partition for set A can be:
{1 2 3} {4} {5 6}
{1 2 3 4 5 6}
A partition for set A cannot be:
{1 2 3} {4 6} (because concatenation does not reproduce the whole set back)
{1 2 3} {3 4 5 6} (because 3 is shared among 2 subsets)
More example:
A partition on all natural numbers N can be:
{1, 2, 3, 4, 5} {everything else}
{1 3 5 7 ... odd numbers} {2 4 6 8 ... even numbers}
Now let's move on to equivalence relation.
Remember in partition we're trying to divide a set into subsets? An equivalence relation helps us do that by saying:
element x and y are both in subset A if and only if x ~ y. The subset A is called an "Equivalent Class".
"~" means "equivalent relation", and "x~y" reads "x is equivalent of y"
Let's understand it.
The definition for ~ include 3 of the following properties:
reflexive: x~x is true
symmetric: if x~y, then y~x is true
transitive: if x~y, y~z, then x~z is true
Examples of equivalent relations:
1) x~y if they have the same age.
To check that 1) describe an equivalent relation, we'll check it against our 3 criterias:
-reflexive, is x~x true?
yes, x has the same age as x.
-symmetric, is x~y implies y~x?
yes, x has same age as y, then y has same age as x.
-transitive, is x~y, y~z implies x~z?
yes, x has same age as y, y has same age as z, then x has same age as z.
Therefore 1) describes a valid equivalent relation.
How do we use equivalent relation to form partitions?
By construction. This is how:
Say our set is A, and we wish to form a partition on A.
We first pick an element a in A.
Now we find all elements x such that a~x
Think of it as finding all the x that are related to a.
Put the a and all the x into a set, call it H_a
We then pick an element b in A, but not in H_a
Now we find all elements x such that b~x
Put everything in H_b
repeat the process until A becomes empty.
Now I claim that H_a, H_b, .... H_n is a partition of A. Do you trust me?
Probably not, so let's prove it:
To satisfy the partition requirement, we must show 2 things, that concatenating all the subsets reproduce A, and no 2 subsets have intersections.
Since we repeat the process until A becomes empty, then our H_a, H_b... must contains ALL the elements from A, therefore concactenating them back will give us all of A.
To show that no 2 subsets have intersections though, that might take some work. Let's prove that by contradiction:
Suppose some 2 subsets have an intersection, then pick an element x from that intersection. Now x is in both H_j and H_k (that's what it means by living in the intersection).
By our definition, x is related to everything in H_j since x in H_j by our construction means x is related to j, and j related to everything.
Then similarly, x is related to everything in H_k.
It follows that everything in H_k is related to everything in H_j, meaning that H_k and H_j would've been in the same subset to begin with, forming a contradiction.
So if you read through all that... let's try an example of forming such partitions by using equivalent classes:
Let the room be full of people {a, b, c, d, e, f, g, h}
Let a = 10 by age, and b = 11, c = 10, d = 11, e = 12, f = 10, g = 12, h = 11;
We let our equivalent relation be x~y if x y same age.
We pick an element from these people, let's say we picked b.
We now find everybody that are related to b, namely all people of age 11, so b, d, h.
We put all that into a subset H_b, and H_b = {b, d, h}
Now we find an element that's not in H_b, but still in our set, we settled with a.
Then find everybody related to a, {a, c, f}
Name our set H_a = {a, c, f}
Then find element e, and H_e = {e, g}
So we've exhausted set A, and now we formed a partition:
H_a, H_b, H_e
or
{a, c, f}, {b, d, h}, {e, g}
Where H_a is an equivalent class, H_b is an equivalent class, H_e is an equivalent class.
You should varify that this does indeed forms a valid partition.
If you followed everything in this post you should get some idea what is a partition and what is an equivalent relation, and what is an equivalent class, and how they are used to construct each other.
|
On May 10 2009 12:54 igotmyown wrote:Show nested quote +On May 10 2009 12:29 micronesia wrote:On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^ Can you explain what that means. Think of the people with white hats as a subset of the people. If two subsets only differ by finitely many elements, then we group those two sets together (into a set of subsets of the people). This is our equivalence relation. There's some conditions you have to prove about equivalence classes, but in this case it's easy enough not to be worth mentioning. In algebra, you can reduce a group with an equivalence class to the unique equivalence classes, for example, the integers by 0 mod p, 1 mod p, ..., p-1 mod p (or odds or evens if that's simpler) into p elements, hence the OP's solution motivated by n-dimensional vector spaces (where dividing the space by the equivalence class of lines is common). edit: oops solution is simpler than i thought. anyway, you have your equivalence classes of subsets. There are infinitely many, but that doesn't matter, and from each equivalence class, you choose one element, that is, one specific way of handing out hats. Since you've covered every equivalence class, any subset of the people will match to all but finitely many of one of the chosen elements. When the hats are handed out, you can see everybody else's hat, and your own hat can only increase the number of possible wrong matches by 1, so you know equivalence class that particular hat distribution is in. Everyone now votes their according to what their representative element would have as a hat.
I dont agree with the bold if there are infinitely many than there are an infinite number of errors. Just because you try to break up the infinite into chunks doesn't make it finite.
|
the way i got it was if i handed out all black hats apart from finitely many white hats it would be easy as everyone would shout black and only finitely many would be wrong. Or if i handed out all white apart from finitely many black it would be easy again as you'd shout out white and only that finite number with black hats would be wrong.
then suppose i handed out hats with the pattern black white black white ... all the way up to infinity (so black hats on odd numbers white hats on even numbers), apart from finitely many places where i brake the pattern and give a white where it should be black (or visa verse). then you should shout black if in the pattern you'd have a black hat (in an odd number) or white if in the pattern you'd have a white hat.
eg: bw bw bB bw bw
in this case the guy in the middle with a capital B would shout white and be wrong, but there would be only finitely many of these.
if that doesn't fit try a different pattern eg bbw bbw etc until you find a "pattern" that fits. I say "pattern" as it's not necessarily going to repeat its self it might be bw bbw bbbw bbbbw bbbbbw or something even more random.
now eventually you'll find a pattern where only finitely many are wrong (after all you'll eventually find the exact pattern that i handed them out in, altho that won't know you which colour you've got on) and that's what you shout out. This is where i used the axiom of choice because we need to agree which order you are going to check the patterns in.
|
While this has been attempted to be explained several times, I feel like the solution is still somewhat unclear.
What's happening is that first the prisoners look at the equivalence classes mentioned before, where two sequences are equivalent if they differ in a finite number of places. The only axiom of an equivalence relation that isn't obvious is the transitive property, which you can see that if a differs from b in some set of locations, and b differs from c in some other set of locations, a can only differ from c in a location where either a differs from b or b differs from c, which is still a finite number.
So then the axiom of choice guarantees the existence a choice function, that is if we have an equivalence class, we can plug it into the function and get a single element that is in that class. So the prisoners need to agree on a choice function beforehand. The key observation here is that seeing all but one hat determines the equivalence class of hats. So then what each prisoner does is he determines the equivalence class that the sequence of hats is in and plugs that class into the choice function. Then every prisoner will get the same sequence of hats out, since they agreed on a choice function beforehand, call it g(i). Then person i will guess g(i) for their hat color.
Now if a(i) is the actual sequence of hats, we know that a(i) and g(i) are in the same equivalence class, so they differ in only a finite number of locations, which means that only a finite number of people got it wrong.
|
On May 11 2009 00:23 drift0ut wrote:
the way i got it was if i handed out all black hats apart from finitely many white hats it would be easy as everyone would shout black and only finitely many would be wrong. Or if i handed out all white apart from finitely many black it would be easy again as you'd shout out white and only that finite number with black hats would be wrong.
then suppose i handed out hats with the pattern black white black white ... all the way up to infinity (so black hats on odd numbers white hats on even numbers), apart from finitely many places where i brake the pattern and give a white where it should be black (or visa verse). then you should shout black if in the pattern you'd have a black hat (in an odd number) or white if in the pattern you'd have a white hat.
eg: bw bw bB bw bw
in this case the guy in the middle with a capital B would shout white and be wrong, but there would be only finitely many of these.
if that doesn't fit try a different pattern eg bbw bbw etc until you find a "pattern" that fits. I say "pattern" as it's not necessarily going to repeat its self it might be bw bbw bbbw bbbbw bbbbbw or something even more random.
now eventually you'll find a pattern where only finitely many are wrong (after all you'll eventually find the exact pattern that i handed them out in, altho that won't know you which colour you've got on) and that's what you shout out. This is where i used the axiom of choice because we need to agree which order you are going to check the patterns in.
thats not finite you're going to break the pattern an infinite number of times.
|
This is dumb because there is no way you are going to have only a finite number of people get their color wrong. Even if only 1% get it wrong (which doesn't seem possible since they can't communicate with each other) then 1% of infinity is still infinity...
I read some of the posts explaining the answer... but I'm not that intelligent I guess... I mean assuming there is no pattern to the way the hats are distributed, and they can't hear the answer of the other prisoners then there is no way there can only be a finite number of incorrect answers.
|
Yeah I'm gonna have to agree with the argument that because there are infinity prisoners, the number of errors will always be a fraction of infinity, hence infinite. But hey, I'd love to see you prove me wrong
Edit:
By the way, big thanks to EvanTheBouncy for explaining the math
|
anyone claiming they understand set theory and that they have a strategy for prisoners does not understand set theory.
if each prisoner is randomly given either a black hat or a white hat, then the types of hats other's wear has no effect on their own, and since they can not communicate, they can do no better than guess randomly at their own hat. clearly on average half the prisoners would be wrong, and half of an infinite amount is still infinite. i assume the problem meant worst case, and if so that is even worse since there is no strategy that would GUARANTEE that even one prisoner is correct, even if it is infinitely likely.
this problem just shows that if you bury yourself in jargon that you don't understand you can prove anything you want and no one will be able to find a fault in your logic because it is nonsensical.
|
Haha... the funny thing is that while you are right that each prisoner has 1/2 probability of surviving, still only finitely many will die. Infinity is strange... this problem is basically the probability-theory version of the existence of non-measurable sets (look up Banach-Tarski paradox).
|
essentially the "solution" says that all people (or all except a finite amount, which is the same) should be able to recognise a pattern in the hat arrangement of the others (identify the equivalence class) and then they all should chose the same example which follows that pattern (member of that equivalence class).
especially the second part of this "solution" seems absolutely impossible. they can't have "pre-arranged" which member to chose for infinitely many equivalence classes - it would have required infinitely long time.
they can't possibly go with a general rule like "chose the blackest set" or something, because this would not be defined for all equivalence classes.
also there is this interesting paradox - assuming that they do have a "winning" strategy, does it matter if any specific person decides to alter that strategy by always saying "white" for himself? their strategy would've resulted in a finite number of differences before this alteration, so the new strategy would clearly also result in a finite number of differences. so it is still "winning". so any person can just say "white", and it wouldn't matter at all. yet clearly, if infinitely many people do this, they break their strategy.
all in all, i don't think this kind of math makes any sense :p
|
On May 13 2009 15:03 Muirhead wrote:
Haha... the funny thing is that while you are right that each prisoner has 1/2 probability of surviving, still only finitely many will die. Infinity is strange... this problem is basically the probability-theory version of the existence of non-measurable sets (look up Banach-Tarski paradox).
Another way to state this is that if you look at a finite subset of people, then only half of them will survive. However when you look at an infinite number, only finitely many will not survive.
That only means that the function Cardinal is not continuous on P(N)=2^N (with the tychonoff topology).
But this is very easy to see, if you have a sequence (X_n) where X_i \subset N, then you can define the inferior limit
X_inf=\cup_{k >= 0} \cap_{l >= k} X_l
and the superior limit
X_sup=\cap_{k >= 0} \cup_{l >= k} X_l
then X_inf is a subset of X_sup, and we say that X_n -> X if X_inf=X_sup=X.
Now if X_n=[0,n], X_n->N, but if X_n=[n,2n], X_n-> \emptyset. So you have two exemples of sets with n elements converging to completely different things.
|
On May 13 2009 16:42 georgir wrote:
especially the second part of this "solution" seems absolutely impossible. they can't have "pre-arranged" which member to chose for infinitely many equivalence classes - it would have required infinitely long time.
Well if we suppose that the function choosing the hats is constructive (ie in the constructible Godel universe), there is an explicit axiom of choice (because there is an explicit well ordering), so the choice of a representative is constructive (ie given by an explicit formula).
Of course in practise you can't look at an infinite number of hats, much less find a decreasing sequence for this well ordering...
|
On May 13 2009 15:03 Muirhead wrote:
Haha... the funny thing is that while you are right that each prisoner has 1/2 probability of surviving, still only finitely many will die. Infinity is strange... this problem is basically the probability-theory version of the existence of non-measurable sets (look up Banach-Tarski paradox).
shouldn't the banach-tarski paradox, which assumes the axiom of choice, disprove the axiom of choice? if you reach a contradiction then one of your assumptions is false. the B-T paradox is a contradiction because after each transformation the volume remains constant, yet after all transformations the volume has doubled.
|
On May 13 2009 22:01 flag wrote:Show nested quote +On May 13 2009 15:03 Muirhead wrote:
Haha... the funny thing is that while you are right that each prisoner has 1/2 probability of surviving, still only finitely many will die. Infinity is strange... this problem is basically the probability-theory version of the existence of non-measurable sets (look up Banach-Tarski paradox). shouldn't the banach-tarski paradox, which assumes the axiom of choice, disprove the axiom of choice? if you reach a contradiction then one of your assumptions is false. the B-T paradox is a contradiction because after each transformation the volume remains constant, yet after all transformations the volume has doubled.
You assume that the total volume of any two objects (subsets of R^3) should equal the sum of the two volumes. The Banach-Tarski paradox shows that this condition is impossible, there are (very weird) sets that will have different volumes depending on how you assemble them. So it's not a contradiction, it's your conception of volume that is wrong.
However this has nothing to do with objects in the real world, since all objects are made up of finitely many atoms, and all subsets of objects are very "nice" compared to all possible sets of objects in R^3.
|
|
|
|
|
|
EPT
