These fields are all optional and need only be supplied if you would like a direct reply. Subject Your email address Your real name

You must answer this! If you don't, my spam filtering will ensure that I never see your email. What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.
File: APointAgainstTheAxiomOfChoice ''' <link rel="alternate" type="application/rss+xml" ''' href="/rss.xml" title="RSS Feed"> ********> width="25%" |>> ''' <a title="Subscribe to my feed" ''' rel="alternate" ''' href="https://www.solipsys.co.uk/rss.xml"> ''' <img style="border-width: 0px;" ''' src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png" ''' align="middle" ''' alt="" />Subscribe!</a> _ ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> <<| ---- My latest posts can be found here: * ColinsBlog ---- Previous blog posts: * InDefenseOfTheAxiomOfChoice * JourneyingHomeThroughStormDennis * EarthRadiusRefined * VolumeOfASphere * BigOhAndRelations * MathematicalRelations * IntroducingBigOh * ConstantDifferences * AlgorithmsAndSizesOfInstances * IntroducingTimeComplexity * TheLinearFrog * SeventyVersusOneHundredRevisited * HowTheFarragoWorks * SeventyVersusOneHundred * PowersOfTwoInLexOrder * EmergingEExpanded * RageInducingSystemImplementation * TheBookIsNotAlwaysRight * EmergingE * ImpossibleToTranslate * WaitingInVain * NonRepeatingDecimals * RationalRepeats * WhyIsItLovely * CompilingCryptoConnections * ExploringConnectionsBetweenCryptoSystems * ElwynBerlekampHasLeftUs * RootCauseAnalysisAndThePhotocopierQuestion * TheUpDownTides * TheForeAftTide * TheSidewaysTide * WrappingUpWrappingUpTheEarth * TheOtherWrappingTheEarthProblem * WrappingTheEarth * TheRingOfSteel * RoundingUpTheRopes * OtherOtherOtherRopeAroundTheEarth * RopeAroundTheEarthRefined * TheOtherRopeAroundTheEarth * ElementaryEstimates * LatitudeCorrection * JustGiveMeTheAnswer * MoreMusingOnPollardRho * IdleThoughtsAboutPollardRho * WhenOptimisingCodeMeasure * ADogCalledMixture * AnotherPayPalScam * WhyTopPostingHasWon * UnexpectedInteractionOfFeatures * ArchimedesHatBoxTheorem * ConsideringASphere * ToLinkOrNotToLink * GenericAdviceForWritingAThesis * JustTeachMyChildTheMaths * NotASpectatorSport * LeftTruncatablePrime * TheDoctorAndTheLawyer * FourPointsTwoDistancesProof * MeetingRonGraham * NapkinRingVersusSphericalCap * TheFourPointsPuzzle * RadiusOfTheEarthPartTwo * GrepTimingAnomaly * TheRadiusOfTheEarth * ThisWorksToCureMyHiccoughs * PerhapsWeSavedOne * ThinkingAboutMastodon * DisappearingTrainsOnVirgin * TheIndependenceGame * OneOfMyFavouritePuzzles * ThinkingAboutRecursion * MemorisingTheTube * SpikeySpheres * SurprisinglyQuick * AnUnexpectedFraction * YouHaveToAdmireTheirOptimism * RepresentativesMatter * PythagorasByIncircle * APuzzleAboutPuzzles * HowNotToDoTwitter * Calculating52FactorialByHand * SmallThingsMightNotBeSoSmall * NotIfYouHurry * FactoringViaGraphThreeColouring * AnotherProofOfTheDoodleTheorem * WhenObviousIsNotObvious * GraphThreeColouring * TheDoodleTheorem * BeCarefulWhatYouSay * TheMutilatedChessboardRevisited * AMirrorCopied * TheOtherOtherRopeAroundTheEarth * PhotocopyAMirror * ThePointOfTheBanachTarskiTheorem * SieveOfEratosthenesInPython * FastPerrinTest * RussianPeasantMultiplication * FindingPerrinPseudoPrimes_Part2 * FindingPerrinPseudoPrimes_Part1 * TheUnwiseUpdate * MilesPerGallon * TrackingAnItemOnHackerNews * HackerNewsUserAges * PokingTheDustyCorners * ThereIsNoTimeForThis * PublicallySharingLinks * LearningTimesTables * GracefulDegradation * DiagrammingMathsTopics * OnTheRack * SquareRootByLongDivision * BeyondTheBoundary * FillInTheGaps * SoftwareChecklist * NASASpaceCrews * TheBirthdayParadox * TheTrapeziumConundrum * RevisitingTheAnt * TheAntAndTheRubberBand * IrrationalsExist * MultipleChoiceProbabilityPuzzle * RandomEratosthenes * WrappingUpSquareDissection * DissectingASquarePart2 * DissectingACircle * DissectingASquare * AnOddityInTennis * DecisionTreeForTennis * DecisionTreesInGames * AMatterOfConvention * DoYouNourishOrTarnish * BinarySearchReconsidered * TwoEqualsFour * TheLostPropertyOffice * TheForgivingUserInterface * SettingUpRSS * WithdrawingFromHackerNews ---- Additionally, some earlier writings: * RandomWritings. * ColinsBlog2010 * ColinsBlog2009 * ColinsBlog2008 * ColinsBlog2007 * ColinsBlogBefore2007 ******** [[[> This page has been _ TaggedAsMaths ]]] Last time we looked at why the AxiomOfChoice seems so reasonable. * InDefenseOfTheAxiomOfChoice One formulation is to say that the product of non-empty sets is always non-empty, and that sounds so obvious. Let's see what this leads to ... !! A Four Hat Problem. There are several formulation of this one. [[[> |>> https://www.solipsys.co.uk/images/FourHats.png ---- Four Hats <<| ]]] Suppose we have four people, and four hats. Two of the hats are white and two are black. Three people are lined up, one in front of the other, the front most facing a wall. So the rear-most of these three can see two people in front of them, the middle can see only the person in front, and the front-most can't see anyone. The fourth person is in a separate room. No one can see their own hat, but each person can see the hats of anyone in front of them. Remember, two hats of each colour. The people are challenged to announce the colour of their own hat. If someone succeeds, they all get rewarded handsomely and released from this bizarre situation. But it must be the *first* thing they say, and the consequences of getting it wrong are unspoken, but dire. Can anyone work out the colour of their hat? !! A hint ... Silence is a clue ... A solution is later. !! Another Hat Problem. Now suppose we have 100 people in a row, all facing forward, all wearing a hat that's either black or white. Each one, starting from the back, is asked their hat colour. They announce it loudly enough for everyone to hear, and the others also hear whether they got it right or wrong. How many can we save? We can easily save half the people by having the odd-numbered candidates announce the colour of the person in front of them, and the even-numbered ones repeating that answer. If the hats are random then we can save about 75%, but maybe we can do better ... Yes we can ... the answer appears further down the page. !! Meta-analysis ... In each of these cases the "contestants" are gaining information by being able to hear other people's responses. So people can somehow encode information for others to act on, and we can save more than the average "half". But what if people *can't* hear what others say? There is still hope. Even if people *can't* hear what others say, people can pair off, and each then looks at their partner's hat. One can say the colour of their partner's hat, and the other can say the opposite of their partner's hat. Now even if they speak simultaneously, or if they are taken out an asked when no one can hear what they say, nevertheless we are guaranteed to save exactly one of each pair ... you might want to see why that is true. Hmm. !! Infinitely many people ... There are many, many variants of hat problems, but this has set the scene, so I'll jump straight to the version of interest. We have countably many mathematicians who are all blessed with an infinite memory. They are told what will happen beforehand, so they can all discuss their strategy, and then commit it to memory. And here's what will happen. They will be brought into a room, one-by-one, and given a sequence number as they go, starting with 1 and including all the positive integers. As they enter the room a coin will be flipped (although the administrator might cheat!) and that determines whether they get a black hat or a white hat. Communication is forbidden, but each person can see everyone else, both their number and the colour of their hat. Then, one by one, in sequence, they are taken back out of the room and asked the colour of their hat. If they are right they are released. If they are wrong they are incarcerated forever. And no one in the big room knows the fate of those who go before. So think about that for a bit. Each person has no information about the hat on their own head, and they gain no information for the answers of the others. The only information they have is the colour of everyone else's hat. [[[>50 We will see a little further down that if we have $n$ people *and* they can hear everyone else's answers then we can guarantee saving $n-1$ people. But here, no one can hear any answers. ]]] How can we possibly guarantee anyone's survival? Surely each person has a 50:50 chance. The situation seems hopeless. Read on ... !! Solution to the Four Hat Problem. [[[> |>> https://www.solipsys.co.uk/images/FourHats.png ---- Four Hats <<| ]]] If person D can see two hats of the same colour then they can deduce the colour of their own hat and announce it pretty quickly. If they don't do that then as time drags on, person C realises that hats B and C cannot be the same colour. So person C can announce their hat as being the opposite of the hat they can see. In each case, someone can announce a hat colour. !! The Hundred Hats Solution. In this case we get the first person to count how many white hats they can see. If it's even they say "White", otherwise they say "Black". They have a 50:50 chance of surviving/winning. Bue the next person now knows the parity of the remaining number of white hats. They count the white hats and if they get the same parity then they know their hat is black, otherwise they know their hat is white, and in either case they act accordingly. Each person can keep a running total of what's happening, and so, provided they don't make a mistake, they can all save themselves. And even if someone makes a mistake, the others can detect that it happened and adjust accordingly. So all but the first person is guaranteed to be saved (provided they don't make a mistake), and the first person has a 50:50 chance. Not bad. !! And now, infinitely many mathematicians ... Back now to our infinitely many mathematicians with the randomly assigned hats. It seems impossible to do better than just 50:50 for everyone. If each can hear the answer of the one before then we can save all the even numbered people. In fact, we can "chunk" people into groups of 100 and save 99% of them. Or more! But that requires being able to hear the answers. If we can't hear the answers, the situation seems hopeless. But it isn't. There is a strategy to guarantee saving all but finitely many. Even though the hat assignment is random, and no one can hear anything anyone says, we can guarantee saving all but finitely many. !! AxiomOfChoice to the rescue ... Here is one strategy ... I'm sure there are others. [[[>50 What we are doing here is defining an equivalence relation on sequences, and then looking at the associated equivalence classes. We talked about this on the page about MathematicalRelations. ]]] The night before, consider all possible sequences of hat. Put one sequence into a bucket, and then into the same bucket put all the sequences that are eventually the same. That means that any two sequences from that bucket will only differ in finitely many places. Take another sequence, put that in another bucket, and do the same. Then again. And in fact, define buckets such that each bucket has sequences that differ in only finitely many places, and every sequence is in some bucket. The collection of buckets is a collection of non-empty sets. So by the perfectly reasonable AxiomOfChoice we can select one item from each bucket. This is our "Choice Set", and all of our mathematicians commit to memorising it. Now move forward in time to when we are in the room. The sequence of hats we can see was in one of the buckets, and from that bucket we have selected a particular "Chosen One". What's more, everyone knows which one it is. So now everyone, in their own mind, has the same chosen sequence, and that chosen sequence only differs from the sequence in the room at a finite number of places. So all the mathematicians call out, at their appointed time, the colour designated by the chosen sequence. And all but finitely many will be saved. !! Conclusion? There are, of course, a few possible objections to this. For one, look at how many buckets there must be, wonder about the ability of the mathematicians to remember all this information, and so on. But even with all that, the very possibility that the AxiomOfChoice *might* let us do this should raise some serious concerns. This isn't the only "paradoxical" result ---- |>> | |>> <<<< Prev <<<< ---- InDefenseOfTheAxiomOfChoice <<| | : | |>> >>>> Next >>>> ---- BackOfTheEnvelopeCOVID19 ... <<| | ---- ********> ''' <a href="https://mathstodon.xyz/@ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/images/Mastodon_Mascot.png" ''' width="256" height="280" ''' alt="https://mathstodon.xyz/@ColinTheMathmo" ''' /></a> ******** ''' <a href="https://mathstodon.xyz/@ColinTheMathmo/">You can follow me on Mathstodon.</a> _ _ _ _ [[[> ''' <a href="https://twitter.com/ColinTheMathmo">Of course, you can also<br>follow me on twitter:</a> ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> ''' <img src="/cgi-bin/CountHits.py?APointAgainstTheAxiomOfChoice" alt="" /> ]]] ********< ---- !! Send us a comment ... ''' <form action="https://www.solipsys.co.uk/cgi-bin/FormMail.pl" method=post> ''' <input type=hidden name="recipient" value="colinsblogcomment@solipsys.co.uk" > ''' <input type=hidden name="subject" value="Blog comment : APointAgainstTheAxiomOfChoice" > ''' <input type=hidden name="redirect" value="https://www.solipsys.co.uk/new/ThankYouForYourComment.html" > ''' <input type=hidden name="missing_fields_redirect" value="https://www.solipsys.co.uk/RequestError.html"> ''' <input type=hidden name="env_report" value="REMOTE_HOST, REMOTE_ADDR, HTTP_USER_AGENT" > ''' <input type=hidden name="print_blank_fields" value="1" > ********> width="47%" You can send us a message here. It doesn't get published, it just sends us an email, and is an easy way to ask any questions, or make any comments, without having to send a separate email. So just fill in the boxes and then ''' <font size="+4"><INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"></font> ******** width="53%" ********< ''' <table cellpadding="5"> ''' <tr> ''' <td valign="top">Your name </td> <td valign="top">:</td> ''' <td> <input type=text name="realname" size="48"> </td> ''' <tr> ''' <td valign="top">Email </td> <td valign="top">:</td> ''' <td> <input type=text name="email" size="48"> </td> ''' </tr> ''' <tr> ''' <td valign="top">Message </td> <td valign="top">:</td> ''' <td> <TEXTAREA NAME="Message" ROWS=10 COLS=64></TEXTAREA> </td> ''' </tr> ''' </table> ''' <center> ''' <font size="+4"> ''' <INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"> ''' </font> ''' </center> ''' </form> ********<