Non-Constructive

In 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 Banach-Tarski 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 Banach-Tarski 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 Hahn-Banach 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

• The axiom of choice isn’t usually included as part of computer science. It is considered more part of pure math than computation. However, it is related to the idea of computablity and therefore deserves consideration.

• The axiom of choice simply says that in all circumstances it is possible to select one thing from each set in a collection. Equivalently you can postulate the existence of a choice function which gives you one element from each set. If the choice function is non-computable the axiom of choice is false.

• There are lots of examples where the axiom of choice is obviously true and a few well known examples where it is far from obvious. The problems arise when the sets in question are uncountable and there are an uncountable number of them.

• If you try to select a single point from a set of all subsets of the real numbers you can see that we have a problem in proving that for whatever rule we select a suitable point exists. This may be regarded as another example of not enough functions/programs to compute everything that is aleph-one.

• The solution of “pick a point at random” doesn’t really help because it challenges what it means to “pick a point”. The only meaningful sense in which you can pick a point is to give a description, or program, that lets you find it. Failing this you have to label it in some way and there are neither enough programs nor labels.

• If the axiom of choice is false many reasonable theorems are also false. If it is true then so is the Banach-Tarski paradox, that you can take a 3D sphere and rearrange its points to create two such spheres of the same size.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem ***NEW!
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. Splitting the Bit 
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<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

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info