{"id":430,"date":"2007-05-27T17:43:05","date_gmt":"2007-05-27T17:43:05","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/05\/27\/the-axiom-of-choice\/"},"modified":"2007-05-27T17:43:05","modified_gmt":"2007-05-27T17:43:05","slug":"the-axiom-of-choice","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/05\/27\/the-axiom-of-choice\/","title":{"rendered":"The Axiom of Choice"},"content":{"rendered":"

The Axiom of Choice
\nThe axiom of choice is a fascinating bugger. It’s probably the most controversial statement in mathematics in the last century – which is pretty serious, considering the kinds of things that have gone on in math during the last century.<\/p>\n

The axiom itself is quite simple, and reading an informal description of it, it’s difficult to understand how it managed to cause so much trouble. For example, wikipedia<\/a> has a rather nice informal statement of it: <\/p>\n

\ngiven a collection of bins each containing at least one object, exactly one object from each bin can be picked and gathered in another bin\n<\/p><\/blockquote>\n

<\/p>\n

There are also a bunch of statements that are equivalent to that – some of which can be pretty astonishingly different, so that it can be quite difficult to see why they’re equivalent. So, for example, here are a few equivalent formulations:<\/p>\n

\n
    \n
  • Given any two sets, one set has cardinality less than or equal to that of the other set — i.e., one set is in one-to-one correspondence with some subset of the other. <\/li>\n
  • Any vector space over a field F has a basis — i.e., a maximal linearly independent subset — over that field. <\/li>\n
  • Any product of compact topological spaces is compact. <\/li>\n
  • Any set of non-empty sets has a non-empty cross-product.<\/li>\n<\/ul>\n<\/blockquote>\n

    The first of those alternative formulations shows why the axiom of choice is so important – and why it’s so controversial. It’s the axiom of set theory that lets us compare the cardinality of sets, and therefore (among other things) makes Cantor’s diagonalization work in axiomatic set theory.<\/p>\n

    How do we get from the simple statement that given a collection of non-empty bins, we can select one item from each bin, to the seemingly more profound statement that for any two sets – even infinite ones, one has cardinality less than or equal to the cardinality of the other?<\/p>\n

    Let’s start with the simple statement, but add a bit of detail: Given a collection of not-empty bins, it’s possible to select one item from each bin. One added detail is that this works even if there’s an infinite number of sets. Another one is that you don’t need to be able to specify a rule to describe how<\/em> to do the selection.<\/p>\n

    Now, with that restatement, we can, instead say: for any class of non-empty sets X, there exists a choice function<\/em> f such that for each x∈X, f(x)∈x. <\/p>\n

    Next, we can go from that statement to something a little closer, by saying that for anf set X of non-empty sets, where S∈X, and p∈S, then there is a choice function f on X such that f(S)=p. And further, for any set<\/em> of values {pi<\/sub> : i∈X and pi<\/sub>∈i}, there is a choice function f on X where f(i)=pi<\/sub>.<\/p>\n

    From that, it’s relatively straightforward to get an infinite set of choice functions assigning a relationship between members of different sets of X. And that<\/em> in turn gives us the result that we want: if we have a pair of sets S and T, then one of two things can happen: either there’s a set of choice functions that creates a one-to-one map between S and T, or there isn’t. If there is, then the two sets have the same cardinality. If not, then one set is smaller than the other.<\/p>\n

    That argument shows why the axiom of choice has been so controversial: it’s all about arguments<\/em> for existence, with no way to construct<\/em> the things that we argue must exist. In fact, there are cases where we can prove<\/em> that something exists, and also prove that there is no algorithm to tell us how to construct it. In fact, these cases are exactly the ones that require the axiom of choice. If we know how to construct the choice functions, we don’t need the axiom: the axiom buys us the ability to work without the ability to construct specific choice functions.<\/p>\n

    So the problem with it is that it embodies the things about set theory that many people disliked from the start. When Cantor was originally formulating what became set theory, one of the extremely popular mathematical philosophies was constructionism. Constructionism basically argues that something only exists if you can construct it: that existence proofs that don’t tell you how to create something, but only argue that it must exist, are artifacts of logic. So by this argument, all of the things that the axiom of choice are completely meaningless artifacts of silly logic. <\/p>\n

    To give you a sense of the environment in which this was born: Leopold Kronecker, one of the early critics of set theory was famously quoted as responding to a paper describing the properties of π by saying, roughly, “Why are you wasting your time studying something which doesn’t exist?” The idea behind that criticism is that you can’t<\/em> write the precise definition of π; and you can’t draw a perfect circle where the ratio between diameter and circumference is really precisely the theoretical value of π. So π only exists in theory.<\/p>\n

    If a finitist\/constructivist like Kronecker had disagreements with the existence of π, then you can imagine just how much trouble he’d have with something whose entire purpose was to let people write non-constructivist proofs!<\/p>\n

    To make matters worse, the first major application of the axiom of choice was
    \nto prove that different infinities have different sizes. But according to finitist\/constructivist arguments, infinity doesn’t actually exist<\/em>: it’s just
    \na concept. How do you compare the sizes of non-existant concepts? It’s like asking who smells better: the invisible pink unicorn, or the great purple arklesnesure? From the constructivist point of view, it’s a meaningless question. So what do you make out of an argument that uses this axiom to describe non-constructable functions to prove differences between non-existent abstractions?<\/p>\n

    But in the end, Cantor and his successors won out. Now the axiom of choice is pretty much universally acknowledged as valid, and the constructivists – and particularly the finitist\/constructivists – were just plain wrong. Constructivism still comes up in analysis, where the point is to find answers, but it’s mostly a dead issue in abstract math. In the words of Hilbert, “No one shall expel us from the Paradise that Cantor has created.”<\/p>\n","protected":false},"excerpt":{"rendered":"

    The Axiom of Choice The axiom of choice is a fascinating bugger. It’s probably the most controversial statement in mathematics in the last century – which is pretty serious, considering the kinds of things that have gone on in math during the last century. The axiom itself is quite simple, and reading an informal description […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[56],"tags":[],"class_list":["post-430","post","type-post","status-publish","format-standard","hentry","category-set-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-6W","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/430","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=430"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/430\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=430"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}