Part III: Mathematical Concepts, III.1 The Axiom of Choice: Page 157.

If a and b are irrational numbers then can ab be rational?  A proof of this is as follows.  Let x = √2√2.  Now either x is rational or it is irrational.  If x is rational then we have irrational numbers, a and b, where ab is rational, namely √2√2.  If x is irrational then we can have irrational numbers a = √2 and  b = √2√2 with ab = (√2√2)√2 = √222  and hence ab2 is rational.  This is called a nonconstructive proof.  Because in the end even though we proved the proposition in which we were interested we do not know which a and b satisfy the proposition.  In this proof we have used the law of the excluded middle.

The axiom of choice can be used to build sets out of other sets.  The power set axiom says that given a set A we can form the set of all subsets of A.  The axiom of comprehension is that for any set A and property p we can form the set of all elements of A that satisfy p.  The axiom of choice is similar and says that we can make an arbitrary number of unspecified choices in order to form a new set.

The axiom of choice is often so natural that we may not realize that it is being used.  One example is in the proof that the union of a countable number of sets of a countable number of objects is itself countable.  The axiom of choice is used in the direct proof of this and it is a nonconstructive proof.

Another example is in graph theory to prove that an infinite disjoint union of even cycles is bipartite.  A bipartite graph is one where the vertices of the graph can be split into two classes X and Y in such a way that no two vertices in the same class are connected by an edge (of the original graph). 

Leave a Reply

You must be logged in to post a comment.