You are browsing as Guest
Click here for list of discussions
Click here to login





Discussion: AxiomOfChoice
You have read-only access
You may need to scroll to the right ...

Click here to view in strict time order
Click here to view in neighbourhood mode.

%3 N_20200219180055a_CDW    By CDW 2020/02/19 @ 18:00:55a -------------------------------- This was a problem, so all of set-theory was reinvented, very carefully, by Ernst Zermelo and Abraham Fraenkel.        (select only this node)     N_20200219180451a_CDW    By CDW 2020/02/19 @ 18:04:51a -------------------------------- The result is what we call ZF-Set Theory.        (select only this node)     N_20200219180055a_CDW->N_20200219180451a_CDW N_20200219180055b_CDW    By CDW 2020/02/19 @ 18:00:55b -------------------------------- They said exactly what you were and were not allowed to do, and managed to get a system that was powerful, but didn't have the Russell paradox.        (select only this node)     N_20200219180055a_CDW->N_20200219180055b_CDW N_20200219173547a_CDW    By CDW 2020/02/19 @ 17:35:47a -------------------------------- Maths Club talk: The Axiom of Choice        (select only this node)     N_20200219173547b_CDW    By CDW 2020/02/19 @ 17:35:47b -------------------------------- A "Set" is a collection of discrete objects        (select only this node)     N_20200219173547a_CDW->N_20200219173547b_CDW N_20200224211321a_CDW    By CDW 2020/02/24 @ 21:13:21a -------------------------------- Prompted by the comment here: https://twitter.com/Thalesdisciple/status/1227688946043211776        (select only this node)     N_20200219173547a_CDW->N_20200224211321a_CDW N_20200220100806a_CDW    By CDW 2020/02/20 @ 10:08:06a -------------------------------- Let's talk about "Hat Problems".        (select only this node)     N_20200219173547a_CDW->N_20200220100806a_CDW N_20200219180055c_CDW    By CDW 2020/02/19 @ 18:00:55c -------------------------------- But they did *not* say that you were arbitrarily allowed to have a choice set.        (select only this node)     N_20200219180055b_CDW->N_20200219180055c_CDW N_20200219173547c_CDW    By CDW 2020/02/19 @ 17:35:47c -------------------------------- When a set is finite we can talk about how many elements are in it.        (select only this node)     N_20200219173547b_CDW->N_20200219173547c_CDW N_20200219180055d_CDW    By CDW 2020/02/19 @ 18:00:55d -------------------------------- If there was a rule to choose a specific item from each set, that was fine.        (select only this node)     N_20200219180055c_CDW->N_20200219180055d_CDW N_20200219173742a_CDW    By CDW 2020/02/19 @ 17:37:42a -------------------------------- For a set X we write |X| to represent the number of elements in X.        (select only this node)     N_20200219173547c_CDW->N_20200219173742a_CDW N_20200219173547d_CDW    By CDW 2020/02/19 @ 17:35:47d -------------------------------- Take two finite sets, R and B, and suppose R has 3 elements and B has 4.        (select only this node)     N_20200219173547c_CDW->N_20200219173547d_CDW N_20200219180055e_CDW    By CDW 2020/02/19 @ 18:00:55e -------------------------------- But you weren't allowed simply to declare that you could create a set by choosing exactly one element from each of the sets you had in front of you.        (select only this node)     N_20200219180055d_CDW->N_20200219180055e_CDW N_20200219173547e_CDW    By CDW 2020/02/19 @ 17:35:47e -------------------------------- We can take the collection of pairs, where the 1st element is chosen from R and the second is chosen from B.        (select only this node)     N_20200219173547d_CDW->N_20200219173547e_CDW N_20200219173702a_CDW    By CDW 2020/02/19 @ 17:37:02a -------------------------------- The mnemonic here is that R is red, which has three letters, B is blue, and later G is green.        (select only this node)     N_20200219173547d_CDW->N_20200219173702a_CDW N_20200219180413a_CDW    By CDW 2020/02/19 @ 18:04:13a -------------------------------- So let's add that in as an axiom. After all, what could *possibly* go wrong.        (select only this node)     N_20200219180055e_CDW->N_20200219180413a_CDW N_20200219173547f_CDW    By CDW 2020/02/19 @ 17:35:47f -------------------------------- How many pairs do we get?        (select only this node)     N_20200219173547e_CDW->N_20200219173547f_CDW N_20200219180250a_CDW    By CDW 2020/02/19 @ 18:02:50a -------------------------------- Given a collection of sets, a set consisting of exactly one element chosen from each of them is called a "Choice Set".        (select only this node)     N_20200219180250b_CDW    By CDW 2020/02/19 @ 18:02:50b -------------------------------- The product of a collection of sets is the collection of all possible choice sets.        (select only this node)     N_20200219180250a_CDW->N_20200219180250b_CDW N_20200219173547g_CDW    By CDW 2020/02/19 @ 17:35:47g -------------------------------- 12, because there are three choices for the first item in a pair, and for each of those there are then four choices for the second item.        (select only this node)     N_20200219173547f_CDW->N_20200219173547g_CDW N_20200219180250c_CDW    By CDW 2020/02/19 @ 18:02:50c -------------------------------- (Yes, this gets *very* meta)        (select only this node)     N_20200219173547h_CDW    By CDW 2020/02/19 @ 17:35:47h -------------------------------- Now |R| x |B| = 12, so there is some motivation to refer to the collection of pairs as RxB.        (select only this node)     N_20200219173547g_CDW->N_20200219173547h_CDW N_20200219180250b_CDW->N_20200219180250c_CDW N_20200219173547i_CDW    By CDW 2020/02/19 @ 17:35:47i -------------------------------- Then the size of the product is the product of the sizes.        (select only this node)     N_20200219173547h_CDW->N_20200219173547i_CDW N_20200219180413b_CDW    By CDW 2020/02/19 @ 18:04:13b -------------------------------- Well, the answer is that nothing goes wrong, as such, but you do have to live with the consequences, and some of those consequences are truly bizarre        (select only this node)     N_20200219180413a_CDW->N_20200219180413b_CDW N_20200220104542a_CDW    By CDW 2020/02/20 @ 10:45:42a -------------------------------- With the Axiom of Choice, we can guarantee that only finitely many prisoners end up in prison.        (select only this node)     N_20200219180413a_CDW->N_20200220104542a_CDW N_20200219180519a_CDW    By CDW 2020/02/19 @ 18:05:19a -------------------------------- The result is what we call ZFC Set Theory.        (select only this node)     N_20200219180413a_CDW->N_20200219180519a_CDW N_20200219181702a_CDW    By CDW 2020/02/19 @ 18:17:02a -------------------------------- The alternative is to allow that the product of non-empty sets can be empty. That just seems ... perverse.        (select only this node)     N_20200219180413a_CDW->N_20200219181702a_CDW N_20200219173547j_CDW    By CDW 2020/02/19 @ 17:35:47j -------------------------------- Let's take another set, G, with 5 elements.        (select only this node)     N_20200219173547i_CDW->N_20200219173547j_CDW N_20200219180904a_CDW    By CDW 2020/02/19 @ 18:09:04a -------------------------------- So |RxB| = |R|x|B|        (select only this node)     N_20200219173547i_CDW->N_20200219180904a_CDW N_20200220104542c_CDW    By CDW 2020/02/20 @ 10:45:42c -------------------------------- So even though no prisoner can possibly know anything about their own hat, only finitely many get it wrong.        (select only this node)     N_20200219180413b_CDW->N_20200220104542c_CDW N_20200219221653a_CDW    By CDW 2020/02/19 @ 22:16:53a -------------------------------- So now |G|=5        (select only this node)     N_20200219173547j_CDW->N_20200219221653a_CDW N_20200219173547k_CDW    By CDW 2020/02/19 @ 17:35:47k -------------------------------- We can consider (RxB)xG and Rx(BxG) ... there's a nice mapping between these.        (select only this node)     N_20200219173547j_CDW->N_20200219173547k_CDW N_20200219180451a_CDW->N_20200219180519a_CDW N_20200219173547l_CDW    By CDW 2020/02/19 @ 17:35:47l -------------------------------- They're not the same, but they can be matched against each other in a "natural" way.        (select only this node)     N_20200219173547k_CDW->N_20200219173547l_CDW N_20200219173547m_CDW    By CDW 2020/02/19 @ 17:35:47m -------------------------------- They can also be matched with the collection of triples        (select only this node)     N_20200219173547l_CDW->N_20200219173547m_CDW N_20200219181525c_CDW    By CDW 2020/02/19 @ 18:15:25c -------------------------------- When giving maths club talks I often say at the beginning that I will gloss over some technicalities, and if anyone spots what seems to be a problem then we can take time to explore it.        (select only this node)     N_20200219173547n_CDW    By CDW 2020/02/19 @ 17:35:47n -------------------------------- So we might choose to call the collection of triples RxBxG.        (select only this node)     N_20200219173547m_CDW->N_20200219173547n_CDW N_20200219173547o_CDW    By CDW 2020/02/19 @ 17:35:47o -------------------------------- So (RxB)xG <--> RxBxG <--> Rx(BxG).        (select only this node)     N_20200219173547n_CDW->N_20200219173547o_CDW N_20200219173547p_CDW    By CDW 2020/02/19 @ 17:35:47p -------------------------------- Similarly, RxB -- BxR, and everything is nice.        (select only this node)     N_20200219173547o_CDW->N_20200219173547p_CDW N_20200220103043a_CDW    By CDW 2020/02/20 @ 10:30:43a -------------------------------- Here's another example:        (select only this node)     N_20200220100806a_CDW->N_20200220103043a_CDW N_20200220102357a_CDW    By CDW 2020/02/20 @ 10:23:57a -------------------------------- Here's another example:        (select only this node)     N_20200220100806a_CDW->N_20200220102357a_CDW N_20200220101340a_CDW    By CDW 2020/02/20 @ 10:13:40a -------------------------------- Here's an example.        (select only this node)     N_20200220100806a_CDW->N_20200220101340a_CDW N_20200220100806b_CDW    By CDW 2020/02/20 @ 10:08:06b -------------------------------- Some people hate "Hat Problems", other people are intrigued by them.        (select only this node)     N_20200220100806a_CDW->N_20200220100806b_CDW N_20200220103729a_CDW    By CDW 2020/02/20 @ 10:37:29a -------------------------------- Here's the example we want to work with ...        (select only this node)     N_20200220100806a_CDW->N_20200220103729a_CDW N_20200219173917a_CDW    By CDW 2020/02/19 @ 17:39:17a -------------------------------- So we call the collection of pairs RxB the *product* of R and B.        (select only this node)     N_20200219173547p_CDW->N_20200219173917a_CDW N_20200220100806c_CDW    By CDW 2020/02/20 @ 10:08:06c -------------------------------- Even if you don't like them, stay with me, they can be a useful vehicle for talking about various things.        (select only this node)     N_20200220100806b_CDW->N_20200220100806c_CDW N_20200219180819a_CDW    By CDW 2020/02/19 @ 18:08:19a -------------------------------- So |R|=3 and |B|=4        (select only this node)     N_20200219173702a_CDW->N_20200219180819a_CDW N_20200219173742a_CDW->N_20200219180819a_CDW N_20200220101340b_CDW    By CDW 2020/02/20 @ 10:13:40b -------------------------------- Three players are told that each of them will receive either a red hat or a blue hat.  They are to raise their hands if they see a red hat on another player as they stand in a circle facing each other. The first correctly to state the colour of their hat wins.        (select only this node)     N_20200220101340a_CDW->N_20200220101340b_CDW N_20200220101340a_CDW->N_20200220102357a_CDW N_20200219174106a_CDW    By CDW 2020/02/19 @ 17:41:06a -------------------------------- Conveniently (because that's the way we've defined things) the product of the sizes is the size of the product.        (select only this node)     N_20200219173917a_CDW->N_20200219174106a_CDW N_20200220101340c_CDW    By CDW 2020/02/20 @ 10:13:40c -------------------------------- All the players raise their hands. After the players have seen each other for a few minutes without guessing, one player announces "Red", and wins.  How did the winner do it, and what is the colour of everyone's hats?        (select only this node)     N_20200220101340b_CDW->N_20200220101340c_CDW N_20200219174106b_CDW    By CDW 2020/02/19 @ 17:41:06b -------------------------------- We can extend this to any finite number of sets, and all is well.        (select only this node)     N_20200219174106a_CDW->N_20200219174106b_CDW N_20200220101340d_CDW    By CDW 2020/02/20 @ 10:13:40d -------------------------------- First, if two people had blue hats, not everyone's hand would have been raised.        (select only this node)     N_20200220101340c_CDW->N_20200220101340d_CDW N_20200219174106d_CDW    By CDW 2020/02/19 @ 17:41:06d -------------------------------- Fairly obviously, if one the sets is empty then the product of the sets will be empty        (select only this node)     N_20200219174106b_CDW->N_20200219174106d_CDW N_20200219174106c_CDW    By CDW 2020/02/19 @ 17:41:06c -------------------------------- Fairly obviously, if all the sets are non-empty then the product of the sets will be non-empty.        (select only this node)     N_20200219174106b_CDW->N_20200219174106c_CDW N_20200220101340e_CDW    By CDW 2020/02/20 @ 10:13:40e -------------------------------- Next, if player 1 had seen a blue hat on player 2 and a red hat on player 3, then player 1 would immediately have known that their own hat must be red.        (select only this node)     N_20200220101340d_CDW->N_20200220101340e_CDW N_20200219175040a_CDW    By CDW 2020/02/19 @ 17:50:40a -------------------------------- This all seems reasonable, but what if we have infinitely many sets?        (select only this node)     N_20200219174106c_CDW->N_20200219175040a_CDW N_20200220101340f_CDW    By CDW 2020/02/20 @ 10:13:40f -------------------------------- Thus any player who sees a blue hat can guess at once.        (select only this node)     N_20200220101340e_CDW->N_20200220101340f_CDW N_20200219174106d_CDW->N_20200219175040a_CDW N_20200220101340g_CDW    By CDW 2020/02/20 @ 10:13:40g -------------------------------- Finally, the winner realizes that since no one guesses at once, there must be no blue hats, so every hat must be red.        (select only this node)     N_20200220101340f_CDW->N_20200220101340g_CDW N_20200219175040b_CDW    By CDW 2020/02/19 @ 17:50:40b -------------------------------- Suppose we have a set containing a head and a tail, and the set is labelled 0.        (select only this node)     N_20200219175040a_CDW->N_20200219175040b_CDW N_20200220111042a_CDW    By CDW 2020/02/20 @ 11:10:42a -------------------------------- There are dozens more "Hat Puzzles"        (select only this node)     N_20200220101340g_CDW->N_20200220111042a_CDW N_20200219181330a_CDW    By CDW 2020/02/19 @ 18:13:30a -------------------------------- A small technicality ... we want the sets all to be disjoint, so the elements in S0 we call H0 and T0.        (select only this node)     N_20200219175040b_CDW->N_20200219181330a_CDW N_20200219175040c_CDW    By CDW 2020/02/19 @ 17:50:40c -------------------------------- The another set containing a head and a tail, but that set is labelled 1.        (select only this node)     N_20200219175040b_CDW->N_20200219175040c_CDW N_20200220102357b_CDW    By CDW 2020/02/20 @ 10:23:57b -------------------------------- Four prisoners are arrested for a crime, but the jail is full and the jailer has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed.        (select only this node)     N_20200220102357a_CDW->N_20200220102357b_CDW N_20200220102357a_CDW->N_20200220103043a_CDW N_20200219175040d_CDW    By CDW 2020/02/19 @ 17:50:40d -------------------------------- And another labelled 2, and so on.        (select only this node)     N_20200219175040c_CDW->N_20200219175040d_CDW N_20200219175040c_CDW->N_20200219181330a_CDW N_20200220102357c_CDW    By CDW 2020/02/20 @ 10:23:57c -------------------------------- The jailer seats three of the prisoners in a line. B faces the wall, C faces B, and D faces C and B. The fourth prisoner, A, is put in a separate room.        (select only this node)     N_20200220102357b_CDW->N_20200220102357c_CDW N_20200219175040e_CDW    By CDW 2020/02/19 @ 17:50:40e -------------------------------- So we have S0, S1, S2, ..., and we ask, what is the product of all these sets?        (select only this node)     N_20200219175040d_CDW->N_20200219175040e_CDW N_20200219181525a_CDW    By CDW 2020/02/19 @ 18:15:25a -------------------------------- And the Head and Tail from 1 we call H1 and T1, and from 2 we call H2 and T2, and so on.        (select only this node)     N_20200219175040d_CDW->N_20200219181525a_CDW N_20200220102357d_CDW    By CDW 2020/02/20 @ 10:23:57d -------------------------------- The jailer gives all four of them party hats. He explains that there are two black hats and two white hats, that each prisoner is wearing one of the hats, and that each of the prisoners can see only the hats in front of them but neither on themselves nor behind. Prisoner A can't see or be seen by any other prisoner. No communication among the prisoners is allowed.        (select only this node)     N_20200220102357c_CDW->N_20200220102357d_CDW N_20200219175040f_CDW    By CDW 2020/02/19 @ 17:50:40f -------------------------------- By analogy, what we would do is look at all the ways we can choose one thing from each set.        (select only this node)     N_20200219175040e_CDW->N_20200219175040f_CDW N_20200220102357e_CDW    By CDW 2020/02/20 @ 10:23:57e -------------------------------- If any prisoner can figure out their colour of hat with 100% certainty, they can announce it, and all four prisoners will go free. If any prisoner suggests an incorrect answer, all four prisoners are executed.        (select only this node)     N_20200220102357d_CDW->N_20200220102357e_CDW N_20200219175040g_CDW    By CDW 2020/02/19 @ 17:50:40g -------------------------------- Clearly the result would be an infinite set, and we can't talk about "How many elements there are" in the same way as we can with finite sets.        (select only this node)     N_20200219175040f_CDW->N_20200219175040g_CDW N_20200220102357f_CDW    By CDW 2020/02/20 @ 10:23:57f -------------------------------- The puzzle is to find how the prisoners can escape.        (select only this node)     N_20200220102357e_CDW->N_20200220102357f_CDW N_20200219175040h_CDW    By CDW 2020/02/19 @ 17:50:40h -------------------------------- Even so, it looks reasonable.        (select only this node)     N_20200219175040g_CDW->N_20200219175040h_CDW N_20200220102357f_CDW->N_20200220111042a_CDW N_20200219175350a_CDW    By CDW 2020/02/19 @ 17:53:50a -------------------------------- So it seems reasonable to say this:        (select only this node)     N_20200219175040h_CDW->N_20200219175350a_CDW N_20200220103043a_CDW->N_20200220103729a_CDW N_20200220103043b_CDW    By CDW 2020/02/20 @ 10:30:43b -------------------------------- There are 10 prisoners, each assigned a random hat, either red or blue, but the number of each colour hat is not known to the prisoners.        (select only this node)     N_20200220103043a_CDW->N_20200220103043b_CDW N_20200219175350b_CDW    By CDW 2020/02/19 @ 17:53:50b -------------------------------- Here's a collection of non-empty sets. Let's choose one element from each of them, and put into a collection all the possible outcomes of doing so. The resulting collection is what we call the *product* of all those sets.        (select only this node)     N_20200219175350a_CDW->N_20200219175350b_CDW N_20200220103043c_CDW    By CDW 2020/02/20 @ 10:30:43c -------------------------------- The prisoners will be lined up single file where each can see the hats in front of him but not behind.        (select only this node)     N_20200220103043b_CDW->N_20200220103043c_CDW N_20200219175350b_CDW->N_20200219180250a_CDW N_20200219175705a_CDW    By CDW 2020/02/19 @ 17:57:05a -------------------------------- This is reasonable for a *finite* collection of sets, and it looks reasonable for an *infinite* collection of sets, but there's a snag.        (select only this node)     N_20200219175350b_CDW->N_20200219175705a_CDW N_20200220103043d_CDW    By CDW 2020/02/20 @ 10:30:43d -------------------------------- Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue".        (select only this node)     N_20200220103043c_CDW->N_20200220103043d_CDW N_20200219175705b_CDW    By CDW 2020/02/19 @ 17:57:05b -------------------------------- Way back in 1901, Bertrand Russell found a paradox in set theory.        (select only this node)     N_20200219175705a_CDW->N_20200219175705b_CDW N_20200220103043e_CDW    By CDW 2020/02/20 @ 10:30:43e -------------------------------- If the word matches their hat colour they are released, if not, they are killed on the spot.        (select only this node)     N_20200220103043d_CDW->N_20200220103043e_CDW N_20200219175705c_CDW    By CDW 2020/02/19 @ 17:57:05c -------------------------------- He defined a set *R* as being all those sets that do not contain themselves, and asked: Does R contain R?        (select only this node)     N_20200219175705b_CDW->N_20200219175705c_CDW N_20200220103043f_CDW    By CDW 2020/02/20 @ 10:30:43f -------------------------------- It's easy enough to guarantee 50% survival rate, the odd numbered prisoners say the colour of the next person.        (select only this node)     N_20200220103043e_CDW->N_20200220103043f_CDW N_20200219175705d_CDW    By CDW 2020/02/19 @ 17:57:05d -------------------------------- If R contains R then that means that it belongs in R, and R contains things that do not contain themselves, so it can't be in R.        (select only this node)     N_20200219175705c_CDW->N_20200219175705d_CDW N_20200219175705e_CDW    By CDW 2020/02/19 @ 17:57:05e -------------------------------- If R does not contain R then that means it satisfies the condition to be in R, so it is in R.        (select only this node)     N_20200219175705c_CDW->N_20200219175705e_CDW N_20200220103043g_CDW    By CDW 2020/02/20 @ 10:30:43g -------------------------------- However, there is a plan that lets 9 of the 10 definitely survive, and 1 has a 50/50 chance of survival.        (select only this node)     N_20200220103043f_CDW->N_20200220103043g_CDW N_20200219175705f_CDW    By CDW 2020/02/19 @ 17:57:05f -------------------------------- Paradox.        (select only this node)     N_20200219175705d_CDW->N_20200219175705f_CDW N_20200220103043h_CDW    By CDW 2020/02/20 @ 10:30:43h -------------------------------- What is the plan to achieve the goal?        (select only this node)     N_20200220103043g_CDW->N_20200220103043h_CDW N_20200219175705e_CDW->N_20200219175705f_CDW N_20200220103043h_CDW->N_20200220111042a_CDW N_20200219175705f_CDW->N_20200219180055a_CDW N_20200219180819a_CDW->N_20200219221653a_CDW N_20200220103729b_CDW    By CDW 2020/02/20 @ 10:37:29b -------------------------------- Prisoners file into a room, one by one, and each given a number and a hat as they enter.        (select only this node)     N_20200220103729a_CDW->N_20200220103729b_CDW N_20200220103729c_CDW    By CDW 2020/02/20 @ 10:37:29c -------------------------------- The numbers are consecutive positive integers, and the hat is either red or blue.        (select only this node)     N_20200220103729b_CDW->N_20200220103729c_CDW N_20200219181330a_CDW->N_20200219181525a_CDW N_20200220103729d_CDW    By CDW 2020/02/20 @ 10:37:29d -------------------------------- No prisoner can see their own hat, but they can see everyone else's hat, and everyone else's number.        (select only this node)     N_20200220103729c_CDW->N_20200220103729d_CDW N_20200219181525b_CDW    By CDW 2020/02/19 @ 18:15:25b -------------------------------- As I say, this is a technicality, but it can prove important.        (select only this node)     N_20200219181525a_CDW->N_20200219181525b_CDW N_20200220103729e_CDW    By CDW 2020/02/20 @ 10:37:29e -------------------------------- So they can deduce their own number, but they can't deduce their own hat colour.        (select only this node)     N_20200220103729d_CDW->N_20200220103729e_CDW N_20200219181525b_CDW->N_20200219181525c_CDW N_20200220103729f_CDW    By CDW 2020/02/20 @ 10:37:29f -------------------------------- They are *not* permitted to communicate ... no cheating!        (select only this node)     N_20200220103729e_CDW->N_20200220103729f_CDW N_20200220103729g_CDW    By CDW 2020/02/20 @ 10:37:29g -------------------------------- They *did* know in advance what was going to happen, and they are *all* infinitely intelligent.        (select only this node)     N_20200220103729f_CDW->N_20200220103729g_CDW N_20200220103729h_CDW    By CDW 2020/02/20 @ 10:37:29h -------------------------------- After a time they are each taken to a separate room and asked the colour of their hat.  Anyone who gets it right is released, but get it wrong and it's life in prison.        (select only this node)     N_20200220103729g_CDW->N_20200220103729h_CDW N_20200220103729i_CDW    By CDW 2020/02/20 @ 10:37:29i -------------------------------- If the announcements are audible to the remaining prisoners then we can ensure that "half" of the prisoners are released.        (select only this node)     N_20200220103729h_CDW->N_20200220103729i_CDW N_20200220104157a_CDW    By CDW 2020/02/20 @ 10:41:57a -------------------------------- Being in a separate room, no prisoners can hear what any other prisoner is saying.        (select only this node)     N_20200220103729h_CDW->N_20200220104157a_CDW N_20200220103958a_CDW    By CDW 2020/02/20 @ 10:39:58a -------------------------------- We need to be careful about what we mean by "half".        (select only this node)     N_20200220103729i_CDW->N_20200220103958a_CDW N_20200220103729j_CDW    By CDW 2020/02/20 @ 10:37:29j -------------------------------- The odd-numbered prisoners say the colour of the next prisoner, and so the even numbered prisoners go free.        (select only this node)     N_20200220103729i_CDW->N_20200220103729j_CDW N_20200220105131a_CDW    By CDW 2020/02/20 @ 10:51:31a -------------------------------- Each odd-numbered prisoner has a 50:50 chance, so on average, as we go, at any moment, about 75% of the prisoners will be released.        (select only this node)     N_20200220103729j_CDW->N_20200220105131a_CDW N_20200220103958b_CDW    By CDW 2020/02/20 @ 10:39:58b -------------------------------- In this case, at any time we have examined finitely many prisoners, and half of them are guaranteed to have been released.        (select only this node)     N_20200220103958a_CDW->N_20200220103958b_CDW N_20200220105235a_CDW    By CDW 2020/02/20 @ 10:52:35a -------------------------------- But this is only if the even-numbered prisoners can hear the previous prisoner.        (select only this node)     N_20200220103958b_CDW->N_20200220105235a_CDW N_20200220104157a_CDW->N_20200220103729i_CDW N_20200220104157b_CDW    By CDW 2020/02/20 @ 10:41:57b -------------------------------- The situation seems hopeless.        (select only this node)     N_20200220104157a_CDW->N_20200220104157b_CDW N_20200220104157c_CDW    By CDW 2020/02/20 @ 10:41:57c -------------------------------- Take some time.  The colour of hat was random ... how then can a prisoner know anything at all about their hat?        (select only this node)     N_20200220104157b_CDW->N_20200220104157c_CDW N_20200220104157d_CDW    By CDW 2020/02/20 @ 10:41:57d -------------------------------- Clearly they can't.        (select only this node)     N_20200220104157c_CDW->N_20200220104157d_CDW N_20200220104157e_CDW    By CDW 2020/02/20 @ 10:41:57e -------------------------------- Well ...        (select only this node)     N_20200220104157d_CDW->N_20200220104157e_CDW N_20200220104335a_CDW    By CDW 2020/02/20 @ 10:43:35a -------------------------------- Funny you should say that.        (select only this node)     N_20200220104157e_CDW->N_20200220104335a_CDW N_20200220104335a_CDW->N_20200220104542a_CDW N_20200220104542b_CDW    By CDW 2020/02/20 @ 10:45:42b -------------------------------- All but finitely many prisoners are released.        (select only this node)     N_20200220104542a_CDW->N_20200220104542b_CDW N_20200220104542b_CDW->N_20200220104542c_CDW N_20200220110130a_CDW    By CDW 2020/02/20 @ 11:01:30a -------------------------------- In Summary:        (select only this node)     N_20200220104542c_CDW->N_20200220110130a_CDW N_20200220105131a_CDW->N_20200220105235a_CDW N_20200220105334a_CDW    By CDW 2020/02/20 @ 10:53:34a -------------------------------- But if the announcements are private, inaudible, unavailable to the next prisoner ...        (select only this node)     N_20200220105235a_CDW->N_20200220105334a_CDW N_20200220105334a_CDW->N_20200220104157b_CDW N_20200220110130d_CDW    By CDW 2020/02/20 @ 11:01:30d -------------------------------- Accept that the Axiom of Choice is False.        (select only this node)     N_20200220110130a_CDW->N_20200220110130d_CDW N_20200220110130b_CDW    By CDW 2020/02/20 @ 11:01:30b -------------------------------- Accept that the Axiom of Choice is True.        (select only this node)     N_20200220110130a_CDW->N_20200220110130b_CDW N_20200220110130c_CDW    By CDW 2020/02/20 @ 11:01:30c -------------------------------- Then prisoners can somehow magically state the colour of their hat, even though they know nothing about it.        (select only this node)     N_20200220110130b_CDW->N_20200220110130c_CDW N_20200220110130f_CDW    By CDW 2020/02/20 @ 11:01:30f -------------------------------- Your choice ...        (select only this node)     N_20200220110130c_CDW->N_20200220110130f_CDW N_20200220110130e_CDW    By CDW 2020/02/20 @ 11:01:30e -------------------------------- Then the product of sets that are non-empty might, actually, turn out to be empty.        (select only this node)     N_20200220110130d_CDW->N_20200220110130e_CDW N_20200220110130e_CDW->N_20200220110130f_CDW N_20200220111042b_CDW    By CDW 2020/02/20 @ 11:10:42b -------------------------------- https://en.wikipedia.org/wiki/Hat_puzzle        (select only this node)     N_20200220111042a_CDW->N_20200220111042b_CDW