{"id":439,"date":"2007-06-07T16:47:36","date_gmt":"2007-06-07T16:47:36","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/06\/07\/why-choice-is-important-the-well-ordering-theorem\/"},"modified":"2007-06-07T16:47:36","modified_gmt":"2007-06-07T16:47:36","slug":"why-choice-is-important-the-well-ordering-theorem","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/06\/07\/why-choice-is-important-the-well-ordering-theorem\/","title":{"rendered":"Why Choice is Important: The Well-Ordering Theorem"},"content":{"rendered":"

One of the reasons that the axiom of choice is so important, and so necessary, is that there are a lot of important facts from other fields of mathematics that we’d like to define in terms of set theory, but which either require the AC, or are equivalent to the AC.
\nThe most well-known of these is called the well-ordering theorem<\/em>, which is fully equivalent to the axiom of choice. What it says is that every set has a well-ordering. Which doesn’t say much until we define what well-ordering means. The reason that it’s so important is that the well-ordering theorem means that a form of inductive proof, called transfinite induction<\/em> can be used on all<\/em> sets.<\/p>\n


\nWhat’s well-ordering?
\nA set S is well-ordered<\/em> if and only if:
\n* There is a total ordering relation ◊ on S;
\n* Every non-empty subset T ⊆ S has a least element<\/em> l : ∀t∈T, t≠l, l◊t.
\nNote that these definitions mean that there must be a least<\/em> element of the set; and that there can<\/em> be a greatest greatest.
\nThese two properties mean that every element (except the greatest, if there is one) e∈S has a unique successor under ◊: the least element of the set {x : e◊x}. By the same reasoning, it also means that every set with an upper bound has a least<\/em> upper bound.
\nIt’s easy to show that ≤ works as an ordering relation for showing that the natural numbers are well-ordered. But it doesn’t<\/em> work for showing that the integers are well-ordered: ≤ has no least value for the set of negative integers. But we can easily define a well-ordering relation on the integers:
\n* x◊y =
\n* x is zero and y is non-zero
\n* x is positive and y is negative.
\n* x and y are both positive and x≤y.
\n* x and y are both negative and y≤x.
\nThis gives us an ordering of the set 0, -1, 1, -2, 2, -3, 3, …
\nThe real numbers are where the axiom of choice comes in. We can’t show a well-ordering of the reals. But the axiom of choice tells us that one exists.
\nIn fact, by the axiom of choice, the well-ordering theorem is provable, which means that every<\/em> set has a well-ordering. And if every set is well-ordered, then we can use induction on the set using the following construction, called transfinite induction:
\nSuppose we have a set S, and a predicate P. We want to prove that P is true for all members of S. We can prove this using the well-ordering relation ◊ of S by showing:
\n* P(l) is true where l is the least element of S under ◊.
\n* For all x ∈ S: P(x) is true if P(y) is true for all y◊x∈S.
\nWith the well-ordering theorem, we now have a way of applying induction to *all* sets; and therefore to use induction for proofs in any of the mathematical theories derivable from set theory. Without the axiom of choice, we wouldn’t have this ability, and without induction, our ability to prove all manner of important theorems would be lost.<\/p>\n","protected":false},"excerpt":{"rendered":"

One of the reasons that the axiom of choice is so important, and so necessary, is that there are a lot of important facts from other fields of mathematics that we’d like to define in terms of set theory, but which either require the AC, or are equivalent to the AC. The most well-known of […]<\/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-439","post","type-post","status-publish","format-standard","hentry","category-set-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-75","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/439","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=439"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/439\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=439"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=439"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=439"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}