Programmer's Guide To Theory  The Algorithm of Choice 
Written by Mike James  
Tuesday, 15 August 2023  
Page 3 of 3
NonConstructiveIn mathematics the axiom of choice is usually invoked to suppose that there is a choice function without having to explicitly supply one  and this leads to conclusions that might not undisputed paradoxes but can be very troubling. The problem is that just insisting that a procedure can be done without explaining how it can be done isn't constructive. It leads to mathematics with objects and procedures which provably exist without giving the exact algorithm to create such an object. For example, the best known is the BanachTarski paradox which says that if you take a 3D solid unit sphere you can "carve it up" into a finite number of pieces and then using rotations and translations reassemble it into two identical 3D solid unit spheres. We seem to have created twice the volume of stuff without actually creating anything at all. The pieces are constructed using the axiom of choice but obviously without giving the choice function used to do the job. If you think that doubling the volume of stuff is simply a crazy illogical idea then you are forgetting some of the strange properties of infinity. Take an infinite set of the integers and split it into a set or even and a set of odd integers  both sets are also infinite. So you start with an infinite set and split it in two and you have two infinite sets  perfectly logical. In the case of the BanachTarski paradox the sets aren't of infinite extent i.e they are bounded but they are continuous and hence have aleph one points. In the same way as the countable sets can be split into two parts each infinite so the ball can be split into two parts each with aleph one points inside. However to do this you have to be able to select an aleph one number of points from an aleph one number of sets i.e. a choice function must exist. If you think that this is just silly and proof that the axiom of choice isn't valid, then you need to know just how many results in less controversial mathematics depend on it. For example, every Hilbert space has an orthonormal basic, the HahnBanach theorem, the additive groups on R and C are isomorphic, the theorem that every countable union of countable sets is countable and so on... they are all fairly basic properties that we expect to be true. At the end of the day the axiom of choice is more illuminating about the properties of infinite sets than anything else. Mathematics makes use of it but there is a certain caution about theorems that rely on it. xkcd's math teacher can rest assured that as long as the sets are restricted to a finite collection then it is always possible to pick an element for execution  but when we get to infinite collections then you have to enforce the axiom of choice first. More cartoon fun at xkcd a webcomic of romance,sarcasm, math, and language Perhaps it is the axiom of choice that should be executed. Summary
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.Contents
<ASIN:1871962439> <ASIN:1871962587> To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@iprogrammer.info


Last Updated ( Tuesday, 15 August 2023 ) 